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 17433296150 : #define REDBLK_(n) FD_EXPAND_THEN_CONCAT3(REDBLK_NAME,_,n)
130 :
131 : #if REDBLK_IMPL_STYLE==0 || 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 || REDBLK_IMPL_STYLE==2 /* need implementations */
408 :
409 : /* Tree node colors */
410 7232570973 : #define REDBLK_FREE -1
411 335617278 : #define REDBLK_NEW 0
412 3518699120 : #define REDBLK_BLACK 1
413 1057723740 : #define REDBLK_RED 2
414 :
415 : #ifndef REDBLK_PARENT
416 100903023 : #define REDBLK_PARENT redblack_parent
417 : #endif
418 : #ifndef REDBLK_LEFT
419 250650966 : #define REDBLK_LEFT redblack_left
420 : #endif
421 : #ifndef REDBLK_RIGHT
422 287807877 : #define REDBLK_RIGHT redblack_right
423 : #endif
424 : #ifndef REDBLK_COLOR
425 306600477 : #define REDBLK_COLOR redblack_color
426 : #endif
427 :
428 : #define POOL_NAME FD_EXPAND_THEN_CONCAT2(REDBLK_NAME,_pool)
429 1024623 : #define POOL_T REDBLK_T
430 : #define POOL_SENTINEL 1
431 : #ifdef REDBLK_NEXTFREE
432 435485685 : #define POOL_NEXT REDBLK_NEXTFREE
433 : #else
434 56130852 : #define POOL_NEXT REDBLK_RIGHT
435 : #endif
436 : #include "fd_pool.c"
437 : #undef MAP_POOL_NAME
438 : #undef MAP_POOL_T
439 :
440 7715012292 : #define REDBLK_POOL_(n) FD_EXPAND_THEN_CONCAT3(REDBLK_NAME,_pool_,n)
441 :
442 17471312076 : #define REDBLK_NIL 0UL /* Must be same as pool sentinel */
443 :
444 6 : ulong REDBLK_(max_for_footprint)( ulong footprint ) {
445 6 : return REDBLK_POOL_(max_for_footprint)(footprint) - 1; /* Allow for sentinel */
446 6 : }
447 :
448 446526 : ulong REDBLK_(align)( void ) {
449 446526 : return REDBLK_POOL_(align)();
450 446526 : }
451 :
452 446532 : ulong REDBLK_(footprint)( ulong max ) {
453 446532 : return REDBLK_POOL_(footprint)(max + 1); /* Allow for sentinel */
454 446532 : }
455 :
456 337746 : void * REDBLK_(new)( void * shmem, ulong max ) {
457 337746 : void * shmem2 = REDBLK_POOL_(new)(shmem, max + 1); /* Allow for sentinel */
458 337746 : if ( FD_UNLIKELY( shmem2 == NULL ) )
459 0 : return NULL;
460 : /* Initialize sentinel */
461 337746 : REDBLK_T * pool = REDBLK_POOL_(join)(shmem2);
462 337746 : if ( FD_UNLIKELY( pool == NULL ) )
463 0 : return NULL;
464 337746 : REDBLK_T * node = REDBLK_POOL_(ele_sentinel)(pool);
465 337746 : node->REDBLK_LEFT = REDBLK_NIL;
466 337746 : node->REDBLK_RIGHT = REDBLK_NIL;
467 337746 : node->REDBLK_PARENT = REDBLK_NIL;
468 337746 : node->REDBLK_COLOR = REDBLK_BLACK;
469 337746 : return shmem2;
470 337746 : }
471 :
472 337755 : REDBLK_T * REDBLK_(join)( void * shpool ) {
473 337755 : FD_COMPILER_MFENCE();
474 337755 : return REDBLK_POOL_(join)(shpool);
475 337755 : }
476 :
477 1087875 : void * REDBLK_(leave)( REDBLK_T * pool ) {
478 1087875 : FD_COMPILER_MFENCE();
479 1087875 : return REDBLK_POOL_(leave)(pool);
480 1087875 : }
481 :
482 1087866 : void * REDBLK_(delete)( void * shpool ) {
483 1087866 : FD_COMPILER_MFENCE();
484 1087866 : return REDBLK_POOL_(delete)(shpool);
485 1087866 : }
486 :
487 15 : ulong REDBLK_(max)( REDBLK_T const * pool ) {
488 15 : return REDBLK_POOL_(max)(pool) - 1; /* Allow for sentinel */
489 15 : }
490 :
491 66 : ulong REDBLK_(free)( REDBLK_T const * pool ) {
492 66 : return REDBLK_POOL_(free)(pool);
493 66 : }
494 :
495 9 : ulong REDBLK_(idx)( REDBLK_T const * pool, REDBLK_T const * node ) {
496 9 : return REDBLK_POOL_(idx)(pool, node);
497 9 : }
498 :
499 9 : REDBLK_T * REDBLK_(node)( REDBLK_T * pool, ulong idx ) {
500 9 : return REDBLK_POOL_(ele)(pool, idx);
501 9 : }
502 :
503 222669630 : REDBLK_T * REDBLK_(acquire)( REDBLK_T * pool ) {
504 222669630 : if ( REDBLK_POOL_(free)( pool ) == 0 )
505 3009 : return NULL;
506 222666621 : REDBLK_T * node = REDBLK_POOL_(ele_acquire)(pool);
507 222666621 : node->REDBLK_COLOR = REDBLK_NEW;
508 222666621 : return node;
509 222669630 : }
510 :
511 : #ifndef REDBLK_UNSAFE
512 7043413998 : void REDBLK_(validate_element)( REDBLK_T * pool, REDBLK_T * node ) {
513 7043413998 : if ( !REDBLK_POOL_(ele_test)( pool, node ) )
514 0 : FD_LOG_ERR(( "invalid redblack node" ));
515 7043413998 : if ( node && node->REDBLK_COLOR == REDBLK_FREE )
516 0 : FD_LOG_ERR(( "invalid redblack node" ));
517 7043413998 : }
518 0 : void REDBLK_(validate_element_const)( REDBLK_T const * pool, REDBLK_T const * node ) {
519 0 : if ( !REDBLK_POOL_(ele_test)( pool, node ) )
520 0 : FD_LOG_ERR(( "invalid redblack node" ));
521 0 : if ( node && node->REDBLK_COLOR == REDBLK_FREE )
522 0 : FD_LOG_ERR(( "invalid redblack node" ));
523 0 : }
524 : #endif
525 :
526 221842146 : void REDBLK_(release)( REDBLK_T * pool, REDBLK_T * node ) {
527 221842146 : #ifndef REDBLK_UNSAFE
528 221842146 : REDBLK_(validate_element)(pool, node);
529 221842146 : #endif
530 :
531 221842146 : node->REDBLK_COLOR = REDBLK_FREE;
532 221842146 : REDBLK_POOL_(ele_release)(pool, node);
533 221842146 : }
534 :
535 : /*
536 : Recursively release all nodes in a tree to a pool. The root argument
537 : is invalid after this method is called.
538 : */
539 239555967 : void REDBLK_(release_tree)( REDBLK_T * pool, REDBLK_T * node ) {
540 239555967 : if (!node || node == &pool[REDBLK_NIL])
541 130664478 : return;
542 :
543 108891489 : #ifndef REDBLK_UNSAFE
544 108891489 : REDBLK_(validate_element)(pool, node);
545 108891489 : #endif
546 :
547 108891489 : REDBLK_T * left = &pool[node->REDBLK_LEFT];
548 108891489 : REDBLK_T * right = &pool[node->REDBLK_RIGHT];
549 :
550 108891489 : REDBLK_(release)(pool, node);
551 :
552 108891489 : REDBLK_(release_tree)(pool, left);
553 108891489 : REDBLK_(release_tree)(pool, right);
554 108891489 : }
555 :
556 : /*
557 : Return the node in a tree that has the smallest key (leftmost).
558 : */
559 3560868 : REDBLK_T * REDBLK_(minimum)(REDBLK_T * pool, REDBLK_T * node) {
560 3560868 : if (!node || node == &pool[REDBLK_NIL])
561 1090422 : return NULL;
562 2470446 : #ifndef REDBLK_UNSAFE
563 2470446 : REDBLK_(validate_element)(pool, node);
564 2470446 : #endif
565 4923537 : while (node->REDBLK_LEFT != REDBLK_NIL) {
566 2453091 : node = &pool[node->REDBLK_LEFT];
567 2453091 : }
568 2470446 : return node;
569 3560868 : }
570 0 : REDBLK_T const * REDBLK_(minimum_const)(REDBLK_T const * pool, REDBLK_T const * node) {
571 0 : if (!node || node == &pool[REDBLK_NIL])
572 0 : return NULL;
573 0 : #ifndef REDBLK_UNSAFE
574 0 : REDBLK_(validate_element_const)(pool, node);
575 0 : #endif
576 0 : while (node->REDBLK_LEFT != REDBLK_NIL) {
577 0 : node = &pool[node->REDBLK_LEFT];
578 0 : }
579 0 : return node;
580 0 : }
581 :
582 : /*
583 : Return the node in a tree that has the largest key (rightmost).
584 : */
585 2041752 : REDBLK_T * REDBLK_(maximum)(REDBLK_T * pool, REDBLK_T * node) {
586 2041752 : if (!node || node == &pool[REDBLK_NIL])
587 0 : return NULL;
588 2041752 : #ifndef REDBLK_UNSAFE
589 2041752 : REDBLK_(validate_element)(pool, node);
590 2041752 : #endif
591 4083000 : while (node->REDBLK_RIGHT != REDBLK_NIL) {
592 2041248 : node = &pool[node->REDBLK_RIGHT];
593 2041248 : }
594 2041752 : return node;
595 2041752 : }
596 0 : REDBLK_T const * REDBLK_(maximum_const)(REDBLK_T const * pool, REDBLK_T const * node) {
597 0 : if (!node || node == &pool[REDBLK_NIL])
598 0 : return NULL;
599 0 : #ifndef REDBLK_UNSAFE
600 0 : REDBLK_(validate_element_const)(pool, node);
601 0 : #endif
602 0 : while (node->REDBLK_RIGHT != REDBLK_NIL) {
603 0 : node = &pool[node->REDBLK_RIGHT];
604 0 : }
605 0 : return node;
606 0 : }
607 :
608 : /*
609 : Return the next node which is larger than the given node.
610 : */
611 4923522 : REDBLK_T * REDBLK_(successor)(REDBLK_T * pool, REDBLK_T * x) {
612 4923522 : #ifndef REDBLK_UNSAFE
613 4923522 : REDBLK_(validate_element)(pool, x);
614 4923522 : #endif
615 :
616 : // if the right subtree is not null,
617 : // the successor is the leftmost node in the
618 : // right subtree
619 4923522 : if (x->REDBLK_RIGHT != REDBLK_NIL) {
620 2456028 : return REDBLK_(minimum)(pool, &pool[x->REDBLK_RIGHT]);
621 2456028 : }
622 :
623 : // else it is the lowest ancestor of x whose
624 : // left child is also an ancestor of x.
625 4923522 : for (;;) {
626 4923522 : if (x->REDBLK_PARENT == REDBLK_NIL)
627 14406 : return NULL;
628 4909116 : REDBLK_T * y = &pool[x->REDBLK_PARENT];
629 4909116 : if (x == &pool[y->REDBLK_LEFT])
630 2453088 : return y;
631 2456028 : x = y;
632 2456028 : }
633 2467494 : }
634 0 : REDBLK_T const * REDBLK_(successor_const)(REDBLK_T const * pool, REDBLK_T const * x) {
635 0 : #ifndef REDBLK_UNSAFE
636 0 : REDBLK_(validate_element_const)(pool, x);
637 0 : #endif
638 :
639 : // if the right subtree is not null,
640 : // the successor is the leftmost node in the
641 : // right subtree
642 0 : if (x->REDBLK_RIGHT != REDBLK_NIL) {
643 0 : return REDBLK_(minimum_const)(pool, &pool[x->REDBLK_RIGHT]);
644 0 : }
645 :
646 : // else it is the lowest ancestor of x whose
647 : // left child is also an ancestor of x.
648 0 : for (;;) {
649 0 : if (x->REDBLK_PARENT == REDBLK_NIL)
650 0 : return NULL;
651 0 : REDBLK_T const * y = &pool[x->REDBLK_PARENT];
652 0 : if (x == &pool[y->REDBLK_LEFT])
653 0 : return y;
654 0 : x = y;
655 0 : }
656 0 : }
657 :
658 : /*
659 : Return the previous node which is smaller than the given node.
660 : */
661 4083000 : REDBLK_T * REDBLK_(predecessor)(REDBLK_T * pool, REDBLK_T * x) {
662 4083000 : #ifndef REDBLK_UNSAFE
663 4083000 : REDBLK_(validate_element)(pool, x);
664 4083000 : #endif
665 :
666 : // if the left subtree is not null,
667 : // the predecessor is the rightmost node in the
668 : // left subtree
669 4083000 : if (x->REDBLK_LEFT != REDBLK_NIL) {
670 2038752 : return REDBLK_(maximum)(pool, &pool[x->REDBLK_LEFT]);
671 2038752 : }
672 :
673 : // else it is the lowest ancestor of x whose
674 : // right child is also an ancestor of x.
675 4083000 : for (;;) {
676 4083000 : if (x->REDBLK_PARENT == REDBLK_NIL)
677 3000 : return NULL;
678 4080000 : REDBLK_T * y = &pool[x->REDBLK_PARENT];
679 4080000 : if (x == &pool[y->REDBLK_RIGHT])
680 2041248 : return y;
681 2038752 : x = y;
682 2038752 : }
683 2044248 : }
684 0 : REDBLK_T const * REDBLK_(predecessor_const)(REDBLK_T const * pool, REDBLK_T const * x) {
685 0 : #ifndef REDBLK_UNSAFE
686 0 : REDBLK_(validate_element_const)(pool, x);
687 0 : #endif
688 :
689 : // if the left subtree is not null,
690 : // the predecessor is the rightmost node in the
691 : // left subtree
692 0 : if (x->REDBLK_LEFT != REDBLK_NIL) {
693 0 : return REDBLK_(maximum_const)(pool, &pool[x->REDBLK_LEFT]);
694 0 : }
695 :
696 : // else it is the lowest ancestor of x whose
697 : // right child is also an ancestor of x.
698 0 : for (;;) {
699 0 : if (x->REDBLK_PARENT == REDBLK_NIL)
700 0 : return NULL;
701 0 : REDBLK_T const * y = &pool[x->REDBLK_PARENT];
702 0 : if (x == &pool[y->REDBLK_RIGHT])
703 0 : return y;
704 0 : x = y;
705 0 : }
706 0 : }
707 :
708 : /*
709 : Perform a left rotation around a node
710 : */
711 98525614 : static void REDBLK_(rotateLeft)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
712 98525614 : REDBLK_T * y = &pool[x->REDBLK_RIGHT];
713 :
714 : /* establish x->REDBLK_RIGHT link */
715 98525614 : x->REDBLK_RIGHT = y->REDBLK_LEFT;
716 98525614 : if (y->REDBLK_LEFT != REDBLK_NIL)
717 24206583 : pool[y->REDBLK_LEFT].REDBLK_PARENT = (uint)(x - pool);
718 :
719 : /* establish y->REDBLK_PARENT link */
720 98525614 : if (y != &pool[REDBLK_NIL])
721 98525614 : y->REDBLK_PARENT = x->REDBLK_PARENT;
722 98525614 : if (x->REDBLK_PARENT) {
723 63707153 : REDBLK_T * p = &pool[x->REDBLK_PARENT];
724 63707153 : if (x == &pool[p->REDBLK_LEFT])
725 17121551 : p->REDBLK_LEFT = (uint)(y - pool);
726 46585602 : else
727 46585602 : p->REDBLK_RIGHT = (uint)(y - pool);
728 63707153 : } else {
729 34818461 : *root = y;
730 34818461 : }
731 :
732 : /* link x and y */
733 98525614 : y->REDBLK_LEFT = (uint)(x - pool);
734 98525614 : if (x != &pool[REDBLK_NIL])
735 98525614 : x->REDBLK_PARENT = (uint)(y - pool);
736 98525614 : }
737 :
738 : /*
739 : Perform a right rotation around a node
740 : */
741 34650991 : static void REDBLK_(rotateRight)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
742 34650991 : REDBLK_T * y = &pool[x->REDBLK_LEFT];
743 :
744 : /* establish x->REDBLK_LEFT link */
745 34650991 : x->REDBLK_LEFT = y->REDBLK_RIGHT;
746 34650991 : if (y->REDBLK_RIGHT != REDBLK_NIL)
747 5559102 : pool[y->REDBLK_RIGHT].REDBLK_PARENT = (uint)(x - pool);
748 :
749 : /* establish y->REDBLK_PARENT link */
750 34650991 : if (y != &pool[REDBLK_NIL])
751 34650991 : y->REDBLK_PARENT = x->REDBLK_PARENT;
752 34650991 : if (x->REDBLK_PARENT) {
753 24524145 : REDBLK_T * p = &pool[x->REDBLK_PARENT];
754 24524145 : if (x == &pool[p->REDBLK_RIGHT])
755 16415256 : p->REDBLK_RIGHT = (uint)(y - pool);
756 8108889 : else
757 8108889 : p->REDBLK_LEFT = (uint)(y - pool);
758 24524145 : } else {
759 10126846 : *root = y;
760 10126846 : }
761 :
762 : /* link x and y */
763 34650991 : y->REDBLK_RIGHT = (uint)(x - pool);
764 34650991 : if (x != &pool[REDBLK_NIL])
765 34650991 : x->REDBLK_PARENT = (uint)(y - pool);
766 34650991 : }
767 :
768 : /*
769 : Restore tree invariants after an insert.
770 : */
771 222666621 : static void REDBLK_(insertFixup)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
772 : /* check Red-Black properties */
773 222666621 : REDBLK_T * p;
774 397828726 : while (x != *root && (p = &pool[x->REDBLK_PARENT])->REDBLK_COLOR == REDBLK_RED) {
775 : /* we have a violation */
776 175162105 : REDBLK_T * gp = &pool[p->REDBLK_PARENT];
777 175162105 : if (x->REDBLK_PARENT == gp->REDBLK_LEFT) {
778 33146926 : REDBLK_T * y = &pool[gp->REDBLK_RIGHT];
779 33146926 : if (y->REDBLK_COLOR == REDBLK_RED) {
780 :
781 : /* uncle is REDBLK_RED */
782 16394737 : p->REDBLK_COLOR = REDBLK_BLACK;
783 16394737 : y->REDBLK_COLOR = REDBLK_BLACK;
784 16394737 : gp->REDBLK_COLOR = REDBLK_RED;
785 16394737 : x = gp;
786 16752189 : } else {
787 :
788 : /* uncle is REDBLK_BLACK */
789 16752189 : if (x == &pool[p->REDBLK_RIGHT]) {
790 : /* make x a left child */
791 8372916 : x = p;
792 8372916 : REDBLK_(rotateLeft)(pool, root, x);
793 8372916 : p = &pool[x->REDBLK_PARENT];
794 8372916 : gp = &pool[p->REDBLK_PARENT];
795 8372916 : }
796 :
797 : /* recolor and rotate */
798 16752189 : p->REDBLK_COLOR = REDBLK_BLACK;
799 16752189 : gp->REDBLK_COLOR = REDBLK_RED;
800 16752189 : REDBLK_(rotateRight)(pool, root, gp);
801 16752189 : }
802 :
803 142015179 : } else {
804 : /* mirror image of above code */
805 142015179 : REDBLK_T * y = &pool[gp->REDBLK_LEFT];
806 142015179 : if (y->REDBLK_COLOR == REDBLK_RED) {
807 :
808 : /* uncle is REDBLK_RED */
809 70826944 : p->REDBLK_COLOR = REDBLK_BLACK;
810 70826944 : y->REDBLK_COLOR = REDBLK_BLACK;
811 70826944 : gp->REDBLK_COLOR = REDBLK_RED;
812 70826944 : x = gp;
813 71188235 : } else {
814 :
815 : /* uncle is REDBLK_BLACK */
816 71188235 : if (x == &pool[p->REDBLK_LEFT]) {
817 8372425 : x = p;
818 8372425 : REDBLK_(rotateRight)(pool, root, x);
819 8372425 : p = &pool[x->REDBLK_PARENT];
820 8372425 : gp = &pool[p->REDBLK_PARENT];
821 8372425 : }
822 71188235 : p->REDBLK_COLOR = REDBLK_BLACK;
823 71188235 : gp->REDBLK_COLOR = REDBLK_RED;
824 71188235 : REDBLK_(rotateLeft)(pool, root, gp);
825 71188235 : }
826 142015179 : }
827 175162105 : }
828 :
829 222666621 : (*root)->REDBLK_COLOR = REDBLK_BLACK;
830 222666621 : }
831 :
832 : /*
833 : Insert a node into a tree. Typically, the node must be allocated
834 : from a pool first.
835 : */
836 222666621 : REDBLK_T * REDBLK_(insert)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
837 222666621 : #ifndef REDBLK_UNSAFE
838 222666621 : REDBLK_(validate_element)(pool, *root);
839 222666621 : REDBLK_(validate_element)(pool, x);
840 222666621 : #endif
841 :
842 222666621 : REDBLK_T * current;
843 222666621 : REDBLK_T * parent;
844 :
845 : /* find where node belongs */
846 222666621 : current = *root;
847 222666621 : if (current == NULL)
848 21787347 : current = &pool[REDBLK_NIL];
849 222666621 : parent = &pool[REDBLK_NIL];
850 804570948 : while (current != &pool[REDBLK_NIL]) {
851 581904327 : long c = REDBLK_(compare)(x, current);
852 581904327 : parent = current;
853 581904327 : current = (c < 0 ? &pool[current->REDBLK_LEFT] : &pool[current->REDBLK_RIGHT]);
854 581904327 : }
855 :
856 : /* setup new node */
857 222666621 : x->REDBLK_PARENT = (uint)(parent - pool);
858 222666621 : x->REDBLK_LEFT = REDBLK_NIL;
859 222666621 : x->REDBLK_RIGHT = REDBLK_NIL;
860 222666621 : x->REDBLK_COLOR = REDBLK_RED;
861 :
862 : /* insert node in tree */
863 222666621 : if (parent != &pool[REDBLK_NIL]) {
864 200879274 : long c = REDBLK_(compare)(x, parent);
865 200879274 : if (c < 0)
866 51445879 : parent->REDBLK_LEFT = (uint)(x - pool);
867 149433395 : else
868 149433395 : parent->REDBLK_RIGHT = (uint)(x - pool);
869 200879274 : } else {
870 21787347 : *root = x;
871 21787347 : }
872 :
873 222666621 : REDBLK_(insertFixup)(pool, root, x);
874 222666621 : return x;
875 222666621 : }
876 :
877 : /*
878 : Restore tree invariants after a delete
879 : */
880 92124722 : static void REDBLK_(deleteFixup)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
881 166922293 : while (x != *root && x->REDBLK_COLOR == REDBLK_BLACK) {
882 74797571 : REDBLK_T * p = &pool[x->REDBLK_PARENT];
883 74797571 : if (x == &pool[p->REDBLK_LEFT]) {
884 37308679 : REDBLK_T * w = &pool[p->REDBLK_RIGHT];
885 37308679 : if (w->REDBLK_COLOR == REDBLK_RED) {
886 4179980 : w->REDBLK_COLOR = REDBLK_BLACK;
887 4179980 : p->REDBLK_COLOR = REDBLK_RED;
888 4179980 : REDBLK_(rotateLeft)(pool, root, p);
889 4179980 : p = &pool[x->REDBLK_PARENT];
890 4179980 : w = &pool[p->REDBLK_RIGHT];
891 4179980 : }
892 37308679 : if (pool[w->REDBLK_LEFT].REDBLK_COLOR == REDBLK_BLACK &&
893 37308679 : pool[w->REDBLK_RIGHT].REDBLK_COLOR == REDBLK_BLACK) {
894 25543674 : w->REDBLK_COLOR = REDBLK_RED;
895 25543674 : x = p;
896 25543674 : } else {
897 11765005 : if (pool[w->REDBLK_RIGHT].REDBLK_COLOR == REDBLK_BLACK) {
898 1505673 : pool[w->REDBLK_LEFT].REDBLK_COLOR = REDBLK_BLACK;
899 1505673 : w->REDBLK_COLOR = REDBLK_RED;
900 1505673 : REDBLK_(rotateRight)(pool, root, w);
901 1505673 : p = &pool[x->REDBLK_PARENT];
902 1505673 : w = &pool[p->REDBLK_RIGHT];
903 1505673 : }
904 11765005 : w->REDBLK_COLOR = p->REDBLK_COLOR;
905 11765005 : p->REDBLK_COLOR = REDBLK_BLACK;
906 11765005 : pool[w->REDBLK_RIGHT].REDBLK_COLOR = REDBLK_BLACK;
907 11765005 : REDBLK_(rotateLeft)(pool, root, p);
908 11765005 : x = *root;
909 11765005 : }
910 :
911 37488892 : } else {
912 37488892 : REDBLK_T * w = &pool[p->REDBLK_LEFT];
913 37488892 : if (w->REDBLK_COLOR == REDBLK_RED) {
914 1499665 : w->REDBLK_COLOR = REDBLK_BLACK;
915 1499665 : p->REDBLK_COLOR = REDBLK_RED;
916 1499665 : REDBLK_(rotateRight)(pool, root, p);
917 1499665 : p = &pool[x->REDBLK_PARENT];
918 1499665 : w = &pool[p->REDBLK_LEFT];
919 1499665 : }
920 37488892 : if (pool[w->REDBLK_RIGHT].REDBLK_COLOR == REDBLK_BLACK &&
921 37488892 : pool[w->REDBLK_LEFT].REDBLK_COLOR == REDBLK_BLACK) {
922 30967853 : w->REDBLK_COLOR = REDBLK_RED;
923 30967853 : x = p;
924 30967853 : } else {
925 6521039 : if (pool[w->REDBLK_LEFT].REDBLK_COLOR == REDBLK_BLACK) {
926 3019478 : pool[w->REDBLK_RIGHT].REDBLK_COLOR = REDBLK_BLACK;
927 3019478 : w->REDBLK_COLOR = REDBLK_RED;
928 3019478 : REDBLK_(rotateLeft)(pool, root, w);
929 3019478 : p = &pool[x->REDBLK_PARENT];
930 3019478 : w = &pool[p->REDBLK_LEFT];
931 3019478 : }
932 6521039 : w->REDBLK_COLOR = p->REDBLK_COLOR;
933 6521039 : p->REDBLK_COLOR = REDBLK_BLACK;
934 6521039 : pool[w->REDBLK_LEFT].REDBLK_COLOR = REDBLK_BLACK;
935 6521039 : REDBLK_(rotateRight)(pool, root, p);
936 6521039 : x = *root;
937 6521039 : }
938 37488892 : }
939 74797571 : }
940 :
941 92124722 : x->REDBLK_COLOR = REDBLK_BLACK;
942 92124722 : }
943 :
944 : /*
945 : Remove a node from a tree. The node must be a member of the tree,
946 : usually the result of a find operation. The node is typically
947 : released to the pool afterwards.
948 : */
949 112950657 : REDBLK_T * REDBLK_(remove)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * z) {
950 112950657 : #ifndef REDBLK_UNSAFE
951 112950657 : REDBLK_(validate_element)(pool, *root);
952 112950657 : REDBLK_(validate_element)(pool, z);
953 112950657 : #endif
954 :
955 112950657 : REDBLK_T * x;
956 112950657 : REDBLK_T * y;
957 :
958 112950657 : if (!z || z == &pool[REDBLK_NIL])
959 0 : return NULL;
960 :
961 112950657 : if (z->REDBLK_LEFT == REDBLK_NIL || z->REDBLK_RIGHT == REDBLK_NIL) {
962 : /* y has a REDBLK_NIL node as a child */
963 81489256 : y = z;
964 81489256 : } else {
965 : /* find tree successor with a REDBLK_NIL node as a child */
966 31461401 : y = &pool[z->REDBLK_RIGHT];
967 43608893 : while (y->REDBLK_LEFT != REDBLK_NIL)
968 12147492 : y = &pool[y->REDBLK_LEFT];
969 31461401 : }
970 :
971 : /* x is y's only child */
972 112950657 : if (y->REDBLK_LEFT != REDBLK_NIL)
973 9310934 : x = &pool[y->REDBLK_LEFT];
974 103639723 : else
975 103639723 : x = &pool[y->REDBLK_RIGHT];
976 :
977 : /* remove y from the parent chain */
978 112950657 : x->REDBLK_PARENT = y->REDBLK_PARENT;
979 112950657 : if (y->REDBLK_PARENT)
980 96616497 : if (y == &pool[pool[y->REDBLK_PARENT].REDBLK_LEFT])
981 45041436 : pool[y->REDBLK_PARENT].REDBLK_LEFT = (uint)(x - pool);
982 51575061 : else
983 51575061 : pool[y->REDBLK_PARENT].REDBLK_RIGHT = (uint)(x - pool);
984 16334160 : else
985 16334160 : *root = x;
986 :
987 112950657 : if (y->REDBLK_COLOR == REDBLK_BLACK)
988 92124722 : REDBLK_(deleteFixup)(pool, root, x);
989 :
990 112950657 : if (y != z) {
991 : /* we got rid of y instead of z. Oops! Replace z with y in the
992 : * tree so we don't lose y's key/value. */
993 31461401 : y->REDBLK_PARENT = z->REDBLK_PARENT;
994 31461401 : y->REDBLK_LEFT = z->REDBLK_LEFT;
995 31461401 : y->REDBLK_RIGHT = z->REDBLK_RIGHT;
996 31461401 : y->REDBLK_COLOR = z->REDBLK_COLOR;
997 31461401 : if (z == *root)
998 13492888 : *root = y;
999 17968513 : else if (&pool[pool[y->REDBLK_PARENT].REDBLK_LEFT] == z)
1000 5629829 : pool[y->REDBLK_PARENT].REDBLK_LEFT = (uint)(y - pool);
1001 12338684 : else
1002 12338684 : pool[y->REDBLK_PARENT].REDBLK_RIGHT = (uint)(y - pool);
1003 31461401 : pool[y->REDBLK_LEFT].REDBLK_PARENT = (uint)(y - pool);
1004 31461401 : pool[y->REDBLK_RIGHT].REDBLK_PARENT = (uint)(y - pool);
1005 31461401 : }
1006 :
1007 112950657 : if (*root == &pool[REDBLK_NIL])
1008 10889451 : *root = NULL;
1009 112950657 : z->REDBLK_COLOR = REDBLK_NEW;
1010 112950657 : return z;
1011 112950657 : }
1012 :
1013 : /*
1014 : Search for a key in the tree. In this special case, the key can be a
1015 : temporary instance of the node type rather than a properly
1016 : allocated node.
1017 : */
1018 447792420 : REDBLK_T * REDBLK_(find)(REDBLK_T * pool, REDBLK_T * root, REDBLK_T * key) {
1019 447792420 : #ifndef REDBLK_UNSAFE
1020 447792420 : REDBLK_(validate_element)(pool, root);
1021 447792420 : #endif
1022 :
1023 447792420 : REDBLK_T * current = root;
1024 447792420 : if (current == NULL || current == &pool[REDBLK_NIL])
1025 10886454 : return NULL;
1026 1330291451 : while (current != &pool[REDBLK_NIL]) {
1027 1232269742 : long c = REDBLK_(compare)(key, current);
1028 1232269742 : if (c == 0)
1029 338884257 : return current;
1030 893385485 : current = (c < 0 ? &pool[current->REDBLK_LEFT] : &pool[current->REDBLK_RIGHT]);
1031 893385485 : }
1032 98021709 : return NULL;
1033 436905966 : }
1034 :
1035 : /*
1036 : Search for a key in the tree. If the key can't be found, a nearby
1037 : approximation is returned instead. This is either the greatest node
1038 : less than the key, or the least node greater than the key. In this
1039 : special case, the key can be a temporary instance of the node type
1040 : rather than a properly allocated node.
1041 : */
1042 0 : REDBLK_T * REDBLK_(nearby)(REDBLK_T * pool, REDBLK_T * root, REDBLK_T * key) {
1043 0 : #ifndef REDBLK_UNSAFE
1044 0 : REDBLK_(validate_element)(pool, root);
1045 0 : #endif
1046 :
1047 0 : REDBLK_T * current = root;
1048 0 : if (current == NULL || current == &pool[REDBLK_NIL])
1049 0 : return NULL;
1050 0 : REDBLK_T * result = current;
1051 0 : while (current != &pool[REDBLK_NIL]) {
1052 0 : result = current; /* Return the last non-NIL node that was touched */
1053 0 : long c = REDBLK_(compare)(key, current);
1054 0 : if (c == 0)
1055 0 : return current;
1056 0 : current = (c < 0 ? &pool[current->REDBLK_LEFT] : &pool[current->REDBLK_RIGHT]);
1057 0 : }
1058 0 : return result;
1059 0 : }
1060 :
1061 : /*
1062 : Count the number of nodes in a tree.
1063 : */
1064 3879465943 : ulong REDBLK_(size)(REDBLK_T * pool, REDBLK_T * root) {
1065 3879465943 : #ifndef REDBLK_UNSAFE
1066 3879465943 : REDBLK_(validate_element)(pool, root);
1067 3879465943 : #endif
1068 3879465943 : if (!root || root == &pool[REDBLK_NIL])
1069 2098007678 : return 0;
1070 1781458265 : return 1 +
1071 1781458265 : REDBLK_(size)(pool, &pool[root->REDBLK_LEFT]) +
1072 1781458265 : REDBLK_(size)(pool, &pool[root->REDBLK_RIGHT]);
1073 3879465943 : }
1074 :
1075 : /*
1076 : Recursive implementation of the verify function
1077 : */
1078 3717056266 : int REDBLK_(verify_private)(REDBLK_T * pool, REDBLK_T * node, REDBLK_T * parent, ulong curblkcnt, ulong correctblkcnt) {
1079 7272683272 : # define REDBLK_TEST(c) do { \
1080 7272683272 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
1081 7272683272 : } while(0)
1082 :
1083 3717056266 : if (!node || node == &pool[REDBLK_NIL]) {
1084 2016387542 : REDBLK_TEST(curblkcnt == correctblkcnt);
1085 2016387542 : return 0;
1086 2016387542 : }
1087 :
1088 1700668724 : #ifndef REDBLK_UNSAFE
1089 1700668724 : REDBLK_(validate_element)(pool, node);
1090 1700668724 : #endif
1091 :
1092 1700668724 : REDBLK_TEST(&pool[node->REDBLK_PARENT] == parent);
1093 :
1094 1700668724 : if (node->REDBLK_COLOR == REDBLK_BLACK)
1095 1094353125 : ++curblkcnt;
1096 606315599 : else {
1097 606315599 : REDBLK_TEST(node->REDBLK_COLOR == REDBLK_RED);
1098 606315599 : REDBLK_TEST(parent->REDBLK_COLOR == REDBLK_BLACK);
1099 606315599 : }
1100 :
1101 1700668724 : if (node->REDBLK_LEFT != REDBLK_NIL)
1102 663986375 : REDBLK_TEST(REDBLK_(compare)(&pool[node->REDBLK_LEFT], node) <= 0);
1103 1700668724 : if (node->REDBLK_RIGHT != REDBLK_NIL)
1104 720963531 : REDBLK_TEST(REDBLK_(compare)(node, &pool[node->REDBLK_RIGHT]) <= 0);
1105 :
1106 1700668724 : int err = REDBLK_(verify_private)(pool, &pool[node->REDBLK_LEFT], node, curblkcnt, correctblkcnt);
1107 1700668724 : if (err) return err;
1108 1700668724 : return REDBLK_(verify_private)(pool, &pool[node->REDBLK_RIGHT], node, curblkcnt, correctblkcnt);
1109 1700668724 : }
1110 :
1111 : /*
1112 : Verify the integrity of the tree data structure. Useful for
1113 : debugging memory corruption. A non-zero result is returned if an error
1114 : is detected.
1115 : */
1116 326608266 : int REDBLK_(verify)(REDBLK_T * pool, REDBLK_T * root) {
1117 326608266 : REDBLK_TEST(pool[REDBLK_NIL].REDBLK_LEFT == REDBLK_NIL &&
1118 326608266 : pool[REDBLK_NIL].REDBLK_RIGHT == REDBLK_NIL &&
1119 326608266 : pool[REDBLK_NIL].REDBLK_COLOR == REDBLK_BLACK);
1120 :
1121 326608266 : if (!root || root == &pool[REDBLK_NIL])
1122 10889448 : return 0; // Trivially correct
1123 315718818 : REDBLK_TEST(root->REDBLK_COLOR == REDBLK_BLACK);
1124 :
1125 315718818 : ulong sz = REDBLK_(size)(pool, root);
1126 315718818 : REDBLK_TEST(sz + 1 == REDBLK_POOL_(used)(pool));
1127 :
1128 : // Compute the correct number of black nodes on a path
1129 315718818 : ulong blkcnt = 0;
1130 315718818 : REDBLK_T * node = root;
1131 1047925099 : while (node != &pool[REDBLK_NIL]) {
1132 732206281 : if (node->REDBLK_COLOR == REDBLK_BLACK)
1133 582355329 : ++blkcnt;
1134 732206281 : node = &pool[node->REDBLK_LEFT];
1135 732206281 : }
1136 : // Recursive check
1137 315718818 : return REDBLK_(verify_private)(pool, root, &pool[REDBLK_NIL], 0, blkcnt);
1138 :
1139 315718818 : #undef REDBLK_TEST
1140 315718818 : }
1141 :
1142 : #undef REDBLK_FREE
1143 : #undef REDBLK_NEW
1144 : #undef REDBLK_BLACK
1145 : #undef REDBLK_RED
1146 : #undef REDBLK_POOL_
1147 : #undef REDBLK_PARENT
1148 : #undef REDBLK_LEFT
1149 : #undef REDBLK_RIGHT
1150 : #undef REDBLK_COLOR
1151 :
1152 : #endif /* REDBLK_IMPL_STYLE==0 || REDBLK_IMPL_STYLE==2 */
1153 :
1154 : #undef REDBLK_
1155 : #undef REDBLK_T
1156 : #undef REDBLK_IMPL_STYLE
|
