Line data Source code
1 : /* Declare ultra high performance dynamic key-val maps of bounded
2 : compile 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 : #define MAP_LG_SLOT_CNT 12
19 : #include "util/tmpl/fd_map.c"
20 :
21 : will declare the following static inline APIs as a header only style
22 : library in the compilation unit:
23 :
24 : // align/footprint - Return the alignment/footprint required for a
25 : // memory region to be used as mymap.
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.
34 : //
35 : // leave - Leave a mymap. Assumes mymap points to a current join.
36 : // Returns a pointer to the shared memory region the join.
37 : //
38 : // delete - Unformat a memory region used as a mymap. Assumes
39 : // shmymap points to a formatted region with no current joins.
40 : // Returns a pointer to the unformatted memory region.
41 :
42 : ulong mymap_align ( void );
43 : ulong mymap_footprint( void );
44 : void * mymap_new ( void * shmem );
45 : mymap_t * mymap_join ( void * shmymap );
46 : void * mymap_leave ( mymap_t * mymap );
47 : void * mymap_delete ( void * shmymap );
48 :
49 : // Return the maximum number of keys that can be inserted into a
50 : // mymap. The mymap will become increasingly inefficient the more
51 : // keys there are. Recommend not using more than around half this
52 : // value.
53 :
54 : ulong mymap_key_max( void ); // == 2^MAP_LG_SLOT_CNT - 1
55 :
56 : // Return the number of slots in a mymap. This is to facilitate
57 : // iterating / listing all contents of a mymap (this process is not
58 : // algorithmically ideal for a sparse mymap). E.g.
59 : // mymap[slot_idx].key for slot_idx in [0,mymap_slot_cnt()] when
60 : // key!=0 is the set of all current key-vals in the mymap.
61 :
62 : ulong mymap_slot_cnt( void ); // == 2^MAP_LG_SLOT_CNT
63 :
64 : // Returns the index of the slot (allows communicating locations of
65 : // map entries between users of mymap in different address spaces).
66 : // Might imply a division (probably via magic multiply) if
67 : // sizeof(mymap_t) is not a power of two (as such, power-of-2
68 : // sizeof(mymap_t) have good Feng Shui). Assumes that mymap is a
69 : // current join and slot points to a slot in that join.
70 :
71 : ulong mymap_slot_idx( mymap_t const * mymap, mymap_t const * slot );
72 :
73 : // Returns the "null" key, which is the canonical key that will
74 : // never be inserted (typically zero).
75 :
76 : ulong mymap_key_null( void ); // == MAP_KEY_NULL
77 :
78 : // Return the 1/0 if key is a key that will never/might be inserted.
79 :
80 : int mymap_key_inval( ulong key );
81 :
82 : // Return the 1/0 if k0 and k1 are keys that are the same
83 :
84 : int mymap_key_equal( ulong k0, ulong k1 );
85 :
86 : // Return the hash of key used by the map. Should ideally be a
87 : // random mapping from MAP_KEY_T -> MAP_HASH_T.
88 :
89 : uint mymap_key_hash( ulong key );
90 :
91 : // Insert key into the map, fast O(1). Returns a pointer to the map
92 : // the entry with key on success and NULL on failure (i.e. key is
93 : // already in the map). The returned pointer lifetime is until
94 : // _any_ map remove or map leave. The caller should not change the
95 : // values in key or hash but is free to modify other fields in the
96 : // entry on return. Assumes map is a current join, there are less
97 : // than mymap_key_max() keys in the map and key is not a value that
98 : // will never be inserted.
99 :
100 : mymap_t * mymap_insert( mymap_t * map, ulong key );
101 :
102 : // Remove entry from map, fast O(1). Assumes map is a current join
103 : // and that entry points to a full entry currently in the map. When
104 : // the function returns, the entry pointed to by entry may be
105 : // clobbered.
106 : // Removal performance very slightly more optimal if sizeof(mymap_t)
107 : // is a power of two.
108 :
109 : void mymap_remove( mymap_t * map, mymap_t * entry );
110 :
111 : // Remove all entries from the map. O(map size).
112 :
113 : void mymap_clear( mymap_t * map );
114 :
115 : // Query map for key, fast O(1). Returns a pointer to the map slot
116 : // holding key or null if key not in map. The returned pointer
117 : // lifetime is until the next map remove or map leave. The caller
118 : // should not change key or hash but is free to modify other fields
119 : // in the entry. Assumes map is a current join and that key is
120 : // non-zero. mymap_query_const is a const correct version.
121 :
122 : mymap_t * mymap_query ( mymap_t * map, ulong key, mymap_t * null );
123 : mymap_t const * mymap_query_const( mymap_t const * map, ulong key, mymap_t const * null );
124 :
125 : You can do this as often as you like in a compilation unit to get
126 : different types of maps. Since it is all static inline, it is fine
127 : to do this in a header too. Further, options exist to use different
128 : hashing functions, variable length keys, etc as detailed below.
129 :
130 : For use with non-POD C++ structs, map_new assumes that a slot can be
131 : initialized to empty by assigning its key to MAP_KEY_NULL. Map insert
132 : will use MAP_KEY_MOVE to move the user provided key into the slot key
133 : value. Map remove will MAP_MOVE slots as necessary to preserve their
134 : probe sequences and assumes the user has already cleaned up the entry
135 : to remove enough so that all that needs to be done to eliminate the
136 : entry from the map is assign the entry's key to MAP_KEY_NULL.
137 :
138 : mymap_t * slot = mymap_insert( map, cxx_key );
139 : if( FD_UNLIKELY( !slot ) ) ... handle failure (cxx_key was not moved)
140 : else {
141 : ... mymap_insert did a MAP_KEY_MOVE of cxx_key into slot->key
142 : ... clean cxx_key's shell here as necessary here
143 : ... initialize other slot fields as necessary
144 : }
145 :
146 : and on removal:
147 :
148 : ... clean up other slot fields as necessary
149 : ... clean up slot->key as necessary
150 : mymap_remove( map, slot );
151 : ... the mapping of keys to map slots might have been changed by the
152 : ... mymap_remove. Any motion of slots was done via:
153 : ... MAP_MOVE( dst_slot, src_slot )
154 :
155 : fd_map align and footprint are declaration friendly. E.g.
156 :
157 : mymap_t map[ ... map slot cnt ... ];
158 :
159 : will have the appropriate alignment and footprint for a mymap_t map. */
160 :
161 : #include "../bits/fd_bits.h"
162 :
163 : #ifndef MAP_NAME
164 : #error "Define MAP_NAME"
165 : #endif
166 :
167 : /* A MAP_T should be something reasonable to shallow copy with the
168 : fields described above. */
169 :
170 : #ifndef MAP_T
171 : #error "Define MAP_T struct"
172 : #endif
173 :
174 : /* MAP_HASH_T should be an unsigned integral type. */
175 :
176 : #ifndef MAP_HASH_T
177 1845481638 : #define MAP_HASH_T uint
178 : #endif
179 :
180 : /* MAP_HASH is the MAP_T hash field name. Defaults to hash. */
181 :
182 : #ifndef MAP_HASH
183 6909 : #define MAP_HASH hash
184 : #endif
185 :
186 : /* MAP_LG_SLOT_CNT is the log2 of the number of slots in the map. */
187 :
188 : #ifndef MAP_LG_SLOT_CNT
189 : #error "Define MAP_LG_SLOT_CNT, should be at least 1 and much less than 63"
190 : #endif
191 :
192 : /* MAP_KEY_T should be something reasonable to pass to a static inline
193 : by value, assign to MAP_KEY_NULL, compare for equality and copy.
194 : E.g. a uint, ulong, __m128i, etc. */
195 :
196 : #ifndef MAP_KEY_T
197 433548924 : #define MAP_KEY_T ulong
198 : #else
199 : #if !defined(MAP_KEY_NULL) || !defined(MAP_KEY_INVAL) || !defined(MAP_KEY_EQUAL) || !defined(MAP_KEY_EQUAL_IS_SLOW) || !defined(MAP_KEY_HASH)
200 : #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"
201 : #endif
202 : #endif
203 :
204 : /* MAP_KEY is the MAP_T key field name. Defaults to key. */
205 :
206 : #ifndef MAP_KEY
207 5513602413 : #define MAP_KEY key
208 : #endif
209 :
210 : /* MAP_KEY_NULL is a key that will never be inserted. */
211 :
212 : #ifndef MAP_KEY_NULL
213 530850 : #define MAP_KEY_NULL 0UL
214 : #endif
215 :
216 : /* MAP_KEY_INVAL returns 1 if k0 is key that will never be inserted
217 : and zero otherwise. Note that MAP_KEY_INVAL( MAP_KEY_NULL ) should
218 : be true. This should be generally fast. */
219 :
220 : #ifndef MAP_KEY_INVAL
221 433545702 : #define MAP_KEY_INVAL(k) !(k)
222 : #endif
223 :
224 : /* MAP_KEY_EQUAL returns 0/1 if k0 is the same/different. Note that
225 : this function may also be called with MAP_KEY_NULL. */
226 :
227 : #ifndef MAP_KEY_EQUAL
228 470285517 : #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 121091733 : #define MAP_KEY_HASH(key) (MAP_HASH_T)fd_ulong_hash( key )
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 1603468773 : #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 374472 : #define MAP_MOVE(d,s) (d)=(s)
260 : #endif
261 :
262 : /* If MAP_MEMOIZE is defined to non-zero, the MAP_T requires a hash
263 : field that will hold the value of the MAP_KEY_HASH of the MAP_T's key
264 : field when the map slot is not empty (undefined otherwise). This is
265 : useful for accelerating user operations that might need a hash of the
266 : key and for accelerating remove operations. It is also potentially
267 : useful as a way to accelerate slow key comparison operations (see
268 : 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 10039300071 : #define MAP_(n) FD_EXPAND_THEN_CONCAT3(MAP_NAME,_,n)
291 4467722583 : #define MAP_SLOT_CNT (1UL<<(MAP_LG_SLOT_CNT))
292 4013481975 : #define MAP_SLOT_MASK (MAP_SLOT_CNT-1UL)
293 :
294 : FD_PROTOTYPES_BEGIN
295 :
296 : /* Private APIs *******************************************************/
297 :
298 : /* Get the linear probing starting slot for a key and the slot to probe
299 : after a given slot */
300 :
301 1845486198 : FD_FN_CONST static inline ulong MAP_(private_start)( MAP_HASH_T hash ) { return (ulong)(hash & (MAP_HASH_T)MAP_SLOT_MASK); }
302 2167995441 : FD_FN_CONST static inline ulong MAP_(private_next) ( ulong slot ) { return (++slot) & MAP_SLOT_MASK; }
303 :
304 : /* Public APIS ********************************************************/
305 :
306 7878 : FD_FN_CONST static inline ulong MAP_(align) ( void ) { return alignof(MAP_T); }
307 8529 : FD_FN_CONST static inline ulong MAP_(footprint)( void ) { return sizeof(MAP_T)*MAP_SLOT_CNT; }
308 :
309 : static inline void *
310 8544 : MAP_(new)( void * shmem ) {
311 : # if FD_TMPL_USE_HANDHOLDING
312 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, MAP_(align)() ) ) ) FD_LOG_CRIT(( "unaligned shmem" ));
313 : # endif
314 8544 : MAP_T * map = (MAP_T *)shmem;
315 454229376 : for( ulong slot_idx=0UL; slot_idx<MAP_SLOT_CNT; slot_idx++ ) map[ slot_idx ].MAP_KEY = (MAP_KEY_NULL);
316 8544 : return map;
317 8544 : }
318 :
319 69459229 : static inline MAP_T * MAP_(join) ( void * shmap ) { return (MAP_T *)shmap; }
320 69459220 : static inline void * MAP_(leave) ( MAP_T * map ) { return map; }
321 7740 : static inline void * MAP_(delete)( void * shmap ) { return shmap; }
322 :
323 336 : FD_FN_CONST static inline ulong MAP_(key_max) ( void ) { return MAP_SLOT_MASK; }
324 1542 : FD_FN_CONST static inline ulong MAP_(slot_cnt)( void ) { return MAP_SLOT_CNT; }
325 :
326 : FD_FN_CONST static inline ulong
327 1603467468 : MAP_(slot_idx)( MAP_T const * map, MAP_T const * entry ) {
328 : # if FD_TMPL_USE_HANDHOLDING
329 : if( FD_UNLIKELY( ((ulong)(entry-map)>=MAP_SLOT_CNT) | (map>entry) ) ) FD_LOG_CRIT(( "index out of bounds" ));
330 : # endif
331 1603467468 : return (ulong)(entry-map);
332 1603467468 : }
333 :
334 1551 : FD_FN_CONST static inline MAP_KEY_T MAP_(key_null)( void ) { return (MAP_KEY_NULL); }
335 :
336 : /* These are FD_FN_PURE instead of FD_FN_CONST in case a non-POD
337 : MAP_KEY_T. FIXME: CONSIDER LETTING THE COMPILER SORT THIS OUT? */
338 :
339 5493522708 : FD_FN_PURE static inline int MAP_(key_inval)( MAP_KEY_T k0 ) { return (MAP_KEY_INVAL(k0)); }
340 598765488 : FD_FN_PURE static inline int MAP_(key_equal)( MAP_KEY_T k0, MAP_KEY_T k1 ) { return (MAP_KEY_EQUAL(k0,k1)); }
341 :
342 1845486198 : FD_FN_PURE static inline MAP_HASH_T MAP_(key_hash)( MAP_KEY_T key ) { return (MAP_KEY_HASH(key)); }
343 :
344 : FD_FN_UNUSED static MAP_T * /* Work around -Winline */
345 : MAP_(insert)( MAP_T * map,
346 1603719615 : MAP_KEY_T key ) {
347 : # if FD_TMPL_USE_HANDHOLDING
348 : if( FD_UNLIKELY( MAP_(key_inval)( key ) ) ) FD_LOG_CRIT(( "invalid key" ));
349 : # endif
350 1603719615 : MAP_HASH_T hash = MAP_(key_hash)( key );
351 1603719615 : ulong slot = MAP_(private_start)( hash );
352 1603719615 : MAP_T * m;
353 1737521349 : for(;;) {
354 1737521349 : m = map + slot;
355 1737521349 : MAP_KEY_T map_key = m->MAP_KEY;
356 1737521349 : if( FD_LIKELY( MAP_(key_inval)( map_key ) ) ) break; /* Optimize for not found */
357 : # if MAP_MEMOIZE && MAP_KEY_EQUAL_IS_SLOW /* ... and then for searching */
358 1170 : if( FD_UNLIKELY( m->MAP_HASH==hash && MAP_(key_equal)( map_key, key ) ) ) return NULL;
359 : # else
360 134051406 : if( FD_UNLIKELY( MAP_(key_equal)( map_key, key ) ) ) return NULL;
361 133800567 : # endif
362 133801734 : slot = MAP_(private_next)( slot );
363 133801734 : }
364 1603468773 : MAP_KEY_MOVE( m->MAP_KEY, key );
365 : # if MAP_MEMOIZE
366 3255 : m->MAP_HASH = hash;
367 : # endif
368 1603468773 : return m;
369 1603719615 : }
370 :
371 : static inline void
372 : MAP_(remove)( MAP_T * map,
373 1603465932 : MAP_T * entry ) {
374 1603465932 : ulong slot = MAP_(slot_idx)( map, entry );
375 :
376 1603840404 : for(;;) {
377 :
378 : /* Make a hole at slot */
379 :
380 1603840404 : map[slot].MAP_KEY = (MAP_KEY_NULL);
381 1603840404 : ulong hole = slot;
382 :
383 : /* The creation of a hole at slot might have disrupted the probe
384 : sequence involving the keys in any contiguously occupied map
385 : entry after slot. */
386 :
387 1727328336 : for(;;) {
388 1727328336 : slot = MAP_(private_next)( slot );
389 :
390 : /* At this point, map entries (hole,slot) (cyclic) are occupied
391 : and the probe sequence for these has been confirmed to be
392 : intact. If slot is empty, then all probe sequences are intact. */
393 :
394 1727328336 : MAP_KEY_T key = map[slot].MAP_KEY;
395 1727328336 : if( MAP_(key_inval)(key) ) return;
396 :
397 : /* slot is occupied. If a probe looking for the key at slot does
398 : not start its scan in (hole,slot] (cyclic), its scan will fail
399 : erroneously due to the hole just made. In this case, we move
400 : slot to hole to restore the probe sequence for the key at slot
401 : and then make a new hole at slot. As the new hole could break
402 : the other probe sequences, we start over on the new hole. */
403 :
404 : # if MAP_MEMOIZE
405 0 : MAP_HASH_T hash = map[slot].MAP_HASH;
406 : # else
407 123862404 : MAP_HASH_T hash = MAP_(key_hash)( key );
408 : # endif
409 123862404 : ulong start = MAP_(private_start)( hash );
410 123862404 : if( !(((hole<start) & (start<=slot)) | ((hole>slot) & ((hole<start) | (start<=slot)))) ) break;
411 123862404 : }
412 :
413 374472 : MAP_MOVE( map[hole], map[slot] );
414 374472 : }
415 : /* never get here */
416 1603465932 : }
417 :
418 : static inline void
419 9 : MAP_(clear)( MAP_T * map ) {
420 1161 : for( ulong slot_idx=0UL; slot_idx<MAP_SLOT_CNT; slot_idx++ ) map[ slot_idx ].MAP_KEY = (MAP_KEY_NULL);
421 9 : }
422 :
423 : FD_FN_PURE FD_FN_UNUSED static MAP_T * /* Work around -Winline */
424 : MAP_(query)( MAP_T * map,
425 : MAP_KEY_T key,
426 117904179 : MAP_T * null ) {
427 : # if FD_TMPL_USE_HANDHOLDING
428 : if( FD_UNLIKELY( MAP_KEY_INVAL( key ) ) ) FD_LOG_CRIT(( "invalid key" ));
429 : # endif
430 117904179 : MAP_HASH_T hash = MAP_(key_hash)( key );
431 117904179 : ulong slot = MAP_(private_start)( hash );
432 117904179 : MAP_T * m;
433 424769550 : for(;;) {
434 424769550 : m = map + slot;
435 424769550 : MAP_KEY_T map_key = m->MAP_KEY;
436 :
437 : # if MAP_MEMOIZE && MAP_KEY_EQUAL_IS_SLOW
438 2697 : # define MAP_IMPL_QUERY_FOUND (hash==m->MAP_HASH && MAP_(key_equal)( map_key, key ))
439 : # else
440 424766589 : # define MAP_IMPL_QUERY_FOUND MAP_(key_equal)( map_key, key )
441 : # endif
442 :
443 : # if MAP_QUERY_OPT==0
444 424769286 : int found = MAP_IMPL_QUERY_FOUND;
445 424769286 : int empty = MAP_(key_inval)( map_key );
446 : int done = found | empty;
447 424769286 : if( empty ) m = null; /* cmov */
448 424769286 : FD_COMPILER_FORGET( done );
449 424769286 : if( FD_LIKELY( done ) ) break;
450 : # elif MAP_QUERY_OPT==1
451 0 : if( FD_LIKELY( MAP_IMPL_QUERY_FOUND ) ) break;
452 0 : if( FD_LIKELY( MAP_(key_inval)( map_key ) ) ) return null;
453 : # else
454 264 : if( FD_LIKELY( MAP_(key_inval)( map_key ) ) ) return null;
455 243 : if( FD_LIKELY( MAP_IMPL_QUERY_FOUND ) ) break;
456 204 : # endif
457 :
458 204 : # undef MAP_IMPL_QUERY_FOUND
459 :
460 306865371 : slot = MAP_(private_next)( slot );
461 306865371 : }
462 39 : return m;
463 117904179 : }
464 :
465 : FD_FN_PURE static inline MAP_T const *
466 : MAP_(query_const)( MAP_T const * map,
467 : MAP_KEY_T key,
468 231 : MAP_T const * null ) {
469 231 : return (MAP_T const *)MAP_(query)( (MAP_T *)map, key, (MAP_T *)null ); /* query doesn't actual change any memory */
470 231 : }
471 :
472 : FD_PROTOTYPES_END
473 :
474 : #undef MAP_SLOT_MASK
475 : #undef MAP_SLOT_CNT
476 : #undef MAP_
477 :
478 : /* End implementation *************************************************/
479 :
480 : #undef MAP_QUERY_OPT
481 : #undef MAP_MEMOIZE
482 : #undef MAP_MOVE
483 : #undef MAP_KEY_MOVE
484 : #undef MAP_KEY_HASH
485 : #undef MAP_KEY_EQUAL_IS_SLOW
486 : #undef MAP_KEY_EQUAL
487 : #undef MAP_KEY_INVAL
488 : #undef MAP_KEY_NULL
489 : #undef MAP_KEY
490 : #undef MAP_KEY_T
491 : #undef MAP_LG_SLOT_CNT
492 : #undef MAP_HASH
493 : #undef MAP_HASH_T
494 : #undef MAP_T
495 : #undef MAP_NAME
496 :
|
