8 * Anderson tree implementation with extensions:
9 * parents are kept track of
10 * duplicates are allowed
11 * data is never allocated or destroyed here
13 * TODO: seperate offset,stride,base into 'generic array', seperate pool
16 typedef struct aatree aatree
;
17 typedef struct aatree_node aatree_node
;
18 typedef struct aatree_pool_node aatree_pool_node
;
20 typedef u32 aatree_ptr
;
21 #define AATREE_PTR_NIL 0xffffffff
25 u32 offset
, stride
; /* distance between elements */
28 int (*p_cmp
)( void *a
, void *b
);
34 aatree_ptr left
, right
, parent
;
38 struct aatree_pool_node
45 * ===========================================================================*/
47 /* return a pointer to the start of the data referenced by t */
48 static void *aatree_get_data( aatree
*tree
, aatree_ptr t
);
50 /* link node x into the tree with root t */
51 static aatree_ptr
aatree_insert( aatree
*tree
, aatree_ptr t
, aatree_ptr x
);
53 /* delete node x from tree, does not free memory */
54 static aatree_ptr
aatree_del( aatree
*tree
, aatree_ptr x
);
56 /* get pointer to element in tree with index k */
57 static aatree_ptr
aatree_kth( aatree
*tree
, aatree_ptr t
, u32 k
);
59 /* get pointer to the element above x */
60 static aatree_ptr
aatree_next( aatree
*tree
, aatree_ptr x
);
62 /* get pointer by value, returns NIL if not found.
64 * if duplicates values are present then the result is undefined, but it will be
65 * AN node with that value, just maybe not the first lexicographically
67 static aatree_ptr
aatree_find( aatree
*tree
, aatree_ptr t
, void *value
);
70 * ===========================================================================*/
72 static void *aatree_get_data( aatree
*tree
, aatree_ptr t
)
74 return (u8
*)tree
->base
+ tree
->stride
*t
;
77 static u8
*aatree_node_base( aatree
*tree
, aatree_ptr t
)
79 return (u8
*)tree
->base
+ tree
->stride
*t
+ tree
->offset
;
82 static aatree_pool_node
*aatree_get_pool_node( aatree
*tree
, aatree_ptr t
)
84 return (aatree_pool_node
*)aatree_node_base( tree
, t
);
87 static aatree_node
*aatree_get_node( aatree
*tree
, aatree_ptr t
)
89 return (aatree_node
*)aatree_node_base( tree
, t
);
92 static void aatree_recount( aatree
*tree
, aatree_ptr n
)
94 aatree_node
*pnode
= aatree_get_node( tree
, n
);
97 if( pnode
->left
!= AATREE_PTR_NIL
)
98 pnode
->count
+= aatree_get_node( tree
, pnode
->left
)->count
;
100 if( pnode
->right
!= AATREE_PTR_NIL
)
101 pnode
->count
+= aatree_get_node( tree
, pnode
->right
)->count
;
110 static aatree_ptr
aatree_skew( aatree
*tree
, u32 t
)
112 if( t
== AATREE_PTR_NIL
) return t
;
114 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
115 if( ptnode
->left
== AATREE_PTR_NIL
) return t
;
117 aatree_node
*plnode
= aatree_get_node( tree
, ptnode
->left
);
118 if( plnode
->level
== ptnode
->level
)
120 aatree_ptr l
= ptnode
->left
;
121 ptnode
->left
= plnode
->right
;
124 aatree_recount( tree
, t
);
125 aatree_recount( tree
, l
);
127 plnode
->parent
= ptnode
->parent
;
129 if( ptnode
->left
!= AATREE_PTR_NIL
)
130 aatree_get_node( tree
, ptnode
->left
)->parent
= t
;
146 static aatree_ptr
aatree_split( aatree
*tree
, aatree_ptr t
)
148 if( t
== AATREE_PTR_NIL
) return t
;
150 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
151 if( ptnode
->right
== AATREE_PTR_NIL
) return t
;
153 aatree_node
*prnode
= aatree_get_node( tree
, ptnode
->right
);
154 if( prnode
->right
== AATREE_PTR_NIL
) return t
;
156 aatree_node
*prrnode
= aatree_get_node( tree
, prnode
->right
);
157 if( ptnode
->level
== prrnode
->level
)
159 aatree_ptr r
= ptnode
->right
;
160 ptnode
->right
= prnode
->left
;
164 aatree_recount( tree
, t
);
165 aatree_recount( tree
, r
);
167 prnode
->parent
= ptnode
->parent
;
169 if( ptnode
->right
!= AATREE_PTR_NIL
)
170 aatree_get_node( tree
, ptnode
->right
)->parent
= t
;
178 static aatree_ptr
aatree_insert( aatree
*tree
, aatree_ptr t
, aatree_ptr x
)
180 aatree_node
*pxnode
= aatree_get_node( tree
, x
);
182 if( t
== AATREE_PTR_NIL
)
184 pxnode
->left
= AATREE_PTR_NIL
;
185 pxnode
->right
= AATREE_PTR_NIL
;
186 pxnode
->parent
= AATREE_PTR_NIL
;
192 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
193 int cmp_result
= tree
->p_cmp( aatree_get_data( tree
, t
),
194 aatree_get_data( tree
, x
) );
198 if( cmp_result
<= 0 )
200 ptnode
->left
= aatree_insert( tree
, ptnode
->left
, x
);
201 aatree_node
*plnode
= aatree_get_node( tree
, ptnode
->left
);
206 ptnode
->right
= aatree_insert( tree
, ptnode
->right
, x
);
207 aatree_node
*prnode
= aatree_get_node( tree
, ptnode
->right
);
211 t
= aatree_skew( tree
, t
);
212 t
= aatree_split( tree
, t
);
216 static void aatree_link_down( aatree
*tree
, aatree_ptr p
, aatree_ptr
*pl
,
221 if( *pl
!= AATREE_PTR_NIL
)
222 aatree_get_node( tree
, *pl
)->parent
= p
;
225 static aatree_ptr
aatree_copy_links( aatree
*tree
, aatree_ptr root
,
226 aatree_ptr src
, aatree_ptr dst
)
228 aatree_node
*pdst
= aatree_get_node( tree
, dst
),
229 *psrc
= aatree_get_node( tree
, src
);
231 pdst
->count
= psrc
->count
;
232 pdst
->level
= psrc
->level
;
233 pdst
->parent
= psrc
->parent
;
235 aatree_link_down( tree
, dst
, &pdst
->left
, psrc
->left
);
236 aatree_link_down( tree
, dst
, &pdst
->right
, psrc
->right
);
238 if( pdst
->parent
!= AATREE_PTR_NIL
)
240 aatree_node
*parent
= aatree_get_node( tree
, pdst
->parent
);
242 if( parent
->left
== src
)
244 else if( parent
->right
== src
)
253 static aatree_ptr
aatree_del( aatree
*tree
, aatree_ptr x
)
258 int count
= 1, dir
= 0;
260 /* TODO: maybe be a better way to do this, without counting back up */
261 for( aatree_node
*s
= aatree_get_node( tree
, x
);
262 s
->parent
!= AATREE_PTR_NIL
;
264 s
= aatree_get_node( tree
, s
->parent
);
269 int index
= count
- (++top
);
272 aatree_node
*itnode
= aatree_get_node( tree
, it
);
273 if( itnode
->parent
== AATREE_PTR_NIL
)
279 aatree_ptr _ptrswap_src
= AATREE_PTR_NIL
,
280 _ptrswap_dst
= AATREE_PTR_NIL
;
282 aatree_node
*pxnode
= aatree_get_node( tree
, x
);
283 aatree_ptr root
= up
[ count
-1 ];
284 if( pxnode
->left
== AATREE_PTR_NIL
|| pxnode
->right
== AATREE_PTR_NIL
)
288 aatree_node
*pnode
= aatree_get_node( tree
, up
[top
-1] ),
289 *parent
= aatree_get_node( tree
, pxnode
->parent
);
291 aatree_ptr next
= pxnode
->left
== AATREE_PTR_NIL
?
295 if( parent
->left
== x
) pnode
->left
= next
;
296 else pnode
->right
= next
;
298 if( next
!= AATREE_PTR_NIL
)
300 aatree_node
*pnext
= aatree_get_node( tree
, next
);
301 pnext
->parent
= up
[top
-1];
306 if( pxnode
->right
!= AATREE_PTR_NIL
) root
= pxnode
->right
;
307 else if( pxnode
->left
!= AATREE_PTR_NIL
) root
= pxnode
->left
;
308 else return AATREE_PTR_NIL
;
310 aatree_node
*newroot
= aatree_get_node( tree
, root
);
311 newroot
->parent
= AATREE_PTR_NIL
;
316 aatree_ptr heir
= pxnode
->right
,
319 aatree_node
*pheir
= aatree_get_node( tree
, heir
);
321 while( pheir
->left
!= AATREE_PTR_NIL
)
323 up
[top
++] = prev
= heir
;
325 pheir
= aatree_get_node( tree
, heir
);
331 aatree_node
*pprev
= aatree_get_node( tree
, prev
);
334 aatree_link_down( tree
, prev
, &pprev
->right
, pheir
->right
);
336 aatree_link_down( tree
, prev
, &pprev
->left
, pheir
->right
);
344 aatree_node
*above
= aatree_get_node( tree
, up
[top
-1] );
345 dir
= above
->right
== up
[top
];
348 aatree_recount( tree
, up
[top
] );
349 aatree_node
*pntop
= aatree_get_node( tree
, up
[top
] );
351 if( !(pntop
->left
== AATREE_PTR_NIL
|| pntop
->right
== AATREE_PTR_NIL
) )
353 aatree_node
*pnl
= aatree_get_node( tree
, pntop
->left
),
354 *pnr
= aatree_get_node( tree
, pntop
->right
);
356 if( pnl
->level
< pntop
->level
-1 || pnr
->level
< pntop
->level
-1 )
358 if( pnr
->level
> --pntop
->level
)
359 pnr
->level
= pntop
->level
;
361 up
[top
] = aatree_skew( tree
, up
[top
] );
363 aatree_node
*ut
= aatree_get_node( tree
, up
[top
] );
364 ut
->right
= aatree_skew( tree
, ut
->right
);
366 aatree_node
*utr
= aatree_get_node( tree
, ut
->right
);
367 utr
->right
= aatree_skew( tree
, utr
->right
);
369 up
[top
] = aatree_split( tree
, up
[top
] );
370 ut
= aatree_get_node( tree
, up
[top
] );
372 ut
->right
= aatree_split( tree
, ut
->right
);
378 aatree_node
*ut1
= aatree_get_node( tree
, up
[top
-1] );
381 aatree_link_down( tree
, up
[top
-1], &ut1
->right
, up
[top
] );
383 aatree_link_down( tree
, up
[top
-1], &ut1
->left
, up
[top
] );
388 aatree_get_node( tree
, root
)->parent
= AATREE_PTR_NIL
;
392 /* This is our extension to the original non-recursive delete, so no data
394 if( _ptrswap_dst
!= AATREE_PTR_NIL
)
395 root
= aatree_copy_links( tree
, root
, _ptrswap_src
, _ptrswap_dst
);
400 static aatree_ptr
aatree_kth( aatree
*tree
, aatree_ptr t
, u32 k
)
404 while( t
!= AATREE_PTR_NIL
)
406 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
409 if( ptnode
->left
!= AATREE_PTR_NIL
)
410 j
+= aatree_get_node( tree
, ptnode
->left
)->count
;
430 return AATREE_PTR_NIL
;
433 static aatree_ptr
aatree_next( aatree
*tree
, aatree_ptr x
)
435 /* if can go left, go left then all the way right,
436 * else go up, if it was right link accept
439 aatree_node
*pnode
= aatree_get_node( tree
, x
);
440 if( pnode
->right
!= AATREE_PTR_NIL
)
442 aatree_ptr next
= pnode
->right
;
446 aatree_node
*pnext
= aatree_get_node( tree
, next
);
448 if( pnext
->left
!= AATREE_PTR_NIL
)
460 aatree_node
*pnode
= aatree_get_node( tree
, next
);
462 if( pnode
->parent
== AATREE_PTR_NIL
)
463 return AATREE_PTR_NIL
;
465 aatree_node
*pabove
= aatree_get_node( tree
, pnode
->parent
);
466 if( pabove
->left
== next
)
467 return pnode
->parent
;
469 next
= pnode
->parent
;
474 static aatree_ptr
aatree_find( aatree
*tree
, aatree_ptr t
, void *value
)
476 while( t
!= AATREE_PTR_NIL
)
478 int cmp_result
= tree
->p_cmp( aatree_get_data( tree
, t
), value
);
480 if( cmp_result
== 0 )
484 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
496 * Debugging stuff, everything below is scaffholding and will be removed
497 * =============================================================================
500 static int aatree_verify_split( aatree
*tree
, aatree_ptr t
)
502 if( t
== AATREE_PTR_NIL
) return 1;
504 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
505 if( ptnode
->right
== AATREE_PTR_NIL
) return 1;
507 aatree_node
*prnode
= aatree_get_node( tree
, ptnode
->right
);
508 if( prnode
->right
== AATREE_PTR_NIL
) return 1;
510 aatree_node
*prrnode
= aatree_get_node( tree
, prnode
->right
);
511 if( ptnode
->level
== prrnode
->level
)
517 static int aatree_verify_skew( aatree
*tree
, aatree_ptr t
)
519 if( t
== AATREE_PTR_NIL
) return 1;
521 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
522 if( ptnode
->left
== AATREE_PTR_NIL
) return 1;
524 aatree_node
*plnode
= aatree_get_node( tree
, ptnode
->left
);
525 if( plnode
->level
== ptnode
->level
)
531 static int aatree_verify( aatree
*tree
, aatree_ptr t
)
533 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
534 if( ptnode
->parent
!= AATREE_PTR_NIL
)
536 aatree_node
*parent
= aatree_get_node( tree
, ptnode
->parent
);
537 if( !(parent
->left
== t
|| parent
->right
== t
) )
541 if( ptnode
->left
!= AATREE_PTR_NIL
)
542 if( aatree_get_node( tree
, ptnode
->left
)->parent
!= t
)
544 if( ptnode
->right
!= AATREE_PTR_NIL
)
545 if( aatree_get_node( tree
, ptnode
->right
)->parent
!= t
)
548 return aatree_verify_skew( tree
, t
) &&
549 aatree_verify_split( tree
, t
);
553 static void aatree_show_r( aatree
*tree
, aatree_ptr t
, int lvl
,
554 void(*p_show
)(void *data
) )
556 if( t
!= AATREE_PTR_NIL
)
558 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
559 aatree_show_r( tree
, ptnode
->left
, lvl
+1, p_show
);
561 void *data
= aatree_get_data( tree
, t
);
563 for( int i
=0; i
<lvl
; i
++ )
568 vg_log( " (%d) \n", t
);
570 aatree_show_r( tree
, ptnode
->right
, lvl
+1, p_show
);
574 static void aatree_show( aatree
*tree
, aatree_ptr t
, void(*p_show
)(void *data
))
576 if( t
!= AATREE_PTR_NIL
)
578 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
579 aatree_show( tree
, ptnode
->left
, p_show
);
580 void *data
= aatree_get_data( tree
, t
);
582 for( int i
=0; i
<ptnode
->level
; i
++ )
587 vg_log( " (%d) \n", t
);
589 aatree_show( tree
, ptnode
->right
, p_show
);
593 static void aatree_show_counts( aatree
*tree
, aatree_ptr t
, int lvl
, int *ln
,
595 void(*p_show
)(void *data
), int show
)
599 if( t
== AATREE_PTR_NIL
) return;
601 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
602 void *data
= aatree_get_data( tree
, t
);
604 aatree_show_counts( tree
, ptnode
->left
, lvl
+1, ln
, err
, p_show
, show
);
606 if( show
) vg_log( "%03d| ", *ln
);
610 for( int i
=0; i
<lvl
; i
++ )
617 if( ptnode
->left
!= AATREE_PTR_NIL
&& ptnode
->right
!= AATREE_PTR_NIL
)
619 if( ptnode
->left
!= AATREE_PTR_NIL
&& ptnode
->right
== AATREE_PTR_NIL
)
621 if( ptnode
->left
== AATREE_PTR_NIL
&& ptnode
->right
!= AATREE_PTR_NIL
)
624 printf( " (%d, %d, parent: %d. V: %d, level: %d) \n", t
,
625 ptnode
->count
, ptnode
->parent
,
626 aatree_verify( tree
, t
), ptnode
->level
);
629 if( !aatree_verify( tree
, t
) )
636 aatree_show_counts( tree
, ptnode
->right
, lvl
+1, ln
, err
, p_show
, show
);
640 * Pool allocator utility which can be placed in a union with regular aa nodes.
643 static aatree_ptr
aatree_init_pool( aatree
*info
, u32 item_count
)
645 for( aatree_ptr i
=0; i
<item_count
; i
++ )
647 aatree_pool_node
*pn
= aatree_get_pool_node( info
, i
);
649 if( i
==item_count
-1 )
650 pn
->next_free
= AATREE_PTR_NIL
;
658 static aatree_ptr
aatree_pool_alloc( aatree
*info
, aatree_ptr
*head
)
660 if( *head
== AATREE_PTR_NIL
)
662 vg_error( "No nodes free in pool allocator!\n" );
663 return AATREE_PTR_NIL
;
667 aatree_ptr gap
= *head
;
668 *head
= aatree_get_pool_node( info
, *head
)->next_free
;
673 static void aatree_pool_free( aatree
*info
, aatree_ptr node
, aatree_ptr
*head
)
675 aatree_pool_node
*pn
= aatree_get_pool_node( info
, node
);
676 pn
->next_free
= *head
;
680 #endif /* VG_STORE_H */