Line data Source code
1 : /* Declare ultra high performance dynamic key-val maps of bounded
2 : run time size. Typical usage:
3 :
4 : struct mymap {
5 : ulong key; // Technically "MAP_KEY_T MAP_KEY;" (default is ulong key)
6 : uint hash; // Technically "MAP_HASH_T MAP_HASH;" (default is uint hash), ==mymap_hash(key)
7 : ... key and hash can be located arbitrarily in struct
8 : ... hash is not required if MAP_MEMOIZE is zero
9 : ... the rest of the struct is POD state/values associated with key
10 : ... the mapping of a key to a map slot is arbitrary and might
11 : ... change over the lifetime of the key
12 : };
13 :
14 : typedef struct mymap mymap_t;
15 :
16 : #define MAP_NAME mymap
17 : #define MAP_T mymap_t
18 : #include "util/tmpl/fd_map_dynamic.c"
19 :
20 : will declare the following static inline APIs as a header only style
21 : library in the compilation unit:
22 :
23 : // align/footprint - Return the alignment/footprint required for a
24 : // memory region to be used as mymap sufficient to hold up to
25 : // (2^lg_slot_cnt)-1 keys. Assumes non-negative lg_slot_cnt.
26 : //
27 : // new - Format a memory region pointed to by shmem into a mymap.
28 : // Assumes shmem points to a region with the required alignment and
29 : // footprint not in use by anything else. Caller is not joined on
30 : // return. Returns shmem.
31 : //
32 : // join - Join a mymap. Assumes shmap points at a region formatted
33 : // as a mymap. Returns a handle of the callers join (will be
34 : // pointer to an array indexed [0,2^lg_slot_cnt) of mymap_t slots).
35 : // THIS IS NOT JUST A SIMPLE CAST OF SHMAP.
36 : //
37 : // leave - Leave a mymap. Assumes mymap points to a current join.
38 : // Returns a pointer to the shared memory region the join. THIS IS
39 : // NOT JUST A SIMPLE CAST OF MAP.
40 : //
41 : // delete - Unformat a memory region used as a mymap. Assumes
42 : // shmymap points to a formatted region with no current joins.
43 : // Returns a pointer to the unformatted memory region.
44 :
45 : ulong mymap_align ( void );
46 : ulong mymap_footprint( int lg_slot_cnt );
47 : void * mymap_new ( void * shmem, int lg_slot_cnt, ulong seed );
48 : mymap_t * mymap_join ( void * shmap ); // Indexed [0,2^lg_slot_cnt)
49 : void * mymap_leave ( mymap_t * map );
50 : void * mymap_delete ( void * shmap );
51 :
52 : // Return the current/maximum number of keys that can be inserted
53 : // into a mymap. The mymap will become increasingly inefficient the
54 : // more keys there are. Recommend not using more than around half
55 : // this value.
56 :
57 : ulong mymap_key_cnt( mymap_t const * map ); // In [0,key_max]
58 : ulong mymap_key_max( mymap_t const * map ); // == 2^lg_slot_cnt - 1
59 :
60 : // Return the log2 number of slots / number of slots in a mymap.
61 : // This is to facilitate iterating / listing all contents of a mymap
62 : // (this process is not algorithmically ideal for a sparse mymap).
63 : // E.g. mymap[slot_idx].key for slot_idx in [0,mymap_slot_cnt()]
64 : // when key!=0 is the set of all current key-vals in the mymap.
65 :
66 : int mymap_lg_slot_cnt( mymap_t const * map ); // Non-negative
67 : ulong mymap_slot_cnt ( mymap_t const * map ); // == 2^lg_slot_cnt
68 :
69 : // Return the hash map seed value used to construct the map.
70 :
71 : ulong mymap_seed( mymap_t const * map );
72 :
73 : // Returns the index of the slot (allows communicating locations of
74 : // map entries between users of mymap in different address spaces).
75 : // Might imply a division (probably via magic multiply) if
76 : // sizeof(mymap_t) is not a power of two (as such, power-of-2
77 : // sizeof(mymap_t) have good Feng Shui). Assumes that mymap is a
78 : // current join and slot points to a slot in that join.
79 :
80 : ulong mymap_slot_idx( mymap_t const * map, mymap_t const * slot );
81 :
82 : // Returns the "null" key, which is the canonical key that will
83 : // never be inserted (typically zero).
84 :
85 : ulong mymap_key_null( void ); // == MAP_KEY_NULL
86 :
87 : // Return the 1/0 if key is a key that will never/might be inserted.
88 :
89 : int mymap_key_inval( ulong key );
90 :
91 : // Return the 1/0 if k0 and k1 are keys that are the same
92 :
93 : int mymap_key_equal( ulong k0, ulong k1 );
94 :
95 : // Return the hash of key using the hash function seed. Should
96 : // ideally be a random mapping from MAP_KEY_T -> MAP_HASH_T. The
97 : // seed used by a particular instance of a map can be obtained
98 : // above.
99 :
100 : uint mymap_key_hash( ulong key, ulong seed );
101 :
102 : // Insert key into the map, fast O(1). Returns a pointer to the map
103 : // entry with key on success and NULL on failure (i.e. key is
104 : // already in the map or there are too many keys in the map to
105 : // insert this key). The returned pointer lifetime is until _any_
106 : // map remove or map leave. The caller should not change the values
107 : // in map_key or map_hash but is free to modify other fields in the
108 : // entry on return. Assumes map is a current join and key is value
109 : // that can be inserted.
110 :
111 : mymap_t * mymap_insert( mymap_t * map, ulong key );
112 :
113 : // Remove entry from map, fast O(1). Assumes map is a current join
114 : // and that entry points to a full entry currently in the map.
115 : // Removal performance very slightly more optimal if sizeof(mymap_t)
116 : // is a power of two.
117 :
118 : void mymap_remove( mymap_t * map, mymap_t * entry );
119 :
120 : // Remove all entries from the map. O(map size).
121 :
122 : void mymap_clear( mymap_t * map );
123 :
124 : // Query map for key, fast O(1). Returns a pointer to the map slot
125 : // holding key or null if key not in map. The returned pointer
126 : // lifetime is until the next map remove or map leave. The caller
127 : // should not change key or hash but is free to modify other fields
128 : // in the entry. Assumes map is a current join and that key is
129 : // non-zero.
130 :
131 : mymap_t * mymap_query( mymap_t * map, ulong key, mymap_t * null );
132 :
133 : You can do this as often as you like in a compilation unit to get
134 : different types of maps. Since it is all static inline, it is fine
135 : to do this in a header too. Further, options exist to use different
136 : hashing functions, variable length keys, etc as detailed below.
137 :
138 : For use with non-POD C++ structs, map_new assumes that a slot can be
139 : initialized to empty by assigning its key to MAP_KEY_NULL. Map insert
140 : will use MAP_KEY_MOVE to move the user provided key into the slot key
141 : value. Map remove will MAP_MOVE slots as necessary to preserve their
142 : probe sequences and assumes the user has already cleaned up the entry
143 : to remove enough so that all that needs to be done to eliminate the
144 : entry from the map is assign the entry's key to MAP_KEY_NULL.
145 :
146 : mymap_t * slot = mymap_insert( map, cxx_key );
147 : if( FD_UNLIKELY( !slot ) ) ... handle failure (cxx_key was not moved)
148 : else {
149 : ... mymap_insert did a MAP_KEY_MOVE of cxx_key into slot->key
150 : ... clean cxx_key's shell here as necessary here
151 : ... initialize other slot fields as necessary
152 : }
153 :
154 : and on removal:
155 :
156 : ... clean up other slot fields as necessary
157 : ... clean up slot->key as necessary
158 : mymap_remove( map, slot );
159 : ... the mapping of keys to map slots might have been changed by the
160 : ... mymap_remove. Any motion of slots was done via:
161 : ... MAP_MOVE( dst_slot, src_slot ) */
162 :
163 : #include "../bits/fd_bits.h"
164 : #include <stddef.h>
165 :
166 : #ifndef offsetof
167 : # define offsetof(TYPE,MEMB) ((ulong)((TYPE*)0)->MEMB)
168 : #endif
169 :
170 : #ifndef MAP_NAME
171 : #error "Define MAP_NAME"
172 : #endif
173 :
174 : /* A MAP_T should be something reasonable to shallow copy with
175 : the fields described above. */
176 :
177 : #ifndef MAP_T
178 : #error "Define MAP_T struct"
179 : #endif
180 :
181 : /* MAP_HASH_T should be an unsigned integral type. */
182 :
183 : #ifndef MAP_HASH_T
184 597881532 : #define MAP_HASH_T uint
185 : #endif
186 :
187 : /* MAP_HASH is the MAP_T hash field name. Defaults to hash. */
188 :
189 : #ifndef MAP_HASH
190 25363695 : #define MAP_HASH hash
191 : #endif
192 :
193 : /* MAP_KEY_T should be something reasonable to pass to a static inline
194 : by value, assign to MAP_KEY_NULL, compare for equality and copy.
195 : E.g. a uint, ulong, __m128i, etc. */
196 :
197 : #ifndef MAP_KEY_T
198 464162922 : #define MAP_KEY_T ulong
199 : #else
200 : #if !defined(MAP_KEY_NULL) || !defined(MAP_KEY_INVAL) || !defined(MAP_KEY_EQUAL) || !defined(MAP_KEY_EQUAL_IS_SLOW) || !defined(MAP_KEY_HASH)
201 : #error "Define MAP_KEY_NULL, MAP_KEY_INVAL, MAP_KEY_EQUAL, MAP_KEY_EQUAL_IS_SLOW, and MAP_KEY_HASH if using a custom MAP_KEY_T"
202 : #endif
203 : #endif
204 :
205 : /* MAP_KEY is the MAP_T key field name. Defaults to key. */
206 :
207 : #ifndef MAP_KEY
208 5189448726 : #define MAP_KEY key
209 : #endif
210 :
211 : /* MAP_KEY_NULL is a key that will never be inserted. */
212 :
213 : #ifndef MAP_KEY_NULL
214 3989215 : #define MAP_KEY_NULL 0UL
215 : #endif
216 :
217 : /* MAP_KEY_INVAL returns 1 if k0 is key that will never be inserted
218 : and zero otherwise. Note that MAP_KEY_INVAL( MAP_KEY_NULL ) should
219 : be true. This should be generally fast. */
220 :
221 : #ifndef MAP_KEY_INVAL
222 377753471 : #define MAP_KEY_INVAL(k) !(k)
223 : #endif
224 :
225 : /* MAP_KEY_EQUAL returns 0/1 if k0 is the same/different */
226 :
227 : #ifndef MAP_KEY_EQUAL
228 456810592 : #define MAP_KEY_EQUAL(k0,k1) (k0)==(k1)
229 : #endif
230 :
231 : /* If MAP_KEY_EQUAL_IS_SLOW is slow (e.g. variable length string
232 : compare, large buffer compares, etc), set MAP_KEY_EQUAL_IS_SLOW to
233 : non-zero. Then, if MAP_MEMOIZE (below) is set, precomputed key hashes
234 : will be used accelerate key insert and key query. */
235 :
236 : #ifndef MAP_KEY_EQUAL_IS_SLOW
237 : #define MAP_KEY_EQUAL_IS_SLOW 0
238 : #endif
239 :
240 : /* MAP_KEY_HASH takes a key and maps it into MAP_HASH_T uniform pseudo
241 : randomly. */
242 :
243 : #ifndef MAP_KEY_HASH
244 178068087 : #define MAP_KEY_HASH(key,seed) ((MAP_HASH_T)fd_ulong_hash( (key) ^ (seed) ))
245 : #endif
246 :
247 : /* MAP_KEY_MOVE moves the contents from src to dst. Non-POD key types
248 : need to customize this accordingly (and handle the case of
249 : ks==MAP_KEY_NULL). Defaults to shallow copy. */
250 :
251 : #ifndef MAP_KEY_MOVE
252 284219391 : #define MAP_KEY_MOVE(kd,ks) (kd)=(ks)
253 : #endif
254 :
255 : /* MAP_MOVE moves the contents of a MAP_T from src to dst. Non-POD key
256 : types need to customize this accordingly. Defaults to shallow copy. */
257 :
258 : #ifndef MAP_MOVE
259 3171821 : #define MAP_MOVE(d,s) (d)=(s)
260 : #endif
261 :
262 : /* If MAP_MEMOIZE is defined to non-zero, the MAP_T requires a
263 : "map_hash" field that will hold the value of the MAP_KEY_HASH of the
264 : MAP_T's MAP_KEY when the map slot is not empty (undefined otherwise).
265 : This is useful for accelerating user operations that might need a
266 : hash of the key and for accelerating remove operations. It is also
267 : potentially useful as a way to accelerate slow key comparison
268 : operations (see MAP_KEY_EQUAL_IS_SLOW). */
269 :
270 : #ifndef MAP_MEMOIZE
271 : #define MAP_MEMOIZE 1
272 : #endif
273 :
274 : /* MAP_QUERY_OPT allows the user to specify how the map query function
275 : should be optimized.
276 : 0 -> optimize for low fill ratio
277 : 1 -> optimize for low fill ratio and extremely rare query failure
278 : 2 -> optimize for low fill ratio and extremely rare query success */
279 :
280 : #ifndef MAP_QUERY_OPT
281 : #define MAP_QUERY_OPT 0
282 : #endif
283 :
284 : #if FD_TMPL_USE_HANDHOLDING
285 : #include "../log/fd_log.h"
286 : #endif
287 :
288 : /* Implementation *****************************************************/
289 :
290 9950026512 : #define MAP_(n) FD_EXPAND_THEN_CONCAT3(MAP_NAME,_,n)
291 :
292 : struct MAP_(private) {
293 : ulong key_cnt; /* == number of keys currently in map */
294 : ulong seed; /* Hash seed, arbitrary */
295 : ulong slot_mask; /* == key_max == 2^lg_slot_cnt - 1 */
296 : int lg_slot_cnt; /* non-negative */
297 : MAP_T slot[]; /* Actually 2^lg_slot_cnt in size */
298 : };
299 :
300 : typedef struct MAP_(private) MAP_(private_t);
301 :
302 : FD_PROTOTYPES_BEGIN
303 :
304 : /* Private APIs *******************************************************/
305 :
306 : /* private_from_slot return a pointer to the map_private given a pointer
307 : to the map's slot. private_from_map_const also provided for
308 : const-correctness purposes. */
309 :
310 : FD_FN_CONST static inline MAP_(private_t) *
311 639816524 : MAP_(private_from_slot)( MAP_T * slot ) {
312 639816524 : ulong slot_ofs = offsetof( MAP_(private_t), slot );
313 639816524 : return (MAP_(private_t) *)( (ulong)slot - (ulong)slot_ofs );
314 639816524 : }
315 :
316 : FD_FN_CONST static inline MAP_(private_t) const *
317 1614742053 : MAP_(private_from_slot_const)( MAP_T const * slot ) {
318 1614742053 : ulong slot_ofs = offsetof( MAP_(private_t), slot );
319 1614742053 : return (MAP_(private_t) const *)( (ulong)slot - (ulong)slot_ofs );
320 1614742053 : }
321 :
322 : /* Get the linear probing starting slot for a key and the slot to probe
323 : after a given slot */
324 :
325 597881532 : FD_FN_CONST static inline ulong MAP_(private_start)( MAP_HASH_T hash, ulong slot_mask ) { return (ulong)(hash & (MAP_HASH_T)slot_mask); }
326 3015990633 : FD_FN_CONST static inline ulong MAP_(private_next) ( ulong slot, ulong slot_mask ) { return (++slot) & slot_mask; }
327 :
328 : /* Public APIS ********************************************************/
329 :
330 1232004 : FD_FN_CONST static inline ulong MAP_(align)( void ) { return alignof(MAP_(private_t)); }
331 :
332 : FD_FN_CONST static inline ulong
333 454632 : MAP_(footprint)( int lg_slot_cnt ) {
334 454632 : ulong slot_cnt = 1UL << lg_slot_cnt;
335 454632 : return fd_ulong_align_up( fd_ulong_align_up( sizeof(MAP_(private_t)), alignof(MAP_T) ) + sizeof(MAP_T)*slot_cnt, alignof(MAP_(private_t)) );
336 454632 : }
337 :
338 : static inline void *
339 : MAP_(new)( void * shmem,
340 : int lg_slot_cnt,
341 320277 : ulong seed ) {
342 : # if FD_TMPL_USE_HANDHOLDING
343 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, MAP_(align)() ) ) ) FD_LOG_CRIT(( "unaligned shmem" ));
344 : if( FD_UNLIKELY( (lg_slot_cnt<0) | (lg_slot_cnt>63) ) ) FD_LOG_CRIT(( "invalid lg_slot_cnt" ));
345 : # endif
346 320277 : ulong slot_cnt = 1UL<<lg_slot_cnt;
347 320277 : ulong slot_mask = slot_cnt - 1UL;
348 320277 : MAP_(private_t) * map = (MAP_(private_t) *)shmem;
349 :
350 320277 : map->key_cnt = 0UL;
351 320277 : map->seed = seed;
352 320277 : map->slot_mask = slot_mask;
353 320277 : map->lg_slot_cnt = lg_slot_cnt;
354 :
355 320277 : MAP_T * slot = map->slot; FD_COMPILER_FORGET( slot );
356 :
357 1975807287 : for( ulong slot_idx=0UL; slot_idx<slot_cnt; slot_idx++ )
358 1975487010 : slot[ slot_idx ].MAP_KEY = (MAP_KEY_NULL);
359 :
360 320277 : return map;
361 320277 : }
362 :
363 : static inline MAP_T *
364 322041 : MAP_(join)( void * shmap ) {
365 322041 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
366 322041 : MAP_T * slot = map->slot; FD_COMPILER_FORGET( slot );
367 322041 : return slot;
368 322041 : }
369 :
370 318261 : static inline void * MAP_(leave) ( MAP_T * slot ) { return (void *)MAP_(private_from_slot)( slot ); }
371 316509 : static inline void * MAP_(delete)( void * shmap ) { return shmap; }
372 :
373 626088 : FD_FN_PURE static inline ulong MAP_(key_cnt) ( MAP_T const * slot ) { return MAP_(private_from_slot_const)( slot )->key_cnt; }
374 12 : FD_FN_PURE static inline ulong MAP_(key_max) ( MAP_T const * slot ) { return MAP_(private_from_slot_const)( slot )->slot_mask; }
375 441 : FD_FN_PURE static inline int MAP_(lg_slot_cnt)( MAP_T const * slot ) { return MAP_(private_from_slot_const)( slot )->lg_slot_cnt; }
376 1614115509 : FD_FN_PURE static inline ulong MAP_(slot_cnt) ( MAP_T const * slot ) { return MAP_(private_from_slot_const)( slot )->slot_mask+1UL; }
377 3 : FD_FN_PURE static inline ulong MAP_(seed) ( MAP_T const * slot ) { return MAP_(private_from_slot_const)( slot )->seed; }
378 :
379 : FD_FN_CONST static inline ulong
380 49750497 : MAP_(slot_idx)( MAP_T const * map, MAP_T const * entry ) {
381 : # if FD_TMPL_USE_HANDHOLDING
382 : if( FD_UNLIKELY( ((ulong)(entry-map)>=MAP_(slot_cnt)( map )) | (map>entry) ) ) FD_LOG_CRIT(( "index out of bounds" ));
383 : # endif
384 49750497 : return (ulong)(entry-map);
385 49750497 : }
386 :
387 1542 : FD_FN_CONST static inline MAP_KEY_T MAP_(key_null)( void ) { return (MAP_KEY_NULL); }
388 :
389 : /* These are FD_FN_PURE instead of FD_FN_CONST in case a non-POD
390 : MAP_KEY_T. FIXME: CONSIDER LETTING THE COMPILER SORT THIS OUT? */
391 :
392 5181287745 : FD_FN_PURE static inline int MAP_(key_inval)( MAP_KEY_T k0 ) { return (MAP_KEY_INVAL(k0)); }
393 3303578821 : FD_FN_PURE static inline int MAP_(key_equal)( MAP_KEY_T k0, MAP_KEY_T k1 ) { return (MAP_KEY_EQUAL(k0,k1)); }
394 :
395 : FD_FN_PURE static inline MAP_HASH_T
396 : MAP_(key_hash)( MAP_KEY_T key,
397 591802501 : ulong seed ) {
398 591802501 : (void)seed;
399 591802501 : return (MAP_KEY_HASH( (key), (seed) ));
400 591802501 : }
401 :
402 : FD_FN_UNUSED static MAP_T * /* Work around -Winline */
403 : MAP_(insert)( MAP_T * map,
404 284372691 : MAP_KEY_T key ) {
405 : # if FD_TMPL_USE_HANDHOLDING
406 : if( FD_UNLIKELY( MAP_(key_inval)( key ) ) ) FD_LOG_CRIT(( "invalid key" ));
407 : # endif
408 284372691 : MAP_(private_t) * hdr = MAP_(private_from_slot)( map );
409 :
410 284372691 : ulong key_cnt = hdr->key_cnt;
411 284372691 : ulong slot_mask = hdr->slot_mask; /* == key_max (FIXME: MAKE KEY_MAX DISTINCT FROM SLOT_MASK?) */
412 284372691 : if( FD_UNLIKELY( key_cnt >= slot_mask ) ) return NULL;
413 :
414 284372391 : MAP_HASH_T hash = MAP_(key_hash)( key, hdr->seed );
415 284372391 : ulong slot = MAP_(private_start)( hash, slot_mask );
416 284372391 : MAP_T * m;
417 2138269355 : for(;;) {
418 2138269355 : m = map + slot;
419 2138269355 : MAP_KEY_T map_key = m->MAP_KEY;
420 2138269355 : if( FD_LIKELY( MAP_(key_inval)( map_key ) ) ) break; /* Optimize for not found */
421 : # if MAP_MEMOIZE && MAP_KEY_EQUAL_IS_SLOW /* ... and then for searching */
422 21 : if( FD_UNLIKELY( m->MAP_HASH==hash && MAP_(key_equal)( map_key, key ) ) ) return NULL;
423 : # else
424 1854049943 : if( FD_UNLIKELY( MAP_(key_equal)( map_key, key ) ) ) return NULL;
425 1853896943 : # endif
426 1853896964 : slot = MAP_(private_next)( slot, slot_mask );
427 1853896964 : }
428 284219391 : MAP_KEY_MOVE( m->MAP_KEY, key );
429 : # if MAP_MEMOIZE
430 19284526 : m->MAP_HASH = hash;
431 : # endif
432 284219391 : hdr->key_cnt = key_cnt + 1UL;
433 284219391 : return m;
434 284372391 : }
435 :
436 : static inline void
437 : MAP_(remove)( MAP_T * map,
438 49748961 : MAP_T * entry ) {
439 49748961 : MAP_(private_t) * hdr = MAP_(private_from_slot)( map );
440 :
441 : /* FIXME: CONSIDER VALIDATING KEY_CNT AND/OR ENTRY ISN'T VALID */
442 49748961 : hdr->key_cnt--;
443 :
444 49748961 : ulong slot_mask = hdr->slot_mask;
445 49748961 : ulong slot = MAP_(slot_idx)( map, entry );
446 52920788 : for(;;) {
447 :
448 : /* Make a hole at slot */
449 :
450 52920788 : map[slot].MAP_KEY = (MAP_KEY_NULL);
451 52920788 : ulong hole = slot;
452 :
453 : /* The creation of a hole at slot might have disrupted the probe
454 : sequence involving the keys in any contiguously occupied map
455 : entry after slot. */
456 :
457 57884149 : for(;;) {
458 57884149 : slot = MAP_(private_next)( slot, slot_mask );
459 :
460 : /* At this point, map entries (hole,slot) (cyclic) are occupied
461 : and the probe sequence for these has been confirmed to be
462 : intact. If slot is empty, then all probe sequences are intact. */
463 :
464 57884149 : MAP_KEY_T key = map[slot].MAP_KEY;
465 57884149 : if( MAP_(key_inval)(key) ) return;
466 :
467 : /* slot is occupied. If a probe looking for the key at slot does
468 : not start its scan in (hole,slot] (cyclic), its scan will fail
469 : erroneously due to the hole just made. In this case, we move
470 : slot to hole to restore the probe sequence for the key at slot
471 : and then make a new hole at slot. As the new hole could break
472 : the other probe sequences, we start over on the new hole. */
473 :
474 : # if MAP_MEMOIZE
475 6079031 : MAP_HASH_T hash = map[slot].MAP_HASH;
476 : # else
477 2056157 : MAP_HASH_T hash = MAP_(key_hash)( key, hdr->seed );
478 : # endif
479 8135188 : ulong start = MAP_(private_start)( hash, slot_mask );
480 8135188 : if( !(((hole<start) & (start<=slot)) | ((hole>slot) & ((hole<start) | (start<=slot)))) ) break;
481 2056157 : }
482 :
483 3171827 : MAP_MOVE( map[hole], map[slot] );
484 3171827 : }
485 : /* never get here */
486 49748961 : }
487 :
488 : static inline void
489 2658 : MAP_(clear)( MAP_T * map ) {
490 2658 : MAP_(private_t) * hdr = MAP_(private_from_slot)( map );
491 2658 : hdr->key_cnt = 0UL;
492 2658 : ulong slot_cnt = 1UL<<hdr->lg_slot_cnt;
493 2658 : MAP_T * slot = hdr->slot;
494 45695970 : for( ulong slot_idx=0UL; slot_idx<slot_cnt; slot_idx++ )
495 45693312 : slot[ slot_idx ].MAP_KEY = (MAP_KEY_NULL);
496 2658 : }
497 :
498 : FD_FN_PURE FD_FN_UNUSED static MAP_T * /* Work around -Winline */
499 : MAP_(query)( MAP_T * map,
500 : MAP_KEY_T key,
501 305373953 : MAP_T * null ) {
502 : # if FD_TMPL_USE_HANDHOLDING
503 : if( FD_UNLIKELY( MAP_KEY_INVAL( key ) ) ) FD_LOG_CRIT(( "invalid key" ));
504 : # endif
505 305373953 : MAP_(private_t) * hdr = MAP_(private_from_slot)( map );
506 305373953 : ulong slot_mask = hdr->slot_mask;
507 305373953 : MAP_HASH_T hash = MAP_(key_hash)( key, hdr->seed );
508 305373953 : ulong slot = MAP_(private_start)( hash, slot_mask );
509 305373953 : MAP_T * m;
510 1409583473 : for(;;) {
511 1409583473 : m = map + slot;
512 1409583473 : MAP_KEY_T map_key = m->MAP_KEY;
513 :
514 : # if MAP_MEMOIZE && MAP_KEY_EQUAL_IS_SLOW
515 69 : # define MAP_IMPL_QUERY_FOUND (hash==m->MAP_HASH && MAP_(key_equal)( map_key, key ))
516 : # else
517 1371009720 : # define MAP_IMPL_QUERY_FOUND MAP_(key_equal)( map_key, key )
518 : # endif
519 :
520 : # if MAP_QUERY_OPT==0
521 1371009789 : int found = MAP_IMPL_QUERY_FOUND;
522 1371009789 : int empty = MAP_(key_inval)( map_key );
523 : int done = found | empty;
524 1371009789 : if( empty ) m = null; /* cmov */
525 1371009789 : FD_COMPILER_FORGET( done );
526 1371009789 : if( FD_LIKELY( done ) ) break;
527 : # elif MAP_QUERY_OPT==1
528 38573684 : if( FD_LIKELY( MAP_IMPL_QUERY_FOUND ) ) break;
529 6 : if( FD_LIKELY( MAP_(key_inval)( map_key ) ) ) return null;
530 : # else
531 : if( FD_LIKELY( MAP_(key_inval)( map_key ) ) ) return null;
532 : if( FD_LIKELY( MAP_IMPL_QUERY_FOUND ) ) break;
533 : # endif
534 :
535 6 : # undef MAP_IMPL_QUERY_FOUND
536 :
537 1104209520 : slot = MAP_(private_next)( slot, slot_mask );
538 1104209520 : }
539 38573678 : return m;
540 305373953 : }
541 :
542 : FD_PROTOTYPES_END
543 :
544 : #undef MAP_SLOT_MASK
545 : #undef MAP_SLOT_CNT
546 : #undef MAP_
547 :
548 : /* End implementation *************************************************/
549 :
550 : #undef MAP_QUERY_OPT
551 : #undef MAP_MEMOIZE
552 : #undef MAP_MOVE
553 : #undef MAP_KEY_MOVE
554 : #undef MAP_KEY_HASH
555 : #undef MAP_KEY_EQUAL_IS_SLOW
556 : #undef MAP_KEY_EQUAL
557 : #undef MAP_KEY_INVAL
558 : #undef MAP_KEY_NULL
559 : #undef MAP_KEY
560 : #undef MAP_KEY_T
561 : #undef MAP_HASH
562 : #undef MAP_HASH_T
563 : #undef MAP_T
564 : #undef MAP_NAME
565 :
|
