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 : /* MAP_NAME gives the API prefix to use for map */
274 :
275 : #ifndef MAP_NAME
276 : #error "Define MAP_NAME"
277 : #endif
278 :
279 : /* MAP_ELE_T is the map element type. */
280 :
281 : #ifndef MAP_ELE_T
282 : #error "Define MAP_ELE_T"
283 : #endif
284 :
285 : /* MAP_KEY_T is the map key type */
286 :
287 : #ifndef MAP_KEY_T
288 : #define MAP_KEY_T ulong
289 : #endif
290 :
291 : /* MAP_KEY is the MAP_ELE_T key field */
292 :
293 : #ifndef MAP_KEY
294 0 : #define MAP_KEY key
295 : #endif
296 :
297 : /* MAP_IDX_T is the type used for the next field in the MAP_ELE_T.
298 : Should be a primitive unsigned integer type. Defaults to ulong. A
299 : map can't use element stores with more elements than the maximum
300 : value that can be represented by a MAP_IDX_T. (E.g. if ushort, the
301 : maximum size element store usable by the map is 65535 elements.) */
302 :
303 : #ifndef MAP_IDX_T
304 162 : #define MAP_IDX_T ulong
305 : #endif
306 :
307 : /* MAP_NEXT is the MAP_ELE_T next field */
308 :
309 : #ifndef MAP_NEXT
310 75 : #define MAP_NEXT next
311 : #endif
312 :
313 : /* MAP_KEY_EQ returns 0/1 if *k0 is the same/different as *k1 */
314 :
315 : #ifndef MAP_KEY_EQ
316 5651997885 : #define MAP_KEY_EQ(k0,k1) ((*(k0))==(*(k1)))
317 : #endif
318 :
319 : /* MAP_KEY_HASH maps *key into ulong uniform pseudo randomly. */
320 :
321 : #ifndef MAP_KEY_HASH
322 105 : #define MAP_KEY_HASH(key,seed) fd_ulong_hash( (*(key)) ^ (seed) )
323 : #endif
324 :
325 : /* MAP_MAGIC is the magic number to use for the structure to aid in
326 : persistent and or IPC usage. */
327 :
328 : #ifndef MAP_MAGIC
329 1068 : #define MAP_MAGIC (0xf17eda2c37c3a900UL) /* firedancer cmap version 0 */
330 : #endif
331 :
332 : /* 0 - local use only
333 : 1 - library header declaration
334 : 2 - library implementation */
335 :
336 : #ifndef MAP_IMPL_STYLE
337 : #define MAP_IMPL_STYLE 0
338 : #endif
339 :
340 : /* 0 - do NOT support multiple values with the same key
341 : 1 - support multiple values with the same key */
342 :
343 : #ifndef MAP_MULTI
344 : #define MAP_MULTI 0
345 : #endif
346 :
347 : /* MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL controls whether the map supports
348 : removal of an element in a chain without iterating the whole chain
349 : from the beginning. */
350 :
351 : #ifndef MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
352 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 0
353 : #endif
354 :
355 : /* Implementation *****************************************************/
356 :
357 : /* Constructors and verification log details on failure (rest only needs
358 : fd_bits.h, consider making logging a compile time option). */
359 :
360 : #include "../log/fd_log.h"
361 :
362 41988694179 : #define MAP_(n) FD_EXPAND_THEN_CONCAT3(MAP_NAME,_,n)
363 :
364 : #if MAP_IMPL_STYLE==0 || MAP_IMPL_STYLE==1 /* need structures and inlines */
365 :
366 : struct MAP_(private) {
367 :
368 : /* join points here */
369 :
370 : /* FIXME: consider having an ele_cnt for number of elements in the
371 : underlying storage? (probably not) consider having a memo of the
372 : chain in which an element is stored and/or using doubly linked
373 : chains? We could do a faster remove by index then. */
374 :
375 : ulong magic; /* == MAP_MAGIC */
376 : ulong seed; /* Hash seed, arbitrary */
377 : ulong chain_cnt; /* Number of chains, positive integer power-of-two */
378 :
379 : /* MAP_IDX_T chain[ chain_cnt ] here */
380 :
381 : };
382 :
383 : typedef struct MAP_(private) MAP_(private_t);
384 :
385 : typedef MAP_(private_t) MAP_(t);
386 :
387 : struct MAP_(iter) {
388 : ulong chain_rem;
389 : ulong ele_idx;
390 : };
391 :
392 : typedef struct MAP_(iter) MAP_(iter_t);
393 :
394 : FD_PROTOTYPES_BEGIN
395 :
396 : /* map_private returns the location of the map private for a current
397 : local join. Assumes join is a current local join. map_private_const
398 : is a const correct version. */
399 :
400 1239423810 : FD_FN_CONST static inline MAP_(private_t) * MAP_(private) ( MAP_(t) * join ) { return join; }
401 2582811657 : FD_FN_CONST static inline MAP_(private_t) const * MAP_(private_const)( MAP_(t) const * join ) { return join; }
402 :
403 : /* map_private_chain returns the location in the caller's address space
404 : of the map chains. Assumes map is valid. map_private_chain_const is
405 : a const correct version. */
406 :
407 : FD_FN_CONST static inline MAP_IDX_T *
408 1238914038 : MAP_(private_chain)( MAP_(private_t) * map ) {
409 1238914038 : return (MAP_IDX_T *)(map+1);
410 1238914038 : }
411 :
412 : FD_FN_CONST static inline MAP_IDX_T const *
413 2582811639 : MAP_(private_chain_const)( MAP_(private_t) const * map ) {
414 2582811639 : return (MAP_IDX_T const *)(map+1);
415 2582811639 : }
416 :
417 : /* map_private_chain_idx returns the index of the chain (in
418 : [0,chain_cnt) that will contain the element corresponding to key (if
419 : present at all) for a map with chain_cnt elements and seed. Assumes
420 : chain_cnt is an integer power-of-two. Assumes key points to a key is
421 : in the caller's address space that will not be changed concurrently.
422 : Retains no interest in key on return. */
423 :
424 : FD_FN_PURE static inline ulong
425 : MAP_(private_chain_idx)( MAP_KEY_T const * key,
426 : ulong seed,
427 4834769562 : ulong chain_cnt ) {
428 4834769562 : return (MAP_KEY_HASH( (key), (seed) )) & (chain_cnt-1UL);
429 4834769562 : }
430 :
431 : /* map_private_{box,unbox} compress / decompress 64-bit in-register
432 : indices to/from their in-memory representations. */
433 :
434 330739710 : FD_FN_CONST static inline MAP_IDX_T MAP_(private_box) ( ulong idx ) { return (MAP_IDX_T)idx; }
435 13988647977 : FD_FN_CONST static inline ulong MAP_(private_unbox)( MAP_IDX_T cidx ) { return (ulong) cidx; }
436 :
437 : /* map_private_idx_null returns the element storage index that
438 : represents NULL. */
439 :
440 2274922131 : FD_FN_CONST static inline ulong MAP_(private_idx_null)( void ) { return (ulong)(MAP_IDX_T)(~0UL); }
441 :
442 : /* map_private_idx_is_null returns 1 if idx is the NULL map index
443 : and 0 otherwise. */
444 :
445 16287367215 : FD_FN_CONST static inline int MAP_(private_idx_is_null)( ulong idx ) { return idx==(ulong)(MAP_IDX_T)(~0UL); }
446 :
447 12146787 : FD_FN_CONST static inline ulong MAP_(ele_max)( void ) { return (ulong)(MAP_IDX_T)(~0UL); }
448 :
449 : FD_FN_CONST static inline ulong
450 12150642 : MAP_(chain_max)( void ) {
451 12150642 : return fd_ulong_pow2_dn( (ULONG_MAX + 1UL - alignof(MAP_(t)) - sizeof(MAP_(t))) / sizeof(MAP_IDX_T) );
452 12150642 : }
453 :
454 : FD_FN_CONST static inline ulong
455 6002763 : MAP_(chain_cnt_est)( ulong ele_max_est ) {
456 :
457 : /* Clamp to be in [1,ele_max] (as ele_max_est 0 is degenerate and as
458 : the map is guaranteed to hold at most ele_max keys). */
459 :
460 6002763 : ele_max_est = fd_ulong_min( fd_ulong_max( ele_max_est, 1UL ), MAP_(ele_max)() );
461 :
462 : /* Compute the number of chains as the power of 2 that makes the
463 : average chain length between ~1 and ~2 when ele_max_est are stored
464 : in the map and then clamp to the chain max. */
465 :
466 6002763 : 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 */
467 6002763 : ulong chain_cnt = fd_ulong_pow2_up( chain_min ); /* Power of 2 in [1,2^63] */
468 :
469 6002763 : return fd_ulong_min( chain_cnt, MAP_(chain_max)() );
470 6002763 : }
471 :
472 12 : FD_FN_PURE static inline ulong MAP_(chain_cnt)( MAP_(t) const * join ) { return MAP_(private_const)( join )->chain_cnt; }
473 6 : FD_FN_PURE static inline ulong MAP_(seed) ( MAP_(t) const * join ) { return MAP_(private_const)( join )->seed; }
474 :
475 : FD_FN_PURE static inline int
476 : MAP_(key_eq)( MAP_KEY_T const * k0,
477 5683639575 : MAP_KEY_T const * k1 ) {
478 5683639575 : return !!(MAP_KEY_EQ( (k0), (k1) ));
479 5683639575 : }
480 :
481 : FD_FN_PURE static inline ulong
482 : MAP_(key_hash)( MAP_KEY_T const * key,
483 6000000 : ulong seed ) {
484 6000000 : return (MAP_KEY_HASH( (key), (seed) ));
485 6000000 : }
486 :
487 : FD_FN_PURE static inline MAP_(iter_t)
488 : MAP_(iter_init)( MAP_(t) const * join,
489 3078000 : MAP_ELE_T const * pool ) {
490 3078000 : (void)pool;
491 :
492 3078000 : MAP_(private_t) const * map = MAP_(private_const)( join );
493 3078000 : MAP_IDX_T const * chain = MAP_(private_chain_const)( map );
494 :
495 : /* Find first element. If the map is empty, chain_rem will be 0 and
496 : ele_idx will be idx_null. */
497 :
498 3078000 : ulong chain_rem = map->chain_cnt; /* At least 1 */
499 3078000 : ulong ele_idx;
500 10746801 : do {
501 10746801 : ele_idx = MAP_(private_unbox)( chain[ chain_rem-1UL ] );
502 10746801 : if( !MAP_(private_idx_is_null)( ele_idx ) ) break;
503 10746801 : } while( --chain_rem );
504 :
505 3078000 : MAP_(iter_t) iter;
506 3078000 : iter.chain_rem = chain_rem;
507 3078000 : iter.ele_idx = ele_idx;
508 3078000 : return iter;
509 3078000 : }
510 :
511 : FD_FN_CONST static inline int
512 : MAP_(iter_done)( MAP_(iter_t) iter,
513 : MAP_(t) const * join,
514 791046000 : MAP_ELE_T const * pool ) {
515 791046000 : (void)join; (void)pool;
516 791046000 : return !iter.chain_rem;
517 791046000 : }
518 :
519 : FD_FN_PURE static inline MAP_(iter_t)
520 : MAP_(iter_next)( MAP_(iter_t) iter,
521 : MAP_(t) const * join,
522 787968000 : MAP_ELE_T const * pool ) {
523 : # if FD_TMPL_USE_HANDHOLDING
524 : if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
525 : # endif
526 787968000 : ulong chain_rem = iter.chain_rem;
527 787968000 : ulong ele_idx = iter.ele_idx;
528 :
529 : /* At this point, we are just finished iterating over element ele_idx
530 : on chain chain_rem-1 and we already iterated over all elements in
531 : chains (chain_rem,chain_cnt] and all elements in chain chain_rem-1
532 : before this element. As such, ele_idx is in [0,ele_cnt) and
533 : chain_rem is in (0,chain_cnt]. Get the next element in the chain
534 : chain_rem-1. */
535 :
536 787968000 : ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT );
537 787968000 : if( MAP_(private_idx_is_null)( ele_idx ) ) {
538 :
539 : /* There were no more elements in chain chain_rem-1. Find the next
540 : chain to start processing. If all unprocessed chains are empty,
541 : then we are done. */
542 :
543 380909301 : MAP_IDX_T const * chain = MAP_(private_chain_const)( MAP_(private_const)( join ) );
544 780293199 : while( --chain_rem ) {
545 777221199 : ele_idx = MAP_(private_unbox)( chain[ chain_rem-1UL ] );
546 777221199 : if( !MAP_(private_idx_is_null)( ele_idx ) ) break;
547 777221199 : }
548 :
549 380909301 : }
550 :
551 787968000 : iter.chain_rem = chain_rem;
552 787968000 : iter.ele_idx = ele_idx;
553 787968000 : return iter;
554 787968000 : }
555 :
556 : FD_FN_CONST static inline ulong
557 : MAP_(iter_idx)( MAP_(iter_t) iter,
558 : MAP_(t) const * join,
559 787968000 : MAP_ELE_T * pool ) {
560 : # if FD_TMPL_USE_HANDHOLDING
561 : if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
562 : # endif
563 787968000 : (void)join; (void)pool;
564 787968000 : return iter.ele_idx;
565 787968000 : }
566 :
567 : FD_FN_CONST static inline MAP_ELE_T *
568 : MAP_(iter_ele)( MAP_(iter_t) iter,
569 : MAP_(t) const * join,
570 787968000 : MAP_ELE_T * pool ) {
571 : # if FD_TMPL_USE_HANDHOLDING
572 : if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
573 : # endif
574 787968000 : (void)join;
575 787968000 : return pool + iter.ele_idx;
576 787968000 : }
577 :
578 : FD_FN_CONST static inline MAP_ELE_T const *
579 : MAP_(iter_ele_const) ( MAP_(iter_t) iter,
580 : MAP_(t) const * join,
581 787968000 : MAP_ELE_T const * pool ) {
582 : # if FD_TMPL_USE_HANDHOLDING
583 : if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
584 : # endif
585 787968000 : (void)join;
586 787968000 : return pool + iter.ele_idx;
587 787968000 : }
588 :
589 : FD_PROTOTYPES_END
590 :
591 : #endif
592 :
593 : #if MAP_IMPL_STYLE==1 /* need prototypes */
594 :
595 : FD_PROTOTYPES_BEGIN
596 :
597 : FD_FN_CONST ulong MAP_(align) ( void );
598 : FD_FN_CONST ulong MAP_(footprint)( ulong chain_cnt );
599 : void * MAP_(new) ( void * shmem, ulong chain_cnt, ulong seed );
600 : MAP_(t) * MAP_(join) ( void * shmap );
601 : void * MAP_(leave) ( MAP_(t) * join );
602 : void * MAP_(delete) ( void * shmap );
603 :
604 : MAP_(t) *
605 : MAP_(idx_insert)( MAP_(t) * join,
606 : ulong ele_idx,
607 : MAP_ELE_T * pool );
608 :
609 : ulong
610 : MAP_(idx_remove)( MAP_(t) * join,
611 : MAP_KEY_T const * key,
612 : ulong sentinel,
613 : MAP_ELE_T * pool );
614 :
615 : FD_FN_PURE ulong
616 : MAP_(idx_query)( MAP_(t) * join,
617 : MAP_KEY_T const * key,
618 : ulong sentinel,
619 : MAP_ELE_T * pool );
620 :
621 : FD_FN_PURE ulong
622 : MAP_(idx_query_const)( MAP_(t) const * join,
623 : MAP_KEY_T const * key,
624 : ulong sentinel,
625 : MAP_ELE_T const * pool );
626 :
627 : #if MAP_MULTI!=0
628 :
629 : FD_FN_PURE ulong
630 : MAP_(idx_next_const)( ulong prev, // Previous result of mymap_idx_query_const
631 : ulong sentinel, // Value to return on failure
632 : MAP_ELE_T const * pool ); // Current local join to element storage
633 :
634 : #endif /* MAP_MULTI!=0 */
635 :
636 : int
637 : MAP_(verify)( MAP_(t) const * join,
638 : ulong ele_cnt,
639 : MAP_ELE_T const * pool );
640 :
641 : FD_PROTOTYPES_END
642 :
643 : #else /* need implementations */
644 :
645 : #if MAP_IMPL_STYLE==0 /* local only */
646 : #define MAP_IMPL_STATIC FD_FN_UNUSED static
647 : #else
648 : #define MAP_IMPL_STATIC
649 : #endif
650 :
651 7776 : FD_FN_CONST MAP_IMPL_STATIC ulong MAP_(align)( void ) { return alignof(MAP_(t)); }
652 :
653 : FD_FN_CONST MAP_IMPL_STATIC ulong
654 3867 : MAP_(footprint)( ulong chain_cnt ) {
655 3867 : if( !(fd_ulong_is_pow2( chain_cnt ) & (chain_cnt<=MAP_(chain_max)())) ) return 0UL;
656 3831 : return fd_ulong_align_up( sizeof(MAP_(t)) + chain_cnt*sizeof(MAP_IDX_T), alignof(MAP_(t)) ); /* no overflow */
657 3867 : }
658 :
659 : MAP_IMPL_STATIC void *
660 : MAP_(new)( void * shmap,
661 : ulong chain_cnt,
662 1098 : ulong seed ) {
663 :
664 1098 : if( FD_UNLIKELY( !shmap ) ) {
665 6 : FD_LOG_WARNING(( "NULL shmap" ));
666 6 : return NULL;
667 6 : }
668 :
669 1092 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmap, MAP_(align)() ) ) ) {
670 6 : FD_LOG_WARNING(( "misaligned shmap" ));
671 6 : return NULL;
672 6 : }
673 :
674 1086 : ulong footprint = MAP_(footprint)( chain_cnt );
675 1086 : if( FD_UNLIKELY( !footprint ) ) {
676 18 : FD_LOG_WARNING(( "bad footprint" ));
677 18 : return NULL;
678 18 : }
679 :
680 : /* seed is arbitrary */
681 :
682 : /* Init the metadata */
683 :
684 1068 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
685 :
686 1068 : map->seed = seed;
687 1068 : map->chain_cnt = chain_cnt;
688 :
689 : /* Set all the chains to NULL */
690 :
691 1068 : MAP_IDX_T * chain = MAP_(private_chain)( map );
692 3365631 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) chain[ chain_idx ] = MAP_(private_box)( MAP_(private_idx_null)() );
693 :
694 1068 : FD_COMPILER_MFENCE();
695 1068 : FD_VOLATILE( map->magic ) = MAP_MAGIC;
696 1068 : FD_COMPILER_MFENCE();
697 :
698 1068 : return shmap;
699 1086 : }
700 :
701 : MAP_IMPL_STATIC MAP_(t) *
702 1152 : MAP_(join)( void * shmap ) {
703 1152 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
704 :
705 1152 : if( FD_UNLIKELY( !map ) ) {
706 6 : FD_LOG_WARNING(( "NULL shmap" ));
707 6 : return NULL;
708 6 : }
709 :
710 1146 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) ) ) {
711 6 : FD_LOG_WARNING(( "misaligned shmap" ));
712 6 : return NULL;
713 6 : }
714 :
715 1140 : if( FD_UNLIKELY( map->magic!=MAP_MAGIC ) ) {
716 6 : FD_LOG_WARNING(( "bad magic" ));
717 6 : return NULL;
718 6 : }
719 :
720 1134 : return (MAP_(t) *)map;
721 1140 : }
722 :
723 : MAP_IMPL_STATIC void *
724 18 : MAP_(leave)( MAP_(t) * join ) {
725 :
726 18 : if( FD_UNLIKELY( !join ) ) {
727 6 : FD_LOG_WARNING(( "NULL join" ));
728 6 : return NULL;
729 6 : }
730 :
731 12 : return (void *)join;
732 18 : }
733 :
734 : MAP_IMPL_STATIC void *
735 24 : MAP_(delete)( void * shmap ) {
736 24 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
737 :
738 24 : if( FD_UNLIKELY( !map ) ) {
739 6 : FD_LOG_WARNING(( "NULL shmap" ));
740 6 : return NULL;
741 6 : }
742 :
743 18 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) ) ) {
744 6 : FD_LOG_WARNING(( "misaligned shmap" ));
745 6 : return NULL;
746 6 : }
747 :
748 12 : if( FD_UNLIKELY( map->magic!=MAP_MAGIC ) ) {
749 6 : FD_LOG_WARNING(( "bad magic" ));
750 6 : return NULL;
751 6 : }
752 :
753 6 : FD_COMPILER_MFENCE();
754 6 : FD_VOLATILE( map->magic ) = 0UL;
755 6 : FD_COMPILER_MFENCE();
756 :
757 6 : return shmap;
758 12 : }
759 :
760 : FD_FN_PURE MAP_IMPL_STATIC ulong
761 : MAP_(idx_query)( MAP_(t) * join,
762 : MAP_KEY_T const * key,
763 : ulong sentinel,
764 1201348002 : MAP_ELE_T * pool ) {
765 1201348002 : MAP_(private_t) * map = MAP_(private)( join );
766 :
767 : /* Find the key */
768 :
769 1201348002 : MAP_IDX_T * head = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
770 1201348002 : MAP_IDX_T * cur = head;
771 2116219734 : for(;;) {
772 2116219734 : ulong ele_idx = MAP_(private_unbox)( *cur );
773 2116219734 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
774 1321385370 : if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) { /* optimize for found */
775 : /* Found, move it to the front of the chain */
776 406513638 : if( FD_UNLIKELY( cur!=head ) ) { /* Assume already at head from previous query */
777 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
778 0 : 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;
779 0 : pool[ ele_idx ].MAP_PREV = MAP_(private_box)( MAP_(private_idx_null)() );
780 : #endif
781 289306677 : *cur = pool[ ele_idx ].MAP_NEXT;
782 289306677 : pool[ ele_idx ].MAP_NEXT = *head;
783 289306677 : *head = MAP_(private_box)( ele_idx );
784 289306677 : }
785 406513638 : return ele_idx;
786 406513638 : }
787 914871732 : cur = &pool[ ele_idx ].MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
788 914871732 : }
789 :
790 : /* Not found */
791 :
792 794834364 : return sentinel;
793 1201348002 : }
794 :
795 : MAP_IMPL_STATIC MAP_(t) *
796 : MAP_(idx_insert)( MAP_(t) * join,
797 : ulong ele_idx,
798 16729482 : MAP_ELE_T * pool ) {
799 : # if FD_TMPL_USE_HANDHOLDING && !MAP_MULTI
800 : if( FD_UNLIKELY( MAP_(idx_query)( join, &pool[ ele_idx ].MAP_KEY, 0UL, pool ) ) ) FD_LOG_CRIT(( "ele_idx already in map" ));
801 : # endif
802 16729482 : MAP_(private_t) * map = MAP_(private)( join );
803 :
804 16729482 : MAP_IDX_T * head = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( &pool[ ele_idx ].MAP_KEY, map->seed, map->chain_cnt );
805 :
806 : # if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
807 13581321 : if( FD_UNLIKELY( !MAP_(private_idx_is_null)( *head ) ) ) pool[ *head ].MAP_PREV = MAP_(private_box)( ele_idx );
808 13581321 : pool[ ele_idx ].MAP_PREV = MAP_(private_box)( MAP_(private_idx_null)() );
809 : # endif
810 16729482 : pool[ ele_idx ].MAP_NEXT = *head;
811 16729482 : *head = MAP_(private_box)( ele_idx );
812 :
813 16729482 : return join;
814 16729482 : }
815 :
816 : MAP_IMPL_STATIC ulong
817 : MAP_(idx_remove)( MAP_(t) * join,
818 : MAP_KEY_T const * key,
819 : ulong sentinel,
820 7765491 : MAP_ELE_T * pool ) {
821 7765491 : MAP_(private_t) * map = MAP_(private)( join );
822 :
823 : /* Find the key */
824 :
825 7765491 : MAP_IDX_T * cur = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
826 11893191 : for(;;) {
827 11893191 : ulong ele_idx = MAP_(private_unbox)( *cur );
828 11893191 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found (it is remove after all) */
829 7274820 : if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) { /* " */
830 3147120 : *cur = pool[ ele_idx ].MAP_NEXT;
831 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
832 : 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;
833 : #endif
834 3147120 : return ele_idx;
835 3147120 : }
836 4127700 : cur = &pool[ ele_idx ].MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
837 4127700 : }
838 :
839 : /* Not found */
840 :
841 4618371 : return sentinel;
842 7765491 : }
843 :
844 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
845 : MAP_IMPL_STATIC void
846 : MAP_(idx_remove_fast)( MAP_(t) * join,
847 : ulong ele_idx,
848 13580835 : MAP_ELE_T * pool ) {
849 13580835 : MAP_(private_t) * map = MAP_(private)( join );
850 :
851 13580835 : MAP_ELE_T * ele = pool+ele_idx;
852 :
853 13580835 : if( FD_UNLIKELY( !MAP_(private_idx_is_null)( ele->MAP_NEXT ) ) ) pool[ ele->MAP_NEXT ].MAP_PREV = ele->MAP_PREV;
854 :
855 13580835 : if( FD_UNLIKELY( !MAP_(private_idx_is_null)( ele->MAP_PREV ) ) ) pool[ ele->MAP_PREV ].MAP_NEXT = ele->MAP_NEXT;
856 13069989 : else { MAP_(private_chain)( map )[ MAP_(private_chain_idx)( &ele->MAP_KEY, map->seed, map->chain_cnt ) ] = ele->MAP_NEXT; }
857 13580835 : }
858 : #endif
859 :
860 : FD_FN_PURE MAP_IMPL_STATIC ulong
861 : MAP_(idx_query_const)( MAP_(t) const * join,
862 : MAP_KEY_T const * key,
863 : ulong sentinel,
864 2192680332 : MAP_ELE_T const * pool ) {
865 2192680332 : MAP_(private_t) const * map = MAP_(private_const)( join );
866 :
867 : /* Find the key */
868 :
869 2192680332 : MAP_IDX_T const * cur = MAP_(private_chain_const)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
870 3404266761 : for(;;) {
871 3404266761 : ulong ele_idx = MAP_(private_unbox)( *cur );
872 3404266761 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
873 3402730728 : if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) return ele_idx; /* optimize for found */
874 1211586429 : cur = &pool[ ele_idx ].MAP_NEXT;
875 1211586429 : }
876 :
877 : /* Not found */
878 :
879 1536033 : return sentinel;
880 2192680332 : }
881 :
882 : #if MAP_MULTI!=0
883 :
884 : FD_FN_PURE MAP_IMPL_STATIC ulong
885 : MAP_(idx_next_const)( ulong prev, // Previous result of mymap_idx_query_const
886 : ulong sentinel, // Value to return on failure
887 688806891 : MAP_ELE_T const * pool ) { // Current local join to element storage
888 : /* Go to next element in chain */
889 :
890 688806891 : MAP_ELE_T const * prev_ele = &pool[ prev ];
891 688806891 : MAP_IDX_T const * cur = &prev_ele->MAP_NEXT;
892 928248687 : for(;;) {
893 928248687 : ulong ele_idx = MAP_(private_unbox)( *cur );
894 928248687 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
895 928248657 : if( FD_LIKELY( MAP_(key_eq)( &prev_ele->MAP_KEY, &pool[ ele_idx ].MAP_KEY ) ) ) return ele_idx; /* optimize for found */
896 239441796 : cur = &pool[ ele_idx ].MAP_NEXT;
897 239441796 : }
898 :
899 : /* Not found */
900 :
901 30 : return sentinel;
902 688806891 : }
903 :
904 : #endif /* MAP_MULTI!=0 */
905 :
906 : MAP_IMPL_STATIC int
907 : MAP_(verify)( MAP_(t) const * join,
908 : ulong ele_cnt,
909 6144024 : MAP_ELE_T const * pool ) {
910 :
911 5649569136 : # define MAP_TEST(c) do { \
912 5649569136 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
913 5649569136 : } while(0)
914 :
915 : /* Validate input arguments */
916 :
917 6144024 : MAP_TEST( join );
918 6144018 : MAP_TEST( ele_cnt<=MAP_(ele_max)() );
919 6144012 : MAP_TEST( (!!pool) | (!ele_cnt) );
920 :
921 : /* Validate metadata */
922 :
923 6144006 : MAP_(private_t) const * map = MAP_(private_const)( join );
924 :
925 6144006 : MAP_TEST( map->magic==MAP_MAGIC );
926 :
927 6144006 : ulong seed = map->seed;
928 : /* seed is arbitrary */
929 :
930 6144006 : ulong chain_cnt = map->chain_cnt;
931 6144006 : MAP_TEST( fd_ulong_is_pow2( chain_cnt ) );
932 6144006 : MAP_TEST( chain_cnt<=MAP_(chain_max)() );
933 :
934 : /* Visit each map entry, doing simple chain integrity checks */
935 :
936 6144006 : MAP_IDX_T const * chain = MAP_(private_chain_const)( map );
937 :
938 6144006 : ulong rem = ele_cnt; /* We can visit at most ele_cnt elements */
939 1579009542 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ )
940 1572865536 : for( ulong ele_idx = MAP_(private_unbox)( chain[ chain_idx ] );
941 2976041802 : !MAP_(private_idx_is_null)( ele_idx );
942 1572865536 : ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT ) ) {
943 1403176266 : MAP_TEST( rem ); rem--; /* Check for cycles */
944 1403176266 : MAP_TEST( ele_idx<ele_cnt ); /* Check valid element index */
945 1403176266 : MAP_TEST( MAP_(private_chain_idx)( &pool[ ele_idx ].MAP_KEY, seed, chain_cnt )==chain_idx ); /* Check in correct chain */
946 1403176266 : }
947 :
948 : /* At this point, we know that there are no cycles in the map chains,
949 : all indices are inbounds and elements are in the correct chains for
950 : probes. It is possible for there to be keys that have been
951 : inserted more than once though. We visit all the nodes a second
952 : time and make sure each probe resolves to itself to prove the key
953 : of every element in the map is unique. (We could do this faster if
954 : we could tag the elements but this verify is written to not modify
955 : any memory.) */
956 :
957 1579009542 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ )
958 1572865536 : for( ulong ele_idx = MAP_(private_unbox)( chain[ chain_idx ] );
959 2976041802 : !MAP_(private_idx_is_null)( ele_idx );
960 1572865536 : ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT ) ) {
961 : #if MAP_MULTI==0
962 786432000 : MAP_TEST( MAP_(idx_query_const)( join, &pool[ ele_idx ].MAP_KEY, ULONG_MAX, pool )==ele_idx );
963 : #else
964 : ulong idx2;
965 616744266 : for (idx2 = MAP_(idx_query_const)( join, &pool[ ele_idx ].MAP_KEY, ULONG_MAX, pool );
966 1046106888 : idx2 != ULONG_MAX && idx2 != ele_idx;
967 429362622 : idx2 = MAP_(idx_next_const)( idx2, ULONG_MAX, pool )) ;
968 616744266 : MAP_TEST( idx2 == ele_idx );
969 : #endif
970 1403176266 : }
971 :
972 6144006 : # undef MAP_TEST
973 :
974 6144006 : return 0;
975 6144006 : }
976 :
977 : #undef MAP_IMPL_STATIC
978 :
979 : #endif
980 :
981 : #if MAP_IMPL_STYLE==0 || MAP_IMPL_STYLE==1 /* need inlines */
982 :
983 : FD_PROTOTYPES_BEGIN
984 :
985 : static inline MAP_(t) *
986 : MAP_(ele_insert)( MAP_(t) * join,
987 : MAP_ELE_T * ele,
988 16729482 : MAP_ELE_T * pool ) {
989 16729482 : return MAP_(idx_insert)( join, (ulong)(ele-pool), pool );
990 16729482 : }
991 :
992 : static inline MAP_ELE_T *
993 : MAP_(ele_remove)( MAP_(t) * join,
994 : MAP_KEY_T const * key,
995 : MAP_ELE_T * sentinel,
996 7680003 : MAP_ELE_T * pool ) {
997 7680003 : ulong ele_idx = MAP_(idx_remove)( join, key, MAP_(private_idx_null)(), pool );
998 7680003 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
999 7680003 : }
1000 :
1001 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
1002 : static inline MAP_ELE_T *
1003 : MAP_(ele_remove_fast)( MAP_(t) * join,
1004 : MAP_ELE_T * ele,
1005 13580835 : MAP_ELE_T * pool ) {
1006 13580835 : MAP_(idx_remove_fast)( join, (ulong)(ele-pool), pool );
1007 13580835 : return ele;
1008 13580835 : }
1009 : #endif
1010 :
1011 : FD_FN_PURE static inline MAP_ELE_T *
1012 : MAP_(ele_query)( MAP_(t) * join,
1013 : MAP_KEY_T const * key,
1014 : MAP_ELE_T * sentinel,
1015 1201347999 : MAP_ELE_T * pool ) {
1016 1201347999 : ulong ele_idx = MAP_(idx_query)( join, key, MAP_(private_idx_null)(), pool );
1017 1201347999 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
1018 1201347999 : }
1019 :
1020 : FD_FN_PURE static inline MAP_ELE_T const *
1021 : MAP_(ele_query_const)( MAP_(t) const * join,
1022 : MAP_KEY_T const * key,
1023 : MAP_ELE_T const * sentinel,
1024 789504009 : MAP_ELE_T const * pool ) {
1025 789504009 : ulong ele_idx = MAP_(idx_query_const)( join, key, MAP_(private_idx_null)(), pool );
1026 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 );
1027 789504009 : }
1028 :
1029 : #if MAP_MULTI!=0
1030 :
1031 : FD_FN_PURE static inline MAP_ELE_T const * // Found element on success (will be from pool), sentinel on failure
1032 : MAP_(ele_next_const)( MAP_ELE_T const * prev, // Previous result of mymap_ele_query_const
1033 : MAP_ELE_T const * sentinel, // Value to return if key not in map
1034 259444236 : MAP_ELE_T const * pool ) { // Current local join to element storage
1035 259444236 : ulong ele_idx = MAP_(idx_next_const)( (ulong)(prev-pool), MAP_(private_idx_null)(), pool );
1036 259444236 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), pool + ele_idx, sentinel );
1037 259444236 : }
1038 :
1039 : #endif /* MAP_MULTI!=0 */
1040 :
1041 : FD_PROTOTYPES_END
1042 :
1043 : #endif
1044 :
1045 : #undef MAP_
1046 :
1047 : #undef MAP_IMPL_STYLE
1048 : #undef MAP_MAGIC
1049 : #undef MAP_KEY_HASH
1050 : #undef MAP_KEY_EQ
1051 : #undef MAP_NEXT
1052 : #undef MAP_PREV
1053 : #undef MAP_IDX_T
1054 : #undef MAP_KEY
1055 : #undef MAP_KEY_T
1056 : #undef MAP_ELE_T
1057 : #undef MAP_NAME
1058 : #undef MAP_MULTI
1059 : #undef MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
|
