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
|
