Line data Source code
1 : /* Declares a family of functions implementing a single-threaded
2 : fixed-capacity red-black tree designed for high performance
3 : contexts.
4 :
5 : A red-black tree is a type of self-balanced binary tree where the
6 : nodes are kept in sorted order. Queries, insertions, and deletions
7 : are O(log n) cost where n is the size of the tree. The implicit
8 : sorting makes in-order traversal very fast, something a hash table
9 : cannot do.
10 :
11 : Tree nodes are allocated from a pool before insertion. After
12 : removal, they are returned to the pool. The pool is the result of
13 : the join operation.
14 :
15 : Multiple trees can coexist in the same pool, provided the total
16 : size of all the trees does not exceed the pool size. This is
17 : convenient for removing nodes from one tree and inserting them into
18 : another without copying the key or value.
19 :
20 : Example usage:
21 :
22 : struct my_rb_node {
23 : ulong key;
24 : ulong val;
25 : ulong redblack_parent;
26 : ulong redblack_left;
27 : ulong redblack_right;
28 : int redblack_color;
29 : };
30 : typedef struct my_rb_node my_rb_node_t;
31 : #define REDBLK_T my_rb_node_t
32 : #define REDBLK_NAME my_rb
33 : #include "fd_redblack.c"
34 :
35 : Note the order of declarations and includes. REDBLK_T and REDBLK_NAME
36 : need to be defined before including this template. REDBLK_T is the
37 : node or element type. It must include the following fields:
38 :
39 : ulong redblack_parent;
40 : ulong redblack_left;
41 : ulong redblack_right;
42 : int redblack_color;
43 :
44 : which are used by the redblack tree. Everything else in the node
45 : type is up to the application.
46 :
47 : This example creates the following API for use in the local compilation unit:
48 :
49 : ulong my_rb_max_for_footprint( ulong footprint );
50 : ulong my_rb_align( void );
51 : ulong my_rb_footprint( ulong max );
52 : void * my_rb_new( void * shmem, ulong max );
53 : my_rb_node_t * my_rb_join( void * shpool );
54 : void * my_rb_leave( my_rb_node_t * pool );
55 : void * my_rb_delete( void * shpool );
56 : ulong my_rb_max( my_rb_node_t const * pool );
57 : ulong my_rb_free( my_rb_node_t const * pool );
58 : ulong my_rb_idx( my_rb_node_t const * pool, my_rb_node_t const * node );
59 : my_rb_node_t * my_rb_node( my_rb_node_t * pool, ulong idx );
60 : my_rb_node_t * my_rb_acquire( my_rb_node_t * pool );
61 : void my_rb_release( my_rb_node_t * pool, my_rb_node_t * node );
62 : void my_rb_release_tree( my_rb_node_t * pool, my_rb_node_t * root );
63 : my_rb_node_t * my_rb_minimum(my_rb_node_t * pool, my_rb_node_t * root);
64 : my_rb_node_t * my_rb_maximum(my_rb_node_t * pool, my_rb_node_t * root);
65 : my_rb_node_t * my_rb_successor(my_rb_node_t * pool, my_rb_node_t * node);
66 : my_rb_node_t * my_rb_predecessor(my_rb_node_t * pool, my_rb_node_t * node);
67 : my_rb_node_t * my_rb_insert(my_rb_node_t * pool, my_rb_node_t ** root, my_rb_node_t * x);
68 : my_rb_node_t * my_rb_remove(my_rb_node_t * pool, my_rb_node_t ** root, my_rb_node_t * z);
69 : my_rb_node_t * my_rb_find(my_rb_node_t * pool, my_rb_node_t * root, my_rb_node_t * key);
70 : my_rb_node_t * my_rb_nearby(my_rb_node_t * pool, my_rb_node_t * root, my_rb_node_t * key);
71 : ulong my_rb_size(my_rb_node_t * pool, my_rb_node_t * root);
72 : int my_rb_verify(my_rb_node_t * pool, my_rb_node_t * root);
73 : long my_rb_compare(my_rb_node_t * left, my_rb_node_t * right);
74 :
75 : The specific usage and semantics of these methods is given below.
76 :
77 : A sample application is as follows:
78 :
79 : my_node_t* pool = my_rb_join( my_rb_new( shmem, 20 ) );
80 : my_node_t* root = NULL;
81 : for (ulong i = 0; i < 10; ++i) {
82 : my_node_t * n = my_rb_acquire( pool );
83 : n->key = 123 + i;
84 : n->value = 456 + i;
85 : my_rb_insert( pool, &root, n );
86 : }
87 : for (ulong i = 0; i < 10; ++i) {
88 : my_node_t k;
89 : k.key = 123 + i;
90 : my_node_t * n = my_rb_find( pool, root, &k );
91 : printf("key=%lu value=%lu\n", n->key, n->value);
92 : n = my_rb_remove( pool, &root, n );
93 : my_rb_release( pool, n );
94 : }
95 : my_rb_delete( my_rb_leave( pool ) );
96 :
97 : The application must provided the compare implementation. It must
98 : return a negative number, zero, or positive depending on whether
99 : the left is less than, equal to, or greater than right. For
100 : example:
101 :
102 : long my_rb_compare(my_node_t* left, my_node_t* right) {
103 : return (long)(left->key - right->key);
104 : }
105 :
106 : */
107 :
108 : #ifndef REDBLK_NAME
109 : #define "Define REDBLK_NAME"
110 : #endif
111 :
112 : #ifndef REDBLK_T
113 : #define "Define REDBLK_T"
114 : #endif
115 :
116 : /* 0 - local use only
117 : 1 - library header declaration
118 : 2 - library implementation */
119 : #ifndef REDBLK_IMPL_STYLE
120 : #define REDBLK_IMPL_STYLE 0
121 : #endif
122 :
123 : /* Constructors and verification logs detail on failure (rest only needs
124 : fd_bits.h, consider making logging a compile time option). */
125 :
126 : #include "../log/fd_log.h"
127 :
128 : /* Namespace macro */
129 17449261330 : #define REDBLK_(n) FD_EXPAND_THEN_CONCAT3(REDBLK_NAME,_,n)
130 :
131 : #if REDBLK_IMPL_STYLE==1 /* need structures and inlines */
132 :
133 : FD_PROTOTYPES_BEGIN
134 :
135 : /*
136 : E.g. ulong my_rb_max_for_footprint( ulong footprint );
137 :
138 : Return the maximum number of nodes that will fit into a pool with
139 : the given footprint.
140 : */
141 : FD_FN_CONST ulong REDBLK_(max_for_footprint)( ulong footprint );
142 :
143 : /*
144 : E.g. ulong my_rb_align( void );
145 :
146 : Return the pool alignment.
147 : */
148 : FD_FN_CONST ulong REDBLK_(align)( void );
149 :
150 : /*
151 : E.g. ulong my_rb_footprint( ulong max );
152 :
153 : Return the minimum memory footprint needed for a pool with the given
154 : number of nodes.
155 : */
156 : FD_FN_CONST ulong REDBLK_(footprint)( ulong max );
157 :
158 : /*
159 : E.g. void * my_rb_new( void * shmem, ulong max );
160 :
161 : Initialize an allocation pool.
162 : */
163 : void * REDBLK_(new)( void * shmem, ulong max );
164 :
165 : /*
166 : E.g. my_rb_node_t * my_rb_join( void * shpool );
167 :
168 : Join an allocation pool.
169 : */
170 : REDBLK_T * REDBLK_(join)( void * shpool );
171 :
172 : /*
173 : E.g. void * my_rb_leave( my_rb_node_t * pool );
174 :
175 : Leave an allocation pool.
176 : */
177 : void * REDBLK_(leave)( REDBLK_T * pool );
178 :
179 : /*
180 : E.g. void * my_rb_delete( void * shpool );
181 :
182 : Delete an allocation pool.
183 : */
184 : void * REDBLK_(delete)( void * shpool );
185 :
186 : /*
187 : E.g. ulong my_rb_max( my_rb_node_t const * pool );
188 :
189 : Return the max value given when new was called.
190 : */
191 : FD_FN_PURE ulong REDBLK_(max)( REDBLK_T const * pool );
192 :
193 : /*
194 : E.g. ulong my_rb_free( my_rb_node_t const * pool );
195 :
196 : Return the number of available nodes in the free pool.
197 : */
198 : FD_FN_PURE ulong REDBLK_(free)( REDBLK_T const * pool );
199 :
200 : /*
201 : E.g. ulong my_rb_idx( my_rb_node_t const * pool, my_rb_node_t const * node );
202 :
203 : Return the logical index of the node in a pool. Useful when
204 : relocating a pool in memory.
205 : */
206 : FD_FN_CONST ulong REDBLK_(idx)( REDBLK_T const * pool, REDBLK_T const * node );
207 :
208 : /*
209 : E.g. my_rb_node_t * my_rb_node( my_rb_node_t * pool, ulong idx );
210 :
211 : Return the node at a logical index in a pool. Useful when relocating
212 : a pool in memory.
213 : */
214 : FD_FN_CONST REDBLK_T * REDBLK_(node)( REDBLK_T * pool, ulong idx );
215 :
216 : /*
217 : E.g. my_rb_node_t * my_rb_acquire( my_rb_node_t * pool );
218 :
219 : Acquire a node from the free pool. The result requires
220 : initialization before insertion. For example:
221 :
222 : my_node_t * n = my_rb_acquire( pool );
223 : n->key = 123 + i;
224 : n->value = 456 + i;
225 : my_rb_insert( pool, &root, n );
226 : */
227 : REDBLK_T * REDBLK_(acquire)( REDBLK_T * pool );
228 :
229 : /*
230 : E.g. void my_rb_release( my_rb_node_t * pool, my_rb_node_t * node );
231 :
232 : Return a node to the free pool. It must be removed from the tree
233 : first. For example:
234 :
235 : my_node_t * n = my_rb_find( pool, root, &k );
236 : n = my_rb_remove( pool, &root, n );
237 : my_rb_release( pool, n );
238 :
239 : */
240 : void REDBLK_(release)( REDBLK_T * pool, REDBLK_T * node );
241 :
242 : /*
243 : E.g. void my_rb_release_tree( my_node_t * pool, my_node_t * root );
244 :
245 : Recursively release all nodes in a tree to a pool. The root argument
246 : is invalid after this method is called.
247 : */
248 : void REDBLK_(release_tree)( REDBLK_T * pool, REDBLK_T * root );
249 :
250 : /*
251 : E.g. my_node_t * my_rb_minimum(my_node_t * pool, my_node_t * root);
252 :
253 : Return the node in a tree that has the smallest key (leftmost).
254 : */
255 : REDBLK_T * REDBLK_(minimum)(REDBLK_T * pool, REDBLK_T * root);
256 : REDBLK_T const * REDBLK_(minimum_const)(REDBLK_T const * pool, REDBLK_T const * root);
257 :
258 : /*
259 : E.g. my_node_t * my_rb_maximum(my_node_t * pool, my_node_t * root);
260 :
261 : Return the node in a tree that has the largest key (rightmost).
262 : */
263 : REDBLK_T * REDBLK_(maximum)(REDBLK_T * pool, REDBLK_T * root);
264 : REDBLK_T const * REDBLK_(maximum_const)(REDBLK_T const * pool, REDBLK_T const * root);
265 :
266 : /*
267 : E.g. my_node_t * my_rb_successor(my_node_t * pool, my_node_t * node);
268 :
269 : Return the next node which is larger than the given node. To iterate
270 : across the entire tree, do the following:
271 :
272 : for ( my_node_t* n = my_rb_minimum(pool, root); n; n = my_rb_successor(pool, n) ) {
273 : printf("key=%lu value=%lu\n", n->key, n->value);
274 : }
275 :
276 : To iterate safely while also deleting, do:
277 :
278 : my_node_t* nn;
279 : for ( my_node_t* n = my_rb_minimum(pool, root); n; n = nn ) {
280 : nn = my_rb_successor(pool, n);
281 : // Possibly delete n
282 : }
283 : */
284 : REDBLK_T * REDBLK_(successor)(REDBLK_T * pool, REDBLK_T * node);
285 : REDBLK_T const * REDBLK_(successor_const)(REDBLK_T const * pool, REDBLK_T const * node);
286 : /*
287 : E.g. my_node_t * my_rb_predecessor(my_node_t * pool, my_node_t * node);
288 :
289 : Return the previous node which is smaller than the given node. To iterate
290 : across the entire tree backwards, do the following:
291 :
292 : for ( my_node_t* n = my_rb_maximum(pool, root); n; n = my_rb_predecessor(pool, n) ) {
293 : printf("key=%lu value=%lu\n", n->key, n->value);
294 : }
295 :
296 : To iterate safely while also deleting, do:
297 :
298 : my_node_t* nn;
299 : for ( my_node_t* n = my_rb_maximum(pool, root); n; n = nn ) {
300 : nn = my_rb_predecessor(pool, n);
301 : // Possibly delete n
302 : }
303 : */
304 : REDBLK_T * REDBLK_(predecessor)(REDBLK_T * pool, REDBLK_T * node);
305 : /*
306 : E.g. my_node_t * my_rb_insert(my_node_t * pool, my_node_t ** root, my_node_t * x);
307 :
308 : Insert a node into a tree. Typically, the node must be allocated
309 : from a pool first. The application must initialize any values in the
310 : node after allocation but before insertion. For example:
311 :
312 : my_node_t * n = my_rb_acquire( pool );
313 : n->key = 123;
314 : n->value = 456;
315 : n = my_rb_insert( pool, &root, n );
316 :
317 : The inserted node is returned.
318 : */
319 : REDBLK_T * REDBLK_(insert)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x);
320 : /*
321 : E.g. my_node_t * my_rb_remove(my_node_t * pool, my_node_t ** root, my_node_t * z);
322 :
323 : Remove a node from a tree. The node must be a member of the tree,
324 : usually the result of a find operation. The node is typically
325 : released to the pool afterwards. For example:
326 :
327 : my_node_t * n = my_rb_find( pool, root, &k );
328 : n = my_rb_remove( pool, &root, n );
329 : my_rb_pool_release( pool, n );
330 :
331 : Remove and release are separate steps to allow an application to
332 : perform final cleanup on the node in between. You can insert a node
333 : into a different tree after deletion if both trees share a pool. For
334 : example:
335 :
336 : n = my_rb_remove( pool, &root, n );
337 : my_rb_insert( pool, &root2, n );
338 : */
339 : REDBLK_T * REDBLK_(remove)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * z);
340 : /*
341 : E.g. my_node_t * my_rb_find(my_node_t * pool, my_node_t * root, my_node_t * key);
342 :
343 : Search for a key in the tree. In this special case, the key can be a
344 : temporary instance of the node type rather than a properly
345 : allocated node. For example:
346 :
347 : my_node_t k;
348 : k.key = 123 + i;
349 : my_node_t * n = my_rb_find( pool, root, &k );
350 : printf("key=%lu value=%lu\n", n->key, n->value);
351 :
352 : A NULL is returned if the find fails.
353 : */
354 : REDBLK_T * REDBLK_(find)(REDBLK_T * pool, REDBLK_T * root, REDBLK_T * key);
355 : /*
356 : E.g. my_node_t * my_rb_nearby(my_node_t * pool, my_node_t * root, my_node_t * key);
357 :
358 : Search for a key in the tree. If the key can't be found, a nearby
359 : approximation is returned instead. This is either the greatest node
360 : less than the key, or the least node greater than the key. In this
361 : special case, the key can be a temporary instance of the node type
362 : rather than a properly allocated node. For example:
363 :
364 : my_node_t k;
365 : k.key = 123 + i;
366 : my_node_t * n = my_rb_nearby( pool, root, &k );
367 : printf("key=%lu value=%lu\n", n->key, n->value);
368 :
369 : A NULL is returned if the search fails.
370 : */
371 : REDBLK_T * REDBLK_(nearby)(REDBLK_T * pool, REDBLK_T * root, REDBLK_T * key);
372 : /*
373 : E.g. ulong my_rb_size(my_node_t * pool, my_node_t * root);
374 :
375 : Count the number of nodes in a tree.
376 : */
377 : ulong REDBLK_(size)(REDBLK_T * pool, REDBLK_T * root);
378 :
379 : /*
380 : E.g. int my_rb_verify(my_node_t * pool, my_node_t * root);
381 :
382 : Verify the integrity of the tree data structure. Useful for
383 : debugging memory corruption. A non-zero result is returned if an error
384 : is detected.
385 : */
386 : int REDBLK_(verify)(REDBLK_T * pool, REDBLK_T * root);
387 :
388 : /*
389 : E.g. long my_rb_compare(my_node_t * left, my_node_t * right);
390 :
391 : Defined by application to implement key comparison. Returns a
392 : negative number, zero, or positive depending on whether the left is
393 : less than, equal to, or greater than right. For example:
394 :
395 : long my_rb_compare(my_node_t* left, my_node_t* right) {
396 : return (long)(left->key - right->key);
397 : }
398 :
399 : Should be a pure function. (FIXME: SHOULD TAKE CONST POINTERS?)
400 : */
401 : FD_FN_PURE long REDBLK_(compare)(REDBLK_T * left, REDBLK_T * right);
402 :
403 : FD_PROTOTYPES_END
404 :
405 : #endif /* REDBLK_IMPL_STYLE==0 || REDBLK_IMPL_STYLE==1 */
406 :
407 : #if REDBLK_IMPL_STYLE==0 /* local only */
408 : #define REDBLK_IMPL_STATIC FD_FN_UNUSED static
409 : #else
410 : #define REDBLK_IMPL_STATIC
411 : #endif
412 :
413 : #if REDBLK_IMPL_STYLE==0 || REDBLK_IMPL_STYLE==2 /* need implementations */
414 :
415 : /* Tree node colors */
416 7240485738 : #define REDBLK_FREE -1
417 335659317 : #define REDBLK_NEW 0
418 3519645278 : #define REDBLK_BLACK 1
419 1057912084 : #define REDBLK_RED 2
420 :
421 : #ifndef REDBLK_PARENT
422 102213567 : #define REDBLK_PARENT redblack_parent
423 : #endif
424 : #ifndef REDBLK_LEFT
425 255942429 : #define REDBLK_LEFT redblack_left
426 : #endif
427 : #ifndef REDBLK_RIGHT
428 410253558 : #define REDBLK_RIGHT redblack_right
429 : #endif
430 : #ifndef REDBLK_COLOR
431 315917442 : #define REDBLK_COLOR redblack_color
432 : #endif
433 :
434 : #define POOL_NAME FD_EXPAND_THEN_CONCAT2(REDBLK_NAME,_pool)
435 3721764 : #define POOL_T REDBLK_T
436 : #define POOL_SENTINEL 1
437 : #ifdef REDBLK_NEXTFREE
438 435485649 : #define POOL_NEXT REDBLK_NEXTFREE
439 : #else
440 173362530 : #define POOL_NEXT REDBLK_RIGHT
441 : #endif
442 : #include "fd_pool.c"
443 : #undef MAP_POOL_NAME
444 : #undef MAP_POOL_T
445 :
446 7734985044 : #define REDBLK_POOL_(n) FD_EXPAND_THEN_CONCAT3(REDBLK_NAME,_pool_,n)
447 :
448 17482294597 : #define REDBLK_NIL 0UL /* Must be same as pool sentinel */
449 :
450 6 : REDBLK_IMPL_STATIC ulong REDBLK_(max_for_footprint)( ulong footprint ) {
451 6 : return REDBLK_POOL_(max_for_footprint)(footprint) - 1; /* Allow for sentinel */
452 6 : }
453 :
454 1644189 : REDBLK_IMPL_STATIC ulong REDBLK_(align)( void ) {
455 1644189 : return REDBLK_POOL_(align)();
456 1644189 : }
457 :
458 1644195 : REDBLK_IMPL_STATIC ulong REDBLK_(footprint)( ulong max ) {
459 1644195 : return REDBLK_POOL_(footprint)(max + 1); /* Allow for sentinel */
460 1644195 : }
461 :
462 1236336 : REDBLK_IMPL_STATIC void * REDBLK_(new)( void * shmem, ulong max ) {
463 1236336 : void * shmem2 = REDBLK_POOL_(new)(shmem, max + 1); /* Allow for sentinel */
464 1236336 : if ( FD_UNLIKELY( shmem2 == NULL ) )
465 0 : return NULL;
466 : /* Initialize sentinel */
467 1236336 : REDBLK_T * pool = REDBLK_POOL_(join)(shmem2);
468 1236336 : if ( FD_UNLIKELY( pool == NULL ) )
469 0 : return NULL;
470 1236336 : REDBLK_T * node = REDBLK_POOL_(ele_sentinel)(pool);
471 1236336 : node->REDBLK_LEFT = REDBLK_NIL;
472 1236336 : node->REDBLK_RIGHT = REDBLK_NIL;
473 1236336 : node->REDBLK_PARENT = REDBLK_NIL;
474 1236336 : node->REDBLK_COLOR = REDBLK_BLACK;
475 1236336 : return shmem2;
476 1236336 : }
477 :
478 1236345 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(join)( void * shpool ) {
479 1236345 : FD_COMPILER_MFENCE();
480 1236345 : return REDBLK_POOL_(join)(shpool);
481 1236345 : }
482 :
483 4078605 : REDBLK_IMPL_STATIC void * REDBLK_(leave)( REDBLK_T * pool ) {
484 4078605 : FD_COMPILER_MFENCE();
485 4078605 : return REDBLK_POOL_(leave)(pool);
486 4078605 : }
487 :
488 4078596 : REDBLK_IMPL_STATIC void * REDBLK_(delete)( void * shpool ) {
489 4078596 : FD_COMPILER_MFENCE();
490 4078596 : return REDBLK_POOL_(delete)(shpool);
491 4078596 : }
492 :
493 15 : REDBLK_IMPL_STATIC ulong REDBLK_(max)( REDBLK_T const * pool ) {
494 15 : return REDBLK_POOL_(max)(pool) - 1; /* Allow for sentinel */
495 15 : }
496 :
497 69 : REDBLK_IMPL_STATIC ulong REDBLK_(free)( REDBLK_T const * pool ) {
498 69 : return REDBLK_POOL_(free)(pool);
499 69 : }
500 :
501 9 : REDBLK_IMPL_STATIC ulong REDBLK_(idx)( REDBLK_T const * pool, REDBLK_T const * node ) {
502 9 : return REDBLK_POOL_(idx)(pool, node);
503 9 : }
504 :
505 9 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(node)( REDBLK_T * pool, ulong idx ) {
506 9 : return REDBLK_POOL_(ele)(pool, idx);
507 9 : }
508 :
509 222711678 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(acquire)( REDBLK_T * pool ) {
510 222711678 : if ( REDBLK_POOL_(free)( pool ) == 0 )
511 3009 : return NULL;
512 222708669 : REDBLK_T * node = REDBLK_POOL_(ele_acquire)(pool);
513 222708669 : node->REDBLK_COLOR = REDBLK_NEW;
514 222708669 : return node;
515 222711678 : }
516 :
517 : #ifndef REDBLK_UNSAFE
518 7051331523 : REDBLK_IMPL_STATIC void REDBLK_(validate_element)( REDBLK_T * pool, REDBLK_T * node ) {
519 7051331523 : if ( !REDBLK_POOL_(ele_test)( pool, node ) )
520 0 : FD_LOG_ERR(( "invalid redblack node" ));
521 7051331523 : if ( node && node->REDBLK_COLOR == REDBLK_FREE )
522 0 : FD_LOG_ERR(( "invalid redblack node" ));
523 7051331523 : }
524 0 : REDBLK_IMPL_STATIC void REDBLK_(validate_element_const)( REDBLK_T const * pool, REDBLK_T const * node ) {
525 0 : if ( !REDBLK_POOL_(ele_test)( pool, node ) )
526 0 : FD_LOG_ERR(( "invalid redblack node" ));
527 0 : if ( node && node->REDBLK_COLOR == REDBLK_FREE )
528 0 : FD_LOG_ERR(( "invalid redblack node" ));
529 0 : }
530 : #endif
531 :
532 221842128 : REDBLK_IMPL_STATIC void REDBLK_(release)( REDBLK_T * pool, REDBLK_T * node ) {
533 221842128 : #ifndef REDBLK_UNSAFE
534 221842128 : REDBLK_(validate_element)(pool, node);
535 221842128 : #endif
536 :
537 221842128 : node->REDBLK_COLOR = REDBLK_FREE;
538 221842128 : REDBLK_POOL_(ele_release)(pool, node);
539 221842128 : }
540 :
541 : /*
542 : Recursively release all nodes in a tree to a pool. The root argument
543 : is invalid after this method is called.
544 : */
545 239555949 : REDBLK_IMPL_STATIC void REDBLK_(release_tree)( REDBLK_T * pool, REDBLK_T * node ) {
546 239555949 : if (!node || node == &pool[REDBLK_NIL])
547 130664469 : return;
548 :
549 108891480 : #ifndef REDBLK_UNSAFE
550 108891480 : REDBLK_(validate_element)(pool, node);
551 108891480 : #endif
552 :
553 108891480 : REDBLK_T * left = &pool[node->REDBLK_LEFT];
554 108891480 : REDBLK_T * right = &pool[node->REDBLK_RIGHT];
555 :
556 108891480 : REDBLK_(release)(pool, node);
557 :
558 108891480 : REDBLK_(release_tree)(pool, left);
559 108891480 : REDBLK_(release_tree)(pool, right);
560 108891480 : }
561 :
562 : /*
563 : Return the node in a tree that has the smallest key (leftmost).
564 : */
565 6573861 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(minimum)(REDBLK_T * pool, REDBLK_T * node) {
566 6573861 : if (!node || node == &pool[REDBLK_NIL])
567 4081290 : return NULL;
568 2492571 : #ifndef REDBLK_UNSAFE
569 2492571 : REDBLK_(validate_element)(pool, node);
570 2492571 : #endif
571 4966503 : while (node->REDBLK_LEFT != REDBLK_NIL) {
572 2473932 : node = &pool[node->REDBLK_LEFT];
573 2473932 : }
574 2492571 : return node;
575 6573861 : }
576 0 : REDBLK_IMPL_STATIC REDBLK_T const * REDBLK_(minimum_const)(REDBLK_T const * pool, REDBLK_T const * node) {
577 0 : if (!node || node == &pool[REDBLK_NIL])
578 0 : return NULL;
579 0 : #ifndef REDBLK_UNSAFE
580 0 : REDBLK_(validate_element_const)(pool, node);
581 0 : #endif
582 0 : while (node->REDBLK_LEFT != REDBLK_NIL) {
583 0 : node = &pool[node->REDBLK_LEFT];
584 0 : }
585 0 : return node;
586 0 : }
587 :
588 : /*
589 : Return the node in a tree that has the largest key (rightmost).
590 : */
591 2041752 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(maximum)(REDBLK_T * pool, REDBLK_T * node) {
592 2041752 : if (!node || node == &pool[REDBLK_NIL])
593 0 : return NULL;
594 2041752 : #ifndef REDBLK_UNSAFE
595 2041752 : REDBLK_(validate_element)(pool, node);
596 2041752 : #endif
597 4083000 : while (node->REDBLK_RIGHT != REDBLK_NIL) {
598 2041248 : node = &pool[node->REDBLK_RIGHT];
599 2041248 : }
600 2041752 : return node;
601 2041752 : }
602 0 : REDBLK_IMPL_STATIC REDBLK_T const * REDBLK_(maximum_const)(REDBLK_T const * pool, REDBLK_T const * node) {
603 0 : if (!node || node == &pool[REDBLK_NIL])
604 0 : return NULL;
605 0 : #ifndef REDBLK_UNSAFE
606 0 : REDBLK_(validate_element_const)(pool, node);
607 0 : #endif
608 0 : while (node->REDBLK_RIGHT != REDBLK_NIL) {
609 0 : node = &pool[node->REDBLK_RIGHT];
610 0 : }
611 0 : return node;
612 0 : }
613 :
614 : /*
615 : Return the next node which is larger than the given node.
616 : */
617 4966488 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(successor)(REDBLK_T * pool, REDBLK_T * x) {
618 4966488 : #ifndef REDBLK_UNSAFE
619 4966488 : REDBLK_(validate_element)(pool, x);
620 4966488 : #endif
621 :
622 : // if the right subtree is not null,
623 : // the successor is the leftmost node in the
624 : // right subtree
625 4966488 : if (x->REDBLK_RIGHT != REDBLK_NIL) {
626 2476779 : return REDBLK_(minimum)(pool, &pool[x->REDBLK_RIGHT]);
627 2476779 : }
628 :
629 : // else it is the lowest ancestor of x whose
630 : // left child is also an ancestor of x.
631 4966488 : for (;;) {
632 4966488 : if (x->REDBLK_PARENT == REDBLK_NIL)
633 15780 : return NULL;
634 4950708 : REDBLK_T * y = &pool[x->REDBLK_PARENT];
635 4950708 : if (x == &pool[y->REDBLK_LEFT])
636 2473929 : return y;
637 2476779 : x = y;
638 2476779 : }
639 2489709 : }
640 0 : REDBLK_IMPL_STATIC REDBLK_T const * REDBLK_(successor_const)(REDBLK_T const * pool, REDBLK_T const * x) {
641 0 : #ifndef REDBLK_UNSAFE
642 0 : REDBLK_(validate_element_const)(pool, x);
643 0 : #endif
644 :
645 : // if the right subtree is not null,
646 : // the successor is the leftmost node in the
647 : // right subtree
648 0 : if (x->REDBLK_RIGHT != REDBLK_NIL) {
649 0 : return REDBLK_(minimum_const)(pool, &pool[x->REDBLK_RIGHT]);
650 0 : }
651 :
652 : // else it is the lowest ancestor of x whose
653 : // left child is also an ancestor of x.
654 0 : for (;;) {
655 0 : if (x->REDBLK_PARENT == REDBLK_NIL)
656 0 : return NULL;
657 0 : REDBLK_T const * y = &pool[x->REDBLK_PARENT];
658 0 : if (x == &pool[y->REDBLK_LEFT])
659 0 : return y;
660 0 : x = y;
661 0 : }
662 0 : }
663 :
664 : /*
665 : Return the previous node which is smaller than the given node.
666 : */
667 4083000 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(predecessor)(REDBLK_T * pool, REDBLK_T * x) {
668 4083000 : #ifndef REDBLK_UNSAFE
669 4083000 : REDBLK_(validate_element)(pool, x);
670 4083000 : #endif
671 :
672 : // if the left subtree is not null,
673 : // the predecessor is the rightmost node in the
674 : // left subtree
675 4083000 : if (x->REDBLK_LEFT != REDBLK_NIL) {
676 2038752 : return REDBLK_(maximum)(pool, &pool[x->REDBLK_LEFT]);
677 2038752 : }
678 :
679 : // else it is the lowest ancestor of x whose
680 : // right child is also an ancestor of x.
681 4083000 : for (;;) {
682 4083000 : if (x->REDBLK_PARENT == REDBLK_NIL)
683 3000 : return NULL;
684 4080000 : REDBLK_T * y = &pool[x->REDBLK_PARENT];
685 4080000 : if (x == &pool[y->REDBLK_RIGHT])
686 2041248 : return y;
687 2038752 : x = y;
688 2038752 : }
689 2044248 : }
690 0 : REDBLK_IMPL_STATIC REDBLK_T const * REDBLK_(predecessor_const)(REDBLK_T const * pool, REDBLK_T const * x) {
691 0 : #ifndef REDBLK_UNSAFE
692 0 : REDBLK_(validate_element_const)(pool, x);
693 0 : #endif
694 :
695 : // if the left subtree is not null,
696 : // the predecessor is the rightmost node in the
697 : // left subtree
698 0 : if (x->REDBLK_LEFT != REDBLK_NIL) {
699 0 : return REDBLK_(maximum_const)(pool, &pool[x->REDBLK_LEFT]);
700 0 : }
701 :
702 : // else it is the lowest ancestor of x whose
703 : // right child is also an ancestor of x.
704 0 : for (;;) {
705 0 : if (x->REDBLK_PARENT == REDBLK_NIL)
706 0 : return NULL;
707 0 : REDBLK_T const * y = &pool[x->REDBLK_PARENT];
708 0 : if (x == &pool[y->REDBLK_RIGHT])
709 0 : return y;
710 0 : x = y;
711 0 : }
712 0 : }
713 :
714 : /*
715 : Perform a left rotation around a node
716 : */
717 98537289 : static void REDBLK_(rotateLeft)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
718 98537289 : REDBLK_T * y = &pool[x->REDBLK_RIGHT];
719 :
720 : /* establish x->REDBLK_RIGHT link */
721 98537289 : x->REDBLK_RIGHT = y->REDBLK_LEFT;
722 98537289 : if (y->REDBLK_LEFT != REDBLK_NIL)
723 24209578 : pool[y->REDBLK_LEFT].REDBLK_PARENT = (uint)(x - pool);
724 :
725 : /* establish y->REDBLK_PARENT link */
726 98537289 : if (y != &pool[REDBLK_NIL])
727 98537289 : y->REDBLK_PARENT = x->REDBLK_PARENT;
728 98537289 : if (x->REDBLK_PARENT) {
729 63718654 : REDBLK_T * p = &pool[x->REDBLK_PARENT];
730 63718654 : if (x == &pool[p->REDBLK_LEFT])
731 17128997 : p->REDBLK_LEFT = (uint)(y - pool);
732 46589657 : else
733 46589657 : p->REDBLK_RIGHT = (uint)(y - pool);
734 63718654 : } else {
735 34818635 : *root = y;
736 34818635 : }
737 :
738 : /* link x and y */
739 98537289 : y->REDBLK_LEFT = (uint)(x - pool);
740 98537289 : if (x != &pool[REDBLK_NIL])
741 98537289 : x->REDBLK_PARENT = (uint)(y - pool);
742 98537289 : }
743 :
744 : /*
745 : Perform a right rotation around a node
746 : */
747 34662819 : static void REDBLK_(rotateRight)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
748 34662819 : REDBLK_T * y = &pool[x->REDBLK_LEFT];
749 :
750 : /* establish x->REDBLK_LEFT link */
751 34662819 : x->REDBLK_LEFT = y->REDBLK_RIGHT;
752 34662819 : if (y->REDBLK_RIGHT != REDBLK_NIL)
753 5561997 : pool[y->REDBLK_RIGHT].REDBLK_PARENT = (uint)(x - pool);
754 :
755 : /* establish y->REDBLK_PARENT link */
756 34662819 : if (y != &pool[REDBLK_NIL])
757 34662819 : y->REDBLK_PARENT = x->REDBLK_PARENT;
758 34662819 : if (x->REDBLK_PARENT) {
759 24535729 : REDBLK_T * p = &pool[x->REDBLK_PARENT];
760 24535729 : if (x == &pool[p->REDBLK_RIGHT])
761 16422924 : p->REDBLK_RIGHT = (uint)(y - pool);
762 8112805 : else
763 8112805 : p->REDBLK_LEFT = (uint)(y - pool);
764 24535729 : } else {
765 10127090 : *root = y;
766 10127090 : }
767 :
768 : /* link x and y */
769 34662819 : y->REDBLK_RIGHT = (uint)(x - pool);
770 34662819 : if (x != &pool[REDBLK_NIL])
771 34662819 : x->REDBLK_PARENT = (uint)(y - pool);
772 34662819 : }
773 :
774 : /*
775 : Restore tree invariants after an insert.
776 : */
777 222708669 : static void REDBLK_(insertFixup)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
778 : /* check Red-Black properties */
779 222708669 : REDBLK_T * p;
780 397906283 : while (x != *root && (p = &pool[x->REDBLK_PARENT])->REDBLK_COLOR == REDBLK_RED) {
781 : /* we have a violation */
782 175197614 : REDBLK_T * gp = &pool[p->REDBLK_PARENT];
783 175197614 : if (x->REDBLK_PARENT == gp->REDBLK_LEFT) {
784 33164562 : REDBLK_T * y = &pool[gp->REDBLK_RIGHT];
785 33164562 : if (y->REDBLK_COLOR == REDBLK_RED) {
786 :
787 : /* uncle is REDBLK_RED */
788 16404519 : p->REDBLK_COLOR = REDBLK_BLACK;
789 16404519 : y->REDBLK_COLOR = REDBLK_BLACK;
790 16404519 : gp->REDBLK_COLOR = REDBLK_RED;
791 16404519 : x = gp;
792 16760043 : } else {
793 :
794 : /* uncle is REDBLK_BLACK */
795 16760043 : if (x == &pool[p->REDBLK_RIGHT]) {
796 : /* make x a left child */
797 8376788 : x = p;
798 8376788 : REDBLK_(rotateLeft)(pool, root, x);
799 8376788 : p = &pool[x->REDBLK_PARENT];
800 8376788 : gp = &pool[p->REDBLK_PARENT];
801 8376788 : }
802 :
803 : /* recolor and rotate */
804 16760043 : p->REDBLK_COLOR = REDBLK_BLACK;
805 16760043 : gp->REDBLK_COLOR = REDBLK_RED;
806 16760043 : REDBLK_(rotateRight)(pool, root, gp);
807 16760043 : }
808 :
809 142033052 : } else {
810 : /* mirror image of above code */
811 142033052 : REDBLK_T * y = &pool[gp->REDBLK_LEFT];
812 142033052 : if (y->REDBLK_COLOR == REDBLK_RED) {
813 :
814 : /* uncle is REDBLK_RED */
815 70837021 : p->REDBLK_COLOR = REDBLK_BLACK;
816 70837021 : y->REDBLK_COLOR = REDBLK_BLACK;
817 70837021 : gp->REDBLK_COLOR = REDBLK_RED;
818 70837021 : x = gp;
819 71196031 : } else {
820 :
821 : /* uncle is REDBLK_BLACK */
822 71196031 : if (x == &pool[p->REDBLK_LEFT]) {
823 8376374 : x = p;
824 8376374 : REDBLK_(rotateRight)(pool, root, x);
825 8376374 : p = &pool[x->REDBLK_PARENT];
826 8376374 : gp = &pool[p->REDBLK_PARENT];
827 8376374 : }
828 71196031 : p->REDBLK_COLOR = REDBLK_BLACK;
829 71196031 : gp->REDBLK_COLOR = REDBLK_RED;
830 71196031 : REDBLK_(rotateLeft)(pool, root, gp);
831 71196031 : }
832 142033052 : }
833 175197614 : }
834 :
835 222708669 : (*root)->REDBLK_COLOR = REDBLK_BLACK;
836 222708669 : }
837 :
838 : /*
839 : Insert a node into a tree. Typically, the node must be allocated
840 : from a pool first.
841 : */
842 222708669 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(insert)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
843 222708669 : #ifndef REDBLK_UNSAFE
844 222708669 : REDBLK_(validate_element)(pool, *root);
845 222708669 : REDBLK_(validate_element)(pool, x);
846 222708669 : #endif
847 :
848 222708669 : REDBLK_T * current;
849 222708669 : REDBLK_T * parent;
850 :
851 : /* find where node belongs */
852 222708669 : current = *root;
853 222708669 : if (current == NULL)
854 21788718 : current = &pool[REDBLK_NIL];
855 222708669 : parent = &pool[REDBLK_NIL];
856 804867294 : while (current != &pool[REDBLK_NIL]) {
857 582158625 : long c = REDBLK_(compare)(x, current);
858 582158625 : parent = current;
859 582158625 : current = (c < 0 ? &pool[current->REDBLK_LEFT] : &pool[current->REDBLK_RIGHT]);
860 582158625 : }
861 :
862 : /* setup new node */
863 222708669 : x->REDBLK_PARENT = (uint)(parent - pool);
864 222708669 : x->REDBLK_LEFT = REDBLK_NIL;
865 222708669 : x->REDBLK_RIGHT = REDBLK_NIL;
866 222708669 : x->REDBLK_COLOR = REDBLK_RED;
867 :
868 : /* insert node in tree */
869 222708669 : if (parent != &pool[REDBLK_NIL]) {
870 200919951 : long c = REDBLK_(compare)(x, parent);
871 200919951 : if (c < 0)
872 51466511 : parent->REDBLK_LEFT = (uint)(x - pool);
873 149453440 : else
874 149453440 : parent->REDBLK_RIGHT = (uint)(x - pool);
875 200919951 : } else {
876 21788718 : *root = x;
877 21788718 : }
878 :
879 222708669 : REDBLK_(insertFixup)(pool, root, x);
880 222708669 : return x;
881 222708669 : }
882 :
883 : /*
884 : Restore tree invariants after a delete
885 : */
886 92124657 : static void REDBLK_(deleteFixup)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
887 166922274 : while (x != *root && x->REDBLK_COLOR == REDBLK_BLACK) {
888 74797617 : REDBLK_T * p = &pool[x->REDBLK_PARENT];
889 74797617 : if (x == &pool[p->REDBLK_LEFT]) {
890 37308685 : REDBLK_T * w = &pool[p->REDBLK_RIGHT];
891 37308685 : if (w->REDBLK_COLOR == REDBLK_RED) {
892 4179985 : w->REDBLK_COLOR = REDBLK_BLACK;
893 4179985 : p->REDBLK_COLOR = REDBLK_RED;
894 4179985 : REDBLK_(rotateLeft)(pool, root, p);
895 4179985 : p = &pool[x->REDBLK_PARENT];
896 4179985 : w = &pool[p->REDBLK_RIGHT];
897 4179985 : }
898 37308685 : if (pool[w->REDBLK_LEFT].REDBLK_COLOR == REDBLK_BLACK &&
899 37308685 : pool[w->REDBLK_RIGHT].REDBLK_COLOR == REDBLK_BLACK) {
900 25543674 : w->REDBLK_COLOR = REDBLK_RED;
901 25543674 : x = p;
902 25543674 : } else {
903 11765011 : if (pool[w->REDBLK_RIGHT].REDBLK_COLOR == REDBLK_BLACK) {
904 1505681 : pool[w->REDBLK_LEFT].REDBLK_COLOR = REDBLK_BLACK;
905 1505681 : w->REDBLK_COLOR = REDBLK_RED;
906 1505681 : REDBLK_(rotateRight)(pool, root, w);
907 1505681 : p = &pool[x->REDBLK_PARENT];
908 1505681 : w = &pool[p->REDBLK_RIGHT];
909 1505681 : }
910 11765011 : w->REDBLK_COLOR = p->REDBLK_COLOR;
911 11765011 : p->REDBLK_COLOR = REDBLK_BLACK;
912 11765011 : pool[w->REDBLK_RIGHT].REDBLK_COLOR = REDBLK_BLACK;
913 11765011 : REDBLK_(rotateLeft)(pool, root, p);
914 11765011 : x = *root;
915 11765011 : }
916 :
917 37488932 : } else {
918 37488932 : REDBLK_T * w = &pool[p->REDBLK_LEFT];
919 37488932 : if (w->REDBLK_COLOR == REDBLK_RED) {
920 1499667 : w->REDBLK_COLOR = REDBLK_BLACK;
921 1499667 : p->REDBLK_COLOR = REDBLK_RED;
922 1499667 : REDBLK_(rotateRight)(pool, root, p);
923 1499667 : p = &pool[x->REDBLK_PARENT];
924 1499667 : w = &pool[p->REDBLK_LEFT];
925 1499667 : }
926 37488932 : if (pool[w->REDBLK_RIGHT].REDBLK_COLOR == REDBLK_BLACK &&
927 37488932 : pool[w->REDBLK_LEFT].REDBLK_COLOR == REDBLK_BLACK) {
928 30967878 : w->REDBLK_COLOR = REDBLK_RED;
929 30967878 : x = p;
930 30967878 : } else {
931 6521054 : if (pool[w->REDBLK_LEFT].REDBLK_COLOR == REDBLK_BLACK) {
932 3019474 : pool[w->REDBLK_RIGHT].REDBLK_COLOR = REDBLK_BLACK;
933 3019474 : w->REDBLK_COLOR = REDBLK_RED;
934 3019474 : REDBLK_(rotateLeft)(pool, root, w);
935 3019474 : p = &pool[x->REDBLK_PARENT];
936 3019474 : w = &pool[p->REDBLK_LEFT];
937 3019474 : }
938 6521054 : w->REDBLK_COLOR = p->REDBLK_COLOR;
939 6521054 : p->REDBLK_COLOR = REDBLK_BLACK;
940 6521054 : pool[w->REDBLK_LEFT].REDBLK_COLOR = REDBLK_BLACK;
941 6521054 : REDBLK_(rotateRight)(pool, root, p);
942 6521054 : x = *root;
943 6521054 : }
944 37488932 : }
945 74797617 : }
946 :
947 92124657 : x->REDBLK_COLOR = REDBLK_BLACK;
948 92124657 : }
949 :
950 : /*
951 : Remove a node from a tree. The node must be a member of the tree,
952 : usually the result of a find operation. The node is typically
953 : released to the pool afterwards.
954 : */
955 112950648 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(remove)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * z) {
956 112950648 : #ifndef REDBLK_UNSAFE
957 112950648 : REDBLK_(validate_element)(pool, *root);
958 112950648 : REDBLK_(validate_element)(pool, z);
959 112950648 : #endif
960 :
961 112950648 : REDBLK_T * x;
962 112950648 : REDBLK_T * y;
963 :
964 112950648 : if (!z || z == &pool[REDBLK_NIL])
965 0 : return NULL;
966 :
967 112950648 : if (z->REDBLK_LEFT == REDBLK_NIL || z->REDBLK_RIGHT == REDBLK_NIL) {
968 : /* y has a REDBLK_NIL node as a child */
969 81489266 : y = z;
970 81489266 : } else {
971 : /* find tree successor with a REDBLK_NIL node as a child */
972 31461382 : y = &pool[z->REDBLK_RIGHT];
973 43608918 : while (y->REDBLK_LEFT != REDBLK_NIL)
974 12147536 : y = &pool[y->REDBLK_LEFT];
975 31461382 : }
976 :
977 : /* x is y's only child */
978 112950648 : if (y->REDBLK_LEFT != REDBLK_NIL)
979 9310926 : x = &pool[y->REDBLK_LEFT];
980 103639722 : else
981 103639722 : x = &pool[y->REDBLK_RIGHT];
982 :
983 : /* remove y from the parent chain */
984 112950648 : x->REDBLK_PARENT = y->REDBLK_PARENT;
985 112950648 : if (y->REDBLK_PARENT)
986 96616488 : if (y == &pool[pool[y->REDBLK_PARENT].REDBLK_LEFT])
987 45041392 : pool[y->REDBLK_PARENT].REDBLK_LEFT = (uint)(x - pool);
988 51575096 : else
989 51575096 : pool[y->REDBLK_PARENT].REDBLK_RIGHT = (uint)(x - pool);
990 16334160 : else
991 16334160 : *root = x;
992 :
993 112950648 : if (y->REDBLK_COLOR == REDBLK_BLACK)
994 92124657 : REDBLK_(deleteFixup)(pool, root, x);
995 :
996 112950648 : if (y != z) {
997 : /* we got rid of y instead of z. Oops! Replace z with y in the
998 : * tree so we don't lose y's key/value. */
999 31461382 : y->REDBLK_PARENT = z->REDBLK_PARENT;
1000 31461382 : y->REDBLK_LEFT = z->REDBLK_LEFT;
1001 31461382 : y->REDBLK_RIGHT = z->REDBLK_RIGHT;
1002 31461382 : y->REDBLK_COLOR = z->REDBLK_COLOR;
1003 31461382 : if (z == *root)
1004 13492890 : *root = y;
1005 17968492 : else if (&pool[pool[y->REDBLK_PARENT].REDBLK_LEFT] == z)
1006 5629778 : pool[y->REDBLK_PARENT].REDBLK_LEFT = (uint)(y - pool);
1007 12338714 : else
1008 12338714 : pool[y->REDBLK_PARENT].REDBLK_RIGHT = (uint)(y - pool);
1009 31461382 : pool[y->REDBLK_LEFT].REDBLK_PARENT = (uint)(y - pool);
1010 31461382 : pool[y->REDBLK_RIGHT].REDBLK_PARENT = (uint)(y - pool);
1011 31461382 : }
1012 :
1013 112950648 : if (*root == &pool[REDBLK_NIL])
1014 10889451 : *root = NULL;
1015 112950648 : z->REDBLK_COLOR = REDBLK_NEW;
1016 112950648 : return z;
1017 112950648 : }
1018 :
1019 : /*
1020 : Search for a key in the tree. In this special case, the key can be a
1021 : temporary instance of the node type rather than a properly
1022 : allocated node.
1023 : */
1024 447793125 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(find)(REDBLK_T * pool, REDBLK_T * root, REDBLK_T * key) {
1025 447793125 : #ifndef REDBLK_UNSAFE
1026 447793125 : REDBLK_(validate_element)(pool, root);
1027 447793125 : #endif
1028 :
1029 447793125 : REDBLK_T * current = root;
1030 447793125 : if (current == NULL || current == &pool[REDBLK_NIL])
1031 10886454 : return NULL;
1032 1330290858 : while (current != &pool[REDBLK_NIL]) {
1033 1232269122 : long c = REDBLK_(compare)(key, current);
1034 1232269122 : if (c == 0)
1035 338884935 : return current;
1036 893384187 : current = (c < 0 ? &pool[current->REDBLK_LEFT] : &pool[current->REDBLK_RIGHT]);
1037 893384187 : }
1038 98021736 : return NULL;
1039 436906671 : }
1040 :
1041 : /*
1042 : Search for a key in the tree. If the key can't be found, a nearby
1043 : approximation is returned instead. This is either the greatest node
1044 : less than the key, or the least node greater than the key. In this
1045 : special case, the key can be a temporary instance of the node type
1046 : rather than a properly allocated node.
1047 : */
1048 0 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(nearby)(REDBLK_T * pool, REDBLK_T * root, REDBLK_T * key) {
1049 0 : #ifndef REDBLK_UNSAFE
1050 0 : REDBLK_(validate_element)(pool, root);
1051 0 : #endif
1052 :
1053 0 : REDBLK_T * current = root;
1054 0 : if (current == NULL || current == &pool[REDBLK_NIL])
1055 0 : return NULL;
1056 0 : REDBLK_T * result = current;
1057 0 : while (current != &pool[REDBLK_NIL]) {
1058 0 : result = current; /* Return the last non-NIL node that was touched */
1059 0 : long c = REDBLK_(compare)(key, current);
1060 0 : if (c == 0)
1061 0 : return current;
1062 0 : current = (c < 0 ? &pool[current->REDBLK_LEFT] : &pool[current->REDBLK_RIGHT]);
1063 0 : }
1064 0 : return result;
1065 0 : }
1066 :
1067 : /*
1068 : Count the number of nodes in a tree.
1069 : */
1070 3887292116 : REDBLK_IMPL_STATIC ulong REDBLK_(size)(REDBLK_T * pool, REDBLK_T * root) {
1071 3887292116 : #ifndef REDBLK_UNSAFE
1072 3887292116 : REDBLK_(validate_element)(pool, root);
1073 3887292116 : #endif
1074 3887292116 : if (!root || root == &pool[REDBLK_NIL])
1075 2101941784 : return 0;
1076 1785350332 : return 1 +
1077 1785350332 : REDBLK_(size)(pool, &pool[root->REDBLK_LEFT]) +
1078 1785350332 : REDBLK_(size)(pool, &pool[root->REDBLK_RIGHT]);
1079 3887292116 : }
1080 :
1081 : /*
1082 : Recursive implementation of the verify function
1083 : */
1084 3716939249 : static int REDBLK_(verify_private)(REDBLK_T * pool, REDBLK_T * node, REDBLK_T * parent, ulong curblkcnt, ulong correctblkcnt) {
1085 7272429818 : # define REDBLK_TEST(c) do { \
1086 7272429818 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
1087 7272429818 : } while(0)
1088 :
1089 3716939249 : if (!node || node == &pool[REDBLK_NIL]) {
1090 2016329020 : REDBLK_TEST(curblkcnt == correctblkcnt);
1091 2016329020 : return 0;
1092 2016329020 : }
1093 :
1094 1700610229 : #ifndef REDBLK_UNSAFE
1095 1700610229 : REDBLK_(validate_element)(pool, node);
1096 1700610229 : #endif
1097 :
1098 1700610229 : REDBLK_TEST(&pool[node->REDBLK_PARENT] == parent);
1099 :
1100 1700610229 : if (node->REDBLK_COLOR == REDBLK_BLACK)
1101 1094333574 : ++curblkcnt;
1102 606276655 : else {
1103 606276655 : REDBLK_TEST(node->REDBLK_COLOR == REDBLK_RED);
1104 606276655 : REDBLK_TEST(parent->REDBLK_COLOR == REDBLK_BLACK);
1105 606276655 : }
1106 :
1107 1700610229 : if (node->REDBLK_LEFT != REDBLK_NIL)
1108 663935574 : REDBLK_TEST(REDBLK_(compare)(&pool[node->REDBLK_LEFT], node) <= 0);
1109 1700610229 : if (node->REDBLK_RIGHT != REDBLK_NIL)
1110 720955864 : REDBLK_TEST(REDBLK_(compare)(node, &pool[node->REDBLK_RIGHT]) <= 0);
1111 :
1112 1700610229 : int err = REDBLK_(verify_private)(pool, &pool[node->REDBLK_LEFT], node, curblkcnt, correctblkcnt);
1113 1700610229 : if (err) return err;
1114 1700610229 : return REDBLK_(verify_private)(pool, &pool[node->REDBLK_RIGHT], node, curblkcnt, correctblkcnt);
1115 1700610229 : }
1116 :
1117 : /*
1118 : Verify the integrity of the tree data structure. Useful for
1119 : debugging memory corruption. A non-zero result is returned if an error
1120 : is detected.
1121 : */
1122 326608239 : REDBLK_IMPL_STATIC int REDBLK_(verify)(REDBLK_T * pool, REDBLK_T * root) {
1123 326608239 : REDBLK_TEST(pool[REDBLK_NIL].REDBLK_LEFT == REDBLK_NIL &&
1124 326608239 : pool[REDBLK_NIL].REDBLK_RIGHT == REDBLK_NIL &&
1125 326608239 : pool[REDBLK_NIL].REDBLK_COLOR == REDBLK_BLACK);
1126 :
1127 326608239 : if (!root || root == &pool[REDBLK_NIL])
1128 10889448 : return 0; // Trivially correct
1129 315718791 : REDBLK_TEST(root->REDBLK_COLOR == REDBLK_BLACK);
1130 :
1131 315718791 : ulong sz = REDBLK_(size)(pool, root);
1132 315718791 : REDBLK_TEST(sz + 1 == REDBLK_POOL_(used)(pool));
1133 :
1134 : // Compute the correct number of black nodes on a path
1135 315718791 : ulong blkcnt = 0;
1136 315718791 : REDBLK_T * node = root;
1137 1047933621 : while (node != &pool[REDBLK_NIL]) {
1138 732214830 : if (node->REDBLK_COLOR == REDBLK_BLACK)
1139 582354819 : ++blkcnt;
1140 732214830 : node = &pool[node->REDBLK_LEFT];
1141 732214830 : }
1142 : // Recursive check
1143 315718791 : return REDBLK_(verify_private)(pool, root, &pool[REDBLK_NIL], 0, blkcnt);
1144 :
1145 315718791 : #undef REDBLK_TEST
1146 315718791 : }
1147 :
1148 : #undef REDBLK_FREE
1149 : #undef REDBLK_NEW
1150 : #undef REDBLK_BLACK
1151 : #undef REDBLK_RED
1152 : #undef REDBLK_POOL_
1153 : #undef REDBLK_PARENT
1154 : #undef REDBLK_LEFT
1155 : #undef REDBLK_RIGHT
1156 : #undef REDBLK_COLOR
1157 :
1158 : #endif /* REDBLK_IMPL_STYLE==0 || REDBLK_IMPL_STYLE==2 */
1159 :
1160 : #undef REDBLK_IMPL_STATIC
1161 : #undef REDBLK_
1162 : #undef REDBLK_T
1163 : #undef REDBLK_IMPL_STYLE
1164 : #undef REDBLK_NAME
|
