#ifndef VG_STORE_H
#define VG_STORE_H
+#include "vg_stdint.h"
+#include "vg_io.h"
+
+/*
+ * Anderson tree implementation with extensions:
+ * parents are kept track of
+ * duplicates are allowed
+ * data is never allocated or destroyed here
+ */
+
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, 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 );
- /* 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 )
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 )
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 );
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 )
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)
aatree_link_down( tree, prev, &pprev->left, pheir->right );
}
+ /* Tail */
while( --top >= 0 )
{
if( top != 0 )
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 )
{
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;
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, everything below is scaffholding and will be removed
* =============================================================================
for( int i=0; i<lvl; i++ )
{
- printf( " " );
+ vg_log( " " );
}
p_show( data );
- printf( " (%d) \n", t );
+ vg_log( " (%d) \n", t );
aatree_show_r( tree, ptnode->right, lvl+1, p_show );
}
for( int i=0; i<ptnode->level; i++ )
{
- printf( " " );
+ vg_log( " " );
}
p_show( data );
- printf( " (%d) \n", t );
+ vg_log( " (%d) \n", t );
aatree_show( tree, ptnode->right, p_show );
}
aatree_show_counts( tree, ptnode->left, lvl+1, ln, err, p_show, show );
- if( show ) printf( " %03d| ", *ln );
+ if( show ) vg_log( "%03d| ", *ln );
*ln = *ln +1;
if( show )
if( !aatree_verify( tree, t ) )
{
if( show )
- printf( "error\n" );
+ vg_log( "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