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 or NULL if there was no space 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 0 : #define MAP_KEY key
232 : #endif
233 :
234 : /* MAP_NEXT is the MAP_T next field */
235 :
236 : #ifndef MAP_NEXT
237 0 : #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 : FD_FN_PURE static inline MAP_(iter_t)
479 : MAP_(iter_next)( MAP_T const * join,
480 787968000 : MAP_(iter_t) ele_rem ) {
481 1557771492 : for( ele_rem--; ele_rem; ele_rem-- ) if( !MAP_(private_unbox_tag)( join[ ele_rem-1UL ].MAP_NEXT ) ) break;
482 787968000 : return ele_rem;
483 787968000 : }
484 :
485 : FD_FN_CONST static inline MAP_T *
486 : MAP_(iter_ele)( MAP_T * join,
487 787968000 : MAP_(iter_t) ele_rem ) {
488 787968000 : return join + ele_rem - 1UL;
489 787968000 : }
490 :
491 : FD_FN_CONST static inline MAP_T const *
492 : MAP_(iter_ele_const)( MAP_T const * join,
493 787968000 : MAP_(iter_t) ele_rem ) {
494 787968000 : return join + ele_rem - 1UL;
495 787968000 : }
496 :
497 : FD_PROTOTYPES_END
498 :
499 : #endif
500 :
501 : #if MAP_IMPL_STYLE==1 /* need prototypes */
502 :
503 : FD_PROTOTYPES_BEGIN
504 :
505 : FD_FN_CONST ulong MAP_(align) ( void );
506 : FD_FN_CONST ulong MAP_(footprint)( ulong key_max );
507 : void * MAP_(new) ( void * shmem, ulong key_max, ulong seed );
508 : MAP_T * MAP_(join) ( void * shmap );
509 : void * MAP_(leave) ( MAP_T * join );
510 : void * MAP_(delete) ( void * shmap );
511 :
512 : MAP_T *
513 : MAP_(insert)( MAP_T * join,
514 : MAP_KEY_T const * key );
515 :
516 : MAP_T *
517 : MAP_(remove)( MAP_T * join,
518 : MAP_KEY_T const * key );
519 :
520 : FD_FN_PURE MAP_T *
521 : MAP_(query)( MAP_T * join,
522 : MAP_KEY_T const * key,
523 : MAP_T * null );
524 :
525 : FD_FN_PURE MAP_T *
526 : MAP_(query2)( MAP_T * join,
527 : MAP_KEY_T const * key,
528 : MAP_T * null );
529 :
530 : FD_FN_PURE MAP_T const *
531 : MAP_(query_const)( MAP_T const * join,
532 : MAP_KEY_T const * key,
533 : MAP_T const * null );
534 :
535 : FD_FN_PURE MAP_T const *
536 : MAP_(query_safe)( MAP_T const * join,
537 : MAP_KEY_T const * key,
538 : MAP_T const * null );
539 :
540 : int
541 : MAP_(verify)( MAP_T const * join );
542 :
543 : MAP_T *
544 : MAP_(pop_free_ele)( MAP_T * join );
545 :
546 : MAP_T *
547 : MAP_(push_free_ele)( MAP_T * join,
548 : MAP_T * ele );
549 :
550 : FD_PROTOTYPES_END
551 :
552 : #else /* need implementations */
553 :
554 : #if MAP_IMPL_STYLE==0 /* local only */
555 : #define MAP_IMPL_STATIC FD_FN_UNUSED static
556 : #else
557 : #define MAP_IMPL_STATIC
558 : #endif
559 :
560 : FD_FN_CONST MAP_IMPL_STATIC ulong
561 6144090 : MAP_(align)( void ) {
562 6144090 : return fd_ulong_max( 128UL, alignof(MAP_T) );
563 6144090 : }
564 :
565 : FD_FN_CONST MAP_IMPL_STATIC ulong
566 6144030 : MAP_(footprint)( ulong key_max ) {
567 6144030 : ulong align = MAP_(align)();
568 :
569 : /* memory layout is:
570 :
571 : 2 ulong | pad | list_cnt ulong | map_private_t | key_max map_t | pad
572 : <------ meta_footprint, align multiple ------>
573 : <------------------ footprint, align multiple -------------------->
574 :
575 : Noting that list_cnt is in [key_max/2,key_max], footprint is
576 : (conservatively) at most:
577 :
578 : 2*sizeof(ulong) + align-1 + key_max*sizeof(ulong) + sizeof(map_private_t) + key_max*sizeof(map_t) + align-1
579 :
580 : Requiring this to be at most ULONG_MAX (such that no calculations
581 : will overflow) yields the below. We also must have
582 : key_max<=2^63-1==MAP_IDX_NULL given how elements are marked. */
583 :
584 6144030 : ulong key_thresh = fd_ulong_min( (ULONG_MAX - 2UL*(align-1UL) - 2UL*sizeof(ulong) - sizeof(MAP_(private_t))) /
585 6144030 : (sizeof(MAP_T) + sizeof(ulong)), MAP_IDX_NULL );
586 6144030 : if( FD_UNLIKELY( key_max>key_thresh ) ) return 0UL;
587 6144018 : ulong list_cnt = MAP_(private_list_cnt) ( key_max );
588 6144018 : ulong meta_footprint = MAP_(private_meta_footprint)( list_cnt );
589 6144018 : return meta_footprint + fd_ulong_align_up( key_max*sizeof(MAP_T), align );
590 6144030 : }
591 :
592 : MAP_IMPL_STATIC void *
593 : MAP_(new)( void * shmem,
594 : ulong key_max,
595 24 : ulong seed ) {
596 24 : ulong * hdr = (ulong *)shmem;
597 :
598 24 : if( FD_UNLIKELY( !hdr ) ) {
599 6 : FD_LOG_WARNING(( "NULL shmem" ));
600 6 : return NULL;
601 6 : }
602 :
603 18 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)hdr, MAP_(align)() ) ) ) {
604 6 : FD_LOG_WARNING(( "misaligned shmem" ));
605 6 : return NULL;
606 6 : }
607 :
608 12 : ulong footprint = MAP_(footprint)( key_max );
609 12 : if( FD_UNLIKELY( !footprint ) ) {
610 6 : FD_LOG_WARNING(( "bad key_max" ));
611 6 : return NULL;
612 6 : }
613 :
614 : /* Init the metadata */
615 :
616 6 : ulong list_cnt = MAP_(private_list_cnt)( key_max );
617 6 : ulong meta_footprint = MAP_(private_meta_footprint)( list_cnt );
618 :
619 6 : MAP_T * join = (MAP_T *)( ((ulong)shmem) + meta_footprint );
620 6 : MAP_(private_t) * map = MAP_(private)( join );
621 :
622 6 : map->key_max = key_max;
623 6 : map->seed = seed;
624 6 : map->list_cnt = list_cnt;
625 6 : map->key_cnt = 0UL;
626 :
627 : /* Init the free stack */
628 :
629 6 : if( FD_UNLIKELY( !key_max ) ) map->free_stack = MAP_(private_box_next)( MAP_IDX_NULL, 1 );
630 6 : else {
631 6 : map->free_stack = MAP_(private_box_next)( 0UL, 1 );
632 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 );
633 6 : join[ key_max-1UL ].MAP_NEXT = MAP_(private_box_next)( MAP_IDX_NULL, 1 );
634 6 : }
635 :
636 : /* Set all the lists to null */
637 :
638 6 : ulong * list = MAP_(private_list)( map );
639 1542 : for( ulong list_idx=0UL; list_idx<list_cnt; list_idx++ ) list[ list_idx ] = MAP_(private_box_next)( MAP_IDX_NULL, 0 );
640 :
641 6 : hdr[1] = meta_footprint;
642 :
643 6 : FD_COMPILER_MFENCE();
644 6 : FD_VOLATILE( hdr[0] ) = MAP_MAGIC;
645 6 : FD_COMPILER_MFENCE();
646 :
647 6 : return hdr;
648 12 : }
649 :
650 : MAP_IMPL_STATIC MAP_T *
651 24 : MAP_(join)( void * shmap ) {
652 24 : ulong * hdr = (ulong *)shmap;
653 :
654 24 : if( FD_UNLIKELY( !hdr ) ) {
655 6 : FD_LOG_WARNING(( "NULL shmap" ));
656 6 : return NULL;
657 6 : }
658 :
659 18 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)hdr, MAP_(align)() ) ) ) {
660 6 : FD_LOG_WARNING(( "misaligned shmap" ));
661 6 : return NULL;
662 6 : }
663 :
664 12 : if( FD_UNLIKELY( hdr[0]!=MAP_MAGIC ) ) {
665 6 : FD_LOG_WARNING(( "bad magic" ));
666 6 : return NULL;
667 6 : }
668 :
669 6 : return (MAP_T *)(((ulong)shmap) + hdr[1]);
670 12 : }
671 :
672 : MAP_IMPL_STATIC void *
673 12 : MAP_(leave)( MAP_T * join ) {
674 :
675 12 : if( FD_UNLIKELY( !join ) ) {
676 6 : FD_LOG_WARNING(( "NULL join" ));
677 6 : return NULL;
678 6 : }
679 :
680 6 : return (void *)(((ulong)join) - MAP_(private_meta_footprint)( MAP_(private)( join )->list_cnt ));
681 12 : }
682 :
683 : MAP_IMPL_STATIC void *
684 24 : MAP_(delete)( void * shmap ) {
685 24 : ulong * hdr = (ulong *)shmap;
686 :
687 24 : if( FD_UNLIKELY( !hdr ) ) {
688 6 : FD_LOG_WARNING(( "NULL shmap" ));
689 6 : return NULL;
690 6 : }
691 :
692 18 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)hdr, MAP_(align)() ) ) ) {
693 6 : FD_LOG_WARNING(( "misaligned shmap" ));
694 6 : return NULL;
695 6 : }
696 :
697 12 : if( FD_UNLIKELY( hdr[0]!=MAP_MAGIC ) ) {
698 6 : FD_LOG_WARNING(( "bad magic" ));
699 6 : return NULL;
700 6 : }
701 :
702 6 : FD_COMPILER_MFENCE();
703 6 : FD_VOLATILE( hdr[0] ) = 0UL;
704 6 : FD_COMPILER_MFENCE();
705 :
706 6 : return shmap;
707 12 : }
708 :
709 : static inline long
710 : MAP_(verify_key)( MAP_T * join,
711 : MAP_KEY_T const * key,
712 0 : ulong cnt ) {
713 0 : # define MAP_TEST(c) do { \
714 0 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
715 0 : } while(0)
716 0 :
717 0 : MAP_(private_t) * map = MAP_(private)( join );
718 0 : ulong list_idx = MAP_(private_list_idx)( key, map->seed, map->list_cnt );
719 0 : ulong key_max = map->key_max;
720 0 : ulong key_cnt = map->key_cnt;
721 0 : ulong ele_idx = MAP_(private_list)( map )[ MAP_(private_list_idx)( key, map->seed, map->list_cnt ) ];
722 0 : while( !MAP_(private_is_null)( ele_idx ) ) {
723 0 : MAP_TEST( cnt<key_cnt );
724 0 : MAP_TEST( ele_idx<key_max );
725 0 : MAP_T const * ele = join + ele_idx;
726 0 : MAP_TEST( MAP_(private_list_idx)( &ele->MAP_KEY, map->seed, map->list_cnt )==list_idx );
727 0 : cnt++;
728 0 : ele_idx = MAP_(private_unbox_idx)( ele->MAP_NEXT );
729 0 : MAP_TEST( !MAP_(private_unbox_tag)( ele->MAP_NEXT ) ); /* Element marked as used */
730 0 : }
731 0 :
732 0 : # undef MAP_TEST
733 0 : return (long)cnt;;
734 0 : }
735 :
736 : FD_FN_PURE MAP_IMPL_STATIC MAP_T *
737 : MAP_(query)( MAP_T * join,
738 : MAP_KEY_T const * key,
739 1575936000 : MAP_T * sentinel ) {
740 1575936000 : MAP_(private_t) * map = MAP_(private)( join );
741 :
742 :
743 : /* Find the key */
744 :
745 1575936000 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
746 1575936000 : ulong * head = MAP_(private_list)( map ) + ( hash & (map->list_cnt-1UL) );
747 1575936000 : ulong * cur = head;
748 3210248280 : for(;;) {
749 3210248280 : ulong ele_idx = MAP_(private_unbox_idx)( *cur );
750 3210248280 : if( FD_UNLIKELY( MAP_(private_is_null)( ele_idx ) ) ) break; /* optimize for found */
751 2422280280 : MAP_T * ele = join + ele_idx;
752 2422280280 : if(
753 : #if MAP_MEMOIZE
754 1211140140 : hash == ele->MAP_HASH &&
755 : #endif
756 1605124140 : FD_LIKELY( MAP_(key_eq)( key, &ele->MAP_KEY ) ) ) { /* Optimize for found (it is remove after all) */
757 : /* Found, move it to the front of the chain. (FIXME: BRANCH PROB? DO BRANCHLESS?) */
758 787968000 : if( FD_UNLIKELY( cur!=head ) ) { /* Assume already at head from previous query */
759 566605140 : *cur = ele->MAP_NEXT; /* Already tagged free */
760 566605140 : ele->MAP_NEXT = *head; /* Already tagged free */
761 566605140 : *head = MAP_(private_box_next)( ele_idx, 0 );
762 566605140 : }
763 787968000 : return ele;
764 787968000 : }
765 1634312280 : cur = &ele->MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
766 1634312280 : }
767 :
768 : /* Not found */
769 :
770 787968000 : return sentinel;
771 1575936000 : }
772 :
773 : FD_FN_PURE MAP_IMPL_STATIC MAP_T *
774 : MAP_(query2)( MAP_T * join,
775 : MAP_KEY_T const * key,
776 0 : MAP_T * sentinel ) {
777 0 : MAP_(private_t) * map = MAP_(private)( join );
778 0 :
779 0 :
780 0 : /* Find the key */
781 0 :
782 0 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
783 0 : ulong * head = MAP_(private_list)( map ) + ( hash & (map->list_cnt-1UL) );
784 0 : ulong * cur = head;
785 0 : for(;;) {
786 0 : ulong ele_idx = MAP_(private_unbox_idx)( *cur );
787 0 : if( FD_UNLIKELY( MAP_(private_is_null)( ele_idx ) ) ) break; /* optimize for found */
788 0 : MAP_T * ele = join + ele_idx;
789 0 : if(
790 0 : #if MAP_MEMOIZE
791 0 : hash == ele->MAP_HASH &&
792 0 : #endif
793 0 : FD_LIKELY( MAP_(key_eq)( key, &ele->MAP_KEY ) ) ) { /* Optimize for found (it is remove after all) */
794 0 : return ele; /* optimize for found */
795 0 : }
796 0 : cur = &ele->MAP_NEXT;
797 0 : }
798 0 :
799 0 : /* Not found */
800 0 :
801 0 : return sentinel;
802 0 : }
803 :
804 : FD_FN_PURE MAP_IMPL_STATIC MAP_T const *
805 : MAP_(query_const)( MAP_T const * join,
806 : MAP_KEY_T const * key,
807 1839202794 : MAP_T const * sentinel ) {
808 1839202794 : MAP_(private_t) const * map = MAP_(private_const)( join );
809 :
810 : /* Find the key */
811 :
812 1839202794 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
813 1839202794 : ulong const * head = MAP_(private_list_const)( map ) + ( hash & (map->list_cnt-1UL) );
814 1839202794 : ulong const * cur = head;
815 3197008218 : for(;;) {
816 3197008218 : ulong ele_idx = MAP_(private_unbox_idx)( *cur );
817 3197008218 : if( FD_UNLIKELY( MAP_(private_is_null)( ele_idx ) ) ) break; /* optimize for found */
818 3193936218 : MAP_T const * ele = join + ele_idx;
819 3193936218 : if(
820 : #if MAP_MEMOIZE
821 1596968109 : hash == ele->MAP_HASH &&
822 : #endif
823 2515033506 : FD_LIKELY( MAP_(key_eq)( key, &ele->MAP_KEY ) ) ) { /* Optimize for found (it is remove after all) */
824 1836130794 : return ele; /* optimize for found */
825 1836130794 : }
826 1357805424 : cur = &ele->MAP_NEXT;
827 1357805424 : }
828 :
829 : /* Not found */
830 :
831 3072000 : return sentinel;
832 1839202794 : }
833 :
834 : FD_FN_PURE MAP_IMPL_STATIC MAP_T const *
835 : MAP_(query_safe)( MAP_T const * join,
836 : MAP_KEY_T const * key,
837 0 : MAP_T const * sentinel ) {
838 0 : MAP_(private_t) const * map = MAP_(private_const)( join );
839 :
840 0 : ulong key_max = map->key_max;
841 :
842 : /* Find the key */
843 :
844 0 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
845 0 : ulong const * head = MAP_(private_list_const)( map ) + ( hash & (map->list_cnt-1UL) );
846 0 : ulong const * cur = head;
847 0 : for( ulong i = 0; i < key_max; ++i ) {
848 0 : ulong ele_idx = MAP_(private_unbox_idx)( *cur );
849 0 : if( FD_UNLIKELY( MAP_(private_is_null)( ele_idx ) || ele_idx >= key_max ) ) break; /* optimize for found */
850 0 : MAP_T const * ele = join + ele_idx;
851 0 : if(
852 : #if MAP_MEMOIZE
853 : hash == ele->MAP_HASH &&
854 : #endif
855 0 : FD_LIKELY( MAP_(key_eq)( key, &ele->MAP_KEY ) ) ) { /* Optimize for found (it is remove after all) */
856 0 : return ele; /* optimize for found */
857 0 : }
858 0 : cur = &ele->MAP_NEXT;
859 0 : }
860 :
861 : /* Not found */
862 :
863 0 : return sentinel;
864 0 : }
865 :
866 : MAP_IMPL_STATIC int
867 6144006 : MAP_(verify)( MAP_T const * join ) {
868 :
869 14472813600 : # define MAP_TEST(c) do { \
870 14472813600 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
871 14472813600 : } while(0)
872 :
873 6144006 : MAP_TEST( join );
874 :
875 6144006 : MAP_(private_t) const * map = MAP_(private_const)( join ); MAP_TEST( map!=NULL );
876 :
877 6144006 : MAP_TEST( MAP_(footprint)( map->key_max ) );
878 :
879 : /* seed can be anything as far as map is concerned */
880 :
881 6144006 : MAP_TEST( map->list_cnt==MAP_(private_list_cnt)( map->key_max ) );
882 6144006 : MAP_TEST( map->key_cnt <=map->key_max );
883 :
884 6144006 : ulong key_max = map->key_max;
885 6144006 : ulong key_cnt = map->key_cnt;
886 6144006 : ulong seed = map->seed;
887 6144006 : ulong list_cnt = map->list_cnt;
888 6144006 : ulong const * list = MAP_(private_list_const)( map ); MAP_TEST( list!=NULL );
889 :
890 6144006 : ulong free_cnt = key_max - key_cnt;
891 :
892 6144006 : ulong ele_idx;
893 6144006 : ulong cnt;
894 :
895 6144006 : cnt = 0UL;
896 1579009542 : for( ulong list_idx=0UL; list_idx<list_cnt; list_idx++ ) {
897 1572865536 : ele_idx = MAP_(private_unbox_idx)( list[ list_idx ] );
898 1572865536 : MAP_TEST( !MAP_(private_unbox_tag)( list[ list_idx ] ) ); /* Head marked as used */
899 3145729536 : while( !MAP_(private_is_null)( ele_idx ) ) {
900 1572864000 : MAP_TEST( cnt<key_cnt );
901 1572864000 : MAP_TEST( ele_idx<key_max );
902 1572864000 : MAP_T const * ele = join + ele_idx;
903 : #if MAP_MEMOIZE
904 786432000 : MAP_TEST( ele->MAP_HASH == MAP_KEY_HASH( (&ele->MAP_KEY), (map->seed) ) );
905 786432000 : #endif
906 1572864000 : MAP_TEST( MAP_(private_list_idx)( &ele->MAP_KEY, seed, list_cnt )==list_idx );
907 1572864000 : cnt++;
908 1572864000 : ele_idx = MAP_(private_unbox_idx)( ele->MAP_NEXT );
909 1572864000 : MAP_TEST( !MAP_(private_unbox_tag)( ele->MAP_NEXT ) ); /* Element marked as used */
910 1572864000 : }
911 1572865536 : }
912 :
913 6144006 : MAP_TEST( cnt==key_cnt );
914 :
915 6144006 : cnt = 0UL;
916 :
917 6144006 : ele_idx = MAP_(private_unbox_idx)( map->free_stack );
918 6144006 : MAP_TEST( MAP_(private_unbox_tag)( map->free_stack ) ); /* Head marked as free */
919 1579011078 : while( !MAP_(private_is_null)( ele_idx ) ) {
920 1572867072 : MAP_TEST( cnt<free_cnt );
921 1572867072 : MAP_TEST( ele_idx<key_max );
922 1572867072 : MAP_T const * ele = join + ele_idx;
923 1572867072 : cnt++;
924 1572867072 : ele_idx = MAP_(private_unbox_idx)( ele->MAP_NEXT );
925 1572867072 : MAP_TEST( MAP_(private_unbox_tag)( ele->MAP_NEXT ) ); /* Element marked as free */
926 1572867072 : }
927 :
928 6144006 : MAP_TEST( cnt==free_cnt );
929 :
930 1579008006 : for( ulong ele_idx=0UL; ele_idx<key_cnt; ele_idx++ ) {
931 1572864000 : if( MAP_(private_unbox_tag)( join[ele_idx].MAP_NEXT ) ) continue;
932 1048162794 : MAP_TEST( MAP_(query_const)( join, &join[ele_idx].MAP_KEY, NULL )==&join[ele_idx] );
933 1048162794 : }
934 :
935 6144006 : # undef MAP_TEST
936 :
937 6144006 : return 0;
938 6144006 : }
939 :
940 : MAP_IMPL_STATIC MAP_T *
941 : MAP_(insert)( MAP_T * join,
942 3072000 : MAP_KEY_T const * key ) {
943 : # if FD_TMPL_USE_HANDHOLDING
944 : if( FD_UNLIKELY( MAP_(key_cnt)( join )>=MAP_(key_max)( join ) ) ) FD_LOG_CRIT(( "map is full" ));
945 : # endif
946 3072000 : MAP_(private_t) * map = MAP_(private)( join );
947 :
948 : /* Pop the free stack to allocate an element (this is guaranteed to
949 : succeed as per contract) */
950 :
951 3072000 : ulong ele_idx = MAP_(private_unbox_idx)( map->free_stack );
952 3072000 : MAP_T * ele = join + ele_idx;
953 3072000 : map->free_stack = ele->MAP_NEXT; /* already tagged free */
954 3072000 : map->key_cnt++; /* Consider eliminating this to help make completely concurrent lockfree? */
955 :
956 : /* ... and map the newly allocated element to key (this is also
957 : guaranteed to not have collisions as per contract). Note that
958 : elements appear in the chain in order of newest to oldest. This
959 : property is NECESSARY for an important optimization in
960 : fd_funk_rec_query_global. */
961 :
962 3072000 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
963 3072000 : ulong * head = MAP_(private_list)( map ) + ( hash & (map->list_cnt-1UL) );
964 3072000 : MAP_(key_copy)( &ele->MAP_KEY, key );
965 3072000 : ele->MAP_NEXT = MAP_(private_box_next)( MAP_(private_unbox_idx)( *head ), 0 );
966 : # if MAP_MEMOIZE
967 1536000 : ele->MAP_HASH = hash;
968 : # endif
969 3072000 : *head = MAP_(private_box_next)( ele_idx, 0 );
970 3072000 : return ele;
971 3072000 : }
972 :
973 : MAP_IMPL_STATIC MAP_T *
974 0 : MAP_(pop_free_ele)( MAP_T * join ) {
975 0 : # if FD_TMPL_USE_HANDHOLDING
976 0 : if( FD_UNLIKELY( !MAP_(key_cnt)( join ) ) ) FD_LOG_CRIT(( "map is empty" ));
977 0 : # endif
978 0 : MAP_(private_t) * map = MAP_(private)( join );
979 0 :
980 0 : /* Pop the free stack to allocate an element (this is guaranteed to
981 0 : succeed as per contract) */
982 0 :
983 0 : ulong ele_idx = MAP_(private_unbox_idx)( map->free_stack );
984 0 : MAP_T * ele = join + ele_idx;
985 0 : map->free_stack = ele->MAP_NEXT; /* already tagged free */
986 0 : return ele;
987 0 : }
988 :
989 : MAP_IMPL_STATIC MAP_T *
990 : MAP_(push_free_ele)( MAP_T * join,
991 0 : MAP_T * ele ) {
992 0 : MAP_(private_t) * map = MAP_(private)( join );
993 0 :
994 0 : ulong ele_idx = (ulong)(ele - join);
995 0 :
996 0 : ele->MAP_NEXT = map->free_stack; /* already tagged free */
997 0 : map->free_stack = MAP_(private_box_next)( ele_idx, 1 );
998 0 : return ele;
999 0 : }
1000 :
1001 : MAP_IMPL_STATIC MAP_T *
1002 : MAP_(insert_free_ele)( MAP_T * join,
1003 : MAP_T * ele,
1004 0 : MAP_KEY_T const * key ) {
1005 0 : MAP_(private_t) * map = MAP_(private)( join );
1006 0 : /* Map the allocated element to key (this is also
1007 0 : guaranteed to not have collisions as per contract). */
1008 0 :
1009 0 : ulong ele_idx = (ulong)(ele - join);
1010 0 :
1011 0 : ulong * head = MAP_(private_list)( map ) + MAP_(private_list_idx)( key, map->seed, map->list_cnt );
1012 0 : MAP_(key_copy)( &ele->MAP_KEY, key );
1013 0 : ele->MAP_NEXT = MAP_(private_box_next)( MAP_(private_unbox_idx)( *head ), 0 );
1014 0 : *head = MAP_(private_box_next)( ele_idx, 0 );
1015 0 : return ele;
1016 0 : }
1017 :
1018 : MAP_IMPL_STATIC MAP_T *
1019 : MAP_(remove)( MAP_T * join,
1020 6144000 : MAP_KEY_T const * key ) {
1021 6144000 : MAP_(private_t) * map = MAP_(private)( join );
1022 :
1023 :
1024 : /* Find the key */
1025 :
1026 6144000 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
1027 6144000 : ulong * head = MAP_(private_list)( map ) + ( hash & (map->list_cnt-1UL) );
1028 6144000 : ulong * cur = head;
1029 9330000 : for(;;) {
1030 9330000 : ulong ele_idx = MAP_(private_unbox_idx)( *cur );
1031 9330000 : if( FD_UNLIKELY( MAP_(private_is_null)( ele_idx ) ) ) break;
1032 6258000 : MAP_T * ele = join + ele_idx;
1033 6258000 : if(
1034 : #if MAP_MEMOIZE
1035 3129000 : hash == ele->MAP_HASH &&
1036 : #endif
1037 4665000 : FD_LIKELY( MAP_(key_eq)( key, &ele->MAP_KEY ) ) ) { /* Optimize for found (it is remove after all) */
1038 : /* Found, remove the mapping and push it to free stack. */
1039 3072000 : *cur = ele->MAP_NEXT; /* already tagged empty */
1040 3072000 : ele->MAP_NEXT = map->free_stack; /* already tagged free */
1041 3072000 : map->free_stack = MAP_(private_box_next)( ele_idx, 1 );
1042 3072000 : map->key_cnt--;
1043 3072000 : return ele;
1044 3072000 : }
1045 3186000 : cur = &ele->MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
1046 3186000 : }
1047 :
1048 : /* Not found */
1049 3072000 : return NULL;
1050 6144000 : }
1051 :
1052 : #undef MAP_IMPL_STATIC
1053 :
1054 : #endif
1055 :
1056 : #undef MAP_
1057 : #undef MAP_IDX_NULL
1058 :
1059 : #undef MAP_IMPL_STYLE
1060 : #undef MAP_MAGIC
1061 : #undef MAP_KEY_COPY
1062 : #undef MAP_KEY_HASH
1063 : #undef MAP_KEY_EQ
1064 : #undef MAP_NEXT
1065 : #undef MAP_KEY
1066 : #undef MAP_KEY_T
1067 : #undef MAP_T
1068 : #undef MAP_NAME
1069 : #undef MAP_MEMOIZE
1070 : #undef MAP_HASH
|
