LCOV - code coverage report
Current view: top level - util/tmpl - fd_map_chain.c (source / functions) Hit Total Coverage
Test: cov.lcov Lines: 299 304 98.4 %
Date: 2025-10-13 04:42:14 Functions: 684 7249 9.4 %

          Line data    Source code
       1             : /* Generate prototypes, inlines and/or implementations for ultra high
       2             :    performance maps based on hash chains.  A map can store a practically
       3             :    unbounded number of elements but, if sized on creation for the
       4             :    maximum number of mapped elements, typical map operations are a fast
       5             :    O(1) time and map element overhead is a small O(1) space.
       6             : 
       7             :    This API is designed for ultra tight coupling with pools, treaps,
       8             :    heaps, lists, other maps, etc.  Likewise, a map can be persisted
       9             :    beyond the lifetime of the creating process, used concurrently in
      10             :    many common operations, used inter-process, relocated in memory,
      11             :    naively serialized/deserialized, moved between hosts, supports index
      12             :    compression for cache and memory bandwidth efficiency, etc.
      13             : 
      14             :    Memory efficiency and flexible footprint are prioritized.  Elements
      15             :    that are recently queried can be optionally moved to the front of
      16             :    hash chains to adaptively optimize the maps for recent queries in
      17             :    non-concurrent use cases.
      18             : 
      19             :    Typical usage:
      20             : 
      21             :      struct myele {
      22             :        ulong key;  // Technically "MAP_KEY_T MAP_KEY"  (default is ulong key),  do not modify while the element is in the map
      23             :        ulong next; // Technically "MAP_IDX_T MAP_NEXT" (default is ulong next), do not modify while the element is in the map
      24             :        ... key and next can be located arbitrarily in the element and
      25             :        ... can be reused for other purposes when the element is not in a
      26             :        ... map.  The mapping of a key to an element storage index is
      27             :        ... arbitrary but an element should not be moved / released while
      28             :        ... an element is in a map.
      29             : 
      30             :        ... if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL is set to 1, elements
      31             :        ... must also have a prev field.  This field is used to optimize
      32             :        ... removing elements from a chain quickly, if they are pointed
      33             :        ... to by some other index.
      34             :        ulong prev; // Technically "MAP_IDX_T MAP_PREV" (default is ulong prev), do not modify while the element is in the map
      35             :      };
      36             : 
      37             :      typedef struct myele myele_t;
      38             : 
      39             :      #define MAP_NAME  mymap
      40             :      #define MAP_ELE_T myele_t
      41             :      #include "tmpl/fd_map_chain.c"
      42             : 
      43             :    will declare the following APIs as a header only style library in the
      44             :    compilation unit:
      45             : 
      46             :      // mymap_ele_max returns the theoretical maximum number of elements
      47             :      // that can be mapped by a mymap.
      48             : 
      49             :      ulong mymap_ele_max( void );
      50             : 
      51             :      // mymap_chain_max returns the theoretical maximum number possible
      52             :      // chains in a mymap.  Will be an integer power-of-two.
      53             : 
      54             :      ulong mymap_chain_max( void );
      55             : 
      56             :      // mymap_chain_cnt_est returns a reasonable number of chains to use
      57             :      // for a map that is expected to hold up to ele_max_est elements.
      58             :      // ele_max_est will be clamped to be in [1,mymap_ele_max()] and the
      59             :      // return value will be an integer power-of-two in
      60             :      // [1,mymap_chain_max()].
      61             : 
      62             :      ulong mymap_chain_cnt_est( ulong ele_max_est );
      63             : 
      64             :      // mymap_{align,footprint} returns the alignment and footprint
      65             :      // needed for a memory region to be used as a mymap.  align will be
      66             :      // an integer power-of-two and footprint will be a multiple of
      67             :      // align.  footprint returns 0 if chain_cnt is not an integer
      68             :      // power-of-two in [1,mymap_chain_max()].
      69             :      //
      70             :      // mymap_new formats a memory region with the appropriate alignment
      71             :      // and footprint whose first byte in the caller's address space is
      72             :      // pointed by shmem for use as a mymap.  Returns shmem on success
      73             :      // and NULL on failure (logs details).  Caller is not joined on
      74             :      // return.  The map will be empty.
      75             :      //
      76             :      // mymap_join joins a mymap.  Assumes shmap points at a memory
      77             :      // region formatted as a mymap in the caller's address space.
      78             :      // Returns a handle to the caller's local join on success and NULL
      79             :      // on failure (logs details).  Do not assume this is a simple cast
      80             :      // of shmap!
      81             :      //
      82             :      // mymap_leave leaves a mymap.  Assumes join points to a current
      83             :      // local join.  Returns shmap used on join.  Do not assume this is
      84             :      // a simple cast of join!
      85             :      //
      86             :      // mymap_delete unformats a memory region used as a mymap.  Assumes
      87             :      // shmap points to a memory region in the caller's local address
      88             :      // space formatted as a mymap, that there are no joins to the mymap
      89             :      // and that any application cleanup of the entries has already been
      90             :      // done.  Returns shmap on success and NULL on failure.
      91             : 
      92             :      ulong     mymap_align    ( void );
      93             :      ulong     mymap_footprint( ulong chain_cnt );
      94             :      void *    mymap_new      ( void * shmem, ulong chain_cnt, ulong seed );
      95             :      mymap_t * mymap_join     ( void * shmap );
      96             :      void *    mymap_leave    ( mymap_t * join  );
      97             :      void *    mymap_delete   ( void * shmap );
      98             : 
      99             :      // mymap_{chain_cnt,seed} return the values used to construct the
     100             :      // map.  They assume join is a current local join.  The values will
     101             :      // be constant for the map lifetime.
     102             : 
     103             :      ulong mymap_chain_cnt( mymap_t const * join );
     104             :      ulong mymap_seed     ( mymap_t const * join );
     105             : 
     106             :      // mymap_key_{eq,hash} expose the provided MAP_KEY_{EQ,HASH} macros
     107             :      // as inline functions with strict semantics.  They assume that the
     108             :      // provided pointers are in the caller's address space to keys that
     109             :      // will not be changed concurrently.  They retain no interest in
     110             :      // any keys on return.
     111             :      //
     112             :      // mymap_key_eq returns 1 if *k0 and *k1 are equal and 0 otherwise.
     113             :      //
     114             :      // mymap_key_hash returns the hash of *key using the hash function
     115             :      // seed.  Should ideally be a random mapping from MAP_KEY_T to
     116             :      // ulong but this depends on what the user actually passed in for
     117             :      // MAP_KEY_HASH.  The seed used by a particular instance of a map
     118             :      // can be obtained above.
     119             : 
     120             :      int   mymap_key_eq  ( ulong * k0,  ulong * k1 );
     121             :      ulong mymap_key_hash( ulong * key, ulong seed );
     122             : 
     123             :      // mymap_idx_insert inserts an element into the map.  The caller
     124             :      // promises the element is not currently in the map and that
     125             :      // element key is not equal to the key of any other element
     126             :      // currently in the map, except if MAP_MULTI is enabled.  Assumes
     127             :      // there are no concurrent operations on the map.  This always
     128             :      // succeeds.
     129             : 
     130             :      mymap_t *                            // Returns join
     131             :      mymap_idx_insert( mymap_t * join,    // Current local join to element map
     132             :                        ulong     ele_idx, // Index of element to insert
     133             :                        myele_t * pool );  // Current local join to element storage
     134             : 
     135             :      // mymap_idx_remove removes the mapping of a key to an element.
     136             :      // Assumes there are no concurrent operations on the map and that
     137             :      // *key will not be modified during the remove.  The map retains no
     138             :      // interest in key.  On success, the map will no longer have an
     139             :      // interest in the returned element.  On failure, the returned
     140             :      // index lifetime will be that of the sentinel.
     141             : 
     142             :      ulong                                     // Index of removed element on success, sentinel on failure
     143             :      mymap_idx_remove( mymap_t *     join,     // Current local join to element map
     144             :                        ulong const * key,      // Points to the key to remove in the caller's address space
     145             :                        ulong         sentinel, // Value to return if key not in map
     146             :                        myele_t *     pool );   // Current local join to element storage
     147             : 
     148             :      // mymap_idx_query finds the element corresponding to key.  Assumes
     149             :      // there are no concurrent operations on the map and that *key will
     150             :      // not be modified during the query.  The map retains no interest
     151             :      // in key.  On success, the returned index lifetime will be at
     152             :      // least as long as the corresponding element is still in the map.
     153             :      // On failure, the returned index lifetime will be that of the
     154             :      // sentinel.
     155             : 
     156             :      ulong                                    // Index of found element on success, sentinel on failure
     157             :      mymap_idx_query( mymap_t *     join,     // Current local join to the element map
     158             :                       ulong const * key,      // Points to the key to find in the caller's address space
     159             :                       ulong         sentinel, // Value to return on failure
     160             :                       myele_t *     pool );   // Current local join to element storage
     161             : 
     162             :      // mymap_idx_query_const is the same as mymap_idx_query but
     163             :      // supports concurrent queries so long as there no concurrently
     164             :      // running insert/remove/query operations.  The value fields of the
     165             :      // element returned by this function can be changed by the
     166             :      // application but it is up to the application to manage
     167             :      // concurrency between different users modifying the same element.
     168             : 
     169             :      ulong                                            // Index of found element on success, sentinel on failure
     170             :      mymap_idx_query_const( mymap_t const * join,     // Current local join to element map
     171             :                             ulong const *   key,      // Points to the key to find in the caller's address space
     172             :                             ulong           sentinel, // Value to return on failure
     173             :                             myele_t const * pool );   // Current local join to element storage
     174             : 
     175             :      // The mymap_ele_{insert,remove,query,query_const} variants are the
     176             :      // same as the above but use pointers in the caller's address
     177             :      // instead of pool element storage indices.
     178             : 
     179             :      mymap_t *                           // Returns join
     180             :      mymap_ele_insert( mymap_t * join,   // Current local join to element map
     181             :                        myele_t * ele,    // Element to insert (assumed to be in pool)
     182             :                        myele_t * pool ); // Current local join to element storage
     183             : 
     184             :      myele_t *                                 // Removed element on success (will be from pool), sentinel on failure
     185             :      mymap_ele_remove( mymap_t *     join,     // Current local join to element map
     186             :                        ulong const * key,      // Points to the key to remove in the caller's address space
     187             :                        myele_t *     sentinel, // Value to return if key not in map
     188             :                        myele_t *     pool );   // Current local join to element storage
     189             : 
     190             :      myele_t *                                // Found element on success (will be from pool), sentinel on failure
     191             :      mymap_ele_query( mymap_t *     join,     // Current local join to element map
     192             :                       ulong const * key,      // Points to the key to find in the caller's address space
     193             :                       myele_t *     sentinel, // Value to return if key not in map
     194             :                       myele_t *     pool );   // Current local join to element storage
     195             : 
     196             :      myele_t const *                                  // Found element on success (will be from pool), sentinel on failure
     197             :      mymap_ele_query_const( mymap_t const * join,     // Current local join to element map
     198             :                             ulong const *   key,      // Points to the key to find in the caller's address space
     199             :                             myele_t const * sentinel, // Value to return if key not in map
     200             :                             myele_t const * pool );   // Current local join to element storage
     201             : 
     202             :      // mymap_iter_* support fast iteration over all the elements in a
     203             :      // map.  The iteration will be in a random order but the order will
     204             :      // be identical if repeated with no insert/remove/query operations
     205             :      // done in between.  Assumes no concurrent insert/remove/query
     206             :      // operations (query_const is fine).  Example usage:
     207             :      //
     208             :      //   for( mymap_iter_t iter = mymap_iter_init( join, pool );
     209             :      //        !mymap_iter_done( iter, join, pool );
     210             :      //        iter = mymap_iter_next( iter, join, pool ) ) {
     211             :      //     ulong ele_idx = mymap_iter_idx( iter, join, pool );
     212             :      //
     213             :      //     ... process element here
     214             :      //
     215             :      //     ... IMPORTANT!  It is _not_ _safe_ to insert, remove
     216             :      //     ... or query here (query_const is fine).
     217             :      //   }
     218             : 
     219             :      struct mymap_iter_private { ... internal use only ... };
     220             :      typedef struct mymap_iter_private mymap_iter_t;
     221             : 
     222             :      mymap_iter_t    mymap_iter_init     (                    mymap_t const * join, myele_t const * pool );
     223             :      int             mymap_iter_done     ( mymap_iter_t iter, mymap_t const * join, myele_t const * pool );
     224             :      mymap_iter_t    mymap_iter_next     ( mymap_iter_t iter, mymap_t const * join, myele_t const * pool ); // assumes not done
     225             :      ulong           mymap_iter_idx      ( mymap_iter_t iter, mymap_t const * join, myele_t const * pool ); // assumes not done
     226             :      myele_t *       mymap_iter_ele      ( mymap_iter_t iter, mymap_t const * join, myele_t *       pool ); // assumes not done
     227             :      myele_t const * mymap_iter_ele_const( mymap_iter_t iter, mymap_t const * join, myele_t const * pool ); // assumes not done
     228             : 
     229             :      // mymap_verify returns 0 if the mymap is not obviously corrupt or
     230             :      // -1 (i.e. ERR_INVAL) otherwise (logs details).
     231             : 
     232             :      int
     233             :      mymap_verify( mymap_t const * join,    // Current local join to a mymap.
     234             :                    ulong           ele_cnt, // Element storage size, in [0,mymap_ele_max()]
     235             :                    myele_t const * pool );  // Current local join to element storage, indexed [0,ele_cnt)
     236             : 
     237             :    You can do this as often as you like in a compilation unit to get
     238             :    different types of maps.  Variants exist for making header prototypes
     239             :    only and/or implementations if doing a library with multiple
     240             :    compilation units.  Further, options exist to use index compression,
     241             :    different hashing functions, comparison functions, etc as detailed
     242             :    below.
     243             : 
     244             :    If MAP_MULTI is defined to be 1, the map will support multiple
     245             :    entries for the same key. In this case, the existing API works as
     246             :    is, but new methods are provided:
     247             : 
     248             :      ulong                                           // Index of found element on success, sentinel on failure
     249             :      mymap_idx_next_const( ulong           prev,     // Previous result of mymap_idx_query_const
     250             :                            ulong           sentinel, // Value to return on failure
     251             :                            myele_t const * pool );   // Current local join to element storage
     252             : 
     253             :      myele_t const *                                 // Found element on success (will be from pool), sentinel on failure
     254             :      mymap_ele_next_const( myele_t const * prev,     // Previous result of mymap_ele_query_const
     255             :                            myele_t const * sentinel, // Value to return if key not in map
     256             :                            myele_t const * pool );   // Current local join to element storage
     257             : 
     258             :    These take a previous result from query_const (or next_const) and
     259             :    return the next element with the same key in the chain.
     260             : 
     261             :   IF MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL is defined to be 1, the map will
     262             :   support removing elements with a known index from the chain in O(1)
     263             :   time without needing to search for them in the chain.  This requires
     264             :   threading a reverse pointer through the elements in the chain.
     265             : 
     266             :     void
     267             :     mymap_idx_remove_fast( mymap_t * join,    // Current uslocal join to element map
     268             :                            ulong     ele_idx, // Index of element to remove in the element storage
     269             :                            myele_t * pool );  // Current local join to element storage
     270             : 
     271             : */
     272             : 
     273             : #include "fd_map.h"
     274             : 
     275             : /* MAP_NAME gives the API prefix to use for map */
     276             : 
     277             : #ifndef MAP_NAME
     278             : #error "Define MAP_NAME"
     279             : #endif
     280             : 
     281             : /* MAP_ELE_T is the map element type. */
     282             : 
     283             : #ifndef MAP_ELE_T
     284             : #error "Define MAP_ELE_T"
     285             : #endif
     286             : 
     287             : /* MAP_KEY_T is the map key type */
     288             : 
     289             : #ifndef MAP_KEY_T
     290             : #define MAP_KEY_T ulong
     291             : #endif
     292             : 
     293             : /* MAP_KEY is the MAP_ELE_T key field */
     294             : 
     295             : #ifndef MAP_KEY
     296     7340799 : #define MAP_KEY key
     297             : #endif
     298             : 
     299             : /* MAP_IDX_T is the type used for the next field in the MAP_ELE_T.
     300             :    Should be a primitive unsigned integer type.  Defaults to ulong.  A
     301             :    map can't use element stores with more elements than the maximum
     302             :    value that can be represented by a MAP_IDX_T.  (E.g. if ushort, the
     303             :    maximum size element store usable by the map is 65535 elements.) */
     304             : 
     305             : #ifndef MAP_IDX_T
     306        9003 : #define MAP_IDX_T ulong
     307             : #endif
     308             : 
     309             : /* MAP_NEXT is the MAP_ELE_T next field */
     310             : 
     311             : #ifndef MAP_NEXT
     312   708045384 : #define MAP_NEXT next
     313             : #endif
     314             : 
     315             : /* If we're using the optimized random access removal, then we also need
     316             :    a MAP_ELE_T prev field. */
     317             : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
     318             : #  ifndef MAP_PREV
     319     4484523 : #    define MAP_PREV prev
     320             : #  endif
     321             : #endif
     322             : 
     323             : /* MAP_KEY_EQ returns 0/1 if *k0 is the same/different as *k1 */
     324             : 
     325             : #ifndef MAP_KEY_EQ
     326  5661241098 : #define MAP_KEY_EQ(k0,k1) ((*(k0))==(*(k1)))
     327             : #endif
     328             : 
     329             : /* MAP_KEY_HASH maps *key into ulong uniform pseudo randomly. */
     330             : 
     331             : #ifndef MAP_KEY_HASH
     332    10967787 : #define MAP_KEY_HASH(key,seed) fd_ulong_hash( (*(key)) ^ (seed) )
     333             : #endif
     334             : 
     335             : /* MAP_MAGIC is the magic number to use for the structure to aid in
     336             :    persistent and or IPC usage. */
     337             : 
     338             : #ifndef MAP_MAGIC
     339        1389 : #define MAP_MAGIC (0xf17eda2c37c3a900UL) /* firedancer cmap version 0 */
     340             : #endif
     341             : 
     342             : /* 0 - local use only
     343             :    1 - library header declaration
     344             :    2 - library implementation */
     345             : 
     346             : #ifndef MAP_IMPL_STYLE
     347             : #define MAP_IMPL_STYLE 0
     348             : #endif
     349             : 
     350             : /* 0 - do NOT support multiple values with the same key
     351             :    1 - support multiple values with the same key */
     352             : 
     353             : #ifndef MAP_MULTI
     354             : #define MAP_MULTI 0
     355             : #endif
     356             : 
     357             : /* MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL controls whether the map supports
     358             :    removal of an element in a chain without iterating the whole chain
     359             :    from the beginning. */
     360             : 
     361             : #ifndef MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
     362             : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 0
     363             : #endif
     364             : 
     365             : /* MAP_INSERT_FENCE prevents the compiler from reordering the two
     366             :    operations: setting the next pointer of the new chain head and
     367             :    updating the chain head. */
     368             : 
     369             : #ifndef MAP_INSERT_FENCE
     370             : #define MAP_INSERT_FENCE 0
     371             : #endif
     372             : 
     373             : /* Implementation *****************************************************/
     374             : 
     375             : /* Constructors and verification log details on failure (rest only needs
     376             :    fd_bits.h, consider making logging a compile time option). */
     377             : 
     378             : #include "../log/fd_log.h"
     379             : 
     380 >17431*10^7 : #define MAP_(n) FD_EXPAND_THEN_CONCAT3(MAP_NAME,_,n)
     381             : 
     382             : #if MAP_IMPL_STYLE==0 || MAP_IMPL_STYLE==1 /* need structures and inlines */
     383             : 
     384             : struct MAP_(private) {
     385             : 
     386             :   /* join points here */
     387             : 
     388             :   /* FIXME: consider having an ele_cnt for number of elements in the
     389             :      underlying storage? (probably not) consider having a memo of the
     390             :      chain in which an element is stored and/or using doubly linked
     391             :      chains?  We could do a faster remove by index then. */
     392             : 
     393             :   ulong magic;     /* == MAP_MAGIC */
     394             :   ulong seed;      /* Hash seed, arbitrary */
     395             :   ulong chain_cnt; /* Number of chains, positive integer power-of-two */
     396             : 
     397             :   /* MAP_IDX_T chain[ chain_cnt ] here */
     398             : 
     399             : };
     400             : 
     401             : typedef struct MAP_(private) MAP_(private_t);
     402             : 
     403             : typedef MAP_(private_t) MAP_(t);
     404             : 
     405             : typedef struct fd_map_chain_iter MAP_(iter_t);
     406             : 
     407             : FD_PROTOTYPES_BEGIN
     408             : 
     409             : /* map_private returns the location of the map private for a current
     410             :    local join.  Assumes join is a current local join.  map_private_const
     411             :    is a const correct version. */
     412             : 
     413  1262450436 : FD_FN_CONST static inline MAP_(private_t) *       MAP_(private)      ( MAP_(t) *       join ) { return join; }
     414  2936902327 : FD_FN_CONST static inline MAP_(private_t) const * MAP_(private_const)( MAP_(t) const * join ) { return join; }
     415             : 
     416             : /* map_private_chain returns the location in the caller's address space
     417             :    of the map chains.  Assumes map is valid.  map_private_chain_const is
     418             :    a const correct version. */
     419             : 
     420             : FD_FN_CONST static inline MAP_IDX_T *
     421  1261807951 : MAP_(private_chain)( MAP_(private_t) * map ) {
     422  1261807951 :   return (MAP_IDX_T *)(map+1);
     423  1261807951 : }
     424             : 
     425             : FD_FN_CONST static inline MAP_IDX_T const *
     426  2936902309 : MAP_(private_chain_const)( MAP_(private_t) const * map ) {
     427  2936902309 :   return (MAP_IDX_T const *)(map+1);
     428  2936902309 : }
     429             : 
     430             : /* map_private_chain_idx returns the index of the chain (in
     431             :    [0,chain_cnt) that will contain the element corresponding to key (if
     432             :    present at all) for a map with chain_cnt elements and seed.  Assumes
     433             :    chain_cnt is an integer power-of-two.  Assumes key points to a key is
     434             :    in the caller's address space that will not be changed concurrently.
     435             :    Retains no interest in key on return. */
     436             : 
     437             : FD_FN_PURE static inline ulong
     438             : MAP_(private_chain_idx)( MAP_KEY_T const * key,
     439             :                          ulong             seed,
     440  5560770220 :                          ulong             chain_cnt ) {
     441  5560770220 :   return (MAP_KEY_HASH( (key), (seed) )) & (chain_cnt-1UL);
     442  5560770220 : }
     443             : 
     444             : /* map_private_{box,unbox} compress / decompress 64-bit in-register
     445             :    indices to/from their in-memory representations. */
     446             : 
     447   374779840 : FD_FN_CONST static inline MAP_IDX_T MAP_(private_box)  ( ulong     idx  ) { return (MAP_IDX_T)idx;  }
     448 66015103895 : FD_FN_CONST static inline ulong     MAP_(private_unbox)( MAP_IDX_T cidx ) { return (ulong)    cidx; }
     449             : 
     450             : /* map_private_idx_null returns the element storage index that
     451             :    represents NULL. */
     452             : 
     453 29362319853 : FD_FN_CONST static inline ulong MAP_(private_idx_null)( void ) { return (ulong)(MAP_IDX_T)(~0UL); }
     454             : 
     455             : /* map_private_idx_is_null returns 1 if idx is the NULL map index
     456             :    and 0 otherwise. */
     457             : 
     458 68328791888 : FD_FN_CONST static inline int MAP_(private_idx_is_null)( ulong idx ) { return idx==(ulong)(MAP_IDX_T)(~0UL); }
     459             : 
     460    14479419 : FD_FN_CONST static inline ulong MAP_(ele_max)( void ) { return (ulong)(MAP_IDX_T)(~0UL); }
     461             : 
     462             : FD_FN_CONST static inline ulong
     463    14484870 : MAP_(chain_max)( void ) {
     464    14484870 :   return fd_ulong_pow2_dn( (ULONG_MAX + 1UL - alignof(MAP_(t)) - sizeof(MAP_(t))) / sizeof(MAP_IDX_T) );
     465    14484870 : }
     466             : 
     467             : FD_FN_CONST static inline ulong
     468     6003474 : MAP_(chain_cnt_est)( ulong ele_max_est ) {
     469             : 
     470             :   /* Clamp to be in [1,ele_max] (as ele_max_est 0 is degenerate and as
     471             :      the map is guaranteed to hold at most ele_max keys). */
     472             : 
     473     6003474 :   ele_max_est = fd_ulong_min( fd_ulong_max( ele_max_est, 1UL ), MAP_(ele_max)() );
     474             : 
     475             :   /* Compute the number of chains as the power of 2 that makes the
     476             :      average chain length between ~1 and ~2 when ele_max_est are stored
     477             :      in the map and then clamp to the chain max. */
     478             : 
     479     6003474 :   ulong chain_min = (ele_max_est>>1) + (ele_max_est&1UL); /* chain_min = ceil(ele_max_est/2), in [1,2^63], computed w/o overflow */
     480     6003474 :   ulong chain_cnt = fd_ulong_pow2_up( chain_min );        /* Power of 2 in [1,2^63] */
     481             : 
     482     6003474 :   return fd_ulong_min( chain_cnt, MAP_(chain_max)() );
     483     6003474 : }
     484             : 
     485          12 : FD_FN_PURE static inline ulong MAP_(chain_cnt)( MAP_(t) const * join ) { return MAP_(private_const)( join )->chain_cnt; }
     486           6 : FD_FN_PURE static inline ulong MAP_(seed)     ( MAP_(t) const * join ) { return MAP_(private_const)( join )->seed;      }
     487             : 
     488             : FD_FN_PURE static inline int
     489             : MAP_(key_eq)( MAP_KEY_T const * k0,
     490  6053777492 :               MAP_KEY_T const * k1 ) {
     491  6053777492 :   return !!(MAP_KEY_EQ( (k0), (k1) ));
     492  6053777492 : }
     493             : 
     494             : FD_FN_PURE static inline ulong
     495             : MAP_(key_hash)( MAP_KEY_T const * key,
     496     6001038 :                 ulong             seed ) {
     497     6001038 :   return (MAP_KEY_HASH( (key), (seed) ));
     498     6001038 : }
     499             : 
     500             : FD_FN_PURE static inline MAP_(iter_t)
     501             : MAP_(iter_init)( MAP_(t) const *   join,
     502     3078948 :                  MAP_ELE_T const * pool ) {
     503     3078948 :   (void)pool;
     504             : 
     505     3078948 :   MAP_(private_t) const * map   = MAP_(private_const)( join );
     506     3078948 :   MAP_IDX_T const *       chain = MAP_(private_chain_const)( map );
     507             : 
     508             :   /* Find first element.  If the map is empty, chain_rem will be 0 and
     509             :      ele_idx will be idx_null. */
     510             : 
     511     3078948 :   ulong chain_rem = map->chain_cnt; /* At least 1 */
     512     3078948 :   ulong ele_idx;
     513    16161364 :   do {
     514    16161364 :     ele_idx = MAP_(private_unbox)( chain[ chain_rem-1UL ] );
     515    16161364 :     if( !MAP_(private_idx_is_null)( ele_idx ) ) break;
     516    16161364 :   } while( --chain_rem );
     517             : 
     518     3078948 :   MAP_(iter_t) iter;
     519     3078948 :   iter.chain_rem = chain_rem;
     520     3078948 :   iter.ele_idx   = ele_idx;
     521     3078948 :   return iter;
     522     3078948 : }
     523             : 
     524             : FD_FN_CONST static inline int
     525             : MAP_(iter_done)( MAP_(iter_t)      iter,
     526             :                  MAP_(t) const *   join,
     527   791047527 :                  MAP_ELE_T const * pool ) {
     528   791047527 :   (void)join; (void)pool;
     529   791047527 :   return !iter.chain_rem;
     530   791047527 : }
     531             : 
     532             : FD_FN_PURE static inline MAP_(iter_t)
     533             : MAP_(iter_next)( MAP_(iter_t)      iter,
     534             :                  MAP_(t) const *   join,
     535   787968579 :                  MAP_ELE_T const * pool ) {
     536             : # if FD_TMPL_USE_HANDHOLDING
     537             :   if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
     538             : # endif
     539   787968579 :   ulong chain_rem = iter.chain_rem;
     540   787968579 :   ulong ele_idx   = iter.ele_idx;
     541             : 
     542             :   /* At this point, we are just finished iterating over element ele_idx
     543             :      on chain chain_rem-1 and we already iterated over all elements in
     544             :      chains (chain_rem,chain_cnt] and all elements in chain chain_rem-1
     545             :      before this element.  As such, ele_idx is in [0,ele_cnt) and
     546             :      chain_rem is in (0,chain_cnt].  Get the next element in the chain
     547             :      chain_rem-1. */
     548             : 
     549   787968579 :   ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT );
     550   787968579 :   if( MAP_(private_idx_is_null)( ele_idx ) ) {
     551             : 
     552             :     /* There were no more elements in chain chain_rem-1.  Find the next
     553             :        chain to start processing.  If all unprocessed chains are empty,
     554             :        then we are done. */
     555             : 
     556   380909872 :     MAP_IDX_T const * chain = MAP_(private_chain_const)( MAP_(private_const)( join ) );
     557   782070407 :     while( --chain_rem ) {
     558   778998116 :       ele_idx = MAP_(private_unbox)( chain[ chain_rem-1UL ] );
     559   778998116 :       if( !MAP_(private_idx_is_null)( ele_idx ) ) break;
     560   778998116 :     }
     561             : 
     562   380909872 :   }
     563             : 
     564   787968579 :   iter.chain_rem = chain_rem;
     565   787968579 :   iter.ele_idx   = ele_idx;
     566   787968579 :   return iter;
     567   787968579 : }
     568             : 
     569             : FD_FN_CONST static inline ulong
     570             : MAP_(iter_idx)( MAP_(iter_t)    iter,
     571             :                 MAP_(t) const * join,
     572   787968096 :                 MAP_ELE_T *     pool ) {
     573             : # if FD_TMPL_USE_HANDHOLDING
     574             :   if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
     575             : # endif
     576   787968096 :   (void)join; (void)pool;
     577   787968096 :   return iter.ele_idx;
     578   787968096 : }
     579             : 
     580             : FD_FN_CONST static inline MAP_ELE_T *
     581             : MAP_(iter_ele)( MAP_(iter_t)    iter,
     582             :                 MAP_(t) const * join,
     583   787968012 :                 MAP_ELE_T *     pool ) {
     584             : # if FD_TMPL_USE_HANDHOLDING
     585             :   if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
     586             : # endif
     587   787968012 :   (void)join;
     588   787968012 :   return pool + iter.ele_idx;
     589   787968012 : }
     590             : 
     591             : FD_FN_CONST static inline MAP_ELE_T const *
     592             : MAP_(iter_ele_const) ( MAP_(iter_t)      iter,
     593             :                        MAP_(t) const *   join,
     594   787968048 :                        MAP_ELE_T const * pool ) {
     595             : # if FD_TMPL_USE_HANDHOLDING
     596             :   if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
     597             : # endif
     598   787968048 :   (void)join;
     599   787968048 :   return pool + iter.ele_idx;
     600   787968048 : }
     601             : 
     602             : FD_PROTOTYPES_END
     603             : 
     604             : #endif
     605             : 
     606             : #if MAP_IMPL_STYLE==1 /* need prototypes */
     607             : 
     608             : FD_PROTOTYPES_BEGIN
     609             : 
     610             : FD_FN_CONST ulong MAP_(align)    ( void );
     611             : FD_FN_CONST ulong MAP_(footprint)( ulong chain_cnt );
     612             : void *            MAP_(new)      ( void * shmem, ulong chain_cnt, ulong seed );
     613             : MAP_(t) *         MAP_(join)     ( void * shmap );
     614             : void *            MAP_(leave)    ( MAP_(t) * join );
     615             : void *            MAP_(delete)   ( void * shmap );
     616             : 
     617             : void              MAP_(reset)    ( MAP_(t) * join );
     618             : 
     619             : MAP_(t) *
     620             : MAP_(idx_insert)( MAP_(t) *   join,
     621             :                   ulong       ele_idx,
     622             :                   MAP_ELE_T * pool );
     623             : 
     624             : ulong
     625             : MAP_(idx_remove)( MAP_(t) *         join,
     626             :                   MAP_KEY_T const * key,
     627             :                   ulong             sentinel,
     628             :                   MAP_ELE_T *       pool );
     629             : 
     630             : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
     631             : void
     632             : MAP_(idx_remove_fast)( MAP_(t) *   join,
     633             :                        ulong       ele_idx,
     634             :                        MAP_ELE_T * pool );
     635             : 
     636             : MAP_ELE_T *
     637             : MAP_(ele_remove_fast)( MAP_(t) *   join,
     638             :                        MAP_ELE_T * ele,
     639             :                        MAP_ELE_T * pool  );
     640             : #endif
     641             : 
     642             : FD_FN_PURE ulong
     643             : MAP_(idx_query)( MAP_(t) *         join,
     644             :                  MAP_KEY_T const * key,
     645             :                  ulong             sentinel,
     646             :                  MAP_ELE_T *       pool );
     647             : 
     648             : FD_FN_PURE ulong
     649             : MAP_(idx_query_const)( MAP_(t) const *   join,
     650             :                        MAP_KEY_T const * key,
     651             :                        ulong             sentinel,
     652             :                        MAP_ELE_T const * pool );
     653             : 
     654             : #if MAP_MULTI!=0
     655             : 
     656             : FD_FN_PURE ulong
     657             : MAP_(idx_next_const)( ulong             prev,     // Previous result of mymap_idx_query_const
     658             :                       ulong             sentinel, // Value to return on failure
     659             :                       MAP_ELE_T const * pool );   // Current local join to element storage
     660             : 
     661             : #endif /* MAP_MULTI!=0 */
     662             : 
     663             : int
     664             : MAP_(verify)( MAP_(t) const *   join,
     665             :               ulong             ele_cnt,
     666             :               MAP_ELE_T const * pool );
     667             : 
     668             : FD_PROTOTYPES_END
     669             : 
     670             : #else /* need implementations */
     671             : 
     672             : #if MAP_IMPL_STYLE==0 /* local only */
     673             : #define MAP_IMPL_STATIC FD_FN_UNUSED static
     674             : #else
     675             : #define MAP_IMPL_STATIC
     676             : #endif
     677             : 
     678       13080 : FD_FN_CONST MAP_IMPL_STATIC ulong MAP_(align)( void ) { return alignof(MAP_(t)); }
     679             : 
     680             : FD_FN_CONST MAP_IMPL_STATIC ulong
     681        5463 : MAP_(footprint)( ulong chain_cnt ) {
     682        5463 :   if( !(fd_ulong_is_pow2( chain_cnt ) & (chain_cnt<=MAP_(chain_max)())) ) return 0UL;
     683        5427 :   return fd_ulong_align_up( sizeof(MAP_(t)) + chain_cnt*sizeof(MAP_IDX_T), alignof(MAP_(t)) ); /* no overflow */
     684        5463 : }
     685             : 
     686             : MAP_IMPL_STATIC void *
     687             : MAP_(new)( void * shmap,
     688             :            ulong  chain_cnt,
     689        1419 :            ulong  seed ) {
     690             : 
     691        1419 :   if( FD_UNLIKELY( !shmap ) ) {
     692           6 :     FD_LOG_WARNING(( "NULL shmap" ));
     693           6 :     return NULL;
     694           6 :   }
     695             : 
     696        1413 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmap, MAP_(align)() ) ) ) {
     697           6 :     FD_LOG_WARNING(( "misaligned shmap" ));
     698           6 :     return NULL;
     699           6 :   }
     700             : 
     701        1407 :   ulong footprint = MAP_(footprint)( chain_cnt );
     702        1407 :   if( FD_UNLIKELY( !footprint ) ) {
     703          18 :     FD_LOG_WARNING(( "bad footprint" ));
     704          18 :     return NULL;
     705          18 :   }
     706             : 
     707             :   /* seed is arbitrary */
     708             : 
     709             :   /* Init the metadata */
     710             : 
     711        1389 :   MAP_(private_t) * map = (MAP_(private_t) *)shmap;
     712             : 
     713        1389 :   map->seed      = seed;
     714        1389 :   map->chain_cnt = chain_cnt;
     715             : 
     716             :   /* Set all the chains to NULL */
     717             : 
     718        1389 :   MAP_IDX_T * chain = MAP_(private_chain)( map );
     719    38451381 :   for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) chain[ chain_idx ] = MAP_(private_box)( MAP_(private_idx_null)() );
     720             : 
     721        1389 :   FD_COMPILER_MFENCE();
     722        1389 :   FD_VOLATILE( map->magic ) = MAP_MAGIC;
     723        1389 :   FD_COMPILER_MFENCE();
     724             : 
     725        1389 :   return shmap;
     726        1407 : }
     727             : 
     728             : MAP_IMPL_STATIC MAP_(t) *
     729        1851 : MAP_(join)( void * shmap ) {
     730        1851 :   MAP_(private_t) * map = (MAP_(private_t) *)shmap;
     731             : 
     732        1851 :   if( FD_UNLIKELY( !map ) ) {
     733           6 :     FD_LOG_WARNING(( "NULL shmap" ));
     734           6 :     return NULL;
     735           6 :   }
     736             : 
     737        1845 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) ) ) {
     738           6 :     FD_LOG_WARNING(( "misaligned shmap" ));
     739           6 :     return NULL;
     740           6 :   }
     741             : 
     742        1839 :   if( FD_UNLIKELY( map->magic!=MAP_MAGIC ) ) {
     743           6 :     FD_LOG_WARNING(( "bad magic" ));
     744           6 :     return NULL;
     745           6 :   }
     746             : 
     747        1833 :   return (MAP_(t) *)map;
     748        1839 : }
     749             : 
     750             : MAP_IMPL_STATIC void *
     751          15 : MAP_(leave)( MAP_(t) * join ) {
     752             : 
     753          15 :   if( FD_UNLIKELY( !join ) ) {
     754           6 :     FD_LOG_WARNING(( "NULL join" ));
     755           6 :     return NULL;
     756           6 :   }
     757             : 
     758           9 :   return (void *)join;
     759          15 : }
     760             : 
     761             : MAP_IMPL_STATIC void *
     762          27 : MAP_(delete)( void * shmap ) {
     763          27 :   MAP_(private_t) * map = (MAP_(private_t) *)shmap;
     764             : 
     765          27 :   if( FD_UNLIKELY( !map ) ) {
     766           6 :     FD_LOG_WARNING(( "NULL shmap" ));
     767           6 :     return NULL;
     768           6 :   }
     769             : 
     770          21 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) ) ) {
     771           6 :     FD_LOG_WARNING(( "misaligned shmap" ));
     772           6 :     return NULL;
     773           6 :   }
     774             : 
     775          15 :   if( FD_UNLIKELY( map->magic!=MAP_MAGIC ) ) {
     776           6 :     FD_LOG_WARNING(( "bad magic" ));
     777           6 :     return NULL;
     778           6 :   }
     779             : 
     780           9 :   FD_COMPILER_MFENCE();
     781           9 :   FD_VOLATILE( map->magic ) = 0UL;
     782           9 :   FD_COMPILER_MFENCE();
     783             : 
     784           9 :   return shmap;
     785          15 : }
     786             : 
     787             : MAP_IMPL_STATIC void
     788           0 : MAP_(reset)( MAP_(t) * join ) {
     789           0 :   MAP_(private_t) * map = MAP_(private)( join );
     790             : 
     791           0 :   MAP_IDX_T * chain = MAP_(private_chain)( map );
     792           0 :   for( ulong chain_idx=0UL; chain_idx<map->chain_cnt; chain_idx++ ) chain[ chain_idx ] = MAP_(private_box)( MAP_(private_idx_null)() );
     793           0 : }
     794             : 
     795             : FD_FN_PURE MAP_IMPL_STATIC ulong
     796             : MAP_(idx_query)( MAP_(t) *         join,
     797             :                  MAP_KEY_T const * key,
     798             :                  ulong             sentinel,
     799  1216082295 :                  MAP_ELE_T *       pool ) {
     800  1216082295 :   MAP_(private_t) * map = MAP_(private)( join );
     801             : 
     802             :   /* Find the key */
     803             : 
     804  1216082295 :   MAP_IDX_T * head = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
     805  1216082295 :   MAP_IDX_T * cur  = head;
     806  2132154465 :   for(;;) {
     807  2132154465 :     ulong ele_idx = MAP_(private_unbox)( *cur );
     808  2132154465 :     if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
     809  1335170517 :     if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) { /* optimize for found */
     810             :       /* Found, move it to the front of the chain */
     811   419098347 :       if( FD_UNLIKELY( cur!=head ) ) { /* Assume already at head from previous query */
     812             : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
     813       84255 :         if( FD_UNLIKELY( !MAP_(private_idx_is_null)( pool[ ele_idx ].MAP_NEXT ) ) ) pool[ pool[ ele_idx ].MAP_NEXT ].MAP_PREV = pool[ ele_idx ].MAP_PREV;
     814       84255 :         pool[ ele_idx ].MAP_PREV = MAP_(private_box)( MAP_(private_idx_null)() );
     815       84255 :         pool[ *head   ].MAP_PREV = MAP_(private_box)( ele_idx );
     816             : #endif
     817   289887987 :         *cur = pool[ ele_idx ].MAP_NEXT;
     818   289887987 :         pool[ ele_idx ].MAP_NEXT = *head;
     819   289887987 :         *head = MAP_(private_box)( ele_idx );
     820   289887987 :       }
     821   419098347 :       return ele_idx;
     822   419098347 :     }
     823   916072170 :     cur = &pool[ ele_idx ].MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
     824   916072170 :   }
     825             : 
     826             :   /* Not found */
     827             : 
     828   796983948 :   return sentinel;
     829  1216082295 : }
     830             : 
     831             : MAP_IMPL_STATIC MAP_(t) *
     832             : MAP_(idx_insert)( MAP_(t) *   join,
     833             :                   ulong       ele_idx,
     834    20887497 :                   MAP_ELE_T * pool ) {
     835             : # if FD_TMPL_USE_HANDHOLDING && !MAP_MULTI
     836             :   if( FD_UNLIKELY( !MAP_(private_idx_is_null)( MAP_(idx_query)( join, &pool[ ele_idx ].MAP_KEY, MAP_(private_idx_null)(), pool ) ) ) ) {
     837             :     FD_LOG_CRIT(( "ele_idx already in map" ));
     838             :   }
     839             : # endif
     840    20887497 :   MAP_(private_t) * map = MAP_(private)( join );
     841             : 
     842    20887497 :   MAP_IDX_T * head = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( &pool[ ele_idx ].MAP_KEY, map->seed, map->chain_cnt );
     843             : 
     844             : # if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
     845    17332695 :   if( FD_UNLIKELY( !MAP_(private_idx_is_null)( *head ) ) ) pool[ *head ].MAP_PREV = MAP_(private_box)( ele_idx );
     846    17332695 :   pool[ ele_idx ].MAP_PREV = MAP_(private_box)( MAP_(private_idx_null)() );
     847             : # endif
     848    20887497 :   pool[ ele_idx ].MAP_NEXT = *head;
     849             : # if MAP_INSERT_FENCE
     850          51 :   FD_COMPILER_MFENCE();
     851             : # endif
     852    20887497 :   *head = MAP_(private_box)( ele_idx );
     853             : 
     854    20887497 :   return join;
     855    20887497 : }
     856             : 
     857             : MAP_IMPL_STATIC ulong
     858             : MAP_(idx_remove)( MAP_(t) *         join,
     859             :                   MAP_KEY_T const * key,
     860             :                   ulong             sentinel,
     861     8171070 :                   MAP_ELE_T *       pool ) {
     862     8171070 :   MAP_(private_t) * map = MAP_(private)( join );
     863             : 
     864             :   /* Find the key */
     865             : 
     866     8171070 :   MAP_IDX_T * cur = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
     867    12298869 :   for(;;) {
     868    12298869 :     ulong ele_idx = MAP_(private_unbox)( *cur );
     869    12298869 :     if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found (it is remove after all) */
     870     7680468 :     if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) { /* " */
     871     3552669 :       *cur = pool[ ele_idx ].MAP_NEXT;
     872             : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
     873          24 :     if( FD_UNLIKELY( !MAP_(private_idx_is_null)( pool[ ele_idx ].MAP_NEXT ) ) ) pool[ pool[ ele_idx ].MAP_NEXT ].MAP_PREV = pool[ ele_idx ].MAP_PREV;
     874             : #endif
     875     3552669 :       return ele_idx;
     876     3552669 :     }
     877     4127799 :     cur = &pool[ ele_idx ].MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
     878     4127799 :   }
     879             : 
     880             :   /* Not found */
     881             : 
     882     4618401 :   return sentinel;
     883     8171070 : }
     884             : 
     885             : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
     886             : MAP_IMPL_STATIC void
     887             : MAP_(idx_remove_fast)( MAP_(t) *   join,
     888             :                        ulong       ele_idx,
     889    17309574 :                        MAP_ELE_T * pool ) {
     890    17309574 :   MAP_(private_t) * map = MAP_(private)( join );
     891             : 
     892    17309574 :   MAP_ELE_T * ele = pool+ele_idx;
     893             : 
     894    17309574 :   if( FD_UNLIKELY( !MAP_(private_idx_is_null)( ele->MAP_NEXT ) ) )          pool[ ele->MAP_NEXT ].MAP_PREV = ele->MAP_PREV;
     895             : 
     896    17309574 :   if( FD_UNLIKELY( !MAP_(private_idx_is_null)( ele->MAP_PREV ) ) )          pool[ ele->MAP_PREV ].MAP_NEXT = ele->MAP_NEXT;
     897    16665694 :   else { MAP_(private_chain)( map )[ MAP_(private_chain_idx)( &ele->MAP_KEY, map->seed, map->chain_cnt ) ] = ele->MAP_NEXT; }
     898    17309574 : }
     899             : 
     900             : MAP_IMPL_STATIC MAP_ELE_T *
     901             : MAP_(ele_remove_fast)( MAP_(t) *   join,
     902             :                        MAP_ELE_T * ele,
     903    13583244 :                        MAP_ELE_T * pool  ) {
     904    13583244 :   MAP_(idx_remove_fast)( join, (ulong)(ele-pool), pool );
     905    13583244 :   return ele;
     906    13583244 : }
     907             : #endif
     908             : 
     909             : FD_FN_PURE MAP_IMPL_STATIC ulong
     910             : MAP_(idx_query_const)( MAP_(t) const *   join,
     911             :                        MAP_KEY_T const * key,
     912             :                        ulong             sentinel,
     913  2544437562 :                        MAP_ELE_T const * pool ) {
     914  2544437562 :   MAP_(private_t) const * map = MAP_(private_const)( join );
     915             : 
     916             :   /* Find the key */
     917             : 
     918  2544437562 :   MAP_IDX_T const * cur = MAP_(private_chain_const)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
     919  3760619423 :   for(;;) {
     920  3760619423 :     ulong ele_idx = MAP_(private_unbox)( *cur );
     921  3760619423 :     if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
     922  3758677844 :     if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) return ele_idx; /* optimize for found */
     923  1216181861 :     cur = &pool[ ele_idx ].MAP_NEXT;
     924  1216181861 :   }
     925             : 
     926             :   /* Not found */
     927             : 
     928     1941579 :   return sentinel;
     929  2544437562 : }
     930             : 
     931             : #if MAP_MULTI!=0
     932             : 
     933             : FD_FN_PURE MAP_IMPL_STATIC ulong
     934             : MAP_(idx_next_const)( ulong             prev,     // Previous result of mymap_idx_query_const
     935             :                       ulong             sentinel, // Value to return on failure
     936   688807017 :                       MAP_ELE_T const * pool ) {  // Current local join to element storage
     937             :   /* Go to next element in chain */
     938             : 
     939   688807017 :   MAP_ELE_T const * prev_ele = &pool[ prev ];
     940   688807017 :   MAP_IDX_T const * cur = &prev_ele->MAP_NEXT;
     941   928248813 :   for(;;) {
     942   928248813 :     ulong ele_idx = MAP_(private_unbox)( *cur );
     943   928248813 :     if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
     944   928248660 :     if( FD_LIKELY( MAP_(key_eq)( &prev_ele->MAP_KEY, &pool[ ele_idx ].MAP_KEY ) ) ) return ele_idx; /* optimize for found */
     945   239441796 :     cur = &pool[ ele_idx ].MAP_NEXT;
     946   239441796 :   }
     947             : 
     948             :   /* Not found */
     949             : 
     950         153 :   return sentinel;
     951   688807017 : }
     952             : 
     953             : #endif /* MAP_MULTI!=0 */
     954             : 
     955             : MAP_IMPL_STATIC int
     956             : MAP_(verify)( MAP_(t) const *   join,
     957             :               ulong             ele_cnt,
     958     8475945 :               MAP_ELE_T const * pool ) {
     959             : 
     960  7417231305 : # define MAP_TEST(c) do {                                                        \
     961  7417231305 :     if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
     962  7417231305 :   } while(0)
     963             : 
     964             :   /* Validate input arguments */
     965             : 
     966     8475945 :   MAP_TEST( join );
     967     8475939 :   MAP_TEST( ele_cnt<=MAP_(ele_max)() );
     968     8475933 :   MAP_TEST( (!!pool) | (!ele_cnt) );
     969             : 
     970             :   /* Validate metadata */
     971             : 
     972     8475927 :   MAP_(private_t) const * map = MAP_(private_const)( join );
     973             : 
     974     8475927 :   MAP_TEST( map->magic==MAP_MAGIC );
     975             : 
     976     8475927 :   ulong seed = map->seed;
     977             :   /* seed is arbitrary */
     978             : 
     979     8475927 :   ulong chain_cnt = map->chain_cnt;
     980     8475927 :   MAP_TEST( fd_ulong_is_pow2( chain_cnt ) );
     981     8475927 :   MAP_TEST( chain_cnt<=MAP_(chain_max)()  );
     982             : 
     983             :   /* Visit each map entry, doing simple chain integrity checks */
     984             : 
     985     8475927 :   MAP_IDX_T const * chain = MAP_(private_chain_const)( map );
     986             : 
     987     8475927 :   ulong rem = ele_cnt; /* We can visit at most ele_cnt elements */
     988 27053276967 :   for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
     989 27044801040 :     ulong prev_ele = MAP_(private_idx_null)();
     990 27044801040 :     (void)prev_ele;
     991 27044801040 :     for( ulong ele_idx = MAP_(private_unbox)( chain[ chain_idx ] );
     992 28799327133 :          !MAP_(private_idx_is_null)( ele_idx );
     993 27044801040 :          ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT ) ) {
     994  1754526093 :       MAP_TEST( rem ); rem--;                                                                      /* Check for cycles */
     995  1754526093 :       MAP_TEST( ele_idx<ele_cnt );                                                                 /* Check valid element index */
     996  1754526093 :       MAP_TEST( MAP_(private_chain_idx)( &pool[ ele_idx ].MAP_KEY, seed, chain_cnt )==chain_idx ); /* Check in correct chain */
     997             : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
     998   348271335 :       MAP_TEST( pool[ ele_idx ].MAP_PREV==prev_ele );
     999   348271335 :       prev_ele = ele_idx;
    1000   348271335 : #endif
    1001   348271335 :     }
    1002 27044801040 :   }
    1003             : 
    1004             :   /* At this point, we know that there are no cycles in the map chains,
    1005             :      all indices are inbounds and elements are in the correct chains for
    1006             :      probes.  It is possible for there to be keys that have been
    1007             :      inserted more than once though.  We visit all the nodes a second
    1008             :      time and make sure each probe resolves to itself to prove the key
    1009             :      of every element in the map is unique.  (We could do this faster if
    1010             :      we could tag the elements but this verify is written to not modify
    1011             :      any memory.) */
    1012             : 
    1013 27053276967 :   for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ )
    1014 27044801040 :     for( ulong ele_idx = MAP_(private_unbox)( chain[ chain_idx ] );
    1015 28799327133 :          !MAP_(private_idx_is_null)( ele_idx );
    1016 27044801040 :          ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT ) ) {
    1017             : #if MAP_MULTI==0
    1018  1137781386 :       MAP_TEST( MAP_(idx_query_const)( join, &pool[ ele_idx ].MAP_KEY, ULONG_MAX, pool )==ele_idx );
    1019             : #else
    1020             :       ulong idx2;
    1021   616744707 :       for (idx2 = MAP_(idx_query_const)( join, &pool[ ele_idx ].MAP_KEY, ULONG_MAX, pool );
    1022  1046107332 :            idx2 != ULONG_MAX && idx2 != ele_idx;
    1023   429362625 :            idx2 = MAP_(idx_next_const)( idx2, ULONG_MAX, pool )) ;
    1024   616744707 :       MAP_TEST( idx2 == ele_idx );
    1025             : #endif
    1026  1754526093 :     }
    1027             : 
    1028     8475927 : # undef MAP_TEST
    1029             : 
    1030     8475927 :   return 0;
    1031     8475927 : }
    1032             : 
    1033             : #undef MAP_IMPL_STATIC
    1034             : 
    1035             : #endif
    1036             : 
    1037             : #if MAP_IMPL_STYLE==0 || MAP_IMPL_STYLE==1 /* need inlines */
    1038             : 
    1039             : FD_PROTOTYPES_BEGIN
    1040             : 
    1041             : static inline MAP_(t) *
    1042             : MAP_(ele_insert)( MAP_(t) *   join,
    1043             :                   MAP_ELE_T * ele,
    1044    17140635 :                   MAP_ELE_T * pool ) {
    1045    17140635 :   return MAP_(idx_insert)( join, (ulong)(ele-pool), pool );
    1046    17140635 : }
    1047             : 
    1048             : static inline MAP_ELE_T *
    1049             : MAP_(ele_remove)( MAP_(t) *         join,
    1050             :                   MAP_KEY_T const * key,
    1051             :                   MAP_ELE_T *       sentinel,
    1052     7680297 :                   MAP_ELE_T *       pool ) {
    1053     7680297 :   ulong ele_idx = MAP_(idx_remove)( join, key, MAP_(private_idx_null)(), pool );
    1054     7680297 :   return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T       *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
    1055     7680297 : }
    1056             : 
    1057             : FD_FN_PURE static inline MAP_ELE_T *
    1058             : MAP_(ele_query)( MAP_(t) *         join,
    1059             :                  MAP_KEY_T const * key,
    1060             :                  MAP_ELE_T *       sentinel,
    1061  1205022054 :                  MAP_ELE_T *       pool ) {
    1062  1205022054 :   ulong ele_idx = MAP_(idx_query)( join, key, MAP_(private_idx_null)(), pool );
    1063  1205022054 :   return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T       *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
    1064  1205022054 : }
    1065             : 
    1066             : FD_FN_PURE static inline MAP_ELE_T const *
    1067             : MAP_(ele_query_const)( MAP_(t) const *   join,
    1068             :                        MAP_KEY_T const * key,
    1069             :                        MAP_ELE_T const * sentinel,
    1070   789505284 :                        MAP_ELE_T const * pool ) {
    1071   789505284 :   ulong ele_idx = MAP_(idx_query_const)( join, key, MAP_(private_idx_null)(), pool );
    1072   789505284 :   return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T const *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
    1073   789505284 : }
    1074             : 
    1075             : #if MAP_MULTI!=0
    1076             : 
    1077             : FD_FN_PURE static inline MAP_ELE_T const *        // Found element on success (will be from pool), sentinel on failure
    1078             : MAP_(ele_next_const)( MAP_ELE_T const * prev,     // Previous result of mymap_ele_query_const
    1079             :                       MAP_ELE_T const * sentinel, // Value to return if key not in map
    1080   259444236 :                       MAP_ELE_T const * pool ) {  // Current local join to element storage
    1081   259444236 :          ulong ele_idx = MAP_(idx_next_const)( (ulong)(prev-pool), MAP_(private_idx_null)(), pool );
    1082   259444236 :   return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), pool + ele_idx, sentinel );
    1083   259444236 : }
    1084             : 
    1085             : #endif /* MAP_MULTI!=0 */
    1086             : 
    1087             : FD_PROTOTYPES_END
    1088             : 
    1089             : #endif
    1090             : 
    1091             : #undef MAP_
    1092             : 
    1093             : #undef MAP_IMPL_STYLE
    1094             : #undef MAP_MAGIC
    1095             : #undef MAP_KEY_HASH
    1096             : #undef MAP_KEY_EQ
    1097             : #undef MAP_NEXT
    1098             : #undef MAP_PREV
    1099             : #undef MAP_IDX_T
    1100             : #undef MAP_KEY
    1101             : #undef MAP_KEY_T
    1102             : #undef MAP_ELE_T
    1103             : #undef MAP_NAME
    1104             : #undef MAP_MULTI
    1105             : #undef MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
    1106             : #undef MAP_INSERT_FENCE

Generated by: LCOV version 1.14