From ca04f71f6e1cb30ca3dbb97c700b134deef25bf7 Mon Sep 17 00:00:00 2001 From: hgn Date: Wed, 10 Aug 2022 23:16:09 +0100 Subject: [PATCH] aatrees --- src/vg/vg_store.h | 353 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 353 insertions(+) create mode 100644 src/vg/vg_store.h diff --git a/src/vg/vg_store.h b/src/vg/vg_store.h new file mode 100644 index 0000000..3684ff7 --- /dev/null +++ b/src/vg/vg_store.h @@ -0,0 +1,353 @@ +#ifndef VG_STORE_H +#define VG_STORE_H + +typedef struct aatree aatree; +typedef struct aatree_node aatree_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 ); + int (*p_cmpv)( void *a, void *v ); +}; + +struct aatree_node +{ + aatree_ptr left, right; + u32 level, count; +}; + +static void *aatree_get_data( aatree *tree, aatree_ptr t ) +{ + return tree->base + tree->stride*t; +} + +static aatree_node *aatree_get_node( aatree *tree, aatree_ptr t ) +{ + return tree->base + tree->stride*t + tree->offset; +} + +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 ); + + 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 ); + + 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->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 ); + else + ptnode->right = aatree_insert( tree, ptnode->right, x ); + + 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 ) +{ + if( t == AATREE_PTR_NIL ) return t; + return AATREE_PTR_NIL; /*TODO*/ +} + +/* + * 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; + + 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_ptrof( aatree *tree, aatree_ptr t, void *value ) +{ + while( t != AATREE_PTR_NIL ) + { + int cmp_result = tree->p_cmpv( 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 + * ============================================================================= + */ + +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++ ) + { + printf( " " ); + } + p_show( data ); + printf( " (%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) ) +{ + 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 ); + + printf( " %03d| ", *ln ); + *ln = *ln +1; + + for( int i=0; icount ); + + aatree_show_counts( tree, ptnode->right, lvl+1, ln, p_show ); +} + +#endif /* VG_STORE_H */ + +#if 0 + +#include +#include +#include +#include +#include +#include + +#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" + +typedef struct yoyo_t yoyo_t; +struct yoyo_t +{ + int my_data; + aatree_node anode; +}; + +static void yoyo_t_show( void *_data ) +{ + yoyo_t *data = _data; + printf( "%d ", data->my_data ); +} + +static int yoyo_t_cmpv( void *_a, void *_v ) +{ + yoyo_t *a = _a; + int *b = _v; + return *b - a->my_data; +} + +static int yoyo_t_cmp( void *_a, void *_b ) +{ + yoyo_t *a = _a, *b = _b; + return b->my_data - a->my_data; +} + +int main(int argc, const char *argv[]) +{ + 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++ ) + { + yoyo_t *rando = &allsorts[i]; + rando->my_data = vg_randf() * 10.0f; + root = aatree_insert( &test, root, i ); + } + + 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++ ) + { + yoyo_t *v = aatree_get_data(&test,aatree_kth( &test, root, i )); + vg_info( "Value of [%d]: %d\n", i, v->my_data ); + } + + free( allsorts ); + return 0; +} + +#endif -- 2.25.1