+++ /dev/null
-#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; i<lvl; i++ )
- {
- vg_info( " " );
- }
- p_show( data );
- vg_info( " (%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++ )
- {
- 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; 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 )
- 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; i<item_count; i++ )
- {
- aatree_pool_node *pn = aatree_get_pool_node( info, i );
-
- if( i==item_count-1 )
- pn->next_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 */
projects / vg.git / blobdiff