bad char

[vg.git] / src / vg / vg_store.h

#ifndef VG_STORE_H
#define VG_STORE_H

typedef struct aatree aatree;
typedef struct aatree_node aatree_node;

typedef u32 aatree_ptr;
#define AATREE_PTR_NIL 0xffffffff

struct aatree
{
   u32 offset, stride; /* distance between elements */
   void *base;

   int (*p_cmp)( void *a, void *b );
   int (*p_cmpv)( void *a, void *v );
};

struct aatree_node
{
   aatree_ptr left, right, parent;
   u32 level, count;
};

static void *aatree_get_data( aatree *tree, aatree_ptr t )
{
   return tree->base + tree->stride*t;
}

static aatree_node *aatree_get_node( aatree *tree, aatree_ptr t )
{
   return tree->base + tree->stride*t + tree->offset;
}

static void aatree_recount( aatree *tree, aatree_ptr n )
{
   aatree_node *pnode = aatree_get_node( tree, n );
   pnode->count = 1;

   if( pnode->left != AATREE_PTR_NIL )
      pnode->count += aatree_get_node( tree, pnode->left )->count;

   if( pnode->right != AATREE_PTR_NIL )
      pnode->count += aatree_get_node( tree, pnode->right )->count;
}

/*         .            .
 *         |            |
 *    L <- T            L -> T
 *   / \    \    ->    /    / \
 *  A   B    R        A    B   R
 */
static aatree_ptr aatree_skew( aatree *tree, u32 t )
{
   if( t == AATREE_PTR_NIL ) return t;

   aatree_node *ptnode = aatree_get_node( tree, t );
   if( ptnode->left == AATREE_PTR_NIL ) return t;

   aatree_node *plnode = aatree_get_node( tree, ptnode->left );
   if( plnode->level == ptnode->level )
   {
      aatree_ptr l = ptnode->left;
      ptnode->left = plnode->right;
      plnode->right = t;

      aatree_recount( tree, t );
      aatree_recount( tree, l );

      /* B's parent is now T,
       * T's parent is now L,
       * L's parent is now T's old parent */
      plnode->parent = ptnode->parent;
      ptnode->parent = l;
      if( ptnode->left != AATREE_PTR_NIL )
         aatree_get_node( tree, ptnode->left )->parent = t;

      return l;
   }

   return t;
}

/*    .                    .
 *    |                    |
 *    T -> R -> X   ->     R
 *   /    /               / \
 *  A    B               T   X
 *                      / \
 *                     A   B
 */
static aatree_ptr aatree_split( aatree *tree, aatree_ptr t )
{
   if( t == AATREE_PTR_NIL ) return t;

   aatree_node *ptnode = aatree_get_node( tree, t );
   if( ptnode->right == AATREE_PTR_NIL ) return t;

   aatree_node *prnode = aatree_get_node( tree, ptnode->right );
   if( prnode->right == AATREE_PTR_NIL ) return t;

   aatree_node *prrnode = aatree_get_node( tree, prnode->right );
   if( ptnode->level == prrnode->level )
   {
      aatree_ptr r = ptnode->right;
      ptnode->right = prnode->left;
      prnode->left = t;
      prnode->level ++;

      aatree_recount( tree, t );
      aatree_recount( tree, r );

      /* B's parent is now T,
       * T's parent is now R,
       * R's parent is now T's old parent */
      prnode->parent = ptnode->parent;
      ptnode->parent = r;
      if( ptnode->right != AATREE_PTR_NIL )
         aatree_get_node( tree, ptnode->right )->parent = t;

      return r;
   }

   return t;
}

static int aatree_verify( aatree *tree, aatree_ptr t );

