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 17193995430 : #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_insert_or_replace(my_node_t * pool, my_node_t ** root, my_node_t * x, my_node_t ** out);
322 :
323 : This function inserts a node into the red-black tree. If a matching node with the same key already exists,
324 : it is replaced, and the replaced node is returned via the `out` pointer. The caller is responsible
325 : for freeing the replaced node (if applicable). The inserted node is always returned.
326 :
327 : Before calling this function, the new node should be allocated (typically from a pool) and
328 : initialized with the required values (e.g., key and value).
329 :
330 : For example:
331 : my_node_t * n = my_rb_acquire(pool); // Acquire from the pool
332 : n->key = 123; // Initialize key
333 : n->value = 456; // Initialize value
334 : my_node_t * out = NULL; // Prepare to store replaced node
335 :
336 : n = my_rb_insert_or_replace(pool, &root, n, &out); // Insert or replace into the tree
337 :
338 : if (out != NULL)
339 : my_rb_release(pool, out); // Release replaced node (if any)
340 :
341 : The `insert_or_replace` function returns the new node after insertion.
342 : */
343 : REDBLK_T * REDBLK_(insert_or_replace)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x, REDBLK_T ** out);
344 : /*
345 : E.g. my_node_t * my_rb_remove(my_node_t * pool, my_node_t ** root, my_node_t * z);
346 :
347 : Remove a node from a tree. The node must be a member of the tree,
348 : usually the result of a find operation. The node is typically
349 : released to the pool afterwards. For example:
350 :
351 : my_node_t * n = my_rb_find( pool, root, &k );
352 : n = my_rb_remove( pool, &root, n );
353 : my_rb_pool_release( pool, n );
354 :
355 : Remove and release are separate steps to allow an application to
356 : perform final cleanup on the node in between. You can insert a node
357 : into a different tree after deletion if both trees share a pool. For
358 : example:
359 :
360 : n = my_rb_remove( pool, &root, n );
361 : my_rb_insert( pool, &root2, n );
362 : */
363 : REDBLK_T * REDBLK_(remove)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * z);
364 : /*
365 : E.g. my_node_t * my_rb_find(my_node_t * pool, my_node_t * root, my_node_t * key);
366 :
367 : Search for a key in the tree. In this special case, the key can be a
368 : temporary instance of the node type rather than a properly
369 : allocated node. For example:
370 :
371 : my_node_t k;
372 : k.key = 123 + i;
373 : my_node_t * n = my_rb_find( pool, root, &k );
374 : printf("key=%lu value=%lu\n", n->key, n->value);
375 :
376 : A NULL is returned if the find fails.
377 : */
378 : REDBLK_T * REDBLK_(find)(REDBLK_T * pool, REDBLK_T * root, REDBLK_T * key);
379 : /*
380 : E.g. my_node_t * my_rb_nearby(my_node_t * pool, my_node_t * root, my_node_t * key);
381 :
382 : Search for a key in the tree. If the key can't be found, a nearby
383 : approximation is returned instead. This is either the greatest node
384 : less than the key, or the least node greater than the key. In this
385 : special case, the key can be a temporary instance of the node type
386 : rather than a properly allocated node. For example:
387 :
388 : my_node_t k;
389 : k.key = 123 + i;
390 : my_node_t * n = my_rb_nearby( pool, root, &k );
391 : printf("key=%lu value=%lu\n", n->key, n->value);
392 :
393 : A NULL is returned if the search fails.
394 : */
395 : REDBLK_T * REDBLK_(nearby)(REDBLK_T * pool, REDBLK_T * root, REDBLK_T * key);
396 : /*
397 : E.g. ulong my_rb_size(my_node_t * pool, my_node_t * root);
398 :
399 : Count the number of nodes in a tree.
400 : */
401 : ulong REDBLK_(size)(REDBLK_T * pool, REDBLK_T * root);
402 :
403 : /*
404 : E.g. int my_rb_verify(my_node_t * pool, my_node_t * root);
405 :
406 : Verify the integrity of the tree data structure. Useful for
407 : debugging memory corruption. A non-zero result is returned if an error
408 : is detected.
409 : */
410 : int REDBLK_(verify)(REDBLK_T * pool, REDBLK_T * root);
411 :
412 : /*
413 : E.g. long my_rb_compare(my_node_t * left, my_node_t * right);
414 :
415 : Defined by application to implement key comparison. Returns a
416 : negative number, zero, or positive depending on whether the left is
417 : less than, equal to, or greater than right. For example:
418 :
419 : long my_rb_compare(my_node_t* left, my_node_t* right) {
420 : return (long)(left->key - right->key);
421 : }
422 :
423 : Should be a pure function. (FIXME: SHOULD TAKE CONST POINTERS?)
424 : */
425 : FD_FN_PURE long REDBLK_(compare)(REDBLK_T * left, REDBLK_T * right);
426 :
427 : FD_PROTOTYPES_END
428 :
429 : #endif /* REDBLK_IMPL_STYLE==0 || REDBLK_IMPL_STYLE==1 */
430 :
431 : #if REDBLK_IMPL_STYLE==0 /* local only */
432 : #define REDBLK_IMPL_STATIC FD_FN_UNUSED static
433 : #else
434 : #define REDBLK_IMPL_STATIC
435 : #endif
436 :
437 : #if REDBLK_IMPL_STYLE==0 || REDBLK_IMPL_STYLE==2 /* need implementations */
438 :
439 : /* Tree node colors */
440 7087573186 : #define REDBLK_FREE -1
441 338866615 : #define REDBLK_NEW 0
442 3516403739 : #define REDBLK_BLACK 1
443 1053969688 : #define REDBLK_RED 2
444 :
445 : #ifndef REDBLK_PARENT
446 118030317 : #define REDBLK_PARENT redblack_parent
447 : #endif
448 : #ifndef REDBLK_LEFT
449 214513479 : #define REDBLK_LEFT redblack_left
450 : #endif
451 : #ifndef REDBLK_RIGHT
452 227064663 : #define REDBLK_RIGHT redblack_right
453 : #endif
454 : #ifndef REDBLK_COLOR
455 167059341 : #define REDBLK_COLOR redblack_color
456 : #endif
457 :
458 : #define POOL_NAME FD_EXPAND_THEN_CONCAT2(REDBLK_NAME,_pool)
459 69 : #define POOL_T REDBLK_T
460 : #define POOL_SENTINEL 1
461 : #ifdef REDBLK_NEXTFREE
462 435485703 : #define POOL_NEXT REDBLK_NEXTFREE
463 : #else
464 28672971 : #define POOL_NEXT REDBLK_RIGHT
465 : #endif
466 : #include "fd_pool.c"
467 : #undef MAP_POOL_NAME
468 : #undef MAP_POOL_T
469 :
470 7572073984 : #define REDBLK_POOL_(n) FD_EXPAND_THEN_CONCAT3(REDBLK_NAME,_pool_,n)
471 :
472 17393645753 : #define REDBLK_NIL 0UL /* Must be same as pool sentinel */
473 :
474 6 : REDBLK_IMPL_STATIC ulong REDBLK_(max_for_footprint)( ulong footprint ) {
475 6 : return REDBLK_POOL_(max_for_footprint)(footprint) - 1; /* Allow for sentinel */
476 6 : }
477 :
478 36 : REDBLK_IMPL_STATIC ulong REDBLK_(align)( void ) {
479 36 : return REDBLK_POOL_(align)();
480 36 : }
481 :
482 30 : REDBLK_IMPL_STATIC ulong REDBLK_(footprint)( ulong max ) {
483 30 : return REDBLK_POOL_(footprint)(max + 1); /* Allow for sentinel */
484 30 : }
485 :
486 18 : REDBLK_IMPL_STATIC void * REDBLK_(new)( void * shmem, ulong max ) {
487 18 : void * shmem2 = REDBLK_POOL_(new)(shmem, max + 1); /* Allow for sentinel */
488 18 : if ( FD_UNLIKELY( shmem2 == NULL ) )
489 0 : return NULL;
490 : /* Initialize sentinel */
491 18 : REDBLK_T * pool = REDBLK_POOL_(join)(shmem2);
492 18 : if ( FD_UNLIKELY( pool == NULL ) )
493 0 : return NULL;
494 18 : REDBLK_T * node = REDBLK_POOL_(ele_sentinel)(pool);
495 18 : node->REDBLK_LEFT = REDBLK_NIL;
496 18 : node->REDBLK_RIGHT = REDBLK_NIL;
497 18 : node->REDBLK_PARENT = REDBLK_NIL;
498 18 : node->REDBLK_COLOR = REDBLK_BLACK;
499 18 : return shmem2;
500 18 : }
501 :
502 27 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(join)( void * shpool ) {
503 27 : FD_COMPILER_MFENCE();
504 27 : return REDBLK_POOL_(join)(shpool);
505 27 : }
506 :
507 27 : REDBLK_IMPL_STATIC void * REDBLK_(leave)( REDBLK_T * pool ) {
508 27 : FD_COMPILER_MFENCE();
509 27 : return REDBLK_POOL_(leave)(pool);
510 27 : }
511 :
512 6 : REDBLK_IMPL_STATIC void * REDBLK_(delete)( void * shpool ) {
513 6 : FD_COMPILER_MFENCE();
514 6 : return REDBLK_POOL_(delete)(shpool);
515 6 : }
516 :
517 15 : REDBLK_IMPL_STATIC ulong REDBLK_(max)( REDBLK_T const * pool ) {
518 15 : return REDBLK_POOL_(max)(pool) - 1; /* Allow for sentinel */
519 15 : }
520 :
521 69 : REDBLK_IMPL_STATIC ulong REDBLK_(free)( REDBLK_T const * pool ) {
522 69 : return REDBLK_POOL_(free)(pool);
523 69 : }
524 :
525 9 : REDBLK_IMPL_STATIC ulong REDBLK_(idx)( REDBLK_T const * pool, REDBLK_T const * node ) {
526 9 : return REDBLK_POOL_(idx)(pool, node);
527 9 : }
528 :
529 9 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(node)( REDBLK_T * pool, ulong idx ) {
530 9 : return REDBLK_POOL_(ele)(pool, idx);
531 9 : }
532 :
533 225922044 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(acquire)( REDBLK_T * pool ) {
534 225922044 : if ( REDBLK_POOL_(free)( pool ) == 0 )
535 6009 : return NULL;
536 225916035 : REDBLK_T * node = REDBLK_POOL_(ele_acquire)(pool);
537 225916035 : node->REDBLK_COLOR = REDBLK_NEW;
538 225916035 : return node;
539 225922044 : }
540 :
541 : #ifndef REDBLK_UNSAFE
542 6894313462 : REDBLK_IMPL_STATIC void REDBLK_(validate_element)( REDBLK_T * pool, REDBLK_T * node ) {
543 6894313462 : if ( !REDBLK_POOL_(ele_test)( pool, node ) )
544 0 : FD_LOG_CRIT(( "invalid redblack node" ));
545 6894313462 : if ( node && node->REDBLK_COLOR == REDBLK_FREE )
546 0 : FD_LOG_CRIT(( "invalid redblack node" ));
547 6894313462 : }
548 0 : REDBLK_IMPL_STATIC void REDBLK_(validate_element_const)( REDBLK_T const * pool, REDBLK_T const * node ) {
549 0 : if ( !REDBLK_POOL_(ele_test)( pool, node ) )
550 0 : FD_LOG_CRIT(( "invalid redblack node" ));
551 0 : if ( node && node->REDBLK_COLOR == REDBLK_FREE )
552 0 : FD_LOG_CRIT(( "invalid redblack node" ));
553 0 : }
554 : #endif
555 :
556 225922155 : REDBLK_IMPL_STATIC void REDBLK_(release)( REDBLK_T * pool, REDBLK_T * node ) {
557 225922155 : #ifndef REDBLK_UNSAFE
558 225922155 : REDBLK_(validate_element)(pool, node);
559 225922155 : #endif
560 :
561 225922155 : node->REDBLK_COLOR = REDBLK_FREE;
562 225922155 : REDBLK_POOL_(ele_release)(pool, node);
563 225922155 : }
564 :
565 : /*
566 : Recursively release all nodes in a tree to a pool. The root argument
567 : is invalid after this method is called.
568 : */
569 239556139 : REDBLK_IMPL_STATIC void REDBLK_(release_tree)( REDBLK_T * pool, REDBLK_T * node ) {
570 239556139 : if (!node || node == &pool[REDBLK_NIL])
571 130664564 : return;
572 :
573 108891575 : #ifndef REDBLK_UNSAFE
574 108891575 : REDBLK_(validate_element)(pool, node);
575 108891575 : #endif
576 :
577 108891575 : REDBLK_T * left = &pool[node->REDBLK_LEFT];
578 108891575 : REDBLK_T * right = &pool[node->REDBLK_RIGHT];
579 :
580 108891575 : REDBLK_(release)(pool, node);
581 :
582 108891575 : REDBLK_(release_tree)(pool, left);
583 108891575 : REDBLK_(release_tree)(pool, right);
584 108891575 : }
585 :
586 : /*
587 : Return the node in a tree that has the smallest key (leftmost).
588 : */
589 2044281 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(minimum)(REDBLK_T * pool, REDBLK_T * node) {
590 2044281 : if (!node || node == &pool[REDBLK_NIL])
591 6 : return NULL;
592 2044275 : #ifndef REDBLK_UNSAFE
593 2044275 : REDBLK_(validate_element)(pool, node);
594 2044275 : #endif
595 4083042 : while (node->REDBLK_LEFT != REDBLK_NIL) {
596 2038767 : node = &pool[node->REDBLK_LEFT];
597 2038767 : }
598 2044275 : return node;
599 2044281 : }
600 0 : REDBLK_IMPL_STATIC REDBLK_T const * REDBLK_(minimum_const)(REDBLK_T const * pool, REDBLK_T const * node) {
601 0 : if (!node || node == &pool[REDBLK_NIL])
602 0 : return NULL;
603 0 : #ifndef REDBLK_UNSAFE
604 0 : REDBLK_(validate_element_const)(pool, node);
605 0 : #endif
606 0 : while (node->REDBLK_LEFT != REDBLK_NIL) {
607 0 : node = &pool[node->REDBLK_LEFT];
608 0 : }
609 0 : return node;
610 0 : }
611 :
612 : /*
613 : Return the node in a tree that has the largest key (rightmost).
614 : */
615 2041752 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(maximum)(REDBLK_T * pool, REDBLK_T * node) {
616 2041752 : if (!node || node == &pool[REDBLK_NIL])
617 0 : return NULL;
618 2041752 : #ifndef REDBLK_UNSAFE
619 2041752 : REDBLK_(validate_element)(pool, node);
620 2041752 : #endif
621 4083000 : while (node->REDBLK_RIGHT != REDBLK_NIL) {
622 2041248 : node = &pool[node->REDBLK_RIGHT];
623 2041248 : }
624 2041752 : return node;
625 2041752 : }
626 0 : REDBLK_IMPL_STATIC REDBLK_T const * REDBLK_(maximum_const)(REDBLK_T const * pool, REDBLK_T const * node) {
627 0 : if (!node || node == &pool[REDBLK_NIL])
628 0 : return NULL;
629 0 : #ifndef REDBLK_UNSAFE
630 0 : REDBLK_(validate_element_const)(pool, node);
631 0 : #endif
632 0 : while (node->REDBLK_RIGHT != REDBLK_NIL) {
633 0 : node = &pool[node->REDBLK_RIGHT];
634 0 : }
635 0 : return node;
636 0 : }
637 :
638 : /*
639 : Return the next node which is larger than the given node.
640 : */
641 4083027 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(successor)(REDBLK_T * pool, REDBLK_T * x) {
642 4083027 : #ifndef REDBLK_UNSAFE
643 4083027 : REDBLK_(validate_element)(pool, x);
644 4083027 : #endif
645 :
646 : // if the right subtree is not null,
647 : // the successor is the leftmost node in the
648 : // right subtree
649 4083027 : if (x->REDBLK_RIGHT != REDBLK_NIL) {
650 2041260 : return REDBLK_(minimum)(pool, &pool[x->REDBLK_RIGHT]);
651 2041260 : }
652 :
653 : // else it is the lowest ancestor of x whose
654 : // left child is also an ancestor of x.
655 4083027 : for (;;) {
656 4083027 : if (x->REDBLK_PARENT == REDBLK_NIL)
657 3003 : return NULL;
658 4080024 : REDBLK_T * y = &pool[x->REDBLK_PARENT];
659 4080024 : if (x == &pool[y->REDBLK_LEFT])
660 2038764 : return y;
661 2041260 : x = y;
662 2041260 : }
663 2041767 : }
664 0 : REDBLK_IMPL_STATIC REDBLK_T const * REDBLK_(successor_const)(REDBLK_T const * pool, REDBLK_T const * x) {
665 0 : #ifndef REDBLK_UNSAFE
666 0 : REDBLK_(validate_element_const)(pool, x);
667 0 : #endif
668 :
669 : // if the right subtree is not null,
670 : // the successor is the leftmost node in the
671 : // right subtree
672 0 : if (x->REDBLK_RIGHT != REDBLK_NIL) {
673 0 : return REDBLK_(minimum_const)(pool, &pool[x->REDBLK_RIGHT]);
674 0 : }
675 :
676 : // else it is the lowest ancestor of x whose
677 : // left child is also an ancestor of x.
678 0 : for (;;) {
679 0 : if (x->REDBLK_PARENT == REDBLK_NIL)
680 0 : return NULL;
681 0 : REDBLK_T const * y = &pool[x->REDBLK_PARENT];
682 0 : if (x == &pool[y->REDBLK_LEFT])
683 0 : return y;
684 0 : x = y;
685 0 : }
686 0 : }
687 :
688 : /*
689 : Return the previous node which is smaller than the given node.
690 : */
691 4083000 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(predecessor)(REDBLK_T * pool, REDBLK_T * x) {
692 4083000 : #ifndef REDBLK_UNSAFE
693 4083000 : REDBLK_(validate_element)(pool, x);
694 4083000 : #endif
695 :
696 : // if the left subtree is not null,
697 : // the predecessor is the rightmost node in the
698 : // left subtree
699 4083000 : if (x->REDBLK_LEFT != REDBLK_NIL) {
700 2038752 : return REDBLK_(maximum)(pool, &pool[x->REDBLK_LEFT]);
701 2038752 : }
702 :
703 : // else it is the lowest ancestor of x whose
704 : // right child is also an ancestor of x.
705 4083000 : for (;;) {
706 4083000 : if (x->REDBLK_PARENT == REDBLK_NIL)
707 3000 : return NULL;
708 4080000 : REDBLK_T * y = &pool[x->REDBLK_PARENT];
709 4080000 : if (x == &pool[y->REDBLK_RIGHT])
710 2041248 : return y;
711 2038752 : x = y;
712 2038752 : }
713 2044248 : }
714 0 : REDBLK_IMPL_STATIC REDBLK_T const * REDBLK_(predecessor_const)(REDBLK_T const * pool, REDBLK_T const * x) {
715 0 : #ifndef REDBLK_UNSAFE
716 0 : REDBLK_(validate_element_const)(pool, x);
717 0 : #endif
718 :
719 : // if the left subtree is not null,
720 : // the predecessor is the rightmost node in the
721 : // left subtree
722 0 : if (x->REDBLK_LEFT != REDBLK_NIL) {
723 0 : return REDBLK_(maximum_const)(pool, &pool[x->REDBLK_LEFT]);
724 0 : }
725 :
726 : // else it is the lowest ancestor of x whose
727 : // right child is also an ancestor of x.
728 0 : for (;;) {
729 0 : if (x->REDBLK_PARENT == REDBLK_NIL)
730 0 : return NULL;
731 0 : REDBLK_T const * y = &pool[x->REDBLK_PARENT];
732 0 : if (x == &pool[y->REDBLK_RIGHT])
733 0 : return y;
734 0 : x = y;
735 0 : }
736 0 : }
737 :
738 : /*
739 : Perform a left rotation around a node
740 : */
741 98293005 : static void REDBLK_(rotateLeft)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
742 98293005 : REDBLK_T * y = &pool[x->REDBLK_RIGHT];
743 :
744 : /* establish x->REDBLK_RIGHT link */
745 98293005 : x->REDBLK_RIGHT = y->REDBLK_LEFT;
746 98293005 : if (y->REDBLK_LEFT != REDBLK_NIL)
747 24148893 : pool[y->REDBLK_LEFT].REDBLK_PARENT = (uint)(x - pool);
748 :
749 : /* establish y->REDBLK_PARENT link */
750 98293005 : if (y != &pool[REDBLK_NIL])
751 98293005 : y->REDBLK_PARENT = x->REDBLK_PARENT;
752 98293005 : if (x->REDBLK_PARENT) {
753 63480048 : REDBLK_T * p = &pool[x->REDBLK_PARENT];
754 63480048 : if (x == &pool[p->REDBLK_LEFT])
755 16970757 : p->REDBLK_LEFT = (uint)(y - pool);
756 46509291 : else
757 46509291 : p->REDBLK_RIGHT = (uint)(y - pool);
758 63480048 : } else {
759 34812957 : *root = y;
760 34812957 : }
761 :
762 : /* link x and y */
763 98293005 : y->REDBLK_LEFT = (uint)(x - pool);
764 98293005 : if (x != &pool[REDBLK_NIL])
765 98293005 : x->REDBLK_PARENT = (uint)(y - pool);
766 98293005 : }
767 :
768 : /*
769 : Perform a right rotation around a node
770 : */
771 34418229 : static void REDBLK_(rotateRight)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
772 34418229 : REDBLK_T * y = &pool[x->REDBLK_LEFT];
773 :
774 : /* establish x->REDBLK_LEFT link */
775 34418229 : x->REDBLK_LEFT = y->REDBLK_RIGHT;
776 34418229 : if (y->REDBLK_RIGHT != REDBLK_NIL)
777 5500597 : pool[y->REDBLK_RIGHT].REDBLK_PARENT = (uint)(x - pool);
778 :
779 : /* establish y->REDBLK_PARENT link */
780 34418229 : if (y != &pool[REDBLK_NIL])
781 34418229 : y->REDBLK_PARENT = x->REDBLK_PARENT;
782 34418229 : if (x->REDBLK_PARENT) {
783 24296949 : REDBLK_T * p = &pool[x->REDBLK_PARENT];
784 24296949 : if (x == &pool[p->REDBLK_RIGHT])
785 16265100 : p->REDBLK_RIGHT = (uint)(y - pool);
786 8031849 : else
787 8031849 : p->REDBLK_LEFT = (uint)(y - pool);
788 24296949 : } else {
789 10121280 : *root = y;
790 10121280 : }
791 :
792 : /* link x and y */
793 34418229 : y->REDBLK_RIGHT = (uint)(x - pool);
794 34418229 : if (x != &pool[REDBLK_NIL])
795 34418229 : x->REDBLK_PARENT = (uint)(y - pool);
796 34418229 : }
797 :
798 : /*
799 : Restore tree invariants after an insert.
800 : */
801 221836035 : static void REDBLK_(insertFixup)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
802 : /* check Red-Black properties */
803 221836035 : REDBLK_T * p;
804 396289929 : while (x != *root && (p = &pool[x->REDBLK_PARENT])->REDBLK_COLOR == REDBLK_RED) {
805 : /* we have a violation */
806 174453894 : REDBLK_T * gp = &pool[p->REDBLK_PARENT];
807 174453894 : if (x->REDBLK_PARENT == gp->REDBLK_LEFT) {
808 32790947 : REDBLK_T * y = &pool[gp->REDBLK_RIGHT];
809 32790947 : if (y->REDBLK_COLOR == REDBLK_RED) {
810 :
811 : /* uncle is REDBLK_RED */
812 16194686 : p->REDBLK_COLOR = REDBLK_BLACK;
813 16194686 : y->REDBLK_COLOR = REDBLK_BLACK;
814 16194686 : gp->REDBLK_COLOR = REDBLK_RED;
815 16194686 : x = gp;
816 16596261 : } else {
817 :
818 : /* uncle is REDBLK_BLACK */
819 16596261 : if (x == &pool[p->REDBLK_RIGHT]) {
820 : /* make x a left child */
821 8294429 : x = p;
822 8294429 : REDBLK_(rotateLeft)(pool, root, x);
823 8294429 : p = &pool[x->REDBLK_PARENT];
824 8294429 : gp = &pool[p->REDBLK_PARENT];
825 8294429 : }
826 :
827 : /* recolor and rotate */
828 16596261 : p->REDBLK_COLOR = REDBLK_BLACK;
829 16596261 : gp->REDBLK_COLOR = REDBLK_RED;
830 16596261 : REDBLK_(rotateRight)(pool, root, gp);
831 16596261 : }
832 :
833 141662947 : } else {
834 : /* mirror image of above code */
835 141662947 : REDBLK_T * y = &pool[gp->REDBLK_LEFT];
836 141662947 : if (y->REDBLK_COLOR == REDBLK_RED) {
837 :
838 : /* uncle is REDBLK_RED */
839 70628818 : p->REDBLK_COLOR = REDBLK_BLACK;
840 70628818 : y->REDBLK_COLOR = REDBLK_BLACK;
841 70628818 : gp->REDBLK_COLOR = REDBLK_RED;
842 70628818 : x = gp;
843 71034129 : } else {
844 :
845 : /* uncle is REDBLK_BLACK */
846 71034129 : if (x == &pool[p->REDBLK_LEFT]) {
847 8295628 : x = p;
848 8295628 : REDBLK_(rotateRight)(pool, root, x);
849 8295628 : p = &pool[x->REDBLK_PARENT];
850 8295628 : gp = &pool[p->REDBLK_PARENT];
851 8295628 : }
852 71034129 : p->REDBLK_COLOR = REDBLK_BLACK;
853 71034129 : gp->REDBLK_COLOR = REDBLK_RED;
854 71034129 : REDBLK_(rotateLeft)(pool, root, gp);
855 71034129 : }
856 141662947 : }
857 174453894 : }
858 :
859 221836035 : (*root)->REDBLK_COLOR = REDBLK_BLACK;
860 221836035 : }
861 :
862 : /*
863 : Insert a node into a tree. Typically, the node must be allocated
864 : from a pool first.
865 : */
866 217753035 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(insert)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
867 217753035 : #ifndef REDBLK_UNSAFE
868 217753035 : REDBLK_(validate_element)(pool, *root);
869 217753035 : REDBLK_(validate_element)(pool, x);
870 217753035 : #endif
871 :
872 217753035 : REDBLK_T * current;
873 217753035 : REDBLK_T * parent;
874 :
875 : /* find where node belongs */
876 217753035 : current = *root;
877 217753035 : if (current == NULL)
878 21772977 : current = &pool[REDBLK_NIL];
879 217753035 : parent = &pool[REDBLK_NIL];
880 756836634 : while (current != &pool[REDBLK_NIL]) {
881 539083599 : long c = REDBLK_(compare)(x, current);
882 539083599 : parent = current;
883 539083599 : current = (c < 0 ? &pool[current->REDBLK_LEFT] : &pool[current->REDBLK_RIGHT]);
884 539083599 : }
885 :
886 : /* setup new node */
887 217753035 : x->REDBLK_PARENT = (uint)(parent - pool);
888 217753035 : x->REDBLK_LEFT = REDBLK_NIL;
889 217753035 : x->REDBLK_RIGHT = REDBLK_NIL;
890 217753035 : x->REDBLK_COLOR = REDBLK_RED;
891 :
892 : /* insert node in tree */
893 217753035 : if (parent != &pool[REDBLK_NIL]) {
894 195980058 : long c = REDBLK_(compare)(x, parent);
895 195980058 : if (c < 0)
896 48998797 : parent->REDBLK_LEFT = (uint)(x - pool);
897 146981261 : else
898 146981261 : parent->REDBLK_RIGHT = (uint)(x - pool);
899 195980058 : } else {
900 21772977 : *root = x;
901 21772977 : }
902 :
903 217753035 : REDBLK_(insertFixup)(pool, root, x);
904 217753035 : return x;
905 217753035 : }
906 :
907 : /*
908 : Insert a node into a tree, replacing any elements that have the same key. Typically, the node must be allocated
909 : from a pool first.
910 : */
911 8163000 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(insert_or_replace)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x, REDBLK_T ** out) {
912 8163000 : #ifndef REDBLK_UNSAFE
913 8163000 : REDBLK_(validate_element)(pool, *root);
914 8163000 : REDBLK_(validate_element)(pool, x);
915 8163000 : #endif
916 :
917 8163000 : REDBLK_T * current;
918 8163000 : REDBLK_T * parent;
919 :
920 : /* find where node belongs */
921 8163000 : current = *root;
922 8163000 : if (current == NULL)
923 3000 : current = &pool[REDBLK_NIL];
924 8163000 : parent = &pool[REDBLK_NIL];
925 81368835 : while (current != &pool[REDBLK_NIL]) {
926 77285835 : long c = REDBLK_(compare)(x, current);
927 77285835 : if(c == 0) { /* Already in the tree so lets special case this */
928 4080000 : if(out != NULL)
929 4080000 : *out = current;
930 :
931 4080000 : x->REDBLK_PARENT = current->REDBLK_PARENT;
932 4080000 : x->REDBLK_LEFT = current->REDBLK_LEFT;
933 4080000 : x->REDBLK_RIGHT = current->REDBLK_RIGHT;
934 4080000 : x->REDBLK_COLOR = current->REDBLK_COLOR;
935 :
936 : /* Lets wire this in */
937 4080000 : if( x->REDBLK_LEFT != REDBLK_NIL )
938 581211 : pool[x->REDBLK_LEFT].REDBLK_PARENT = (uint)(x - pool);
939 4080000 : if( x->REDBLK_RIGHT != REDBLK_NIL )
940 581211 : pool[x->REDBLK_RIGHT].REDBLK_PARENT = (uint)(x - pool);
941 4080000 : if( x->REDBLK_PARENT != REDBLK_NIL ) {
942 4075977 : if( pool[x->REDBLK_PARENT].REDBLK_LEFT == (uint)(current - pool) )
943 2036667 : pool[x->REDBLK_PARENT].REDBLK_LEFT = (uint)(x - pool);
944 4075977 : if( pool[x->REDBLK_PARENT].REDBLK_RIGHT == (uint)(current - pool) )
945 2039310 : pool[x->REDBLK_PARENT].REDBLK_RIGHT = (uint)(x - pool);
946 4075977 : }
947 4080000 : if(*root == current)
948 4023 : *root = x;
949 :
950 4080000 : return x;
951 4080000 : }
952 :
953 73205835 : parent = current;
954 73205835 : current = (c < 0 ? &pool[current->REDBLK_LEFT] : &pool[current->REDBLK_RIGHT]);
955 73205835 : }
956 :
957 : /* setup new node */
958 4083000 : x->REDBLK_PARENT = (uint)(parent - pool);
959 4083000 : x->REDBLK_LEFT = REDBLK_NIL;
960 4083000 : x->REDBLK_RIGHT = REDBLK_NIL;
961 4083000 : x->REDBLK_COLOR = REDBLK_RED;
962 :
963 : /* insert node in tree */
964 4083000 : if (parent != &pool[REDBLK_NIL]) {
965 4080000 : long c = REDBLK_(compare)(x, parent);
966 4080000 : if (c < 0)
967 2038440 : parent->REDBLK_LEFT = (uint)(x - pool);
968 2041560 : else
969 2041560 : parent->REDBLK_RIGHT = (uint)(x - pool);
970 4080000 : } else {
971 3000 : *root = x;
972 3000 : }
973 :
974 4083000 : REDBLK_(insertFixup)(pool, root, x);
975 4083000 : return x;
976 8163000 : }
977 :
978 : /*
979 : Restore tree invariants after a delete
980 : */
981 92124604 : static void REDBLK_(deleteFixup)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
982 166922082 : while (x != *root && x->REDBLK_COLOR == REDBLK_BLACK) {
983 74797478 : REDBLK_T * p = &pool[x->REDBLK_PARENT];
984 74797478 : if (x == &pool[p->REDBLK_LEFT]) {
985 37308631 : REDBLK_T * w = &pool[p->REDBLK_RIGHT];
986 37308631 : if (w->REDBLK_COLOR == REDBLK_RED) {
987 4179982 : w->REDBLK_COLOR = REDBLK_BLACK;
988 4179982 : p->REDBLK_COLOR = REDBLK_RED;
989 4179982 : REDBLK_(rotateLeft)(pool, root, p);
990 4179982 : p = &pool[x->REDBLK_PARENT];
991 4179982 : w = &pool[p->REDBLK_RIGHT];
992 4179982 : }
993 37308631 : if (pool[w->REDBLK_LEFT].REDBLK_COLOR == REDBLK_BLACK &&
994 37308631 : pool[w->REDBLK_RIGHT].REDBLK_COLOR == REDBLK_BLACK) {
995 25543657 : w->REDBLK_COLOR = REDBLK_RED;
996 25543657 : x = p;
997 25543657 : } else {
998 11764974 : if (pool[w->REDBLK_RIGHT].REDBLK_COLOR == REDBLK_BLACK) {
999 1505646 : pool[w->REDBLK_LEFT].REDBLK_COLOR = REDBLK_BLACK;
1000 1505646 : w->REDBLK_COLOR = REDBLK_RED;
1001 1505646 : REDBLK_(rotateRight)(pool, root, w);
1002 1505646 : p = &pool[x->REDBLK_PARENT];
1003 1505646 : w = &pool[p->REDBLK_RIGHT];
1004 1505646 : }
1005 11764974 : w->REDBLK_COLOR = p->REDBLK_COLOR;
1006 11764974 : p->REDBLK_COLOR = REDBLK_BLACK;
1007 11764974 : pool[w->REDBLK_RIGHT].REDBLK_COLOR = REDBLK_BLACK;
1008 11764974 : REDBLK_(rotateLeft)(pool, root, p);
1009 11764974 : x = *root;
1010 11764974 : }
1011 :
1012 37488847 : } else {
1013 37488847 : REDBLK_T * w = &pool[p->REDBLK_LEFT];
1014 37488847 : if (w->REDBLK_COLOR == REDBLK_RED) {
1015 1499645 : w->REDBLK_COLOR = REDBLK_BLACK;
1016 1499645 : p->REDBLK_COLOR = REDBLK_RED;
1017 1499645 : REDBLK_(rotateRight)(pool, root, p);
1018 1499645 : p = &pool[x->REDBLK_PARENT];
1019 1499645 : w = &pool[p->REDBLK_LEFT];
1020 1499645 : }
1021 37488847 : if (pool[w->REDBLK_RIGHT].REDBLK_COLOR == REDBLK_BLACK &&
1022 37488847 : pool[w->REDBLK_LEFT].REDBLK_COLOR == REDBLK_BLACK) {
1023 30967798 : w->REDBLK_COLOR = REDBLK_RED;
1024 30967798 : x = p;
1025 30967798 : } else {
1026 6521049 : if (pool[w->REDBLK_LEFT].REDBLK_COLOR == REDBLK_BLACK) {
1027 3019491 : pool[w->REDBLK_RIGHT].REDBLK_COLOR = REDBLK_BLACK;
1028 3019491 : w->REDBLK_COLOR = REDBLK_RED;
1029 3019491 : REDBLK_(rotateLeft)(pool, root, w);
1030 3019491 : p = &pool[x->REDBLK_PARENT];
1031 3019491 : w = &pool[p->REDBLK_LEFT];
1032 3019491 : }
1033 6521049 : w->REDBLK_COLOR = p->REDBLK_COLOR;
1034 6521049 : p->REDBLK_COLOR = REDBLK_BLACK;
1035 6521049 : pool[w->REDBLK_LEFT].REDBLK_COLOR = REDBLK_BLACK;
1036 6521049 : REDBLK_(rotateRight)(pool, root, p);
1037 6521049 : x = *root;
1038 6521049 : }
1039 37488847 : }
1040 74797478 : }
1041 :
1042 92124604 : x->REDBLK_COLOR = REDBLK_BLACK;
1043 92124604 : }
1044 :
1045 : /*
1046 : Remove a node from a tree. The node must be a member of the tree,
1047 : usually the result of a find operation. The node is typically
1048 : released to the pool afterwards.
1049 : */
1050 112950580 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(remove)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * z) {
1051 112950580 : #ifndef REDBLK_UNSAFE
1052 112950580 : REDBLK_(validate_element)(pool, *root);
1053 112950580 : REDBLK_(validate_element)(pool, z);
1054 112950580 : #endif
1055 :
1056 112950580 : REDBLK_T * x;
1057 112950580 : REDBLK_T * y;
1058 :
1059 112950580 : if (!z || z == &pool[REDBLK_NIL])
1060 0 : return NULL;
1061 :
1062 112950580 : if (z->REDBLK_LEFT == REDBLK_NIL || z->REDBLK_RIGHT == REDBLK_NIL) {
1063 : /* y has a REDBLK_NIL node as a child */
1064 81489214 : y = z;
1065 81489214 : } else {
1066 : /* find tree successor with a REDBLK_NIL node as a child */
1067 31461366 : y = &pool[z->REDBLK_RIGHT];
1068 43608885 : while (y->REDBLK_LEFT != REDBLK_NIL)
1069 12147519 : y = &pool[y->REDBLK_LEFT];
1070 31461366 : }
1071 :
1072 : /* x is y's only child */
1073 112950580 : if (y->REDBLK_LEFT != REDBLK_NIL)
1074 9310918 : x = &pool[y->REDBLK_LEFT];
1075 103639662 : else
1076 103639662 : x = &pool[y->REDBLK_RIGHT];
1077 :
1078 : /* remove y from the parent chain */
1079 112950580 : x->REDBLK_PARENT = y->REDBLK_PARENT;
1080 112950580 : if (y->REDBLK_PARENT)
1081 96616420 : if (y == &pool[pool[y->REDBLK_PARENT].REDBLK_LEFT])
1082 45041383 : pool[y->REDBLK_PARENT].REDBLK_LEFT = (uint)(x - pool);
1083 51575037 : else
1084 51575037 : pool[y->REDBLK_PARENT].REDBLK_RIGHT = (uint)(x - pool);
1085 16334160 : else
1086 16334160 : *root = x;
1087 :
1088 112950580 : if (y->REDBLK_COLOR == REDBLK_BLACK)
1089 92124604 : REDBLK_(deleteFixup)(pool, root, x);
1090 :
1091 112950580 : if (y != z) {
1092 : /* we got rid of y instead of z. Oops! Replace z with y in the
1093 : * tree so we don't lose y's key/value. */
1094 31461366 : y->REDBLK_PARENT = z->REDBLK_PARENT;
1095 31461366 : y->REDBLK_LEFT = z->REDBLK_LEFT;
1096 31461366 : y->REDBLK_RIGHT = z->REDBLK_RIGHT;
1097 31461366 : y->REDBLK_COLOR = z->REDBLK_COLOR;
1098 31461366 : if (z == *root)
1099 13492889 : *root = y;
1100 17968477 : else if (&pool[pool[y->REDBLK_PARENT].REDBLK_LEFT] == z)
1101 5629818 : pool[y->REDBLK_PARENT].REDBLK_LEFT = (uint)(y - pool);
1102 12338659 : else
1103 12338659 : pool[y->REDBLK_PARENT].REDBLK_RIGHT = (uint)(y - pool);
1104 31461366 : pool[y->REDBLK_LEFT].REDBLK_PARENT = (uint)(y - pool);
1105 31461366 : pool[y->REDBLK_RIGHT].REDBLK_PARENT = (uint)(y - pool);
1106 31461366 : }
1107 :
1108 112950580 : if (*root == &pool[REDBLK_NIL])
1109 10889451 : *root = NULL;
1110 112950580 : z->REDBLK_COLOR = REDBLK_NEW;
1111 112950580 : return z;
1112 112950580 : }
1113 :
1114 : /*
1115 : Search for a key in the tree. In this special case, the key can be a
1116 : temporary instance of the node type rather than a properly
1117 : allocated node.
1118 : */
1119 451865018 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(find)(REDBLK_T * pool, REDBLK_T * root, REDBLK_T * key) {
1120 451865018 : #ifndef REDBLK_UNSAFE
1121 451865018 : REDBLK_(validate_element)(pool, root);
1122 451865018 : #endif
1123 :
1124 451865018 : REDBLK_T * current = root;
1125 451865018 : if (current == NULL || current == &pool[REDBLK_NIL])
1126 10886454 : return NULL;
1127 1369833354 : while (current != &pool[REDBLK_NIL]) {
1128 1271814126 : long c = REDBLK_(compare)(key, current);
1129 1271814126 : if (c == 0)
1130 342959336 : return current;
1131 928854790 : current = (c < 0 ? &pool[current->REDBLK_LEFT] : &pool[current->REDBLK_RIGHT]);
1132 928854790 : }
1133 98019228 : return NULL;
1134 440978564 : }
1135 :
1136 : /*
1137 : Search for a key in the tree. If the key can't be found, a nearby
1138 : approximation is returned instead. This is either the greatest node
1139 : less than the key, or the least node greater than the key. In this
1140 : special case, the key can be a temporary instance of the node type
1141 : rather than a properly allocated node.
1142 : */
1143 0 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(nearby)(REDBLK_T * pool, REDBLK_T * root, REDBLK_T * key) {
1144 0 : #ifndef REDBLK_UNSAFE
1145 0 : REDBLK_(validate_element)(pool, root);
1146 0 : #endif
1147 :
1148 0 : REDBLK_T * current = root;
1149 0 : if (current == NULL || current == &pool[REDBLK_NIL])
1150 0 : return NULL;
1151 0 : REDBLK_T * result = current;
1152 0 : while (current != &pool[REDBLK_NIL]) {
1153 0 : result = current; /* Return the last non-NIL node that was touched */
1154 0 : long c = REDBLK_(compare)(key, current);
1155 0 : if (c == 0)
1156 0 : return current;
1157 0 : current = (c < 0 ? &pool[current->REDBLK_LEFT] : &pool[current->REDBLK_RIGHT]);
1158 0 : }
1159 0 : return result;
1160 0 : }
1161 :
1162 : /*
1163 : Count the number of nodes in a tree.
1164 : */
1165 3717005870 : REDBLK_IMPL_STATIC ulong REDBLK_(size)(REDBLK_T * pool, REDBLK_T * root) {
1166 3717005870 : #ifndef REDBLK_UNSAFE
1167 3717005870 : REDBLK_(validate_element)(pool, root);
1168 3717005870 : #endif
1169 3717005870 : if (!root || root == &pool[REDBLK_NIL])
1170 2016362310 : return 0;
1171 1700643560 : return 1 +
1172 1700643560 : REDBLK_(size)(pool, &pool[root->REDBLK_LEFT]) +
1173 1700643560 : REDBLK_(size)(pool, &pool[root->REDBLK_RIGHT]);
1174 3717005870 : }
1175 :
1176 : /*
1177 : Recursive implementation of the verify function
1178 : */
1179 3717005870 : static int REDBLK_(verify_private)(REDBLK_T * pool, REDBLK_T * node, REDBLK_T * parent, ulong curblkcnt, ulong correctblkcnt) {
1180 7272603584 : # define REDBLK_TEST(c) do { \
1181 7272603584 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
1182 7272603584 : } while(0)
1183 :
1184 3717005870 : if (!node || node == &pool[REDBLK_NIL]) {
1185 2016362310 : REDBLK_TEST(curblkcnt == correctblkcnt);
1186 2016362310 : return 0;
1187 2016362310 : }
1188 :
1189 1700643560 : #ifndef REDBLK_UNSAFE
1190 1700643560 : REDBLK_(validate_element)(pool, node);
1191 1700643560 : #endif
1192 :
1193 1700643560 : REDBLK_TEST(&pool[node->REDBLK_PARENT] == parent);
1194 :
1195 1700643560 : if (node->REDBLK_COLOR == REDBLK_BLACK)
1196 1094329957 : ++curblkcnt;
1197 606313603 : else {
1198 606313603 : REDBLK_TEST(node->REDBLK_COLOR == REDBLK_RED);
1199 606313603 : REDBLK_TEST(parent->REDBLK_COLOR == REDBLK_BLACK);
1200 606313603 : }
1201 :
1202 1700643560 : if (node->REDBLK_LEFT != REDBLK_NIL)
1203 663957056 : REDBLK_TEST(REDBLK_(compare)(&pool[node->REDBLK_LEFT], node) <= 0);
1204 1700643560 : if (node->REDBLK_RIGHT != REDBLK_NIL)
1205 720967754 : REDBLK_TEST(REDBLK_(compare)(node, &pool[node->REDBLK_RIGHT]) <= 0);
1206 :
1207 1700643560 : int err = REDBLK_(verify_private)(pool, &pool[node->REDBLK_LEFT], node, curblkcnt, correctblkcnt);
1208 1700643560 : if (err) return err;
1209 1700643560 : return REDBLK_(verify_private)(pool, &pool[node->REDBLK_RIGHT], node, curblkcnt, correctblkcnt);
1210 1700643560 : }
1211 :
1212 : /*
1213 : Verify the integrity of the tree data structure. Useful for
1214 : debugging memory corruption. A non-zero result is returned if an error
1215 : is detected.
1216 : */
1217 326608198 : REDBLK_IMPL_STATIC int REDBLK_(verify)(REDBLK_T * pool, REDBLK_T * root) {
1218 326608198 : REDBLK_TEST(pool[REDBLK_NIL].REDBLK_LEFT == REDBLK_NIL &&
1219 326608198 : pool[REDBLK_NIL].REDBLK_RIGHT == REDBLK_NIL &&
1220 326608198 : pool[REDBLK_NIL].REDBLK_COLOR == REDBLK_BLACK);
1221 :
1222 326608198 : if (!root || root == &pool[REDBLK_NIL])
1223 10889448 : return 0; // Trivially correct
1224 315718750 : REDBLK_TEST(root->REDBLK_COLOR == REDBLK_BLACK);
1225 :
1226 315718750 : ulong sz = REDBLK_(size)(pool, root);
1227 315718750 : REDBLK_TEST(sz + 1 == REDBLK_POOL_(used)(pool));
1228 :
1229 : // Compute the correct number of black nodes on a path
1230 315718750 : ulong blkcnt = 0;
1231 315718750 : REDBLK_T * node = root;
1232 1047930256 : while (node != &pool[REDBLK_NIL]) {
1233 732211506 : if (node->REDBLK_COLOR == REDBLK_BLACK)
1234 582354405 : ++blkcnt;
1235 732211506 : node = &pool[node->REDBLK_LEFT];
1236 732211506 : }
1237 : // Recursive check
1238 315718750 : return REDBLK_(verify_private)(pool, root, &pool[REDBLK_NIL], 0, blkcnt);
1239 :
1240 315718750 : #undef REDBLK_TEST
1241 315718750 : }
1242 :
1243 : #undef REDBLK_FREE
1244 : #undef REDBLK_NEW
1245 : #undef REDBLK_BLACK
1246 : #undef REDBLK_RED
1247 : #undef REDBLK_POOL_
1248 : #undef REDBLK_PARENT
1249 : #undef REDBLK_LEFT
1250 : #undef REDBLK_RIGHT
1251 : #undef REDBLK_COLOR
1252 :
1253 : #endif /* REDBLK_IMPL_STYLE==0 || REDBLK_IMPL_STYLE==2 */
1254 :
1255 : #undef REDBLK_IMPL_STATIC
1256 : #undef REDBLK_
1257 : #undef REDBLK_T
1258 : #undef REDBLK_IMPL_STYLE
1259 : #undef REDBLK_NAME
|
