X-Git-Url: https://harrygodden.com/git/?a=blobdiff_plain;f=src%2Fvg%2Fvg_store.h;h=ee0e91acf04d3e94579b1f62c7dfafda8d322a9d;hb=5071899d6840f99825d0eaab4132a0bf27646938;hp=3684ff7113db790a4ce3d21d5f31b3f6b12915c1;hpb=ca04f71f6e1cb30ca3dbb97c700b134deef25bf7;p=vg.git

diff --git a/src/vg/vg_store.h b/src/vg/vg_store.h
index 3684ff7..ee0e91a 100644
--- a/src/vg/vg_store.h
+++ b/src/vg/vg_store.h
@@ -1,8 +1,22 @@
 #ifndef VG_STORE_H
 #define VG_STORE_H
 
+#include "vg_stdint.h"
+#include "vg_io.h"
+#include "vg_log.h"
+
+/* 
+ * Anderson tree implementation with extensions:
+ *   parents are kept track of
+ *   duplicates are allowed
+ *   data is never allocated or destroyed here
+ *
+ * TODO: seperate offset,stride,base into 'generic array', seperate pool
+ */
+
 typedef struct aatree aatree;
 typedef struct aatree_node aatree_node;
+typedef struct aatree_pool_node aatree_pool_node;
 
 typedef u32 aatree_ptr;
 #define AATREE_PTR_NIL 0xffffffff
@@ -13,23 +27,67 @@ struct aatree
    void *base;
 
    int (*p_cmp)( void *a, void *b );
-   int (*p_cmpv)( void *a, void *v );
 };
 
+#pragma pack(push,1)
 struct aatree_node
 {
-   aatree_ptr left, right;
+   aatree_ptr left, right, parent;
    u32 level, count;
 };
 
+struct aatree_pool_node 
+{
+   aatree_ptr next_free;
+};
+#pragma pack(pop)
+
+/* api 
+ * ===========================================================================*/
+
+/* return a pointer to the start of the data referenced by t */
+static void *aatree_get_data( aatree *tree, aatree_ptr t );
+
+/* link node x into the tree with root t */
+static aatree_ptr aatree_insert( aatree *tree, aatree_ptr t, aatree_ptr x );
+
+/* delete node x from tree, does not free memory */
+static aatree_ptr aatree_del( aatree *tree, aatree_ptr x );
+
+/* get pointer to element in tree with index k */
+static aatree_ptr aatree_kth( aatree *tree, aatree_ptr t, u32 k );
+
+/* get pointer to the element above x */
+static aatree_ptr aatree_next( aatree *tree, aatree_ptr x );
+
+/* get pointer by value, returns NIL if not found.
+ *
+ * if duplicates values are present then the result is undefined, but it will be
+ * AN node with that value, just maybe not the first lexicographically
+ */
+static aatree_ptr aatree_find( aatree *tree, aatree_ptr t, void *value );
+
+/* implementation 
+ * ===========================================================================*/
+
 static void *aatree_get_data( aatree *tree, aatree_ptr t )
 {
-   return tree->base + tree->stride*t;
+   return (u8 *)tree->base + tree->stride*t;
+}
+
+static u8 *aatree_node_base( aatree *tree, aatree_ptr t )
+{
+   return (u8 *)tree->base + tree->stride*t + tree->offset;
+}
+
+static aatree_pool_node *aatree_get_pool_node( aatree *tree, aatree_ptr t )
+{
+   return (aatree_pool_node *)aatree_node_base( tree, t );
 }
 
 static aatree_node *aatree_get_node( aatree *tree, aatree_ptr t )
 {
-   return tree->base + tree->stride*t + tree->offset;
+   return (aatree_node *)aatree_node_base( tree, t );
 }
 
 static void aatree_recount( aatree *tree, aatree_ptr n )