static aatree_ptr aatree_insert( aatree *tree, aatree_ptr t, aatree_ptr x )
{
   aatree_node *pxnode = aatree_get_node( tree, x );

   if( t == AATREE_PTR_NIL )
   {
      pxnode->left = AATREE_PTR_NIL;
      pxnode->right = AATREE_PTR_NIL;
      pxnode->parent = AATREE_PTR_NIL;
      pxnode->level = 0;
      pxnode->count = 1;
      return x;
   }

   aatree_node *ptnode = aatree_get_node( tree, t );
   int cmp_result = tree->p_cmp( aatree_get_data( tree, t ), 
                                 aatree_get_data( tree, x ) );

   ptnode->count ++;

   if( cmp_result <= 0 )
   {
      ptnode->left = aatree_insert( tree, ptnode->left, x );
      aatree_node *plnode = aatree_get_node( tree, ptnode->left );
      plnode->parent = t;
   }
   else
   {
      ptnode->right = aatree_insert( tree, ptnode->right, x );
      aatree_node *prnode = aatree_get_node( tree, ptnode->right );
      prnode->parent = t;
   }

   t = aatree_skew( tree, t );
   t = aatree_split( tree, t );
   return t;
}

static void aatree_link_down( aatree *tree, aatree_ptr p, aatree_ptr *pl,
                              aatree_ptr l )
{
   *pl = l;

   if( *pl != AATREE_PTR_NIL )
      aatree_get_node( tree, *pl )->parent = p;
}

static aatree_ptr aatree_del( aatree *tree, aatree_ptr x )
{
   /* Simulate what we would have created on the tail,
    * we work along the tail in order, doing the same as the regular
    * implementation. This only works because we have parent pointers. */
   
   aatree_ptr it = x,
              up[32];

   int count = 1, dir = 0;
   
   aatree_node *search = aatree_get_node( tree, x );
   while(1)
      if( search->parent == AATREE_PTR_NIL ) break;
      else
      {
         search = aatree_get_node( tree, search->parent );
         count ++;
      }

   int top=0;
   while(1)
   {
      int index = count - (++top);

      up[ index ] = it;
      aatree_node *itnode = aatree_get_node( tree, it );
      if( itnode->parent == AATREE_PTR_NIL )
         break;
      else
         it = itnode->parent;
   }
   
   aatree_ptr _ptrswap_src = AATREE_PTR_NIL,
              _ptrswap_dst = AATREE_PTR_NIL;

   aatree_node *pxnode = aatree_get_node( tree, x );
   aatree_ptr root = up[ count-1 ];
   if( pxnode->left == AATREE_PTR_NIL || pxnode->right == AATREE_PTR_NIL )
   {
      if( --top != 0 )
      {
         aatree_node *pnode = aatree_get_node( tree, up[top-1] ),
                     *parent = aatree_get_node( tree, pxnode->parent );
         
         aatree_ptr next = pxnode->left == AATREE_PTR_NIL?
                           pxnode->right:
                           pxnode->left;

         if( parent->left == x ) pnode->left = next;
         else pnode->right = next;
         
         if( next != AATREE_PTR_NIL )
         {
            aatree_node *pnext = aatree_get_node( tree, next );
            pnext->parent = up[top-1];
         }
      }
      else
      {
         if( pxnode->right != AATREE_PTR_NIL ) root = pxnode->right;
         else if( pxnode->left != AATREE_PTR_NIL ) root = pxnode->left;
         else return AATREE_PTR_NIL;

         aatree_node *newroot = aatree_get_node( tree, root );
         newroot->parent = AATREE_PTR_NIL;
      }
   }
   else
   {
      aatree_ptr heir = pxnode->right,
                 prev = x;

      aatree_node *pheir = aatree_get_node( tree, heir );
      
      while( pheir->left != AATREE_PTR_NIL )
      {
         up[top++] = prev = heir;
         heir = pheir->left;
         pheir = aatree_get_node( tree, heir );
      }
      
      _ptrswap_dst = heir;
      _ptrswap_src = x;

      aatree_node *pprev = aatree_get_node( tree, prev );
      
      if( prev == x )
         aatree_link_down( tree, prev, &pprev->right, pheir->right );
      else
         aatree_link_down( tree, prev, &pprev->left, pheir->right );
   }

   while( --top >= 0 )
   {
      if( top != 0 )
      {
         aatree_node *above = aatree_get_node( tree, up[top-1] );
         dir = above->right == up[top];
      }

      aatree_recount( tree, up[top] );
      aatree_node *pntop = aatree_get_node( tree, up[top] );
      if( pntop->left == AATREE_PTR_NIL || pntop->right == AATREE_PTR_NIL ){}
      else 
      {
         aatree_node
                  *pnl   = aatree_get_node( tree, pntop->left ),
                  *pnr   = aatree_get_node( tree, pntop->right );
         
         if( pnl->level < pntop->level-1 || pnr->level < pntop->level-1 )
         {
            if( pnr->level > --pntop->level )
               pnr->level = pntop->level;

            up[top] = aatree_skew( tree, up[top] );

            aatree_node *ut = aatree_get_node( tree, up[top] );
            ut->right = aatree_skew( tree, ut->right );

            aatree_node *utr = aatree_get_node( tree, ut->right );
            utr->right = aatree_skew( tree, utr->right );

            up[top] = aatree_split( tree, up[top] );
            ut = aatree_get_node( tree, up[top] );

            ut->right = aatree_split( tree, ut->right );
         }
      }

      if( top != 0 )
      {
         aatree_node *ut1 = aatree_get_node( tree, up[top-1] );
         
         if( dir == 1 )
            aatree_link_down( tree, up[top-1], &ut1->right, up[top] );
         else
            aatree_link_down( tree, up[top-1], &ut1->left, up[top] );
      }
      else
      {
         root = up[top];
         aatree_get_node( tree, root )->parent = AATREE_PTR_NIL;
      }
   }

   if( _ptrswap_dst != AATREE_PTR_NIL )
   {
      /* Copy everything except data from _src to _dst, relink.
       * This is a bit of a messy addon, since the algorithm is originally 
       * based around moving the actual data(key) around, but we have the 
       * requirement that data can't move, so everything is done normally but 
       * the pointers are just swapped afterwards. 
       */

      aatree_node *pdst = aatree_get_node( tree, _ptrswap_dst ),
                  *psrc = aatree_get_node( tree, _ptrswap_src );

      pdst->count = psrc->count;
      pdst->level = psrc->level;
      pdst->left = psrc->left;
      pdst->right = psrc->right;
      pdst->parent = psrc->parent;
      
      if( pdst->parent != AATREE_PTR_NIL )
      {
         aatree_node *parent = aatree_get_node( tree, pdst->parent );

         if( parent->left == _ptrswap_src )
            parent->left = _ptrswap_dst;
         else if( parent->right == _ptrswap_src )
            parent->right = _ptrswap_dst;
      }
      else
      {
         root = _ptrswap_dst;
      }

      if( pdst->left != AATREE_PTR_NIL )
         aatree_get_node( tree, pdst->left )->parent = _ptrswap_dst;
      if( pdst->right != AATREE_PTR_NIL )
         aatree_get_node( tree, pdst->right )->parent = _ptrswap_dst;
   }

   return root;
}

