X-Git-Url: https://harrygodden.com/git/?p=vg.git;a=blobdiff_plain;f=vg_store.h;fp=vg_store.h;h=0000000000000000000000000000000000000000;hp=ee0e91acf04d3e94579b1f62c7dfafda8d322a9d;hb=3b14f3dcd5bf9dd3c85144f2123d667bfa4bb63f;hpb=fce86711735b15bff37de0f70716808410fcf269 diff --git a/vg_store.h b/vg_store.h deleted file mode 100644 index ee0e91a..0000000 --- a/vg_store.h +++ /dev/null @@ -1,681 +0,0 @@ -#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 - -struct aatree -{ - u32 offset, stride; /* distance between elements */ - void *base; - - int (*p_cmp)( void *a, void *b ); -}; - -#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 (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 (aatree_node *)aatree_node_base( tree, t ); -} - -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 ); - - 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 ); - - 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 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_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 ) -{ - 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_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_cmp( 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; iright, 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; ilevel; i++ ) - { - vg_info( " " ); - } - p_show( data ); - 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, - 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 ) vg_info( "%03d| ", *ln ); - *ln = *ln +1; - - if( show ) - for( int i=0; ileft != 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 ) - 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 */