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_ele_cnt returns the current number of elements in the map.
107 : // Requires MAP_COUNT.
108 :
109 : ulong mymap_ele_cnt( mymap_t const * join );
110 :
111 : // mymap_key_{eq,hash} expose the provided MAP_KEY_{EQ,HASH} macros
112 : // as inline functions with strict semantics. They assume that the
113 : // provided pointers are in the caller's address space to keys that
114 : // will not be changed concurrently. They retain no interest in
115 : // any keys on return.
116 : //
117 : // mymap_key_eq returns 1 if *k0 and *k1 are equal and 0 otherwise.
118 : //
119 : // mymap_key_hash returns the hash of *key using the hash function
120 : // seed. Should ideally be a random mapping from MAP_KEY_T to
121 : // ulong but this depends on what the user actually passed in for
122 : // MAP_KEY_HASH. The seed used by a particular instance of a map
123 : // can be obtained above.
124 :
125 : int mymap_key_eq ( ulong * k0, ulong * k1 );
126 : ulong mymap_key_hash( ulong * key, ulong seed );
127 :
128 : // mymap_idx_insert inserts an element into the map. The caller
129 : // promises the element is not currently in the map and that
130 : // element key is not equal to the key of any other element
131 : // currently in the map, except if MAP_MULTI is enabled. Assumes
132 : // there are no concurrent operations on the map. This always
133 : // succeeds.
134 :
135 : mymap_t * // Returns join
136 : mymap_idx_insert( mymap_t * join, // Current local join to element map
137 : ulong ele_idx, // Index of element to insert
138 : myele_t * pool ); // Current local join to element storage
139 :
140 : // mymap_idx_remove removes the mapping of a key to an element.
141 : // Assumes there are no concurrent operations on the map and that
142 : // *key will not be modified during the remove. The map retains no
143 : // interest in key. On success, the map will no longer have an
144 : // interest in the returned element. On failure, the returned
145 : // index lifetime will be that of the sentinel.
146 :
147 : ulong // Index of removed element on success, sentinel on failure
148 : mymap_idx_remove( mymap_t * join, // Current local join to element map
149 : ulong const * key, // Points to the key to remove in the caller's address space
150 : ulong sentinel, // Value to return if key not in map
151 : myele_t * pool ); // Current local join to element storage
152 :
153 : // mymap_idx_query finds the element corresponding to key. Assumes
154 : // there are no concurrent operations on the map and that *key will
155 : // not be modified during the query. The map retains no interest
156 : // in key. On success, the returned index lifetime will be at
157 : // least as long as the corresponding element is still in the map.
158 : // On failure, the returned index lifetime will be that of the
159 : // sentinel.
160 :
161 : ulong // Index of found element on success, sentinel on failure
162 : mymap_idx_query( mymap_t * join, // Current local join to the element map
163 : ulong const * key, // Points to the key to find in the caller's address space
164 : ulong sentinel, // Value to return on failure
165 : myele_t * pool ); // Current local join to element storage
166 :
167 : // mymap_idx_query_const is the same as mymap_idx_query but
168 : // supports concurrent queries so long as there no concurrently
169 : // running insert/remove/query operations. The value fields of the
170 : // element returned by this function can be changed by the
171 : // application but it is up to the application to manage
172 : // concurrency between different users modifying the same element.
173 :
174 : ulong // Index of found element on success, sentinel on failure
175 : mymap_idx_query_const( mymap_t const * join, // Current local join to element map
176 : ulong const * key, // Points to the key to find in the caller's address space
177 : ulong sentinel, // Value to return on failure
178 : myele_t const * pool ); // Current local join to element storage
179 :
180 : // The mymap_ele_{insert,remove,query,query_const} variants are the
181 : // same as the above but use pointers in the caller's address
182 : // instead of pool element storage indices.
183 :
184 : mymap_t * // Returns join
185 : mymap_ele_insert( mymap_t * join, // Current local join to element map
186 : myele_t * ele, // Element to insert (assumed to be in pool)
187 : myele_t * pool ); // Current local join to element storage
188 :
189 : myele_t * // Removed element on success (will be from pool), sentinel on failure
190 : mymap_ele_remove( mymap_t * join, // Current local join to element map
191 : ulong const * key, // Points to the key to remove in the caller's address space
192 : myele_t * sentinel, // Value to return if key not in map
193 : myele_t * pool ); // Current local join to element storage
194 :
195 : myele_t * // Found element on success (will be from pool), sentinel on failure
196 : mymap_ele_query( mymap_t * join, // Current local join to element map
197 : ulong const * key, // Points to the key to find in the caller's address space
198 : myele_t * sentinel, // Value to return if key not in map
199 : myele_t * pool ); // Current local join to element storage
200 :
201 : myele_t const * // Found element on success (will be from pool), sentinel on failure
202 : mymap_ele_query_const( mymap_t const * join, // Current local join to element map
203 : ulong const * key, // Points to the key to find in the caller's address space
204 : myele_t const * sentinel, // Value to return if key not in map
205 : myele_t const * pool ); // Current local join to element storage
206 :
207 : // mymap_iter_* support fast iteration over all the elements in a
208 : // map. The iteration will be in a random order but the order will
209 : // be identical if repeated with no insert/remove/query operations
210 : // done in between. Assumes no concurrent insert/remove/query
211 : // operations (query_const is fine). Example usage:
212 : //
213 : // for( mymap_iter_t iter = mymap_iter_init( join, pool );
214 : // !mymap_iter_done( iter, join, pool );
215 : // iter = mymap_iter_next( iter, join, pool ) ) {
216 : // ulong ele_idx = mymap_iter_idx( iter, join, pool );
217 : //
218 : // ... process element here
219 : //
220 : // ... IMPORTANT! It is _not_ _safe_ to insert, remove
221 : // ... or query here (query_const is fine).
222 : // }
223 :
224 : struct mymap_iter_private { ... internal use only ... };
225 : typedef struct mymap_iter_private mymap_iter_t;
226 :
227 : mymap_iter_t mymap_iter_init ( mymap_t const * join, myele_t const * pool );
228 : int mymap_iter_done ( mymap_iter_t iter, mymap_t const * join, myele_t const * pool );
229 : mymap_iter_t mymap_iter_next ( mymap_iter_t iter, mymap_t const * join, myele_t const * pool ); // assumes not done
230 : ulong mymap_iter_idx ( mymap_iter_t iter, mymap_t const * join, myele_t const * pool ); // assumes not done
231 : myele_t * mymap_iter_ele ( mymap_iter_t iter, mymap_t const * join, myele_t * pool ); // assumes not done
232 : myele_t const * mymap_iter_ele_const( mymap_iter_t iter, mymap_t const * join, myele_t const * pool ); // assumes not done
233 :
234 : // mymap_verify returns 0 if the mymap is not obviously corrupt or
235 : // -1 (i.e. ERR_INVAL) otherwise (logs details).
236 :
237 : int
238 : mymap_verify( mymap_t const * join, // Current local join to a mymap.
239 : ulong ele_max, // Element storage size, in [0,mymap_ele_max()]
240 : myele_t const * pool ); // Current local join to element storage, indexed [0,ele_max)
241 :
242 : You can do this as often as you like in a compilation unit to get
243 : different types of maps. Variants exist for making header prototypes
244 : only and/or implementations if doing a library with multiple
245 : compilation units. Further, options exist to use index compression,
246 : different hashing functions, comparison functions, etc as detailed
247 : below.
248 :
249 : If MAP_MULTI is defined to be 1, the map will support multiple
250 : entries for the same key. In this case, the existing API works as
251 : is, but new methods are provided:
252 :
253 : ulong // Index of found element on success, sentinel on failure
254 : mymap_idx_next_const( ulong prev, // Previous result of mymap_idx_query_const
255 : ulong sentinel, // Value to return on failure
256 : myele_t const * pool ); // Current local join to element storage
257 :
258 : myele_t const * // Found element on success (will be from pool), sentinel on failure
259 : mymap_ele_next_const( myele_t const * prev, // Previous result of mymap_ele_query_const
260 : myele_t const * sentinel, // Value to return if key not in map
261 : myele_t const * pool ); // Current local join to element storage
262 :
263 : These take a previous result from query_const (or next_const) and
264 : return the next element with the same key in the chain.
265 :
266 : IF MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL is defined to be 1, the map will
267 : support removing elements with a known index from the chain in O(1)
268 : time without needing to search for them in the chain. This requires
269 : threading a reverse pointer through the elements in the chain.
270 :
271 : void
272 : mymap_idx_remove_fast( mymap_t * join, // Current uslocal join to element map
273 : ulong ele_idx, // Index of element to remove in the element storage
274 : myele_t * pool ); // Current local join to element storage
275 :
276 : */
277 :
278 : #include "fd_map.h"
279 :
280 : /* MAP_NAME gives the API prefix to use for map */
281 :
282 : #ifndef MAP_NAME
283 : #error "Define MAP_NAME"
284 : #endif
285 :
286 : /* MAP_ELE_T is the map element type. */
287 :
288 : #ifndef MAP_ELE_T
289 : #error "Define MAP_ELE_T"
290 : #endif
291 :
292 : /* MAP_KEY_T is the map key type */
293 :
294 : #ifndef MAP_KEY_T
295 : #define MAP_KEY_T ulong
296 : #endif
297 :
298 : /* MAP_KEY is the MAP_ELE_T key field */
299 :
300 : #ifndef MAP_KEY
301 3776418 : #define MAP_KEY key
302 : #endif
303 :
304 : /* MAP_IDX_T is the type used for the next field in the MAP_ELE_T.
305 : Should be a primitive unsigned integer type. Defaults to ulong. A
306 : map can't use element stores with more elements than the maximum
307 : value that can be represented by a MAP_IDX_T. (E.g. if ushort, the
308 : maximum size element store usable by the map is 65535 elements.) */
309 :
310 : #ifndef MAP_IDX_T
311 8767686 : #define MAP_IDX_T ulong
312 : #endif
313 :
314 : /* MAP_NEXT is the MAP_ELE_T next field */
315 :
316 : #ifndef MAP_NEXT
317 229211673 : #define MAP_NEXT next
318 : #endif
319 :
320 : /* If we're using the optimized random access removal, then we also need
321 : a MAP_ELE_T prev field. */
322 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
323 : # ifndef MAP_PREV
324 2647326 : # define MAP_PREV prev
325 : # endif
326 : #endif
327 :
328 : /* MAP_KEY_EQ returns 0/1 if *k0 is the same/different as *k1 */
329 :
330 : #ifndef MAP_KEY_EQ
331 5656732506 : #define MAP_KEY_EQ(k0,k1) ((*(k0))==(*(k1)))
332 : #endif
333 :
334 : /* MAP_KEY_HASH maps *key into ulong uniform pseudo randomly. */
335 :
336 : #ifndef MAP_KEY_HASH
337 6566346 : #define MAP_KEY_HASH(key,seed) fd_ulong_hash( (*(key)) ^ (seed) )
338 : #endif
339 :
340 : /* MAP_MAGIC is the magic number to use for the structure to aid in
341 : persistent and or IPC usage. */
342 :
343 : #ifndef MAP_MAGIC
344 7884 : #define MAP_MAGIC (0xf17eda2c37c3a900UL) /* firedancer cmap version 0 */
345 : #endif
346 :
347 : /* 0 - local use only
348 : 1 - library header declaration
349 : 2 - library implementation */
350 :
351 : #ifndef MAP_IMPL_STYLE
352 : #define MAP_IMPL_STYLE 0
353 : #endif
354 :
355 : /* 0 - do NOT support multiple values with the same key
356 : 1 - support multiple values with the same key */
357 :
358 : #ifndef MAP_MULTI
359 : #define MAP_MULTI 0
360 : #endif
361 :
362 : /* MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL controls whether the map supports
363 : removal of an element in a chain without iterating the whole chain
364 : from the beginning. */
365 :
366 : #ifndef MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
367 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 0
368 : #endif
369 :
370 : /* MAP_INSERT_FENCE prevents the compiler from reordering the two
371 : operations: setting the next pointer of the new chain head and
372 : updating the chain head. */
373 :
374 : #ifndef MAP_INSERT_FENCE
375 : #define MAP_INSERT_FENCE 0
376 : #endif
377 :
378 : /* MAP_COUNT specifies whether to keep track of map element count. */
379 :
380 : #ifndef MAP_COUNT
381 : #define MAP_COUNT 0
382 : #endif
383 :
384 : /* Implementation *****************************************************/
385 :
386 : /* Constructors and verification log details on failure (rest only needs
387 : fd_bits.h, consider making logging a compile time option). */
388 :
389 : #include "../log/fd_log.h"
390 :
391 95671884453 : #define MAP_(n) FD_EXPAND_THEN_CONCAT3(MAP_NAME,_,n)
392 :
393 : #if MAP_IMPL_STYLE==0 || MAP_IMPL_STYLE==1 /* need structures and inlines */
394 :
395 : struct MAP_(private) {
396 :
397 : /* join points here */
398 :
399 : /* FIXME: consider having an ele_cnt for number of elements in the
400 : underlying storage? (probably not) consider having a memo of the
401 : chain in which an element is stored and/or using doubly linked
402 : chains? We could do a faster remove by index then. */
403 :
404 : ulong magic; /* == MAP_MAGIC */
405 : ulong seed; /* Hash seed, arbitrary */
406 : ulong chain_cnt; /* Number of chains, positive integer power-of-two */
407 : # if MAP_COUNT
408 : ulong ele_cnt; /* Number of elements */
409 : # endif
410 :
411 : /* MAP_IDX_T chain[ chain_cnt ] here */
412 :
413 : };
414 :
415 : typedef struct MAP_(private) MAP_(private_t);
416 :
417 : typedef MAP_(private_t) MAP_(t);
418 :
419 : typedef struct fd_map_chain_iter MAP_(iter_t);
420 :
421 : FD_PROTOTYPES_BEGIN
422 :
423 : /* map_private returns the location of the map private for a current
424 : local join. Assumes join is a current local join. map_private_const
425 : is a const correct version. */
426 :
427 1225842822 : FD_FN_CONST static inline MAP_(private_t) * MAP_(private) ( MAP_(t) * join ) { return join; }
428 2696890165 : FD_FN_CONST static inline MAP_(private_t) const * MAP_(private_const)( MAP_(t) const * join ) { return join; }
429 :
430 : /* map_private_chain returns the location in the caller's address space
431 : of the map chains. Assumes map is valid. map_private_chain_const is
432 : a const correct version. */
433 :
434 : FD_FN_CONST static inline MAP_IDX_T *
435 1225717318 : MAP_(private_chain)( MAP_(private_t) * map ) {
436 1225717318 : return (MAP_IDX_T *)(map+1);
437 1225717318 : }
438 :
439 : FD_FN_CONST static inline MAP_IDX_T const *
440 2696890135 : MAP_(private_chain_const)( MAP_(private_t) const * map ) {
441 2696890135 : return (MAP_IDX_T const *)(map+1);
442 2696890135 : }
443 :
444 : /* map_private_chain_idx returns the index of the chain (in
445 : [0,chain_cnt) that will contain the element corresponding to key (if
446 : present at all) for a map with chain_cnt elements and seed. Assumes
447 : chain_cnt is an integer power-of-two. Assumes key points to a key is
448 : in the caller's address space that will not be changed concurrently.
449 : Retains no interest in key on return. */
450 :
451 : FD_FN_PURE static inline ulong
452 : MAP_(private_chain_idx)( MAP_KEY_T const * key,
453 : ulong seed,
454 5041361428 : ulong chain_cnt ) {
455 5041361428 : return (MAP_KEY_HASH( (key), (seed) )) & (chain_cnt-1UL);
456 5041361428 : }
457 :
458 : /* map_private_{box,unbox} compress / decompress 64-bit in-register
459 : indices to/from their in-memory representations. */
460 :
461 396250745 : FD_FN_CONST static inline MAP_IDX_T MAP_(private_box) ( ulong idx ) { return (MAP_IDX_T)idx; }
462 34747681384 : FD_FN_CONST static inline ulong MAP_(private_unbox)( MAP_IDX_T cidx ) { return (ulong) cidx; }
463 :
464 : /* map_private_idx_null returns the element storage index that
465 : represents NULL. */
466 :
467 14123464988 : FD_FN_CONST static inline ulong MAP_(private_idx_null)( void ) { return (ulong)(MAP_IDX_T)(~0UL); }
468 :
469 : /* map_private_idx_is_null returns 1 if idx is the NULL map index
470 : and 0 otherwise. */
471 :
472 37015885095 : FD_FN_CONST static inline int MAP_(private_idx_is_null)( ulong idx ) { return idx==(ulong)(MAP_IDX_T)(~0UL); }
473 :
474 12620277 : FD_FN_CONST static inline ulong MAP_(ele_max)( void ) { return (ulong)(MAP_IDX_T)(~0UL); }
475 :
476 : FD_FN_CONST static inline ulong
477 12642465 : MAP_(chain_max)( void ) {
478 12642465 : return fd_ulong_pow2_dn( (ULONG_MAX + 1UL - alignof(MAP_(t)) - sizeof(MAP_(t))) / sizeof(MAP_IDX_T) );
479 12642465 : }
480 :
481 : FD_FN_CONST static inline ulong
482 6008400 : MAP_(chain_cnt_est)( ulong ele_max_est ) {
483 :
484 : /* Clamp to be in [1,ele_max] (as ele_max_est 0 is degenerate and as
485 : the map is guaranteed to hold at most ele_max keys). */
486 :
487 6008400 : ele_max_est = fd_ulong_min( fd_ulong_max( ele_max_est, 1UL ), MAP_(ele_max)() );
488 :
489 : /* Compute the number of chains as the power of 2 that makes the
490 : average chain length between ~1 and ~2 when ele_max_est are stored
491 : in the map and then clamp to the chain max. */
492 :
493 6008400 : 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 */
494 6008400 : ulong chain_cnt = fd_ulong_pow2_up( chain_min ); /* Power of 2 in [1,2^63] */
495 :
496 6008400 : return fd_ulong_min( chain_cnt, MAP_(chain_max)() );
497 6008400 : }
498 :
499 12 : FD_FN_PURE static inline ulong MAP_(chain_cnt)( MAP_(t) const * join ) { return MAP_(private_const)( join )->chain_cnt; }
500 6 : FD_FN_PURE static inline ulong MAP_(seed) ( MAP_(t) const * join ) { return MAP_(private_const)( join )->seed; }
501 : #if MAP_COUNT
502 12 : FD_FN_PURE static inline ulong MAP_(ele_cnt) ( MAP_(t) const * join ) { return MAP_(private_const)( join )->ele_cnt; }
503 : #endif
504 :
505 : FD_FN_PURE static inline int
506 : MAP_(key_eq)( MAP_KEY_T const * k0,
507 5801527672 : MAP_KEY_T const * k1 ) {
508 5801527672 : return !!(MAP_KEY_EQ( (k0), (k1) ));
509 5801527672 : }
510 :
511 : FD_FN_PURE static inline ulong
512 : MAP_(key_hash)( MAP_KEY_T const * key,
513 6001038 : ulong seed ) {
514 6001038 : return (MAP_KEY_HASH( (key), (seed) ));
515 6001038 : }
516 :
517 : FD_FN_PURE static inline MAP_(iter_t)
518 : MAP_(iter_init)( MAP_(t) const * join,
519 3111909 : MAP_ELE_T const * pool ) {
520 3111909 : (void)pool;
521 :
522 3111909 : MAP_(private_t) const * map = MAP_(private_const)( join );
523 3111909 : MAP_IDX_T const * chain = MAP_(private_chain_const)( map );
524 :
525 : /* Find first element. If the map is empty, chain_rem will be 0 and
526 : ele_idx will be idx_null. */
527 :
528 3111909 : ulong chain_rem = map->chain_cnt; /* At least 1 */
529 3111909 : ulong ele_idx;
530 31868443 : do {
531 31868443 : ele_idx = MAP_(private_unbox)( chain[ chain_rem-1UL ] );
532 31868443 : if( !MAP_(private_idx_is_null)( ele_idx ) ) break;
533 31868443 : } while( --chain_rem );
534 :
535 3111909 : MAP_(iter_t) iter;
536 3111909 : iter.chain_rem = chain_rem;
537 3111909 : iter.ele_idx = ele_idx;
538 3111909 : return iter;
539 3111909 : }
540 :
541 : FD_FN_CONST static inline int
542 : MAP_(iter_done)( MAP_(iter_t) iter,
543 : MAP_(t) const * join,
544 796321626 : MAP_ELE_T const * pool ) {
545 796321626 : (void)join; (void)pool;
546 796321626 : return !iter.chain_rem;
547 796321626 : }
548 :
549 : __attribute__((warn_unused_result)) FD_FN_PURE static inline MAP_(iter_t)
550 : MAP_(iter_next)( MAP_(iter_t) iter,
551 : MAP_(t) const * join,
552 793207452 : MAP_ELE_T const * pool ) {
553 : # if FD_TMPL_USE_HANDHOLDING
554 : if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
555 : # endif
556 793207452 : ulong chain_rem = iter.chain_rem;
557 793207452 : ulong ele_idx = iter.ele_idx;
558 :
559 : /* At this point, we are just finished iterating over element ele_idx
560 : on chain chain_rem-1 and we already iterated over all elements in
561 : chains (chain_rem,chain_cnt] and all elements in chain chain_rem-1
562 : before this element. As such, ele_idx is in [0,ele_cnt) and
563 : chain_rem is in (0,chain_cnt]. Get the next element in the chain
564 : chain_rem-1. */
565 :
566 793207452 : ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT );
567 793207452 : if( MAP_(private_idx_is_null)( ele_idx ) ) {
568 :
569 : /* There were no more elements in chain chain_rem-1. Find the next
570 : chain to start processing. If all unprocessed chains are empty,
571 : then we are done. */
572 :
573 384350476 : MAP_IDX_T const * chain = MAP_(private_chain_const)( MAP_(private_const)( join ) );
574 796026194 : while( --chain_rem ) {
575 792921998 : ele_idx = MAP_(private_unbox)( chain[ chain_rem-1UL ] );
576 792921998 : if( !MAP_(private_idx_is_null)( ele_idx ) ) break;
577 792921998 : }
578 :
579 384350476 : }
580 :
581 793207452 : iter.chain_rem = chain_rem;
582 793207452 : iter.ele_idx = ele_idx;
583 793207452 : return iter;
584 793207452 : }
585 :
586 : FD_FN_CONST static inline ulong
587 : MAP_(iter_idx)( MAP_(iter_t) iter,
588 : MAP_(t) const * join,
589 787970514 : MAP_ELE_T * pool ) {
590 : # if FD_TMPL_USE_HANDHOLDING
591 : if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
592 : # endif
593 787970514 : (void)join; (void)pool;
594 787970514 : return iter.ele_idx;
595 787970514 : }
596 :
597 : FD_FN_CONST static inline MAP_ELE_T *
598 : MAP_(iter_ele)( MAP_(iter_t) iter,
599 : MAP_(t) const * join,
600 793204464 : MAP_ELE_T * pool ) {
601 : # if FD_TMPL_USE_HANDHOLDING
602 : if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
603 : # endif
604 793204464 : (void)join;
605 793204464 : return pool + iter.ele_idx;
606 793204464 : }
607 :
608 : FD_FN_CONST static inline MAP_ELE_T const *
609 : MAP_(iter_ele_const) ( MAP_(iter_t) iter,
610 : MAP_(t) const * join,
611 787969401 : MAP_ELE_T const * pool ) {
612 : # if FD_TMPL_USE_HANDHOLDING
613 : if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
614 : # endif
615 787969401 : (void)join;
616 787969401 : return pool + iter.ele_idx;
617 787969401 : }
618 :
619 : FD_PROTOTYPES_END
620 :
621 : #endif
622 :
623 : #if MAP_IMPL_STYLE==1 /* need prototypes */
624 :
625 : FD_PROTOTYPES_BEGIN
626 :
627 : FD_FN_CONST ulong MAP_(align) ( void );
628 : FD_FN_CONST ulong MAP_(footprint)( ulong chain_cnt );
629 : void * MAP_(new) ( void * shmem, ulong chain_cnt, ulong seed );
630 : MAP_(t) * MAP_(join) ( void * shmap );
631 : void * MAP_(leave) ( MAP_(t) * join );
632 : void * MAP_(delete) ( void * shmap );
633 :
634 : void MAP_(reset) ( MAP_(t) * join );
635 :
636 : MAP_(t) *
637 : MAP_(idx_insert)( MAP_(t) * join,
638 : ulong ele_idx,
639 : MAP_ELE_T * pool );
640 :
641 : ulong
642 : MAP_(idx_remove)( MAP_(t) * join,
643 : MAP_KEY_T const * key,
644 : ulong sentinel,
645 : MAP_ELE_T * pool );
646 :
647 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
648 : void
649 : MAP_(idx_remove_fast)( MAP_(t) * join,
650 : ulong ele_idx,
651 : MAP_ELE_T * pool );
652 :
653 : MAP_ELE_T *
654 : MAP_(ele_remove_fast)( MAP_(t) * join,
655 : MAP_ELE_T * ele,
656 : MAP_ELE_T * pool );
657 : #endif
658 :
659 : ulong
660 : MAP_(idx_query)( MAP_(t) * join,
661 : MAP_KEY_T const * key,
662 : ulong sentinel,
663 : MAP_ELE_T * pool );
664 :
665 : FD_FN_PURE ulong
666 : MAP_(idx_query_const)( MAP_(t) const * join,
667 : MAP_KEY_T const * key,
668 : ulong sentinel,
669 : MAP_ELE_T const * pool );
670 :
671 : #if MAP_MULTI!=0
672 :
673 : FD_FN_PURE ulong
674 : MAP_(idx_next_const)( ulong prev, // Previous result of mymap_idx_query_const
675 : ulong sentinel, // Value to return on failure
676 : MAP_ELE_T const * pool ); // Current local join to element storage
677 :
678 : #endif /* MAP_MULTI!=0 */
679 :
680 : int
681 : MAP_(verify)( MAP_(t) const * join,
682 : ulong ele_max,
683 : MAP_ELE_T const * pool );
684 :
685 : FD_PROTOTYPES_END
686 :
687 : #else /* need implementations */
688 :
689 : #if MAP_IMPL_STYLE==0 /* local only */
690 : #define MAP_IMPL_STATIC FD_FN_UNUSED static
691 : #else
692 : #define MAP_IMPL_STATIC
693 : #endif
694 :
695 43032 : FD_FN_CONST MAP_IMPL_STATIC ulong MAP_(align)( void ) { return alignof(MAP_(t)); }
696 :
697 : FD_FN_CONST MAP_IMPL_STATIC ulong
698 22200 : MAP_(footprint)( ulong chain_cnt ) {
699 22200 : if( !(fd_ulong_is_pow2( chain_cnt ) & (chain_cnt<=MAP_(chain_max)())) ) return 0UL;
700 22164 : return fd_ulong_align_up( sizeof(MAP_(t)) + chain_cnt*sizeof(MAP_IDX_T), alignof(MAP_(t)) ); /* no overflow */
701 22200 : }
702 :
703 : MAP_IMPL_STATIC void *
704 : MAP_(new)( void * shmap,
705 : ulong chain_cnt,
706 8049 : ulong seed ) {
707 :
708 8049 : if( FD_UNLIKELY( !shmap ) ) {
709 6 : FD_LOG_WARNING(( "NULL shmap" ));
710 6 : return NULL;
711 6 : }
712 :
713 8043 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmap, MAP_(align)() ) ) ) {
714 6 : FD_LOG_WARNING(( "misaligned shmap" ));
715 6 : return NULL;
716 6 : }
717 :
718 8037 : ulong footprint = MAP_(footprint)( chain_cnt );
719 8037 : if( FD_UNLIKELY( !footprint ) ) {
720 18 : FD_LOG_WARNING(( "bad footprint" ));
721 18 : return NULL;
722 18 : }
723 :
724 : /* seed is arbitrary */
725 :
726 : /* Init the metadata */
727 :
728 8019 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
729 :
730 8019 : map->seed = seed;
731 8019 : map->chain_cnt = chain_cnt;
732 : # if MAP_COUNT
733 : map->ele_cnt = 0UL;
734 : # endif
735 :
736 : /* Set all the chains to NULL */
737 :
738 8019 : MAP_IDX_T * chain = MAP_(private_chain)( map );
739 50461563 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) chain[ chain_idx ] = MAP_(private_box)( MAP_(private_idx_null)() );
740 :
741 8019 : FD_COMPILER_MFENCE();
742 8019 : FD_VOLATILE( map->magic ) = MAP_MAGIC;
743 8019 : FD_COMPILER_MFENCE();
744 :
745 8019 : return shmap;
746 8037 : }
747 :
748 : MAP_IMPL_STATIC MAP_(t) *
749 8082 : MAP_(join)( void * shmap ) {
750 8082 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
751 :
752 8082 : if( FD_UNLIKELY( !map ) ) {
753 6 : FD_LOG_WARNING(( "NULL shmap" ));
754 6 : return NULL;
755 6 : }
756 :
757 8076 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) ) ) {
758 6 : FD_LOG_WARNING(( "misaligned shmap" ));
759 6 : return NULL;
760 6 : }
761 :
762 8070 : if( FD_UNLIKELY( map->magic!=MAP_MAGIC ) ) {
763 6 : FD_LOG_WARNING(( "bad magic" ));
764 6 : return NULL;
765 6 : }
766 :
767 8064 : return (MAP_(t) *)map;
768 8070 : }
769 :
770 : MAP_IMPL_STATIC void *
771 285 : MAP_(leave)( MAP_(t) * join ) {
772 :
773 285 : if( FD_UNLIKELY( !join ) ) {
774 6 : FD_LOG_WARNING(( "NULL join" ));
775 6 : return NULL;
776 6 : }
777 :
778 279 : return (void *)join;
779 285 : }
780 :
781 : MAP_IMPL_STATIC void *
782 294 : MAP_(delete)( void * shmap ) {
783 294 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
784 :
785 294 : if( FD_UNLIKELY( !map ) ) {
786 6 : FD_LOG_WARNING(( "NULL shmap" ));
787 6 : return NULL;
788 6 : }
789 :
790 288 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) ) ) {
791 6 : FD_LOG_WARNING(( "misaligned shmap" ));
792 6 : return NULL;
793 6 : }
794 :
795 282 : if( FD_UNLIKELY( map->magic!=MAP_MAGIC ) ) {
796 6 : FD_LOG_WARNING(( "bad magic" ));
797 6 : return NULL;
798 6 : }
799 :
800 276 : FD_COMPILER_MFENCE();
801 276 : FD_VOLATILE( map->magic ) = 0UL;
802 276 : FD_COMPILER_MFENCE();
803 :
804 276 : return shmap;
805 282 : }
806 :
807 : MAP_IMPL_STATIC void
808 69615 : MAP_(reset)( MAP_(t) * join ) {
809 69615 : MAP_(private_t) * map = MAP_(private)( join );
810 :
811 69615 : MAP_IDX_T * chain = MAP_(private_chain)( map );
812 47878239 : for( ulong chain_idx=0UL; chain_idx<map->chain_cnt; chain_idx++ ) chain[ chain_idx ] = MAP_(private_box)( MAP_(private_idx_null)() );
813 :
814 : # if MAP_COUNT
815 : map->ele_cnt = 0UL;
816 : # endif
817 69615 : }
818 :
819 : MAP_IMPL_STATIC ulong
820 : MAP_(idx_query)( MAP_(t) * join,
821 : MAP_KEY_T const * key,
822 : ulong sentinel,
823 1209908739 : MAP_ELE_T * pool ) {
824 1209908739 : MAP_(private_t) * map = MAP_(private)( join );
825 :
826 : /* Find the key */
827 :
828 1209908739 : MAP_IDX_T * head = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
829 1209908739 : MAP_IDX_T * cur = head;
830 2125840223 : for(;;) {
831 2125840223 : ulong ele_idx = MAP_(private_unbox)( *cur );
832 2125840223 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
833 1327171169 : if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) { /* optimize for found */
834 : /* Found, move it to the front of the chain */
835 411239685 : if( FD_UNLIKELY( cur!=head ) ) { /* Assume already at head from previous query */
836 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
837 26480 : 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;
838 26480 : pool[ ele_idx ].MAP_PREV = MAP_(private_box)( MAP_(private_idx_null)() );
839 26480 : pool[ *head ].MAP_PREV = MAP_(private_box)( ele_idx );
840 : #endif
841 289662185 : *cur = pool[ ele_idx ].MAP_NEXT;
842 289662185 : pool[ ele_idx ].MAP_NEXT = *head;
843 289662185 : *head = MAP_(private_box)( ele_idx );
844 289662185 : }
845 411239685 : return ele_idx;
846 411239685 : }
847 915931484 : cur = &pool[ ele_idx ].MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
848 915931484 : }
849 :
850 : /* Not found */
851 :
852 798669054 : return sentinel;
853 1209908739 : }
854 :
855 : MAP_IMPL_STATIC MAP_(t) *
856 : MAP_(idx_insert)( MAP_(t) * join,
857 : ulong ele_idx,
858 5848707 : MAP_ELE_T * pool ) {
859 : # if FD_TMPL_USE_HANDHOLDING && !MAP_MULTI
860 : if( FD_UNLIKELY( !MAP_(private_idx_is_null)( MAP_(idx_query)( join, &pool[ ele_idx ].MAP_KEY, MAP_(private_idx_null)(), pool ) ) ) ) {
861 : FD_LOG_CRIT(( "ele_idx already in map" ));
862 : }
863 : # endif
864 5848707 : MAP_(private_t) * map = MAP_(private)( join );
865 :
866 5848707 : MAP_IDX_T * head = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( &pool[ ele_idx ].MAP_KEY, map->seed, map->chain_cnt );
867 :
868 : # if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
869 2210790 : if( FD_UNLIKELY( !MAP_(private_idx_is_null)( *head ) ) ) pool[ *head ].MAP_PREV = MAP_(private_box)( ele_idx );
870 2210790 : pool[ ele_idx ].MAP_PREV = MAP_(private_box)( MAP_(private_idx_null)() );
871 : # endif
872 5848707 : pool[ ele_idx ].MAP_NEXT = *head;
873 : # if MAP_INSERT_FENCE
874 84 : FD_COMPILER_MFENCE();
875 : # endif
876 5848707 : *head = MAP_(private_box)( ele_idx );
877 : # if MAP_COUNT
878 : map->ele_cnt++;
879 : # endif
880 :
881 5848707 : return join;
882 5848707 : }
883 :
884 : MAP_IMPL_STATIC ulong
885 : MAP_(idx_remove)( MAP_(t) * join,
886 : MAP_KEY_T const * key,
887 : ulong sentinel,
888 8249130 : MAP_ELE_T * pool ) {
889 8249130 : MAP_(private_t) * map = MAP_(private)( join );
890 :
891 : /* Find the key */
892 :
893 8249130 : MAP_IDX_T * cur = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
894 12383508 : for(;;) {
895 12383508 : ulong ele_idx = MAP_(private_unbox)( *cur );
896 12383508 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found (it is remove after all) */
897 7707054 : if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) { /* " */
898 3572676 : *cur = pool[ ele_idx ].MAP_NEXT;
899 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
900 57 : 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;
901 : #endif
902 : #if MAP_COUNT
903 : map->ele_cnt--;
904 : #endif
905 3572676 : return ele_idx;
906 3572676 : }
907 4134378 : cur = &pool[ ele_idx ].MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
908 4134378 : }
909 :
910 : /* Not found */
911 :
912 4676454 : return sentinel;
913 8249130 : }
914 :
915 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
916 : MAP_IMPL_STATIC void
917 : MAP_(idx_remove_fast)( MAP_(t) * join,
918 : ulong ele_idx,
919 1766631 : MAP_ELE_T * pool ) {
920 1766631 : MAP_(private_t) * map = MAP_(private)( join );
921 :
922 1766631 : MAP_ELE_T * ele = pool+ele_idx;
923 :
924 1766631 : if( FD_UNLIKELY( !MAP_(private_idx_is_null)( ele->MAP_NEXT ) ) ) pool[ ele->MAP_NEXT ].MAP_PREV = ele->MAP_PREV;
925 :
926 1766631 : if( FD_UNLIKELY( !MAP_(private_idx_is_null)( ele->MAP_PREV ) ) ) pool[ ele->MAP_PREV ].MAP_NEXT = ele->MAP_NEXT;
927 1633102 : else { MAP_(private_chain)( map )[ MAP_(private_chain_idx)( &ele->MAP_KEY, map->seed, map->chain_cnt ) ] = ele->MAP_NEXT; }
928 :
929 : #if MAP_COUNT
930 : map->ele_cnt--;
931 : #endif
932 1766631 : }
933 :
934 : MAP_IMPL_STATIC MAP_ELE_T *
935 : MAP_(ele_remove_fast)( MAP_(t) * join,
936 : MAP_ELE_T * ele,
937 36969 : MAP_ELE_T * pool ) {
938 36969 : MAP_(idx_remove_fast)( join, (ulong)(ele-pool), pool );
939 36969 : return ele;
940 36969 : }
941 : #endif
942 :
943 : FD_FN_PURE MAP_IMPL_STATIC ulong
944 : MAP_(idx_query_const)( MAP_(t) const * join,
945 : MAP_KEY_T const * key,
946 : ulong sentinel,
947 2302815891 : MAP_ELE_T const * pool ) {
948 2302815891 : MAP_(private_t) const * map = MAP_(private_const)( join );
949 :
950 : /* Find the key */
951 :
952 2302815891 : MAP_IDX_T const * cur = MAP_(private_chain_const)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
953 3516334174 : for(;;) {
954 3516334174 : ulong ele_idx = MAP_(private_unbox)( *cur );
955 3516334174 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
956 3514400671 : if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) return ele_idx; /* optimize for found */
957 1213518283 : cur = &pool[ ele_idx ].MAP_NEXT;
958 1213518283 : }
959 :
960 : /* Not found */
961 :
962 1933503 : return sentinel;
963 2302815891 : }
964 :
965 : #if MAP_MULTI!=0
966 :
967 : FD_FN_PURE MAP_IMPL_STATIC ulong
968 : MAP_(idx_next_const)( ulong prev, // Previous result of mymap_idx_query_const
969 : ulong sentinel, // Value to return on failure
970 688807248 : MAP_ELE_T const * pool ) { // Current local join to element storage
971 : /* Go to next element in chain */
972 :
973 688807248 : MAP_ELE_T const * prev_ele = &pool[ prev ];
974 688807248 : MAP_IDX_T const * cur = &prev_ele->MAP_NEXT;
975 928249054 : for(;;) {
976 928249054 : ulong ele_idx = MAP_(private_unbox)( *cur );
977 928249054 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
978 928248775 : if( FD_LIKELY( MAP_(key_eq)( &prev_ele->MAP_KEY, &pool[ ele_idx ].MAP_KEY ) ) ) return ele_idx; /* optimize for found */
979 239441806 : cur = &pool[ ele_idx ].MAP_NEXT;
980 239441806 : }
981 :
982 : /* Not found */
983 :
984 279 : return sentinel;
985 688807248 : }
986 :
987 : #endif /* MAP_MULTI!=0 */
988 :
989 : MAP_IMPL_STATIC int
990 : MAP_(verify)( MAP_(t) const * join,
991 : ulong ele_max,
992 6611877 : MAP_ELE_T const * pool ) {
993 :
994 6200407431 : # define MAP_TEST(c) do { \
995 6200407431 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
996 6200407431 : } while(0)
997 :
998 : /* Validate input arguments */
999 :
1000 6611877 : MAP_TEST( join );
1001 6611871 : MAP_TEST( ele_max<=MAP_(ele_max)() );
1002 6611865 : MAP_TEST( (!!pool) | (!ele_max) );
1003 :
1004 : /* Validate metadata */
1005 :
1006 6611859 : MAP_(private_t) const * map = MAP_(private_const)( join );
1007 :
1008 6611859 : MAP_TEST( map->magic==MAP_MAGIC );
1009 :
1010 6611859 : ulong seed = map->seed;
1011 : /* seed is arbitrary */
1012 :
1013 6611859 : ulong chain_cnt = map->chain_cnt;
1014 6611859 : MAP_TEST( fd_ulong_is_pow2( chain_cnt ) );
1015 6611859 : MAP_TEST( chain_cnt<=MAP_(chain_max)() );
1016 :
1017 : /* Visit each map entry, doing simple chain integrity checks */
1018 :
1019 6611859 : MAP_IDX_T const * chain = MAP_(private_chain_const)( map );
1020 :
1021 6611859 : ulong ele_cnt = 0UL; (void)ele_cnt;
1022 6611859 : ulong rem = ele_max; /* We can visit at most ele_max elements */
1023 11767144287 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
1024 11760532428 : ulong prev_ele = MAP_(private_idx_null)();
1025 11760532428 : (void)prev_ele;
1026 11760532428 : for( ulong ele_idx = MAP_(private_unbox)( chain[ chain_idx ] );
1027 13273438266 : !MAP_(private_idx_is_null)( ele_idx );
1028 11760532428 : ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT ) ) {
1029 1512905838 : MAP_TEST( rem ); rem--; /* Check for cycles */
1030 1512905838 : MAP_TEST( ele_idx<ele_max ); /* Check valid element index */
1031 1512905838 : MAP_TEST( MAP_(private_chain_idx)( &pool[ ele_idx ].MAP_KEY, seed, chain_cnt )==chain_idx ); /* Check in correct chain */
1032 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
1033 109112877 : MAP_TEST( pool[ ele_idx ].MAP_PREV==prev_ele );
1034 109112877 : prev_ele = ele_idx;
1035 109112877 : #endif
1036 1403792961 : ele_cnt++;
1037 1403792961 : }
1038 11760532428 : }
1039 :
1040 : # if MAP_COUNT
1041 12 : MAP_TEST( MAP_(ele_cnt)( join )==ele_cnt );
1042 12 : # endif
1043 :
1044 : /* At this point, we know that there are no cycles in the map chains,
1045 : all indices are inbounds and elements are in the correct chains for
1046 : probes. It is possible for there to be keys that have been
1047 : inserted more than once though. We visit all the nodes a second
1048 : time and make sure each probe resolves to itself to prove the key
1049 : of every element in the map is unique. (We could do this faster if
1050 : we could tag the elements but this verify is written to not modify
1051 : any memory.) */
1052 :
1053 11767144287 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ )
1054 11760532428 : for( ulong ele_idx = MAP_(private_unbox)( chain[ chain_idx ] );
1055 13273438266 : !MAP_(private_idx_is_null)( ele_idx );
1056 11760532428 : ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT ) ) {
1057 : #if MAP_MULTI==0
1058 896161131 : MAP_TEST( MAP_(idx_query_const)( join, &pool[ ele_idx ].MAP_KEY, ULONG_MAX, pool )==ele_idx );
1059 : #else
1060 : ulong idx2;
1061 616744707 : for (idx2 = MAP_(idx_query_const)( join, &pool[ ele_idx ].MAP_KEY, ULONG_MAX, pool );
1062 1046107332 : idx2 != ULONG_MAX && idx2 != ele_idx;
1063 429362625 : idx2 = MAP_(idx_next_const)( idx2, ULONG_MAX, pool )) ;
1064 616744707 : MAP_TEST( idx2 == ele_idx );
1065 : #endif
1066 1512905838 : }
1067 :
1068 6611859 : # undef MAP_TEST
1069 :
1070 6611859 : return 0;
1071 6611859 : }
1072 :
1073 : #undef MAP_IMPL_STATIC
1074 :
1075 : #endif
1076 :
1077 : #if MAP_IMPL_STYLE==0 || MAP_IMPL_STYLE==1 /* need inlines */
1078 :
1079 : FD_PROTOTYPES_BEGIN
1080 :
1081 : static inline MAP_(t) *
1082 : MAP_(ele_insert)( MAP_(t) * join,
1083 : MAP_ELE_T * ele,
1084 3681663 : MAP_ELE_T * pool ) {
1085 3681663 : return MAP_(idx_insert)( join, (ulong)(ele-pool), pool );
1086 3681663 : }
1087 :
1088 : static inline MAP_ELE_T *
1089 : MAP_(ele_remove)( MAP_(t) * join,
1090 : MAP_KEY_T const * key,
1091 : MAP_ELE_T * sentinel,
1092 7767903 : MAP_ELE_T * pool ) {
1093 7767903 : ulong ele_idx = MAP_(idx_remove)( join, key, MAP_(private_idx_null)(), pool );
1094 7767903 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
1095 7767903 : }
1096 :
1097 : FD_FN_PURE static inline MAP_ELE_T *
1098 : MAP_(ele_query)( MAP_(t) * join,
1099 : MAP_KEY_T const * key,
1100 : MAP_ELE_T * sentinel,
1101 1205708700 : MAP_ELE_T * pool ) {
1102 1205708700 : ulong ele_idx = MAP_(idx_query)( join, key, MAP_(private_idx_null)(), pool );
1103 1205708700 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
1104 1205708700 : }
1105 :
1106 : FD_FN_PURE static inline MAP_ELE_T const *
1107 : MAP_(ele_query_const)( MAP_(t) const * join,
1108 : MAP_KEY_T const * key,
1109 : MAP_ELE_T const * sentinel,
1110 789512076 : MAP_ELE_T const * pool ) {
1111 789512076 : ulong ele_idx = MAP_(idx_query_const)( join, key, MAP_(private_idx_null)(), pool );
1112 789512076 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T const *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
1113 789512076 : }
1114 :
1115 : #if MAP_MULTI!=0
1116 :
1117 : FD_FN_PURE static inline MAP_ELE_T const * // Found element on success (will be from pool), sentinel on failure
1118 : MAP_(ele_next_const)( MAP_ELE_T const * prev, // Previous result of mymap_ele_query_const
1119 : MAP_ELE_T const * sentinel, // Value to return if key not in map
1120 259444443 : MAP_ELE_T const * pool ) { // Current local join to element storage
1121 259444443 : ulong ele_idx = MAP_(idx_next_const)( (ulong)(prev-pool), MAP_(private_idx_null)(), pool );
1122 259444443 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), pool + ele_idx, sentinel );
1123 259444443 : }
1124 :
1125 : #endif /* MAP_MULTI!=0 */
1126 :
1127 : FD_PROTOTYPES_END
1128 :
1129 : #endif
1130 :
1131 : #undef MAP_
1132 :
1133 : #undef MAP_IMPL_STYLE
1134 : #undef MAP_MAGIC
1135 : #undef MAP_KEY_HASH
1136 : #undef MAP_KEY_EQ
1137 : #undef MAP_NEXT
1138 : #undef MAP_PREV
1139 : #undef MAP_IDX_T
1140 : #undef MAP_KEY
1141 : #undef MAP_KEY_T
1142 : #undef MAP_ELE_T
1143 : #undef MAP_NAME
1144 : #undef MAP_MULTI
1145 : #undef MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
1146 : #undef MAP_INSERT_FENCE
1147 : #undef MAP_COUNT
|