@@ -67,6 +125,11 @@ static aatree_ptr aatree_skew( aatree *tree, u32 t )
       aatree_recount( tree, t );
       aatree_recount( tree, l );
 
+      plnode->parent = ptnode->parent;
+      ptnode->parent = l;
+      if( ptnode->left != AATREE_PTR_NIL )
+         aatree_get_node( tree, ptnode->left )->parent = t;
+
       return l;
    }
 
@@ -102,6 +165,11 @@ static aatree_ptr aatree_split( aatree *tree, aatree_ptr t )
       aatree_recount( tree, t );
       aatree_recount( tree, r );
 
+      prnode->parent = ptnode->parent;
+      ptnode->parent = r;
+      if( ptnode->right != AATREE_PTR_NIL )
+         aatree_get_node( tree, ptnode->right )->parent = t;
+
       return r;
    }
 
@@ -116,6 +184,7 @@ static aatree_ptr aatree_insert( aatree *tree, aatree_ptr t, aatree_ptr x )
    {
       pxnode->left = AATREE_PTR_NIL;
       pxnode->right = AATREE_PTR_NIL;
+      pxnode->parent = AATREE_PTR_NIL;
       pxnode->level = 0;
       pxnode->count = 1;
       return x;
@@ -124,28 +193,210 @@ static aatree_ptr aatree_insert( aatree *tree, aatree_ptr t, aatree_ptr 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 aatree_ptr aatree_del( aatree *tree, aatree_ptr t, aatree_ptr x )
+static void aatree_link_down( aatree *tree, aatree_ptr p, aatree_ptr *pl,
+                              aatree_ptr l )
 {
-   if( t == AATREE_PTR_NIL ) return t;
-   return AATREE_PTR_NIL; /*TODO*/
+   *pl = l;
+
+   if( *pl != AATREE_PTR_NIL )
+      aatree_get_node( tree, *pl )->parent = p;
 }
 
-/*
- * Accessors
- */
+static aatree_ptr aatree_copy_links( aatree *tree, aatree_ptr root,
+                                     aatree_ptr src, aatree_ptr dst )
+{
+   aatree_node *pdst = aatree_get_node( tree, dst ),
+               *psrc = aatree_get_node( tree, src );
+
+   pdst->count = psrc->count;
+   pdst->level = psrc->level;
+   pdst->parent = psrc->parent;
+
+   aatree_link_down( tree, dst, &pdst->left, psrc->left );
+   aatree_link_down( tree, dst, &pdst->right, psrc->right );
+   
+   if( pdst->parent != AATREE_PTR_NIL )
+   {
+      aatree_node *parent = aatree_get_node( tree, pdst->parent );
+
+      if( parent->left == src )
+         parent->left = dst;
+      else if( parent->right == src )
+         parent->right = dst;
+   }
+   else
+      return dst;
+
+   return root;
+}
+
+static aatree_ptr aatree_del( aatree *tree, aatree_ptr x )
+{
+   aatree_ptr it = x,
+              up[32];
+
+   int count = 1, dir = 0;
+   
+   /* TODO: maybe be a better way to do this, without counting back up */
+   for( aatree_node *s = aatree_get_node( tree, x ); 
+         s->parent != AATREE_PTR_NIL;
+         count ++ )
+      s = aatree_get_node( tree, s->parent );
+
+   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 );
+   }
+
+   /* Tail */
+   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) )
+      {
+         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;
+      }
+   }
+   
+   /* This is our extension to the original non-recursive delete, so no data
+    * has to be moved */
+   if( _ptrswap_dst != AATREE_PTR_NIL )
+      root = aatree_copy_links( tree, root, _ptrswap_src, _ptrswap_dst );
+
+   return root;
+}
 
 static aatree_ptr aatree_kth( aatree *tree, aatree_ptr t, u32 k )
 {
@@ -154,7 +405,7 @@ static aatree_ptr aatree_kth( aatree *tree, aatree_ptr t, u32 k )
    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;
@@ -180,11 +431,52 @@ static aatree_ptr aatree_kth( aatree *tree, aatree_ptr t, u32 k )
    return AATREE_PTR_NIL;
 }
 
