X-Git-Url: https://harrygodden.com/git/?a=blobdiff_plain;f=src%2Fvg%2Fvg_store.h;h=ee0e91acf04d3e94579b1f62c7dfafda8d322a9d;hb=3dd767bb10e6fee9cbffeb185d1a9685810c17b5;hp=0bbec253d0804217f51df33a80465dd8071d8085;hpb=00eaa4d4e0700bc6864de6d193155080524232ee;p=vg.git diff --git a/src/vg/vg_store.h b/src/vg/vg_store.h index 0bbec25..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, 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,9 +125,6 @@ static aatree_ptr aatree_skew( aatree *tree, u32 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 ) @@ -110,9 +165,6 @@ static aatree_ptr aatree_split( aatree *tree, aatree_ptr t ) 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 ) @@ -124,8 +176,6 @@ static aatree_ptr aatree_split( aatree *tree, aatree_ptr t ) 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 ); @@ -143,7 +193,7 @@ 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 ) @@ -173,25 +223,46 @@ static void aatree_link_down( aatree *tree, aatree_ptr p, aatree_ptr *pl, aatree_get_node( tree, *pl )->parent = p; } -static aatree_ptr aatree_del( aatree *tree, aatree_ptr x ) +static aatree_ptr aatree_copy_links( aatree *tree, aatree_ptr root, + aatree_ptr src, aatree_ptr dst ) { - /* 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_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; - 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 ++; - } + /* 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) @@ -266,6 +337,7 @@ static aatree_ptr aatree_del( aatree *tree, aatree_ptr x ) aatree_link_down( tree, prev, &pprev->left, pheir->right ); } + /* Tail */ while( --top >= 0 ) { if( top != 0 ) @@ -276,12 +348,11 @@ static aatree_ptr aatree_del( aatree *tree, aatree_ptr x ) 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 + + 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 ); + 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 ) { @@ -318,52 +389,15 @@ static aatree_ptr aatree_del( aatree *tree, aatree_ptr x ) 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 ) - { - /* 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; - } + root = aatree_copy_links( tree, root, _ptrswap_src, _ptrswap_dst ); return root; } -/* - * Accessors - */ - static aatree_ptr aatree_kth( aatree *tree, aatree_ptr t, u32 k ) { u32 i = 0; @@ -371,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; @@ -397,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; @@ -418,7 +493,6 @@ static aatree_ptr aatree_ptrof( aatree *tree, aatree_ptr t, void *value ) return t; } - /* * Debugging stuff, everything below is scaffholding and will be removed * ============================================================================= @@ -489,10 +563,10 @@ static void aatree_show_r( aatree *tree, aatree_ptr t, int lvl, for( int i=0; iright, lvl+1, p_show ); } @@ -508,10 +582,10 @@ static void aatree_show( aatree *tree, aatree_ptr t, void(*p_show)(void *data)) for( int i=0; ilevel; i++ ) { - printf( " " ); + vg_info( " " ); } p_show( data ); - printf( " (%d) \n", t ); + vg_info( " (%d) \n", t ); aatree_show( tree, ptnode->right, p_show ); } @@ -530,7 +604,7 @@ static void aatree_show_counts( aatree *tree, aatree_ptr t, int lvl, int *ln, aatree_show_counts( tree, ptnode->left, lvl+1, ln, err, p_show, show ); - if( show ) printf( " %03d| ", *ln ); + if( show ) vg_info( "%03d| ", *ln ); *ln = *ln +1; if( show ) @@ -556,11 +630,52 @@ static void aatree_show_counts( aatree *tree, aatree_ptr t, int lvl, int *ln, if( !aatree_verify( tree, t ) ) { if( show ) - printf( "error\n" ); + vg_info( "error\n" ); *err = 1; } aatree_show_counts( tree, ptnode->right, lvl+1, ln, err, p_show, show ); } +/* + * Pool allocator utility which can be placed in a union with regular aa nodes. + */ + +static aatree_ptr aatree_init_pool( aatree *info, u32 item_count ) +{ + for( aatree_ptr i=0; inext_free = AATREE_PTR_NIL; + else + pn->next_free = i+1; + } + + return 0; +} + +static aatree_ptr aatree_pool_alloc( aatree *info, aatree_ptr *head ) +{ + if( *head == AATREE_PTR_NIL ) + { + vg_error( "No nodes free in pool allocator!\n" ); + return AATREE_PTR_NIL; + } + else + { + aatree_ptr gap = *head; + *head = aatree_get_pool_node( info, *head )->next_free; + return gap; + } +} + +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 /* VG_STORE_H */