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 387 : #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 6114 : #define MAP_IDX_T ulong
305 : #endif
306 :
307 : /* MAP_NEXT is the MAP_ELE_T next field */
308 :
309 : #ifndef MAP_NEXT
310 453 : #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 5651998296 : #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 1038 : #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 1200 : #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 : /* MAP_INSERT_FENCE prevents the compiler from reordering the two
356 : operations: setting the next pointer of the new chain head and
357 : updating the chain head. */
358 :
359 : #ifndef MAP_INSERT_FENCE
360 : #define MAP_INSERT_FENCE 0
361 : #endif
362 :
363 : /* Implementation *****************************************************/
364 :
365 : /* Constructors and verification log details on failure (rest only needs
366 : fd_bits.h, consider making logging a compile time option). */
367 :
368 : #include "../log/fd_log.h"
369 :
370 43605174394 : #define MAP_(n) FD_EXPAND_THEN_CONCAT3(MAP_NAME,_,n)
371 :
372 : #if MAP_IMPL_STYLE==0 || MAP_IMPL_STYLE==1 /* need structures and inlines */
373 :
374 : struct MAP_(private) {
375 :
376 : /* join points here */
377 :
378 : /* FIXME: consider having an ele_cnt for number of elements in the
379 : underlying storage? (probably not) consider having a memo of the
380 : chain in which an element is stored and/or using doubly linked
381 : chains? We could do a faster remove by index then. */
382 :
383 : ulong magic; /* == MAP_MAGIC */
384 : ulong seed; /* Hash seed, arbitrary */
385 : ulong chain_cnt; /* Number of chains, positive integer power-of-two */
386 :
387 : /* MAP_IDX_T chain[ chain_cnt ] here */
388 :
389 : };
390 :
391 : typedef struct MAP_(private) MAP_(private_t);
392 :
393 : typedef MAP_(private_t) MAP_(t);
394 :
395 : struct MAP_(iter) {
396 : ulong chain_rem;
397 : ulong ele_idx;
398 : };
399 :
400 : typedef struct MAP_(iter) MAP_(iter_t);
401 :
402 : FD_PROTOTYPES_BEGIN
403 :
404 : /* map_private returns the location of the map private for a current
405 : local join. Assumes join is a current local join. map_private_const
406 : is a const correct version. */
407 :
408 1239430491 : FD_FN_CONST static inline MAP_(private_t) * MAP_(private) ( MAP_(t) * join ) { return join; }
409 2582816971 : FD_FN_CONST static inline MAP_(private_t) const * MAP_(private_const)( MAP_(t) const * join ) { return join; }
410 :
411 : /* map_private_chain returns the location in the caller's address space
412 : of the map chains. Assumes map is valid. map_private_chain_const is
413 : a const correct version. */
414 :
415 : FD_FN_CONST static inline MAP_IDX_T *
416 1238920741 : MAP_(private_chain)( MAP_(private_t) * map ) {
417 1238920741 : return (MAP_IDX_T *)(map+1);
418 1238920741 : }
419 :
420 : FD_FN_CONST static inline MAP_IDX_T const *
421 2582816953 : MAP_(private_chain_const)( MAP_(private_t) const * map ) {
422 2582816953 : return (MAP_IDX_T const *)(map+1);
423 2582816953 : }
424 :
425 : /* map_private_chain_idx returns the index of the chain (in
426 : [0,chain_cnt) that will contain the element corresponding to key (if
427 : present at all) for a map with chain_cnt elements and seed. Assumes
428 : chain_cnt is an integer power-of-two. Assumes key points to a key is
429 : in the caller's address space that will not be changed concurrently.
430 : Retains no interest in key on return. */
431 :
432 : FD_FN_PURE static inline ulong
433 : MAP_(private_chain_idx)( MAP_KEY_T const * key,
434 : ulong seed,
435 4834780195 : ulong chain_cnt ) {
436 4834780195 : return (MAP_KEY_HASH( (key), (seed) )) & (chain_cnt-1UL);
437 4834780195 : }
438 :
439 : /* map_private_{box,unbox} compress / decompress 64-bit in-register
440 : indices to/from their in-memory representations. */
441 :
442 330798865 : FD_FN_CONST static inline MAP_IDX_T MAP_(private_box) ( ulong idx ) { return (MAP_IDX_T)idx; }
443 14007291518 : FD_FN_CONST static inline ulong MAP_(private_unbox)( MAP_IDX_T cidx ) { return (ulong) cidx; }
444 :
445 : /* map_private_idx_null returns the element storage index that
446 : represents NULL. */
447 :
448 3854008845 : FD_FN_CONST static inline ulong MAP_(private_idx_null)( void ) { return (ulong)(MAP_IDX_T)(~0UL); }
449 :
450 : /* map_private_idx_is_null returns 1 if idx is the NULL map index
451 : and 0 otherwise. */
452 :
453 16306017986 : FD_FN_CONST static inline int MAP_(private_idx_is_null)( ulong idx ) { return idx==(ulong)(MAP_IDX_T)(~0UL); }
454 :
455 12147798 : FD_FN_CONST static inline ulong MAP_(ele_max)( void ) { return (ulong)(MAP_IDX_T)(~0UL); }
456 :
457 : FD_FN_CONST static inline ulong
458 12152175 : MAP_(chain_max)( void ) {
459 12152175 : return fd_ulong_pow2_dn( (ULONG_MAX + 1UL - alignof(MAP_(t)) - sizeof(MAP_(t))) / sizeof(MAP_IDX_T) );
460 12152175 : }
461 :
462 : FD_FN_CONST static inline ulong
463 6002781 : MAP_(chain_cnt_est)( ulong ele_max_est ) {
464 :
465 : /* Clamp to be in [1,ele_max] (as ele_max_est 0 is degenerate and as
466 : the map is guaranteed to hold at most ele_max keys). */
467 :
468 6002781 : ele_max_est = fd_ulong_min( fd_ulong_max( ele_max_est, 1UL ), MAP_(ele_max)() );
469 :
470 : /* Compute the number of chains as the power of 2 that makes the
471 : average chain length between ~1 and ~2 when ele_max_est are stored
472 : in the map and then clamp to the chain max. */
473 :
474 6002781 : 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 */
475 6002781 : ulong chain_cnt = fd_ulong_pow2_up( chain_min ); /* Power of 2 in [1,2^63] */
476 :
477 6002781 : return fd_ulong_min( chain_cnt, MAP_(chain_max)() );
478 6002781 : }
479 :
480 12 : FD_FN_PURE static inline ulong MAP_(chain_cnt)( MAP_(t) const * join ) { return MAP_(private_const)( join )->chain_cnt; }
481 6 : FD_FN_PURE static inline ulong MAP_(seed) ( MAP_(t) const * join ) { return MAP_(private_const)( join )->seed; }
482 :
483 : FD_FN_PURE static inline int
484 : MAP_(key_eq)( MAP_KEY_T const * k0,
485 5683644425 : MAP_KEY_T const * k1 ) {
486 5683644425 : return !!(MAP_KEY_EQ( (k0), (k1) ));
487 5683644425 : }
488 :
489 : FD_FN_PURE static inline ulong
490 : MAP_(key_hash)( MAP_KEY_T const * key,
491 6001038 : ulong seed ) {
492 6001038 : return (MAP_KEY_HASH( (key), (seed) ));
493 6001038 : }
494 :
495 : FD_FN_PURE static inline MAP_(iter_t)
496 : MAP_(iter_init)( MAP_(t) const * join,
497 3078885 : MAP_ELE_T const * pool ) {
498 3078885 : (void)pool;
499 :
500 3078885 : MAP_(private_t) const * map = MAP_(private_const)( join );
501 3078885 : MAP_IDX_T const * chain = MAP_(private_chain_const)( map );
502 :
503 : /* Find first element. If the map is empty, chain_rem will be 0 and
504 : ele_idx will be idx_null. */
505 :
506 3078885 : ulong chain_rem = map->chain_cnt; /* At least 1 */
507 3078885 : ulong ele_idx;
508 15988090 : do {
509 15988090 : ele_idx = MAP_(private_unbox)( chain[ chain_rem-1UL ] );
510 15988090 : if( !MAP_(private_idx_is_null)( ele_idx ) ) break;
511 15988090 : } while( --chain_rem );
512 :
513 3078885 : MAP_(iter_t) iter;
514 3078885 : iter.chain_rem = chain_rem;
515 3078885 : iter.ele_idx = ele_idx;
516 3078885 : return iter;
517 3078885 : }
518 :
519 : FD_FN_CONST static inline int
520 : MAP_(iter_done)( MAP_(iter_t) iter,
521 : MAP_(t) const * join,
522 791047371 : MAP_ELE_T const * pool ) {
523 791047371 : (void)join; (void)pool;
524 791047371 : return !iter.chain_rem;
525 791047371 : }
526 :
527 : FD_FN_PURE static inline MAP_(iter_t)
528 : MAP_(iter_next)( MAP_(iter_t) iter,
529 : MAP_(t) const * join,
530 787968486 : MAP_ELE_T const * pool ) {
531 : # if FD_TMPL_USE_HANDHOLDING
532 : if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
533 : # endif
534 787968486 : ulong chain_rem = iter.chain_rem;
535 787968486 : ulong ele_idx = iter.ele_idx;
536 :
537 : /* At this point, we are just finished iterating over element ele_idx
538 : on chain chain_rem-1 and we already iterated over all elements in
539 : chains (chain_rem,chain_cnt] and all elements in chain chain_rem-1
540 : before this element. As such, ele_idx is in [0,ele_cnt) and
541 : chain_rem is in (0,chain_cnt]. Get the next element in the chain
542 : chain_rem-1. */
543 :
544 787968486 : ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT );
545 787968486 : if( MAP_(private_idx_is_null)( ele_idx ) ) {
546 :
547 : /* There were no more elements in chain chain_rem-1. Find the next
548 : chain to start processing. If all unprocessed chains are empty,
549 : then we are done. */
550 :
551 380909779 : MAP_IDX_T const * chain = MAP_(private_chain_const)( MAP_(private_const)( join ) );
552 781260554 : while( --chain_rem ) {
553 778188326 : ele_idx = MAP_(private_unbox)( chain[ chain_rem-1UL ] );
554 778188326 : if( !MAP_(private_idx_is_null)( ele_idx ) ) break;
555 778188326 : }
556 :
557 380909779 : }
558 :
559 787968486 : iter.chain_rem = chain_rem;
560 787968486 : iter.ele_idx = ele_idx;
561 787968486 : return iter;
562 787968486 : }
563 :
564 : FD_FN_CONST static inline ulong
565 : MAP_(iter_idx)( MAP_(iter_t) iter,
566 : MAP_(t) const * join,
567 787968003 : MAP_ELE_T * pool ) {
568 : # if FD_TMPL_USE_HANDHOLDING
569 : if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
570 : # endif
571 787968003 : (void)join; (void)pool;
572 787968003 : return iter.ele_idx;
573 787968003 : }
574 :
575 : FD_FN_CONST static inline MAP_ELE_T *
576 : MAP_(iter_ele)( MAP_(iter_t) iter,
577 : MAP_(t) const * join,
578 787968012 : MAP_ELE_T * pool ) {
579 : # if FD_TMPL_USE_HANDHOLDING
580 : if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
581 : # endif
582 787968012 : (void)join;
583 787968012 : return pool + iter.ele_idx;
584 787968012 : }
585 :
586 : FD_FN_CONST static inline MAP_ELE_T const *
587 : MAP_(iter_ele_const) ( MAP_(iter_t) iter,
588 : MAP_(t) const * join,
589 787968048 : MAP_ELE_T const * 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 787968048 : (void)join;
594 787968048 : return pool + iter.ele_idx;
595 787968048 : }
596 :
597 : FD_PROTOTYPES_END
598 :
599 : #endif
600 :
601 : #if MAP_IMPL_STYLE==1 /* need prototypes */
602 :
603 : FD_PROTOTYPES_BEGIN
604 :
605 : FD_FN_CONST ulong MAP_(align) ( void );
606 : FD_FN_CONST ulong MAP_(footprint)( ulong chain_cnt );
607 : void * MAP_(new) ( void * shmem, ulong chain_cnt, ulong seed );
608 : MAP_(t) * MAP_(join) ( void * shmap );
609 : void * MAP_(leave) ( MAP_(t) * join );
610 : void * MAP_(delete) ( void * shmap );
611 :
612 : MAP_(t) *
613 : MAP_(idx_insert)( MAP_(t) * join,
614 : ulong ele_idx,
615 : MAP_ELE_T * pool );
616 :
617 : ulong
618 : MAP_(idx_remove)( MAP_(t) * join,
619 : MAP_KEY_T const * key,
620 : ulong sentinel,
621 : MAP_ELE_T * pool );
622 :
623 : FD_FN_PURE ulong
624 : MAP_(idx_query)( MAP_(t) * join,
625 : MAP_KEY_T const * key,
626 : ulong sentinel,
627 : MAP_ELE_T * pool );
628 :
629 : FD_FN_PURE ulong
630 : MAP_(idx_query_const)( MAP_(t) const * join,
631 : MAP_KEY_T const * key,
632 : ulong sentinel,
633 : MAP_ELE_T const * pool );
634 :
635 : #if MAP_MULTI!=0
636 :
637 : FD_FN_PURE ulong
638 : MAP_(idx_next_const)( ulong prev, // Previous result of mymap_idx_query_const
639 : ulong sentinel, // Value to return on failure
640 : MAP_ELE_T const * pool ); // Current local join to element storage
641 :
642 : #endif /* MAP_MULTI!=0 */
643 :
644 : int
645 : MAP_(verify)( MAP_(t) const * join,
646 : ulong ele_cnt,
647 : MAP_ELE_T const * pool );
648 :
649 : FD_PROTOTYPES_END
650 :
651 : #else /* need implementations */
652 :
653 : #if MAP_IMPL_STYLE==0 /* local only */
654 : #define MAP_IMPL_STATIC FD_FN_UNUSED static
655 : #else
656 : #define MAP_IMPL_STATIC
657 : #endif
658 :
659 8847 : FD_FN_CONST MAP_IMPL_STATIC ulong MAP_(align)( void ) { return alignof(MAP_(t)); }
660 :
661 : FD_FN_CONST MAP_IMPL_STATIC ulong
662 4389 : MAP_(footprint)( ulong chain_cnt ) {
663 4389 : if( !(fd_ulong_is_pow2( chain_cnt ) & (chain_cnt<=MAP_(chain_max)())) ) return 0UL;
664 4353 : return fd_ulong_align_up( sizeof(MAP_(t)) + chain_cnt*sizeof(MAP_IDX_T), alignof(MAP_(t)) ); /* no overflow */
665 4389 : }
666 :
667 : MAP_IMPL_STATIC void *
668 : MAP_(new)( void * shmap,
669 : ulong chain_cnt,
670 1230 : ulong seed ) {
671 :
672 1230 : if( FD_UNLIKELY( !shmap ) ) {
673 6 : FD_LOG_WARNING(( "NULL shmap" ));
674 6 : return NULL;
675 6 : }
676 :
677 1224 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmap, MAP_(align)() ) ) ) {
678 6 : FD_LOG_WARNING(( "misaligned shmap" ));
679 6 : return NULL;
680 6 : }
681 :
682 1218 : ulong footprint = MAP_(footprint)( chain_cnt );
683 1218 : if( FD_UNLIKELY( !footprint ) ) {
684 18 : FD_LOG_WARNING(( "bad footprint" ));
685 18 : return NULL;
686 18 : }
687 :
688 : /* seed is arbitrary */
689 :
690 : /* Init the metadata */
691 :
692 1200 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
693 :
694 1200 : map->seed = seed;
695 1200 : map->chain_cnt = chain_cnt;
696 :
697 : /* Set all the chains to NULL */
698 :
699 1200 : MAP_IDX_T * chain = MAP_(private_chain)( map );
700 3369267 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) chain[ chain_idx ] = MAP_(private_box)( MAP_(private_idx_null)() );
701 :
702 1200 : FD_COMPILER_MFENCE();
703 1200 : FD_VOLATILE( map->magic ) = MAP_MAGIC;
704 1200 : FD_COMPILER_MFENCE();
705 :
706 1200 : return shmap;
707 1218 : }
708 :
709 : MAP_IMPL_STATIC MAP_(t) *
710 1311 : MAP_(join)( void * shmap ) {
711 1311 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
712 :
713 1311 : if( FD_UNLIKELY( !map ) ) {
714 6 : FD_LOG_WARNING(( "NULL shmap" ));
715 6 : return NULL;
716 6 : }
717 :
718 1305 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) ) ) {
719 6 : FD_LOG_WARNING(( "misaligned shmap" ));
720 6 : return NULL;
721 6 : }
722 :
723 1299 : if( FD_UNLIKELY( map->magic!=MAP_MAGIC ) ) {
724 6 : FD_LOG_WARNING(( "bad magic" ));
725 6 : return NULL;
726 6 : }
727 :
728 1293 : return (MAP_(t) *)map;
729 1299 : }
730 :
731 : MAP_IMPL_STATIC void *
732 18 : MAP_(leave)( MAP_(t) * join ) {
733 :
734 18 : if( FD_UNLIKELY( !join ) ) {
735 6 : FD_LOG_WARNING(( "NULL join" ));
736 6 : return NULL;
737 6 : }
738 :
739 12 : return (void *)join;
740 18 : }
741 :
742 : MAP_IMPL_STATIC void *
743 24 : MAP_(delete)( void * shmap ) {
744 24 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
745 :
746 24 : if( FD_UNLIKELY( !map ) ) {
747 6 : FD_LOG_WARNING(( "NULL shmap" ));
748 6 : return NULL;
749 6 : }
750 :
751 18 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) ) ) {
752 6 : FD_LOG_WARNING(( "misaligned shmap" ));
753 6 : return NULL;
754 6 : }
755 :
756 12 : if( FD_UNLIKELY( map->magic!=MAP_MAGIC ) ) {
757 6 : FD_LOG_WARNING(( "bad magic" ));
758 6 : return NULL;
759 6 : }
760 :
761 6 : FD_COMPILER_MFENCE();
762 6 : FD_VOLATILE( map->magic ) = 0UL;
763 6 : FD_COMPILER_MFENCE();
764 :
765 6 : return shmap;
766 12 : }
767 :
768 : FD_FN_PURE MAP_IMPL_STATIC ulong
769 : MAP_(idx_query)( MAP_(t) * join,
770 : MAP_KEY_T const * key,
771 : ulong sentinel,
772 1201351281 : MAP_ELE_T * pool ) {
773 1201351281 : MAP_(private_t) * map = MAP_(private)( join );
774 :
775 : /* Find the key */
776 :
777 1201351281 : MAP_IDX_T * head = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
778 1201351281 : MAP_IDX_T * cur = head;
779 2116223538 : for(;;) {
780 2116223538 : ulong ele_idx = MAP_(private_unbox)( *cur );
781 2116223538 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
782 1321386828 : if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) { /* optimize for found */
783 : /* Found, move it to the front of the chain */
784 406514571 : if( FD_UNLIKELY( cur!=head ) ) { /* Assume already at head from previous query */
785 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
786 3 : 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;
787 3 : pool[ ele_idx ].MAP_PREV = MAP_(private_box)( MAP_(private_idx_null)() );
788 3 : pool[ *head ].MAP_PREV = MAP_(private_box)( ele_idx );
789 : #endif
790 289306734 : *cur = pool[ ele_idx ].MAP_NEXT;
791 289306734 : pool[ ele_idx ].MAP_NEXT = *head;
792 289306734 : *head = MAP_(private_box)( ele_idx );
793 289306734 : }
794 406514571 : return ele_idx;
795 406514571 : }
796 914872257 : cur = &pool[ ele_idx ].MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
797 914872257 : }
798 :
799 : /* Not found */
800 :
801 794836710 : return sentinel;
802 1201351281 : }
803 :
804 : MAP_IMPL_STATIC MAP_(t) *
805 : MAP_(idx_insert)( MAP_(t) * join,
806 : ulong ele_idx,
807 16731678 : MAP_ELE_T * pool ) {
808 : # if FD_TMPL_USE_HANDHOLDING && !MAP_MULTI
809 : if( FD_UNLIKELY( !MAP_(private_idx_is_null)( MAP_(idx_query)( join, &pool[ ele_idx ].MAP_KEY, MAP_(private_idx_null)(), pool ) ) ) ) {
810 : FD_LOG_CRIT(( "ele_idx already in map" ));
811 : }
812 : # endif
813 16731678 : MAP_(private_t) * map = MAP_(private)( join );
814 :
815 16731678 : MAP_IDX_T * head = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( &pool[ ele_idx ].MAP_KEY, map->seed, map->chain_cnt );
816 :
817 : # if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
818 13582347 : if( FD_UNLIKELY( !MAP_(private_idx_is_null)( *head ) ) ) pool[ *head ].MAP_PREV = MAP_(private_box)( ele_idx );
819 13582347 : pool[ ele_idx ].MAP_PREV = MAP_(private_box)( MAP_(private_idx_null)() );
820 : # endif
821 16731678 : pool[ ele_idx ].MAP_NEXT = *head;
822 : # if MAP_INSERT_FENCE
823 51 : FD_COMPILER_MFENCE();
824 : # endif
825 16731678 : *head = MAP_(private_box)( ele_idx );
826 :
827 16731678 : return join;
828 16731678 : }
829 :
830 : MAP_IMPL_STATIC ulong
831 : MAP_(idx_remove)( MAP_(t) * join,
832 : MAP_KEY_T const * key,
833 : ulong sentinel,
834 7765671 : MAP_ELE_T * pool ) {
835 7765671 : MAP_(private_t) * map = MAP_(private)( join );
836 :
837 : /* Find the key */
838 :
839 7765671 : MAP_IDX_T * cur = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
840 11893410 : for(;;) {
841 11893410 : ulong ele_idx = MAP_(private_unbox)( *cur );
842 11893410 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found (it is remove after all) */
843 7275036 : if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) { /* " */
844 3147297 : *cur = pool[ ele_idx ].MAP_NEXT;
845 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
846 : 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;
847 : #endif
848 3147297 : return ele_idx;
849 3147297 : }
850 4127739 : cur = &pool[ ele_idx ].MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
851 4127739 : }
852 :
853 : /* Not found */
854 :
855 4618374 : return sentinel;
856 7765671 : }
857 :
858 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
859 : MAP_IMPL_STATIC void
860 : MAP_(idx_remove_fast)( MAP_(t) * join,
861 : ulong ele_idx,
862 13581861 : MAP_ELE_T * pool ) {
863 13581861 : MAP_(private_t) * map = MAP_(private)( join );
864 :
865 13581861 : MAP_ELE_T * ele = pool+ele_idx;
866 :
867 13581861 : if( FD_UNLIKELY( !MAP_(private_idx_is_null)( ele->MAP_NEXT ) ) ) pool[ ele->MAP_NEXT ].MAP_PREV = ele->MAP_PREV;
868 :
869 13581861 : if( FD_UNLIKELY( !MAP_(private_idx_is_null)( ele->MAP_PREV ) ) ) pool[ ele->MAP_PREV ].MAP_NEXT = ele->MAP_NEXT;
870 13070905 : else { MAP_(private_chain)( map )[ MAP_(private_chain_idx)( &ele->MAP_KEY, map->seed, map->chain_cnt ) ] = ele->MAP_NEXT; }
871 13581861 : }
872 : #endif
873 :
874 : FD_FN_PURE MAP_IMPL_STATIC ulong
875 : MAP_(idx_query_const)( MAP_(t) const * join,
876 : MAP_KEY_T const * key,
877 : ulong sentinel,
878 2192683290 : MAP_ELE_T const * pool ) {
879 2192683290 : MAP_(private_t) const * map = MAP_(private_const)( join );
880 :
881 : /* Find the key */
882 :
883 2192683290 : MAP_IDX_T const * cur = MAP_(private_chain_const)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
884 3404270069 : for(;;) {
885 3404270069 : ulong ele_idx = MAP_(private_unbox)( *cur );
886 3404270069 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
887 3402733898 : if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) return ele_idx; /* optimize for found */
888 1211586779 : cur = &pool[ ele_idx ].MAP_NEXT;
889 1211586779 : }
890 :
891 : /* Not found */
892 :
893 1536171 : return sentinel;
894 2192683290 : }
895 :
896 : #if MAP_MULTI!=0
897 :
898 : FD_FN_PURE MAP_IMPL_STATIC ulong
899 : MAP_(idx_next_const)( ulong prev, // Previous result of mymap_idx_query_const
900 : ulong sentinel, // Value to return on failure
901 688807017 : MAP_ELE_T const * pool ) { // Current local join to element storage
902 : /* Go to next element in chain */
903 :
904 688807017 : MAP_ELE_T const * prev_ele = &pool[ prev ];
905 688807017 : MAP_IDX_T const * cur = &prev_ele->MAP_NEXT;
906 928248813 : for(;;) {
907 928248813 : ulong ele_idx = MAP_(private_unbox)( *cur );
908 928248813 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
909 928248660 : if( FD_LIKELY( MAP_(key_eq)( &prev_ele->MAP_KEY, &pool[ ele_idx ].MAP_KEY ) ) ) return ele_idx; /* optimize for found */
910 239441796 : cur = &pool[ ele_idx ].MAP_NEXT;
911 239441796 : }
912 :
913 : /* Not found */
914 :
915 153 : return sentinel;
916 688807017 : }
917 :
918 : #endif /* MAP_MULTI!=0 */
919 :
920 : MAP_IMPL_STATIC int
921 : MAP_(verify)( MAP_(t) const * join,
922 : ulong ele_cnt,
923 6145017 : MAP_ELE_T const * pool ) {
924 :
925 5649579963 : # define MAP_TEST(c) do { \
926 5649579963 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
927 5649579963 : } while(0)
928 :
929 : /* Validate input arguments */
930 :
931 6145017 : MAP_TEST( join );
932 6145011 : MAP_TEST( ele_cnt<=MAP_(ele_max)() );
933 6145005 : MAP_TEST( (!!pool) | (!ele_cnt) );
934 :
935 : /* Validate metadata */
936 :
937 6144999 : MAP_(private_t) const * map = MAP_(private_const)( join );
938 :
939 6144999 : MAP_TEST( map->magic==MAP_MAGIC );
940 :
941 6144999 : ulong seed = map->seed;
942 : /* seed is arbitrary */
943 :
944 6144999 : ulong chain_cnt = map->chain_cnt;
945 6144999 : MAP_TEST( fd_ulong_is_pow2( chain_cnt ) );
946 6144999 : MAP_TEST( chain_cnt<=MAP_(chain_max)() );
947 :
948 : /* Visit each map entry, doing simple chain integrity checks */
949 :
950 6144999 : MAP_IDX_T const * chain = MAP_(private_chain_const)( map );
951 :
952 6144999 : ulong rem = ele_cnt; /* We can visit at most ele_cnt elements */
953 1585223031 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
954 1579078032 : ulong prev_ele = MAP_(private_idx_null)();
955 1579078032 : (void)prev_ele;
956 1579078032 : for( ulong ele_idx = MAP_(private_unbox)( chain[ chain_idx ] );
957 2982255393 : !MAP_(private_idx_is_null)( ele_idx );
958 1579078032 : ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT ) ) {
959 1403177361 : MAP_TEST( rem ); rem--; /* Check for cycles */
960 1403177361 : MAP_TEST( ele_idx<ele_cnt ); /* Check valid element index */
961 1403177361 : MAP_TEST( MAP_(private_chain_idx)( &pool[ ele_idx ].MAP_KEY, seed, chain_cnt )==chain_idx ); /* Check in correct chain */
962 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
963 489 : MAP_TEST( pool[ ele_idx ].MAP_PREV==prev_ele );
964 489 : prev_ele = ele_idx;
965 489 : #endif
966 489 : }
967 1579078032 : }
968 :
969 : /* At this point, we know that there are no cycles in the map chains,
970 : all indices are inbounds and elements are in the correct chains for
971 : probes. It is possible for there to be keys that have been
972 : inserted more than once though. We visit all the nodes a second
973 : time and make sure each probe resolves to itself to prove the key
974 : of every element in the map is unique. (We could do this faster if
975 : we could tag the elements but this verify is written to not modify
976 : any memory.) */
977 :
978 1585223031 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ )
979 1579078032 : for( ulong ele_idx = MAP_(private_unbox)( chain[ chain_idx ] );
980 2982255393 : !MAP_(private_idx_is_null)( ele_idx );
981 1579078032 : ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT ) ) {
982 : #if MAP_MULTI==0
983 786432654 : MAP_TEST( MAP_(idx_query_const)( join, &pool[ ele_idx ].MAP_KEY, ULONG_MAX, pool )==ele_idx );
984 : #else
985 : ulong idx2;
986 616744707 : for (idx2 = MAP_(idx_query_const)( join, &pool[ ele_idx ].MAP_KEY, ULONG_MAX, pool );
987 1046107332 : idx2 != ULONG_MAX && idx2 != ele_idx;
988 429362625 : idx2 = MAP_(idx_next_const)( idx2, ULONG_MAX, pool )) ;
989 616744707 : MAP_TEST( idx2 == ele_idx );
990 : #endif
991 1403177361 : }
992 :
993 6144999 : # undef MAP_TEST
994 :
995 6144999 : return 0;
996 6144999 : }
997 :
998 : #undef MAP_IMPL_STATIC
999 :
1000 : #endif
1001 :
1002 : #if MAP_IMPL_STYLE==0 || MAP_IMPL_STYLE==1 /* need inlines */
1003 :
1004 : FD_PROTOTYPES_BEGIN
1005 :
1006 : static inline MAP_(t) *
1007 : MAP_(ele_insert)( MAP_(t) * join,
1008 : MAP_ELE_T * ele,
1009 16731678 : MAP_ELE_T * pool ) {
1010 16731678 : return MAP_(idx_insert)( join, (ulong)(ele-pool), pool );
1011 16731678 : }
1012 :
1013 : static inline MAP_ELE_T *
1014 : MAP_(ele_remove)( MAP_(t) * join,
1015 : MAP_KEY_T const * key,
1016 : MAP_ELE_T * sentinel,
1017 7680144 : MAP_ELE_T * pool ) {
1018 7680144 : ulong ele_idx = MAP_(idx_remove)( join, key, MAP_(private_idx_null)(), pool );
1019 7680144 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
1020 7680144 : }
1021 :
1022 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
1023 : static inline MAP_ELE_T *
1024 : MAP_(ele_remove_fast)( MAP_(t) * join,
1025 : MAP_ELE_T * ele,
1026 13581843 : MAP_ELE_T * pool ) {
1027 13581843 : MAP_(idx_remove_fast)( join, (ulong)(ele-pool), pool );
1028 13581843 : return ele;
1029 13581843 : }
1030 : #endif
1031 :
1032 : FD_FN_PURE static inline MAP_ELE_T *
1033 : MAP_(ele_query)( MAP_(t) * join,
1034 : MAP_KEY_T const * key,
1035 : MAP_ELE_T * sentinel,
1036 1201350828 : MAP_ELE_T * pool ) {
1037 1201350828 : ulong ele_idx = MAP_(idx_query)( join, key, MAP_(private_idx_null)(), pool );
1038 1201350828 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
1039 1201350828 : }
1040 :
1041 : FD_FN_PURE static inline MAP_ELE_T const *
1042 : MAP_(ele_query_const)( MAP_(t) const * join,
1043 : MAP_KEY_T const * key,
1044 : MAP_ELE_T const * sentinel,
1045 789505188 : MAP_ELE_T const * pool ) {
1046 789505188 : ulong ele_idx = MAP_(idx_query_const)( join, key, MAP_(private_idx_null)(), pool );
1047 789505188 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T const *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
1048 789505188 : }
1049 :
1050 : #if MAP_MULTI!=0
1051 :
1052 : FD_FN_PURE static inline MAP_ELE_T const * // Found element on success (will be from pool), sentinel on failure
1053 : MAP_(ele_next_const)( MAP_ELE_T const * prev, // Previous result of mymap_ele_query_const
1054 : MAP_ELE_T const * sentinel, // Value to return if key not in map
1055 259444236 : MAP_ELE_T const * pool ) { // Current local join to element storage
1056 259444236 : ulong ele_idx = MAP_(idx_next_const)( (ulong)(prev-pool), MAP_(private_idx_null)(), pool );
1057 259444236 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), pool + ele_idx, sentinel );
1058 259444236 : }
1059 :
1060 : #endif /* MAP_MULTI!=0 */
1061 :
1062 : FD_PROTOTYPES_END
1063 :
1064 : #endif
1065 :
1066 : #undef MAP_
1067 :
1068 : #undef MAP_IMPL_STYLE
1069 : #undef MAP_MAGIC
1070 : #undef MAP_KEY_HASH
1071 : #undef MAP_KEY_EQ
1072 : #undef MAP_NEXT
1073 : #undef MAP_PREV
1074 : #undef MAP_IDX_T
1075 : #undef MAP_KEY
1076 : #undef MAP_KEY_T
1077 : #undef MAP_ELE_T
1078 : #undef MAP_NAME
1079 : #undef MAP_MULTI
1080 : #undef MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
1081 : #undef MAP_INSERT_FENCE
|
