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 returns 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 retains 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 occuring,
157 : // this API will still return a resonable 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 : protoypes only and/or implementations if doing a library with multiple
207 : compilation units. Further, options exist to use different hashing
208 : 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 1087860000 : #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 copys 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 108792 : #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 41339742233 : #define MAP_IDX_NULL (~(1UL<<63)) /* 2^63-1 */
301 65926047053 : #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 101057085 : 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 101057085 : ulong list_min = (key_max>>1) + (key_max&1UL); /* list_min = ceil(key_max/2), at most 2^63, computed without overflow */
349 101057085 : ulong list_cnt = fd_ulong_pow2_up( list_min ); /* at most 2^63 */
350 101057085 : return list_cnt;
351 101057085 : }
352 :
353 : FD_FN_CONST static inline ulong
354 51515940 : MAP_(private_meta_footprint)( ulong list_cnt ) {
355 51515940 : return fd_ulong_align_up( (2UL + list_cnt)*sizeof(ulong) + sizeof(MAP_(private_t)), fd_ulong_max( 128UL, alignof(MAP_T) ) );
356 51515940 : }
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 2148396705 : MAP_(private)( MAP_T * join ) {
364 2148396705 : return (MAP_(private_t) *)(((ulong)join) - sizeof(MAP_(private_t)));
365 2148396705 : }
366 :
367 : FD_FN_CONST static inline MAP_(private_t) const *
368 3330584685 : MAP_(private_const)( MAP_T const * join ) {
369 3330584685 : return (MAP_(private_t) const *)(((ulong)join) - sizeof(MAP_(private_t)));
370 3330584685 : }
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 2148067386 : MAP_(private_list)( MAP_(private_t) * map ) {
378 2148067386 : return ((ulong *)map) - map->list_cnt;
379 2148067386 : }
380 :
381 : FD_FN_PURE static inline ulong const *
382 3450170085 : MAP_(private_list_const)( MAP_(private_t) const * map ) {
383 3450170085 : return ((ulong const *)map) - map->list_cnt;
384 3450170085 : }
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 2269796808 : ulong list_cnt ) {
397 2269796808 : return (MAP_KEY_HASH( (key), (seed) )) & (list_cnt-1UL);
398 2269796808 : }
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 2884311835 : FD_FN_CONST static inline ulong MAP_(private_box_next) ( ulong idx, int tag ) { return idx | (((ulong)tag)<<63); }
410 20173211173 : FD_FN_CONST static inline ulong MAP_(private_unbox_idx) ( ulong next ) { return next & MAP_IDX_NULL; }
411 25234065075 : 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 20155272439 : 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 44055123 : MAP_(key_max)( MAP_T const * join ) {
420 44055123 : if( FD_UNLIKELY( !join ) ) return 0UL;
421 44055123 : return MAP_(private_const)( join )->key_max;
422 44055123 : }
423 :
424 : FD_FN_PURE static inline ulong
425 44052822 : MAP_(seed)( MAP_T const * join ) {
426 44052822 : if( FD_UNLIKELY( !join ) ) return 0UL;
427 44052822 : return MAP_(private_const)( join )->seed;
428 44052822 : }
429 :
430 : FD_FN_PURE static inline ulong
431 78440964 : MAP_(key_cnt)( MAP_T const * join ) {
432 78440964 : if( FD_UNLIKELY( !join ) ) return 0UL;
433 78440964 : return MAP_(private_const)( join )->key_cnt;
434 78440964 : }
435 :
436 : FD_FN_PURE static inline int
437 129391905 : MAP_(is_full)( MAP_T const * join ) {
438 129391905 : if( FD_UNLIKELY( !join ) ) return 0UL;
439 129391905 : MAP_(private_t) const * map = MAP_(private_const)( join );
440 129391905 : return MAP_(private_is_null)( MAP_(private_unbox_idx)( map->free_stack ) );
441 129391905 : }
442 :
443 : FD_FN_PURE static inline int
444 : MAP_(key_eq)( MAP_KEY_T const * k0,
445 5871842319 : MAP_KEY_T const * k1 ) {
446 5871842319 : return !!(MAP_KEY_EQ( (k0), (k1) ));
447 5871842319 : }
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 18098367 : MAP_KEY_T const * ks ) {
458 18098367 : (MAP_KEY_COPY( (kd), (ks) ));
459 18098367 : return kd;
460 18098367 : }
461 :
462 : FD_FN_PURE static inline MAP_(iter_t)
463 116361198 : MAP_(iter_init)( MAP_T const * join ) {
464 116361198 : if( FD_UNLIKELY( !join ) ) return 0UL; /* Debatable */
465 116361198 : MAP_(private_t) const * map = MAP_(private_const)( join );
466 116361198 : ulong ele_rem = map->key_max;
467 5935955574 : for( ; ele_rem; ele_rem-- ) if( !MAP_(private_unbox_tag)( join[ ele_rem-1UL ].MAP_NEXT ) ) break;
468 116361198 : return ele_rem;
469 116361198 : }
470 :
471 : FD_FN_CONST static inline int
472 : MAP_(iter_done)( MAP_T const * join,
473 2925037266 : MAP_(iter_t) ele_rem ) {
474 2925037266 : (void)join;
475 2925037266 : return !ele_rem;
476 2925037266 : }
477 :
478 : FD_FN_PURE static inline MAP_(iter_t)
479 : MAP_(iter_next)( MAP_T const * join,
480 2808676068 : MAP_(iter_t) ele_rem ) {
481 6798523512 : for( ele_rem--; ele_rem; ele_rem-- ) if( !MAP_(private_unbox_tag)( join[ ele_rem-1UL ].MAP_NEXT ) ) break;
482 2808676068 : return ele_rem;
483 2808676068 : }
484 :
485 : FD_FN_CONST static inline MAP_T *
486 : MAP_(iter_ele)( MAP_T * join,
487 2808676068 : MAP_(iter_t) ele_rem ) {
488 2808676068 : return join + ele_rem - 1UL;
489 2808676068 : }
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 : FD_FN_PURE 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 23452806 : MAP_(align)( void ) {
562 23452806 : return fd_ulong_max( 128UL, alignof(MAP_T) );
563 23452806 : }
564 :
565 : FD_FN_CONST MAP_IMPL_STATIC ulong
566 50856702 : MAP_(footprint)( ulong key_max ) {
567 50856702 : 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 50856702 : ulong key_thresh = fd_ulong_min( (ULONG_MAX - 2UL*(align-1UL) - 2UL*sizeof(ulong) - sizeof(MAP_(private_t))) /
585 50856702 : (sizeof(MAP_T) + sizeof(ulong)), MAP_IDX_NULL );
586 50856702 : if( FD_UNLIKELY( key_max>key_thresh ) ) return 0UL;
587 50856690 : ulong list_cnt = MAP_(private_list_cnt) ( key_max );
588 50856690 : ulong meta_footprint = MAP_(private_meta_footprint)( list_cnt );
589 50856690 : return meta_footprint + fd_ulong_align_up( key_max*sizeof(MAP_T), align );
590 50856702 : }
591 :
592 : MAP_IMPL_STATIC void *
593 : MAP_(new)( void * shmem,
594 : ulong key_max,
595 329949 : ulong seed ) {
596 329949 : ulong * hdr = (ulong *)shmem;
597 :
598 329949 : if( FD_UNLIKELY( !hdr ) ) {
599 6 : FD_LOG_WARNING(( "NULL shmem" ));
600 6 : return NULL;
601 6 : }
602 :
603 329943 : 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 329937 : ulong footprint = MAP_(footprint)( key_max );
609 329937 : 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 329931 : ulong list_cnt = MAP_(private_list_cnt)( key_max );
617 329931 : ulong meta_footprint = MAP_(private_meta_footprint)( list_cnt );
618 :
619 329931 : MAP_T * join = (MAP_T *)( ((ulong)shmem) + meta_footprint );
620 329931 : MAP_(private_t) * map = MAP_(private)( join );
621 :
622 329931 : map->key_max = key_max;
623 329931 : map->seed = seed;
624 329931 : map->list_cnt = list_cnt;
625 329931 : map->key_cnt = 0UL;
626 :
627 : /* Init the free stack */
628 :
629 329931 : if( FD_UNLIKELY( !key_max ) ) map->free_stack = MAP_(private_box_next)( MAP_IDX_NULL, 1 );
630 329919 : else {
631 329919 : map->free_stack = MAP_(private_box_next)( 0UL, 1 );
632 1225323447 : 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 329919 : join[ key_max-1UL ].MAP_NEXT = MAP_(private_box_next)( MAP_IDX_NULL, 1 );
634 329919 : }
635 :
636 : /* Set all the lists to null */
637 :
638 329931 : ulong * list = MAP_(private_list)( map );
639 960401919 : for( ulong list_idx=0UL; list_idx<list_cnt; list_idx++ ) list[ list_idx ] = MAP_(private_box_next)( MAP_IDX_NULL, 0 );
640 :
641 329931 : hdr[1] = meta_footprint;
642 :
643 329931 : FD_COMPILER_MFENCE();
644 329931 : FD_VOLATILE( hdr[0] ) = MAP_MAGIC;
645 329931 : FD_COMPILER_MFENCE();
646 :
647 329931 : return hdr;
648 329937 : }
649 :
650 : MAP_IMPL_STATIC MAP_T *
651 329949 : MAP_(join)( void * shmap ) {
652 329949 : ulong * hdr = (ulong *)shmap;
653 :
654 329949 : if( FD_UNLIKELY( !hdr ) ) {
655 6 : FD_LOG_WARNING(( "NULL shmap" ));
656 6 : return NULL;
657 6 : }
658 :
659 329943 : 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 329937 : if( FD_UNLIKELY( hdr[0]!=MAP_MAGIC ) ) {
665 6 : FD_LOG_WARNING(( "bad magic" ));
666 6 : return NULL;
667 6 : }
668 :
669 329931 : return (MAP_T *)(((ulong)shmap) + hdr[1]);
670 329937 : }
671 :
672 : MAP_IMPL_STATIC void *
673 329325 : MAP_(leave)( MAP_T * join ) {
674 :
675 329325 : if( FD_UNLIKELY( !join ) ) {
676 6 : FD_LOG_WARNING(( "NULL join" ));
677 6 : return NULL;
678 6 : }
679 :
680 329319 : return (void *)(((ulong)join) - MAP_(private_meta_footprint)( MAP_(private)( join )->list_cnt ));
681 329325 : }
682 :
683 : MAP_IMPL_STATIC void *
684 329337 : MAP_(delete)( void * shmap ) {
685 329337 : ulong * hdr = (ulong *)shmap;
686 :
687 329337 : if( FD_UNLIKELY( !hdr ) ) {
688 6 : FD_LOG_WARNING(( "NULL shmap" ));
689 6 : return NULL;
690 6 : }
691 :
692 329331 : 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 329325 : if( FD_UNLIKELY( hdr[0]!=MAP_MAGIC ) ) {
698 6 : FD_LOG_WARNING(( "bad magic" ));
699 6 : return NULL;
700 6 : }
701 :
702 329319 : FD_COMPILER_MFENCE();
703 329319 : FD_VOLATILE( hdr[0] ) = 0UL;
704 329319 : FD_COMPILER_MFENCE();
705 :
706 329319 : return shmap;
707 329325 : }
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 : MAP_IMPL_STATIC MAP_T *
737 : MAP_(insert)( MAP_T * join,
738 12098367 : MAP_KEY_T const * key ) {
739 12098367 : MAP_(private_t) * map = MAP_(private)( join );
740 :
741 : /* Pop the free stack to allocate an element (this is guaranteed to
742 : succeed as per contract) */
743 :
744 12098367 : ulong ele_idx = MAP_(private_unbox_idx)( map->free_stack );
745 12098367 : MAP_T * ele = join + ele_idx;
746 12098367 : map->free_stack = ele->MAP_NEXT; /* already tagged free */
747 12098367 : map->key_cnt++; /* Consider eliminating this to help make completely concurrent lockfree? */
748 :
749 : /* ... and map the newly allocated element to key (this is also
750 : guaranteed to not have collisions as per contract). */
751 :
752 12098367 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
753 12098367 : ulong * head = MAP_(private_list)( map ) + ( hash & (map->list_cnt-1UL) );
754 12098367 : MAP_(key_copy)( &ele->MAP_KEY, key );
755 12098367 : ele->MAP_NEXT = MAP_(private_box_next)( MAP_(private_unbox_idx)( *head ), 0 );
756 : #if MAP_MEMOIZE
757 10562367 : ele->MAP_HASH = hash;
758 : #endif
759 12098367 : *head = MAP_(private_box_next)( ele_idx, 0 );
760 :
761 12098367 : return ele;
762 12098367 : }
763 :
764 : MAP_IMPL_STATIC MAP_T *
765 0 : MAP_(pop_free_ele)( MAP_T * join ) {
766 0 : MAP_(private_t) * map = MAP_(private)( join );
767 :
768 : /* Pop the free stack to allocate an element (this is guaranteed to
769 : succeed as per contract) */
770 :
771 0 : ulong ele_idx = MAP_(private_unbox_idx)( map->free_stack );
772 0 : MAP_T * ele = join + ele_idx;
773 0 : map->free_stack = ele->MAP_NEXT; /* already tagged free */
774 :
775 0 : return ele;
776 0 : }
777 :
778 : MAP_IMPL_STATIC MAP_T *
779 : MAP_(push_free_ele)( MAP_T * join,
780 0 : MAP_T * ele ) {
781 0 : MAP_(private_t) * map = MAP_(private)( join );
782 :
783 0 : ulong ele_idx = (ulong)(ele - join);
784 :
785 0 : ele->MAP_NEXT = map->free_stack; /* already tagged free */
786 0 : map->free_stack = MAP_(private_box_next)( ele_idx, 1 );
787 :
788 0 : return ele;
789 0 : }
790 :
791 : MAP_IMPL_STATIC MAP_T *
792 : MAP_(insert_free_ele)( MAP_T * join,
793 : MAP_T * ele,
794 0 : MAP_KEY_T const * key ) {
795 0 : MAP_(private_t) * map = MAP_(private)( join );
796 : /* Map the allocated element to key (this is also
797 : guaranteed to not have collisions as per contract). */
798 :
799 0 : ulong ele_idx = (ulong)(ele - join);
800 :
801 0 : ulong * head = MAP_(private_list)( map ) + MAP_(private_list_idx)( key, map->seed, map->list_cnt );
802 0 : MAP_(key_copy)( &ele->MAP_KEY, key );
803 0 : ele->MAP_NEXT = MAP_(private_box_next)( MAP_(private_unbox_idx)( *head ), 0 );
804 0 : *head = MAP_(private_box_next)( ele_idx, 0 );
805 :
806 0 : return ele;
807 0 : }
808 :
809 : MAP_IMPL_STATIC MAP_T *
810 : MAP_(remove)( MAP_T * join,
811 15161649 : MAP_KEY_T const * key ) {
812 15161649 : MAP_(private_t) * map = MAP_(private)( join );
813 :
814 :
815 : /* Find the key */
816 :
817 15161649 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
818 15161649 : ulong * head = MAP_(private_list)( map ) + ( hash & (map->list_cnt-1UL) );
819 15161649 : ulong * cur = head;
820 19110995 : for(;;) {
821 19110995 : ulong ele_idx = MAP_(private_unbox_idx)( *cur );
822 19110995 : if( FD_UNLIKELY( MAP_(private_is_null)( ele_idx ) ) ) break;
823 16038995 : MAP_T * ele = join + ele_idx;
824 16038995 : if(
825 : #if MAP_MEMOIZE
826 12909995 : hash == ele->MAP_HASH &&
827 : #endif
828 13683345 : FD_LIKELY( MAP_(key_eq)( key, &ele->MAP_KEY ) ) ) { /* Optimize for found (it is remove after all) */
829 : /* Found, remove the mapping and push it to free stack. */
830 12089649 : *cur = ele->MAP_NEXT; /* already tagged empty */
831 12089649 : ele->MAP_NEXT = map->free_stack; /* already tagged free */
832 12089649 : map->free_stack = MAP_(private_box_next)( ele_idx, 1 );
833 12089649 : map->key_cnt--;
834 12089649 : return ele;
835 12089649 : }
836 3949346 : cur = &ele->MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
837 3949346 : }
838 :
839 : /* Not found */
840 :
841 3072000 : return NULL;
842 15161649 : }
843 :
844 : FD_FN_PURE MAP_IMPL_STATIC MAP_T *
845 : MAP_(query)( MAP_T * join,
846 : MAP_KEY_T const * key,
847 2120477439 : MAP_T * sentinel ) {
848 2120477439 : MAP_(private_t) * map = MAP_(private)( join );
849 :
850 :
851 : /* Find the key */
852 :
853 2120477439 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
854 2120477439 : ulong * head = MAP_(private_list)( map ) + ( hash & (map->list_cnt-1UL) );
855 2120477439 : ulong * cur = head;
856 3943346307 : for(;;) {
857 3943346307 : ulong ele_idx = MAP_(private_unbox_idx)( *cur );
858 3943346307 : if( FD_UNLIKELY( MAP_(private_is_null)( ele_idx ) ) ) break; /* optimize for found */
859 2949619560 : MAP_T * ele = join + ele_idx;
860 2949619560 : if(
861 : #if MAP_MEMOIZE
862 1738479420 : hash == ele->MAP_HASH &&
863 : #endif
864 1943907555 : FD_LIKELY( MAP_(key_eq)( key, &ele->MAP_KEY ) ) ) { /* Optimize for found (it is remove after all) */
865 : /* Found, move it to the front of the chain. (FIXME: BRANCH PROB? DO BRANCHLESS?) */
866 1126750692 : if( FD_UNLIKELY( cur!=head ) ) { /* Assume already at head from previous query */
867 662300086 : *cur = ele->MAP_NEXT; /* Already tagged free */
868 662300086 : ele->MAP_NEXT = *head; /* Already tagged free */
869 662300086 : *head = MAP_(private_box_next)( ele_idx, 0 );
870 662300086 : }
871 1126750692 : return ele;
872 1126750692 : }
873 1822868868 : cur = &ele->MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
874 1822868868 : }
875 :
876 : /* Not found */
877 :
878 993726747 : return sentinel;
879 2120477439 : }
880 :
881 : FD_FN_PURE MAP_IMPL_STATIC MAP_T *
882 : MAP_(query2)( MAP_T * join,
883 : MAP_KEY_T const * key,
884 0 : MAP_T * sentinel ) {
885 0 : MAP_(private_t) * map = MAP_(private)( join );
886 :
887 :
888 : /* Find the key */
889 :
890 0 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
891 0 : ulong * head = MAP_(private_list)( map ) + ( hash & (map->list_cnt-1UL) );
892 0 : ulong * cur = head;
893 0 : for(;;) {
894 0 : ulong ele_idx = MAP_(private_unbox_idx)( *cur );
895 0 : if( FD_UNLIKELY( MAP_(private_is_null)( ele_idx ) ) ) break; /* optimize for found */
896 0 : MAP_T * ele = join + ele_idx;
897 0 : if(
898 0 : #if MAP_MEMOIZE
899 0 : hash == ele->MAP_HASH &&
900 0 : #endif
901 0 : FD_LIKELY( MAP_(key_eq)( key, &ele->MAP_KEY ) ) ) { /* Optimize for found (it is remove after all) */
902 0 : return ele; /* optimize for found */
903 0 : }
904 0 : cur = &ele->MAP_NEXT;
905 0 : }
906 :
907 : /* Not found */
908 :
909 0 : return sentinel;
910 0 : }
911 :
912 : FD_FN_PURE MAP_IMPL_STATIC MAP_T const *
913 : MAP_(query_const)( MAP_T const * join,
914 : MAP_KEY_T const * key,
915 3399973263 : MAP_T const * sentinel ) {
916 3399973263 : MAP_(private_t) const * map = MAP_(private_const)( join );
917 :
918 : /* Find the key */
919 :
920 3399973263 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
921 3399973263 : ulong const * head = MAP_(private_list_const)( map ) + ( hash & (map->list_cnt-1UL) );
922 3399973263 : ulong const * cur = head;
923 5837548202 : for(;;) {
924 5837548202 : ulong ele_idx = MAP_(private_unbox_idx)( *cur );
925 5837548202 : if( FD_UNLIKELY( MAP_(private_is_null)( ele_idx ) ) ) break; /* optimize for found */
926 5648921099 : MAP_T const * ele = join + ele_idx;
927 5648921099 : if(
928 : #if MAP_MEMOIZE
929 4051952990 : hash == ele->MAP_HASH &&
930 : #endif
931 4051952990 : FD_LIKELY( MAP_(key_eq)( key, &ele->MAP_KEY ) ) ) { /* Optimize for found (it is remove after all) */
932 3211346160 : return ele; /* optimize for found */
933 3211346160 : }
934 2437574939 : cur = &ele->MAP_NEXT;
935 2437574939 : }
936 :
937 : /* Not found */
938 :
939 188627103 : return sentinel;
940 3399973263 : }
941 :
942 : FD_FN_PURE MAP_IMPL_STATIC MAP_T const *
943 : MAP_(query_safe)( MAP_T const * join,
944 : MAP_KEY_T const * key,
945 0 : MAP_T const * sentinel ) {
946 0 : MAP_(private_t) const * map = MAP_(private_const)( join );
947 :
948 0 : ulong key_max = map->key_max;
949 :
950 : /* Find the key */
951 :
952 0 : ulong hash = MAP_KEY_HASH( (key), (map->seed) );
953 0 : ulong const * head = MAP_(private_list_const)( map ) + ( hash & (map->list_cnt-1UL) );
954 0 : ulong const * cur = head;
955 0 : for( ulong i = 0; i < key_max; ++i ) {
956 0 : ulong ele_idx = MAP_(private_unbox_idx)( *cur );
957 0 : if( FD_UNLIKELY( MAP_(private_is_null)( ele_idx ) || ele_idx >= key_max ) ) break; /* optimize for found */
958 0 : MAP_T const * ele = join + ele_idx;
959 0 : if(
960 : #if MAP_MEMOIZE
961 0 : hash == ele->MAP_HASH &&
962 : #endif
963 0 : FD_LIKELY( MAP_(key_eq)( key, &ele->MAP_KEY ) ) ) { /* Optimize for found (it is remove after all) */
964 0 : return ele; /* optimize for found */
965 0 : }
966 0 : cur = &ele->MAP_NEXT;
967 0 : }
968 :
969 : /* Not found */
970 :
971 0 : return sentinel;
972 0 : }
973 :
974 : FD_FN_PURE MAP_IMPL_STATIC int
975 50196822 : MAP_(verify)( MAP_T const * join ) {
976 :
977 29368820724 : # define MAP_TEST(c) do { \
978 29368820724 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
979 29368820724 : } while(0)
980 :
981 50196822 : MAP_TEST( join );
982 :
983 50196822 : MAP_(private_t) const * map = MAP_(private_const)( join ); MAP_TEST( map!=NULL );
984 :
985 50196822 : MAP_TEST( MAP_(footprint)( map->key_max ) );
986 :
987 : /* seed can be anything as far as map is concerned */
988 :
989 50196822 : MAP_TEST( map->list_cnt==MAP_(private_list_cnt)( map->key_max ) );
990 50196822 : MAP_TEST( map->key_cnt <=map->key_max );
991 :
992 50196822 : ulong key_max = map->key_max;
993 50196822 : ulong key_cnt = map->key_cnt;
994 50196822 : ulong seed = map->seed;
995 50196822 : ulong list_cnt = map->list_cnt;
996 50196822 : ulong const * list = MAP_(private_list_const)( map ); MAP_TEST( list!=NULL );
997 :
998 50196822 : ulong free_cnt = key_max - key_cnt;
999 :
1000 50196822 : ulong ele_idx;
1001 50196822 : ulong cnt;
1002 :
1003 50196822 : cnt = 0UL;
1004 3442089558 : for( ulong list_idx=0UL; list_idx<list_cnt; list_idx++ ) {
1005 3391892736 : ele_idx = MAP_(private_unbox_idx)( list[ list_idx ] );
1006 3391892736 : MAP_TEST( !MAP_(private_unbox_tag)( list[ list_idx ] ) ); /* Head marked as used */
1007 5661689544 : while( !MAP_(private_is_null)( ele_idx ) ) {
1008 2269796808 : MAP_TEST( cnt<key_cnt );
1009 2269796808 : MAP_TEST( ele_idx<key_max );
1010 2269796808 : MAP_T const * ele = join + ele_idx;
1011 : #if MAP_MEMOIZE
1012 1483364808 : MAP_TEST( ele->MAP_HASH == MAP_KEY_HASH( (&ele->MAP_KEY), (map->seed) ) );
1013 1483364808 : #endif
1014 2269796808 : MAP_TEST( MAP_(private_list_idx)( &ele->MAP_KEY, seed, list_cnt )==list_idx );
1015 2269796808 : cnt++;
1016 2269796808 : ele_idx = MAP_(private_unbox_idx)( ele->MAP_NEXT );
1017 2269796808 : MAP_TEST( !MAP_(private_unbox_tag)( ele->MAP_NEXT ) ); /* Element marked as used */
1018 2269796808 : }
1019 3391892736 : }
1020 :
1021 50196822 : MAP_TEST( cnt==key_cnt );
1022 :
1023 50196822 : cnt = 0UL;
1024 :
1025 50196822 : ele_idx = MAP_(private_unbox_idx)( map->free_stack );
1026 50196822 : MAP_TEST( MAP_(private_unbox_tag)( map->free_stack ) ); /* Head marked as free */
1027 4564185486 : while( !MAP_(private_is_null)( ele_idx ) ) {
1028 4513988664 : MAP_TEST( cnt<free_cnt );
1029 4513988664 : MAP_TEST( ele_idx<key_max );
1030 4513988664 : MAP_T const * ele = join + ele_idx;
1031 4513988664 : cnt++;
1032 4513988664 : ele_idx = MAP_(private_unbox_idx)( ele->MAP_NEXT );
1033 4513988664 : MAP_TEST( MAP_(private_unbox_tag)( ele->MAP_NEXT ) ); /* Element marked as free */
1034 4513988664 : }
1035 :
1036 50196822 : MAP_TEST( cnt==free_cnt );
1037 :
1038 2319993630 : for( ulong ele_idx=0UL; ele_idx<key_cnt; ele_idx++ ) {
1039 2269796808 : if( MAP_(private_unbox_tag)( join[ele_idx].MAP_NEXT ) ) continue;
1040 1420638558 : MAP_TEST( MAP_(query_const)( join, &join[ele_idx].MAP_KEY, NULL )==&join[ele_idx] );
1041 1420638558 : }
1042 :
1043 50196822 : # undef MAP_TEST
1044 :
1045 50196822 : return 0;
1046 50196822 : }
1047 :
1048 : #undef MAP_IMPL_STATIC
1049 :
1050 : #endif
1051 :
1052 : #undef MAP_
1053 : #undef MAP_IDX_NULL
1054 :
1055 : #undef MAP_IMPL_STYLE
1056 : #undef MAP_MAGIC
1057 : #undef MAP_KEY_COPY
1058 : #undef MAP_KEY_HASH
1059 : #undef MAP_KEY_EQ
1060 : #undef MAP_NEXT
1061 : #undef MAP_KEY
1062 : #undef MAP_KEY_T
1063 : #undef MAP_T
1064 : #undef MAP_NAME
1065 : #undef MAP_MEMOIZE
1066 : #undef MAP_HASH
|