/*
 * Accessors
 */

static aatree_ptr aatree_kth( aatree *tree, aatree_ptr t, u32 k )
{
   u32 i = 0;

   while( t != AATREE_PTR_NIL )
   {
      aatree_node *ptnode = aatree_get_node( tree, t );
      
      u32 j = i;
      if( ptnode->left != AATREE_PTR_NIL )
         j += aatree_get_node( tree, ptnode->left )->count;

      if( j < k )
      {
         i = j+1;
         t = ptnode->right;
      }
      else
      {
         if( j > k )
         {
            t = ptnode->left;
         }
         else
         {
            return t;
         }
      }
   }

   return AATREE_PTR_NIL;
}

static aatree_ptr aatree_ptrof( aatree *tree, aatree_ptr t, void *value )
{
   while( t != AATREE_PTR_NIL )
   {
      int cmp_result = tree->p_cmpv( aatree_get_data( tree, t ), value );

      if( cmp_result == 0 )
         return t;
      else 
      {
         aatree_node *ptnode = aatree_get_node( tree, t );

         if( cmp_result < 0 )
            t = ptnode->left;
         else
            t = ptnode->right;
      }
   }
   return t;
}


/*
 * Debugging stuff, everything below is scaffholding and will be removed
 * =============================================================================
 */

