LCOV - code coverage report
Current view: top level - util/tmpl - fd_redblack.c (source / functions) Hit Total Coverage
Test: cov.lcov Lines: 490 573 85.5 %
Date: 2025-07-01 05:00:49 Functions: 64 648 9.9 %

          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 17194216232 : #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  7087666269 : #define REDBLK_FREE -1
     441   338866657 : #define REDBLK_NEW 0
     442  3516437186 : #define REDBLK_BLACK 1
     443  1053969982 : #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   435485705 : #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  7572167069 : #define REDBLK_POOL_(n) FD_EXPAND_THEN_CONCAT3(REDBLK_NAME,_pool_,n)
     471             : 
     472 17393837598 : #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   225922045 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(acquire)( REDBLK_T * pool ) {
     534   225922045 :   if ( REDBLK_POOL_(free)( pool ) == 0 )
     535        6009 :     return NULL;
     536   225916036 :   REDBLK_T * node = REDBLK_POOL_(ele_acquire)(pool);
     537   225916036 :   node->REDBLK_COLOR = REDBLK_NEW;
     538   225916036 :   return node;
     539   225922045 : }
     540             : 
     541             : #ifndef REDBLK_UNSAFE
     542  6894406544 : REDBLK_IMPL_STATIC void REDBLK_(validate_element)( REDBLK_T * pool, REDBLK_T * node ) {
     543  6894406544 :   if ( !REDBLK_POOL_(ele_test)( pool, node ) )
     544           0 :     FD_LOG_CRIT(( "invalid redblack node" ));
     545  6894406544 :   if ( node && node->REDBLK_COLOR == REDBLK_FREE )
     546           0 :     FD_LOG_CRIT(( "invalid redblack node" ));
     547  6894406544 : }
     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   225922156 : REDBLK_IMPL_STATIC void REDBLK_(release)( REDBLK_T * pool, REDBLK_T * node ) {
     557   225922156 : #ifndef REDBLK_UNSAFE
     558   225922156 :   REDBLK_(validate_element)(pool, node);
     559   225922156 : #endif
     560             : 
     561   225922156 :   node->REDBLK_COLOR = REDBLK_FREE;
     562   225922156 :   REDBLK_POOL_(ele_release)(pool, node);
     563   225922156 : }
     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   239556059 : REDBLK_IMPL_STATIC void REDBLK_(release_tree)( REDBLK_T * pool, REDBLK_T * node ) {
     570   239556059 :   if (!node || node == &pool[REDBLK_NIL])
     571   130664524 :     return;
     572             : 
     573   108891535 : #ifndef REDBLK_UNSAFE
     574   108891535 :   REDBLK_(validate_element)(pool, node);
     575   108891535 : #endif
     576             : 
     577   108891535 :   REDBLK_T * left = &pool[node->REDBLK_LEFT];
     578   108891535 :   REDBLK_T * right = &pool[node->REDBLK_RIGHT];
     579             : 
     580   108891535 :   REDBLK_(release)(pool, node);
     581             : 
     582   108891535 :   REDBLK_(release_tree)(pool, left);
     583   108891535 :   REDBLK_(release_tree)(pool, right);
     584   108891535 : }
     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    98293042 : static void REDBLK_(rotateLeft)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
     742    98293042 :   REDBLK_T * y = &pool[x->REDBLK_RIGHT];
     743             : 
     744             :   /* establish x->REDBLK_RIGHT link */
     745    98293042 :   x->REDBLK_RIGHT = y->REDBLK_LEFT;
     746    98293042 :   if (y->REDBLK_LEFT != REDBLK_NIL)
     747    24148918 :     pool[y->REDBLK_LEFT].REDBLK_PARENT = (uint)(x - pool);
     748             : 
     749             :   /* establish y->REDBLK_PARENT link */
     750    98293042 :   if (y != &pool[REDBLK_NIL])
     751    98293042 :     y->REDBLK_PARENT = x->REDBLK_PARENT;
     752    98293042 :   if (x->REDBLK_PARENT) {
     753    63480087 :     REDBLK_T * p = &pool[x->REDBLK_PARENT];
     754    63480087 :     if (x == &pool[p->REDBLK_LEFT])
     755    16970774 :       p->REDBLK_LEFT = (uint)(y - pool);
     756    46509313 :     else
     757    46509313 :       p->REDBLK_RIGHT = (uint)(y - pool);
     758    63480087 :   } else {
     759    34812955 :     *root = y;
     760    34812955 :   }
     761             : 
     762             :   /* link x and y */
     763    98293042 :   y->REDBLK_LEFT = (uint)(x - pool);
     764    98293042 :   if (x != &pool[REDBLK_NIL])
     765    98293042 :     x->REDBLK_PARENT = (uint)(y - pool);
     766    98293042 : }
     767             : 
     768             : /*
     769             :   Perform a right rotation around a node
     770             : */
     771    34418219 : static void REDBLK_(rotateRight)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
     772    34418219 :   REDBLK_T * y = &pool[x->REDBLK_LEFT];
     773             : 
     774             :   /* establish x->REDBLK_LEFT link */
     775    34418219 :   x->REDBLK_LEFT = y->REDBLK_RIGHT;
     776    34418219 :   if (y->REDBLK_RIGHT != REDBLK_NIL)
     777     5500632 :     pool[y->REDBLK_RIGHT].REDBLK_PARENT = (uint)(x - pool);
     778             : 
     779             :   /* establish y->REDBLK_PARENT link */
     780    34418219 :   if (y != &pool[REDBLK_NIL])
     781    34418219 :     y->REDBLK_PARENT = x->REDBLK_PARENT;
     782    34418219 :   if (x->REDBLK_PARENT) {
     783    24296936 :     REDBLK_T * p = &pool[x->REDBLK_PARENT];
     784    24296936 :     if (x == &pool[p->REDBLK_RIGHT])
     785    16265113 :       p->REDBLK_RIGHT = (uint)(y - pool);
     786     8031823 :     else
     787     8031823 :       p->REDBLK_LEFT = (uint)(y - pool);
     788    24296936 :   } else {
     789    10121283 :     *root = y;
     790    10121283 :   }
     791             : 
     792             :   /* link x and y */
     793    34418219 :   y->REDBLK_RIGHT = (uint)(x - pool);
     794    34418219 :   if (x != &pool[REDBLK_NIL])
     795    34418219 :     x->REDBLK_PARENT = (uint)(y - pool);
     796    34418219 : }
     797             : 
     798             : /*
     799             :   Restore tree invariants after an insert.
     800             : */
     801   221836036 : static void REDBLK_(insertFixup)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
     802             :   /* check Red-Black properties */
     803   221836036 :   REDBLK_T * p;
     804   396289972 :   while (x != *root && (p = &pool[x->REDBLK_PARENT])->REDBLK_COLOR == REDBLK_RED) {
     805             :     /* we have a violation */
     806   174453936 :     REDBLK_T * gp = &pool[p->REDBLK_PARENT];
     807   174453936 :     if (x->REDBLK_PARENT == gp->REDBLK_LEFT) {
     808    32790919 :       REDBLK_T * y = &pool[gp->REDBLK_RIGHT];
     809    32790919 :       if (y->REDBLK_COLOR == REDBLK_RED) {
     810             : 
     811             :         /* uncle is REDBLK_RED */
     812    16194674 :         p->REDBLK_COLOR = REDBLK_BLACK;
     813    16194674 :         y->REDBLK_COLOR = REDBLK_BLACK;
     814    16194674 :         gp->REDBLK_COLOR = REDBLK_RED;
     815    16194674 :         x = gp;
     816    16596245 :       } else {
     817             : 
     818             :         /* uncle is REDBLK_BLACK */
     819    16596245 :         if (x == &pool[p->REDBLK_RIGHT]) {
     820             :           /* make x a left child */
     821     8294424 :           x = p;
     822     8294424 :           REDBLK_(rotateLeft)(pool, root, x);
     823     8294424 :           p = &pool[x->REDBLK_PARENT];
     824     8294424 :           gp = &pool[p->REDBLK_PARENT];
     825     8294424 :         }
     826             : 
     827             :         /* recolor and rotate */
     828    16596245 :         p->REDBLK_COLOR = REDBLK_BLACK;
     829    16596245 :         gp->REDBLK_COLOR = REDBLK_RED;
     830    16596245 :         REDBLK_(rotateRight)(pool, root, gp);
     831    16596245 :       }
     832             : 
     833   141663017 :     } else {
     834             :       /* mirror image of above code */
     835   141663017 :       REDBLK_T * y = &pool[gp->REDBLK_LEFT];
     836   141663017 :       if (y->REDBLK_COLOR == REDBLK_RED) {
     837             : 
     838             :         /* uncle is REDBLK_RED */
     839    70628861 :         p->REDBLK_COLOR = REDBLK_BLACK;
     840    70628861 :         y->REDBLK_COLOR = REDBLK_BLACK;
     841    70628861 :         gp->REDBLK_COLOR = REDBLK_RED;
     842    70628861 :         x = gp;
     843    71034156 :       } else {
     844             : 
     845             :         /* uncle is REDBLK_BLACK */
     846    71034156 :         if (x == &pool[p->REDBLK_LEFT]) {
     847     8295617 :           x = p;
     848     8295617 :           REDBLK_(rotateRight)(pool, root, x);
     849     8295617 :           p = &pool[x->REDBLK_PARENT];
     850     8295617 :           gp = &pool[p->REDBLK_PARENT];
     851     8295617 :         }
     852    71034156 :         p->REDBLK_COLOR = REDBLK_BLACK;
     853    71034156 :         gp->REDBLK_COLOR = REDBLK_RED;
     854    71034156 :         REDBLK_(rotateLeft)(pool, root, gp);
     855    71034156 :       }
     856   141663017 :     }
     857   174453936 :   }
     858             : 
     859   221836036 :   (*root)->REDBLK_COLOR = REDBLK_BLACK;
     860   221836036 : }
     861             : 
     862             : /*
     863             :   Insert a node into a tree. Typically, the node must be allocated
     864             :   from a pool first.
     865             : */
     866   217753036 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(insert)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
     867   217753036 : #ifndef REDBLK_UNSAFE
     868   217753036 :   REDBLK_(validate_element)(pool, *root);
     869   217753036 :   REDBLK_(validate_element)(pool, x);
     870   217753036 : #endif
     871             : 
     872   217753036 :   REDBLK_T * current;
     873   217753036 :   REDBLK_T * parent;
     874             : 
     875             :   /* find where node belongs */
     876   217753036 :   current = *root;
     877   217753036 :   if (current == NULL)
     878    21772977 :     current = &pool[REDBLK_NIL];
     879   217753036 :   parent = &pool[REDBLK_NIL];
     880   756837027 :   while (current != &pool[REDBLK_NIL]) {
     881   539083991 :     long c = REDBLK_(compare)(x, current);
     882   539083991 :     parent = current;
     883   539083991 :     current = (c < 0 ? &pool[current->REDBLK_LEFT] : &pool[current->REDBLK_RIGHT]);
     884   539083991 :   }
     885             : 
     886             :   /* setup new node */
     887   217753036 :   x->REDBLK_PARENT = (uint)(parent - pool);
     888   217753036 :   x->REDBLK_LEFT = REDBLK_NIL;
     889   217753036 :   x->REDBLK_RIGHT = REDBLK_NIL;
     890   217753036 :   x->REDBLK_COLOR = REDBLK_RED;
     891             : 
     892             :   /* insert node in tree */
     893   217753036 :   if (parent != &pool[REDBLK_NIL]) {
     894   195980059 :     long c = REDBLK_(compare)(x, parent);
     895   195980059 :     if (c < 0)
     896    48998722 :       parent->REDBLK_LEFT = (uint)(x - pool);
     897   146981337 :     else
     898   146981337 :       parent->REDBLK_RIGHT = (uint)(x - pool);
     899   195980059 :   } else {
     900    21772977 :     *root = x;
     901    21772977 :   }
     902             : 
     903   217753036 :   REDBLK_(insertFixup)(pool, root, x);
     904   217753036 :   return x;
     905   217753036 : }
     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    92124670 : static void REDBLK_(deleteFixup)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * x) {
     982   166922230 :   while (x != *root && x->REDBLK_COLOR == REDBLK_BLACK) {
     983    74797560 :     REDBLK_T * p = &pool[x->REDBLK_PARENT];
     984    74797560 :     if (x == &pool[p->REDBLK_LEFT]) {
     985    37308669 :       REDBLK_T * w = &pool[p->REDBLK_RIGHT];
     986    37308669 :       if (w->REDBLK_COLOR == REDBLK_RED) {
     987     4179981 :         w->REDBLK_COLOR = REDBLK_BLACK;
     988     4179981 :         p->REDBLK_COLOR = REDBLK_RED;
     989     4179981 :         REDBLK_(rotateLeft)(pool, root, p);
     990     4179981 :         p = &pool[x->REDBLK_PARENT];
     991     4179981 :         w = &pool[p->REDBLK_RIGHT];
     992     4179981 :       }
     993    37308669 :       if (pool[w->REDBLK_LEFT].REDBLK_COLOR == REDBLK_BLACK &&
     994    37308669 :          pool[w->REDBLK_RIGHT].REDBLK_COLOR == REDBLK_BLACK) {
     995    25543676 :         w->REDBLK_COLOR = REDBLK_RED;
     996    25543676 :         x = p;
     997    25543676 :       } else {
     998    11764993 :         if (pool[w->REDBLK_RIGHT].REDBLK_COLOR == REDBLK_BLACK) {
     999     1505669 :           pool[w->REDBLK_LEFT].REDBLK_COLOR = REDBLK_BLACK;
    1000     1505669 :           w->REDBLK_COLOR = REDBLK_RED;
    1001     1505669 :           REDBLK_(rotateRight)(pool, root, w);
    1002     1505669 :           p = &pool[x->REDBLK_PARENT];
    1003     1505669 :           w = &pool[p->REDBLK_RIGHT];
    1004     1505669 :         }
    1005    11764993 :         w->REDBLK_COLOR = p->REDBLK_COLOR;
    1006    11764993 :         p->REDBLK_COLOR = REDBLK_BLACK;
    1007    11764993 :         pool[w->REDBLK_RIGHT].REDBLK_COLOR = REDBLK_BLACK;
    1008    11764993 :         REDBLK_(rotateLeft)(pool, root, p);
    1009    11764993 :         x = *root;
    1010    11764993 :       }
    1011             : 
    1012    37488891 :     } else {
    1013    37488891 :       REDBLK_T * w = &pool[p->REDBLK_LEFT];
    1014    37488891 :       if (w->REDBLK_COLOR == REDBLK_RED) {
    1015     1499643 :         w->REDBLK_COLOR = REDBLK_BLACK;
    1016     1499643 :         p->REDBLK_COLOR = REDBLK_RED;
    1017     1499643 :         REDBLK_(rotateRight)(pool, root, p);
    1018     1499643 :         p = &pool[x->REDBLK_PARENT];
    1019     1499643 :         w = &pool[p->REDBLK_LEFT];
    1020     1499643 :       }
    1021    37488891 :       if (pool[w->REDBLK_RIGHT].REDBLK_COLOR == REDBLK_BLACK &&
    1022    37488891 :           pool[w->REDBLK_LEFT].REDBLK_COLOR == REDBLK_BLACK) {
    1023    30967846 :         w->REDBLK_COLOR = REDBLK_RED;
    1024    30967846 :         x = p;
    1025    30967846 :       } else {
    1026     6521045 :         if (pool[w->REDBLK_LEFT].REDBLK_COLOR == REDBLK_BLACK) {
    1027     3019488 :           pool[w->REDBLK_RIGHT].REDBLK_COLOR = REDBLK_BLACK;
    1028     3019488 :           w->REDBLK_COLOR = REDBLK_RED;
    1029     3019488 :           REDBLK_(rotateLeft)(pool, root, w);
    1030     3019488 :           p = &pool[x->REDBLK_PARENT];
    1031     3019488 :           w = &pool[p->REDBLK_LEFT];
    1032     3019488 :         }
    1033     6521045 :         w->REDBLK_COLOR = p->REDBLK_COLOR;
    1034     6521045 :         p->REDBLK_COLOR = REDBLK_BLACK;
    1035     6521045 :         pool[w->REDBLK_LEFT].REDBLK_COLOR = REDBLK_BLACK;
    1036     6521045 :         REDBLK_(rotateRight)(pool, root, p);
    1037     6521045 :         x = *root;
    1038     6521045 :       }
    1039    37488891 :     }
    1040    74797560 :   }
    1041             : 
    1042    92124670 :   x->REDBLK_COLOR = REDBLK_BLACK;
    1043    92124670 : }
    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   112950621 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(remove)(REDBLK_T * pool, REDBLK_T ** root, REDBLK_T * z) {
    1051   112950621 : #ifndef REDBLK_UNSAFE
    1052   112950621 :   REDBLK_(validate_element)(pool, *root);
    1053   112950621 :   REDBLK_(validate_element)(pool, z);
    1054   112950621 : #endif
    1055             : 
    1056   112950621 :   REDBLK_T * x;
    1057   112950621 :   REDBLK_T * y;
    1058             : 
    1059   112950621 :   if (!z || z == &pool[REDBLK_NIL])
    1060           0 :     return NULL;
    1061             : 
    1062   112950621 :   if (z->REDBLK_LEFT == REDBLK_NIL || z->REDBLK_RIGHT == REDBLK_NIL) {
    1063             :     /* y has a REDBLK_NIL node as a child */
    1064    81489289 :     y = z;
    1065    81489289 :   } else {
    1066             :     /* find tree successor with a REDBLK_NIL node as a child */
    1067    31461332 :     y = &pool[z->REDBLK_RIGHT];
    1068    43608765 :     while (y->REDBLK_LEFT != REDBLK_NIL)
    1069    12147433 :       y = &pool[y->REDBLK_LEFT];
    1070    31461332 :   }
    1071             : 
    1072             :   /* x is y's only child */
    1073   112950621 :   if (y->REDBLK_LEFT != REDBLK_NIL)
    1074     9310940 :     x = &pool[y->REDBLK_LEFT];
    1075   103639681 :   else
    1076   103639681 :     x = &pool[y->REDBLK_RIGHT];
    1077             : 
    1078             :   /* remove y from the parent chain */
    1079   112950621 :   x->REDBLK_PARENT = y->REDBLK_PARENT;
    1080   112950621 :   if (y->REDBLK_PARENT)
    1081    96616461 :     if (y == &pool[pool[y->REDBLK_PARENT].REDBLK_LEFT])
    1082    45041389 :       pool[y->REDBLK_PARENT].REDBLK_LEFT = (uint)(x - pool);
    1083    51575072 :     else
    1084    51575072 :       pool[y->REDBLK_PARENT].REDBLK_RIGHT = (uint)(x - pool);
    1085    16334160 :   else
    1086    16334160 :     *root = x;
    1087             : 
    1088   112950621 :   if (y->REDBLK_COLOR == REDBLK_BLACK)
    1089    92124670 :     REDBLK_(deleteFixup)(pool, root, x);
    1090             : 
    1091   112950621 :   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    31461332 :     y->REDBLK_PARENT = z->REDBLK_PARENT;
    1095    31461332 :     y->REDBLK_LEFT = z->REDBLK_LEFT;
    1096    31461332 :     y->REDBLK_RIGHT = z->REDBLK_RIGHT;
    1097    31461332 :     y->REDBLK_COLOR = z->REDBLK_COLOR;
    1098    31461332 :     if (z == *root)
    1099    13492890 :       *root = y;
    1100    17968442 :     else if (&pool[pool[y->REDBLK_PARENT].REDBLK_LEFT] == z)
    1101     5629819 :       pool[y->REDBLK_PARENT].REDBLK_LEFT = (uint)(y - pool);
    1102    12338623 :     else
    1103    12338623 :       pool[y->REDBLK_PARENT].REDBLK_RIGHT = (uint)(y - pool);
    1104    31461332 :     pool[y->REDBLK_LEFT].REDBLK_PARENT = (uint)(y - pool);
    1105    31461332 :     pool[y->REDBLK_RIGHT].REDBLK_PARENT = (uint)(y - pool);
    1106    31461332 :   }
    1107             : 
    1108   112950621 :   if (*root == &pool[REDBLK_NIL])
    1109    10889451 :     *root = NULL;
    1110   112950621 :   z->REDBLK_COLOR = REDBLK_NEW;
    1111   112950621 :   return z;
    1112   112950621 : }
    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   451865100 : REDBLK_IMPL_STATIC REDBLK_T * REDBLK_(find)(REDBLK_T * pool, REDBLK_T * root, REDBLK_T * key) {
    1120   451865100 : #ifndef REDBLK_UNSAFE
    1121   451865100 :   REDBLK_(validate_element)(pool, root);
    1122   451865100 : #endif
    1123             : 
    1124   451865100 :   REDBLK_T * current = root;
    1125   451865100 :   if (current == NULL || current == &pool[REDBLK_NIL])
    1126    10886454 :     return NULL;
    1127  1369836740 :   while (current != &pool[REDBLK_NIL]) {
    1128  1271817511 :     long c = REDBLK_(compare)(key, current);
    1129  1271817511 :     if (c == 0)
    1130   342959417 :       return current;
    1131   928858094 :     current = (c < 0 ? &pool[current->REDBLK_LEFT] : &pool[current->REDBLK_RIGHT]);
    1132   928858094 :   }
    1133    98019229 :   return NULL;
    1134   440978646 : }
    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  3717067854 : REDBLK_IMPL_STATIC ulong REDBLK_(size)(REDBLK_T * pool, REDBLK_T * root) {
    1166  3717067854 : #ifndef REDBLK_UNSAFE
    1167  3717067854 :   REDBLK_(validate_element)(pool, root);
    1168  3717067854 : #endif
    1169  3717067854 :  if (!root || root == &pool[REDBLK_NIL])
    1170  2016393323 :    return 0;
    1171  1700674531 :  return 1 +
    1172  1700674531 :         REDBLK_(size)(pool, &pool[root->REDBLK_LEFT]) +
    1173  1700674531 :         REDBLK_(size)(pool, &pool[root->REDBLK_RIGHT]);
    1174  3717067854 : }
    1175             : 
    1176             : /*
    1177             :   Recursive implementation of the verify function
    1178             : */
    1179  3717067854 : static int REDBLK_(verify_private)(REDBLK_T * pool, REDBLK_T * node, REDBLK_T * parent, ulong curblkcnt, ulong correctblkcnt) {
    1180  7272685921 : # define REDBLK_TEST(c) do {                                                        \
    1181  7272685921 :     if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
    1182  7272685921 :   } while(0)
    1183             : 
    1184  3717067854 :   if (!node || node == &pool[REDBLK_NIL]) {
    1185  2016393323 :     REDBLK_TEST(curblkcnt == correctblkcnt);
    1186  2016393323 :     return 0;
    1187  2016393323 :   }
    1188             : 
    1189  1700674531 : #ifndef REDBLK_UNSAFE
    1190  1700674531 :   REDBLK_(validate_element)(pool, node);
    1191  1700674531 : #endif
    1192             : 
    1193  1700674531 :   REDBLK_TEST(&pool[node->REDBLK_PARENT] == parent);
    1194             : 
    1195  1700674531 :   if (node->REDBLK_COLOR == REDBLK_BLACK)
    1196  1094366279 :     ++curblkcnt;
    1197   606308252 :   else {
    1198   606308252 :     REDBLK_TEST(node->REDBLK_COLOR == REDBLK_RED);
    1199   606308252 :     REDBLK_TEST(parent->REDBLK_COLOR == REDBLK_BLACK);
    1200   606308252 :   }
    1201             : 
    1202  1700674531 :   if (node->REDBLK_LEFT != REDBLK_NIL)
    1203   663949847 :     REDBLK_TEST(REDBLK_(compare)(&pool[node->REDBLK_LEFT], node) <= 0);
    1204  1700674531 :   if (node->REDBLK_RIGHT != REDBLK_NIL)
    1205   721005892 :     REDBLK_TEST(REDBLK_(compare)(node, &pool[node->REDBLK_RIGHT]) <= 0);
    1206             : 
    1207  1700674531 :   int err = REDBLK_(verify_private)(pool, &pool[node->REDBLK_LEFT], node, curblkcnt, correctblkcnt);
    1208  1700674531 :   if (err) return err;
    1209  1700674531 :   return REDBLK_(verify_private)(pool, &pool[node->REDBLK_RIGHT], node, curblkcnt, correctblkcnt);
    1210  1700674531 : }
    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   326608240 : REDBLK_IMPL_STATIC int REDBLK_(verify)(REDBLK_T * pool, REDBLK_T * root) {
    1218   326608240 :   REDBLK_TEST(pool[REDBLK_NIL].REDBLK_LEFT == REDBLK_NIL &&
    1219   326608240 :        pool[REDBLK_NIL].REDBLK_RIGHT == REDBLK_NIL &&
    1220   326608240 :        pool[REDBLK_NIL].REDBLK_COLOR == REDBLK_BLACK);
    1221             : 
    1222   326608240 :   if (!root || root == &pool[REDBLK_NIL])
    1223    10889448 :     return 0; // Trivially correct
    1224   315718792 :   REDBLK_TEST(root->REDBLK_COLOR == REDBLK_BLACK);
    1225             : 
    1226   315718792 :   ulong sz = REDBLK_(size)(pool, root);
    1227   315718792 :   REDBLK_TEST(sz + 1 == REDBLK_POOL_(used)(pool));
    1228             : 
    1229             :   // Compute the correct number of black nodes on a path
    1230   315718792 :   ulong blkcnt = 0;
    1231   315718792 :   REDBLK_T * node = root;
    1232  1047932168 :   while (node != &pool[REDBLK_NIL]) {
    1233   732213376 :     if (node->REDBLK_COLOR == REDBLK_BLACK)
    1234   582355261 :       ++blkcnt;
    1235   732213376 :     node = &pool[node->REDBLK_LEFT];
    1236   732213376 :   }
    1237             :   // Recursive check
    1238   315718792 :   return REDBLK_(verify_private)(pool, root, &pool[REDBLK_NIL], 0, blkcnt);
    1239             : 
    1240   315718792 : #undef REDBLK_TEST
    1241   315718792 : }
    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

Generated by: LCOV version 1.14