From 00eaa4d4e0700bc6864de6d193155080524232ee Mon Sep 17 00:00:00 2001 From: hgn Date: Fri, 12 Aug 2022 02:33:10 +0100 Subject: [PATCH] some work on in-place anderson trees --- src/vg/vg_store.h | 391 +++++++++++++++++++++++++++++++++++----------- 1 file changed, 302 insertions(+), 89 deletions(-) diff --git a/src/vg/vg_store.h b/src/vg/vg_store.h index 3684ff7..0bbec25 100644 --- a/src/vg/vg_store.h +++ b/src/vg/vg_store.h @@ -18,7 +18,7 @@ struct aatree struct aatree_node { - aatree_ptr left, right; + aatree_ptr left, right, parent; u32 level, count; }; @@ -67,6 +67,14 @@ 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 ) + aatree_get_node( tree, ptnode->left )->parent = t; + return l; } @@ -102,12 +110,22 @@ 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 ) + aatree_get_node( tree, ptnode->right )->parent = t; + return r; } 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 ); @@ -116,6 +134,7 @@ static aatree_ptr aatree_insert( aatree *tree, aatree_ptr t, aatree_ptr x ) { pxnode->left = AATREE_PTR_NIL; pxnode->right = AATREE_PTR_NIL; + pxnode->parent = AATREE_PTR_NIL; pxnode->level = 0; pxnode->count = 1; return x; @@ -128,19 +147,217 @@ static aatree_ptr aatree_insert( aatree *tree, aatree_ptr t, aatree_ptr 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 aatree_ptr aatree_del( aatree *tree, aatree_ptr t, aatree_ptr x ) +static void aatree_link_down( aatree *tree, aatree_ptr p, aatree_ptr *pl, + aatree_ptr l ) { - if( t == AATREE_PTR_NIL ) return t; - return AATREE_PTR_NIL; /*TODO*/ + *pl = l; + + if( *pl != AATREE_PTR_NIL ) + aatree_get_node( tree, *pl )->parent = p; +} + +static aatree_ptr aatree_del( aatree *tree, aatree_ptr x ) +{ + /* 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_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 ++; + } + + 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 ); + } + + 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 ){} + else + { + 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; + } + } + + 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; + } + + return root; } /* @@ -203,10 +420,63 @@ static aatree_ptr aatree_ptrof( aatree *tree, aatree_ptr t, void *value ) /* - * Debugging stuff + * 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) ) { @@ -248,106 +518,49 @@ static void aatree_show( aatree *tree, aatree_ptr t, void(*p_show)(void *data)) } static void aatree_show_counts( aatree *tree, aatree_ptr t, int lvl, int *ln, - void(*p_show)(void *data) ) + 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, p_show ); + aatree_show_counts( tree, ptnode->left, lvl+1, ln, err, p_show, show ); - printf( " %03d| ", *ln ); + if( 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; -} + if( show ) + for( int i=0; imy_data - a->my_data; -} + if( show ) + { + p_show( 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; + 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( "\\" ); - 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 ); + printf( " (%d, %d, parent: %d. V: %d, level: %d) \n", t, + ptnode->count, ptnode->parent, + aatree_verify( tree, t ), ptnode->level); } - - 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++ ) + if( !aatree_verify( tree, t ) ) { - yoyo_t *v = aatree_get_data(&test,aatree_kth( &test, root, i )); - vg_info( "Value of [%d]: %d\n", i, v->my_data ); + if( show ) + printf( "error\n" ); + *err = 1; } - free( allsorts ); - return 0; + aatree_show_counts( tree, ptnode->right, lvl+1, ln, err, p_show, show ); } -#endif +#endif /* VG_STORE_H */ -- 2.25.1