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 );
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 : // Returns the index of the slot (allows communicating locations of
70 : // map entries between users of mymap in different address spaces).
71 : // Might imply a division (probably via magic multiply) if
72 : // sizeof(mymap_t) is not a power of two (as such, power-of-2
73 : // sizeof(mymap_t) have good Feng Shui). Assumes that mymap is a
74 : // current join and slot points to a slot in that join.
75 :
76 : ulong mymap_slot_idx( mymap_t const * map, mymap_t const * slot );
77 :
78 : // Returns the "null" key, which is the canonical key that will
79 : // never be inserted (typically zero).
80 :
81 : ulong mymap_key_null( void ); // == MAP_KEY_NULL
82 :
83 : // Return the 1/0 if key is a key that will never/might be inserted.
84 :
85 : int mymap_key_inval( ulong key );
86 :
87 : // Return the 1/0 if k0 and k1 are keys that are the same
88 :
89 : int mymap_key_equal( ulong k0, ulong k1 );
90 :
91 : // Return the hash of key used by the map. Should ideally be a
92 : // random mapping from MAP_KEY_T -> MAP_HASH_T.
93 :
94 : uint mymap_key_hash( ulong key );
95 :
96 : // Insert key into the map, fast O(1). Returns a pointer to the map
97 : // entry with key on success and NULL on failure (i.e. key is
98 : // already in the map or there are too many keys in the map to
99 : // insert this key). The returned pointer lifetime is until _any_
100 : // map remove or map leave. The caller should not change the values
101 : // in map_key or map_hash but is free to modify other fields in the
102 : // entry on return. Assumes map is a current join and key is value
103 : // that can be inserted.
104 :
105 : mymap_t * mymap_insert( mymap_t * map, ulong key );
106 :
107 : // Remove entry from map, fast O(1). Assumes map is a current join
108 : // and that entry points to a full entry currently in the map.
109 : // Removal performance very slightly more optimal if sizeof(mymap_t)
110 : // is a power of two.
111 :
112 : void mymap_remove( mymap_t * map, mymap_t * entry );
113 :
114 : // Remove all entries from the map. O(map size).
115 :
116 : void mymap_clear( mymap_t * map );
117 :
118 : // Query map for key, fast O(1). Returns a pointer to the map slot
119 : // holding key or null if key not in map. The returned pointer
120 : // lifetime is until the next map remove or map leave. The caller
121 : // should not change key or hash but is free to modify other fields
122 : // in the entry. Assumes map is a current join and that key is
123 : // non-zero.
124 :
125 : mymap_t * mymap_query( mymap_t * map, ulong key, mymap_t * null );
126 :
127 : You can do this as often as you like in a compilation unit to get
128 : different types of maps. Since it is all static inline, it is fine
129 : to do this in a header too. Further, options exist to use different
130 : hashing functions, variable length keys, etc as detailed below.
131 :
132 : For use with non-POD C++ structs, map_new assumes that a slot can be
133 : initialized to empty by assigning its key to MAP_KEY_NULL. Map insert
134 : will use MAP_KEY_MOVE to move the user provided key into the slot key
135 : value. Map remove will MAP_MOVE slots as necessary to preserve their
136 : probe sequences and assumes the user has already cleaned up the entry
137 : to remove enough so that all that needs to be done to eliminate the
138 : entry from the map is assign the entry's key to MAP_KEY_NULL.
139 :
140 : mymap_t * slot = mymap_insert( map, cxx_key );
141 : if( FD_UNLIKELY( !slot ) ) ... handle failure (cxx_key was not moved)
142 : else {
143 : ... mymap_insert did a MAP_KEY_MOVE of cxx_key into slot->key
144 : ... clean cxx_key's shell here as necessary here
145 : ... initialize other slot fields as necessary
146 : }
147 :
148 : and on removal:
149 :
150 : ... clean up other slot fields as necessary
151 : ... clean up slot->key as necessary
152 : mymap_remove( map, slot );
153 : ... the mapping of keys to map slots might have been changed by the
154 : ... mymap_remove. Any motion of slots was done via:
155 : ... MAP_MOVE( dst_slot, src_slot ) */
156 :
157 : #include "../bits/fd_bits.h"
158 : #include <stddef.h>
159 :
160 : #ifndef offsetof
161 : # define offsetof(TYPE,MEMB) ((ulong)((TYPE*)0)->MEMB)
162 : #endif
163 :
164 : #ifndef MAP_NAME
165 : #error "Define MAP_NAME"
166 : #endif
167 :
168 : /* A MAP_T should be something reasonable to shallow copy with
169 : the fields described above. */
170 :
171 : #ifndef MAP_T
172 : #error "Define MAP_T struct"
173 : #endif
174 :
175 : /* MAP_HASH_T should be an unsigned integral type. */
176 :
177 : #ifndef MAP_HASH_T
178 572131353 : #define MAP_HASH_T uint
179 : #endif
180 :
181 : /* MAP_HASH is the MAP_T hash field name. Defaults to hash. */
182 :
183 : #ifndef MAP_HASH
184 16827022 : #define MAP_HASH hash
185 : #endif
186 :
187 : /* MAP_KEY_T should be something reasonable to pass to a static inline
188 : by value, assign to MAP_KEY_NULL, compare for equality and copy.
189 : E.g. a uint, ulong, __m128i, etc. */
190 :
191 : #ifndef MAP_KEY_T
192 505934121 : #define MAP_KEY_T ulong
193 : #else
194 : #if !defined(MAP_KEY_NULL) || !defined(MAP_KEY_INVAL) || !defined(MAP_KEY_EQUAL) || !defined(MAP_KEY_EQUAL_IS_SLOW) || !defined(MAP_KEY_HASH)
195 : #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"
196 : #endif
197 : #endif
198 :
199 : /* MAP_KEY is the MAP_T key field name. Defaults to key. */
200 :
201 : #ifndef MAP_KEY
202 5177731058 : #define MAP_KEY key
203 : #endif
204 :
205 : /* MAP_KEY_NULL is a key that will never be inserted. */
206 :
207 : #ifndef MAP_KEY_NULL
208 4073262 : #define MAP_KEY_NULL 0UL
209 : #endif
210 :
211 : /* MAP_KEY_INVAL returns 1 if k0 is key that will never be inserted
212 : and zero otherwise. Note that MAP_KEY_INVAL( MAP_KEY_NULL ) should
213 : be true. This should be generally fast. */
214 :
215 : #ifndef MAP_KEY_INVAL
216 447402169 : #define MAP_KEY_INVAL(k) !(k)
217 : #endif
218 :
219 : /* MAP_KEY_EQUAL returns 0/1 if k0 is the same/different */
220 :
221 : #ifndef MAP_KEY_EQUAL
222 512238678 : #define MAP_KEY_EQUAL(k0,k1) (k0)==(k1)
223 : #endif
224 :
225 : /* If MAP_KEY_EQUAL_IS_SLOW is slow (e.g. variable length string
226 : compare, large buffer compares, etc), set MAP_KEY_EQUAL_IS_SLOW to
227 : non-zero. Then, if MAP_MEMOIZE (below) is set, precomputed key hashes
228 : will be used accelerate key insert and key query. */
229 :
230 : #ifndef MAP_KEY_EQUAL_IS_SLOW
231 : #define MAP_KEY_EQUAL_IS_SLOW 0
232 : #endif
233 :
234 : /* MAP_KEY_HASH takes a key and maps it into MAP_HASH_T uniform pseudo
235 : randomly. */
236 :
237 : #ifndef MAP_KEY_HASH
238 160952447 : #define MAP_KEY_HASH(key) ((MAP_HASH_T)fd_ulong_hash( key ))
239 : #endif
240 :
241 : /* MAP_KEY_MOVE moves the contents from src to dst. Non-POD key types
242 : need to customize this accordingly (and handle the case of
243 : ks==MAP_KEY_NULL). Defaults to shallow copy. */
244 :
245 : #ifndef MAP_KEY_MOVE
246 278215193 : #define MAP_KEY_MOVE(kd,ks) (kd)=(ks)
247 : #endif
248 :
249 : /* MAP_MOVE moves the contents of a MAP_T from src to dst. Non-POD key
250 : types need to customize this accordingly. Defaults to shallow copy. */
251 :
252 : #ifndef MAP_MOVE
253 2073950 : #define MAP_MOVE(d,s) (d)=(s)
254 : #endif
255 :
256 : /* If MAP_MEMOIZE is defined to non-zero, the MAP_T requires a
257 : "map_hash" field that will hold the value of the MAP_KEY_HASH of the
258 : MAP_T's MAP_KEY when the map slot is not empty (undefined otherwise).
259 : This is useful for accelerating user operations that might need a
260 : hash of the key and for accelerating remove operations. It is also
261 : potentially useful as a way to accelerate slow key comparison
262 : operations (see MAP_KEY_EQUAL_IS_SLOW). */
263 :
264 : #ifndef MAP_MEMOIZE
265 : #define MAP_MEMOIZE 1
266 : #endif
267 :
268 : /* MAP_QUERY_OPT allows the user to specify how the map query function
269 : should be optimized.
270 : 0 -> optimize for low fill ratio
271 : 1 -> optimize for low fill ratio and extremely rare query failure
272 : 2 -> optimize for low fill ratio and extremely rare query success */
273 :
274 : #ifndef MAP_QUERY_OPT
275 : #define MAP_QUERY_OPT 0
276 : #endif
277 :
278 : #if FD_TMPL_USE_HANDHOLDING
279 : #include "../log/fd_log.h"
280 : #endif
281 :
282 : /* Implementation *****************************************************/
283 :
284 8125442005 : #define MAP_(n) FD_EXPAND_THEN_CONCAT3(MAP_NAME,_,n)
285 :
286 : struct MAP_(private) {
287 : ulong key_cnt; /* == number of keys currently in map */
288 : ulong slot_mask; /* == key_max == 2^lg_slot_cnt - 1 */
289 : int lg_slot_cnt; /* non-negative */
290 : MAP_T slot[1]; /* Actually 2^lg_slot_cnt in size */
291 : };
292 :
293 : typedef struct MAP_(private) MAP_(private_t);
294 :
295 : FD_PROTOTYPES_BEGIN
296 :
297 : /* Private APIs *******************************************************/
298 :
299 : /* private_from_slot return a pointer to the map_private given a pointer
300 : to the map's slot. private_from_map_const also provided for
301 : const-correctness purposes. */
302 :
303 : FD_FN_CONST static inline MAP_(private_t) *
304 609710063 : MAP_(private_from_slot)( MAP_T * slot ) {
305 609710063 : ulong slot_ofs = offsetof( MAP_(private_t), slot );
306 609710063 : return (MAP_(private_t) *)( (ulong)slot - (ulong)slot_ofs );
307 609710063 : }
308 :
309 : FD_FN_CONST static inline MAP_(private_t) const *
310 625608 : MAP_(private_from_slot_const)( MAP_T const * slot ) {
311 625608 : ulong slot_ofs = offsetof( MAP_(private_t), slot );
312 625608 : return (MAP_(private_t) const *)( (ulong)slot - (ulong)slot_ofs );
313 625608 : }
314 :
315 : /* Get the linear probing starting slot for a key and the slot to probe
316 : after a given slot */
317 :
318 572131353 : FD_FN_CONST static inline ulong MAP_(private_start)( MAP_HASH_T hash, ulong slot_mask ) { return (ulong)(hash & (MAP_HASH_T)slot_mask); }
319 3081837152 : FD_FN_CONST static inline ulong MAP_(private_next) ( ulong slot, ulong slot_mask ) { return (++slot) & slot_mask; }
320 :
321 : /* Public APIS ********************************************************/
322 :
323 1549212 : FD_FN_CONST static inline ulong MAP_(align)( void ) { return alignof(MAP_(private_t)); }
324 :
325 : FD_FN_CONST static inline ulong
326 453111 : MAP_(footprint)( int lg_slot_cnt ) {
327 453111 : ulong slot_cnt = 1UL << lg_slot_cnt;
328 453111 : return fd_ulong_align_up( fd_ulong_align_up( 24UL, alignof(MAP_T) ) + sizeof(MAP_T)*slot_cnt, alignof(MAP_(private_t)) );
329 453111 : }
330 :
331 : static inline void *
332 : MAP_(new)( void * shmem,
333 319830 : int lg_slot_cnt ) {
334 : # if FD_TMPL_USE_HANDHOLDING
335 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, MAP_(align)() ) ) ) FD_LOG_CRIT(( "unaligned shmem" ));
336 : if( FD_UNLIKELY( (lg_slot_cnt<0) | (lg_slot_cnt>63) ) ) FD_LOG_CRIT(( "invalid lg_slot_cnt" ));
337 : # endif
338 319830 : ulong slot_cnt = 1UL<<lg_slot_cnt;
339 319830 : ulong slot_mask = slot_cnt - 1UL;
340 319830 : MAP_(private_t) * map = (MAP_(private_t) *)shmem;
341 :
342 319830 : map->key_cnt = 0UL;
343 319830 : map->slot_mask = slot_mask;
344 319830 : map->lg_slot_cnt = lg_slot_cnt;
345 :
346 319830 : MAP_T * slot = map->slot; FD_COMPILER_FORGET( slot );
347 :
348 1965745152 : for( ulong slot_idx=0UL; slot_idx<slot_cnt; slot_idx++ )
349 1965425322 : slot[ slot_idx ].MAP_KEY = (MAP_KEY_NULL);
350 :
351 319830 : return map;
352 319830 : }
353 :
354 : static inline MAP_T *
355 319830 : MAP_(join)( void * shmap ) {
356 319830 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
357 319830 : MAP_T * slot = map->slot; FD_COMPILER_FORGET( slot );
358 319830 : return slot;
359 319830 : }
360 :
361 316392 : static inline void * MAP_(leave) ( MAP_T * slot ) { return (void *)MAP_(private_from_slot)( slot ); }
362 316392 : static inline void * MAP_(delete)( void * shmap ) { return shmap; }
363 :
364 625593 : FD_FN_PURE static inline ulong MAP_(key_cnt) ( MAP_T const * slot ) { return MAP_(private_from_slot_const)( slot )->key_cnt; }
365 3 : FD_FN_PURE static inline ulong MAP_(key_max) ( MAP_T const * slot ) { return MAP_(private_from_slot_const)( slot )->slot_mask; }
366 3 : FD_FN_PURE static inline int MAP_(lg_slot_cnt)( MAP_T const * slot ) { return MAP_(private_from_slot_const)( slot )->lg_slot_cnt; }
367 9 : FD_FN_PURE static inline ulong MAP_(slot_cnt) ( MAP_T const * slot ) { return MAP_(private_from_slot_const)( slot )->slot_mask+1UL; }
368 :
369 : FD_FN_CONST static inline ulong
370 43743963 : MAP_(slot_idx)( MAP_T const * map, MAP_T const * entry ) {
371 : # if FD_TMPL_USE_HANDHOLDING
372 : if( FD_UNLIKELY( ((ulong)(entry-map)>=MAP_(slot_cnt)( map )) | (map>entry) ) ) FD_LOG_CRIT(( "index out of bounds" ));
373 : # endif
374 43743963 : return (ulong)(entry-map);
375 43743963 : }
376 :
377 1542 : FD_FN_CONST static inline MAP_KEY_T MAP_(key_null)( void ) { return (MAP_KEY_NULL); }
378 :
379 : /* These are FD_FN_PURE instead of FD_FN_CONST in case a non-POD
380 : MAP_KEY_T. FIXME: CONSIDER LETTING THE COMPILER SORT THIS OUT? */
381 :
382 3620924961 : FD_FN_PURE static inline int MAP_(key_inval)( MAP_KEY_T k0 ) { return (MAP_KEY_INVAL(k0)); }
383 3358990159 : FD_FN_PURE static inline int MAP_(key_equal)( MAP_KEY_T k0, MAP_KEY_T k1 ) { return (MAP_KEY_EQUAL(k0,k1)); }
384 :
385 568587792 : FD_FN_PURE static inline MAP_HASH_T MAP_(key_hash)( MAP_KEY_T key ) { return (MAP_KEY_HASH(key)); }
386 :
387 : FD_FN_UNUSED static MAP_T * /* Work around -Winline */
388 : MAP_(insert)( MAP_T * map,
389 278368493 : MAP_KEY_T key ) {
390 : # if FD_TMPL_USE_HANDHOLDING
391 : if( FD_UNLIKELY( MAP_(key_inval)( key ) ) ) FD_LOG_CRIT(( "invalid key" ));
392 : # endif
393 278368493 : MAP_(private_t) * hdr = MAP_(private_from_slot)( map );
394 :
395 278368493 : ulong key_cnt = hdr->key_cnt;
396 278368493 : ulong slot_mask = hdr->slot_mask; /* == key_max (FIXME: MAKE KEY_MAX DISTINCT FROM SLOT_MASK?) */
397 278368493 : if( FD_UNLIKELY( key_cnt >= slot_mask ) ) return NULL;
398 :
399 278368193 : MAP_HASH_T hash = MAP_(key_hash)( key );
400 278368193 : ulong slot = MAP_(private_start)( hash, slot_mask );
401 278368193 : MAP_T * m;
402 2132767964 : for(;;) {
403 2132767964 : m = map + slot;
404 2132767964 : MAP_KEY_T map_key = m->MAP_KEY;
405 2132767964 : if( FD_LIKELY( MAP_(key_inval)( map_key ) ) ) break; /* Optimize for not found */
406 : # if MAP_MEMOIZE && MAP_KEY_EQUAL_IS_SLOW /* ... and then for searching */
407 0 : if( FD_UNLIKELY( m->MAP_HASH==hash && MAP_(key_equal)( map_key, key ) ) ) return NULL;
408 : # else
409 1854552771 : if( FD_UNLIKELY( MAP_(key_equal)( map_key, key ) ) ) return NULL;
410 1854399771 : # endif
411 1854399771 : slot = MAP_(private_next)( slot, slot_mask );
412 1854399771 : }
413 278215193 : MAP_KEY_MOVE( m->MAP_KEY, key );
414 : # if MAP_MEMOIZE
415 13283461 : m->MAP_HASH = hash;
416 : # endif
417 278215193 : hdr->key_cnt = key_cnt + 1UL;
418 278215193 : return m;
419 278368193 : }
420 :
421 : static inline void
422 : MAP_(remove)( MAP_T * map,
423 43742427 : MAP_T * entry ) {
424 43742427 : MAP_(private_t) * hdr = MAP_(private_from_slot)( map );
425 :
426 : /* FIXME: CONSIDER VALIDATING KEY_CNT AND/OR ENTRY ISN'T VALID */
427 43742427 : hdr->key_cnt--;
428 :
429 43742427 : ulong slot_mask = hdr->slot_mask;
430 43742427 : ulong slot = MAP_(slot_idx)( map, entry );
431 45816383 : for(;;) {
432 :
433 : /* Make a hole at slot */
434 :
435 45816383 : map[slot].MAP_KEY = (MAP_KEY_NULL);
436 45816383 : ulong hole = slot;
437 :
438 : /* The creation of a hole at slot might have disrupted the probe
439 : sequence involving the keys in any contiguously occupied map
440 : entry after slot. */
441 :
442 50225482 : for(;;) {
443 50225482 : slot = MAP_(private_next)( slot, slot_mask );
444 :
445 : /* At this point, map entries (hole,slot) (cyclic) are occupied
446 : and the probe sequence for these has been confirmed to be
447 : intact. If slot is empty, then all probe sequences are intact. */
448 :
449 50225482 : MAP_KEY_T key = map[slot].MAP_KEY;
450 50225482 : if( MAP_(key_inval)(key) ) return;
451 :
452 : /* slot is occupied. If a probe looking for the key at slot does
453 : not start its scan in (hole,slot] (cyclic), its scan will fail
454 : erroneously due to the hole just made. In this case, we move
455 : slot to hole to restore the probe sequence for the key at slot
456 : and then make a new hole at slot. As the new hole could break
457 : the other probe sequences, we start over on the new hole. */
458 :
459 : # if MAP_MEMOIZE
460 3543561 : MAP_HASH_T hash = map[slot].MAP_HASH;
461 : # else
462 2939494 : MAP_HASH_T hash = MAP_(key_hash)( key );
463 : # endif
464 6483055 : ulong start = MAP_(private_start)( hash, slot_mask );
465 6483055 : if( !(((hole<start) & (start<=slot)) | ((hole>slot) & ((hole<start) | (start<=slot)))) ) break;
466 2939494 : }
467 :
468 2073956 : MAP_MOVE( map[hole], map[slot] );
469 2073956 : }
470 : /* never get here */
471 43742427 : }
472 :
473 : static inline void
474 2646 : MAP_(clear)( MAP_T * map ) {
475 2646 : MAP_(private_t) * hdr = MAP_(private_from_slot)( map );
476 2646 : hdr->key_cnt = 0UL;
477 2646 : ulong slot_cnt = 1UL<<hdr->lg_slot_cnt;
478 2646 : MAP_T * slot = hdr->slot;
479 44048982 : for( ulong slot_idx=0UL; slot_idx<slot_cnt; slot_idx++ )
480 44046336 : slot[ slot_idx ].MAP_KEY = (MAP_KEY_NULL);
481 2646 : }
482 :
483 : FD_FN_PURE FD_FN_UNUSED static MAP_T * /* Work around -Winline */
484 : MAP_(query)( MAP_T * map,
485 : MAP_KEY_T key,
486 287280105 : MAP_T * null ) {
487 : # if FD_TMPL_USE_HANDHOLDING
488 : if( FD_UNLIKELY( MAP_KEY_INVAL( key ) ) ) FD_LOG_CRIT(( "invalid key" ));
489 : # endif
490 287280105 : ulong slot_mask = MAP_(private_from_slot)( map )->slot_mask;
491 287280105 : MAP_HASH_T hash = MAP_(key_hash)( key );
492 287280105 : ulong slot = MAP_(private_start)( hash, slot_mask );
493 287280105 : MAP_T * m;
494 1464492004 : for(;;) {
495 1464492004 : m = map + slot;
496 1464492004 : MAP_KEY_T map_key = m->MAP_KEY;
497 :
498 : # if MAP_MEMOIZE && MAP_KEY_EQUAL_IS_SLOW
499 0 : # define MAP_IMPL_QUERY_FOUND (hash==m->MAP_HASH && MAP_(key_equal)( map_key, key ))
500 : # else
501 1437914451 : # define MAP_IMPL_QUERY_FOUND MAP_(key_equal)( map_key, key )
502 : # endif
503 :
504 : # if MAP_QUERY_OPT==0
505 1437914451 : int found = MAP_IMPL_QUERY_FOUND;
506 1437914451 : int empty = MAP_(key_inval)( map_key );
507 : int done = found | empty;
508 1437914451 : if( empty ) m = null; /* cmov */
509 1437914451 : FD_COMPILER_FORGET( done );
510 1437914451 : if( FD_LIKELY( done ) ) break;
511 : # elif MAP_QUERY_OPT==1
512 26577553 : if( FD_LIKELY( MAP_IMPL_QUERY_FOUND ) ) break;
513 5994 : if( FD_LIKELY( MAP_(key_inval)( map_key ) ) ) return null;
514 : # else
515 : if( FD_LIKELY( MAP_(key_inval)( map_key ) ) ) return null;
516 : if( FD_LIKELY( MAP_IMPL_QUERY_FOUND ) ) break;
517 : # endif
518 :
519 0 : # undef MAP_IMPL_QUERY_FOUND
520 :
521 1177211899 : slot = MAP_(private_next)( slot, slot_mask );
522 1177211899 : }
523 26571559 : return m;
524 287280105 : }
525 :
526 : FD_PROTOTYPES_END
527 :
528 : #undef MAP_SLOT_MASK
529 : #undef MAP_SLOT_CNT
530 : #undef MAP_
531 :
532 : /* End implementation *************************************************/
533 :
534 : #undef MAP_QUERY_OPT
535 : #undef MAP_MEMOIZE
536 : #undef MAP_MOVE
537 : #undef MAP_KEY_MOVE
538 : #undef MAP_KEY_HASH
539 : #undef MAP_KEY_EQUAL_IS_SLOW
540 : #undef MAP_KEY_EQUAL
541 : #undef MAP_KEY_INVAL
542 : #undef MAP_KEY_NULL
543 : #undef MAP_KEY
544 : #undef MAP_KEY_T
545 : #undef MAP_HASH
546 : #undef MAP_HASH_T
547 : #undef MAP_T
548 : #undef MAP_NAME
549 :
|
