LCOV - code coverage report
Current view: top level - util/tmpl - fd_treap.c (source / functions) Hit Total Coverage
Test: cov.lcov Lines: 503 565 89.0 %
Date: 2025-07-01 05:00:49 Functions: 141 10171 1.4 %

          Line data    Source code
       1             : /* Generate prototypes, inlines and implementations for ultra high
       2             :    performance treaps.  A treap hybrid of a binary search tree and heap
       3             :    such that it will well-balanced on average statistically.
       4             : 
       5             :    It is not as well-balanced theoretically as more complex
       6             :    non-randomized balancing tree algorithms (e.g. red-black trees, AVL
       7             :    trees, etc).  But it is often better in practice as it is much
       8             :    simpler (i.e. amenable for ultra high performance and small code
       9             :    footprint implementation) and very adaptable (e.g. easy to tweak to
      10             :    support adaptive queries like a splay tree, etc).  Additionally,
      11             :    there are a bunch of tricks in the below to optimize this much
      12             :    further than textbook implementations (those tend to miss a lot of
      13             :    practical opportunities including eliminating the cost of random
      14             :    number generation during operations).
      15             : 
      16             :    This API is designed for ultra tight coupling with pools, maps, other
      17             :    treaps, etc.  Likewise, a treap can be persisted beyond the lifetime
      18             :    of creating process, used concurrently in many common operations,
      19             :    used inter-process, relocated in memory, naively
      20             :    serialized/deserialized, moved between hosts, supports index
      21             :    compression for cache and memory bandwidth efficiency, etc.
      22             : 
      23             :    Typical usage:
      24             : 
      25             :      struct myele {
      26             : 
      27             :        ... Each field below can be located arbitrarily in the struct
      28             : 
      29             :        ulong parent; // Technically "TREAP_IDX_T TREAP_PARENT;" (default is ulong parent), similarly for left, right, and prio.
      30             :        ulong left;   // parent, left and right managed by the treap when a myele is in the treap.  prio is constant while in a
      31             :        ulong right;  // treap.  Further, all these can be used arbitrarily when not in treap (this includes perhaps using an
      32             :        ulong prio;   // anonymous union and/or bit fields for even more flexibility).  Additional considerations for prio below.
      33             : 
      34             :        // if TREAP_OPTIMIZE_ITERATION is set to 1, the following two
      35             :        // fields are also needed:
      36             :        ulong next;  // Similarly to above, technically TREAP_IDX_T TREAP_NEXT, TREAP_PREV.  These fields are treap-managed when
      37             :        ulong prev;  // a myele is in the treap and can be used arbitrarily when not.
      38             : 
      39             : 
      40             :        ... Generally speaking, this treap implement is agnostic to how
      41             :        ... the user manages treap priorities.  The algorithmic costs
      42             :        ... below assume that priorities are random though.
      43             : 
      44             :        ... For stock usage cases, the most optimal handling of prio is
      45             :        ... to initialize the prio field exactly once when the myele
      46             :        ... storage is first created with random values and then leave it
      47             :        ... unchanged thereafter (and potentially reused by other APIs
      48             :        ... needing similar randomization).  This eliminates all
      49             :        ... overheads associated with random number generation during
      50             :        ... operation.  But this also means that prio field is not
      51             :        ... available for use when a myele is not in the treap.
      52             : 
      53             :        ... In other situations, the user might choose to generate random
      54             :        ... priorities dynamically (as it done in textbook
      55             :        ... implementations) and/or adjust element priorities on the fly
      56             :        ... to splay-tree-like adaptively optimize treap queries.
      57             : 
      58             :        ... To support potential future bulk operations (e.g. fast treap
      59             :        ... splits / joins), it is recommended that these random values
      60             :        ... exclude the largest possible value but this is not strictly
      61             :        ... required currently.
      62             : 
      63             :        ... Note that other kinds of objects can use these fields for
      64             :        ... their metadata needs to keep element metadata / cache
      65             :        ... footprint overheads minimal.  The only restriction is that
      66             :        ... they cannot concurrently use the same field.  E.g. a pool
      67             :        ... could use the "parent" field for its next pointer while
      68             :        ... multiple other _disjoint_ treaps of myele_t from the same
      69             :        ... pool can all use the same treap fields.
      70             : 
      71             :        ... Note that fields could be made into narrow bit fields if
      72             :        ... useful for additional memory, bandwidth and cache efficiency.
      73             :        ... In particular, for priorities, unbiased pseudo random coin
      74             :        ... flipping is used to break ties (a little priority can go a
      75             :        ... very long way practically).
      76             : 
      77             :        ... Arbitrary application fields mixed in here.  Power-of-2
      78             :        ... element sizes have good cache and indexing Feng Shui.
      79             : 
      80             :        char key[ KEY_MAX ]; // For demonstration purposes
      81             : 
      82             :      };
      83             : 
      84             :      typedef struct myele myele_t;
      85             : 
      86             :      #define TREAP_NAME      mytreap
      87             :      #define TREAP_T         myele_t
      88             :      #define TREAP_QUERY_T   char const *
      89             :      #define TREAP_CMP(q,e)  strcmp( q, e->key )
      90             :      #define TREAP_LT(e0,e1) (strcmp( e0->key, e1->key )<0)
      91             :      #include "fd_treap.c"
      92             : 
      93             :    will declare the following APIs as a header-only style library in the
      94             :    compilation unit:
      95             : 
      96             :      int mytreap_cmp( char const *    q,  myele_t const * e  ); // Provides TREAP_CMP
      97             :      int mytreap_lt ( myele_t const * e0, myele_t const * e1 ); // Provides TREAP_LT
      98             : 
      99             :      // mytreap_idx_null returns the element index used to represent
     100             :      // NULL, infinite lifetime.  mytreap_ele_null returns NULL,
     101             :      // infinite lifetime, for completeness, mytreap_ele_null_const is a
     102             :      // const-correct version, also for completeness.
     103             : 
     104             :      ulong           mytreap_idx_null      ( void );
     105             :      myele_t *       mytreap_ele_null      ( void );
     106             :      myele_t const * mytreap_ele_null_const( void );
     107             : 
     108             :      // mytreap_{idx,ele}_is_null returns i==mytreap_idx_null() / !e
     109             : 
     110             :      int mytreap_idx_is_null( ulong           i );
     111             :      int mytreap_ele_is_null( myele_t const * e );
     112             : 
     113             :      // mytreap_idx returns e's index.  Assumes e is a pointer in the
     114             :      // caller's local address space to a pool element or is NULL.
     115             :      // Return will be in [0,ele_max) or mytreap_idx_null().  Lifetime
     116             :      // is the element storage lifetime.  mytreap_idx_fast is the same
     117             :      // assumes e is not NULL.  pool is a pointer in the caller's
     118             :      // address space to the ele_max linearly addressable storage region
     119             :      // backing the treap.
     120             : 
     121             :      ulong mytreap_idx     ( myele_t const * e, myele_t const * pool );
     122             :      ulong mytreap_idx_fast( myele_t const * e, myele_t const * pool );
     123             : 
     124             :      // mytreap_ele returns a pointer in the caller's address space to
     125             :      // element idx.  Assumes idx is in [0,ele_max) or is
     126             :      // mytreap_idx_null().  Return pointer lifetime is ele's local
     127             :      // lifetime.  mytreap_ele_fast is the same but assumes idx is not
     128             :      // mytreap_idx_null().  mytreap_ele[_fast]_const is a const correct
     129             :      // version.  pool is a pointer in the caller's address space to the
     130             :      // ele_max linearly addressable storage region backing the treap.
     131             : 
     132             :      myele_t * mytreap_ele     ( ulong i, myele_t * pool );
     133             :      myele_t * mytreap_ele_fast( ulong i, myele_t * pool );
     134             : 
     135             :      myele_t const * mytreap_ele_const     ( ulong i, myele_t const * pool );
     136             :      myele_t const * mytreap_ele_fast_const( ulong i, myele_t const * pool );
     137             : 
     138             :      // mytreap_seed is a helper that sets pool[i].prio for i in
     139             :      // [0,ele_max) to a random value in [0,PRIO_MAX) (yes half-open)
     140             :      // where PRIO_MAX is the largest possible value representable in
     141             :      // the prio field.  Uses seed (arbitrary) to select a simple hash
     142             :      // based random number of sequence for prio.
     143             :      //
     144             :      // If an application wants to set this as optimally and securely as
     145             :      // possible, it should seed pool[i].prio with a cryptographic
     146             :      // secure uniform random permutation of [0,ele_max) and/or
     147             :      // dynamically manage the prio field as described above.
     148             : 
     149             :      void mytreap_seed( myele_t * pool, ulong ele_max, ulong seed );
     150             : 
     151             :      // mytreap_{align,footprint} returns the alignment and footprint
     152             :      // needed for a memory region to hold the state of a mytreap of
     153             :      // elements from a linearly addressable ele_max element storage.
     154             :      // align will be an integer power-of-two and footprint will be a
     155             :      // multiple of align.  footprint will non-zero on a success and 0
     156             :      // on failure (silent) (e.g. ele_max too large for the specified
     157             :      // TREAP_IDX_T).  mytreap_t is stack declaration, data segment
     158             :      // declaration, heap allocation and stack allocation friendly.
     159             :      // Even though footprint is passed ele_max, the footprint is a
     160             :      // small O(1) spatial overhead.
     161             :      //
     162             :      // mytreap_new formats a memory region with the appropriate
     163             :      // alignment and footprint whose first byte in the caller's address
     164             :      // space is pointed to by shmem as a mytreap for elements from a
     165             :      // linearly addressable ele_max element storage.  Returns shmem on
     166             :      // success and NULL on failure (log details, e.g. ele_max is too
     167             :      // large for the width of the TREAP_IDX_T specified).  Caller is
     168             :      // not joined on return.  The treap will be empty.
     169             :      //
     170             :      // mytreap_join joins a mytreap.  Assumes shtreap points at a
     171             :      // memory region formatted as a mytreap in the caller's address
     172             :      // space.  Returns a handle to the caller's local join on success
     173             :      // and NULL on failure (logs details).
     174             :      //
     175             :      // mytreap_leave leaves a mytreap.  Assumes join points to a
     176             :      // current local join.  Returns shtreap used on join and NULL on
     177             :      // failure (logs details).
     178             :      //
     179             :      // mytreap_delete unformats a memory region used as a mytreap.
     180             :      // Assumes shtreap points to a memory region in the caller's local
     181             :      // address space formatted as a mytreap, that there are no joins to
     182             :      // the mytreap and that any application side cleanups have been
     183             :      // done.  Returns shtreap on success and NULL on failure (logs
     184             :      // details).
     185             : 
     186             :      ulong       mytreap_align    ( void                              );
     187             :      ulong       mytreap_footprint( ulong       ele_max               );
     188             :      void *      mytreap_new      ( void *      shmem,  ulong ele_max );
     189             :      mytreap_t * mytreap_join     ( void *      shtreap               );
     190             :      void *      mytreap_leave    ( mytreap_t * treap                 );
     191             :      void *      mytreap_delete   ( void *      shtreap               );
     192             : 
     193             :      // mytreap_ele_max gives the maximum number of elements the underlying
     194             :      // linearly addressable storage can support
     195             :      // mytreap_ele_cnt gives the current number of elements in the treap
     196             :      // mytreap_{ele_max,ele_cnt} assumes treap is a current local join.
     197             :      // These might be deprecated in the future.
     198             : 
     199             :      ulong mytreap_ele_max( mytreap_t const * treap );
     200             :      ulong mytreap_ele_cnt( mytreap_t const * treap );
     201             : 
     202             :      // mytreap_idx_query finds where q is stored in the treap.  Assumes
     203             :      // treap is a current local join and pool points in the caller's
     204             :      // address space to the ele_max element storage containing the
     205             :      // treap elements.  Returns [0,ele_max) on success and
     206             :      // mytreap_idx_null() on failure.  Lifetime of the returned idx is
     207             :      // the lesser of until it is removed or the underlying element
     208             :      // storage.  mytreap_ele_query is the same but returns the location
     209             :      // in the caller's address space of the found element on success
     210             :      // and NULL on failure (lifetime of the returned pointer is until
     211             :      // ele is removed or ele's local lifetime).  If there are multiple
     212             :      // elements matching q, this returns an arbitrary one of them.
     213             :      // mytreap_ele_query_const is a const correct version.
     214             :      //
     215             :      // These operations have HPC implementations and are O(lg N)
     216             :      // average with an ultra high probability of having a small
     217             :      // coefficient (i.e. close to algorithmically optimal trees).
     218             : 
     219             :      ulong           mytreap_idx_query      ( mytreap_t const * treap, char const * q, myele_t const * pool );
     220             :      myele_t *       mytreap_ele_query      ( mytreap_t *       treap, char const * q, myele_t *       pool );
     221             :      myele_t const * mytreap_ele_query_const( mytreap_t const * treap, char const * q, myele_t const * pool );
     222             : 
     223             :      // my_treap_idx_ge returns the index of the smallest element
     224             :      // in the treap that is not less than q. If no such element exists,
     225             :      // it returns idx_null
     226             : 
     227             :      ulong mytreap_idx_ge( mytreap_t const * treap, TREAP_QUERY_T * q, myele_t const * pool );
     228             : 
     229             :      // mytreap_idx_{insert,remove} inserts / removes element n/d into
     230             :      // the treap and returns treap.  Assumes treap is a current local
     231             :      // join, pool points in the caller's address space to the ele_max
     232             :      // element storage used for treap elements, n/d are in [0,ele_max),
     233             :      // n/d are currently out of / in the treap.  Given these
     234             :      // assumptions, these cannot fail.
     235             :      //
     236             :      // For insert, n's query and prio fields should already be
     237             :      // populated (i.e. TREAP_LT( ele+n, ele+i ) should return valid
     238             :      // results before this is called and prio should be a suitable
     239             :      // value as described above.  On return, n and n's queries will be
     240             :      // in the treap.  n's left, right, parent, prio and/or queries
     241             :      // should not be modified while n is in the treap.  Further, the
     242             :      // caller should not assume n's left, right or parent values are
     243             :      // stable while n is in the treap.  The treap does not care about
     244             :      // any other fields and these can be modified by the user as
     245             :      // necessary.
     246             :      //
     247             :      // When inserting an element that compares equal (i.e.
     248             :      // TREAP_LT( x, y )==0 and TREAP_LT( y, x )==0), the newly inserted
     249             :      // element is treated as if being epsilon larger than all existing
     250             :      // equal elements.  This means that iterating in forward order will
     251             :      // iterate over equal elements in "time" order, with the one
     252             :      // inserted first returned first.
     253             :      //
     254             :      // For remove, on return d and d's queries are no longer in the
     255             :      // treap.  The caller is free to modify all fields of d as
     256             :      // necessary.
     257             :      //
     258             :      // mytreap_ele_{insert,remove} are the same but n and d point in
     259             :      // the caller's local address space the element to insert / remove.
     260             :      //
     261             :      // These operations have HPC implementations and are O(lg N)
     262             :      // average with an ultra high probability of having a small
     263             :      // coefficient (i.e. close to algorithmically optimal trees).
     264             : 
     265             :      mytreap_t * mytreap_idx_insert( mytreap_t * treap, ulong     n, myele_t * pool );
     266             :      mytreap_t * mytreap_idx_remove( mytreap_t * treap, ulong     d, myele_t * pool );
     267             : 
     268             :      mytreap_t * mytreap_ele_insert( mytreap_t * treap, myele_t * n, myele_t * pool );
     269             :      mytreap_t * mytreap_ele_remove( mytreap_t * treap, myele_t * d, myele_t * pool );
     270             : 
     271             :      // mytreap_fwd_iter_{init,done,next,idx,ele,ele_const} provide an
     272             :      // in-order iterator from smallest to largest value.  Typical
     273             :      // usage:
     274             :      //
     275             :      //  for( mytreap_fwd_iter_t iter = mytreap_fwd_iter_init( treap, pool );
     276             :      //       !mytreap_fwd_iter_done( iter );
     277             :      //       iter = mytreap_fwd_iter_next( iter, pool ) ) {
     278             :      //     ulong i = mytreap_fwd_iter_idx( iter );
     279             :      //     ... or myele_t *       e = mytreap_fwd_iter_ele      ( iter, pool );
     280             :      //     ... or myele_t const * e = mytreap_fwd_iter_ele_const( iter, pool );
     281             :      //
     282             :      //     ... process i (or e) here
     283             :      //
     284             :      //     ... Do not remove the element the iterator is currently
     285             :      //     ... pointing to, and do not change the element's parent,
     286             :      //     ... left, right, prio or queries here.  It is fine to run
     287             :      //     ... queries and other iterations concurrently.  Other fields
     288             :      //     ... are free to modify (from the treap's POV, the
     289             :      //     ... application manages concurrency for other fields).
     290             :      //  }
     291             :      //
     292             :      // pool is a pointer in the caller's address space to the ele_max
     293             :      // linearly addressable storage region backing the treap.
     294             : 
     295             :      typedef ... mytreap_fwd_iter_t;
     296             : 
     297             :      mytreap_fwd_iter_t mytreap_fwd_iter_init     ( mytreap_t const * treap, myele_t const * pool );
     298             :      int                mytreap_fwd_iter_done     ( mytreap_fwd_iter_t iter                       );
     299             :      mytreap_fwd_iter_t mytreap_fwd_iter_next     ( mytreap_fwd_iter_t iter, myele_t const * pool );
     300             :      ulong              mytreap_fwd_iter_idx      ( mytreap_fwd_iter_t iter                       );
     301             :      myele_t *          mytreap_fwd_iter_ele      ( mytreap_fwd_iter_t iter, myele_t *       pool );
     302             :      myele_t const *    mytreap_fwd_iter_ele_const( mytreap_fwd_iter_t iter, myele_t const * pool );
     303             : 
     304             :      // mytreap_rev_iter_{init,done,next,idx,ele,ele_const} is the same
     305             :      // but used when iterating from largest to smallest.
     306             : 
     307             :      typedef ... mytreap_rev_iter_t;
     308             : 
     309             :      mytreap_rev_iter_t mytreap_rev_iter_init     ( mytreap_t const * treap, myele_t const * pool );
     310             :      int                mytreap_rev_iter_done     ( mytreap_rev_iter_t iter                       );
     311             :      mytreap_rev_iter_t mytreap_rev_iter_next     ( mytreap_rev_iter_t iter, myele_t const * pool );
     312             :      ulong              mytreap_rev_iter_idx      ( mytreap_rev_iter_t iter                       );
     313             :      myele_t *          mytreap_rev_iter_ele      ( mytreap_rev_iter_t iter, myele_t *       pool );
     314             :      myele_t const *    mytreap_rev_iter_ele_const( mytreap_rev_iter_t iter, myele_t const * pool );
     315             : 
     316             :      // mytreap_merge merges two treaps backed by the same pool into a
     317             :      // single treap.  If all keys in treap_a and treap_b are distinct,
     318             :      // merge is equivalent to removing each element from treap_b and
     319             :      // inserting it into treap_a, but merging the heaps is
     320             :      // asymptotically slightly better.  If there are some duplicate
     321             :      // elements, they may be interleaved arbitrarily.  Returns treap_a,
     322             :      // which now additionally contains the elements from treap_b.
     323             :      // Requires that the treap does not use the maximum priority
     324             :      // element (see the note above about PRIO_MAX).
     325             : 
     326             :      mytreap * mytreap_merge( mytreap * treap_a, mytreap * treap_b, myele_t * pool );
     327             : 
     328             :      // mytreap_verify returns 0 if the mytreap is not obviously corrupt
     329             :      // or a -1 (i.e. ERR_INVAL) if it is (logs details).  treap is
     330             :      // current local join to a mytreap.  pool is a pointer in the
     331             :      // caller's address space to the ele_max linearly addressable
     332             :      // storage region backing the treap.
     333             : 
     334             :      int mytreap_verify( mytreap_t const * treap, myele_t const * pool );
     335             : 
     336             :      // IMPORTANT SAFETY TIP!  queries and iteration can be done
     337             :      // concurrently by multiple threads distributed arbitrarily over
     338             :      // multiple processes provided there are no concurrent insert /
     339             :      // remove operations on the treap and the application manages
     340             :      // concurrency for fields not managed by the treap.
     341             : 
     342             :    You can do this as often as you like within a compilation unit to get
     343             :    different types of treaps.  Variants exist for making separate headers
     344             :    and implementations for doing libraries and handling multiple
     345             :    compilation units.  Additional options exist as detailed below. */
     346             : 
     347             : /* TREAP_NAME gives the API prefix to use */
     348             : 
     349             : #ifndef TREAP_NAME
     350             : #error "Define TREAP_NAME"
     351             : #endif
     352             : 
     353             : /* TREAP_T is the treap element type */
     354             : 
     355             : #ifndef TREAP_T
     356             : #error "Define TREAP_T"
     357             : #endif
     358             : 
     359             : /* TREAP_QUERY_T is the type that is passed to the query function */
     360             : 
     361             : #ifndef TREAP_QUERY_T
     362             : #error "Define TREAP_QUERY_T"
     363             : #endif
     364             : 
     365             : /* TREAP_CMP compares a TREAP_QUERY_T q with an element e's query
     366             :    fields and returns a negative/zero/positive int if q is less
     367             :    than/equal/greater than element e's query fields.  Should be a pure
     368             :    function. */
     369             : 
     370             : #ifndef TREAP_CMP
     371             : #error "Define TREAP_CMP"
     372             : #endif
     373             : 
     374             : /* TREAP_LT returns 1 if the element e0's query fields are strictly less
     375             :    element e1's query fields and 0 otherwise.  Should be a pure
     376             :    function. */
     377             : 
     378             : #ifndef TREAP_LT
     379             : #error "Define TREAP_LT"
     380             : #endif
     381             : 
     382             : /* TREAP_IDX_T is the type used for the fields in the TREAP_T.  Should
     383             :    be a primitive unsigned integer type.  Defaults to ulong.  A treap
     384             :    can't use element memory regions that contain more than the maximum
     385             :    value that can be represented by a TREAP_IDX_T. */
     386             : 
     387             : #ifndef TREAP_IDX_T
     388   172417260 : #define TREAP_IDX_T ulong
     389             : #endif
     390             : 
     391             : /* TREAP_{PARENT,LEFT,RIGHT,PRIO} is the name the treap element parent /
     392             :    left / right / prio fields.  Defaults to parent / left / right /
     393             :    prio. */
     394             : 
     395             : #ifndef TREAP_PARENT
     396   135458223 : #define TREAP_PARENT parent
     397             : #endif
     398             : 
     399             : #ifndef TREAP_LEFT
     400   120109520 : #define TREAP_LEFT left
     401             : #endif
     402             : 
     403             : #ifndef TREAP_RIGHT
     404    93135258 : #define TREAP_RIGHT right
     405             : #endif
     406             : 
     407             : #ifndef TREAP_PRIO
     408    73184865 : #define TREAP_PRIO prio
     409             : #endif
     410             : 
     411             : /* TREAP_OPTIMIZE_ITERATION controls a space/time tradeoff: when
     412             :    TREAP_OPTIMIZE_ITERATION is set to 1, each element has two additional
     413             :    fields and insert and delete take slightly longer.  However, in
     414             :    return, iteration in either direction is substantially faster.  This
     415             :    works by essentially threading a doubly-linked list through elements
     416             :    in iteration order. The default is sets this to 0, meaning that the
     417             :    next and prev fields are not required. */
     418             : 
     419             : #ifndef TREAP_OPTIMIZE_ITERATION
     420             : #define TREAP_OPTIMIZE_ITERATION 0
     421             : #endif
     422             : 
     423             : #if TREAP_OPTIMIZE_ITERATION
     424             : # ifndef  TREAP_NEXT
     425    81055589 : #   define TREAP_NEXT next
     426             : # endif
     427             : # ifndef  TREAP_PREV
     428    78256353 : #   define TREAP_PREV prev
     429             : # endif
     430             : #endif
     431             : 
     432             : /* TREAP_IMPL_STYLE controls what this template should emit.
     433             :    0 - local use only
     434             :    1 - library header
     435             :    2 - library implementation */
     436             : 
     437             : #ifndef TREAP_IMPL_STYLE
     438             : #define TREAP_IMPL_STYLE 0
     439             : #endif
     440             : 
     441             : /* Implementation *****************************************************/
     442             : 
     443             : #if TREAP_IMPL_STYLE==0
     444             : #define TREAP_STATIC static FD_FN_UNUSED
     445             : #else
     446             : #define TREAP_STATIC
     447             : #endif
     448             : 
     449  4030073463 : #define TREAP_IDX_NULL           ((ulong)(TREAP_IDX_T)(~0UL))
     450  3810700951 : #define TREAP_IDX_IS_NULL( idx ) ((idx)==TREAP_IDX_NULL)
     451             : 
     452   711901423 : #define TREAP_(n) FD_EXPAND_THEN_CONCAT3(TREAP_NAME,_,n)
     453             : 
     454             : /* Verification logs details on failure.  The rest only needs fd_bits.h
     455             :    (consider making logging a compile time option). */
     456             : 
     457             : #include "../log/fd_log.h"
     458             : 
     459             : #if TREAP_IMPL_STYLE!=2 /* need structures, prototypes and inlines */
     460             : 
     461             : /* structures */
     462             : 
     463             : /* TODO: consider eliminating ele_cnt and maybe ele_max fields (less overhead,
     464             :    faster bulk ops, concurrency options, simpler constructors, etc) */
     465             : 
     466             : struct TREAP_(private) {
     467             :   ulong       ele_max; /* Maximum number of elements in underlying storage, in [0,TREAP_IDX_NULL] */
     468             :   ulong       ele_cnt; /* Current number of elements in treap, in [0,ele_max] */
     469             : # if TREAP_OPTIMIZE_ITERATION
     470             :   TREAP_IDX_T first;   /* Index of the left-most treap element, in [0,ele_max) or TREAP_IDX_NULL */
     471             :   TREAP_IDX_T last;    /* Index of the right-most treap element, in [0,ele_max) or TREAP_IDX_NULL */
     472             : # endif
     473             :   TREAP_IDX_T root;    /* Index of the root treap element, in [0,ele_max) or TREAP_IDX_NULL */
     474             : };
     475             : 
     476             : typedef struct TREAP_(private) TREAP_(t);
     477             : 
     478             : typedef ulong TREAP_(fwd_iter_t);
     479             : typedef ulong TREAP_(rev_iter_t);
     480             : 
     481             : FD_PROTOTYPES_BEGIN
     482             : 
     483             : /* prototypes */
     484             : 
     485             : TREAP_STATIC void TREAP_(seed)( TREAP_T * pool, ulong ele_max, ulong seed );
     486             : 
     487             : TREAP_STATIC FD_FN_CONST ulong       TREAP_(align)    ( void                              );
     488             : TREAP_STATIC FD_FN_CONST ulong       TREAP_(footprint)( ulong       ele_max               );
     489             : TREAP_STATIC /**/        void *      TREAP_(new)      ( void *      shmem,  ulong ele_max );
     490             : TREAP_STATIC /**/        TREAP_(t) * TREAP_(join)     ( void *      shtreap               );
     491             : TREAP_STATIC /**/        void *      TREAP_(leave)    ( TREAP_(t) * treap                 );
     492             : TREAP_STATIC /**/        void *      TREAP_(delete)   ( void *      shtreap               );
     493             : 
     494             : TREAP_STATIC FD_FN_PURE ulong TREAP_(idx_query)( TREAP_(t) const * treap, TREAP_QUERY_T q, TREAP_T const * pool );
     495             : TREAP_STATIC FD_FN_PURE ulong TREAP_(idx_ge)( TREAP_(t) const * treap, TREAP_QUERY_T q, TREAP_T const * pool );
     496             : 
     497             : TREAP_STATIC TREAP_(t) * TREAP_(idx_insert)( TREAP_(t) * treap, ulong n, TREAP_T * pool );
     498             : TREAP_STATIC TREAP_(t) * TREAP_(idx_remove)( TREAP_(t) * treap, ulong d, TREAP_T * pool );
     499             : 
     500             : TREAP_STATIC FD_FN_PURE TREAP_(fwd_iter_t) TREAP_(fwd_iter_init)( TREAP_(t) const * treap, TREAP_T const * pool );
     501             : TREAP_STATIC FD_FN_PURE TREAP_(rev_iter_t) TREAP_(rev_iter_init)( TREAP_(t) const * treap, TREAP_T const * pool );
     502             : 
     503             : TREAP_STATIC FD_FN_PURE TREAP_(fwd_iter_t) TREAP_(fwd_iter_next)( TREAP_(fwd_iter_t) i, TREAP_T const * pool );
     504             : TREAP_STATIC FD_FN_PURE TREAP_(rev_iter_t) TREAP_(rev_iter_next)( TREAP_(rev_iter_t) i, TREAP_T const * pool );
     505             : 
     506             : TREAP_STATIC TREAP_(t) * TREAP_(merge)( TREAP_(t) * treap_a, TREAP_(t) * treap_b, TREAP_T * pool );
     507             : 
     508             : TREAP_STATIC int TREAP_(verify)( TREAP_(t) const * treap, TREAP_T const * pool );
     509             : 
     510             : /* inlines */
     511             : 
     512   163228254 : FD_FN_PURE static inline int TREAP_(cmp)( TREAP_QUERY_T   q,  TREAP_T const * e  ) { return TREAP_CMP( q, e );  }
     513  1410940277 : FD_FN_PURE static inline int TREAP_(lt) ( TREAP_T const * e0, TREAP_T const * e1 ) { return TREAP_LT( e0, e1 ); }
     514             : 
     515      679601 : FD_FN_CONST static inline ulong           TREAP_(idx_null)      ( void ) { return TREAP_IDX_NULL; }
     516           3 : FD_FN_CONST static inline TREAP_T *       TREAP_(ele_null)      ( void ) { return NULL;           }
     517           3 : FD_FN_CONST static inline TREAP_T const * TREAP_(ele_null_const)( void ) { return NULL;           }
     518             : 
     519     3571659 : FD_FN_CONST static inline int TREAP_(idx_is_null)( ulong           i ) { return TREAP_IDX_IS_NULL( i ); }
     520        1536 : FD_FN_CONST static inline int TREAP_(ele_is_null)( TREAP_T const * e ) { return !e;                     }
     521             : 
     522             : FD_FN_CONST static inline ulong
     523             : TREAP_(idx)( TREAP_T const * e,
     524    12008712 :              TREAP_T const * pool ) {
     525    12008712 :   return fd_ulong_if( !!e, (ulong)(e - pool), TREAP_IDX_NULL );
     526    12008712 : }
     527             : 
     528             : FD_FN_CONST static inline TREAP_T *
     529             : TREAP_(ele)( ulong     i,
     530         768 :              TREAP_T * pool ) {
     531         768 :   return fd_ptr_if( !TREAP_IDX_IS_NULL( i ), pool + i, NULL );
     532         768 : }
     533             : 
     534             : FD_FN_CONST static inline TREAP_T const *
     535             : TREAP_(ele_const)( ulong           i,
     536         768 :                    TREAP_T const * pool ) {
     537         768 :   return fd_ptr_if( !TREAP_IDX_IS_NULL( i ), pool + i, NULL );
     538         768 : }
     539             : 
     540             : FD_FN_CONST static inline ulong
     541             : TREAP_(idx_fast)( TREAP_T const * e,
     542        1530 :                   TREAP_T const * pool ) {
     543        1530 :   return (ulong)(e - pool);
     544        1530 : }
     545             : 
     546         765 : FD_FN_CONST static inline TREAP_T *       TREAP_(ele_fast)      ( ulong i, TREAP_T *       pool ) { return pool + i; }
     547         765 : FD_FN_CONST static inline TREAP_T const * TREAP_(ele_fast_const)( ulong i, TREAP_T const * pool ) { return pool + i; }
     548             : 
     549     6051756 : FD_FN_PURE static inline ulong TREAP_(ele_max)( TREAP_(t) const * treap ) { return treap->ele_max; }
     550    13380780 : FD_FN_PURE static inline ulong TREAP_(ele_cnt)( TREAP_(t) const * treap ) { return treap->ele_cnt; }
     551             : 
     552             : FD_FN_PURE static inline TREAP_T *
     553             : TREAP_(ele_query)( TREAP_(t) const * treap,
     554             :                    TREAP_QUERY_T     q,
     555     6003600 :                    TREAP_T *         pool ) {
     556     6003600 :   ulong i = TREAP_(idx_query)( treap, q, pool );
     557     6003600 :   return fd_ptr_if( !TREAP_IDX_IS_NULL( i ), pool + i, NULL );
     558     6003600 : }
     559             : 
     560             : FD_FN_PURE static inline TREAP_T const *
     561             : TREAP_(ele_query_const)( TREAP_(t) const * treap,
     562             :                          TREAP_QUERY_T     q,
     563     6003588 :                          TREAP_T const *   pool ) {
     564     6003588 :   ulong i = TREAP_(idx_query)( treap, q, pool );
     565     6003588 :   return fd_ptr_if( !TREAP_IDX_IS_NULL( i ), pool + i, NULL );
     566     6003588 : }
     567             : 
     568             : static inline TREAP_(t) *
     569             : TREAP_(ele_insert)( TREAP_(t) * treap,
     570             :                     TREAP_T *   e,
     571    30178455 :                     TREAP_T *   pool ) {
     572    30178455 :   return TREAP_(idx_insert)( treap, (ulong)(e - pool), pool );
     573    30178455 : }
     574             : 
     575             : static inline TREAP_(t) *
     576             : TREAP_(ele_remove)( TREAP_(t) * treap,
     577             :                     TREAP_T *   e,
     578    17062439 :                     TREAP_T *   pool ) {
     579    17062439 :   return TREAP_(idx_remove)( treap, (ulong)(e - pool), pool );
     580    17062439 : }
     581             : 
     582   184685473 : FD_FN_CONST static inline int             TREAP_(fwd_iter_done)     ( TREAP_(fwd_iter_t) i ) { return TREAP_IDX_IS_NULL( i ); }
     583    94721799 : FD_FN_CONST static inline ulong           TREAP_(fwd_iter_idx)      ( TREAP_(fwd_iter_t) i                       ) { return i;        }
     584   138345337 : FD_FN_CONST static inline TREAP_T *       TREAP_(fwd_iter_ele)      ( TREAP_(fwd_iter_t) i, TREAP_T *       pool ) { return pool + i; }
     585    94643556 : FD_FN_CONST static inline TREAP_T const * TREAP_(fwd_iter_ele_const)( TREAP_(fwd_iter_t) i, TREAP_T const * pool ) { return pool + i; }
     586             : 
     587   123113326 : FD_FN_CONST static inline int             TREAP_(rev_iter_done)     ( TREAP_(rev_iter_t) i ) { return TREAP_IDX_IS_NULL( i ); }
     588    94767330 : FD_FN_CONST static inline ulong           TREAP_(rev_iter_idx)      ( TREAP_(rev_iter_t) i                       ) { return i;        }
     589   119359198 : FD_FN_CONST static inline TREAP_T *       TREAP_(rev_iter_ele)      ( TREAP_(rev_iter_t) i, TREAP_T *       pool ) { return pool + i; }
     590    94765287 : FD_FN_CONST static inline TREAP_T const * TREAP_(rev_iter_ele_const)( TREAP_(rev_iter_t) i, TREAP_T const * pool ) { return pool + i; }
     591             : 
     592             : FD_PROTOTYPES_END
     593             : 
     594             : #endif
     595             : 
     596             : #if TREAP_IMPL_STYLE!=1 /* need implementations */
     597             : 
     598             : TREAP_STATIC void
     599             : TREAP_(seed)( TREAP_T * pool,
     600             :               ulong     ele_max,
     601        6357 :               ulong     seed ) {
     602     5583123 :   for( ulong ele_idx=0UL; ele_idx<ele_max; ele_idx++ ) {
     603     5576766 :     ulong r = fd_ulong_hash( ele_idx ^ seed ) & TREAP_IDX_NULL;
     604     5576766 :     pool[ ele_idx ].TREAP_PRIO = (TREAP_IDX_T)(r - (ulong)(r==TREAP_IDX_NULL));
     605     5576766 :   }
     606        6357 : }
     607             : 
     608             : TREAP_STATIC FD_FN_CONST ulong
     609     2667978 : TREAP_(align)( void ) {
     610     2667978 :   return alignof(TREAP_(t));
     611     2667978 : }
     612             : 
     613             : TREAP_STATIC FD_FN_CONST ulong
     614          66 : TREAP_(footprint)( ulong ele_max ) {
     615          66 :   if( FD_UNLIKELY( ele_max>TREAP_IDX_NULL ) ) return 0UL;
     616          63 :   return sizeof(TREAP_(t));
     617          66 : }
     618             : 
     619             : TREAP_STATIC void *
     620             : TREAP_(new)( void * shmem,
     621     1345671 :              ulong  ele_max ) {
     622     1345671 :   if( !shmem ) {
     623           3 :     FD_LOG_WARNING(( "NULL shmem" ));
     624           3 :     return NULL;
     625           3 :   }
     626             : 
     627     1345668 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, TREAP_(align)() ) ) ) {
     628           3 :     FD_LOG_WARNING(( "misaligned shmem" ));
     629           3 :     return NULL;
     630           3 :   }
     631             : 
     632     1345665 :   if( FD_UNLIKELY( ele_max>TREAP_IDX_NULL ) ) {
     633           3 :     FD_LOG_WARNING(( "ele_max too large" ));
     634           3 :     return NULL;
     635           3 :   }
     636             : 
     637     1345662 :   TREAP_(t) * treap = (TREAP_(t) *)shmem;
     638             : 
     639     1345662 :   treap->ele_max = ele_max;
     640     1345662 :   treap->ele_cnt = 0UL;
     641     1345662 :   treap->root    = (TREAP_IDX_T)TREAP_IDX_NULL;
     642             : 
     643             : # if TREAP_OPTIMIZE_ITERATION
     644     1345554 :   treap->first   = (TREAP_IDX_T)TREAP_IDX_NULL;
     645     1345554 :   treap->last    = (TREAP_IDX_T)TREAP_IDX_NULL;
     646             : # endif
     647             : 
     648     1345662 :   return treap;
     649     1345665 : }
     650             : 
     651             : TREAP_STATIC TREAP_(t) *
     652     1293024 : TREAP_(join)( void * shtreap ) {
     653     1293024 :   if( FD_UNLIKELY( !shtreap ) ) {
     654           3 :     FD_LOG_WARNING(( "NULL shtreap" ));
     655           3 :     return NULL;
     656           3 :   }
     657             : 
     658     1293021 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shtreap, TREAP_(align)() ) ) ) {
     659           3 :     FD_LOG_WARNING(( "misaligned shtreap" ));
     660           3 :     return NULL;
     661           3 :   }
     662             : 
     663     1293018 :   return (TREAP_(t) *)shtreap;
     664     1293021 : }
     665             : 
     666             : TREAP_STATIC void *
     667       29202 : TREAP_(leave)( TREAP_(t) * treap ) {
     668       29202 :   if( FD_UNLIKELY( !treap ) ) {
     669           3 :     FD_LOG_WARNING(( "NULL treap" ));
     670           3 :     return NULL;
     671           3 :   }
     672             : 
     673       29199 :   return (void *)treap;
     674       29202 : }
     675             : 
     676             : TREAP_STATIC void *
     677       29205 : TREAP_(delete)( void * shtreap ) {
     678       29205 :   if( FD_UNLIKELY( !shtreap ) ) {
     679           3 :     FD_LOG_WARNING(( "NULL shtreap" ));
     680           3 :     return NULL;
     681           3 :   }
     682             : 
     683       29202 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shtreap, TREAP_(align)() ) ) ) {
     684           3 :     FD_LOG_WARNING(( "misaligned shtreap" ));
     685           3 :     return NULL;
     686           3 :   }
     687             : 
     688       29199 :   return shtreap;
     689       29202 : }
     690             : 
     691             : TREAP_STATIC ulong
     692             : TREAP_(idx_ge)( TREAP_(t) const * treap,
     693             :                 TREAP_QUERY_T     q,
     694     6508536 :                 TREAP_T const *   pool ) {
     695     6508536 :   ulong i         = (ulong)treap->root;
     696     6508536 :   ulong candidate = TREAP_IDX_NULL;
     697             : 
     698    73436187 :   while( FD_LIKELY( !TREAP_IDX_IS_NULL(i) ) ) {
     699    69871479 :     ulong l = (ulong)pool[i].TREAP_LEFT;
     700    69871479 :     ulong r = (ulong)pool[i].TREAP_RIGHT;
     701    69871479 :     int   c = TREAP_(cmp)( q, pool + i );
     702    69871479 :     if( FD_UNLIKELY( !c ) ) {
     703     2943828 :       candidate = i;
     704     2943828 :       break;
     705     2943828 :     }
     706             : 
     707    66927651 :     candidate = fd_ulong_if( c<0, i, candidate );
     708    66927651 :     i         = fd_ulong_if( c<0, l, r         );
     709    66927651 :   }
     710     6508536 :   return candidate;
     711     6508536 : }
     712             : 
     713             : TREAP_STATIC ulong
     714             : TREAP_(idx_query)( TREAP_(t) const * treap,
     715             :                    TREAP_QUERY_T     q,
     716    18010776 :                    TREAP_T const *   pool ) {
     717    18010776 :   ulong i = (ulong)treap->root;
     718   102734724 :   while( FD_LIKELY( !TREAP_IDX_IS_NULL( i ) ) ) { /* Optimize for found */
     719    93356775 :     ulong l = (ulong)pool[ i ].TREAP_LEFT;
     720    93356775 :     ulong r = (ulong)pool[ i ].TREAP_RIGHT;
     721    93356775 :     int   c = TREAP_(cmp)( q, pool + i );
     722    93356775 :     if( FD_UNLIKELY( !c ) ) break; /* Optimize for larger treaps */
     723    84723948 :     i = fd_ulong_if( c<0, l, r );
     724    84723948 :   }
     725    18010776 :   return i;
     726    18010776 : }
     727             : 
     728             : TREAP_STATIC TREAP_(t) *
     729             : TREAP_(idx_insert)( TREAP_(t) * treap,
     730             :                     ulong       n,
     731    41050314 :                     TREAP_T *   pool ) {
     732             : 
     733             : # if FD_TMPL_USE_HANDHOLDING
     734             :   if( FD_UNLIKELY( n>=treap->ele_max              ) ) FD_LOG_CRIT(( "index out of bounds" ));
     735             :   if( FD_UNLIKELY( treap->ele_cnt>=treap->ele_max ) ) FD_LOG_CRIT(( "treap full" ));
     736             : # endif
     737             : 
     738             :   /* Find leaf where to insert n */
     739             : 
     740    41050314 :   TREAP_IDX_T * _p_child = &treap->root;
     741             : # if TREAP_OPTIMIZE_ITERATION
     742    34419330 :   TREAP_IDX_T * _p_pnext = &treap->first; /* pointer to prev node's next idx */
     743    34419330 :   TREAP_IDX_T * _p_nprev = &treap->last;  /* pointer to next node's prev idx */
     744             : # endif
     745             : 
     746    41050314 :   ulong i = TREAP_IDX_NULL;
     747   520211630 :   for(;;) {
     748   520211630 :     ulong j = (ulong)*_p_child;
     749   520211630 :     if( FD_UNLIKELY( TREAP_IDX_IS_NULL( j ) ) ) break; /* Optimize for large treap */
     750   479161316 :     i = j;
     751   479161316 :     int lt = TREAP_(lt)( pool + n, pool + i );
     752   479161316 :     _p_child = fd_ptr_if( lt, &pool[ i ].TREAP_LEFT, &pool[ i ].TREAP_RIGHT );
     753             : #   if TREAP_OPTIMIZE_ITERATION
     754   409088867 :     _p_pnext = fd_ptr_if( lt, _p_pnext,              &pool[ i ].TREAP_NEXT  );
     755   409088867 :     _p_nprev = fd_ptr_if( lt, &pool[ i ].TREAP_PREV, _p_nprev               );
     756             : #   endif
     757   479161316 :   }
     758             : 
     759             :   /* Insert n.  This might momentarily break the heap property. */
     760             : 
     761    41050314 :   pool[ n ].TREAP_PARENT = (TREAP_IDX_T)i;
     762    41050314 :   pool[ n ].TREAP_LEFT   = (TREAP_IDX_T)TREAP_IDX_NULL;
     763    41050314 :   pool[ n ].TREAP_RIGHT  = (TREAP_IDX_T)TREAP_IDX_NULL;
     764    41050314 :   *_p_child = (TREAP_IDX_T)n;
     765             : 
     766             : # if TREAP_OPTIMIZE_ITERATION
     767    34419330 :   pool[ n ].TREAP_PREV = *_p_nprev;
     768    34419330 :   pool[ n ].TREAP_NEXT = *_p_pnext;
     769             :   *_p_nprev = (TREAP_IDX_T)n;
     770             :   *_p_pnext = (TREAP_IDX_T)n;
     771             : # endif
     772             : 
     773             :   /* Bubble n up until the heap property is restored. */
     774             : 
     775    41050314 :   ulong n_prio = (ulong)pool[ n ].TREAP_PRIO;
     776    85637393 :   while( !TREAP_IDX_IS_NULL( i ) ) {
     777    68656105 :     ulong i_prio = (ulong)pool[ i ].TREAP_PRIO;
     778             : 
     779    68656105 :     int heap_intact = (n_prio<i_prio) | ((n_prio==i_prio) & (!((n ^ i) & 1UL))); /* Flip coin on equal priority */
     780    68656105 :     if( heap_intact ) break;
     781             : 
     782             :     /* Get i's parent (if any) and parent's link to i (tree root link if no parent) */
     783             : 
     784    44587079 :     ulong p = (ulong)pool[ i ].TREAP_PARENT;
     785             : 
     786    44587079 :     TREAP_IDX_T * _t0      = fd_ptr_if( TREAP_IDX_IS_NULL( p ), &treap->root, &pool[ p ].TREAP_LEFT  );
     787    44587079 :     /**/          _p_child = fd_ptr_if( i==(ulong)*_t0,         _t0,          &pool[ p ].TREAP_RIGHT );
     788             : 
     789             :     /* Get n's child (if any) that will become i's child */
     790             : 
     791    44587079 :     int           n_is_left_child = (n==(ulong)pool[ i ].TREAP_LEFT);
     792    44587079 :     TREAP_IDX_T * _n_child        = fd_ptr_if( n_is_left_child, &pool[ n ].TREAP_RIGHT, &pool[ n ].TREAP_LEFT );
     793    44587079 :     ulong         j               = (ulong)*_n_child;
     794             : 
     795             :     /* Make n child of p (or the root if no parent) */
     796             : 
     797    44587079 :     *_p_child              = (TREAP_IDX_T)n;
     798    44587079 :     pool[ n ].TREAP_PARENT = (TREAP_IDX_T)p;
     799             : 
     800             :     /* Make i child of n */
     801             : 
     802    44587079 :     *_n_child              = (TREAP_IDX_T)i;
     803    44587079 :     pool[ i ].TREAP_PARENT = (TREAP_IDX_T)n;
     804             : 
     805             :     /* Make j (if present) child of i */
     806             : 
     807    44587079 :     TREAP_IDX_T dummy;
     808    44587079 :     *fd_ptr_if( n_is_left_child,        &pool[ i ].TREAP_LEFT, &pool[ i ].TREAP_RIGHT  ) = (TREAP_IDX_T)j;
     809    44587079 :     *fd_ptr_if( TREAP_IDX_IS_NULL( j ), &dummy,                &pool[ j ].TREAP_PARENT ) = (TREAP_IDX_T)i;
     810             : 
     811             :     /* Keep bubbling up */
     812             : 
     813    44587079 :     i = p;
     814    44587079 :   }
     815             : 
     816    41050314 :   treap->ele_cnt++;
     817    41050314 :   return treap;
     818    41050314 : }
     819             : 
     820             : TREAP_(t) *
     821             : TREAP_(idx_remove)( TREAP_(t) * treap,
     822             :                     ulong       d,
     823    41020484 :                     TREAP_T *   pool ) {
     824             : # if FD_TMPL_USE_HANDHOLDING
     825             :   if( FD_UNLIKELY( (d>=treap->ele_max) ) ) FD_LOG_CRIT(( "index out of bounds" ));
     826             :   if( FD_UNLIKELY( (treap->ele_cnt<1)  ) ) FD_LOG_CRIT(( "index out of bounds" ));
     827             : # endif
     828             : 
     829             :   /* Make a hole at d */
     830             : 
     831    41020484 :   ulong p = (ulong)pool[ d ].TREAP_PARENT;
     832    41020484 :   ulong l = (ulong)pool[ d ].TREAP_LEFT;
     833    41020484 :   ulong r = (ulong)pool[ d ].TREAP_RIGHT;
     834             : 
     835    41020484 :   TREAP_IDX_T * _t0      = fd_ptr_if( TREAP_IDX_IS_NULL( p ), &treap->root, &pool[ p ].TREAP_LEFT  );
     836    41020484 :   TREAP_IDX_T * _p_child = fd_ptr_if( d==(ulong)*_t0,         _t0,          &pool[ p ].TREAP_RIGHT );
     837             : 
     838             : # if TREAP_OPTIMIZE_ITERATION
     839    31073558 :   TREAP_IDX_T prev = pool[ d ].TREAP_PREV;
     840    31073558 :   TREAP_IDX_T next = pool[ d ].TREAP_NEXT;
     841    31073558 :   TREAP_IDX_T * _pnext = fd_ptr_if( TREAP_IDX_IS_NULL( prev ), &treap->first, &pool[ prev ].TREAP_NEXT );
     842    31073558 :   TREAP_IDX_T * _nprev = fd_ptr_if( TREAP_IDX_IS_NULL( next ), &treap->last,  &pool[ next ].TREAP_PREV );
     843             :   *_pnext = next;
     844             :   *_nprev = prev;
     845             : # endif
     846             : 
     847    45593859 :   for(;;) {
     848             : 
     849             :     /* At this point, we have a hole to fill at d:
     850             : 
     851             :        p is the hole's parent (if any)
     852             :        l is the hole's left subtree (if any)
     853             :        r is the hole's right subtree (if any)
     854             : 
     855             :        p_child points to the link from p to hole (if the hole has a
     856             :        parent) and to the treap root link otherwise.
     857             : 
     858             :        If there is neither a left subtree nor a right subtree, we are
     859             :        done.  If there is a left/right subtree, we fill the hole with
     860             :        the right/left subtree and we are done. */
     861             : 
     862    45593859 :     int is_null_left  = TREAP_IDX_IS_NULL( l );
     863    45593859 :     int is_null_right = TREAP_IDX_IS_NULL( r );
     864    45593859 :     if( FD_LIKELY( is_null_left | is_null_right ) ) { /* Most nodes near bottom */
     865    41020484 :       TREAP_IDX_T dummy;
     866    41020484 :       *_p_child = (TREAP_IDX_T)fd_ulong_if( !is_null_left, l, r );
     867    41020484 :       *( fd_ptr_if( !is_null_left,  &pool[ l ].TREAP_PARENT,
     868    41020484 :          fd_ptr_if( !is_null_right, &pool[ r ].TREAP_PARENT, &dummy ) ) ) = (TREAP_IDX_T)p;
     869    41020484 :       break;
     870    41020484 :     }
     871             : 
     872             :     /* The hole has two subtrees.  We bubble the hole down one, fill the
     873             :        hole with the root of the subtree that will preserve the heap
     874             :        priority up to the hole (flipping a coin on ties).  Note we don't
     875             :        need to update any links to/from d as we will be getting rid of
     876             :        all links / from d. */
     877             : 
     878     4573375 :     ulong l_prio = (ulong)pool[ l ].TREAP_PRIO;
     879     4573375 :     ulong r_prio = (ulong)pool[ r ].TREAP_PRIO;
     880             : 
     881     4573375 :     int promote_left = (l_prio>r_prio) | ((l_prio==r_prio) & (!((p ^ d) & 1UL)));
     882             : 
     883     4573375 :     ulong c = fd_ulong_if( promote_left, l, r );
     884             : 
     885     4573375 :     *_p_child = (TREAP_IDX_T)c;
     886     4573375 :     pool[ c ].TREAP_PARENT = (TREAP_IDX_T)p;
     887             : 
     888     4573375 :     _p_child = fd_ptr_if  ( promote_left, &pool[ l ].TREAP_RIGHT, &pool[ r ].TREAP_LEFT  );
     889     4573375 :     p        = c;
     890     4573375 :     l        = fd_ulong_if( promote_left,  pool[ l ].TREAP_RIGHT,        l               );
     891     4573375 :     r        = fd_ulong_if( promote_left,        r,                pool[ r ].TREAP_LEFT  );
     892             : 
     893     4573375 :   }
     894             : 
     895    41020484 :   treap->ele_cnt--;
     896    41020484 :   return treap;
     897    41020484 : }
     898             : 
     899             : static inline void
     900             : TREAP_(private_split)( TREAP_IDX_T   idx_node,         /* Tree to split */
     901             :                        TREAP_T *     key,              /* Element whose key is not in the treap rooted at idx_node */
     902             :                        TREAP_IDX_T * _idx_left,        /* Where to store the left tree root */
     903             :                        TREAP_IDX_T * _idx_right,       /* Where to store the right tree root */
     904             :                        TREAP_IDX_T * _idx_last_left,   /* Where to store the last (in BST order) element of the new left tree */
     905             :                        TREAP_IDX_T * _idx_first_right, /* Where to store the first(in BST order) element in the new right tree */
     906     3203154 :                        TREAP_T *     pool ) {          /* Underlying pool */
     907             : 
     908     3203154 :   TREAP_IDX_T idx_parent_left  = TREAP_IDX_NULL;
     909     3203154 :   TREAP_IDX_T idx_parent_right = TREAP_IDX_NULL;
     910     3203154 :   *_idx_last_left   = TREAP_IDX_NULL;
     911     3203154 :   *_idx_first_right = TREAP_IDX_NULL;
     912             : 
     913     6620343 :   while( !TREAP_IDX_IS_NULL( idx_node ) ) {
     914             : 
     915             :     /* At this point we have a non-empty subtree to split whose root is
     916             :        node and we should attach the left and right split trees at
     917             :        idx_parent_left / *_idx_left and idx_parent_right / *_idx_right.
     918             :        (On the first attach, idx_parent_left/right will be idx_null and
     919             :        *_idx_left / *_idx_right are locations where to store the output
     920             :        split treaps.) */
     921             : 
     922     3417189 :     if( TREAP_(lt)( &pool[ idx_node ], key ) ) {
     923             : 
     924             :       /* node is left of key which, by the BST property, means all
     925             :          elements in node's left subtree are also left of key.  We don't
     926             :          know if node's right subtree contains any elements left of key.
     927             :          If it does, these elements should be attached to node's right
     928             :          subtree to preserve the BST property of the left split.
     929             : 
     930             :          As such, we attach node and node's left subtree to the
     931             :          left split, update the attach point for the left split to
     932             :          node's right subtree and then recurse on the node's right
     933             :          subtree.
     934             : 
     935             :          Note that this operation does not do any reordering of
     936             :          priorities (e.g. if element B was a descendant of element A
     937             :          before the split and both B and A belong on the left split, B
     938             :          will still be a descendant of A). */
     939             : 
     940             :       /* Attach node and node's left subtree to the left split */
     941     3236079 :       pool[ idx_node ].TREAP_PARENT = idx_parent_left;
     942     3236079 :       *_idx_left = idx_node;
     943             : 
     944             :       /* The next left split attach is node's right child */
     945     3236079 :       idx_parent_left = idx_node;
     946     3236079 :       _idx_left = &pool[ idx_node ].TREAP_RIGHT;
     947             : 
     948             :       /* If everything in the right subtree is to the right of the key,
     949             :          this is the last node on the left. */
     950     3236079 :       *_idx_last_left = idx_node;
     951             : 
     952             :       /* Recurse on the right subtree */
     953     3236079 :       idx_node = pool[ idx_node ].TREAP_RIGHT;
     954             : 
     955     3236079 :     } else { /* Mirror image of the above */
     956             : 
     957      181110 :       pool[ idx_node ].TREAP_PARENT = idx_parent_right;
     958      181110 :       *_idx_right = idx_node;
     959             : 
     960      181110 :       idx_parent_right = idx_node;
     961      181110 :       _idx_right = &pool[ idx_node ].TREAP_LEFT;
     962             : 
     963      181110 :       *_idx_first_right = idx_node;
     964             : 
     965      181110 :       idx_node = pool[ idx_node ].TREAP_LEFT;
     966             : 
     967      181110 :     }
     968     3417189 :   }
     969             : 
     970             :   /* At this point, we have an empty tree to split */
     971             : 
     972     3203154 :   *_idx_left  = TREAP_IDX_NULL;
     973     3203154 :   *_idx_right = TREAP_IDX_NULL;
     974     3203154 : }
     975             : 
     976             : #if !TREAP_OPTIMIZE_ITERATION
     977             : static inline void
     978             : TREAP_(private_join)( TREAP_IDX_T    idx_left,  /* Root of the left treap */
     979             :                       TREAP_IDX_T    idx_right, /* Root of the right treap, keys in left treap < keys in right treap */
     980             :                       TREAP_IDX_T *  _idx_join, /* Where to store root of joined treaps */
     981           0 :                       TREAP_T     *  pool ) {   /* Underlying pool */
     982           0 : 
     983           0 :   TREAP_IDX_T idx_join_parent = TREAP_IDX_NULL;
     984           0 : 
     985           0 :   for(;;) {
     986           0 : 
     987           0 :     /* TODO: consolidate these cases into a single branch. */
     988           0 : 
     989           0 :     if( TREAP_IDX_IS_NULL( idx_left ) ) { /* Left treap empty */
     990           0 :       /* join is the right treap (or empty if both left and right empty) */
     991           0 :       if( !TREAP_IDX_IS_NULL( idx_right ) ) pool[ idx_right ].TREAP_PARENT = idx_join_parent;
     992           0 :       *_idx_join = idx_right;
     993           0 :       break;
     994           0 :     }
     995           0 : 
     996           0 :     if( TREAP_IDX_IS_NULL( idx_right ) ) { /* Right treap empty */
     997           0 :       /* join is the left treap */
     998           0 :       pool[ idx_left ].TREAP_PARENT = idx_join_parent;
     999           0 :       *_idx_join = idx_left;
    1000           0 :       break;
    1001           0 :     }
    1002           0 : 
    1003           0 :     /* At this point, we have two non empty treaps to join and elements
    1004           0 :        in the left treap have keys before elements in the right treap. */
    1005           0 : 
    1006           0 :     ulong prio_left  = (ulong)pool[ idx_left  ].TREAP_PRIO;
    1007           0 :     ulong prio_right = (ulong)pool[ idx_right ].TREAP_PRIO;
    1008           0 :     if( (prio_left>prio_right) | ((prio_left==prio_right) & (int)(idx_left^idx_right)) ) {
    1009           0 : 
    1010           0 :       /* At this point, the left treap root has higher priority than the
    1011           0 :          right treap root.  So we attach the left treap root and left
    1012           0 :          treap left subtree to the join to preserve the heap property.
    1013           0 :          We know that the left treap right subtree is to the right of
    1014           0 :          these and that the right treap is to the right of that.  So our
    1015           0 :          next join attachment point should be at the left treap right
    1016           0 :          subtree and we should recurse on the left treap right subtree
    1017           0 :          and the right treap. */
    1018           0 : 
    1019           0 :       /* Attach left's root and left's left subtree to the join */
    1020           0 :       pool[ idx_left ].TREAP_PARENT = idx_join_parent;
    1021           0 :       *_idx_join = idx_left;
    1022           0 : 
    1023           0 :       /* The next join attach should be left's right subtree */
    1024           0 :       idx_join_parent = idx_left;
    1025           0 :       _idx_join = &pool[ idx_left ].TREAP_LEFT;
    1026           0 : 
    1027           0 :       /* Recurse on left's right subtree and right treap */
    1028           0 :       idx_left = pool[ idx_left ].TREAP_RIGHT;
    1029           0 : 
    1030           0 :     } else { /* Mirror image of the above */
    1031           0 : 
    1032           0 :       pool[ idx_right ].TREAP_PARENT = idx_join_parent;
    1033           0 :       *_idx_join = idx_right;
    1034           0 : 
    1035           0 :       idx_join_parent = idx_right;
    1036           0 :       _idx_join = &pool[ idx_right ].TREAP_RIGHT;
    1037           0 : 
    1038           0 :       idx_right = pool[ idx_right ].TREAP_LEFT;
    1039           0 : 
    1040           0 :     }
    1041           0 :   }
    1042           0 : }
    1043             : #endif
    1044             : 
    1045             : TREAP_(t) *
    1046             : TREAP_(merge)( TREAP_(t) * treap_a,
    1047             :                TREAP_(t) * treap_b,
    1048       26430 :                TREAP_T *   pool ) {
    1049             : 
    1050       26430 :   TREAP_IDX_T   idx_a      = treap_a->root;
    1051       26430 :   TREAP_IDX_T   idx_b      = treap_b->root;
    1052       26430 :   TREAP_IDX_T   new_root   = TREAP_IDX_NULL;
    1053       26430 :   TREAP_IDX_T * _idx_merge = &new_root;
    1054             : 
    1055             : # if TREAP_OPTIMIZE_ITERATION
    1056             :   /* Invariant: idx_{a,b}_{first,last} is the index of the first/last
    1057             :      node in key order in the subtree rooted at idx_a/idx_b. */
    1058       13065 :   TREAP_IDX_T  idx_a_first = treap_a->first;
    1059       13065 :   TREAP_IDX_T  idx_a_last  = treap_a->last;
    1060       13065 :   TREAP_IDX_T  idx_b_first = treap_b->first;
    1061       13065 :   TREAP_IDX_T  idx_b_last  = treap_b->last;
    1062             : 
    1063             :   /* merged_{prev,next} are the nodes immediately before/after the
    1064             :      merged subtree.  If these are IDX_NULL, then treap_a->first/last
    1065             :      should be updated instead. */
    1066       13065 :   TREAP_IDX_T  merged_prev   = TREAP_IDX_NULL;
    1067       13065 :   TREAP_IDX_T  merged_next   = TREAP_IDX_NULL;
    1068             : # endif
    1069             : 
    1070       26430 : # define STACK_MAX (128UL)
    1071             : 
    1072       26430 :   struct { TREAP_IDX_T idx_merge_parent; TREAP_IDX_T * _idx_merge; TREAP_IDX_T idx_a; TREAP_IDX_T idx_b;
    1073             : #   if TREAP_OPTIMIZE_ITERATION
    1074             :     TREAP_IDX_T idx_a_first, idx_a_last, idx_b_first, idx_b_last;
    1075             :     TREAP_IDX_T merged_prev, merged_next;
    1076             : #   endif
    1077       26430 :   } stack[ STACK_MAX ];
    1078       26430 :   ulong stack_top = 0UL;
    1079             : 
    1080     3229584 : # define STACK_IS_EMPTY (!stack_top)
    1081       26430 : # define STACK_IS_FULL  (stack_top>=STACK_MAX)
    1082             : 
    1083             : # if TREAP_OPTIMIZE_ITERATION
    1084     1588149 : # define STACK_PUSH( imp, im, ia, ib, iaf, ial, ibf, ibl, mp, mn ) do { \
    1085     1588149 :     stack[ stack_top ].idx_merge_parent = (imp);                        \
    1086     1588149 :     stack[ stack_top ]._idx_merge       = (im);                         \
    1087     1588149 :     stack[ stack_top ].idx_a            = (ia);                         \
    1088     1588149 :     stack[ stack_top ].idx_b            = (ib);                         \
    1089     1588149 :     stack[ stack_top ].idx_a_first      = (iaf);                        \
    1090     1588149 :     stack[ stack_top ].idx_a_last       = (ial);                        \
    1091     1588149 :     stack[ stack_top ].idx_b_first      = (ibf);                        \
    1092     1588149 :     stack[ stack_top ].idx_b_last       = (ibl);                        \
    1093     1588149 :     stack[ stack_top ].merged_prev      = (mp);                         \
    1094     1588149 :     stack[ stack_top ].merged_next      = (mn);                         \
    1095     1588149 :     stack_top++;                                                        \
    1096     1588149 :   } while(0)
    1097     1588149 : # define STACK_POP( imp, im, ia, ib, iaf, ial, ibf, ibl, mp, mn ) do {  \
    1098     1588149 :     stack_top--;                                 \
    1099     1588149 :     (imp) = stack[ stack_top ].idx_merge_parent; \
    1100     1588149 :     (im)  = stack[ stack_top ]._idx_merge;       \
    1101     1588149 :     (ia)  = stack[ stack_top ].idx_a;            \
    1102     1588149 :     (ib)  = stack[ stack_top ].idx_b;            \
    1103     1588149 :     (iaf) = stack[ stack_top ].idx_a_first;      \
    1104     1588149 :     (ial) = stack[ stack_top ].idx_a_last;       \
    1105     1588149 :     (ibf) = stack[ stack_top ].idx_b_first;      \
    1106     1588149 :     (ibl) = stack[ stack_top ].idx_b_last;       \
    1107     1588149 :     (mp)  = stack[ stack_top ].merged_prev;      \
    1108     1588149 :     (mn)  = stack[ stack_top ].merged_next;      \
    1109     1588149 :   } while(0)
    1110             : # else
    1111     1615005 : # define STACK_PUSH( imp, im, ia, ib ) do {      \
    1112     1615005 :     stack[ stack_top ].idx_merge_parent = (imp); \
    1113     1615005 :     stack[ stack_top ]._idx_merge       = (im);  \
    1114     1615005 :     stack[ stack_top ].idx_a            = (ia);  \
    1115     1615005 :     stack[ stack_top ].idx_b            = (ib);  \
    1116     1615005 :     stack_top++;                                 \
    1117     1615005 :   } while(0)
    1118     1615005 : # define STACK_POP( imp, im, ia, ib ) do {       \
    1119     1615005 :     stack_top--;                                 \
    1120     1615005 :     (imp) = stack[ stack_top ].idx_merge_parent; \
    1121     1615005 :     (im)  = stack[ stack_top ]._idx_merge;       \
    1122     1615005 :     (ia)  = stack[ stack_top ].idx_a;            \
    1123     1615005 :     (ib)  = stack[ stack_top ].idx_b;            \
    1124     1615005 :   } while(0)
    1125             : # endif
    1126             : 
    1127       26430 :   TREAP_IDX_T idx_merge_parent = TREAP_IDX_NULL;
    1128             : 
    1129     6432738 :   for(;;) {
    1130             : 
    1131             :     /* At this point, we are to merge the treaps rooted at idx_a and
    1132             :        idx_b.  The result should be attached to the output treap at node
    1133             :        idx_merge_parent via the link *idx_merge.  (On the first
    1134             :        iteration, the idx_merge_parent will be idx_null and *_idx_merge
    1135             :        will be where to store the root of the output treap.) */
    1136             : 
    1137     6432738 :     int idx_a_is_null = TREAP_IDX_IS_NULL( idx_a );
    1138     6432738 :     int idx_b_is_null = TREAP_IDX_IS_NULL( idx_b );
    1139     6432738 :     if( idx_a_is_null | idx_b_is_null ) {
    1140             : 
    1141             :       /* At this point, at least one of the treaps to merge is empty.
    1142             :          Attach the non-empty treap (if any) accordingly.  If both are
    1143             :          empty, we attach NULL and there is no parent field to update. */
    1144             : 
    1145     3205584 :       TREAP_IDX_T idx_tmp;
    1146     3205584 :       *fd_ptr_if( idx_b_is_null, fd_ptr_if( idx_a_is_null, &idx_tmp,
    1147     3205584 :                                                            &pool[ idx_a ].TREAP_PARENT ),
    1148     3205584 :                                                            &pool[ idx_b ].TREAP_PARENT ) = idx_merge_parent;
    1149     3205584 :       *_idx_merge = (TREAP_IDX_T)fd_ulong_if( idx_b_is_null, (ulong)idx_a, (ulong)idx_b );
    1150             : 
    1151             : #     if TREAP_OPTIMIZE_ITERATION
    1152             :       /* Update the four pointers to insert the range
    1153             :          idx_a_first and idx_a_last (or b if a is the empty subtree)
    1154             :          between merged_prev and merged_next.  If both are the empty
    1155             :          subtree, then merged_prev connects directly to merged_next. */
    1156     1589214 :       *fd_ptr_if( TREAP_IDX_IS_NULL( merged_prev ), &treap_a->first, &pool[ merged_prev ].TREAP_NEXT ) =
    1157             :                                         (TREAP_IDX_T)fd_ulong_if( idx_b_is_null, fd_ulong_if( idx_a_is_null, (ulong)merged_next,
    1158             :                                                                                                              (ulong)idx_a_first ),
    1159             :                                                                                                              (ulong)idx_b_first );
    1160     1589214 :       *fd_ptr_if( TREAP_IDX_IS_NULL( merged_next ), &treap_a->last , &pool[ merged_next ].TREAP_PREV ) =
    1161             :                                         (TREAP_IDX_T)fd_ulong_if( idx_b_is_null, fd_ulong_if( idx_a_is_null, (ulong)merged_prev,
    1162             :                                                                                                              (ulong)idx_a_last  ),
    1163             :                                                                                                              (ulong)idx_b_last  );
    1164     1589214 :       *fd_ptr_if( idx_b_is_null, fd_ptr_if( idx_a_is_null, &idx_tmp,
    1165             :                                                            &pool[ idx_a_first ].TREAP_PREV ),
    1166             :                                                            &pool[ idx_b_first ].TREAP_PREV ) = merged_prev;
    1167     1589214 :       *fd_ptr_if( idx_b_is_null, fd_ptr_if( idx_a_is_null, &idx_tmp,
    1168             :                                                            &pool[ idx_a_last ].TREAP_NEXT ),
    1169             :                                                            &pool[ idx_b_last ].TREAP_NEXT ) = merged_next;
    1170             : 
    1171             : #     endif
    1172             :       /* Pop the stack to get the next merge to do.  If the stack is
    1173             :          empty, we are done. */
    1174             : 
    1175     3205584 :       if( STACK_IS_EMPTY ) break;
    1176             : #     if TREAP_OPTIMIZE_ITERATION
    1177     1576149 :       STACK_POP( idx_merge_parent, _idx_merge, idx_a, idx_b, idx_a_first, idx_a_last, idx_b_first, idx_b_last, merged_prev, merged_next );
    1178             : #     else
    1179     1603005 :       STACK_POP( idx_merge_parent, _idx_merge, idx_a, idx_b );
    1180     1603005 : #     endif
    1181     1603005 :       continue;
    1182     3205584 :     }
    1183             : 
    1184             :     /* If the stack is full, it appears we have exceedingly poorly
    1185             :        balanced treaps to merge.  To mitigate stack overflow risk from
    1186             :        the recursion, we fall back on a marginally less efficient brute
    1187             :        force non-recursive algorithm for the merge.  FIXME: consider
    1188             :        doing this post swap for statistical reasons (i.e. the treap with
    1189             :        the higher root priority is likely to be the larger treap and
    1190             :        such might have some performance implications for the below
    1191             :        loop). */
    1192             : 
    1193     3227154 :     if( FD_UNLIKELY( STACK_IS_FULL ) ) {
    1194             : 
    1195             :       /* Remove elements from B one-by-one and insert them into A.
    1196             :          O(B lg B) for the removes, O(B lg(A + B)) for the inserts.  The
    1197             :          value for ele_cnt in temp_treap_b is a dummy value to avoid
    1198             :          handholding checks from spuriously firing. */
    1199             : 
    1200             : #     if TREAP_OPTIMIZE_ITERATION
    1201       12000 :       TREAP_(t) temp_treap_a = { .ele_max = treap_a->ele_max, .ele_cnt = 0UL,              .root = idx_a, .first=idx_a_first, .last=idx_a_last };
    1202       12000 :       TREAP_(t) temp_treap_b = { .ele_max = treap_b->ele_max, .ele_cnt = treap_b->ele_max, .root = idx_b, .first=idx_b_first, .last=idx_b_last };
    1203             : #     else
    1204       12000 :       TREAP_(t) temp_treap_a = { .ele_max = treap_a->ele_max, .ele_cnt = 0UL,              .root = idx_a };
    1205       12000 :       TREAP_(t) temp_treap_b = { .ele_max = treap_b->ele_max, .ele_cnt = treap_b->ele_max, .root = idx_b };
    1206             : #     endif
    1207       24000 :       pool[ idx_a ].TREAP_PARENT = TREAP_IDX_NULL;
    1208       24000 :       pool[ idx_b ].TREAP_PARENT = TREAP_IDX_NULL;
    1209     1124883 :       do {
    1210     1124883 :         TREAP_IDX_T idx_tmp = temp_treap_b.root;
    1211     1124883 :         TREAP_(idx_remove)( &temp_treap_b, idx_tmp, pool );
    1212     1124883 :         TREAP_(idx_insert)( &temp_treap_a, idx_tmp, pool );
    1213     1124883 :       } while( !TREAP_IDX_IS_NULL( temp_treap_b.root ) );
    1214             : 
    1215       24000 :       idx_b = TREAP_IDX_NULL;
    1216       24000 :       idx_a = temp_treap_a.root;
    1217             : 
    1218             :       /* Attach the merged treap to the output */
    1219             : 
    1220       24000 :       pool[ idx_a ].TREAP_PARENT = idx_merge_parent;
    1221       24000 :       *_idx_merge = idx_a;
    1222             : 
    1223             : #     if TREAP_OPTIMIZE_ITERATION
    1224       12000 :       *fd_ptr_if( TREAP_IDX_IS_NULL( merged_prev ), &treap_a->first, &pool[ merged_prev ].TREAP_NEXT ) = temp_treap_a.first;
    1225       12000 :       *fd_ptr_if( TREAP_IDX_IS_NULL( merged_next ), &treap_a->last,  &pool[ merged_next ].TREAP_PREV ) = temp_treap_a.last;
    1226       12000 :       pool[ temp_treap_a.first ].TREAP_PREV = merged_prev;
    1227       12000 :       pool[ temp_treap_a.last  ].TREAP_NEXT = merged_next;
    1228             : #     endif
    1229             : 
    1230             :       /* Pop the stack to get the next merge to do.  If the stack is
    1231             :          empty, we are done. */
    1232             : 
    1233       24000 :       if( STACK_IS_EMPTY ) break;
    1234             : #     if TREAP_OPTIMIZE_ITERATION
    1235       12000 :       STACK_POP( idx_merge_parent, _idx_merge, idx_a, idx_b,
    1236       12000 :           idx_a_first, idx_a_last, idx_b_first, idx_b_last, merged_prev, merged_next );
    1237             : #     else
    1238       12000 :       STACK_POP( idx_merge_parent, _idx_merge, idx_a, idx_b );
    1239       12000 : #     endif
    1240       12000 :       continue;
    1241       24000 :     }
    1242             : 
    1243             :     /* At this point, we have two non-empty treaps A and B to merge and
    1244             :        we have stack space so we can use a fast recursive algorithm.  If
    1245             :        A's root priority is below B's root priority, swap A and B. */
    1246             : 
    1247     3203154 :     TREAP_IDX_T prio_a = pool[ idx_a ].TREAP_PRIO;
    1248     3203154 :     TREAP_IDX_T prio_b = pool[ idx_b ].TREAP_PRIO;
    1249     3203154 :     int swap = (prio_a<prio_b) | ((prio_a==prio_b) & (int)(idx_a ^ idx_b));
    1250     3203154 :     fd_swap_if( swap, idx_a,       idx_b       );
    1251             : #   if TREAP_OPTIMIZE_ITERATION
    1252     1588149 :     fd_swap_if( swap, idx_a_first, idx_b_first );
    1253     1588149 :     fd_swap_if( swap, idx_a_last,  idx_b_last  );
    1254             : #   endif
    1255             : 
    1256             :     /* At this point, we have two non-empty treaps to merge and A's root
    1257             :        priority is higher than B's root priority.  So, we know the root
    1258             :        of the merged treaps is A's root and can attach it to the output
    1259             :        treap accordingly. */
    1260             : 
    1261     3203154 :     pool[ idx_a ].TREAP_PARENT = idx_merge_parent;
    1262     3203154 :     *_idx_merge = idx_a;
    1263             : 
    1264             :     /* Get A's left and right subtrees */
    1265             : 
    1266     3203154 :     TREAP_IDX_T idx_a_left  = pool[ idx_a ].TREAP_LEFT;
    1267     3203154 :     TREAP_IDX_T idx_a_right = pool[ idx_a ].TREAP_RIGHT;
    1268             : 
    1269             :     /* Split B by A's root key */
    1270             : 
    1271     3203154 :     TREAP_IDX_T idx_b_left;
    1272     3203154 :     TREAP_IDX_T idx_b_right;
    1273     3203154 :     TREAP_IDX_T idx_b_left_last;
    1274     3203154 :     TREAP_IDX_T idx_b_right_first;
    1275     3203154 :     TREAP_(private_split)( idx_b, &pool[ idx_a ], &idx_b_left, &idx_b_right, &idx_b_left_last, &idx_b_right_first, pool );
    1276             : 
    1277             : #   if TREAP_OPTIMIZE_ITERATION
    1278             :     /* Split the iteration order links in B as well */
    1279     1588149 :     TREAP_IDX_T dummy;
    1280     1588149 :     *fd_ptr_if( TREAP_IDX_IS_NULL( idx_b_left_last   ), &dummy, &pool[ idx_b_left_last   ].TREAP_NEXT ) = TREAP_IDX_NULL;
    1281     1588149 :     *fd_ptr_if( TREAP_IDX_IS_NULL( idx_b_right_first ), &dummy, &pool[ idx_b_right_first ].TREAP_PREV ) = TREAP_IDX_NULL;
    1282             : 
    1283             :     /* The first node in B's left subtree is the first node in B unless
    1284             :        it is empty.  Similarly for B's right subtree. */
    1285     1588149 :     TREAP_IDX_T idx_b_left_first = (TREAP_IDX_T)fd_ulong_if( TREAP_IDX_IS_NULL( idx_b_left  ), TREAP_IDX_NULL, idx_b_first );
    1286     1588149 :     TREAP_IDX_T idx_b_right_last = (TREAP_IDX_T)fd_ulong_if( TREAP_IDX_IS_NULL( idx_b_right ), TREAP_IDX_NULL, idx_b_last  );
    1287             : #   endif
    1288             : 
    1289             :     /* At this point, A's left subtree and B's left split are all keys
    1290             :        to the left of A's root and A's right subtree.  Similarly, B's
    1291             :        right split are all keys to the right of A's root and A's left
    1292             :        subtree.  We can't do a fast join on A's left/right subtree and B's
    1293             :        left/right split though as theses are not guaranteed to already
    1294             :        have their keys distributed as required by join.  We instead
    1295             :        recursively merge the left side and right side.  We do the left
    1296             :        side first and the right side later (making this a cache oblivious
    1297             :        algorithm too). */
    1298             : 
    1299             : #   if TREAP_OPTIMIZE_ITERATION
    1300     1588149 :     STACK_PUSH( idx_a, &pool[ idx_a ].TREAP_RIGHT, idx_a_right, idx_b_right,
    1301             :                 pool[ idx_a ].TREAP_NEXT, idx_a_last, idx_b_right_first, idx_b_right_last, idx_a, merged_next );
    1302             : #   else
    1303     1615005 :     STACK_PUSH( idx_a, &pool[ idx_a ].TREAP_RIGHT, idx_a_right, idx_b_right );
    1304             : #   endif
    1305             : 
    1306     3203154 :     idx_merge_parent = idx_a;
    1307     3203154 :     _idx_merge       = &pool[ idx_a ].TREAP_LEFT;
    1308             : #   if TREAP_OPTIMIZE_ITERATION
    1309     1588149 :     idx_a_last       = pool[ idx_a ].TREAP_PREV;
    1310             :     idx_b_first      = idx_b_left_first;
    1311             :     idx_b_last       = idx_b_left_last;
    1312             :     merged_next      = idx_a;
    1313             : #   endif
    1314     3203154 :     idx_a            = idx_a_left;
    1315     3203154 :     idx_b            = idx_b_left;
    1316     3203154 :   }
    1317             : 
    1318       26430 :   treap_a->root     = new_root;
    1319       26430 :   treap_b->root     = TREAP_IDX_NULL;
    1320       26430 :   treap_a->ele_cnt += treap_b->ele_cnt;
    1321       26430 :   treap_b->ele_cnt  = 0UL;
    1322             : # if TREAP_OPTIMIZE_ITERATION
    1323       13065 :   treap_b->first    = TREAP_IDX_NULL;
    1324       13065 :   treap_b->last     = TREAP_IDX_NULL;
    1325             : # endif
    1326             : 
    1327       26430 :   return treap_a;
    1328             : 
    1329       26430 : # undef STACK_POP
    1330       26430 : # undef STACK_PUSH
    1331       26430 : # undef STACK_IS_FULL
    1332       26430 : # undef STACK_IS_EMPTY
    1333       26430 : # undef STACK_MAX
    1334       26430 : }
    1335             : 
    1336             : TREAP_STATIC TREAP_(fwd_iter_t)
    1337             : TREAP_(fwd_iter_init)( TREAP_(t) const * treap,
    1338    62820652 :                        TREAP_T const *   pool ) {
    1339             : # if TREAP_OPTIMIZE_ITERATION
    1340             :   (void)pool;
    1341             :   return treap->first;
    1342             : # else
    1343     2998872 :   ulong i = TREAP_IDX_NULL;
    1344             :   ulong j = (ulong)treap->root;
    1345    14178318 :   while( FD_LIKELY( !TREAP_IDX_IS_NULL( j ) ) ) { i = j; j = (ulong)pool[ j ].TREAP_LEFT; }
    1346             :   return i;
    1347             : # endif
    1348    62820652 : }
    1349             : 
    1350             : TREAP_STATIC TREAP_(rev_iter_t)
    1351             : TREAP_(rev_iter_init)( TREAP_(t) const * treap,
    1352     5172521 :                        TREAP_T const *   pool ) {
    1353             : # if TREAP_OPTIMIZE_ITERATION
    1354             :   (void)pool;
    1355             :   return treap->last;
    1356             : # else
    1357     2999310 :   ulong i = TREAP_IDX_NULL;
    1358             :   ulong j = (ulong)treap->root;
    1359    14226927 :   while( FD_LIKELY( !TREAP_IDX_IS_NULL( j ) ) ) { i = j; j = (ulong)pool[ j ].TREAP_RIGHT; }
    1360             :   return i;
    1361             : # endif
    1362     5172521 : }
    1363             : 
    1364             : TREAP_STATIC TREAP_(fwd_iter_t)
    1365             : TREAP_(fwd_iter_next)( TREAP_(fwd_iter_t) i,
    1366   121362333 :                        TREAP_T const *    pool ) {
    1367             : # if TREAP_OPTIMIZE_ITERATION
    1368    26640381 :   return pool[ i ].TREAP_NEXT;
    1369             : # else
    1370    94721952 :   ulong r = (ulong)pool[ i ].TREAP_RIGHT;
    1371             : 
    1372    94721952 :   if( TREAP_IDX_IS_NULL( r ) ) {
    1373    48788271 :     ulong p = (ulong)pool[ i ].TREAP_PARENT;
    1374    94721892 :     while( !TREAP_IDX_IS_NULL( p ) ) {
    1375    91769691 :       if( i==(ulong)pool[ p ].TREAP_LEFT ) break;
    1376    45933621 :       i = p;
    1377    45933621 :       p = (ulong)pool[ p ].TREAP_PARENT;
    1378    45933621 :     }
    1379    48788271 :     return p;
    1380    48788271 :   }
    1381             : 
    1382    45933681 :   i = r;
    1383    83542536 :   for(;;) {
    1384    83542536 :     ulong l = (ulong)pool[ i ].TREAP_LEFT;
    1385    83542536 :     if( TREAP_IDX_IS_NULL( l ) ) break;
    1386    37608855 :     i = l;
    1387    37608855 :   }
    1388             : 
    1389    45933681 :   return i;
    1390             : # endif
    1391   121362333 : }
    1392             : 
    1393             : TREAP_STATIC TREAP_(rev_iter_t)
    1394             : TREAP_(rev_iter_next)( TREAP_(rev_iter_t) i,
    1395   118608604 :                        TREAP_T const *    pool ) {
    1396             : # if TREAP_OPTIMIZE_ITERATION
    1397    23841145 :   return pool[ i ].TREAP_PREV;
    1398             : #else
    1399    94767459 :   ulong l = (ulong)pool[ i ].TREAP_LEFT;
    1400             : 
    1401    94767459 :   if( TREAP_IDX_IS_NULL( l ) ) {
    1402    48909408 :     ulong p = (ulong)pool[ i ].TREAP_PARENT;
    1403    94766706 :     while( !TREAP_IDX_IS_NULL( p ) ) {
    1404    91814016 :       if( i==(ulong)pool[ p ].TREAP_RIGHT ) break;
    1405    45857298 :       i = p;
    1406    45857298 :       p = (ulong)pool[ p ].TREAP_PARENT;
    1407    45857298 :     }
    1408    48909408 :     return p;
    1409    48909408 :   }
    1410             : 
    1411    45858051 :   i = l;
    1412    83539842 :   for(;;) {
    1413    83539842 :     ulong r = (ulong)pool[ i ].TREAP_RIGHT;
    1414    83539842 :     if( TREAP_IDX_IS_NULL( r ) ) break;
    1415    37681791 :     i = r;
    1416    37681791 :   }
    1417             : 
    1418    45858051 :   return i;
    1419             : #endif
    1420   118608604 : }
    1421             : 
    1422             : TREAP_STATIC int
    1423             : TREAP_(verify)( TREAP_(t) const * treap,
    1424    30061167 :                 TREAP_T const *   pool ) {
    1425             : 
    1426  7679708790 : # define TREAP_TEST( c ) do { if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: " #c )); return -1; } } while(0)
    1427             : 
    1428    30061167 :   TREAP_TEST( treap ); /* Validate local join */
    1429             : 
    1430    30061167 :   ulong ele_max = treap->ele_max; TREAP_TEST( ele_max<=TREAP_IDX_NULL ); /* Validate ele_max */
    1431    30061167 :   ulong ele_cnt = treap->ele_cnt; TREAP_TEST( ele_cnt<=ele_max        ); /* Validate ele_cnt */
    1432    30061167 :   if( ele_max ) TREAP_TEST( pool );                                      /* Validate ele storage */
    1433             : 
    1434             :   /* Find leftmost */
    1435             : 
    1436    30061167 :   ulong i = TREAP_IDX_NULL;
    1437    30061167 :   ulong l = (ulong)treap->root;
    1438             : 
    1439    30061167 :   ulong loop_cnt = 0UL;
    1440   151275504 :   while( FD_LIKELY( !TREAP_IDX_IS_NULL( l ) ) ) {
    1441   121214337 :     TREAP_TEST( loop_cnt<ele_cnt ); /* Make sure no cycles */
    1442   121214337 :     TREAP_TEST( l       <ele_max ); /* Make sure valid index */
    1443   121214337 :     i = l;
    1444   121214337 :     l = (ulong)pool[ l ].TREAP_LEFT;
    1445   121214337 :     loop_cnt++;
    1446   121214337 :   }
    1447             : # if TREAP_OPTIMIZE_ITERATION
    1448       43347 :   TREAP_TEST( treap->first==i );
    1449       43347 : # endif
    1450             : 
    1451             :   /* In-order traverse the treap starting from the leftmost */
    1452             : 
    1453    30061167 :   ulong cnt = 0UL; /* Number of elements we've visited so far */
    1454   988018611 :   while( FD_LIKELY( !TREAP_IDX_IS_NULL( i ) ) ) {
    1455   957957444 :     TREAP_TEST( cnt<ele_cnt ); /* Make sure no cycles */
    1456             : 
    1457             :     /* At this point, we are visiting element i.  We've already visited
    1458             :        all elements less than i and l is the last element we visited (or
    1459             :        NULL if i is the first element we are visiting. */
    1460             : 
    1461   957957444 :     if( FD_LIKELY( !TREAP_IDX_IS_NULL( l ) ) ) TREAP_TEST( !TREAP_(lt)( pool + i, pool + l ) ); /* Make sure ordering valid */
    1462             : #   if TREAP_OPTIMIZE_ITERATION
    1463             :     /* Check the l <-> i link */
    1464     6839202 :     if( FD_LIKELY( !TREAP_IDX_IS_NULL( l ) ) ) TREAP_TEST( pool[ l ].TREAP_NEXT==i );
    1465     6839202 :     if( FD_LIKELY( !TREAP_IDX_IS_NULL( i ) ) ) TREAP_TEST( pool[ i ].TREAP_PREV==l );
    1466     6839202 : #   endif
    1467             : 
    1468             : 
    1469   957957444 :     ulong p = (ulong)pool[ i ].TREAP_PARENT;
    1470   957957444 :     if( FD_LIKELY( !TREAP_IDX_IS_NULL( p ) ) ) {
    1471   928361772 :       TREAP_TEST( p < ele_max );                                                /* Make sure valid index */
    1472   928361772 :       TREAP_TEST( (ulong)pool[ p ].TREAP_PRIO >= (ulong)pool[ i ].TREAP_PRIO ); /* Make sure heap property valid */
    1473   928361772 :     }
    1474             : 
    1475             :     /* Done visiting i, advance to i's successor */
    1476             : 
    1477   957957444 :     cnt++;
    1478             : 
    1479   957957444 :     l = i;
    1480             : 
    1481   957957444 :     ulong r = (ulong)pool[ i ].TREAP_RIGHT;
    1482   957957444 :     if( TREAP_IDX_IS_NULL( r ) ) {
    1483             : 
    1484             :       /* i has no right subtree.  Look for first ancestor of i that we
    1485             :          haven't visited (this will be the first ancestor for which i is
    1486             :          in the ancestor's left subtree).  If there is no such ancestor,
    1487             :          we are at the rightmost and we are done. */
    1488             : 
    1489   497957373 :       loop_cnt = 0UL;
    1490   957957444 :       while( !TREAP_IDX_IS_NULL( p ) ) {
    1491   928361772 :         TREAP_TEST( loop_cnt<ele_cnt ); /* Make sure no cycles */
    1492   928361772 :         TREAP_TEST( p       <ele_max ); /* Make sure valid index */
    1493   928361772 :         if( i==(ulong)pool[ p ].TREAP_LEFT ) break;
    1494   460000071 :         i = p;
    1495   460000071 :         p = (ulong)pool[ p ].TREAP_PARENT;
    1496   460000071 :         loop_cnt++;
    1497   460000071 :       }
    1498             : 
    1499   497957373 :       i = p;
    1500             : 
    1501   497957373 :     } else {
    1502             : 
    1503             :       /* i has a right subtree.  Find the leftmost in this subtree. */
    1504             : 
    1505   460000071 :       i = r;
    1506             : 
    1507   460000071 :       loop_cnt = 0UL;
    1508   836743107 :       for(;;) {
    1509   836743107 :         TREAP_TEST( loop_cnt<ele_cnt ); /* Make sure no cycles */
    1510   836743107 :         TREAP_TEST( i       <ele_max ); /* Make sure valid index */
    1511   836743107 :         ulong ll = (ulong)pool[ i ].TREAP_LEFT;
    1512   836743107 :         if( TREAP_IDX_IS_NULL( ll ) ) break;
    1513   376743036 :         i = ll;
    1514   376743036 :         loop_cnt++;
    1515   376743036 :       }
    1516             : 
    1517   460000071 :     }
    1518             : 
    1519   957957444 :   }
    1520             : 
    1521             : # if TREAP_OPTIMIZE_ITERATION
    1522       43347 :   TREAP_TEST( treap->last==l );
    1523       43347 : # endif
    1524             : 
    1525    30061167 :   TREAP_TEST( cnt==ele_cnt ); /* Make sure we visited correct number of elements */
    1526             : 
    1527    30061167 : # undef TREAP_TEST
    1528             : 
    1529    30061167 :   return 0;
    1530    30061167 : }
    1531             : 
    1532             : #endif
    1533             : 
    1534             : #undef TREAP_IDX_IS_NULL
    1535             : #undef TREAP_IDX_NULL
    1536             : #undef TREAP_STATIC
    1537             : 
    1538             : #undef TREAP_IMPL_STYLE
    1539             : #undef TREAP_NEXT
    1540             : #undef TREAP_PREV
    1541             : #undef TREAP_OPTIMIZE_ITERATION
    1542             : #undef TREAP_PRIO
    1543             : #undef TREAP_RIGHT
    1544             : #undef TREAP_LEFT
    1545             : #undef TREAP_PARENT
    1546             : #undef TREAP_IDX_T
    1547             : #undef TREAP_LT
    1548             : #undef TREAP_CMP
    1549             : #undef TREAP_QUERY_T
    1550             : #undef TREAP_T
    1551             : #undef TREAP_NAME

Generated by: LCOV version 1.14