8 * Anderson tree implementation with extensions:
9 * parents are kept track of
10 * duplicates are allowed
11 * data is never allocated or destroyed here
14 typedef struct aatree aatree
;
15 typedef struct aatree_node aatree_node
;
16 typedef struct aatree_pool_node aatree_pool_node
;
18 typedef u32 aatree_ptr
;
19 #define AATREE_PTR_NIL 0xffffffff
23 u32 offset
, stride
; /* distance between elements */
26 int (*p_cmp
)( void *a
, void *b
);
32 aatree_ptr left
, right
, parent
;
36 struct aatree_pool_node
43 * ===========================================================================*/
45 /* return a pointer to the start of the data referenced by t */
46 static void *aatree_get_data( aatree
*tree
, aatree_ptr t
);
48 /* link node x into the tree with root t */
49 static aatree_ptr
aatree_insert( aatree
*tree
, aatree_ptr t
, aatree_ptr x
);
51 /* delete node x from tree, does not free memory */
52 static aatree_ptr
aatree_del( aatree
*tree
, aatree_ptr x
);
54 /* get pointer to element in tree with index k */
55 static aatree_ptr
aatree_kth( aatree
*tree
, aatree_ptr t
, u32 k
);
57 /* get pointer to the element above x */
58 static aatree_ptr
aatree_next( aatree
*tree
, aatree_ptr x
);
60 /* get pointer by value, returns NIL if not found.
62 * if duplicates values are present then the result is undefined, but it will be
63 * AN node with that value, just maybe not the first lexicographically
65 static aatree_ptr
aatree_find( aatree
*tree
, aatree_ptr t
, void *value
);
68 * ===========================================================================*/
70 static void *aatree_get_data( aatree
*tree
, aatree_ptr t
)
72 return (u8
*)tree
->base
+ tree
->stride
*t
;
75 static u8
*aatree_node_base( aatree
*tree
, aatree_ptr t
)
77 return (u8
*)tree
->base
+ tree
->stride
*t
+ tree
->offset
;
80 static aatree_pool_node
*aatree_get_pool_node( aatree
*tree
, aatree_ptr t
)
82 return (aatree_pool_node
*)aatree_node_base( tree
, t
);
85 static aatree_node
*aatree_get_node( aatree
*tree
, aatree_ptr t
)
87 return (aatree_node
*)aatree_node_base( tree
, t
);
90 static void aatree_recount( aatree
*tree
, aatree_ptr n
)
92 aatree_node
*pnode
= aatree_get_node( tree
, n
);
95 if( pnode
->left
!= AATREE_PTR_NIL
)
96 pnode
->count
+= aatree_get_node( tree
, pnode
->left
)->count
;
98 if( pnode
->right
!= AATREE_PTR_NIL
)
99 pnode
->count
+= aatree_get_node( tree
, pnode
->right
)->count
;
108 static aatree_ptr
aatree_skew( aatree
*tree
, u32 t
)
110 if( t
== AATREE_PTR_NIL
) return t
;
112 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
113 if( ptnode
->left
== AATREE_PTR_NIL
) return t
;
115 aatree_node
*plnode
= aatree_get_node( tree
, ptnode
->left
);
116 if( plnode
->level
== ptnode
->level
)
118 aatree_ptr l
= ptnode
->left
;
119 ptnode
->left
= plnode
->right
;
122 aatree_recount( tree
, t
);
123 aatree_recount( tree
, l
);
125 plnode
->parent
= ptnode
->parent
;
127 if( ptnode
->left
!= AATREE_PTR_NIL
)
128 aatree_get_node( tree
, ptnode
->left
)->parent
= t
;
144 static aatree_ptr
aatree_split( aatree
*tree
, aatree_ptr t
)
146 if( t
== AATREE_PTR_NIL
) return t
;
148 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
149 if( ptnode
->right
== AATREE_PTR_NIL
) return t
;
151 aatree_node
*prnode
= aatree_get_node( tree
, ptnode
->right
);
152 if( prnode
->right
== AATREE_PTR_NIL
) return t
;
154 aatree_node
*prrnode
= aatree_get_node( tree
, prnode
->right
);
155 if( ptnode
->level
== prrnode
->level
)
157 aatree_ptr r
= ptnode
->right
;
158 ptnode
->right
= prnode
->left
;
162 aatree_recount( tree
, t
);
163 aatree_recount( tree
, r
);
165 prnode
->parent
= ptnode
->parent
;
167 if( ptnode
->right
!= AATREE_PTR_NIL
)
168 aatree_get_node( tree
, ptnode
->right
)->parent
= t
;
176 static aatree_ptr
aatree_insert( aatree
*tree
, aatree_ptr t
, aatree_ptr x
)
178 aatree_node
*pxnode
= aatree_get_node( tree
, x
);
180 if( t
== AATREE_PTR_NIL
)
182 pxnode
->left
= AATREE_PTR_NIL
;
183 pxnode
->right
= AATREE_PTR_NIL
;
184 pxnode
->parent
= AATREE_PTR_NIL
;
190 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
191 int cmp_result
= tree
->p_cmp( aatree_get_data( tree
, t
),
192 aatree_get_data( tree
, x
) );
196 if( cmp_result
<= 0 )
198 ptnode
->left
= aatree_insert( tree
, ptnode
->left
, x
);
199 aatree_node
*plnode
= aatree_get_node( tree
, ptnode
->left
);
204 ptnode
->right
= aatree_insert( tree
, ptnode
->right
, x
);
205 aatree_node
*prnode
= aatree_get_node( tree
, ptnode
->right
);
209 t
= aatree_skew( tree
, t
);
210 t
= aatree_split( tree
, t
);
214 static void aatree_link_down( aatree
*tree
, aatree_ptr p
, aatree_ptr
*pl
,
219 if( *pl
!= AATREE_PTR_NIL
)
220 aatree_get_node( tree
, *pl
)->parent
= p
;
223 static aatree_ptr
aatree_copy_links( aatree
*tree
, aatree_ptr root
,
224 aatree_ptr src
, aatree_ptr dst
)
226 aatree_node
*pdst
= aatree_get_node( tree
, dst
),
227 *psrc
= aatree_get_node( tree
, src
);
229 pdst
->count
= psrc
->count
;
230 pdst
->level
= psrc
->level
;
231 pdst
->parent
= psrc
->parent
;
233 aatree_link_down( tree
, dst
, &pdst
->left
, psrc
->left
);
234 aatree_link_down( tree
, dst
, &pdst
->right
, psrc
->right
);
236 if( pdst
->parent
!= AATREE_PTR_NIL
)
238 aatree_node
*parent
= aatree_get_node( tree
, pdst
->parent
);
240 if( parent
->left
== src
)
242 else if( parent
->right
== src
)
251 static aatree_ptr
aatree_del( aatree
*tree
, aatree_ptr x
)
256 int count
= 1, dir
= 0;
258 /* TODO: maybe be a better way to do this, without counting back up */
259 for( aatree_node
*s
= aatree_get_node( tree
, x
);
260 s
->parent
!= AATREE_PTR_NIL
;
262 s
= aatree_get_node( tree
, s
->parent
);
267 int index
= count
- (++top
);
270 aatree_node
*itnode
= aatree_get_node( tree
, it
);
271 if( itnode
->parent
== AATREE_PTR_NIL
)
277 aatree_ptr _ptrswap_src
= AATREE_PTR_NIL
,
278 _ptrswap_dst
= AATREE_PTR_NIL
;
280 aatree_node
*pxnode
= aatree_get_node( tree
, x
);
281 aatree_ptr root
= up
[ count
-1 ];
282 if( pxnode
->left
== AATREE_PTR_NIL
|| pxnode
->right
== AATREE_PTR_NIL
)
286 aatree_node
*pnode
= aatree_get_node( tree
, up
[top
-1] ),
287 *parent
= aatree_get_node( tree
, pxnode
->parent
);
289 aatree_ptr next
= pxnode
->left
== AATREE_PTR_NIL
?
293 if( parent
->left
== x
) pnode
->left
= next
;
294 else pnode
->right
= next
;
296 if( next
!= AATREE_PTR_NIL
)
298 aatree_node
*pnext
= aatree_get_node( tree
, next
);
299 pnext
->parent
= up
[top
-1];
304 if( pxnode
->right
!= AATREE_PTR_NIL
) root
= pxnode
->right
;
305 else if( pxnode
->left
!= AATREE_PTR_NIL
) root
= pxnode
->left
;
306 else return AATREE_PTR_NIL
;
308 aatree_node
*newroot
= aatree_get_node( tree
, root
);
309 newroot
->parent
= AATREE_PTR_NIL
;
314 aatree_ptr heir
= pxnode
->right
,
317 aatree_node
*pheir
= aatree_get_node( tree
, heir
);
319 while( pheir
->left
!= AATREE_PTR_NIL
)
321 up
[top
++] = prev
= heir
;
323 pheir
= aatree_get_node( tree
, heir
);
329 aatree_node
*pprev
= aatree_get_node( tree
, prev
);
332 aatree_link_down( tree
, prev
, &pprev
->right
, pheir
->right
);
334 aatree_link_down( tree
, prev
, &pprev
->left
, pheir
->right
);
342 aatree_node
*above
= aatree_get_node( tree
, up
[top
-1] );
343 dir
= above
->right
== up
[top
];
346 aatree_recount( tree
, up
[top
] );
347 aatree_node
*pntop
= aatree_get_node( tree
, up
[top
] );
349 if( !(pntop
->left
== AATREE_PTR_NIL
|| pntop
->right
== AATREE_PTR_NIL
) )
351 aatree_node
*pnl
= aatree_get_node( tree
, pntop
->left
),
352 *pnr
= aatree_get_node( tree
, pntop
->right
);
354 if( pnl
->level
< pntop
->level
-1 || pnr
->level
< pntop
->level
-1 )
356 if( pnr
->level
> --pntop
->level
)
357 pnr
->level
= pntop
->level
;
359 up
[top
] = aatree_skew( tree
, up
[top
] );
361 aatree_node
*ut
= aatree_get_node( tree
, up
[top
] );
362 ut
->right
= aatree_skew( tree
, ut
->right
);
364 aatree_node
*utr
= aatree_get_node( tree
, ut
->right
);
365 utr
->right
= aatree_skew( tree
, utr
->right
);
367 up
[top
] = aatree_split( tree
, up
[top
] );
368 ut
= aatree_get_node( tree
, up
[top
] );
370 ut
->right
= aatree_split( tree
, ut
->right
);
376 aatree_node
*ut1
= aatree_get_node( tree
, up
[top
-1] );
379 aatree_link_down( tree
, up
[top
-1], &ut1
->right
, up
[top
] );
381 aatree_link_down( tree
, up
[top
-1], &ut1
->left
, up
[top
] );
386 aatree_get_node( tree
, root
)->parent
= AATREE_PTR_NIL
;
390 /* This is our extension to the original non-recursive delete, so no data
392 if( _ptrswap_dst
!= AATREE_PTR_NIL
)
393 root
= aatree_copy_links( tree
, root
, _ptrswap_src
, _ptrswap_dst
);
398 static aatree_ptr
aatree_kth( aatree
*tree
, aatree_ptr t
, u32 k
)
402 while( t
!= AATREE_PTR_NIL
)
404 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
407 if( ptnode
->left
!= AATREE_PTR_NIL
)
408 j
+= aatree_get_node( tree
, ptnode
->left
)->count
;
428 return AATREE_PTR_NIL
;
431 static aatree_ptr
aatree_next( aatree
*tree
, aatree_ptr x
)
433 /* if can go left, go left then all the way right,
434 * else go up, if it was right link accept
437 aatree_node
*pnode
= aatree_get_node( tree
, x
);
438 if( pnode
->right
!= AATREE_PTR_NIL
)
440 aatree_ptr next
= pnode
->right
;
444 aatree_node
*pnext
= aatree_get_node( tree
, next
);
446 if( pnext
->left
!= AATREE_PTR_NIL
)
458 aatree_node
*pnode
= aatree_get_node( tree
, next
);
460 if( pnode
->parent
== AATREE_PTR_NIL
)
461 return AATREE_PTR_NIL
;
463 aatree_node
*pabove
= aatree_get_node( tree
, pnode
->parent
);
464 if( pabove
->left
== next
)
465 return pnode
->parent
;
467 next
= pnode
->parent
;
472 static aatree_ptr
aatree_find( aatree
*tree
, aatree_ptr t
, void *value
)
474 while( t
!= AATREE_PTR_NIL
)
476 int cmp_result
= tree
->p_cmp( aatree_get_data( tree
, t
), value
);
478 if( cmp_result
== 0 )
482 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
494 * Debugging stuff, everything below is scaffholding and will be removed
495 * =============================================================================
498 static int aatree_verify_split( aatree
*tree
, aatree_ptr t
)
500 if( t
== AATREE_PTR_NIL
) return 1;
502 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
503 if( ptnode
->right
== AATREE_PTR_NIL
) return 1;
505 aatree_node
*prnode
= aatree_get_node( tree
, ptnode
->right
);
506 if( prnode
->right
== AATREE_PTR_NIL
) return 1;
508 aatree_node
*prrnode
= aatree_get_node( tree
, prnode
->right
);
509 if( ptnode
->level
== prrnode
->level
)
515 static int aatree_verify_skew( aatree
*tree
, aatree_ptr t
)
517 if( t
== AATREE_PTR_NIL
) return 1;
519 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
520 if( ptnode
->left
== AATREE_PTR_NIL
) return 1;
522 aatree_node
*plnode
= aatree_get_node( tree
, ptnode
->left
);
523 if( plnode
->level
== ptnode
->level
)
529 static int aatree_verify( aatree
*tree
, aatree_ptr t
)
531 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
532 if( ptnode
->parent
!= AATREE_PTR_NIL
)
534 aatree_node
*parent
= aatree_get_node( tree
, ptnode
->parent
);
535 if( !(parent
->left
== t
|| parent
->right
== t
) )
539 if( ptnode
->left
!= AATREE_PTR_NIL
)
540 if( aatree_get_node( tree
, ptnode
->left
)->parent
!= t
)
542 if( ptnode
->right
!= AATREE_PTR_NIL
)
543 if( aatree_get_node( tree
, ptnode
->right
)->parent
!= t
)
546 return aatree_verify_skew( tree
, t
) &&
547 aatree_verify_split( tree
, t
);
551 static void aatree_show_r( aatree
*tree
, aatree_ptr t
, int lvl
,
552 void(*p_show
)(void *data
) )
554 if( t
!= AATREE_PTR_NIL
)
556 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
557 aatree_show_r( tree
, ptnode
->left
, lvl
+1, p_show
);
559 void *data
= aatree_get_data( tree
, t
);
561 for( int i
=0; i
<lvl
; i
++ )
566 vg_log( " (%d) \n", t
);
568 aatree_show_r( tree
, ptnode
->right
, lvl
+1, p_show
);
572 static void aatree_show( aatree
*tree
, aatree_ptr t
, void(*p_show
)(void *data
))
574 if( t
!= AATREE_PTR_NIL
)
576 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
577 aatree_show( tree
, ptnode
->left
, p_show
);
578 void *data
= aatree_get_data( tree
, t
);
580 for( int i
=0; i
<ptnode
->level
; i
++ )
585 vg_log( " (%d) \n", t
);
587 aatree_show( tree
, ptnode
->right
, p_show
);
591 static void aatree_show_counts( aatree
*tree
, aatree_ptr t
, int lvl
, int *ln
,
593 void(*p_show
)(void *data
), int show
)
597 if( t
== AATREE_PTR_NIL
) return;
599 aatree_node
*ptnode
= aatree_get_node( tree
, t
);
600 void *data
= aatree_get_data( tree
, t
);
602 aatree_show_counts( tree
, ptnode
->left
, lvl
+1, ln
, err
, p_show
, show
);
604 if( show
) vg_log( "%03d| ", *ln
);
608 for( int i
=0; i
<lvl
; i
++ )
615 if( ptnode
->left
!= AATREE_PTR_NIL
&& ptnode
->right
!= AATREE_PTR_NIL
)
617 if( ptnode
->left
!= AATREE_PTR_NIL
&& ptnode
->right
== AATREE_PTR_NIL
)
619 if( ptnode
->left
== AATREE_PTR_NIL
&& ptnode
->right
!= AATREE_PTR_NIL
)
622 printf( " (%d, %d, parent: %d. V: %d, level: %d) \n", t
,
623 ptnode
->count
, ptnode
->parent
,
624 aatree_verify( tree
, t
), ptnode
->level
);
627 if( !aatree_verify( tree
, t
) )
634 aatree_show_counts( tree
, ptnode
->right
, lvl
+1, ln
, err
, p_show
, show
);
638 * Pool allocator utility which can be placed in a union with regular aa nodes.
641 static aatree_ptr
aatree_init_pool( aatree
*info
, u32 item_count
)
643 for( aatree_ptr i
=0; i
<item_count
; i
++ )
645 aatree_pool_node
*pn
= aatree_get_pool_node( info
, i
);
647 if( i
==item_count
-1 )
648 pn
->next_free
= AATREE_PTR_NIL
;
656 static aatree_ptr
aatree_pool_alloc( aatree
*info
, aatree_ptr
*head
)
658 if( *head
== AATREE_PTR_NIL
)
660 vg_error( "No nodes free in pool allocator!\n" );
661 return AATREE_PTR_NIL
;
665 aatree_ptr gap
= *head
;
666 *head
= aatree_get_pool_node( info
, *head
)->next_free
;
671 static void aatree_pool_free( aatree
*info
, aatree_ptr node
, aatree_ptr
*head
)
673 aatree_pool_node
*pn
= aatree_get_pool_node( info
, node
);
674 pn
->next_free
= *head
;
678 #endif /* VG_STORE_H */