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