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 634875063 : #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 31422444 : #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 489564384 : #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 10414917888 : #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 3615337 : #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 382417596 : #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 471512798 : #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 191953119 : #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 293586004 : #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 5858271 : #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 15363181426 : #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 672422487 : MAP_(private_from_slot)( MAP_T * slot ) {
312 672422487 : ulong slot_ofs = offsetof( MAP_(private_t), slot );
313 672422487 : return (MAP_(private_t) *)( (ulong)slot - (ulong)slot_ofs );
314 672422487 : }
315 :
316 : FD_FN_CONST static inline MAP_(private_t) const *
317 1614741750 : MAP_(private_from_slot_const)( MAP_T const * slot ) {
318 1614741750 : ulong slot_ofs = offsetof( MAP_(private_t), slot );
319 1614741750 : return (MAP_(private_t) const *)( (ulong)slot - (ulong)slot_ofs );
320 1614741750 : }
321 :
322 : /* Get the linear probing starting slot for a key and the slot to probe
323 : after a given slot */
324 :
325 634875063 : 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 8211099480 : FD_FN_CONST static inline ulong MAP_(private_next) ( ulong slot, ulong slot_mask ) { return (++slot) & slot_mask; }
327 :
328 : /* Public APIS ********************************************************/
329 :
330 1168482 : FD_FN_CONST static inline ulong MAP_(align)( void ) { return alignof(MAP_(private_t)); }
331 :
332 : FD_FN_CONST static inline ulong
333 444132 : MAP_(footprint)( int lg_slot_cnt ) {
334 444132 : ulong slot_cnt = 1UL << lg_slot_cnt;
335 444132 : 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 444132 : }
337 :
338 : static inline void *
339 : MAP_(new)( void * shmem,
340 : int lg_slot_cnt,
341 317442 : 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 317442 : ulong slot_cnt = 1UL<<lg_slot_cnt;
347 317442 : ulong slot_mask = slot_cnt - 1UL;
348 317442 : MAP_(private_t) * map = (MAP_(private_t) *)shmem;
349 :
350 317442 : map->key_cnt = 0UL;
351 317442 : map->seed = seed;
352 317442 : map->slot_mask = slot_mask;
353 317442 : map->lg_slot_cnt = lg_slot_cnt;
354 :
355 317442 : MAP_T * slot = map->slot; FD_COMPILER_FORGET( slot );
356 :
357 2020160568 : for( ulong slot_idx=0UL; slot_idx<slot_cnt; slot_idx++ )
358 2019843126 : slot[ slot_idx ].MAP_KEY = (MAP_KEY_NULL);
359 :
360 317442 : return map;
361 317442 : }
362 :
363 : static inline MAP_T *
364 319194 : MAP_(join)( void * shmap ) {
365 319194 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
366 319194 : MAP_T * slot = map->slot; FD_COMPILER_FORGET( slot );
367 319194 : return slot;
368 319194 : }
369 :
370 315027 : static inline void * MAP_(leave) ( MAP_T * slot ) { return (void *)MAP_(private_from_slot)( slot ); }
371 313275 : static inline void * MAP_(delete)( void * shmap ) { return shmap; }
372 :
373 625806 : FD_FN_PURE static inline ulong MAP_(key_cnt) ( MAP_T const * slot ) { return MAP_(private_from_slot_const)( slot )->key_cnt; }
374 21 : 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 1614115479 : 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 54770389 : 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 54770389 : return (ulong)(entry-map);
385 54770389 : }
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 10394759680 : FD_FN_PURE static inline int MAP_(key_inval)( MAP_KEY_T k0 ) { return (MAP_KEY_INVAL(k0)); }
393 8502486242 : 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 627345416 : ulong seed ) {
398 627345416 : (void)seed;
399 627345416 : return (MAP_KEY_HASH( (key), (seed) ));
400 627345416 : }
401 :
402 : FD_FN_UNUSED static MAP_T * /* Work around -Winline */
403 : MAP_(insert)( MAP_T * map,
404 293739304 : 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 293739304 : MAP_(private_t) * hdr = MAP_(private_from_slot)( map );
409 :
410 293739304 : ulong key_cnt = hdr->key_cnt;
411 293739304 : ulong slot_mask = hdr->slot_mask; /* == key_max (FIXME: MAKE KEY_MAX DISTINCT FROM SLOT_MASK?) */
412 293739304 : if( FD_UNLIKELY( key_cnt >= slot_mask ) ) return NULL;
413 :
414 293739004 : MAP_HASH_T hash = MAP_(key_hash)( key, hdr->seed );
415 293739004 : ulong slot = MAP_(private_start)( hash, slot_mask );
416 293739004 : MAP_T * m;
417 7306898583 : for(;;) {
418 7306898583 : m = map + slot;
419 7306898583 : MAP_KEY_T map_key = m->MAP_KEY;
420 7306898583 : 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 : if( FD_UNLIKELY( m->MAP_HASH==hash && MAP_(key_equal)( map_key, key ) ) ) return NULL;
423 : # else
424 7013312579 : if( FD_UNLIKELY( MAP_(key_equal)( map_key, key ) ) ) return NULL;
425 7013159579 : # endif
426 7013159579 : slot = MAP_(private_next)( slot, slot_mask );
427 7013159579 : }
428 293586004 : MAP_KEY_MOVE( m->MAP_KEY, key );
429 : # if MAP_MEMOIZE
430 23892797 : m->MAP_HASH = hash;
431 : # endif
432 293586004 : hdr->key_cnt = key_cnt + 1UL;
433 293586004 : return m;
434 293739004 : }
435 :
436 : static inline void
437 : MAP_(remove)( MAP_T * map,
438 54768853 : MAP_T * entry ) {
439 54768853 : MAP_(private_t) * hdr = MAP_(private_from_slot)( map );
440 :
441 : # if FD_TMPL_USE_HANDHOLDING
442 : /* Note: this walks the probe chain a second time (the remove logic
443 : below walks it again). Acceptable for a debug-only check. */
444 : if( FD_UNLIKELY( !hdr->key_cnt ) ) FD_LOG_CRIT(( "map is empty" ));
445 : if( FD_UNLIKELY( MAP_(key_inval)( entry->MAP_KEY ) ) ) FD_LOG_CRIT(( "entry is not valid" ));
446 : {
447 : ulong _slot_mask = hdr->slot_mask;
448 : MAP_KEY_T _key = entry->MAP_KEY;
449 : MAP_HASH_T _hash = MAP_(key_hash)( _key, hdr->seed );
450 : ulong _slot = MAP_(private_start)( _hash, _slot_mask );
451 : for(;;) {
452 : if( FD_UNLIKELY( MAP_(key_inval)( map[_slot].MAP_KEY ) ) ) FD_LOG_CRIT(( "entry is not in the map" ));
453 : if( FD_LIKELY( &map[_slot]==entry ) ) break;
454 : _slot = MAP_(private_next)( _slot, _slot_mask );
455 : }
456 : }
457 : # endif
458 54768853 : hdr->key_cnt--;
459 :
460 54768853 : ulong slot_mask = hdr->slot_mask;
461 54768853 : ulong slot = MAP_(slot_idx)( map, entry );
462 60627124 : for(;;) {
463 :
464 : /* Make a hole at slot */
465 :
466 60627124 : map[slot].MAP_KEY = (MAP_KEY_NULL);
467 60627124 : ulong hole = slot;
468 :
469 : /* The creation of a hole at slot might have disrupted the probe
470 : sequence involving the keys in any contiguously occupied map
471 : entry after slot. */
472 :
473 72308267 : for(;;) {
474 72308267 : slot = MAP_(private_next)( slot, slot_mask );
475 :
476 : /* At this point, map entries (hole,slot) (cyclic) are occupied
477 : and the probe sequence for these has been confirmed to be
478 : intact. If slot is empty, then all probe sequences are intact. */
479 :
480 72308267 : MAP_KEY_T key = map[slot].MAP_KEY;
481 72308267 : if( MAP_(key_inval)(key) ) return;
482 :
483 : /* slot is occupied. If a probe looking for the key at slot does
484 : not start its scan in (hole,slot] (cyclic), its scan will fail
485 : erroneously due to the hole just made. In this case, we move
486 : slot to hole to restore the probe sequence for the key at slot
487 : and then make a new hole at slot. As the new hole could break
488 : the other probe sequences, we start over on the new hole. */
489 :
490 : # if MAP_MEMOIZE
491 7529647 : MAP_HASH_T hash = map[slot].MAP_HASH;
492 : # else
493 10009767 : MAP_HASH_T hash = MAP_(key_hash)( key, hdr->seed );
494 : # endif
495 17539414 : ulong start = MAP_(private_start)( hash, slot_mask );
496 17539414 : if( !(((hole<start) & (start<=slot)) | ((hole>slot) & ((hole<start) | (start<=slot)))) ) break;
497 10009767 : }
498 :
499 5858271 : MAP_MOVE( map[hole], map[slot] );
500 5858271 : }
501 : /* never get here */
502 54768853 : }
503 :
504 : static inline void
505 2658 : MAP_(clear)( MAP_T * map ) {
506 2658 : MAP_(private_t) * hdr = MAP_(private_from_slot)( map );
507 2658 : hdr->key_cnt = 0UL;
508 2658 : ulong slot_cnt = 1UL<<hdr->lg_slot_cnt;
509 2658 : MAP_T * slot = hdr->slot;
510 26624994 : for( ulong slot_idx=0UL; slot_idx<slot_cnt; slot_idx++ )
511 26622336 : slot[ slot_idx ].MAP_KEY = (MAP_KEY_NULL);
512 2658 : }
513 :
514 : FD_FN_PURE FD_FN_UNUSED static MAP_T * /* Work around -Winline */
515 : MAP_(query)( MAP_T * map,
516 : MAP_KEY_T key,
517 323596645 : MAP_T * null ) {
518 : # if FD_TMPL_USE_HANDHOLDING
519 : if( FD_UNLIKELY( MAP_KEY_INVAL( key ) ) ) FD_LOG_CRIT(( "invalid key" ));
520 : # endif
521 323596645 : MAP_(private_t) * hdr = MAP_(private_from_slot)( map );
522 323596645 : ulong slot_mask = hdr->slot_mask;
523 323596645 : MAP_HASH_T hash = MAP_(key_hash)( key, hdr->seed );
524 323596645 : ulong slot = MAP_(private_start)( hash, slot_mask );
525 323596645 : MAP_T * m;
526 1449228279 : for(;;) {
527 1449228279 : m = map + slot;
528 1449228279 : MAP_KEY_T map_key = m->MAP_KEY;
529 :
530 : # if MAP_MEMOIZE && MAP_KEY_EQUAL_IS_SLOW
531 : # define MAP_IMPL_QUERY_FOUND (hash==m->MAP_HASH && MAP_(key_equal)( map_key, key ))
532 : # else
533 1449228279 : # define MAP_IMPL_QUERY_FOUND MAP_(key_equal)( map_key, key )
534 1449228279 : # endif
535 :
536 : # if MAP_QUERY_OPT==0
537 1401438007 : int found = MAP_IMPL_QUERY_FOUND;
538 1401438007 : int empty = MAP_(key_inval)( map_key );
539 : int done = found | empty;
540 1401438007 : if( empty ) m = null; /* cmov */
541 1401438007 : FD_COMPILER_FORGET( done );
542 1401438007 : if( FD_LIKELY( done ) ) break;
543 : # elif MAP_QUERY_OPT==1
544 47790272 : if( FD_LIKELY( MAP_IMPL_QUERY_FOUND ) ) break;
545 7 : if( FD_LIKELY( MAP_(key_inval)( map_key ) ) ) return null;
546 : # else
547 : if( FD_LIKELY( MAP_(key_inval)( map_key ) ) ) return null;
548 : if( FD_LIKELY( MAP_IMPL_QUERY_FOUND ) ) break;
549 : # endif
550 :
551 4 : # undef MAP_IMPL_QUERY_FOUND
552 :
553 1125631634 : slot = MAP_(private_next)( slot, slot_mask );
554 1125631634 : }
555 47790265 : return m;
556 323596645 : }
557 :
558 : FD_PROTOTYPES_END
559 :
560 : #undef MAP_SLOT_MASK
561 : #undef MAP_SLOT_CNT
562 : #undef MAP_
563 :
564 : /* End implementation *************************************************/
565 :
566 : #undef MAP_QUERY_OPT
567 : #undef MAP_MEMOIZE
568 : #undef MAP_MOVE
569 : #undef MAP_KEY_MOVE
570 : #undef MAP_KEY_HASH
571 : #undef MAP_KEY_EQUAL_IS_SLOW
572 : #undef MAP_KEY_EQUAL
573 : #undef MAP_KEY_INVAL
574 : #undef MAP_KEY_NULL
575 : #undef MAP_KEY
576 : #undef MAP_KEY_T
577 : #undef MAP_HASH
578 : #undef MAP_HASH_T
579 : #undef MAP_T
580 : #undef MAP_NAME
|
