Line data Source code
1 : /* Generate prototypes, inlines and/or implementations for ultra high
2 : performance dynamic key-val maps of gigantic size. A giant map can
3 : be persisting beyond the lifetime of creating process, used
4 : concurrently, used IPC, relocated in memory, naively
5 : serialized/deserialized and/or moved between hosts. Memory
6 : efficiency and flexible footprint are prioritized. Elements that are
7 : recently used can be optionally moved to the front of the chains to
8 : adaptively optimize the maps for recent queries. Typical usage:
9 :
10 : struct mymap {
11 : ulong key; // Technically "MAP_KEY_T MAP_KEY;" (default is ulong key), should not be touched by user
12 : ulong next; // Technically "ulong MAP_NEXT;", should not be touched by user
13 : ... key and next can be located arbitrarily in struct
14 : ... the mapping of a key to an array index is arbitrary but is
15 : ... fixed over the lifetime of the key in the map
16 : };
17 :
18 : typedef struct mymap mymap_t;
19 :
20 : #define MAP_NAME mymap
21 : #define MAP_T mymap_t
22 : #include "tmpl/fd_map_giant.c"
23 :
24 : will declare the following APIs as a header only style library in the
25 : compilation unit:
26 :
27 : // mymap_{align,footprint} returns alignment and footprint needed
28 : // for a memory region to be used as a mymap. align will be an
29 : // integer power-of-two and footprint will be a multiple of align.
30 : // footprint will return 0 if key_max requires a footprint that
31 : // would overflow 64-bit. key_max is the maximum number of keys
32 : // (elements) the map can hold.
33 : //
34 : // mymap_new formats a memory region with the appropriate alignment
35 : // and footprint whose first byte in the caller's address space is
36 : // pointed by shmem. Returns shmem on success and NULL on failure
37 : // (logs details). Caller is not joined on return. The map will be
38 : // empty.
39 : //
40 : // mymap_join joins a mymap. Assumes shmap points at a memory
41 : // region formatted as a mymap in the caller's address space.
42 : // Returns a handle to the caller's local join on success and NULL
43 : // on failure (logs details). THIS IS NOT A SIMPLE CAST OF SHMAP!
44 : // The join can be indexed as a flat array with key_max elements in
45 : // the caller's address space.
46 : //
47 : // mymap_leave leaves a mymap. Assumes join points to a current
48 : // local join. Returns shmap used on join. THIS IS NOT A SIMPLE
49 : // CASE OF JOIN!
50 : //
51 : // mymap_delete unformats a memory region used as a mymap. Assumes
52 : // shmap points to a memory region in the caller's local address
53 : // space formatted as a mymap, that there are no joins to the mymap
54 : // and that any application cleanup of the entries has already been
55 : // done. Returns shmap on success and NULL on failure.
56 :
57 : ulong mymap_align ( void );
58 : ulong mymap_footprint( ulong key_max );
59 : void * mymap_new ( void * shmem, ulong key_max, ulong seed );
60 : mymap_t * mymap_join ( void * shmap ); // Indexed [0,key_max)
61 : void * mymap_leave ( mymap_t * join );
62 : void * mymap_delete ( void * shmap );
63 :
64 : // mymap_key_max and mymap_seed return the values used to construct
65 : // the map. They assume join is a current local join. The values
66 : // will be constant for the map lifetime.
67 :
68 : ulong mymap_key_max( mymap_t const * join );
69 : ulong mymap_seed ( mymap_t const * join );
70 :
71 : // mymap_key_cnt returns the current number of keys in the map.
72 : // Will be in [0,key_max]. mymap_is_full returns 1 if
73 : // key_cnt==key_max. Assumes join is a current local join. The
74 : // values will be constant until the next map insert / remove.
75 :
76 : ulong mymap_key_cnt( mymap_t const * join );
77 : int mymap_is_full( mymap_t const * join );
78 :
79 : // mymap_key_{eq,hash,copy} expose the provided
80 : // MAP_KEY_{EQ,HASH,COPY} macros as inline functions with strict
81 : // semantics. They assume that the provided pointers are in the
82 : // caller's address space to keys that will not be changed
83 : // concurrently. They retain no interest in key on return.
84 : //
85 : // mymap_key_eq returns 1 if the *k0 and *k1 are equal and 0
86 : // otherwise.
87 : //
88 : // mymap_key_hash returns the hash *key using the hash function
89 : // seed. Should ideally be a random mapping from MAP_KEY_T -> ulong
90 : // but this depends on what the user actually passed in for
91 : // MAP_HASH. The seed used by a particular instance of a giant map
92 : // can be obtained above.
93 : //
94 : // mymap_key_copy deep copies *ks into *kd and returns kd.
95 :
96 : int mymap_key_eq ( ulong * k0, ulong * k1 );
97 : ulong mymap_key_hash( ulong * key, ulong seed );
98 : ulong * mymap_key_copy( ulong * kd, ulong const * ks );
99 :
100 : // mymap_insert inserts the key pointed to by key into the map.
101 : // Returns the location in the caller's address space of the element
102 : // for key in the map.
103 : //
104 : // Assumes map is a current local join, key points to a valid key in
105 : // the caller's address space, there are no concurrent operations on
106 : // the map or key. The map retains no interest in key. The
107 : // returned element will be valid for the lesser of the lifetime of
108 : // the join and until key is removed from the map.
109 : //
110 : // Critically, as this is used in high performance contexts where
111 : // the application already knows this, THE CALLER PROMISES THE KEY
112 : // IS NOT IN THE MAP AND THAT THE MAP HAS SPACE FOR KEY.
113 : //
114 : // This always succeeds (with the above requirements) and returns
115 : // non NULL.
116 :
117 : mymap_t * mymap_insert( mymap_t * join, ulong const * key );
118 :
119 : // mymap_remove removes the key pointed to by key from the map. A
120 : // pointer in the caller's address space to the former element is
121 : // returned to allow additional cleanup of the application fields.
122 : // Returns NULL if key is not in the map.
123 : //
124 : // Assumes map is a current local join, key points to a valid key in
125 : // the caller's address space and there are no concurrent operations
126 : // on the map or key. The map retains no interest in key. Any
127 : // returned pointer will be valid for the lesser of the lifetime of
128 : // the join and until the next insert.
129 :
130 : mymap_t * mymap_remove( mymap_t * join, ulong const * key );
131 :
132 : // mymap_query finds the element for the key pointed to by key in
133 : // the map and returns a pointer to it in the caller's address
134 : // space. If key is not found, returns sentinel (usually pass
135 : // NULL).
136 : //
137 : // Assumes map is a current local join, key points to a valid key in
138 : // the caller's address space and there are no concurrent operations
139 : // on the map or key. The map retains no interest in key. On
140 : // success, the returned pointer will be valid for the lesser of the
141 : // lifetime of join or until key is removed. On failure, the
142 : // returned pointer lifetime will be that of the sentinel.
143 :
144 : mymap_t * mymap_query( mymap_t * join, ulong const * key, mymap_t * sentinel );
145 :
146 : // mymap_query_const is the same as mymap_query but supports
147 : // concurrent queries so long as there no concurrently running
148 : // insert/remove/query operations. The value fields of the mymap_t
149 : // returned by this function can be changed by the application (but
150 : // it is up to the application to manage concurrency between
151 : // different users modifying the same key).
152 :
153 : mymap_t const * mymap_query_const( mymap_t const * join, ulong const * key, mymap_t const * sentinel );
154 :
155 : // mymap_query_safe is the same as mymap_query_const but with
156 : // additional safety checks. If a concurrent write is occurring,
157 : // this API will still return a reasonable map entry without
158 : // crashing, even if it is wrong.
159 :
160 : mymap_t const * mymap_query_safe( mymap_t const * join, ulong const * key, mymap_t const * sentinel );
161 :
162 : // mymap_iter_* allow for iteration over all the keys inserted into
163 : // a mymap. The iteration will be in a random order but the order
164 : // will be identical if repeated with no insert/remove/query
165 : // operations done in between. Assumes no concurrent
166 : // insert/remove/query operations. Example usage:
167 : //
168 : // for( mymap_t iter = mymap_iter_init( join ); !mymap_iter_done( join, iter ); iter = mymap_iter_next( join, iter ) ) {
169 : // mymap_t * ele = mymap_iter_ele( join, iter );
170 : //
171 : // ... process ele here
172 : //
173 : // ... IMPORTANT! It is _okay_ to insert, remove, query or
174 : // ... query_const here. In particular, if an element is
175 : // ... inserted, it may or may not be covered by this iteration.
176 : // ... If an element is removed that has not already been
177 : // ... iterated over, it will not be iterated over in this
178 : // ... iteration. It is fine to remove the current item being
179 : // ... iterated over.
180 : //
181 : // ... WARNING! While this looks like an O(key_cnt) operation,
182 : // ... technically, this is an O(key_max) operation under the
183 : // ... hood. As such, use outside critical paths (e.g.
184 : // ... checkpointing), on dense maps (e.g. key_cnt/key_max ~
185 : // ... O(1)) and/or on maps where key_max is small enough not to
186 : // ... matter practically.
187 : // }
188 :
189 : struct mymap_iter_private { ... internal use only ... };
190 : typedef struct mymap_iter_private mymap_iter_t;
191 :
192 : mymap_iter_t mymap_iter_init ( mymap_t const * join, mymap_iter_t iter ); // returns iter, NULL join fine
193 : int mymap_iter_done ( mymap_t const * join, mymap_iter_t iter ); // returns 1 if no more iterations, 0 o.w.
194 : mymap_iter_t mymap_iter_next ( mymap_t const * join, mymap_iter_t iter ); // returns next iter value iter
195 : mymap_t * mymap_iter_ele ( mymap_t * join, mymap_iter_t iter ); // assumes not done, return non-NULL ele
196 : mymap_t const * mymap_iter_ele_const( mymap_t const * join, mymap_iter_t iter ); // assumes not done, return non-NULL ele
197 :
198 : // mymap_verify returns 0 if the mymap is not obviously corrupt or a
199 : // -1 (i.e. ERR_INVAL) if it is obviously corrupt (logs details).
200 : // join is the handle of a current local join to mymap.
201 :
202 : int mymap_verify( mymap_t const * join );
203 :
204 : You can do this as often as you like in a compilation unit to get
205 : different types of gigantic maps. Variants exist for making header
206 : prototypes only and/or implementations if doing a library with
207 : multiple compilation units. Further, options exist to use different
208 : hashing functions, comparison functions, etc as detailed below. */
209 :
210 : /* MAP_NAME gives the API prefix to use for map */
211 :
212 : #ifndef MAP_NAME
213 : #error "Define MAP_NAME"
214 : #endif
215 :
216 : /* MAP_T is the map element type. */
217 :
218 : #ifndef MAP_T
219 : #error "Define MAP_T"
220 : #endif
221 :
222 : /* MAP_KEY_T is the map key type */
223 :
224 : #ifndef MAP_KEY_T
225 : #define MAP_KEY_T ulong
226 : #endif
227 :
228 : /* MAP_KEY is the MAP_T key field */
229 :
230 : #ifndef MAP_KEY
231 : #define MAP_KEY key
232 : #endif
233 :
234 : /* MAP_NEXT is the MAP_T next field */
235 :
236 : #ifndef MAP_NEXT
237 : #define MAP_NEXT next
238 : #endif
239 :
240 : /* MAP_KEY_EQ returns 0/1 if *k0 is the same/different as *k1 */
241 :
242 : #ifndef MAP_KEY_EQ
243 4148822646 : #define MAP_KEY_EQ(k0,k1) ((*(k0))==(*(k1)))
244 : #endif
245 :
246 : /* MAP_KEY_HASH maps *key into ulong uniform pseudo randomly. */
247 :
248 : #ifndef MAP_KEY_HASH
249 5003218794 : #define MAP_KEY_HASH(key,seed) fd_ulong_hash( (*(key)) ^ (seed) )
250 : #endif
251 :
252 : /* MAP_KEY_COPY copies the contents from *ks to *kd. Non-POD key types
253 : might need to customize this accordingly. Defaults to the copy
254 : operator. */
255 :
256 : #ifndef MAP_KEY_COPY
257 9072000 : #define MAP_KEY_COPY(kd,ks) (*(kd))=(*(ks))
258 : #endif
259 :
260 : /* MAP_MAGIC is the magic number to use for the structure to aid in
261 : persistent and or IPC usage. */
262 :
263 : #ifndef MAP_MAGIC
264 6 : #define MAP_MAGIC (0xf17eda2c3763a900UL) /* firedancer gmap version 0 */
265 : #endif
266 :
267 : /* 0 - local use only
268 : 1 - library header declaration
269 : 2 - library implementation */
270 :
271 : #ifndef MAP_IMPL_STYLE
272 : #define MAP_IMPL_STYLE 0
273 : #endif
274 :
275 : /* If MAP_MEMOIZE is defined to non-zero, the MAP_T requires a
276 : "hash" field that will hold the value of the MAP_KEY_HASH of the
277 : MAP_T's MAP_KEY when the map slot is not empty (undefined otherwise).
278 : This is useful for accelerating user operations that might need a
279 : hash of the key and for accelerating remove operations. It is also
280 : potentially useful as a way to accelerate slow key comparison
281 : operations (see MAP_KEY_EQUAL_IS_SLOW). */
282 :
283 : #ifndef MAP_MEMOIZE
284 : #define MAP_MEMOIZE 0
285 : #endif
286 :
287 : /* If MAP_MEMOIZE is non-zero, MAP_HASH is the element member to store the hash in. */
288 :
289 : #ifndef MAP_HASH
290 : #define MAP_HASH map_hash
291 : #endif
292 :
293 : /* Implementation *****************************************************/
294 :
295 : /* Constructors and verification logs detail on failure (rest only needs
296 : fd_bits.h, consider making logging a compile time option). */
297 :
298 : #include "../log/fd_log.h"
299 :
300 22307243796 : #define MAP_IDX_NULL (~(1UL<<63)) /* 2^63-1 */
301 29949810018 : #define MAP_(n) FD_EXPAND_THEN_CONCAT3(MAP_NAME,_,n)
302 :
303 : #if MAP_IMPL_STYLE==0 || MAP_IMPL_STYLE==1 /* need structures and inlines */
304 :
305 : struct MAP_(private) {
306 :
307 : /* This point is max(128,alignof(MAP_T)) aligned */
308 :
309 : /* 2 ulong here, index 0 is MAP_MAGIC, index 1 is offset from shmem
310 : region to key_max map array below. */
311 :
312 : /* alignment padding here */
313 :
314 : /* list_cnt ulong here, indexed [0,list_cnt)
315 : list[ list_idx ], idx is in [0,key_max) or MAP_IDX_NULL, tag is used */
316 :
317 : ulong key_max; /* yields non-zero footprint, <2^63 */
318 : ulong seed; /* hash seed, arbitrary */
319 : ulong list_cnt; /* == MAP_(private_list_cnt)( key_max ) */
320 : ulong key_cnt; /* in [0,key_max] */
321 : ulong free_stack; /* idx is in [0,key_max) or MAP_IDX_NULL, tag is free */
322 :
323 : /* Elements on the free_stack will have bit 63 of their next field set
324 : to facilitate iteration and validation. Elements in lists will
325 : have their bit 63 of their next field clear. key_max<2^63 ensures
326 : no confusion possible with MAP_IDX_NULL though this is more
327 : theoretical as ~2^63 keys is impractical physically. */
328 :
329 : /* This point is max(128,alignof(MAP_T)) aligned */
330 :
331 : /* key_max MAP_T here, hdr[1] above points here */
332 :
333 : };
334 :
335 : typedef struct MAP_(private) MAP_(private_t);
336 :
337 : typedef ulong MAP_(iter_t);
338 :
339 : FD_PROTOTYPES_BEGIN
340 :
341 : /* map_private_list_cnt returns the number of lists a map with the given
342 : key_max should use. */
343 :
344 : FD_FN_CONST static inline ulong
345 12288030 : MAP_(private_list_cnt)( ulong key_max ) {
346 : /* Compute the number of lists as the power of 2 that makes the
347 : average chain length between ~1 and ~2 */
348 12288030 : ulong list_min = (key_max>>1) + (key_max&1UL); /* list_min = ceil(key_max/2), at most 2^63, computed without overflow */
349 12288030 : ulong list_cnt = fd_ulong_pow2_up( list_min ); /* at most 2^63 */
350 12288030 : return list_cnt;
351 12288030 : }
352 :
353 : FD_FN_CONST static inline ulong
354 6144030 : MAP_(private_meta_footprint)( ulong list_cnt ) {
355 6144030 : return fd_ulong_align_up( (2UL + list_cnt)*sizeof(ulong) + sizeof(MAP_(private_t)), fd_ulong_max( 128UL, alignof(MAP_T) ) );
356 6144030 : }
357 :
358 : /* map_private returns the location of the map private for a current
359 : local join. Assumes join is a current local join. map_private_const
360 : is a const correct version. */
361 :
362 : FD_FN_CONST static inline MAP_(private_t) *
363 1585152012 : MAP_(private)( MAP_T * join ) {
364 1585152012 : return (MAP_(private_t) *)(((ulong)join) - sizeof(MAP_(private_t)));
365 1585152012 : }
366 :
367 : FD_FN_CONST static inline MAP_(private_t) const *
368 1863790818 : MAP_(private_const)( MAP_T const * join ) {
369 1863790818 : return (MAP_(private_t) const *)(((ulong)join) - sizeof(MAP_(private_t)));
370 1863790818 : }
371 :
372 : /* map_private_{list,ele}[_const] returns the location in the caller's
373 : address space of the map lists and elements. The _const variants are
374 : for const correctness. Assumes map is valid. */
375 :
376 : FD_FN_PURE static inline ulong *
377 1585152006 : MAP_(private_list)( MAP_(private_t) * map ) {
378 1585152006 : return ((ulong *)map) - map->list_cnt;
379 1585152006 : }
380 :
381 : FD_FN_PURE static inline ulong const *
382 1845346800 : MAP_(private_list_const)( MAP_(private_t) const * map ) {
383 1845346800 : return ((ulong const *)map) - map->list_cnt;
384 1845346800 : }
385 :
386 : /* map_private_list_idx returns the index of the list (in [0,list_cnt)
387 : that will contain the element corresponding to key (if present at
388 : all) for a map with list_cnt elements and seed. Assumes list_cnt is
389 : an integer power-of 2. Assumes key points to a key is in the
390 : caller's address space that will not be changed concurrently.
391 : Retains no interest in key on return. */
392 :
393 : FD_FN_PURE static inline ulong
394 : MAP_(private_list_idx)( MAP_KEY_T const * key,
395 : ulong seed,
396 1572864000 : ulong list_cnt ) {
397 1572864000 : return (MAP_KEY_HASH( (key), (seed) )) & (list_cnt-1UL);
398 1572864000 : }
399 :
400 : /* map_private_box_next boxes idx and tag into a map next field value.
401 : Assumes idx is in [0,2^63-1==MAP_IDX_NULL] and tag is in [0,1].
402 :
403 : map_private_unbox_idx unboxes the idx from a map next field value.
404 : Return will be in [0,2^63-1==MAP_IDX_NULL].
405 :
406 : map_private_unbox_tag unboxes the tag from a map next field value.
407 : Return will be in [0,1] */
408 :
409 575825754 : FD_FN_CONST static inline ulong MAP_(private_box_next) ( ulong idx, int tag ) { return idx | (((ulong)tag)<<63); }
410 11153621112 : FD_FN_CONST static inline ulong MAP_(private_unbox_idx) ( ulong next ) { return next & MAP_IDX_NULL; }
411 7873540614 : FD_FN_CONST static inline int MAP_(private_unbox_tag) ( ulong next ) { return (int)(next>>63); }
412 :
413 : /* map_private_is_null returns 1 if idx is the NULL map idx value
414 : and 0 otherwise. */
415 :
416 11147477112 : FD_FN_CONST static inline int MAP_(private_is_null)( ulong idx ) { return idx==MAP_IDX_NULL; }
417 :
418 : FD_FN_PURE static inline ulong
419 6 : MAP_(key_max)( MAP_T const * join ) {
420 6 : if( FD_UNLIKELY( !join ) ) return 0UL;
421 6 : return MAP_(private_const)( join )->key_max;
422 6 : }
423 :
424 : FD_FN_PURE static inline ulong
425 6 : MAP_(seed)( MAP_T const * join ) {
426 6 : if( FD_UNLIKELY( !join ) ) return 0UL;
427 6 : return MAP_(private_const)( join )->seed;
428 6 : }
429 :
430 : FD_FN_PURE static inline ulong
431 9216006 : MAP_(key_cnt)( MAP_T const * join ) {
432 9216006 : if( FD_UNLIKELY( !join ) ) return 0UL;
433 9216006 : return MAP_(private_const)( join )->key_cnt;
434 9216006 : }
435 :
436 : FD_FN_PURE static inline int
437 6150000 : MAP_(is_full)( MAP_T const * join ) {
438 6150000 : if( FD_UNLIKELY( !join ) ) return 0UL;
439 6150000 : MAP_(private_t) const * map = MAP_(private_const)( join );
440 6150000 : return MAP_(private_is_null)( MAP_(private_unbox_idx)( map->free_stack ) );
441 6150000 : }
442 :
443 : FD_FN_PURE static inline int
444 : MAP_(key_eq)( MAP_KEY_T const * k0,
445 4148822646 : MAP_KEY_T const * k1 ) {
446 4148822646 : return !!(MAP_KEY_EQ( (k0), (k1) ));
447 4148822646 : }
448 :
449 : FD_FN_PURE static inline ulong
450 : MAP_(key_hash)( MAP_KEY_T const * key,
451 6000000 : ulong seed ) {
452 6000000 : return (MAP_KEY_HASH( (key), (seed) ));
453 6000000 : }
454 :
455 : static inline MAP_KEY_T *
456 : MAP_(key_copy)( MAP_KEY_T * kd,
457 9072000 : MAP_KEY_T const * ks ) {
458 9072000 : (MAP_KEY_COPY( (kd), (ks) ));
459 9072000 : return kd;
460 9072000 : }
461 :
462 : FD_FN_PURE static inline MAP_(iter_t)
463 3078000 : MAP_(iter_init)( MAP_T const * join ) {
464 3078000 : if( FD_UNLIKELY( !join ) ) return 0UL; /* Debatable */
465 3078000 : MAP_(private_t) const * map = MAP_(private_const)( join );
466 3078000 : ulong ele_rem = map->key_max;
467 21242508 : for( ; ele_rem; ele_rem-- ) if( !MAP_(private_unbox_tag)( join[ ele_rem-1UL ].MAP_NEXT ) ) break;
468 3078000 : return ele_rem;
469 3078000 : }
470 :
471 : FD_FN_CONST static inline int
472 : MAP_(iter_done)( MAP_T const * join,
473 791046000 : MAP_(iter_t) ele_rem ) {
474 791046000 : (void)join;
475 791046000 : return !ele_rem;
476 791046000 : }
477 :
478 : __attribute__((warn_unused_result))
479 : FD_FN_PURE static inline MAP_(iter_t)
480 : MAP_(iter_next)( MAP_T const * join,
481 787968000 : MAP_(iter_t) ele_rem ) {
482 1557771492 : for( ele_rem--; ele_rem; ele_rem-- ) if( !MAP_(private_unbox_tag)( join[ ele_rem-1UL ].MAP_NEXT ) ) break;
483 787968000 : return ele_rem;
484 787968000 : }
485 :
486 : FD_FN_CONST static inline MAP_T *
487 : MAP_(iter_ele)( MAP_T * join,
488 787968000 : MAP_(iter_t) ele_rem ) {
489 787968000 : return join + ele_rem - 1UL;
490 787968000 : }
491 :
492 : FD_FN_CONST static inline MAP_T const *
493 : MAP_(iter_ele_const)( MAP_T const * join,
494 787968000 : MAP_(iter_t) ele_rem ) {
495 787968000 : return join + ele_rem - 1UL;
496 787968000 : }
497 :
498 : FD_PROTOTYPES_END
499 :
500 : #endif
501 :
502 : #if MAP_IMPL_STYLE==1 /* need prototypes */
503 :
504 : FD_PROTOTYPES_BEGIN
505 :
506 : FD_FN_CONST ulong MAP_(align) ( void );
507 : FD_FN_CONST ulong MAP_(footprint)( ulong key_max );
508 : void * MAP_(new) ( void * shmem, ulong key_max, ulong seed );
509 : MAP_T * MAP_(join) ( void * shmap );
510 : void * MAP_(leave) ( MAP_T * join );
511 : void * MAP_(delete) ( void * shmap );
512 :
513 : MAP_T *
514 : MAP_(insert)( MAP_T * join,
515 : MAP_KEY_T const * key );
516 :
517 : MAP_T *
518 : MAP_(remove)( MAP_T * join,
519 : MAP_KEY_T const * key );
520 :
521 : FD_FN_PURE MAP_T *
522 : MAP_(query)( MAP_T * join,
523 : MAP_KEY_T const * key,
524 : MAP_T * null );
525 :
526 : FD_FN_PURE MAP_T *
527 : MAP_(query2)( MAP_T * join,
528 : MAP_KEY_T const * key,
529 : MAP_T * null );
530 :
531 : FD_FN_PURE MAP_T const *
532 : MAP_(query_const)( MAP_T const * join,
533 : MAP_KEY_T const * key,
534 : MAP_T const * null );
535 :
536 : FD_FN_PURE MAP_T const *
537 : MAP_(query_safe)( MAP_T const * join,
538 : MAP_KEY_T const * key,
539 : MAP_T const * null );
540 :
541 : int
542 : MAP_(verify)( MAP_T const * join );
543 :
544 : MAP_T *
545 : MAP_(pop_free_ele)( MAP_T * join );
546 :
547 : MAP_T *
548 : MAP_(push_free_ele)( MAP_T * join,
549 : MAP_T * ele );
550 :
551 : FD_PROTOTYPES_END
552 :
553 : #else /* need implementations */
554 :
555 : #if MAP_IMPL_STYLE==0 /* local only */
556 : #define MAP_IMPL_STATIC FD_FN_UNUSED static
557 : #else
558 : #define MAP_IMPL_STATIC
559 : #endif
560 :
561 : FD_FN_CONST MAP_IMPL_STATIC ulong
562 6144090 : MAP_(align)( void ) {
563 6144090 : return fd_ulong_max( 128UL, alignof(MAP_T) );
564 6144090 : }
565 :
566 : FD_FN_CONST MAP_IMPL_STATIC ulong
567 6144030 : MAP_(footprint)( ulong key_max ) {
568 6144030 : ulong align = MAP_(align)();
569 :
570 : /* memory layout is:
571 :
572 : 2 ulong | pad | list_cnt ulong | map_private_t | key_max map_t | pad
573 : <------ meta_footprint, align multiple ------>
574 : <------------------ footprint, align multiple -------------------->
575 :
576 : Noting that list_cnt is in [key_max/2,key_max], footprint is
577 : (conservatively) at most:
578 :
579 : 2*sizeof(ulong) + align-1 + key_max*sizeof(ulong) + sizeof(map_private_t) + key_max*sizeof(map_t) + align-1
580 :
581 : Requiring this to be at most ULONG_MAX (such that no calculations
582 : will overflow) yields the below. We also must have
583 : key_max<=2^63-1==MAP_IDX_NULL given how elements are marked. */
584 :
585 6144030 : ulong key_thresh = fd_ulong_min( (ULONG_MAX - 2UL*(align-1UL) - 2UL*sizeof(ulong) - sizeof(MAP_(private_t))) /
586 6144030 : (sizeof(MAP_T) + sizeof(ulong)), MAP_IDX_NULL );
587 6144030 : if( FD_UNLIKELY( key_max>key_thresh ) ) return 0UL;
588 6144018 : ulong list_cnt = MAP_(private_list_cnt) ( key_max );
589 6144018 : ulong meta_footprint = MAP_(private_meta_footprint)( list_cnt );
590 6144018 : return meta_footprint + fd_ulong_align_up( key_max*sizeof(MAP_T), align );
591 6144030 : }
592 :
593 : MAP_IMPL_STATIC void *
594 : MAP_(new)( void * shmem,
595 : ulong key_max,
596 24 : ulong seed ) {
597 24 : ulong * hdr = (ulong *)shmem;
598 :
599 24 : if( FD_UNLIKELY( !hdr ) ) {
600 6 : FD_LOG_WARNING(( "NULL shmem" ));
601 6 : return NULL;
602 6 : }
603 :
604 18 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)hdr, MAP_(align)() ) ) ) {
605 6 : FD_LOG_WARNING(( "misaligned shmem" ));
606 6 : return NULL;
607 6 : }
608 :
609 12 : ulong footprint = MAP_(footprint)( key_max );
610 12 : if( FD_UNLIKELY( !footprint ) ) {
611 6 : FD_LOG_WARNING(( "bad key_max" ));
612 6 : return NULL;
613 6 : }
614 :
615 : /* Init the metadata */
616 :
617 6 : ulong list_cnt = MAP_(private_list_cnt)( key_max );
618 6 : ulong meta_footprint = MAP_(private_meta_footprint)( list_cnt );
619 :
620 6 : MAP_T * join = (MAP_T *)( ((ulong)shmem) + meta_footprint );
621 6 : MAP_(private_t) * map = MAP_(private)( join );
622 :
623 6 : map->key_max = key_max;
624 6 : map->seed = seed;
625 6 : map->list_cnt = list_cnt;
626 6 : map->key_cnt = 0UL;
627 :
628 : /* Init the free stack */
629 :
630 6 : if( FD_UNLIKELY( !key_max ) ) map->free_stack = MAP_(private_box_next)( MAP_IDX_NULL, 1 );
631 6 : else {
632 6 : map->free_stack = MAP_(private_box_next)( 0UL, 1 );
633 3072 : for( ulong ele_idx=1UL; ele_idx<key_max; ele_idx++ ) join[ ele_idx-1UL ].MAP_NEXT = MAP_(private_box_next)( ele_idx, 1 );
634 6 : join[ key_max-1UL ].MAP_NEXT = MAP_(private_box_next)( MAP_IDX_NULL, 1 );
635 6 : }
636 :
637 : /* Set all the lists to null */
638 :
639 6 : ulong * list = MAP_(private_list)( map );
640 1542 : for( ulong list_idx=0UL; list_idx<list_cnt; list_idx++ ) list[ list_idx ] = MAP_(private_box_next)( MAP_IDX_NULL, 0 );
641 :
642 6 : hdr[1] = meta_footprint;
643 :
644 6 : FD_COMPILER_MFENCE();
645 6 : FD_VOLATILE( hdr[0] ) = MAP_MAGIC;
646 6 : FD_COMPILER_MFENCE();
647 :
648 6 : return hdr;
649 12 : }
650 :
651 : MAP_IMPL_STATIC MAP_T *
652 24 : MAP_(join)( void * shmap ) {
653 24 : ulong * hdr = (ulong *)shmap;
654 :
655 24 : if( FD_UNLIKELY( !hdr ) ) {
656 6 : FD_LOG_WARNING(( "NULL shmap" ));
657 6 : return NULL;
658 6 : }
659 :
660 18 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)hdr, MAP_(align)() ) ) ) {
661 6 : FD_LOG_WARNING(( "misaligned shmap" ));
662 6 : return NULL;
663 6 : }
664 :
665 12 : if( FD_UNLIKELY( hdr[0]!=MAP_MAGIC ) ) {
666 6 : FD_LOG_WARNING(( "bad magic" ));
667 6 : return NULL;
668 6 : }
669 :
670 6 : return (MAP_T *)(((ulong)shmap) + hdr[1]);
671 12 : }
672 :
673 : MAP_IMPL_STATIC void *
674 12 : MAP_(leave)( MAP_T * join ) {
675 :
676 12 : if( FD_UNLIKELY( !join ) ) {
677 6 : FD_LOG_WARNING(( "NULL join" ));
678 6 : return NULL;
679 6 : }
680 :
681 6 : return (void *)(((ulong)join) - MAP_(private_meta_footprint)( MAP_(private)( join )->list_cnt ));
682 12 : }
683 :
684 : MAP_IMPL_STATIC void *
685 24 : MAP_(delete)( void * shmap ) {
686 24 : ulong * hdr = (ulong *)shmap;
687 :
688 24 : if( FD_UNLIKELY( !hdr ) ) {
689 6 : FD_LOG_WARNING(( "NULL shmap" ));
690 6 : return NULL;
691 6 : }
692 :
693 18 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)hdr, MAP_(align)() ) ) ) {
694 6 : FD_LOG_WARNING(( "misaligned shmap" ));
695 6 : return NULL;
696 6 : }
697 :
698 12 : if( FD_UNLIKELY( hdr[0]!=MAP_MAGIC ) ) {
699 6 : FD_LOG_WARNING(( "bad magic" ));
700 6 : return NULL;
701 6 : }
702 :
703 6 : FD_COMPILER_MFENCE();
704 6 : FD_VOLATILE( hdr[0] ) = 0UL;
705 6 : FD_COMPILER_MFENCE();
706 :
707 6 : return shmap;
708 12 : }
709 :
710 : static inline long
711 : MAP_(verify_key)( MAP_T * join,
712 : MAP_KEY_T const * key,
713 0 : ulong cnt ) {
714 0 : # define MAP_TEST(c) do { \
715 0 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
716 0 : } while(0)
717 0 :
718 0 : MAP_(private_t) * map = MAP_(private)( join );
719 0 : ulong list_idx = MAP_(private_list_idx)( key, map->seed, map->list_cnt );
720 0 : ulong key_max = map->key_max;
721 0 : ulong key_cnt = map->key_cnt;
722 0 : ulong ele_idx = MAP_(private_list)( map )[ MAP_(private_list_idx)( key, map->seed, map->list_cnt ) ];
723 0 : while( !MAP_(private_is_null)( ele_idx ) ) {
724 0 : MAP_TEST( cnt<key_cnt );
725 0 : MAP_TEST( ele_idx<key_max );
726 0 : MAP_T const * ele = join + ele_idx;
727 0 : MAP_TEST( MAP_(private_list_idx)( &ele->MAP_KEY, map->seed, map->list_cnt )==list_idx );
728 0 : cnt++;
729 0 : ele_idx = MAP_(private_unbox_idx)( ele->MAP_NEXT );
730 0 : MAP_TEST( !MAP_(private_unbox_tag)( ele->MAP_NEXT ) ); /* Element marked as used */
731 0 : }
732 0 :
733 0 : # undef MAP_TEST
734 0 : return (long)cnt;;
735 0 : }
736 :
737 : FD_FN_PURE MAP_IMPL_STATIC MAP_T *
738 : MAP_(query)( MAP_T * join,
739 : MAP_KEY_T const * key,
740 1575936000 : MAP_T * sentinel ) {
741 1575936000 : MAP_(private_t) * map = MAP_(private)( join );
742 :
743 :
744 : /* Find the key */
745 :
746 1575936000 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
747 1575936000 : ulong * head = MAP_(private_list)( map ) + ( hash & (map->list_cnt-1UL) );
748 1575936000 : ulong * cur = head;
749 3210248280 : for(;;) {
750 3210248280 : ulong ele_idx = MAP_(private_unbox_idx)( *cur );
751 3210248280 : if( FD_UNLIKELY( MAP_(private_is_null)( ele_idx ) ) ) break; /* optimize for found */
752 2422280280 : MAP_T * ele = join + ele_idx;
753 2422280280 : if(
754 : #if MAP_MEMOIZE
755 1211140140 : hash == ele->MAP_HASH &&
756 : #endif
757 1605124140 : FD_LIKELY( MAP_(key_eq)( key, &ele->MAP_KEY ) ) ) { /* Optimize for found (it is remove after all) */
758 : /* Found, move it to the front of the chain. (FIXME: BRANCH PROB? DO BRANCHLESS?) */
759 787968000 : if( FD_UNLIKELY( cur!=head ) ) { /* Assume already at head from previous query */
760 566605140 : *cur = ele->MAP_NEXT; /* Already tagged free */
761 566605140 : ele->MAP_NEXT = *head; /* Already tagged free */
762 566605140 : *head = MAP_(private_box_next)( ele_idx, 0 );
763 566605140 : }
764 787968000 : return ele;
765 787968000 : }
766 1634312280 : cur = &ele->MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
767 1634312280 : }
768 :
769 : /* Not found */
770 :
771 787968000 : return sentinel;
772 1575936000 : }
773 :
774 : FD_FN_PURE MAP_IMPL_STATIC MAP_T *
775 : MAP_(query2)( MAP_T * join,
776 : MAP_KEY_T const * key,
777 0 : MAP_T * sentinel ) {
778 0 : MAP_(private_t) * map = MAP_(private)( join );
779 0 :
780 0 :
781 0 : /* Find the key */
782 0 :
783 0 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
784 0 : ulong * head = MAP_(private_list)( map ) + ( hash & (map->list_cnt-1UL) );
785 0 : ulong * cur = head;
786 0 : for(;;) {
787 0 : ulong ele_idx = MAP_(private_unbox_idx)( *cur );
788 0 : if( FD_UNLIKELY( MAP_(private_is_null)( ele_idx ) ) ) break; /* optimize for found */
789 0 : MAP_T * ele = join + ele_idx;
790 0 : if(
791 0 : #if MAP_MEMOIZE
792 0 : hash == ele->MAP_HASH &&
793 0 : #endif
794 0 : FD_LIKELY( MAP_(key_eq)( key, &ele->MAP_KEY ) ) ) { /* Optimize for found (it is remove after all) */
795 0 : return ele; /* optimize for found */
796 0 : }
797 0 : cur = &ele->MAP_NEXT;
798 0 : }
799 0 :
800 0 : /* Not found */
801 0 :
802 0 : return sentinel;
803 0 : }
804 :
805 : FD_FN_PURE MAP_IMPL_STATIC MAP_T const *
806 : MAP_(query_const)( MAP_T const * join,
807 : MAP_KEY_T const * key,
808 1839202794 : MAP_T const * sentinel ) {
809 1839202794 : MAP_(private_t) const * map = MAP_(private_const)( join );
810 :
811 : /* Find the key */
812 :
813 1839202794 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
814 1839202794 : ulong const * head = MAP_(private_list_const)( map ) + ( hash & (map->list_cnt-1UL) );
815 1839202794 : ulong const * cur = head;
816 3197008218 : for(;;) {
817 3197008218 : ulong ele_idx = MAP_(private_unbox_idx)( *cur );
818 3197008218 : if( FD_UNLIKELY( MAP_(private_is_null)( ele_idx ) ) ) break; /* optimize for found */
819 3193936218 : MAP_T const * ele = join + ele_idx;
820 3193936218 : if(
821 : #if MAP_MEMOIZE
822 1596968109 : hash == ele->MAP_HASH &&
823 : #endif
824 2515033506 : FD_LIKELY( MAP_(key_eq)( key, &ele->MAP_KEY ) ) ) { /* Optimize for found (it is remove after all) */
825 1836130794 : return ele; /* optimize for found */
826 1836130794 : }
827 1357805424 : cur = &ele->MAP_NEXT;
828 1357805424 : }
829 :
830 : /* Not found */
831 :
832 3072000 : return sentinel;
833 1839202794 : }
834 :
835 : FD_FN_PURE MAP_IMPL_STATIC MAP_T const *
836 : MAP_(query_safe)( MAP_T const * join,
837 : MAP_KEY_T const * key,
838 0 : MAP_T const * sentinel ) {
839 0 : MAP_(private_t) const * map = MAP_(private_const)( join );
840 :
841 0 : ulong key_max = map->key_max;
842 :
843 : /* Find the key */
844 :
845 0 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
846 0 : ulong const * head = MAP_(private_list_const)( map ) + ( hash & (map->list_cnt-1UL) );
847 0 : ulong const * cur = head;
848 0 : for( ulong i = 0; i < key_max; ++i ) {
849 0 : ulong ele_idx = MAP_(private_unbox_idx)( *cur );
850 0 : if( FD_UNLIKELY( MAP_(private_is_null)( ele_idx ) || ele_idx >= key_max ) ) break; /* optimize for found */
851 0 : MAP_T const * ele = join + ele_idx;
852 0 : if(
853 : #if MAP_MEMOIZE
854 : hash == ele->MAP_HASH &&
855 : #endif
856 0 : FD_LIKELY( MAP_(key_eq)( key, &ele->MAP_KEY ) ) ) { /* Optimize for found (it is remove after all) */
857 0 : return ele; /* optimize for found */
858 0 : }
859 0 : cur = &ele->MAP_NEXT;
860 0 : }
861 :
862 : /* Not found */
863 :
864 0 : return sentinel;
865 0 : }
866 :
867 : MAP_IMPL_STATIC int
868 6144006 : MAP_(verify)( MAP_T const * join ) {
869 :
870 14472813600 : # define MAP_TEST(c) do { \
871 14472813600 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
872 14472813600 : } while(0)
873 :
874 6144006 : MAP_TEST( join );
875 :
876 6144006 : MAP_(private_t) const * map = MAP_(private_const)( join ); MAP_TEST( map!=NULL );
877 :
878 6144006 : MAP_TEST( MAP_(footprint)( map->key_max ) );
879 :
880 : /* seed can be anything as far as map is concerned */
881 :
882 6144006 : MAP_TEST( map->list_cnt==MAP_(private_list_cnt)( map->key_max ) );
883 6144006 : MAP_TEST( map->key_cnt <=map->key_max );
884 :
885 6144006 : ulong key_max = map->key_max;
886 6144006 : ulong key_cnt = map->key_cnt;
887 6144006 : ulong seed = map->seed;
888 6144006 : ulong list_cnt = map->list_cnt;
889 6144006 : ulong const * list = MAP_(private_list_const)( map ); MAP_TEST( list!=NULL );
890 :
891 6144006 : ulong free_cnt = key_max - key_cnt;
892 :
893 6144006 : ulong ele_idx;
894 6144006 : ulong cnt;
895 :
896 6144006 : cnt = 0UL;
897 1579009542 : for( ulong list_idx=0UL; list_idx<list_cnt; list_idx++ ) {
898 1572865536 : ele_idx = MAP_(private_unbox_idx)( list[ list_idx ] );
899 1572865536 : MAP_TEST( !MAP_(private_unbox_tag)( list[ list_idx ] ) ); /* Head marked as used */
900 3145729536 : while( !MAP_(private_is_null)( ele_idx ) ) {
901 1572864000 : MAP_TEST( cnt<key_cnt );
902 1572864000 : MAP_TEST( ele_idx<key_max );
903 1572864000 : MAP_T const * ele = join + ele_idx;
904 : #if MAP_MEMOIZE
905 786432000 : MAP_TEST( ele->MAP_HASH == MAP_KEY_HASH( (&ele->MAP_KEY), (map->seed) ) );
906 786432000 : #endif
907 1572864000 : MAP_TEST( MAP_(private_list_idx)( &ele->MAP_KEY, seed, list_cnt )==list_idx );
908 1572864000 : cnt++;
909 1572864000 : ele_idx = MAP_(private_unbox_idx)( ele->MAP_NEXT );
910 1572864000 : MAP_TEST( !MAP_(private_unbox_tag)( ele->MAP_NEXT ) ); /* Element marked as used */
911 1572864000 : }
912 1572865536 : }
913 :
914 6144006 : MAP_TEST( cnt==key_cnt );
915 :
916 6144006 : cnt = 0UL;
917 :
918 6144006 : ele_idx = MAP_(private_unbox_idx)( map->free_stack );
919 6144006 : MAP_TEST( MAP_(private_unbox_tag)( map->free_stack ) ); /* Head marked as free */
920 1579011078 : while( !MAP_(private_is_null)( ele_idx ) ) {
921 1572867072 : MAP_TEST( cnt<free_cnt );
922 1572867072 : MAP_TEST( ele_idx<key_max );
923 1572867072 : MAP_T const * ele = join + ele_idx;
924 1572867072 : cnt++;
925 1572867072 : ele_idx = MAP_(private_unbox_idx)( ele->MAP_NEXT );
926 1572867072 : MAP_TEST( MAP_(private_unbox_tag)( ele->MAP_NEXT ) ); /* Element marked as free */
927 1572867072 : }
928 :
929 6144006 : MAP_TEST( cnt==free_cnt );
930 :
931 1579008006 : for( ulong ele_idx=0UL; ele_idx<key_cnt; ele_idx++ ) {
932 1572864000 : if( MAP_(private_unbox_tag)( join[ele_idx].MAP_NEXT ) ) continue;
933 1048162794 : MAP_TEST( MAP_(query_const)( join, &join[ele_idx].MAP_KEY, NULL )==&join[ele_idx] );
934 1048162794 : }
935 :
936 6144006 : # undef MAP_TEST
937 :
938 6144006 : return 0;
939 6144006 : }
940 :
941 : MAP_IMPL_STATIC MAP_T *
942 : MAP_(insert)( MAP_T * join,
943 3072000 : MAP_KEY_T const * key ) {
944 : # if FD_TMPL_USE_HANDHOLDING
945 : if( FD_UNLIKELY( MAP_(key_cnt)( join )>=MAP_(key_max)( join ) ) ) FD_LOG_CRIT(( "map is full" ));
946 : # endif
947 3072000 : MAP_(private_t) * map = MAP_(private)( join );
948 :
949 : /* Pop the free stack to allocate an element (this is guaranteed to
950 : succeed as per contract) */
951 :
952 3072000 : ulong ele_idx = MAP_(private_unbox_idx)( map->free_stack );
953 3072000 : MAP_T * ele = join + ele_idx;
954 3072000 : map->free_stack = ele->MAP_NEXT; /* already tagged free */
955 3072000 : map->key_cnt++; /* Consider eliminating this to help make completely concurrent lockfree? */
956 :
957 : /* ... and map the newly allocated element to key (this is also
958 : guaranteed to not have collisions as per contract). Note that
959 : elements appear in the chain in order of newest to oldest. This
960 : property is NECESSARY for an important optimization in
961 : fd_funk_rec_query_global. */
962 :
963 3072000 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
964 3072000 : ulong * head = MAP_(private_list)( map ) + ( hash & (map->list_cnt-1UL) );
965 3072000 : MAP_(key_copy)( &ele->MAP_KEY, key );
966 3072000 : ele->MAP_NEXT = MAP_(private_box_next)( MAP_(private_unbox_idx)( *head ), 0 );
967 : # if MAP_MEMOIZE
968 1536000 : ele->MAP_HASH = hash;
969 : # endif
970 3072000 : *head = MAP_(private_box_next)( ele_idx, 0 );
971 3072000 : return ele;
972 3072000 : }
973 :
974 : MAP_IMPL_STATIC MAP_T *
975 0 : MAP_(pop_free_ele)( MAP_T * join ) {
976 0 : # if FD_TMPL_USE_HANDHOLDING
977 0 : if( FD_UNLIKELY( !MAP_(key_cnt)( join ) ) ) FD_LOG_CRIT(( "map is empty" ));
978 0 : # endif
979 0 : MAP_(private_t) * map = MAP_(private)( join );
980 0 :
981 0 : /* Pop the free stack to allocate an element (this is guaranteed to
982 0 : succeed as per contract) */
983 0 :
984 0 : ulong ele_idx = MAP_(private_unbox_idx)( map->free_stack );
985 0 : MAP_T * ele = join + ele_idx;
986 0 : map->free_stack = ele->MAP_NEXT; /* already tagged free */
987 0 : return ele;
988 0 : }
989 :
990 : MAP_IMPL_STATIC MAP_T *
991 : MAP_(push_free_ele)( MAP_T * join,
992 0 : MAP_T * ele ) {
993 0 : MAP_(private_t) * map = MAP_(private)( join );
994 0 :
995 0 : ulong ele_idx = (ulong)(ele - join);
996 0 :
997 0 : ele->MAP_NEXT = map->free_stack; /* already tagged free */
998 0 : map->free_stack = MAP_(private_box_next)( ele_idx, 1 );
999 0 : return ele;
1000 0 : }
1001 :
1002 : MAP_IMPL_STATIC MAP_T *
1003 : MAP_(insert_free_ele)( MAP_T * join,
1004 : MAP_T * ele,
1005 0 : MAP_KEY_T const * key ) {
1006 0 : MAP_(private_t) * map = MAP_(private)( join );
1007 0 : /* Map the allocated element to key (this is also
1008 0 : guaranteed to not have collisions as per contract). */
1009 0 :
1010 0 : ulong ele_idx = (ulong)(ele - join);
1011 0 :
1012 0 : ulong * head = MAP_(private_list)( map ) + MAP_(private_list_idx)( key, map->seed, map->list_cnt );
1013 0 : MAP_(key_copy)( &ele->MAP_KEY, key );
1014 0 : ele->MAP_NEXT = MAP_(private_box_next)( MAP_(private_unbox_idx)( *head ), 0 );
1015 0 : *head = MAP_(private_box_next)( ele_idx, 0 );
1016 0 : return ele;
1017 0 : }
1018 :
1019 : MAP_IMPL_STATIC MAP_T *
1020 : MAP_(remove)( MAP_T * join,
1021 6144000 : MAP_KEY_T const * key ) {
1022 6144000 : MAP_(private_t) * map = MAP_(private)( join );
1023 :
1024 :
1025 : /* Find the key */
1026 :
1027 6144000 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
1028 6144000 : ulong * head = MAP_(private_list)( map ) + ( hash & (map->list_cnt-1UL) );
1029 6144000 : ulong * cur = head;
1030 9330000 : for(;;) {
1031 9330000 : ulong ele_idx = MAP_(private_unbox_idx)( *cur );
1032 9330000 : if( FD_UNLIKELY( MAP_(private_is_null)( ele_idx ) ) ) break;
1033 6258000 : MAP_T * ele = join + ele_idx;
1034 6258000 : if(
1035 : #if MAP_MEMOIZE
1036 3129000 : hash == ele->MAP_HASH &&
1037 : #endif
1038 4665000 : FD_LIKELY( MAP_(key_eq)( key, &ele->MAP_KEY ) ) ) { /* Optimize for found (it is remove after all) */
1039 : /* Found, remove the mapping and push it to free stack. */
1040 3072000 : *cur = ele->MAP_NEXT; /* already tagged empty */
1041 3072000 : ele->MAP_NEXT = map->free_stack; /* already tagged free */
1042 3072000 : map->free_stack = MAP_(private_box_next)( ele_idx, 1 );
1043 3072000 : map->key_cnt--;
1044 3072000 : return ele;
1045 3072000 : }
1046 3186000 : cur = &ele->MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
1047 3186000 : }
1048 :
1049 : /* Not found */
1050 3072000 : return NULL;
1051 6144000 : }
1052 :
1053 : #undef MAP_IMPL_STATIC
1054 :
1055 : #endif
1056 :
1057 : #undef MAP_
1058 : #undef MAP_IDX_NULL
1059 :
1060 : #undef MAP_IMPL_STYLE
1061 : #undef MAP_MAGIC
1062 : #undef MAP_KEY_COPY
1063 : #undef MAP_KEY_HASH
1064 : #undef MAP_KEY_EQ
1065 : #undef MAP_NEXT
1066 : #undef MAP_KEY
1067 : #undef MAP_KEY_T
1068 : #undef MAP_T
1069 : #undef MAP_NAME
1070 : #undef MAP_MEMOIZE
1071 : #undef MAP_HASH
|