-static aatree_ptr aatree_ptrof( aatree *tree, aatree_ptr t, void *value )
+static aatree_ptr aatree_next( aatree *tree, aatree_ptr x )
+{
+   /* if can go left, go left then all the way right,
+    * else go up, if it was right link accept
+    */
+
+   aatree_node *pnode = aatree_get_node( tree, x );
+   if( pnode->right != AATREE_PTR_NIL )
+   {
+      aatree_ptr next = pnode->right;
+      
+      while(1)
+      {
+         aatree_node *pnext = aatree_get_node( tree, next );
+         
+         if( pnext->left != AATREE_PTR_NIL )
+            next = pnext->left;
+         else
+            return next;
+      }
+   }
+   else
+   {
+      aatree_ptr next = x;
+      
+      while(1)
+      {
+         aatree_node *pnode = aatree_get_node( tree, next );
+
+         if( pnode->parent == AATREE_PTR_NIL )
+            return AATREE_PTR_NIL;
+
+         aatree_node *pabove = aatree_get_node( tree, pnode->parent );
+         if( pabove->left == next )
+            return pnode->parent;
+         else
+            next = pnode->parent;
+      }
+   }
+}
+
+static aatree_ptr aatree_find( aatree *tree, aatree_ptr t, void *value )
 {
    while( t != AATREE_PTR_NIL )
    {
-      int cmp_result = tree->p_cmpv( aatree_get_data( tree, t ), value );
+      int cmp_result = tree->p_cmp( aatree_get_data( tree, t ), value );
 
       if( cmp_result == 0 )
          return t;
@@ -201,12 +493,64 @@ static aatree_ptr aatree_ptrof( aatree *tree, aatree_ptr t, void *value )
    return t;
 }
 
-
 /*
- * Debugging stuff
+ * 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) )
 {
@@ -219,10 +563,10 @@ static void aatree_show_r( aatree *tree, aatree_ptr t, int lvl,
 
       for( int i=0; i<lvl; i++ )
       {
-         printf( "  " );
+         vg_info( "  " );
       }
       p_show( data );
-      printf( " (%d) \n", t );
+      vg_info( " (%d) \n", t );
 
       aatree_show_r( tree, ptnode->right, lvl+1, p_show );
    }
@@ -238,116 +582,100 @@ static void aatree_show( aatree *tree, aatree_ptr t, void(*p_show)(void *data))
 
       for( int i=0; i<ptnode->level; i++ )
       {
-         printf( "  " );
+         vg_info( "  " );
       }
       p_show( data );
-      printf( " (%d) \n", t );
+      vg_info( " (%d) \n", t );
 
       aatree_show( tree, ptnode->right, p_show );
    }
 }
 
 static void aatree_show_counts( aatree *tree, aatree_ptr t, int lvl, int *ln,
-                                void(*p_show)(void *data) )
+                                 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, p_show );
+   aatree_show_counts( tree, ptnode->left, lvl+1, ln, err, p_show, show );
 
-   printf( "    %03d| ", *ln );
+   if( show ) vg_info( "%03d| ", *ln );
    *ln = *ln +1;
 
-   for( int i=0; i<lvl; i++ )
-   {
-      printf( "   " );
-   }
-
-   p_show( data );
-   printf( " (%d, %d) \n", t, ptnode->count );
+   if( show ) 
+      for( int i=0; i<lvl; i++ )
+         printf( "   " );
 
-   aatree_show_counts( tree, ptnode->right, lvl+1, ln, p_show );
-}
+   if( show )
+   {
+      p_show( data );
 
-#endif /* VG_STORE_H */
+      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( "\\" );
 
-#if 0
+      printf( " (%d, %d, parent: %d. V: %d, level: %d) \n", t, 
+            ptnode->count, ptnode->parent,
+            aatree_verify( tree, t ), ptnode->level);
+   }
 