static int aatree_verify_split( aatree *tree, aatree_ptr t )
{
   if( t == AATREE_PTR_NIL ) return 1;

   aatree_node *ptnode = aatree_get_node( tree, t );
   if( ptnode->right == AATREE_PTR_NIL ) return 1;

   aatree_node *prnode = aatree_get_node( tree, ptnode->right );
   if( prnode->right == AATREE_PTR_NIL ) return 1;

   aatree_node *prrnode = aatree_get_node( tree, prnode->right );
   if( ptnode->level == prrnode->level )
      return 0;

   return 1;
}

static int aatree_verify_skew( aatree *tree, aatree_ptr t )
{
   if( t == AATREE_PTR_NIL ) return 1;

   aatree_node *ptnode = aatree_get_node( tree, t );
   if( ptnode->left == AATREE_PTR_NIL ) return 1;

   aatree_node *plnode = aatree_get_node( tree, ptnode->left );
   if( plnode->level == ptnode->level )
      return 0;

   return 1;
}

static int aatree_verify( aatree *tree, aatree_ptr t )
{
   aatree_node *ptnode = aatree_get_node( tree, t );
   if( ptnode->parent != AATREE_PTR_NIL )
   {
      aatree_node *parent = aatree_get_node( tree, ptnode->parent );
      if( !(parent->left == t || parent->right == t) )
         return 0;
   }

   if( ptnode->left != AATREE_PTR_NIL )
      if( aatree_get_node( tree, ptnode->left )->parent != t )
         return 0;
   if( ptnode->right != AATREE_PTR_NIL )
      if( aatree_get_node( tree, ptnode->right )->parent != t )
         return 0;

   return aatree_verify_skew( tree, t ) &&
          aatree_verify_split( tree, t );
}


static void aatree_show_r( aatree *tree, aatree_ptr t, int lvl, 
                           void(*p_show)(void *data) )
{
   if( t != AATREE_PTR_NIL )
   {
      aatree_node *ptnode = aatree_get_node( tree, t );
      aatree_show_r( tree, ptnode->left, lvl+1, p_show );

      void *data = aatree_get_data( tree, t );

      for( int i=0; i<lvl; i++ )
      {
         printf( "  " );
      }
      p_show( data );
      printf( " (%d) \n", t );

      aatree_show_r( tree, ptnode->right, lvl+1, p_show );
   }
}

static void aatree_show( aatree *tree, aatree_ptr t, void(*p_show)(void *data))
{
   if( t != AATREE_PTR_NIL )
   {
      aatree_node *ptnode = aatree_get_node( tree, t );
      aatree_show( tree, ptnode->left, p_show );
      void *data = aatree_get_data( tree, t );

      for( int i=0; i<ptnode->level; i++ )
      {
         printf( "  " );
      }
      p_show( data );
      printf( " (%d) \n", t );

      aatree_show( tree, ptnode->right, p_show );
   }
}

static void aatree_show_counts( aatree *tree, aatree_ptr t, int lvl, int *ln,
                                 int *err,
                                void(*p_show)(void *data), int show )
{
   if( lvl > 20 )
      return;
   if( t == AATREE_PTR_NIL ) return;

   aatree_node *ptnode = aatree_get_node( tree, t );
   void *data = aatree_get_data( tree, t );

   aatree_show_counts( tree, ptnode->left, lvl+1, ln, err, p_show, show );

   if( show ) printf( "    %03d| ", *ln );
   *ln = *ln +1;

   if( show ) 
      for( int i=0; i<lvl; i++ )
         printf( "   " );

   if( show )
   {
      p_show( data );

      if( ptnode->left != AATREE_PTR_NIL && ptnode->right != AATREE_PTR_NIL )
         printf( "|" );
      if( ptnode->left != AATREE_PTR_NIL && ptnode->right == AATREE_PTR_NIL )
         printf( "/" );
      if( ptnode->left == AATREE_PTR_NIL && ptnode->right != AATREE_PTR_NIL )
         printf( "\\" );

      printf( " (%d, %d, parent: %d. V: %d, level: %d) \n", t, 
            ptnode->count, ptnode->parent,
            aatree_verify( tree, t ), ptnode->level);
   }

   if( !aatree_verify( tree, t ) )
   {
      if( show )
         printf( "error\n" );
      *err = 1;
   }

   aatree_show_counts( tree, ptnode->right, lvl+1, ln, err, p_show, show );
}

#endif /* VG_STORE_H */