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 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 735349207 : #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 49526535 : #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 671218188 : #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 5500009683 : #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 4068426 : #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 433828994 : #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 616381986 : #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 281603769 : #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 319770248 : #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 4616882 : #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 : /* Implementation *****************************************************/
279 :
280 9740126935 : #define MAP_(n) FD_EXPAND_THEN_CONCAT3(MAP_NAME,_,n)
281 :
282 : struct MAP_(private) {
283 : ulong key_cnt; /* == number of keys currently in map */
284 : ulong slot_mask; /* == key_max == 2^lg_slot_cnt - 1 */
285 : int lg_slot_cnt; /* non-negative */
286 : MAP_T slot[1]; /* Actually 2^lg_slot_cnt in size */
287 : };
288 :
289 : typedef struct MAP_(private) MAP_(private_t);
290 :
291 : FD_PROTOTYPES_BEGIN
292 :
293 : /* Private APIs *******************************************************/
294 :
295 : /* private_from_slot return a pointer to the map_private given a pointer
296 : to the map's slot. private_from_map_const also provided for
297 : const-correctness purposes. */
298 :
299 : FD_FN_CONST static inline MAP_(private_t) *
300 808240877 : MAP_(private_from_slot)( MAP_T * slot ) {
301 808240877 : ulong slot_ofs = offsetof( MAP_(private_t), slot );
302 808240877 : return (MAP_(private_t) *)( (ulong)slot - (ulong)slot_ofs );
303 808240877 : }
304 :
305 : FD_FN_CONST static inline MAP_(private_t) const *
306 627813 : MAP_(private_from_slot_const)( MAP_T const * slot ) {
307 627813 : ulong slot_ofs = offsetof( MAP_(private_t), slot );
308 627813 : return (MAP_(private_t) const *)( (ulong)slot - (ulong)slot_ofs );
309 627813 : }
310 :
311 : /* Get the linear probing starting slot for a key and the slot to probe
312 : after a given slot */
313 :
314 735349207 : FD_FN_CONST static inline ulong MAP_(private_start)( MAP_HASH_T hash, ulong slot_mask ) { return (ulong)(hash & (MAP_HASH_T)slot_mask); }
315 3431320385 : FD_FN_CONST static inline ulong MAP_(private_next) ( ulong slot, ulong slot_mask ) { return (++slot) & slot_mask; }
316 :
317 : /* Public APIS ********************************************************/
318 :
319 0 : FD_FN_CONST static inline ulong MAP_(align)( void ) { return alignof(MAP_(private_t)); }
320 :
321 : FD_FN_CONST static inline ulong
322 777294 : MAP_(footprint)( int lg_slot_cnt ) {
323 777294 : ulong slot_cnt = 1UL << lg_slot_cnt;
324 777294 : return fd_ulong_align_up( fd_ulong_align_up( 24UL, alignof(MAP_T) ) + sizeof(MAP_T)*slot_cnt, alignof(MAP_(private_t)) );
325 777294 : }
326 :
327 : static inline void *
328 : MAP_(new)( void * shmem,
329 634743 : int lg_slot_cnt ) {
330 634743 : ulong slot_cnt = 1UL<<lg_slot_cnt;
331 634743 : ulong slot_mask = slot_cnt - 1UL;
332 634743 : MAP_(private_t) * map = (MAP_(private_t) *)shmem;
333 :
334 634743 : map->key_cnt = 0UL;
335 634743 : map->slot_mask = slot_mask;
336 634743 : map->lg_slot_cnt = lg_slot_cnt;
337 :
338 634743 : MAP_T * slot = map->slot; FD_COMPILER_FORGET( slot );
339 :
340 1935944049 : for( ulong slot_idx=0UL; slot_idx<slot_cnt; slot_idx++ )
341 1935309306 : slot[ slot_idx ].MAP_KEY = (MAP_KEY_NULL);
342 :
343 634743 : return map;
344 634743 : }
345 :
346 : static inline MAP_T *
347 634743 : MAP_(join)( void * shmap ) {
348 634743 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
349 634743 : MAP_T * slot = map->slot; FD_COMPILER_FORGET( slot );
350 634743 : return slot;
351 634743 : }
352 :
353 316182 : static inline void * MAP_(leave) ( MAP_T * slot ) { return (void *)MAP_(private_from_slot)( slot ); }
354 316182 : static inline void * MAP_(delete)( void * shmap ) { return shmap; }
355 :
356 627804 : FD_FN_PURE static inline ulong MAP_(key_cnt) ( MAP_T const * slot ) { return MAP_(private_from_slot_const)( slot )->key_cnt; }
357 3 : FD_FN_PURE static inline ulong MAP_(key_max) ( MAP_T const * slot ) { return MAP_(private_from_slot_const)( slot )->slot_mask; }
358 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; }
359 3 : FD_FN_PURE static inline ulong MAP_(slot_cnt) ( MAP_T const * slot ) { return MAP_(private_from_slot_const)( slot )->slot_mask+1UL; }
360 :
361 84717637 : FD_FN_CONST static inline ulong MAP_(slot_idx)( MAP_T const * map, MAP_T const * entry ) { return (ulong)(entry - map); }
362 :
363 0 : FD_FN_CONST static inline MAP_KEY_T MAP_(key_null)( void ) { return (MAP_KEY_NULL); }
364 :
365 : /* These are FD_FN_PURE instead of FD_FN_CONST in case a non-POD
366 : MAP_KEY_T. FIXME: CONSIDER LETTING THE COMPILER SORT THIS OUT? */
367 :
368 4051879544 : FD_FN_PURE static inline int MAP_(key_inval)( MAP_KEY_T k0 ) { return (MAP_KEY_INVAL(k0)); }
369 3777841509 : FD_FN_PURE static inline int MAP_(key_equal)( MAP_KEY_T k0, MAP_KEY_T k1 ) { return (MAP_KEY_EQUAL(k0,k1)); }
370 :
371 728131281 : FD_FN_PURE static inline MAP_HASH_T MAP_(key_hash)( MAP_KEY_T key ) { return (MAP_KEY_HASH(key)); }
372 :
373 : FD_FN_UNUSED static MAP_T * /* Work around -Winline */
374 : MAP_(insert)( MAP_T * map,
375 319923548 : MAP_KEY_T key ) {
376 319923548 : MAP_(private_t) * hdr = MAP_(private_from_slot)( map );
377 :
378 319923548 : ulong key_cnt = hdr->key_cnt;
379 319923548 : ulong slot_mask = hdr->slot_mask; /* == key_max (FIXME: MAKE KEY_MAX DISTINCT FROM SLOT_MASK?) */
380 319923548 : if( FD_UNLIKELY( key_cnt >= slot_mask ) ) return NULL;
381 :
382 319923248 : MAP_HASH_T hash = MAP_(key_hash)( key );
383 319923248 : ulong slot = MAP_(private_start)( hash, slot_mask );
384 319923248 : MAP_T * m;
385 2191302491 : for(;;) {
386 2191302491 : m = map + slot;
387 2191302491 : MAP_KEY_T map_key = m->MAP_KEY;
388 2191302491 : if( FD_LIKELY( MAP_(key_inval)( map_key ) ) ) break; /* Optimize for not found */
389 : # if MAP_MEMOIZE && MAP_KEY_EQUAL_IS_SLOW /* ... and then for searching */
390 0 : if( FD_UNLIKELY( m->MAP_HASH==hash && MAP_(key_equal)( map_key, key ) ) ) return NULL;
391 : # else
392 1871532243 : if( FD_UNLIKELY( MAP_(key_equal)( map_key, key ) ) ) return NULL;
393 1871379243 : # endif
394 1871379243 : slot = MAP_(private_next)( slot, slot_mask );
395 1871379243 : }
396 319770248 : MAP_KEY_MOVE( m->MAP_KEY, key );
397 : # if MAP_MEMOIZE
398 42308609 : m->MAP_HASH = hash;
399 : # endif
400 319770248 : hdr->key_cnt = key_cnt + 1UL;
401 319770248 : return m;
402 319923248 : }
403 :
404 : static inline void
405 : MAP_(remove)( MAP_T * map,
406 84716101 : MAP_T * entry ) {
407 84716101 : MAP_(private_t) * hdr = MAP_(private_from_slot)( map );
408 :
409 : /* FIXME: CONSIDER VALIDATING KEY_CNT AND/OR ENTRY ISN'T VALID */
410 84716101 : hdr->key_cnt--;
411 :
412 84716101 : ulong slot_mask = hdr->slot_mask;
413 84716101 : ulong slot = MAP_(slot_idx)( map, entry );
414 89332989 : for(;;) {
415 :
416 : /* Make a hole at slot */
417 :
418 89332989 : map[slot].MAP_KEY = (MAP_KEY_NULL);
419 89332989 : ulong hole = slot;
420 :
421 : /* The creation of a hole at slot might have disrupted the probe
422 : sequence involving the keys in any contiguously occupied map
423 : entry after slot. */
424 :
425 96859660 : for(;;) {
426 96859660 : slot = MAP_(private_next)( slot, slot_mask );
427 :
428 : /* At this point, map entries (hole,slot) (cyclic) are occupied
429 : and the probe sequence for these has been confirmed to be
430 : intact. If slot is empty, then all probe sequences are intact. */
431 :
432 96859660 : MAP_KEY_T key = map[slot].MAP_KEY;
433 96859660 : if( MAP_(key_inval)(key) ) return;
434 :
435 : /* slot is occupied. If a probe looking for the key at slot does
436 : not start its scan in (hole,slot] (cyclic), its scan will fail
437 : erroneously due to the hole just made. In this case, we move
438 : slot to hole to restore the probe sequence for the key at slot
439 : and then make a new hole at slot. As the new hole could break
440 : the other probe sequences, we start over on the new hole. */
441 :
442 : # if MAP_MEMOIZE
443 7217926 : MAP_HASH_T hash = map[slot].MAP_HASH;
444 : # else
445 4925633 : MAP_HASH_T hash = MAP_(key_hash)( key );
446 : # endif
447 12143559 : ulong start = MAP_(private_start)( hash, slot_mask );
448 12143559 : if( !(((hole<start) & (start<=slot)) | ((hole>slot) & ((hole<start) | (start<=slot)))) ) break;
449 4925633 : }
450 :
451 4616888 : MAP_MOVE( map[hole], map[slot] );
452 4616888 : }
453 : /* never get here */
454 84716101 : }
455 :
456 : static inline void
457 2646 : MAP_(clear)( MAP_T * map ) {
458 2646 : MAP_(private_t) * hdr = MAP_(private_from_slot)( map );
459 2646 : hdr->key_cnt = 0UL;
460 2646 : ulong slot_cnt = 1UL<<hdr->lg_slot_cnt;
461 2646 : MAP_T * slot = hdr->slot;
462 44835414 : for( ulong slot_idx=0UL; slot_idx<slot_cnt; slot_idx++ )
463 44832768 : slot[ slot_idx ].MAP_KEY = (MAP_KEY_NULL);
464 2646 : }
465 :
466 : FD_FN_PURE FD_FN_UNUSED static MAP_T * /* Work around -Winline */
467 : MAP_(query)( MAP_T * map,
468 : MAP_KEY_T key,
469 403282400 : MAP_T * null ) {
470 403282400 : ulong slot_mask = MAP_(private_from_slot)( map )->slot_mask;
471 403282400 : MAP_HASH_T hash = MAP_(key_hash)( key );
472 403282400 : ulong slot = MAP_(private_start)( hash, slot_mask );
473 403282400 : MAP_T * m;
474 1866363882 : for(;;) {
475 1866363882 : m = map + slot;
476 1866363882 : MAP_KEY_T map_key = m->MAP_KEY;
477 :
478 : # if MAP_MEMOIZE && MAP_KEY_EQUAL_IS_SLOW
479 0 : # define MAP_IMPL_QUERY_FOUND (hash==m->MAP_HASH && MAP_(key_equal)( map_key, key ))
480 : # else
481 1724484915 : # define MAP_IMPL_QUERY_FOUND MAP_(key_equal)( map_key, key )
482 : # endif
483 :
484 : # if MAP_QUERY_OPT==0
485 1724484915 : int found = MAP_IMPL_QUERY_FOUND;
486 1724484915 : int empty = MAP_(key_inval)( map_key );
487 : int done = found | empty;
488 1724484915 : if( empty ) m = null; /* cmov */
489 1724484915 : FD_COMPILER_FORGET( done );
490 1724484915 : if( FD_LIKELY( done ) ) break;
491 : # elif MAP_QUERY_OPT==1
492 141878967 : if( FD_LIKELY( MAP_IMPL_QUERY_FOUND ) ) break;
493 39227432 : if( FD_LIKELY( MAP_(key_inval)( map_key ) ) ) return null;
494 : # else
495 : if( FD_LIKELY( MAP_(key_inval)( map_key ) ) ) return null;
496 : if( FD_LIKELY( MAP_IMPL_QUERY_FOUND ) ) break;
497 : # endif
498 :
499 5444749 : # undef MAP_IMPL_QUERY_FOUND
500 :
501 1463081482 : slot = MAP_(private_next)( slot, slot_mask );
502 1463081482 : }
503 102651535 : return m;
504 403282400 : }
505 :
506 : FD_PROTOTYPES_END
507 :
508 : #undef MAP_SLOT_MASK
509 : #undef MAP_SLOT_CNT
510 : #undef MAP_
511 :
512 : /* End implementation *************************************************/
513 :
514 : #undef MAP_QUERY_OPT
515 : #undef MAP_MEMOIZE
516 : #undef MAP_MOVE
517 : #undef MAP_KEY_MOVE
518 : #undef MAP_KEY_HASH
519 : #undef MAP_KEY_EQUAL_IS_SLOW
520 : #undef MAP_KEY_EQUAL
521 : #undef MAP_KEY_INVAL
522 : #undef MAP_KEY_NULL
523 : #undef MAP_KEY
524 : #undef MAP_KEY_T
525 : #undef MAP_HASH
526 : #undef MAP_HASH_T
527 : #undef MAP_T
528 : #undef MAP_NAME
|