-#include <stdlib.h>
-#include <stdio.h>
-#include <stdarg.h>
-#include <string.h>
-#include <stddef.h>
-#include <math.h>
+   if( !aatree_verify( tree, t ) )
+   {
+      if( show )
+         vg_info( "error\n" );
+      *err = 1;
+   }
 
-#include "vg/vg_platform.h"
-#include "vg/vg_stdint.h"
-#include "vg/vg_store.h"
-#include "vg/vg_io.h"
-#include "vg/vg_m.h"
+   aatree_show_counts( tree, ptnode->right, lvl+1, ln, err, p_show, show );
+}
 
-typedef struct yoyo_t yoyo_t;
-struct yoyo_t
-{
-   int my_data;
-   aatree_node anode;
-};
+/*
+ * Pool allocator utility which can be placed in a union with regular aa nodes.
+ */
 
-static void yoyo_t_show( void *_data )
+static aatree_ptr aatree_init_pool( aatree *info, u32 item_count )
 {
-   yoyo_t *data = _data;
-   printf( "%d ", data->my_data );
-}
+   for( aatree_ptr i=0; i<item_count; i++ )
+   {
+      aatree_pool_node *pn = aatree_get_pool_node( info, i );
 
-static int yoyo_t_cmpv( void *_a, void *_v )
-{
-   yoyo_t *a = _a;
-   int *b = _v;
-   return *b - a->my_data;
-}
+      if( i==item_count-1 )
+         pn->next_free = AATREE_PTR_NIL;
+      else
+         pn->next_free = i+1;
+   }
 
-static int yoyo_t_cmp( void *_a, void *_b )
-{
-   yoyo_t *a = _a, *b = _b;
-   return b->my_data - a->my_data;
+   return 0;
 }
 
-int main(int argc, const char *argv[])
+static aatree_ptr aatree_pool_alloc( aatree *info, aatree_ptr *head )
 {
-   yoyo_t *allsorts = malloc( sizeof(yoyo_t) * 10000 );
-
-   aatree test;
-   test.base = allsorts;
-   test.offset = offsetof( yoyo_t, anode );
-   test.stride = sizeof( yoyo_t );
-   test.p_cmp = yoyo_t_cmp;
-   test.p_cmpv = yoyo_t_cmpv;
-   
-   aatree_ptr root = AATREE_PTR_NIL;
-
-   for( int i=0; i<20; i++ )
+   if( *head == AATREE_PTR_NIL )
    {
-      yoyo_t *rando = &allsorts[i];
-      rando->my_data = vg_randf() * 10.0f;
-      root = aatree_insert( &test, root, i );
+      vg_error( "No nodes free in pool allocator!\n" );
+      return AATREE_PTR_NIL;
    }
-   
-   int ln=0;
-   aatree_show_counts( &test, root, 0, &ln, yoyo_t_show );
-
-   int value = 3;
-   vg_info( "Ptr of %d: %u\n", value, aatree_ptrof( &test, root, &value ) );
-
-   for( int i=0; i<20; i++ )
+   else
    {
-      yoyo_t *v = aatree_get_data(&test,aatree_kth( &test, root, i ));
-      vg_info( "Value of [%d]: %d\n", i, v->my_data );
+      aatree_ptr gap = *head;
+      *head = aatree_get_pool_node( info, *head )->next_free;
+      return gap;
    }
+}
 
-   free( allsorts );
-   return 0;
+static void aatree_pool_free( aatree *info, aatree_ptr node, aatree_ptr *head )
+{
+   aatree_pool_node *pn = aatree_get_pool_node( info, node );
+   pn->next_free = *head;
+   *head = node;
 }
 
-#endif
+#endif /* VG_STORE_H */