Line data Source code
1 : /* Generate prototypes, inlines and/or implementations for ultra high
2 : performance maps based on hash chains. A map can store a practically
3 : unbounded number of elements but, if sized on creation for the
4 : maximum number of mapped elements, typical map operations are a fast
5 : O(1) time and map element overhead is a small O(1) space.
6 :
7 : This API is designed for ultra tight coupling with pools, treaps,
8 : heaps, lists, other maps, etc. Likewise, a map can be persisted
9 : beyond the lifetime of the creating process, used concurrently in
10 : many common operations, used inter-process, relocated in memory,
11 : naively serialized/deserialized, moved between hosts, supports index
12 : compression for cache and memory bandwidth efficiency, etc.
13 :
14 : Memory efficiency and flexible footprint are prioritized. Elements
15 : that are recently queried can be optionally moved to the front of
16 : hash chains to adaptively optimize the maps for recent queries in
17 : non-concurrent use cases.
18 :
19 : Typical usage:
20 :
21 : struct myele {
22 : ulong key; // Technically "MAP_KEY_T MAP_KEY" (default is ulong key), do not modify while the element is in the map
23 : ulong next; // Technically "MAP_IDX_T MAP_NEXT" (default is ulong next), do not modify while the element is in the map
24 : ... key and next can be located arbitrarily in the element and
25 : ... can be reused for other purposes when the element is not in a
26 : ... map. The mapping of a key to an element storage index is
27 : ... arbitrary but an element should not be moved / released while
28 : ... an element is in a map.
29 :
30 : ... if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL is set to 1, elements
31 : ... must also have a prev field. This field is used to optimize
32 : ... removing elements from a chain quickly, if they are pointed
33 : ... to by some other index.
34 : ulong prev; // Technically "MAP_IDX_T MAP_PREV" (default is ulong prev), do not modify while the element is in the map
35 : };
36 :
37 : typedef struct myele myele_t;
38 :
39 : #define MAP_NAME mymap
40 : #define MAP_ELE_T myele_t
41 : #include "tmpl/fd_map_chain.c"
42 :
43 : will declare the following APIs as a header only style library in the
44 : compilation unit:
45 :
46 : // mymap_ele_max returns the theoretical maximum number of elements
47 : // that can be mapped by a mymap.
48 :
49 : ulong mymap_ele_max( void );
50 :
51 : // mymap_chain_max returns the theoretical maximum number possible
52 : // chains in a mymap. Will be an integer power-of-two.
53 :
54 : ulong mymap_chain_max( void );
55 :
56 : // mymap_chain_cnt_est returns a reasonable number of chains to use
57 : // for a map that is expected to hold up to ele_max_est elements.
58 : // ele_max_est will be clamped to be in [1,mymap_ele_max()] and the
59 : // return value will be an integer power-of-two in
60 : // [1,mymap_chain_max()].
61 :
62 : ulong mymap_chain_cnt_est( ulong ele_max_est );
63 :
64 : // mymap_{align,footprint} returns the alignment and footprint
65 : // needed for a memory region to be used as a mymap. align will be
66 : // an integer power-of-two and footprint will be a multiple of
67 : // align. footprint returns 0 if chain_cnt is not an integer
68 : // power-of-two in [1,mymap_chain_max()].
69 : //
70 : // mymap_new formats a memory region with the appropriate alignment
71 : // and footprint whose first byte in the caller's address space is
72 : // pointed by shmem for use as a mymap. Returns shmem on success
73 : // and NULL on failure (logs details). Caller is not joined on
74 : // return. The map will be empty.
75 : //
76 : // mymap_join joins a mymap. Assumes shmap points at a memory
77 : // region formatted as a mymap in the caller's address space.
78 : // Returns a handle to the caller's local join on success and NULL
79 : // on failure (logs details). Do not assume this is a simple cast
80 : // of shmap!
81 : //
82 : // mymap_leave leaves a mymap. Assumes join points to a current
83 : // local join. Returns shmap used on join. Do not assume this is
84 : // a simple cast of join!
85 : //
86 : // mymap_delete unformats a memory region used as a mymap. Assumes
87 : // shmap points to a memory region in the caller's local address
88 : // space formatted as a mymap, that there are no joins to the mymap
89 : // and that any application cleanup of the entries has already been
90 : // done. Returns shmap on success and NULL on failure.
91 :
92 : ulong mymap_align ( void );
93 : ulong mymap_footprint( ulong chain_cnt );
94 : void * mymap_new ( void * shmem, ulong chain_cnt, ulong seed );
95 : mymap_t * mymap_join ( void * shmap );
96 : void * mymap_leave ( mymap_t * join );
97 : void * mymap_delete ( void * shmap );
98 :
99 : // mymap_{chain_cnt,seed} return the values used to construct the
100 : // map. They assume join is a current local join. The values will
101 : // be constant for the map lifetime.
102 :
103 : ulong mymap_chain_cnt( mymap_t const * join );
104 : ulong mymap_seed ( mymap_t const * join );
105 :
106 : // mymap_key_{eq,hash} expose the provided MAP_KEY_{EQ,HASH} macros
107 : // as inline functions with strict semantics. They assume that the
108 : // provided pointers are in the caller's address space to keys that
109 : // will not be changed concurrently. They retain no interest in
110 : // any keys on return.
111 : //
112 : // mymap_key_eq returns 1 if *k0 and *k1 are equal and 0 otherwise.
113 : //
114 : // mymap_key_hash returns the hash of *key using the hash function
115 : // seed. Should ideally be a random mapping from MAP_KEY_T to
116 : // ulong but this depends on what the user actually passed in for
117 : // MAP_KEY_HASH. The seed used by a particular instance of a map
118 : // can be obtained above.
119 :
120 : int mymap_key_eq ( ulong * k0, ulong * k1 );
121 : ulong mymap_key_hash( ulong * key, ulong seed );
122 :
123 : // mymap_idx_insert inserts an element into the map. The caller
124 : // promises the element is not currently in the map and that
125 : // element key is not equal to the key of any other element
126 : // currently in the map, except if MAP_MULTI is enabled. Assumes
127 : // there are no concurrent operations on the map. This always
128 : // succeeds.
129 :
130 : mymap_t * // Returns join
131 : mymap_idx_insert( mymap_t * join, // Current local join to element map
132 : ulong ele_idx, // Index of element to insert
133 : myele_t * pool ); // Current local join to element storage
134 :
135 : // mymap_idx_remove removes the mapping of a key to an element.
136 : // Assumes there are no concurrent operations on the map and that
137 : // *key will not be modified during the remove. The map retains no
138 : // interest in key. On success, the map will no longer have an
139 : // interest in the returned element. On failure, the returned
140 : // index lifetime will be that of the sentinel.
141 :
142 : ulong // Index of removed element on success, sentinel on failure
143 : mymap_idx_remove( mymap_t * join, // Current local join to element map
144 : ulong const * key, // Points to the key to remove in the caller's address space
145 : ulong sentinel, // Value to return if key not in map
146 : myele_t * pool ); // Current local join to element storage
147 :
148 : // mymap_idx_query finds the element corresponding to key. Assumes
149 : // there are no concurrent operations on the map and that *key will
150 : // not be modified during the query. The map retains no interest
151 : // in key. On success, the returned index lifetime will be at
152 : // least as long as the corresponding element is still in the map.
153 : // On failure, the returned index lifetime will be that of the
154 : // sentinel.
155 :
156 : ulong // Index of found element on success, sentinel on failure
157 : mymap_idx_query( mymap_t * join, // Current local join to the element map
158 : ulong const * key, // Points to the key to find in the caller's address space
159 : ulong sentinel, // Value to return on failure
160 : myele_t * pool ); // Current local join to element storage
161 :
162 : // mymap_idx_query_const is the same as mymap_idx_query but
163 : // supports concurrent queries so long as there no concurrently
164 : // running insert/remove/query operations. The value fields of the
165 : // element returned by this function can be changed by the
166 : // application but it is up to the application to manage
167 : // concurrency between different users modifying the same element.
168 :
169 : ulong // Index of found element on success, sentinel on failure
170 : mymap_idx_query_const( mymap_t const * join, // Current local join to element map
171 : ulong const * key, // Points to the key to find in the caller's address space
172 : ulong sentinel, // Value to return on failure
173 : myele_t const * pool ); // Current local join to element storage
174 :
175 : // The mymap_ele_{insert,remove,query,query_const} variants are the
176 : // same as the above but use pointers in the caller's address
177 : // instead of pool element storage indices.
178 :
179 : mymap_t * // Returns join
180 : mymap_ele_insert( mymap_t * join, // Current local join to element map
181 : myele_t * ele, // Element to insert (assumed to be in pool)
182 : myele_t * pool ); // Current local join to element storage
183 :
184 : myele_t * // Removed element on success (will be from pool), sentinel on failure
185 : mymap_ele_remove( mymap_t * join, // Current local join to element map
186 : ulong const * key, // Points to the key to remove in the caller's address space
187 : myele_t * sentinel, // Value to return if key not in map
188 : myele_t * pool ); // Current local join to element storage
189 :
190 : myele_t * // Found element on success (will be from pool), sentinel on failure
191 : mymap_ele_query( mymap_t * join, // Current local join to element map
192 : ulong const * key, // Points to the key to find in the caller's address space
193 : myele_t * sentinel, // Value to return if key not in map
194 : myele_t * pool ); // Current local join to element storage
195 :
196 : myele_t const * // Found element on success (will be from pool), sentinel on failure
197 : mymap_ele_query_const( mymap_t const * join, // Current local join to element map
198 : ulong const * key, // Points to the key to find in the caller's address space
199 : myele_t const * sentinel, // Value to return if key not in map
200 : myele_t const * pool ); // Current local join to element storage
201 :
202 : // mymap_iter_* support fast iteration over all the elements in a
203 : // map. The iteration will be in a random order but the order will
204 : // be identical if repeated with no insert/remove/query operations
205 : // done in between. Assumes no concurrent insert/remove/query
206 : // operations (query_const is fine). Example usage:
207 : //
208 : // for( mymap_iter_t iter = mymap_iter_init( join, pool );
209 : // !mymap_iter_done( iter, join, pool );
210 : // iter = mymap_iter_next( iter, join, pool ) ) {
211 : // ulong ele_idx = mymap_iter_idx( iter, join, pool );
212 : //
213 : // ... process element here
214 : //
215 : // ... IMPORTANT! It is _not_ _safe_ to insert, remove
216 : // ... or query here (query_const is fine).
217 : // }
218 :
219 : struct mymap_iter_private { ... internal use only ... };
220 : typedef struct mymap_iter_private mymap_iter_t;
221 :
222 : mymap_iter_t mymap_iter_init ( mymap_t const * join, myele_t const * pool );
223 : int mymap_iter_done ( mymap_iter_t iter, mymap_t const * join, myele_t const * pool );
224 : mymap_iter_t mymap_iter_next ( mymap_iter_t iter, mymap_t const * join, myele_t const * pool ); // assumes not done
225 : ulong mymap_iter_idx ( mymap_iter_t iter, mymap_t const * join, myele_t const * pool ); // assumes not done
226 : myele_t * mymap_iter_ele ( mymap_iter_t iter, mymap_t const * join, myele_t * pool ); // assumes not done
227 : myele_t const * mymap_iter_ele_const( mymap_iter_t iter, mymap_t const * join, myele_t const * pool ); // assumes not done
228 :
229 : // mymap_verify returns 0 if the mymap is not obviously corrupt or
230 : // -1 (i.e. ERR_INVAL) otherwise (logs details).
231 :
232 : int
233 : mymap_verify( mymap_t const * join, // Current local join to a mymap.
234 : ulong ele_cnt, // Element storage size, in [0,mymap_ele_max()]
235 : myele_t const * pool ); // Current local join to element storage, indexed [0,ele_cnt)
236 :
237 : You can do this as often as you like in a compilation unit to get
238 : different types of maps. Variants exist for making header prototypes
239 : only and/or implementations if doing a library with multiple
240 : compilation units. Further, options exist to use index compression,
241 : different hashing functions, comparison functions, etc as detailed
242 : below.
243 :
244 : If MAP_MULTI is defined to be 1, the map will support multiple
245 : entries for the same key. In this case, the existing API works as
246 : is, but new methods are provided:
247 :
248 : ulong // Index of found element on success, sentinel on failure
249 : mymap_idx_next_const( ulong prev, // Previous result of mymap_idx_query_const
250 : ulong sentinel, // Value to return on failure
251 : myele_t const * pool ); // Current local join to element storage
252 :
253 : myele_t const * // Found element on success (will be from pool), sentinel on failure
254 : mymap_ele_next_const( myele_t const * prev, // Previous result of mymap_ele_query_const
255 : myele_t const * sentinel, // Value to return if key not in map
256 : myele_t const * pool ); // Current local join to element storage
257 :
258 : These take a previous result from query_const (or next_const) and
259 : return the next element with the same key in the chain.
260 :
261 : IF MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL is defined to be 1, the map will
262 : support removing elements with a known index from the chain in O(1)
263 : time without needing to search for them in the chain. This requires
264 : threading a reverse pointer through the elements in the chain.
265 :
266 : void
267 : mymap_idx_remove_fast( mymap_t * join, // Current uslocal join to element map
268 : ulong ele_idx, // Index of element to remove in the element storage
269 : myele_t * pool ); // Current local join to element storage
270 :
271 : */
272 :
273 : #include "fd_map.h"
274 :
275 : /* MAP_NAME gives the API prefix to use for map */
276 :
277 : #ifndef MAP_NAME
278 : #error "Define MAP_NAME"
279 : #endif
280 :
281 : /* MAP_ELE_T is the map element type. */
282 :
283 : #ifndef MAP_ELE_T
284 : #error "Define MAP_ELE_T"
285 : #endif
286 :
287 : /* MAP_KEY_T is the map key type */
288 :
289 : #ifndef MAP_KEY_T
290 : #define MAP_KEY_T ulong
291 : #endif
292 :
293 : /* MAP_KEY is the MAP_ELE_T key field */
294 :
295 : #ifndef MAP_KEY
296 8692917 : #define MAP_KEY key
297 : #endif
298 :
299 : /* MAP_IDX_T is the type used for the next field in the MAP_ELE_T.
300 : Should be a primitive unsigned integer type. Defaults to ulong. A
301 : map can't use element stores with more elements than the maximum
302 : value that can be represented by a MAP_IDX_T. (E.g. if ushort, the
303 : maximum size element store usable by the map is 65535 elements.) */
304 :
305 : #ifndef MAP_IDX_T
306 9420 : #define MAP_IDX_T ulong
307 : #endif
308 :
309 : /* MAP_NEXT is the MAP_ELE_T next field */
310 :
311 : #ifndef MAP_NEXT
312 535681266 : #define MAP_NEXT next
313 : #endif
314 :
315 : /* If we're using the optimized random access removal, then we also need
316 : a MAP_ELE_T prev field. */
317 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
318 : # ifndef MAP_PREV
319 6006960 : # define MAP_PREV prev
320 : # endif
321 : #endif
322 :
323 : /* MAP_KEY_EQ returns 0/1 if *k0 is the same/different as *k1 */
324 :
325 : #ifndef MAP_KEY_EQ
326 5654307951 : #define MAP_KEY_EQ(k0,k1) ((*(k0))==(*(k1)))
327 : #endif
328 :
329 : /* MAP_KEY_HASH maps *key into ulong uniform pseudo randomly. */
330 :
331 : #ifndef MAP_KEY_HASH
332 2893239 : #define MAP_KEY_HASH(key,seed) fd_ulong_hash( (*(key)) ^ (seed) )
333 : #endif
334 :
335 : /* MAP_MAGIC is the magic number to use for the structure to aid in
336 : persistent and or IPC usage. */
337 :
338 : #ifndef MAP_MAGIC
339 1371 : #define MAP_MAGIC (0xf17eda2c37c3a900UL) /* firedancer cmap version 0 */
340 : #endif
341 :
342 : /* 0 - local use only
343 : 1 - library header declaration
344 : 2 - library implementation */
345 :
346 : #ifndef MAP_IMPL_STYLE
347 : #define MAP_IMPL_STYLE 0
348 : #endif
349 :
350 : /* 0 - do NOT support multiple values with the same key
351 : 1 - support multiple values with the same key */
352 :
353 : #ifndef MAP_MULTI
354 : #define MAP_MULTI 0
355 : #endif
356 :
357 : /* MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL controls whether the map supports
358 : removal of an element in a chain without iterating the whole chain
359 : from the beginning. */
360 :
361 : #ifndef MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
362 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 0
363 : #endif
364 :
365 : /* MAP_INSERT_FENCE prevents the compiler from reordering the two
366 : operations: setting the next pointer of the new chain head and
367 : updating the chain head. */
368 :
369 : #ifndef MAP_INSERT_FENCE
370 : #define MAP_INSERT_FENCE 0
371 : #endif
372 :
373 : /* Implementation *****************************************************/
374 :
375 : /* Constructors and verification log details on failure (rest only needs
376 : fd_bits.h, consider making logging a compile time option). */
377 :
378 : #include "../log/fd_log.h"
379 :
380 69609854343 : #define MAP_(n) FD_EXPAND_THEN_CONCAT3(MAP_NAME,_,n)
381 :
382 : #if MAP_IMPL_STYLE==0 || MAP_IMPL_STYLE==1 /* need structures and inlines */
383 :
384 : struct MAP_(private) {
385 :
386 : /* join points here */
387 :
388 : /* FIXME: consider having an ele_cnt for number of elements in the
389 : underlying storage? (probably not) consider having a memo of the
390 : chain in which an element is stored and/or using doubly linked
391 : chains? We could do a faster remove by index then. */
392 :
393 : ulong magic; /* == MAP_MAGIC */
394 : ulong seed; /* Hash seed, arbitrary */
395 : ulong chain_cnt; /* Number of chains, positive integer power-of-two */
396 :
397 : /* MAP_IDX_T chain[ chain_cnt ] here */
398 :
399 : };
400 :
401 : typedef struct MAP_(private) MAP_(private_t);
402 :
403 : typedef MAP_(private_t) MAP_(t);
404 :
405 : typedef struct fd_map_chain_iter MAP_(iter_t);
406 :
407 : FD_PROTOTYPES_BEGIN
408 :
409 : /* map_private returns the location of the map private for a current
410 : local join. Assumes join is a current local join. map_private_const
411 : is a const correct version. */
412 :
413 1259071174 : FD_FN_CONST static inline MAP_(private_t) * MAP_(private) ( MAP_(t) * join ) { return join; }
414 2842428835 : FD_FN_CONST static inline MAP_(private_t) const * MAP_(private_const)( MAP_(t) const * join ) { return join; }
415 :
416 : /* map_private_chain returns the location in the caller's address space
417 : of the map chains. Assumes map is valid. map_private_chain_const is
418 : a const correct version. */
419 :
420 : FD_FN_CONST static inline MAP_IDX_T *
421 1258368134 : MAP_(private_chain)( MAP_(private_t) * map ) {
422 1258368134 : return (MAP_IDX_T *)(map+1);
423 1258368134 : }
424 :
425 : FD_FN_CONST static inline MAP_IDX_T const *
426 2842428817 : MAP_(private_chain_const)( MAP_(private_t) const * map ) {
427 2842428817 : return (MAP_IDX_T const *)(map+1);
428 2842428817 : }
429 :
430 : /* map_private_chain_idx returns the index of the chain (in
431 : [0,chain_cnt) that will contain the element corresponding to key (if
432 : present at all) for a map with chain_cnt elements and seed. Assumes
433 : chain_cnt is an integer power-of-two. Assumes key points to a key is
434 : in the caller's address space that will not be changed concurrently.
435 : Retains no interest in key on return. */
436 :
437 : FD_FN_PURE static inline ulong
438 : MAP_(private_chain_idx)( MAP_KEY_T const * key,
439 : ulong seed,
440 5370000125 : ulong chain_cnt ) {
441 5370000125 : return (MAP_KEY_HASH( (key), (seed) )) & (chain_cnt-1UL);
442 5370000125 : }
443 :
444 : /* map_private_{box,unbox} compress / decompress 64-bit in-register
445 : indices to/from their in-memory representations. */
446 :
447 362856733 : FD_FN_CONST static inline MAP_IDX_T MAP_(private_box) ( ulong idx ) { return (MAP_IDX_T)idx; }
448 24209530685 : FD_FN_CONST static inline ulong MAP_(private_unbox)( MAP_IDX_T cidx ) { return (ulong) cidx; }
449 :
450 : /* map_private_idx_null returns the element storage index that
451 : represents NULL. */
452 :
453 8585346960 : FD_FN_CONST static inline ulong MAP_(private_idx_null)( void ) { return (ulong)(MAP_IDX_T)(~0UL); }
454 :
455 : /* map_private_idx_is_null returns 1 if idx is the NULL map index
456 : and 0 otherwise. */
457 :
458 26523607582 : FD_FN_CONST static inline int MAP_(private_idx_is_null)( ulong idx ) { return idx==(ulong)(MAP_IDX_T)(~0UL); }
459 :
460 13868964 : FD_FN_CONST static inline ulong MAP_(ele_max)( void ) { return (ulong)(MAP_IDX_T)(~0UL); }
461 :
462 : FD_FN_CONST static inline ulong
463 13874316 : MAP_(chain_max)( void ) {
464 13874316 : return fd_ulong_pow2_dn( (ULONG_MAX + 1UL - alignof(MAP_(t)) - sizeof(MAP_(t))) / sizeof(MAP_IDX_T) );
465 13874316 : }
466 :
467 : FD_FN_CONST static inline ulong
468 6003408 : MAP_(chain_cnt_est)( ulong ele_max_est ) {
469 :
470 : /* Clamp to be in [1,ele_max] (as ele_max_est 0 is degenerate and as
471 : the map is guaranteed to hold at most ele_max keys). */
472 :
473 6003408 : ele_max_est = fd_ulong_min( fd_ulong_max( ele_max_est, 1UL ), MAP_(ele_max)() );
474 :
475 : /* Compute the number of chains as the power of 2 that makes the
476 : average chain length between ~1 and ~2 when ele_max_est are stored
477 : in the map and then clamp to the chain max. */
478 :
479 6003408 : ulong chain_min = (ele_max_est>>1) + (ele_max_est&1UL); /* chain_min = ceil(ele_max_est/2), in [1,2^63], computed w/o overflow */
480 6003408 : ulong chain_cnt = fd_ulong_pow2_up( chain_min ); /* Power of 2 in [1,2^63] */
481 :
482 6003408 : return fd_ulong_min( chain_cnt, MAP_(chain_max)() );
483 6003408 : }
484 :
485 12 : FD_FN_PURE static inline ulong MAP_(chain_cnt)( MAP_(t) const * join ) { return MAP_(private_const)( join )->chain_cnt; }
486 6 : FD_FN_PURE static inline ulong MAP_(seed) ( MAP_(t) const * join ) { return MAP_(private_const)( join )->seed; }
487 :
488 : FD_FN_PURE static inline int
489 : MAP_(key_eq)( MAP_KEY_T const * k0,
490 5961061625 : MAP_KEY_T const * k1 ) {
491 5961061625 : return !!(MAP_KEY_EQ( (k0), (k1) ));
492 5961061625 : }
493 :
494 : FD_FN_PURE static inline ulong
495 : MAP_(key_hash)( MAP_KEY_T const * key,
496 6001038 : ulong seed ) {
497 6001038 : return (MAP_KEY_HASH( (key), (seed) ));
498 6001038 : }
499 :
500 : FD_FN_PURE static inline MAP_(iter_t)
501 : MAP_(iter_init)( MAP_(t) const * join,
502 3078999 : MAP_ELE_T const * pool ) {
503 3078999 : (void)pool;
504 :
505 3078999 : MAP_(private_t) const * map = MAP_(private_const)( join );
506 3078999 : MAP_IDX_T const * chain = MAP_(private_chain_const)( map );
507 :
508 : /* Find first element. If the map is empty, chain_rem will be 0 and
509 : ele_idx will be idx_null. */
510 :
511 3078999 : ulong chain_rem = map->chain_cnt; /* At least 1 */
512 3078999 : ulong ele_idx;
513 16155850 : do {
514 16155850 : ele_idx = MAP_(private_unbox)( chain[ chain_rem-1UL ] );
515 16155850 : if( !MAP_(private_idx_is_null)( ele_idx ) ) break;
516 16155850 : } while( --chain_rem );
517 :
518 3078999 : MAP_(iter_t) iter;
519 3078999 : iter.chain_rem = chain_rem;
520 3078999 : iter.ele_idx = ele_idx;
521 3078999 : return iter;
522 3078999 : }
523 :
524 : FD_FN_CONST static inline int
525 : MAP_(iter_done)( MAP_(iter_t) iter,
526 : MAP_(t) const * join,
527 791047644 : MAP_ELE_T const * pool ) {
528 791047644 : (void)join; (void)pool;
529 791047644 : return !iter.chain_rem;
530 791047644 : }
531 :
532 : FD_FN_PURE static inline MAP_(iter_t)
533 : MAP_(iter_next)( MAP_(iter_t) iter,
534 : MAP_(t) const * join,
535 787968645 : MAP_ELE_T const * pool ) {
536 : # if FD_TMPL_USE_HANDHOLDING
537 : if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
538 : # endif
539 787968645 : ulong chain_rem = iter.chain_rem;
540 787968645 : ulong ele_idx = iter.ele_idx;
541 :
542 : /* At this point, we are just finished iterating over element ele_idx
543 : on chain chain_rem-1 and we already iterated over all elements in
544 : chains (chain_rem,chain_cnt] and all elements in chain chain_rem-1
545 : before this element. As such, ele_idx is in [0,ele_cnt) and
546 : chain_rem is in (0,chain_cnt]. Get the next element in the chain
547 : chain_rem-1. */
548 :
549 787968645 : ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT );
550 787968645 : if( MAP_(private_idx_is_null)( ele_idx ) ) {
551 :
552 : /* There were no more elements in chain chain_rem-1. Find the next
553 : chain to start processing. If all unprocessed chains are empty,
554 : then we are done. */
555 :
556 380909938 : MAP_IDX_T const * chain = MAP_(private_chain_const)( MAP_(private_const)( join ) );
557 782028536 : while( --chain_rem ) {
558 778956206 : ele_idx = MAP_(private_unbox)( chain[ chain_rem-1UL ] );
559 778956206 : if( !MAP_(private_idx_is_null)( ele_idx ) ) break;
560 778956206 : }
561 :
562 380909938 : }
563 :
564 787968645 : iter.chain_rem = chain_rem;
565 787968645 : iter.ele_idx = ele_idx;
566 787968645 : return iter;
567 787968645 : }
568 :
569 : FD_FN_CONST static inline ulong
570 : MAP_(iter_idx)( MAP_(iter_t) iter,
571 : MAP_(t) const * join,
572 787968162 : MAP_ELE_T * pool ) {
573 : # if FD_TMPL_USE_HANDHOLDING
574 : if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
575 : # endif
576 787968162 : (void)join; (void)pool;
577 787968162 : return iter.ele_idx;
578 787968162 : }
579 :
580 : FD_FN_CONST static inline MAP_ELE_T *
581 : MAP_(iter_ele)( MAP_(iter_t) iter,
582 : MAP_(t) const * join,
583 787968012 : MAP_ELE_T * pool ) {
584 : # if FD_TMPL_USE_HANDHOLDING
585 : if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
586 : # endif
587 787968012 : (void)join;
588 787968012 : return pool + iter.ele_idx;
589 787968012 : }
590 :
591 : FD_FN_CONST static inline MAP_ELE_T const *
592 : MAP_(iter_ele_const) ( MAP_(iter_t) iter,
593 : MAP_(t) const * join,
594 787968048 : MAP_ELE_T const * pool ) {
595 : # if FD_TMPL_USE_HANDHOLDING
596 : if( FD_UNLIKELY( MAP_(iter_done)( iter, join, pool ) ) ) FD_LOG_CRIT(( "assumes not done" ));
597 : # endif
598 787968048 : (void)join;
599 787968048 : return pool + iter.ele_idx;
600 787968048 : }
601 :
602 : FD_PROTOTYPES_END
603 :
604 : #endif
605 :
606 : #if MAP_IMPL_STYLE==1 /* need prototypes */
607 :
608 : FD_PROTOTYPES_BEGIN
609 :
610 : FD_FN_CONST ulong MAP_(align) ( void );
611 : FD_FN_CONST ulong MAP_(footprint)( ulong chain_cnt );
612 : void * MAP_(new) ( void * shmem, ulong chain_cnt, ulong seed );
613 : MAP_(t) * MAP_(join) ( void * shmap );
614 : void * MAP_(leave) ( MAP_(t) * join );
615 : void * MAP_(delete) ( void * shmap );
616 :
617 : MAP_(t) *
618 : MAP_(idx_insert)( MAP_(t) * join,
619 : ulong ele_idx,
620 : MAP_ELE_T * pool );
621 :
622 : ulong
623 : MAP_(idx_remove)( MAP_(t) * join,
624 : MAP_KEY_T const * key,
625 : ulong sentinel,
626 : MAP_ELE_T * pool );
627 :
628 : FD_FN_PURE ulong
629 : MAP_(idx_query)( MAP_(t) * join,
630 : MAP_KEY_T const * key,
631 : ulong sentinel,
632 : MAP_ELE_T * pool );
633 :
634 : FD_FN_PURE ulong
635 : MAP_(idx_query_const)( MAP_(t) const * join,
636 : MAP_KEY_T const * key,
637 : ulong sentinel,
638 : MAP_ELE_T const * pool );
639 :
640 : #if MAP_MULTI!=0
641 :
642 : FD_FN_PURE ulong
643 : MAP_(idx_next_const)( ulong prev, // Previous result of mymap_idx_query_const
644 : ulong sentinel, // Value to return on failure
645 : MAP_ELE_T const * pool ); // Current local join to element storage
646 :
647 : #endif /* MAP_MULTI!=0 */
648 :
649 : int
650 : MAP_(verify)( MAP_(t) const * join,
651 : ulong ele_cnt,
652 : MAP_ELE_T const * pool );
653 :
654 : FD_PROTOTYPES_END
655 :
656 : #else /* need implementations */
657 :
658 : #if MAP_IMPL_STYLE==0 /* local only */
659 : #define MAP_IMPL_STATIC FD_FN_UNUSED static
660 : #else
661 : #define MAP_IMPL_STATIC
662 : #endif
663 :
664 12954 : FD_FN_CONST MAP_IMPL_STATIC ulong MAP_(align)( void ) { return alignof(MAP_(t)); }
665 :
666 : FD_FN_CONST MAP_IMPL_STATIC ulong
667 5364 : MAP_(footprint)( ulong chain_cnt ) {
668 5364 : if( !(fd_ulong_is_pow2( chain_cnt ) & (chain_cnt<=MAP_(chain_max)())) ) return 0UL;
669 5328 : return fd_ulong_align_up( sizeof(MAP_(t)) + chain_cnt*sizeof(MAP_IDX_T), alignof(MAP_(t)) ); /* no overflow */
670 5364 : }
671 :
672 : MAP_IMPL_STATIC void *
673 : MAP_(new)( void * shmap,
674 : ulong chain_cnt,
675 1401 : ulong seed ) {
676 :
677 1401 : if( FD_UNLIKELY( !shmap ) ) {
678 6 : FD_LOG_WARNING(( "NULL shmap" ));
679 6 : return NULL;
680 6 : }
681 :
682 1395 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmap, MAP_(align)() ) ) ) {
683 6 : FD_LOG_WARNING(( "misaligned shmap" ));
684 6 : return NULL;
685 6 : }
686 :
687 1389 : ulong footprint = MAP_(footprint)( chain_cnt );
688 1389 : if( FD_UNLIKELY( !footprint ) ) {
689 18 : FD_LOG_WARNING(( "bad footprint" ));
690 18 : return NULL;
691 18 : }
692 :
693 : /* seed is arbitrary */
694 :
695 : /* Init the metadata */
696 :
697 1371 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
698 :
699 1371 : map->seed = seed;
700 1371 : map->chain_cnt = chain_cnt;
701 :
702 : /* Set all the chains to NULL */
703 :
704 1371 : MAP_IDX_T * chain = MAP_(private_chain)( map );
705 25418502 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) chain[ chain_idx ] = MAP_(private_box)( MAP_(private_idx_null)() );
706 :
707 1371 : FD_COMPILER_MFENCE();
708 1371 : FD_VOLATILE( map->magic ) = MAP_MAGIC;
709 1371 : FD_COMPILER_MFENCE();
710 :
711 1371 : return shmap;
712 1389 : }
713 :
714 : MAP_IMPL_STATIC MAP_(t) *
715 2049 : MAP_(join)( void * shmap ) {
716 2049 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
717 :
718 2049 : if( FD_UNLIKELY( !map ) ) {
719 6 : FD_LOG_WARNING(( "NULL shmap" ));
720 6 : return NULL;
721 6 : }
722 :
723 2043 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) ) ) {
724 6 : FD_LOG_WARNING(( "misaligned shmap" ));
725 6 : return NULL;
726 6 : }
727 :
728 2037 : if( FD_UNLIKELY( map->magic!=MAP_MAGIC ) ) {
729 6 : FD_LOG_WARNING(( "bad magic" ));
730 6 : return NULL;
731 6 : }
732 :
733 2031 : return (MAP_(t) *)map;
734 2037 : }
735 :
736 : MAP_IMPL_STATIC void *
737 21 : MAP_(leave)( MAP_(t) * join ) {
738 :
739 21 : if( FD_UNLIKELY( !join ) ) {
740 6 : FD_LOG_WARNING(( "NULL join" ));
741 6 : return NULL;
742 6 : }
743 :
744 15 : return (void *)join;
745 21 : }
746 :
747 : MAP_IMPL_STATIC void *
748 24 : MAP_(delete)( void * shmap ) {
749 24 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
750 :
751 24 : if( FD_UNLIKELY( !map ) ) {
752 6 : FD_LOG_WARNING(( "NULL shmap" ));
753 6 : return NULL;
754 6 : }
755 :
756 18 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) ) ) {
757 6 : FD_LOG_WARNING(( "misaligned shmap" ));
758 6 : return NULL;
759 6 : }
760 :
761 12 : if( FD_UNLIKELY( map->magic!=MAP_MAGIC ) ) {
762 6 : FD_LOG_WARNING(( "bad magic" ));
763 6 : return NULL;
764 6 : }
765 :
766 6 : FD_COMPILER_MFENCE();
767 6 : FD_VOLATILE( map->magic ) = 0UL;
768 6 : FD_COMPILER_MFENCE();
769 :
770 6 : return shmap;
771 12 : }
772 :
773 : FD_FN_PURE MAP_IMPL_STATIC ulong
774 : MAP_(idx_query)( MAP_(t) * join,
775 : MAP_KEY_T const * key,
776 : ulong sentinel,
777 1212082794 : MAP_ELE_T * pool ) {
778 1212082794 : MAP_(private_t) * map = MAP_(private)( join );
779 :
780 : /* Find the key */
781 :
782 1212082794 : MAP_IDX_T * head = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
783 1212082794 : MAP_IDX_T * cur = head;
784 2127545196 : for(;;) {
785 2127545196 : ulong ele_idx = MAP_(private_unbox)( *cur );
786 2127545196 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
787 1330208079 : if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) { /* optimize for found */
788 : /* Found, move it to the front of the chain */
789 414745677 : if( FD_UNLIKELY( cur!=head ) ) { /* Assume already at head from previous query */
790 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
791 213354 : 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;
792 213354 : pool[ ele_idx ].MAP_PREV = MAP_(private_box)( MAP_(private_idx_null)() );
793 213354 : pool[ *head ].MAP_PREV = MAP_(private_box)( ele_idx );
794 : #endif
795 289520109 : *cur = pool[ ele_idx ].MAP_NEXT;
796 289520109 : pool[ ele_idx ].MAP_NEXT = *head;
797 289520109 : *head = MAP_(private_box)( ele_idx );
798 289520109 : }
799 414745677 : return ele_idx;
800 414745677 : }
801 915462402 : cur = &pool[ ele_idx ].MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
802 915462402 : }
803 :
804 : /* Not found */
805 :
806 797337117 : return sentinel;
807 1212082794 : }
808 :
809 : MAP_IMPL_STATIC MAP_(t) *
810 : MAP_(idx_insert)( MAP_(t) * join,
811 : ulong ele_idx,
812 21197592 : MAP_ELE_T * pool ) {
813 : # if FD_TMPL_USE_HANDHOLDING && !MAP_MULTI
814 : if( FD_UNLIKELY( !MAP_(private_idx_is_null)( MAP_(idx_query)( join, &pool[ ele_idx ].MAP_KEY, MAP_(private_idx_null)(), pool ) ) ) ) {
815 : FD_LOG_CRIT(( "ele_idx already in map" ));
816 : }
817 : # endif
818 21197592 : MAP_(private_t) * map = MAP_(private)( join );
819 :
820 21197592 : MAP_IDX_T * head = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( &pool[ ele_idx ].MAP_KEY, map->seed, map->chain_cnt );
821 :
822 : # if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
823 18038922 : if( FD_UNLIKELY( !MAP_(private_idx_is_null)( *head ) ) ) pool[ *head ].MAP_PREV = MAP_(private_box)( ele_idx );
824 18038922 : pool[ ele_idx ].MAP_PREV = MAP_(private_box)( MAP_(private_idx_null)() );
825 : # endif
826 21197592 : pool[ ele_idx ].MAP_NEXT = *head;
827 : # if MAP_INSERT_FENCE
828 51 : FD_COMPILER_MFENCE();
829 : # endif
830 21197592 : *head = MAP_(private_box)( ele_idx );
831 :
832 21197592 : return join;
833 21197592 : }
834 :
835 : MAP_IMPL_STATIC ulong
836 : MAP_(idx_remove)( MAP_(t) * join,
837 : MAP_KEY_T const * key,
838 : ulong sentinel,
839 7774938 : MAP_ELE_T * pool ) {
840 7774938 : MAP_(private_t) * map = MAP_(private)( join );
841 :
842 : /* Find the key */
843 :
844 7774938 : MAP_IDX_T * cur = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
845 11902695 : for(;;) {
846 11902695 : ulong ele_idx = MAP_(private_unbox)( *cur );
847 11902695 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found (it is remove after all) */
848 7284252 : if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) { /* " */
849 3156495 : *cur = pool[ ele_idx ].MAP_NEXT;
850 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
851 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;
852 : #endif
853 3156495 : return ele_idx;
854 3156495 : }
855 4127757 : cur = &pool[ ele_idx ].MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
856 4127757 : }
857 :
858 : /* Not found */
859 :
860 4618443 : return sentinel;
861 7774938 : }
862 :
863 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
864 : MAP_IMPL_STATIC void
865 : MAP_(idx_remove_fast)( MAP_(t) * join,
866 : ulong ele_idx,
867 18015850 : MAP_ELE_T * pool ) {
868 18015850 : MAP_(private_t) * map = MAP_(private)( join );
869 :
870 18015850 : MAP_ELE_T * ele = pool+ele_idx;
871 :
872 18015850 : if( FD_UNLIKELY( !MAP_(private_idx_is_null)( ele->MAP_NEXT ) ) ) pool[ ele->MAP_NEXT ].MAP_PREV = ele->MAP_PREV;
873 :
874 18015850 : if( FD_UNLIKELY( !MAP_(private_idx_is_null)( ele->MAP_PREV ) ) ) pool[ ele->MAP_PREV ].MAP_NEXT = ele->MAP_NEXT;
875 17311433 : else { MAP_(private_chain)( map )[ MAP_(private_chain_idx)( &ele->MAP_KEY, map->seed, map->chain_cnt ) ] = ele->MAP_NEXT; }
876 18015850 : }
877 : #endif
878 :
879 : FD_FN_PURE MAP_IMPL_STATIC ulong
880 : MAP_(idx_query_const)( MAP_(t) const * join,
881 : MAP_KEY_T const * key,
882 : ulong sentinel,
883 2450574342 : MAP_ELE_T const * pool ) {
884 2450574342 : MAP_(private_t) const * map = MAP_(private_const)( join );
885 :
886 : /* Find the key */
887 :
888 2450574342 : MAP_IDX_T const * cur = MAP_(private_chain_const)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
889 3672865982 : for(;;) {
890 3672865982 : ulong ele_idx = MAP_(private_unbox)( *cur );
891 3672865982 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
892 3671320631 : if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) return ele_idx; /* optimize for found */
893 1222291640 : cur = &pool[ ele_idx ].MAP_NEXT;
894 1222291640 : }
895 :
896 : /* Not found */
897 :
898 1545351 : return sentinel;
899 2450574342 : }
900 :
901 : #if MAP_MULTI!=0
902 :
903 : FD_FN_PURE MAP_IMPL_STATIC ulong
904 : MAP_(idx_next_const)( ulong prev, // Previous result of mymap_idx_query_const
905 : ulong sentinel, // Value to return on failure
906 688807017 : MAP_ELE_T const * pool ) { // Current local join to element storage
907 : /* Go to next element in chain */
908 :
909 688807017 : MAP_ELE_T const * prev_ele = &pool[ prev ];
910 688807017 : MAP_IDX_T const * cur = &prev_ele->MAP_NEXT;
911 928248813 : for(;;) {
912 928248813 : ulong ele_idx = MAP_(private_unbox)( *cur );
913 928248813 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
914 928248660 : if( FD_LIKELY( MAP_(key_eq)( &prev_ele->MAP_KEY, &pool[ ele_idx ].MAP_KEY ) ) ) return ele_idx; /* optimize for found */
915 239441796 : cur = &pool[ ele_idx ].MAP_NEXT;
916 239441796 : }
917 :
918 : /* Not found */
919 :
920 153 : return sentinel;
921 688807017 : }
922 :
923 : #endif /* MAP_MULTI!=0 */
924 :
925 : MAP_IMPL_STATIC int
926 : MAP_(verify)( MAP_(t) const * join,
927 : ulong ele_cnt,
928 7865556 : MAP_ELE_T const * pool ) {
929 :
930 6948746928 : # define MAP_TEST(c) do { \
931 6948746928 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
932 6948746928 : } while(0)
933 :
934 : /* Validate input arguments */
935 :
936 7865556 : MAP_TEST( join );
937 7865550 : MAP_TEST( ele_cnt<=MAP_(ele_max)() );
938 7865544 : MAP_TEST( (!!pool) | (!ele_cnt) );
939 :
940 : /* Validate metadata */
941 :
942 7865538 : MAP_(private_t) const * map = MAP_(private_const)( join );
943 :
944 7865538 : MAP_TEST( map->magic==MAP_MAGIC );
945 :
946 7865538 : ulong seed = map->seed;
947 : /* seed is arbitrary */
948 :
949 7865538 : ulong chain_cnt = map->chain_cnt;
950 7865538 : MAP_TEST( fd_ulong_is_pow2( chain_cnt ) );
951 7865538 : MAP_TEST( chain_cnt<=MAP_(chain_max)() );
952 :
953 : /* Visit each map entry, doing simple chain integrity checks */
954 :
955 7865538 : MAP_IDX_T const * chain = MAP_(private_chain_const)( map );
956 :
957 7865538 : ulong rem = ele_cnt; /* We can visit at most ele_cnt elements */
958 6289750170 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
959 6281884632 : ulong prev_ele = MAP_(private_idx_null)();
960 6281884632 : (void)prev_ele;
961 6281884632 : for( ulong ele_idx = MAP_(private_unbox)( chain[ chain_idx ] );
962 7942943649 : !MAP_(private_idx_is_null)( ele_idx );
963 6281884632 : ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT ) ) {
964 1661059017 : MAP_TEST( rem ); rem--; /* Check for cycles */
965 1661059017 : MAP_TEST( ele_idx<ele_cnt ); /* Check valid element index */
966 1661059017 : MAP_TEST( MAP_(private_chain_idx)( &pool[ ele_idx ].MAP_KEY, seed, chain_cnt )==chain_idx ); /* Check in correct chain */
967 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
968 257317596 : MAP_TEST( pool[ ele_idx ].MAP_PREV==prev_ele );
969 257317596 : prev_ele = ele_idx;
970 257317596 : #endif
971 257317596 : }
972 6281884632 : }
973 :
974 : /* At this point, we know that there are no cycles in the map chains,
975 : all indices are inbounds and elements are in the correct chains for
976 : probes. It is possible for there to be keys that have been
977 : inserted more than once though. We visit all the nodes a second
978 : time and make sure each probe resolves to itself to prove the key
979 : of every element in the map is unique. (We could do this faster if
980 : we could tag the elements but this verify is written to not modify
981 : any memory.) */
982 :
983 6289750170 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ )
984 6281884632 : for( ulong ele_idx = MAP_(private_unbox)( chain[ chain_idx ] );
985 7942943649 : !MAP_(private_idx_is_null)( ele_idx );
986 6281884632 : ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT ) ) {
987 : #if MAP_MULTI==0
988 1044314310 : MAP_TEST( MAP_(idx_query_const)( join, &pool[ ele_idx ].MAP_KEY, ULONG_MAX, pool )==ele_idx );
989 : #else
990 : ulong idx2;
991 616744707 : for (idx2 = MAP_(idx_query_const)( join, &pool[ ele_idx ].MAP_KEY, ULONG_MAX, pool );
992 1046107332 : idx2 != ULONG_MAX && idx2 != ele_idx;
993 429362625 : idx2 = MAP_(idx_next_const)( idx2, ULONG_MAX, pool )) ;
994 616744707 : MAP_TEST( idx2 == ele_idx );
995 : #endif
996 1661059017 : }
997 :
998 7865538 : # undef MAP_TEST
999 :
1000 7865538 : return 0;
1001 7865538 : }
1002 :
1003 : #undef MAP_IMPL_STATIC
1004 :
1005 : #endif
1006 :
1007 : #if MAP_IMPL_STYLE==0 || MAP_IMPL_STYLE==1 /* need inlines */
1008 :
1009 : FD_PROTOTYPES_BEGIN
1010 :
1011 : static inline MAP_(t) *
1012 : MAP_(ele_insert)( MAP_(t) * join,
1013 : MAP_ELE_T * ele,
1014 16744404 : MAP_ELE_T * pool ) {
1015 16744404 : return MAP_(idx_insert)( join, (ulong)(ele-pool), pool );
1016 16744404 : }
1017 :
1018 : static inline MAP_ELE_T *
1019 : MAP_(ele_remove)( MAP_(t) * join,
1020 : MAP_KEY_T const * key,
1021 : MAP_ELE_T * sentinel,
1022 7680333 : MAP_ELE_T * pool ) {
1023 7680333 : ulong ele_idx = MAP_(idx_remove)( join, key, MAP_(private_idx_null)(), pool );
1024 7680333 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
1025 7680333 : }
1026 :
1027 : #if MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
1028 : static inline MAP_ELE_T *
1029 : MAP_(ele_remove_fast)( MAP_(t) * join,
1030 : MAP_ELE_T * ele,
1031 13583191 : MAP_ELE_T * pool ) {
1032 13583191 : MAP_(idx_remove_fast)( join, (ulong)(ele-pool), pool );
1033 13583191 : return ele;
1034 13583191 : }
1035 : #endif
1036 :
1037 : FD_FN_PURE static inline MAP_ELE_T *
1038 : MAP_(ele_query)( MAP_(t) * join,
1039 : MAP_KEY_T const * key,
1040 : MAP_ELE_T * sentinel,
1041 1203163068 : MAP_ELE_T * pool ) {
1042 1203163068 : ulong ele_idx = MAP_(idx_query)( join, key, MAP_(private_idx_null)(), pool );
1043 1203163068 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
1044 1203163068 : }
1045 :
1046 : FD_FN_PURE static inline MAP_ELE_T const *
1047 : MAP_(ele_query_const)( MAP_(t) const * join,
1048 : MAP_KEY_T const * key,
1049 : MAP_ELE_T const * sentinel,
1050 789505284 : MAP_ELE_T const * pool ) {
1051 789505284 : ulong ele_idx = MAP_(idx_query_const)( join, key, MAP_(private_idx_null)(), pool );
1052 789505284 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T const *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
1053 789505284 : }
1054 :
1055 : #if MAP_MULTI!=0
1056 :
1057 : FD_FN_PURE static inline MAP_ELE_T const * // Found element on success (will be from pool), sentinel on failure
1058 : MAP_(ele_next_const)( MAP_ELE_T const * prev, // Previous result of mymap_ele_query_const
1059 : MAP_ELE_T const * sentinel, // Value to return if key not in map
1060 259444236 : MAP_ELE_T const * pool ) { // Current local join to element storage
1061 259444236 : ulong ele_idx = MAP_(idx_next_const)( (ulong)(prev-pool), MAP_(private_idx_null)(), pool );
1062 259444236 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), pool + ele_idx, sentinel );
1063 259444236 : }
1064 :
1065 : #endif /* MAP_MULTI!=0 */
1066 :
1067 : FD_PROTOTYPES_END
1068 :
1069 : #endif
1070 :
1071 : #undef MAP_
1072 :
1073 : #undef MAP_IMPL_STYLE
1074 : #undef MAP_MAGIC
1075 : #undef MAP_KEY_HASH
1076 : #undef MAP_KEY_EQ
1077 : #undef MAP_NEXT
1078 : #undef MAP_PREV
1079 : #undef MAP_IDX_T
1080 : #undef MAP_KEY
1081 : #undef MAP_KEY_T
1082 : #undef MAP_ELE_T
1083 : #undef MAP_NAME
1084 : #undef MAP_MULTI
1085 : #undef MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL
1086 : #undef MAP_INSERT_FENCE
|
