#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
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 )
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;
}
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;
}
{
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 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 )
{
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;
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;
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) )
{
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 );
}
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 */
projects / vg.git / blobdiff