Line data Source code
1 : /* Generate prototypes, inlines and/or implementations for
2 : _non_-concurrent persistent shared key-val maps based on linear
3 : probing. Roughly speaking, this provides the advanced features of
4 : fd_map_slot_para with an API more like fd_map_dynamic. Namely, like
5 : fd_map_slot_para and beyond fd_map_dynamic, this has:
6 :
7 : - First class support for seeded hashing (this has also been
8 : backported to fd_map_dynamic).
9 :
10 : - First class support for upserting.
11 :
12 : - First class support for prefetching (including efficient handling
13 : of expensive key hashing between prefetch and use).
14 :
15 : - No requirement for a sentinel key. (Maps that do use sentinel
16 : keys are still supported.)
17 :
18 : - Improved support for key-val pairs that are not plain-old-data.
19 :
20 : - Bounded and configurable worst case algorithmic bounds (and, as a
21 : side effect, no requirement for the user to guarantee there is
22 : always at least one free element in the element store).
23 :
24 : - Iteration over all keys with a common hash (e.g. for maps that
25 : use structured hashing to group keys together).
26 :
27 : - A run-time data integrity verification function.
28 :
29 : All operations have been factored into a strict O(1) inline fast path
30 : and a compact bounded worst case non-inlined slow path. The shared
31 : part of the map is just a plain-old flat array of elements.
32 :
33 : In typical usage, doing:
34 :
35 : struct myele {
36 :
37 : ulong key; // Technically "MAP_KEY_T MAP_KEY;" (default is ulong key)
38 : ulong memo; // Technically "ulong MAP_MEMO;" (default is ulong memo), ==mymap_key_hash(key,seed)
39 :
40 : ... key and memo can be located arbitrarily in struct and are
41 : ... managed by the mymap. memo is not required if MAP_MEMOIZE is
42 : ... zero or not specified. The rest of the struct holds the vals
43 : ... associated with key. The mapping of a key to a location in
44 : ... the element store is arbitrary and might change whenever any
45 : ... key is removed from the map.
46 :
47 : };
48 :
49 : typedef struct myele myele_t;
50 :
51 : #define MAP_NAME mymap
52 : #define MAP_ELE_T myele_t
53 : #include "util/tmpl/fd_map_slot.c"
54 :
55 : will declare the following APIs as a header only style library in the
56 : current translation unit:
57 :
58 : // A mymap_t is a stack declaration friendly quasi-opaque local
59 : // object used to hold the state of a local join to a mymap.
60 : // Similarly, a mymap_iter_t holds the local state of an ongoing
61 : // iteration. E.g. it is fine to do mymap_t join[1];" to allocate
62 : // a mymap_t but the contents should not be used directly.
63 :
64 : typedef struct mymap_private mymap_t;
65 : typedef struct mymap_iter_private mymap_iter_t;
66 :
67 : // mymap_{ele_is_free,key_eq,key_hash} expose the user provided
68 : // MAP_{ELE_IS_FREE,KEY_EQ,KEY_HASH} implementations as functions
69 : // with strict semantics. They assume that the provided pointers
70 : // are in the caller's address space and will not be changed during
71 : // the call. They retain no interest after the call.
72 : //
73 : // mymap_ele_is_free returns 1 if *ele is not in use and 0 otherwise.
74 : //
75 : // mymap_key_eq returns 1 if *k0 and *k1 are equal and 0 otherwise.
76 : //
77 : // mymap_key_hash returns the hash of *key using the hash function
78 : // seed. This should ideally be a random mapping from a MAP_KEY_T
79 : // to a ulong but this depends on what the user actually provided
80 : // for MAP_KEY_HASH. The seed used by a particular mymap instance
81 : // can be obtained from the mymap accessors.
82 :
83 : int mymap_ele_is_free( myele_t * ele );
84 : int mymap_key_eq ( ulong * k0, ulong * k1 );
85 : ulong mymap_key_hash ( ulong * key, ulong seed );
86 :
87 : // mymap_probe_max_est returns a reasonable value to use for
88 : // probe_max with an ele_max myele_t store. Assumes a valid
89 : // ele_max. Return will be in [1,ele_max].
90 :
91 : ulong mymap_probe_max_est( ulong ele_max );
92 :
93 : // mymap_{align,footprint} return the {alignment,footprint}
94 : // required for a memory region to be used as myele_t store with
95 : // ele_max elements. footprint returns 0 if ele_max is not an
96 : // integer power of 2 where ele_max*sizeof(myele_t) does not
97 : // overflow.
98 : //
99 : // mymap_new formats the memory region pointed to by shmem into a
100 : // myele_t element store sufficient for ele_max elements. If reset
101 : // is non-zero, this will also clear the memory region. If reset
102 : // is zero or clearing the region does not mark all the elements in
103 : // the store as free, it is the caller's responsibility to mark all
104 : // elements as free. Assumes shmem is not in use on entry.
105 : // Returns shmem on success (shmem will be a suitable store for the
106 : // mymap) or NULL on failure (bad ele_max, NULL shmem, misaligned
107 : // shmem ... no changes, log details). Caller is not joined on
108 : // return.
109 : //
110 : // mymap_join joins the caller to an existing mymap. lmem points
111 : // to a mymap_t compatible memory region in the caller's address
112 : // space, ele0 points to the mymap's element store, ele_max is the
113 : // store's element capacity, probe_max is a bound for worst case
114 : // time complexity for most operations (in [1,ele_max]) and seed is
115 : // the hash seed to use. All joiners must use the same ele_max,
116 : // probe_max and seed (as this is not a concurrent structure, there
117 : // typically is only a single join in practice). Returns a handle
118 : // to the caller's local join on success (join has ownership of the
119 : // lmem region) and NULL on failure (no changes, logs details).
120 : //
121 : // mymap_leave leaves a mymap. join points to a current local
122 : // join. Returns the memory region used for the join on success
123 : // (caller has ownership on return and the caller is no longer
124 : // joined) and NULL on failure (no changes, logs details). Use the
125 : // mymap accessors before leaving to get the underlying element
126 : // store if needed.
127 : //
128 : // mymap_delete unformats a memory region used as a mymap element
129 : // store. Assumes ele0 points in the caller's address space to the
130 : // memory region used as the element store and that there are no
131 : // current joins. Returns shmem on success (caller has ownership
132 : // of the memory region, any remaining elements still in the mymap
133 : // are released to the caller implicitly, any resources used by
134 : // theses are the caller's responsibility to clean up) and NULL on
135 : // failure (no changes, logs details).
136 :
137 : ulong mymap_align ( void );
138 : ulong mymap_footprint( ulong ele_max );
139 : myele_t * mymap_new ( void * shmem, ulong ele_max, int reset );
140 : mymap_t * mymap_join ( void * lmem, myele_t * ele0, ulong ele_max, ulong probe_max, ulong seed );
141 : void * mymap_leave ( mymap_t * join );
142 : void * mymap_delete ( myele_t * ele0 );
143 :
144 : // mymap_{ele0,ele_max,probe_max,seed} return the corresponding
145 : // join value. Assumes join is a current local join.
146 : // mymap_ele0_const is a const correct version.
147 :
148 : myele_t * mymap_ele0 ( mymap_t * join );
149 : ulong mymap_ele_max ( mymap_t const * join );
150 : ulong mymap_probe_max ( mymap_t const * join );
151 : ulong mymap_seed ( mymap_t const * join );
152 :
153 : myele_t const * mymap_ele0_const( mymap_t const * join );
154 :
155 : // mymap_{ctx,ctx_max} return {a pointer in the caller's address
156 : // space to,the byte size of} the join's user context. The
157 : // lifetime of the returned pointer is the join's lifetime.
158 : // Assumes join is a current local join. mymap_ctx_const is a
159 : // const correct version.
160 :
161 : void * mymap_ctx ( mymap_t * join );
162 : ulong mymap_ctx_max( mymap_t const * join );
163 :
164 : void const * mymap_ctx_const( mymap_t const * join );
165 :
166 : // Basic operations
167 :
168 : // mymap_query:
169 : //
170 : // ... join is a current local join and key points to the key of
171 : // ... interest (for maps that use key sentinels, *key should not
172 : // ... be a sentinel key), retains no interest in join or key.
173 : //
174 : // ele = mymap_query( join, key );
175 : //
176 : // if( FD_UNLIKELY( !ele ) ) {
177 : //
178 : // ... no element *key in map
179 : //
180 : // } else {
181 : //
182 : // ... ele points in the caller's address space into the
183 : // ... element store where element *key is currently held. The
184 : // ... caller is free to read any field of ele. ele's lifetime
185 : // ... is until the next remove or leave.
186 : //
187 : // }
188 :
189 : myele_t const * mymap_query ( mymap_t const * join, ulong const * key );
190 :
191 : // mymap_update:
192 : //
193 : // ... join is a current local join and key points to the key of
194 : // ... interest (for maps that use key sentinels, *key should not
195 : // ... be a sentinel key), retains no interest in join or key.
196 : //
197 : // ele = mymap_update( join, key );
198 : //
199 : // if( FD_UNLIKELY( !ele ) ) {
200 : //
201 : // ... no element *key in map
202 : //
203 : // } else {
204 : //
205 : // ... ele points in the caller's address space into the
206 : // ... element store where element *key is currently held. The
207 : // ... caller is free to update ele's val fields. Caller
208 : // ... should not update ele's key, update ele's memo (if
209 : // ... applicable) or mark ele as free (if applicable). ele's
210 : // ... lifetime is until the next remove or leave.
211 : //
212 : // }
213 :
214 : myele_t * mymap_update( mymap_t * join, ulong const * key );
215 :
216 : // mymap_insert:
217 : //
218 : // ... join is a current local join and key points to the key of
219 : // ... interest (for maps that use key sentinels, *key should not
220 : // ... be a sentinel key), retains no interest in join or key.
221 : //
222 : // ele = mymap_insert( join, key );
223 : //
224 : // if( FD_UNLIKELY( !ele ) ) {
225 : //
226 : // ... element *key is already in the map or the map was too
227 : // ... full to insert element *key
228 : //
229 : // } else {
230 : //
231 : // ... we are starting to insert element *key. ele's key and
232 : // ... (if applicable) ele's memo will already be initialized
233 : // ... to *key and mymap_key_hash( key, seed ) respectively.
234 : // ... Further, if the map uses key sentinels, the ele will be
235 : // ... implicitly marked as not free.
236 : //
237 : // ... caller should initalize ele's val fields here and, if
238 : // ... map does not use key sentinels, mark ele as not free (at
239 : // ... which point, ele's lifetime is until the next remove or
240 : // ... leave).
241 : //
242 : // ... If ele is not marked as in use, the insert is implicitly
243 : // ... canceled (at which point, ele's lifetime is until the
244 : // ... next insert, remove or leave).
245 : //
246 : // }
247 :
248 : myele_t * mymap_insert( mymap_t * join, ulong const * key );
249 :
250 : // mymap_upsert:
251 : //
252 : // ... join is a current local join and key points to the key of
253 : // ... interest (for maps that use key sentinels, *key should not
254 : // ... be a sentinel key), retains no interest in join or key.
255 : //
256 : // ele = mymap_upsert( join, key );
257 : //
258 : // if( FD_UNLIKELY( !ele ) ) {
259 : //
260 : // ... element *key is not in map and the map is too full to
261 : // ... insert it
262 : //
263 : // } else if( FD_UNLIKELY( mymap_ele_is_free( ele ) ) ) {
264 : //
265 : // ... element *key was not in map and should be inserted at
266 : // ... ele. See insert for details how to complete inserting
267 : // ... ele.
268 : //
269 : // ... Note that if mymap uses key sentinels to indicate when
270 : // ... an element is free, this code path will never be taken.
271 : // ... That is, the caller will not be able to tell via
272 : // ... mymap_ele_is_free if an upsert is inserting or updating
273 : // ... as the upsert initialized ele's key field (implicitly
274 : // ... marking the element as not free such).
275 : //
276 : // } else {
277 : //
278 : // ... element *key is stored in the map at ele. See update
279 : // ... for details how to complete updating ele.
280 : //
281 : // ... Note that if mymap uses key sentinels to indicate when
282 : // ... an element is free, we might actually be inserting ele
283 : // ... here (see note above).
284 : //
285 : // }
286 :
287 : myele_t * mymap_upsert( mymap_t * join, ulong const * key );
288 :
289 : // mymap_remove:
290 : //
291 : // ... join is a current local join and ele points to the
292 : // ... location in the element store holding element key to
293 : // ... remove. (As such this location is marked as not free.)
294 : //
295 : // mymap_remove( join, ele );
296 : //
297 : // ... at this point, element key is no longer in the map and all
298 : // ... pointers into the element store are potentially pointing
299 : // ... at different and/or free elements.
300 :
301 : void mymap_remove( mymap_t * join, myele_t * ele );
302 :
303 : // Advanced operations
304 :
305 : // mymap_hint tries to prefetch the location currently holding
306 : // element *key from the map according to the user hint and returns
307 : // the memo==mymap_key_hash( key, seed ) for use with the below
308 : // APIs.
309 : //
310 : // mymap_{query,update,insert,upsert}_fast are the same as the
311 : // basic operations but require the user to pass in the memo
312 : // corresponding to key (e.g. computed earlier by hint) and allow
313 : // the user to give an element sentinel location to return on
314 : // failure.
315 : //
316 : // All these assume join is a current local join and key points to
317 : // the key of interest (for maps that use key sentinels, *key
318 : // should not be a sentinel key). These retain no interest in
319 : // join, key or the element sentinel (use NULL for error handling
320 : // like the basic API).
321 : //
322 : // Advanced example (prefetching query with branchless error
323 : // handling):
324 : //
325 : // memo = mymap_hint( map, key, hint )
326 : //
327 : // ... do other stuff while memory subsystem is prefetching in
328 : // ... the background here
329 : //
330 : // ele = mymap_query_fast( join, key, memo, fallback );
331 : //
332 : // ... at this point, ele is guaranteed non-NULL (if element *key
333 : // ... is not in the map, ele will point to fallback which could
334 : // ... hold, for example, fallback vals to use when *key specific
335 : // ... vals are not available).
336 :
337 : ulong mymap_hint( mymap_t * join, ulong const * key, int hint );
338 :
339 : myele_t const * mymap_query_fast ( mymap_t const * join, ulong const * key, ulong memo, myele_t const * sentinel );
340 : myele_t * mymap_update_fast( mymap_t * join, ulong const * key, ulong memo, myele_t * sentinel );
341 : myele_t * mymap_insert_fast( mymap_t * join, ulong const * key, ulong memo, myele_t * sentinel );
342 : myele_t * mymap_upsert_fast( mymap_t * join, ulong const * key, ulong memo, myele_t * sentinel );
343 :
344 : // mymap_iter_{init,done,next,ele,ele_const} allow for iteration
345 : // over all mymap elements with the same memo. Basic usage:
346 : //
347 : // ulong memo = ... memo of keys of interest;
348 : //
349 : // for( mymap_iter_t iter = mymap_iter_init( join, memo );
350 : // !mymap_iter_done( join, memo, iter );
351 : // iter = mymap_iter_next( join, memo, iter ) ) {
352 : //
353 : // myele_t * ele = mymap_iter_ele( join, memo, iter );
354 : //
355 : // ... process ele here (do not modify key or memo, do
356 : // ... not insert or remove any elements)
357 : //
358 : // }
359 :
360 : mymap_iter_t mymap_iter_init ( mymap_t const * join, ulong memo );
361 : int mymap_iter_done ( mymap_t const * join, ulong memo, mymap_iter_t iter );
362 : mymap_iter_t mymap_iter_next ( mymap_t const * join, ulong memo, mymap_iter_t iter );
363 : myele_t const * mymap_iter_ele_const( mymap_t const * join, ulong memo, mymap_iter_t iter );
364 : myele_t * mymap_iter_ele ( mymap_t * join, ulong memo, mymap_iter_t iter );
365 :
366 : // mymap_verify returns 0 if the join and underlying element store
367 : // give a mapping of unique keys to unique elements in the element
368 : // store with properly bounded maximum probe length and -1
369 : // otherwise (no changes, logs details).
370 :
371 : int mymap_verify( mymap_t const * join );
372 :
373 : Do this as often as desired in a compilation unit to get different
374 : types of maps. Options exist for generating library header
375 : prototypes and/or library implementations for maps usable across
376 : multiple translation units. Additional options exist to use
377 : different hashing functions, key comparison functions, etc as
378 : detailed below. */
379 :
380 : /* MAP_NAME gives the API prefix to use */
381 :
382 : #ifndef MAP_NAME
383 : #error "Define MAP_NAME"
384 : #endif
385 :
386 : /* MAP_ELE_T is the map element type */
387 :
388 : #ifndef MAP_ELE_T
389 : #error "Define MAP_ELE_T"
390 : #endif
391 :
392 : /* MAP_KEY_T is the map key type */
393 :
394 : #ifndef MAP_KEY_T
395 : #define MAP_KEY_T ulong
396 : #endif
397 :
398 : /* MAP_KEY is the MAP_KEY_T key field. When a slot is in use, this
399 : field is managed by the map. For maps that use key sentinels, this
400 : element may also designate whether or not an element is in use. */
401 :
402 : #ifndef MAP_KEY
403 : #define MAP_KEY key
404 : #endif
405 :
406 : /* MAP_KEY_EQ returns 0/1 if *k0 is the same/different as *k1 */
407 :
408 : #ifndef MAP_KEY_EQ
409 498 : #define MAP_KEY_EQ(k0,k1) ((*(k0))==(*(k1)))
410 : #endif
411 :
412 : /* MAP_KEY_HASH returns a random mapping of *key into ulong. The
413 : mapping is parameterized by the 64-bit ulong seed. */
414 :
415 : #ifndef MAP_KEY_HASH
416 : #define MAP_KEY_HASH(key,seed) fd_ulong_hash( (*(key)) ^ (seed) )
417 : #endif
418 :
419 : /* If MAP_MEMOIZE is non-zero, elements have a field that can be used
420 : while in the map to hold the MAP_KEY_HASH for an element's key. This
421 : is useful for accelerating user code that might need a hash and
422 : various map operations. */
423 :
424 : #ifndef MAP_MEMOIZE
425 : #define MAP_MEMOIZE 0
426 : #endif
427 :
428 : /* If MAP_MEMOIZE is non-zero, MAP_MEMO is the memo element field.
429 : Should be a ulong. Like MAP_KEY, when a slot is in use, this field
430 : is managed by the map and will contain the MAP_KEY_HASH of the
431 : element's key and the map's seed. */
432 :
433 : #ifndef MAP_MEMO
434 : #define MAP_MEMO memo
435 : #endif
436 :
437 : /* If MAP_MEMOIZE and MAP_KEY_EQ_IS_SLOW are both non-zero, the MAP_MEMO
438 : field should be used to accelerate MAP_KEY_EQ operations. This is
439 : useful when MAP_KEY_EQ is non-trivial (e.g. variable length string
440 : compare, large buffer compares, etc). */
441 :
442 : #ifndef MAP_KEY_EQ_IS_SLOW
443 : #define MAP_KEY_EQ_IS_SLOW 0
444 : #endif
445 :
446 : /* MAP_ELE_IS_FREE returns 0/1 if the slot pointed to by ele in the
447 : caller's address space contains/does not contain a key-val pair. The
448 : implementation can assume ele points to a slot in the element store.
449 : The default implementation tests if key is not 0 (i.e. "0" is a key
450 : sentinel). If using a different key sentinel or not using a key
451 : sentinel, update this appropriately. */
452 :
453 : #ifndef MAP_ELE_IS_FREE
454 4188 : #define MAP_ELE_IS_FREE(ele) (!((ele)->MAP_KEY))
455 : #endif
456 :
457 : /* MAP_ELE_FREE frees the key-val pair in the slot pointed to by ele in
458 : the caller's address space. The implementation can assume ele is
459 : valid, ele contains a key-value pair on entry and there will be no
460 : concurrent operations on ele during the free. The default
461 : implementation sets key to 0. If using a different key sentinel or
462 : not using a key sentinel, update this appropriately. Likewise, if
463 : not using plain-old-data keys and vals, this should do the
464 : appropriate application specific resource management. The join ctx
465 : is provided to facilitate this. */
466 :
467 : #ifndef MAP_ELE_FREE
468 0 : #define MAP_ELE_FREE(ctx,ele) do (ele)->MAP_KEY = (MAP_KEY_T)0; while(0)
469 : #endif
470 :
471 : /* MAP_ELE_MOVE moves the key-val pair in slot src to slot dst. src and
472 : dst are in the caller's address space. The implementation can assume
473 : src and dst are valid and src/dst does/does not contain a key-val
474 : pair on entry. The default implementation shallow copies src to dst
475 : and sets src key to 0. If using a different key sentinel or not
476 : using a key sentinel, update this appropriately. Likewise, if
477 : elements do not use plain-old-data keys and/or vals, this should do
478 : the appropriate key and/or val resource management. The join ctx is
479 : provided to facilitate this. */
480 :
481 : #ifndef MAP_ELE_MOVE
482 : #define MAP_ELE_MOVE(ctx,dst,src) do { MAP_ELE_T * _src = (src); (*(dst)) = *_src; _src->MAP_KEY = (MAP_KEY_T)0; } while(0)
483 : #endif
484 :
485 : /* MAP_CTX_MAX specifies the maximum number of bytes of user context for
486 : use in MAP_ELE_FREE / MAP_ELE_MOVE above (e.g. custom allocators /
487 : workspaces / local pointers to additional value arrays / etc). This
488 : context will be ulong aligned. Default is up to 32 bytes. */
489 :
490 : #ifndef MAP_CTX_MAX
491 3 : #define MAP_CTX_MAX (32UL)
492 : #endif
493 :
494 : /* MAP_PREFETCH specifies how the hint API should prefetch a slot. The
495 : default is to call __builtin_prefetch on the address of the slot's
496 : leading byte using the default rw and locality hints of 0 (read) / 3
497 : (high temporal locality). Note that a user hint value is provided to
498 : support for more sophisticated and application specific forms of
499 : prefetching.
500 :
501 : Also note that instrincs like __builtin_prefetch often require their
502 : hints to be _compile_ _time_ _constants_ (because they map to
503 : assembly instructions that encode these hints into the raw
504 : instruction stream). Ideally, we would plumb in the appropriate
505 : instrinic hint from a _compile_ _time _constant_ user hint directly
506 : via something like:
507 :
508 : __builtin_prefetch( (src), (hint) & 1, (hint) >> 1 )
509 :
510 : But ... sigh ... the compiler frequently does not recognize the above
511 : values are in fact compile time constants (it will try to compile the
512 : enclosing static inline to an intermediate representation and fail
513 : because it doesn't know the values above will simplify into compile
514 : time constants at the inline call sites ... yet another area where
515 : macros actually are faster than inlines in real world code).
516 :
517 : Working around this typically requires using constructs like:
518 :
519 : if( (hint)==0 ) __builtin_prefetch( (src), 0, 3 );
520 : else if( (hint)==1 ) __builtin_prefetch( (src), 1, 3 );
521 : ...
522 :
523 : and keeping our fingers crossed the compiler will prune the
524 : unnecessary branches at compile time. Which it often won't because
525 : it will view the construct as too large and complex to inline and
526 : thus never get around to pruning the dead branches at the call sites
527 : ... more sighs ... YMMV. */
528 :
529 : #ifndef MAP_PREFETCH
530 : #define MAP_PREFETCH(src,hint) __builtin_prefetch( (src), 0, 3 )
531 : #endif
532 :
533 : /* MAP_IMPL_STYLE controls what to generate:
534 : 0 - header only library
535 : 1 - library header declaration
536 : 2 - library implementation */
537 :
538 : #ifndef MAP_IMPL_STYLE
539 : #define MAP_IMPL_STYLE 0
540 : #endif
541 :
542 : /* Implementation *****************************************************/
543 :
544 : #if MAP_IMPL_STYLE==0 /* local use only */
545 : #define MAP_STATIC FD_FN_UNUSED static
546 : #else /* library header and/or implementation */
547 : #define MAP_STATIC
548 : #endif
549 :
550 52985139 : #define MAP_(n) FD_EXPAND_THEN_CONCAT3(MAP_NAME,_,n)
551 :
552 : #if MAP_IMPL_STYLE!=2 /* need header */
553 :
554 : #include "../bits/fd_bits.h"
555 :
556 : struct MAP_(private) {
557 : MAP_ELE_T * ele0; /* Points to the element store in caller's address space, indexed [0,ele_max) */
558 : ulong ele_mask; /* ==ele_max-1UL where ele_max is a power of 2 */
559 : ulong probe_rem; /* ==probe_max-1UL where probe_max is in [1,ele_max], probe_max bounds worst case ops count. */
560 : ulong seed; /* Key hash seed */
561 : uchar ctx[ MAP_CTX_MAX ]; /* User context (for non-POD datatypes) */
562 : };
563 :
564 : typedef struct MAP_(private) MAP_(t);
565 :
566 : typedef ulong MAP_(iter_t); /* Element store index cursor for current iteration */
567 :
568 : FD_PROTOTYPES_BEGIN
569 :
570 : /* Private APIs *******************************************************/
571 :
572 : static inline void
573 : MAP_(private_ele_free)( void * ctx,
574 3746628 : MAP_ELE_T * ele ) {
575 3746628 : (void)ctx;
576 3746628 : MAP_ELE_FREE( (ctx), (ele) );
577 3746628 : }
578 :
579 : static inline void
580 : MAP_(private_ele_move)( void * ctx,
581 : MAP_ELE_T * dst,
582 178689 : MAP_ELE_T * src ) {
583 178689 : (void)ctx;
584 178689 : MAP_ELE_MOVE( (ctx), (dst), (src) );
585 178689 : }
586 :
587 : FD_FN_PURE MAP_STATIC MAP_ELE_T *
588 : MAP_(private_update)( MAP_(t) * join,
589 : MAP_KEY_T const * key,
590 : ulong memo,
591 : MAP_ELE_T * sentinel );
592 :
593 : MAP_STATIC MAP_ELE_T *
594 : MAP_(private_insert)( MAP_(t) * join,
595 : MAP_KEY_T const * key,
596 : ulong memo,
597 : MAP_ELE_T * sentinel );
598 :
599 : MAP_STATIC MAP_ELE_T *
600 : MAP_(private_upsert)( MAP_(t) * join,
601 : MAP_KEY_T const * key,
602 : ulong memo,
603 : MAP_ELE_T * sentinel );
604 :
605 : MAP_STATIC void
606 : MAP_(private_remove)( MAP_(t) * join,
607 : ulong hole_idx );
608 :
609 : /* Public APIs ********************************************************/
610 :
611 : FD_FN_PURE static inline int
612 34684452 : MAP_(ele_is_free)( MAP_ELE_T const * ele ) {
613 34684452 : return !!(MAP_ELE_IS_FREE( (ele) ));
614 34684452 : }
615 :
616 : FD_FN_PURE static inline int
617 : MAP_(key_eq)( MAP_KEY_T const * k0,
618 25216143 : MAP_KEY_T const * k1 ) {
619 25216143 : return !!(MAP_KEY_EQ( (k0), (k1) ));
620 25216143 : }
621 :
622 : FD_FN_PURE static inline ulong
623 : MAP_(key_hash)( MAP_KEY_T const * key,
624 42114000 : ulong seed ) {
625 42114000 : return (MAP_KEY_HASH( (key), (seed) ));
626 42114000 : }
627 :
628 3000003 : FD_FN_CONST static inline ulong MAP_(probe_max_est)( ulong ele_max ) { return ele_max; }
629 :
630 237 : FD_FN_CONST static inline ulong MAP_(align)( void ) { return alignof(MAP_ELE_T); }
631 :
632 : FD_FN_CONST static inline ulong
633 213 : MAP_(footprint)( ulong ele_max ) {
634 213 : if( !((ele_max<=(ULONG_MAX / sizeof(MAP_ELE_T))) & fd_ulong_is_pow2( ele_max )) ) return 0UL;
635 195 : return ele_max*sizeof(MAP_ELE_T); /* no overflow */
636 213 : }
637 :
638 : MAP_STATIC MAP_ELE_T * MAP_(new) ( void * shmem, ulong ele_max, int reset );
639 : MAP_STATIC MAP_(t) * MAP_(join) ( void * lmem, MAP_ELE_T * ele0, ulong ele_max, ulong probe_max, ulong seed );
640 : MAP_STATIC void * MAP_(leave) ( MAP_(t) * join );
641 : MAP_STATIC void * MAP_(delete)( MAP_ELE_T * ele0 );
642 :
643 3 : FD_FN_PURE static inline MAP_ELE_T * MAP_(ele0) ( MAP_(t) * join ) { return join->ele0; }
644 15 : FD_FN_PURE static inline MAP_ELE_T const * MAP_(ele0_const)( MAP_(t) const * join ) { return join->ele0; }
645 3 : FD_FN_PURE static inline ulong MAP_(ele_max) ( MAP_(t) const * join ) { return join->ele_mask + 1UL; }
646 3 : FD_FN_PURE static inline ulong MAP_(probe_max) ( MAP_(t) const * join ) { return join->probe_rem + 1UL; }
647 3 : FD_FN_PURE static inline ulong MAP_(seed) ( MAP_(t) const * join ) { return join->seed; }
648 3 : FD_FN_CONST static inline void * MAP_(ctx) ( MAP_(t) * join ) { return join->ctx; }
649 3 : FD_FN_CONST static inline void const * MAP_(ctx_const) ( MAP_(t) const * join ) { return join->ctx; }
650 3 : FD_FN_CONST static inline ulong MAP_(ctx_max) ( MAP_(t) const * join ) { (void)join; return MAP_CTX_MAX; }
651 :
652 : FD_FN_PURE static inline ulong
653 : MAP_(hint)( MAP_(t) const * join,
654 : MAP_KEY_T const * key,
655 9364152 : int hint ) {
656 9364152 : ulong memo = MAP_(key_hash)( key, join->seed );
657 9364152 : MAP_PREFETCH( join->ele0 + (memo & join->ele_mask), hint ); (void)hint;
658 9364152 : return memo;
659 9364152 : }
660 :
661 : FD_FN_PURE static inline MAP_ELE_T *
662 : MAP_(update_fast)( MAP_(t) * join,
663 : MAP_KEY_T const * key,
664 : ulong memo,
665 14987250 : MAP_ELE_T * sentinel ) {
666 : # if FD_TMPL_USE_HANDHOLDING
667 : FD_TEST( memo==MAP_(key_hash)( key, join->seed ) );
668 : # endif
669 :
670 14987250 : ulong ele_idx = memo & join->ele_mask;
671 :
672 14987250 : MAP_ELE_T * ele = join->ele0 + ele_idx;
673 :
674 14987250 : if( FD_UNLIKELY( MAP_(ele_is_free)( ele ) ) ) return sentinel;
675 :
676 : # if MAP_MEMOIZE && MAP_KEY_EQ_IS_SLOW
677 : if( FD_LIKELY( ele->MAP_MEMO==memo ) && FD_LIKELY( MAP_(key_eq)( &ele->MAP_KEY, key ) ) ) return ele;
678 : # else
679 8081802 : if( FD_LIKELY( MAP_(key_eq)( &ele->MAP_KEY, key ) ) ) return ele;
680 893985 : # endif
681 :
682 893985 : return MAP_(private_update)( join, key, memo, sentinel );
683 8081802 : }
684 :
685 : static inline MAP_ELE_T *
686 : MAP_(insert_fast)( MAP_(t) * join,
687 : MAP_KEY_T const * key,
688 : ulong memo,
689 5615277 : MAP_ELE_T * sentinel ) {
690 : # if FD_TMPL_USE_HANDHOLDING
691 : FD_TEST( memo==MAP_(key_hash)( key, join->seed ) );
692 : # endif
693 :
694 5615277 : ulong ele_idx = memo & join->ele_mask;
695 :
696 5615277 : MAP_ELE_T * ele = join->ele0 + ele_idx;
697 :
698 5615277 : if( FD_LIKELY( MAP_(ele_is_free)( ele ) ) ) {
699 : # if MAP_MEMOIZE
700 : ele->MAP_MEMO = memo;
701 : # endif
702 3449136 : ele->MAP_KEY = *key;
703 3449136 : return ele;
704 3449136 : }
705 :
706 : # if MAP_MEMOIZE && MAP_KEY_EQ_IS_SLOW
707 : if( FD_UNLIKELY( ele->MAP_MEMO==memo ) && FD_UNLIKELY( MAP_(key_eq)( &ele->MAP_KEY, key ) ) ) return sentinel;
708 : # else
709 2166141 : if( FD_UNLIKELY( MAP_(key_eq)( &ele->MAP_KEY, key ) ) ) return sentinel;
710 373212 : # endif
711 :
712 373212 : return MAP_(private_insert)( join, key, memo, sentinel );
713 2166141 : }
714 :
715 : static inline MAP_ELE_T *
716 : MAP_(upsert_fast)( MAP_(t) * join,
717 : MAP_KEY_T const * key,
718 : ulong memo,
719 5623221 : MAP_ELE_T * sentinel ) {
720 : # if FD_TMPL_USE_HANDHOLDING
721 : FD_TEST( memo==MAP_(key_hash)( key, join->seed ) );
722 : # endif
723 :
724 5623221 : ulong ele_idx = memo & join->ele_mask;
725 :
726 5623221 : MAP_ELE_T * ele = join->ele0 + ele_idx;
727 :
728 5623221 : if( FD_UNLIKELY( MAP_(ele_is_free)( ele ) ) ) {
729 : # if MAP_MEMOIZE
730 : ele->MAP_MEMO = memo;
731 : # endif
732 3453216 : ele->MAP_KEY = *key;
733 3453216 : return ele;
734 3453216 : }
735 :
736 : # if MAP_MEMOIZE && MAP_KEY_EQ_IS_SLOW
737 : if( FD_LIKELY( ele->MAP_MEMO==memo ) && FD_LIKELY( MAP_(key_eq)( &ele->MAP_KEY, key ) ) ) return ele;
738 : # else
739 2170005 : if( FD_LIKELY( MAP_(key_eq)( &ele->MAP_KEY, key ) ) ) return ele;
740 373539 : # endif
741 :
742 373539 : return MAP_(private_upsert)( join, key, memo, sentinel );
743 2170005 : }
744 :
745 : /* Note that this is just a const correct version of update */
746 :
747 : FD_FN_PURE static inline MAP_ELE_T const *
748 : MAP_(query_fast)( MAP_(t) const * join,
749 : MAP_KEY_T const * key,
750 : ulong memo,
751 1872105 : MAP_ELE_T const * sentinel ) {
752 1872105 : return MAP_(update_fast)( (MAP_(t) *)join, key, memo, (MAP_ELE_T *)sentinel );
753 1872105 : }
754 :
755 : /* Basic APIs *********************************************************/
756 :
757 : FD_FN_PURE static inline MAP_ELE_T const *
758 : MAP_(query)( MAP_(t) const * join,
759 1874175 : MAP_KEY_T const * key ) {
760 1874175 : return MAP_(update_fast)( (MAP_(t) *)join, key, MAP_(key_hash)( key, join->seed ), NULL );
761 1874175 : }
762 :
763 : FD_FN_PURE static inline MAP_ELE_T *
764 : MAP_(update)( MAP_(t) * join,
765 9367257 : MAP_KEY_T const * key ) {
766 9367257 : return MAP_(update_fast)( join, key, MAP_(key_hash)( key, join->seed ), NULL );
767 9367257 : }
768 :
769 : static inline MAP_ELE_T *
770 : MAP_(insert)( MAP_(t) * join,
771 2810079 : MAP_KEY_T const * key ) {
772 2810079 : return MAP_(insert_fast)( join, key, MAP_(key_hash)( key, join->seed ), NULL );
773 2810079 : }
774 :
775 : static inline MAP_ELE_T *
776 : MAP_(upsert)( MAP_(t) * join,
777 2810085 : MAP_KEY_T const * key ) {
778 2810085 : return MAP_(upsert_fast)( join, key, MAP_(key_hash)( key, join->seed ), NULL );
779 2810085 : }
780 :
781 : static inline void
782 : MAP_(remove)( MAP_(t) * join,
783 3746628 : MAP_ELE_T * ele ) {
784 3746628 : MAP_ELE_T * ele0 = join->ele0;
785 3746628 : ulong ele_mask = join->ele_mask;
786 3746628 : ulong hole_idx = (ulong)(ele - ele0);
787 :
788 : # if FD_TMPL_USE_HANDHOLDING
789 : FD_TEST( fd_ulong_is_aligned( (ulong)ele0, alignof(MAP_ELE_T) ) );
790 : FD_TEST( ele0<=ele );
791 : FD_TEST( ele<=(ele0+ele_mask) );
792 : FD_TEST( !MAP_(ele_is_free( ele ) ) );
793 : # endif
794 :
795 3746628 : MAP_(private_ele_free)( join->ctx, ele );
796 :
797 3746628 : if( FD_UNLIKELY( !MAP_(ele_is_free)( &ele0[ (hole_idx+1UL) & ele_mask ] ) ) ) MAP_(private_remove)( join, hole_idx );
798 3746628 : }
799 :
800 : FD_FN_PURE static inline int
801 : MAP_(iter_done)( MAP_(t) const * join,
802 : ulong memo,
803 1868109 : MAP_(iter_t) iter ) {
804 1868109 : (void)memo;
805 1868109 : return iter > join->probe_rem;
806 1868109 : }
807 :
808 : FD_FN_PURE static inline MAP_(iter_t)
809 : MAP_(iter_next)( MAP_(t) const * join,
810 : ulong memo,
811 1868109 : MAP_(iter_t) iter ) {
812 1868109 : MAP_ELE_T const * ele0 = join->ele0;
813 1868109 : ulong ele_mask = join->ele_mask;
814 1868109 : ulong probe_rem = join->probe_rem;
815 1868109 : ulong seed = join->seed; (void)seed;
816 :
817 2043519 : for(;;) {
818 2043519 : iter++;
819 2043519 : if( FD_UNLIKELY( iter>probe_rem ) ) break;
820 2043519 : MAP_ELE_T const * ele = ele0 + ((memo + iter) & ele_mask);
821 2043519 : if( FD_LIKELY( MAP_(ele_is_free)( ele ) ) ) {
822 935094 : iter = probe_rem + 1UL;
823 935094 : break;
824 935094 : }
825 : # if MAP_MEMOIZE
826 : if( FD_LIKELY( ele->MAP_MEMO==memo ) ) break;
827 : # else
828 1108425 : if( FD_LIKELY( MAP_(key_hash)( &ele->MAP_KEY, seed )==memo ) ) break;
829 1108425 : # endif
830 1108425 : }
831 :
832 1868109 : return iter;
833 1868109 : }
834 :
835 : FD_FN_PURE static inline MAP_(iter_t)
836 : MAP_(iter_init)( MAP_(t) const * join,
837 935094 : ulong memo ) {
838 935094 : return MAP_(iter_next)( join, memo, -1UL );
839 935094 : }
840 :
841 : FD_FN_PURE static inline MAP_ELE_T const *
842 : MAP_(iter_ele_const)( MAP_(t) const * join,
843 : ulong memo,
844 933015 : MAP_(iter_t) iter ) {
845 933015 : (void)memo;
846 933015 : return join->ele0 + ((memo + iter) & join->ele_mask);
847 933015 : }
848 :
849 : FD_FN_PURE static inline MAP_ELE_T *
850 : MAP_(iter_ele)( MAP_(t) * join,
851 : ulong memo,
852 933015 : MAP_(iter_t) iter ) {
853 933015 : (void)memo;
854 933015 : return join->ele0 + ((memo + iter) & join->ele_mask);
855 933015 : }
856 :
857 : MAP_STATIC int MAP_(verify)( MAP_(t) const * join );
858 :
859 : FD_PROTOTYPES_END
860 :
861 : #endif
862 :
863 : #if MAP_IMPL_STYLE!=1 /* need implementations (assumes header already included) */
864 :
865 : #include "../log/fd_log.h" /* Used by constructors and verify (FIXME: Consider making a compile time option) */
866 :
867 : MAP_ELE_T *
868 : MAP_(new)( void * shmem,
869 : ulong ele_max,
870 81 : int reset ) {
871 :
872 81 : if( FD_UNLIKELY( !shmem ) ) {
873 3 : FD_LOG_WARNING(( "NULL shmem" ));
874 3 : return NULL;
875 3 : }
876 :
877 78 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, MAP_(align)() ) ) ) {
878 3 : FD_LOG_WARNING(( "misaligned shmem" ));
879 3 : return NULL;
880 3 : }
881 :
882 75 : ulong footprint = MAP_(footprint)( ele_max );
883 75 : if( FD_UNLIKELY( !footprint ) ) {
884 6 : FD_LOG_WARNING(( "bad ele_max" ));
885 6 : return NULL;
886 6 : }
887 :
888 69 : MAP_ELE_T * ele0 = (MAP_ELE_T *)shmem;
889 :
890 69 : if( reset ) memset( ele0, 0, footprint );
891 :
892 69 : return ele0;
893 75 : }
894 :
895 : MAP_(t) *
896 : MAP_(join)( void * lmem,
897 : MAP_ELE_T * ele0,
898 : ulong ele_max,
899 : ulong probe_max,
900 96 : ulong seed ) {
901 :
902 96 : if( FD_UNLIKELY( !lmem ) ) {
903 3 : FD_LOG_WARNING(( "NULL lmem" ));
904 3 : return NULL;
905 3 : }
906 :
907 93 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)lmem, alignof(MAP_(t)) ) ) ) {
908 3 : FD_LOG_WARNING(( "misaligned lmem" ));
909 3 : return NULL;
910 3 : }
911 :
912 90 : if( FD_UNLIKELY( !ele0 ) ) {
913 3 : FD_LOG_WARNING(( "NULL ele0" ));
914 3 : return NULL;
915 3 : }
916 :
917 87 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)ele0, MAP_(align)() ) ) ) {
918 3 : FD_LOG_WARNING(( "misaligned ele0" ));
919 3 : return NULL;
920 3 : }
921 :
922 84 : ulong footprint = MAP_(footprint)( ele_max );
923 84 : if( FD_UNLIKELY( !footprint ) ) {
924 6 : FD_LOG_WARNING(( "bad ele_max" ));
925 6 : return NULL;
926 6 : }
927 :
928 78 : if( FD_UNLIKELY( !((1UL<=probe_max) & (probe_max<=ele_max)) ) ) {
929 6 : FD_LOG_WARNING(( "bad probe_max" ));
930 6 : return NULL;
931 6 : }
932 :
933 : /* seed is arbitrary */
934 :
935 72 : MAP_(t) * join = (MAP_(t) *)lmem;
936 :
937 72 : memset( join, 0, sizeof(MAP_(t)) ); /* note: clears user context */
938 :
939 72 : join->ele0 = ele0;
940 72 : join->ele_mask = ele_max - 1UL;
941 72 : join->probe_rem = probe_max - 1UL;
942 72 : join->seed = seed;
943 :
944 72 : return join;
945 78 : }
946 :
947 : void *
948 51 : MAP_(leave)( MAP_(t) * join ) {
949 :
950 51 : if( FD_UNLIKELY( !join ) ) {
951 3 : FD_LOG_WARNING(( "NULL join" ));
952 3 : return NULL;
953 3 : }
954 :
955 48 : return (void *)join;
956 51 : }
957 :
958 : void *
959 9 : MAP_(delete)( MAP_ELE_T * ele0 ) {
960 :
961 9 : if( FD_UNLIKELY( !ele0 ) ) {
962 3 : FD_LOG_WARNING(( "NULL ele0" ));
963 3 : return NULL;
964 3 : }
965 :
966 6 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)ele0, alignof(MAP_ELE_T) ) ) ) {
967 3 : FD_LOG_WARNING(( "misaligned ele0" ));
968 3 : return NULL;
969 3 : }
970 :
971 3 : return ele0;
972 6 : }
973 :
974 : MAP_ELE_T *
975 : MAP_(private_update)( MAP_(t) * join,
976 : MAP_KEY_T const * key,
977 : ulong memo,
978 893985 : MAP_ELE_T * sentinel ) {
979 :
980 893985 : MAP_ELE_T * ele0 = join->ele0;
981 893985 : ulong ele_mask = join->ele_mask;
982 :
983 : /* Note that the fast path did the first probe (and it collided) */
984 :
985 893985 : ulong ele_idx = (memo+1UL) & ele_mask;
986 1074621 : for( ulong rem=join->probe_rem; rem; rem-- ) {
987 1074621 : MAP_ELE_T * ele = ele0 + ele_idx;
988 :
989 1074621 : if( FD_UNLIKELY( MAP_(ele_is_free)( ele ) ) ) break;
990 :
991 : # if MAP_MEMOIZE && MAP_KEY_EQ_IS_SLOW
992 : if( FD_LIKELY( ele->MAP_MEMO==memo ) && FD_LIKELY( MAP_(key_eq)( &ele->MAP_KEY, key ) ) ) return ele;
993 : # else
994 477954 : if( FD_LIKELY( MAP_(key_eq)( &ele->MAP_KEY, key ) ) ) return ele;
995 180636 : # endif
996 :
997 180636 : ele_idx = (ele_idx+1UL) & ele_mask;
998 180636 : }
999 :
1000 596667 : return sentinel;
1001 893985 : }
1002 :
1003 : MAP_ELE_T *
1004 : MAP_(private_insert)( MAP_(t) * join,
1005 : MAP_KEY_T const * key,
1006 : ulong memo,
1007 373212 : MAP_ELE_T * sentinel ) {
1008 :
1009 373212 : MAP_ELE_T * ele0 = join->ele0;
1010 373212 : ulong ele_mask = join->ele_mask;
1011 :
1012 : /* Note that the fast path did the first probe (and it collided) */
1013 :
1014 373212 : ulong ele_idx = (memo+1UL) & ele_mask;
1015 451533 : for( ulong rem=join->probe_rem; rem; rem-- ) {
1016 451533 : MAP_ELE_T * ele = ele0 + ele_idx;
1017 :
1018 451533 : if( FD_LIKELY( MAP_(ele_is_free)( ele ) ) ) {
1019 : # if MAP_MEMOIZE
1020 : ele->MAP_MEMO = memo;
1021 : # endif
1022 298725 : ele->MAP_KEY = *key;
1023 298725 : return ele;
1024 298725 : }
1025 :
1026 : # if MAP_MEMOIZE && MAP_KEY_EQ_IS_SLOW
1027 : if( FD_UNLIKELY( ele->MAP_MEMO==memo ) && FD_UNLIKELY( MAP_(key_eq)( &ele->MAP_KEY, key ) ) ) return sentinel;
1028 : # else
1029 152808 : if( FD_UNLIKELY( MAP_(key_eq)( &ele->MAP_KEY, key ) ) ) return sentinel;
1030 78321 : # endif
1031 :
1032 78321 : ele_idx = (ele_idx+1UL) & ele_mask;
1033 78321 : }
1034 :
1035 0 : return sentinel;
1036 373212 : }
1037 :
1038 : MAP_ELE_T *
1039 : MAP_(private_upsert)( MAP_(t) * join,
1040 : MAP_KEY_T const * key,
1041 : ulong memo,
1042 373539 : MAP_ELE_T * sentinel ) {
1043 :
1044 373539 : MAP_ELE_T * ele0 = join->ele0;
1045 373539 : ulong ele_mask = join->ele_mask;
1046 :
1047 : /* Note that the fast path did the first probe */
1048 :
1049 373539 : ulong ele_idx = (memo+1UL) & ele_mask;
1050 453057 : for( ulong rem=join->probe_rem; rem; rem-- ) {
1051 453057 : MAP_ELE_T * ele = ele0 + ele_idx;
1052 :
1053 453057 : if( FD_UNLIKELY( MAP_(ele_is_free)( ele ) ) ) {
1054 : # if MAP_MEMOIZE
1055 : ele->MAP_MEMO = memo;
1056 : # endif
1057 298509 : ele->MAP_KEY = *key;
1058 298509 : return ele;
1059 298509 : }
1060 :
1061 : # if MAP_MEMOIZE && MAP_KEY_EQ_IS_SLOW
1062 : if( FD_LIKELY( ele->MAP_MEMO==memo ) && FD_LIKELY( MAP_(key_eq)( &ele->MAP_KEY, key ) ) ) return ele;
1063 : # else
1064 154548 : if( FD_LIKELY( MAP_(key_eq)( &ele->MAP_KEY, key ) ) ) return ele;
1065 79518 : # endif
1066 :
1067 79518 : ele_idx = (ele_idx+1UL) & ele_mask;
1068 79518 : }
1069 :
1070 0 : return sentinel;
1071 373539 : }
1072 :
1073 : void
1074 : MAP_(private_remove)( MAP_(t) * join,
1075 423753 : ulong hole_idx ) {
1076 :
1077 423753 : MAP_ELE_T * ele0 = join->ele0;
1078 423753 : ulong ele_mask = join->ele_mask;
1079 423753 : ulong seed = join->seed; (void)seed;
1080 423753 : void * ctx = join->ctx; (void)ctx;
1081 :
1082 : /* At this point, element hole is free, we need to repair any broken
1083 : probe sequences for all contiguously occupied slots following
1084 : element hole and the first element following hole is occupied. */
1085 :
1086 423753 : ulong ele_idx = (hole_idx+1UL) & ele_mask;
1087 :
1088 538029 : do {
1089 :
1090 : # if MAP_MEMOIZE
1091 : ulong start_idx = ele0[ ele_idx ].MAP_MEMO & ele_mask;
1092 : # else
1093 538029 : ulong start_idx = MAP_(key_hash)( &ele0[ ele_idx ].MAP_KEY, seed ) & ele_mask;
1094 538029 : # endif
1095 :
1096 538029 : if( !( ((hole_idx<start_idx) & (start_idx<=ele_idx) ) |
1097 538029 : ((hole_idx>ele_idx) & ((hole_idx<start_idx) | (start_idx<=ele_idx))) ) ) {
1098 :
1099 178689 : MAP_(private_ele_move)( ctx, ele0 + hole_idx, ele0 + ele_idx );
1100 :
1101 178689 : hole_idx = ele_idx;
1102 :
1103 178689 : }
1104 :
1105 538029 : ele_idx = (ele_idx+1UL) & ele_mask;
1106 :
1107 538029 : } while( !MAP_(ele_is_free)( &ele0[ ele_idx ] ) );
1108 423753 : }
1109 :
1110 : int
1111 33 : MAP_(verify)( MAP_(t) const * join ) {
1112 :
1113 37617 : # define MAP_TEST(c) do { \
1114 37617 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
1115 37617 : } while(0)
1116 :
1117 : /* Validate join */
1118 :
1119 33 : MAP_TEST( join );
1120 33 : MAP_TEST( fd_ulong_is_aligned( (ulong)join, alignof(MAP_(t)) ) );
1121 :
1122 33 : MAP_ELE_T const * ele0 = join->ele0;
1123 33 : ulong ele_mask = join->ele_mask;
1124 33 : ulong probe_rem = join->probe_rem;
1125 33 : ulong seed = join->seed;
1126 :
1127 33 : ulong ele_max = ele_mask + 1UL;
1128 33 : ulong probe_max = probe_rem + 1UL;
1129 :
1130 33 : MAP_TEST( ele0 );
1131 33 : MAP_TEST( fd_ulong_is_aligned( (ulong)ele0, alignof(MAP_ELE_T) ) );
1132 33 : MAP_TEST( ele_max <= (ULONG_MAX / sizeof(MAP_ELE_T)) );
1133 33 : MAP_TEST( fd_ulong_is_pow2( ele_max ) );
1134 33 : MAP_TEST( (1UL<=probe_max) & (probe_max<=ele_max) );
1135 : /* seed is arbitrary */
1136 :
1137 : /* Validate map elements */
1138 :
1139 135201 : for( ulong ele_idx=0UL; ele_idx<ele_max; ele_idx++ ) {
1140 135168 : MAP_ELE_T const * ele = ele0 + ele_idx;
1141 135168 : if( FD_LIKELY( MAP_(ele_is_free)( ele ) ) ) continue; /* opt for sparse */
1142 :
1143 11616 : ulong memo = MAP_(key_hash)( &ele->MAP_KEY, seed );
1144 :
1145 : # if MAP_MEMOIZE
1146 : MAP_TEST( ele->MAP_MEMO==memo );
1147 : # endif
1148 :
1149 11616 : ulong probe_idx = memo & ele_mask;
1150 11616 : ulong probe_cnt = fd_ulong_if( ele_idx>=probe_idx, ele_idx - probe_idx, ele_max + ele_idx - probe_idx ) + 1UL;
1151 11616 : MAP_TEST( probe_cnt<=probe_max );
1152 :
1153 24501 : for( ulong probe_rem=probe_cnt; probe_rem; probe_rem-- ) {
1154 12885 : MAP_ELE_T const * probe = ele0 + probe_idx;
1155 12885 : MAP_TEST( !MAP_(ele_is_free)( probe ) );
1156 :
1157 12885 : int found =
1158 : # if MAP_MEMOIZE && MAP_KEY_EQ_IS_SLOW
1159 : FD_LIKELY( probe->MAP_MEMO == ele->MAP_MEMO ) &&
1160 : # endif
1161 12885 : MAP_(key_eq)( &probe->MAP_KEY, &ele->MAP_KEY );
1162 :
1163 12885 : MAP_TEST( (probe_rem==1UL) ? found : !found );
1164 :
1165 12885 : probe_idx = (probe_idx+1UL) & ele_mask;
1166 12885 : }
1167 11616 : }
1168 :
1169 : /* At this point, every key in the map is reachable via it's probe
1170 : sequence and every probe sequence is at most probe_max probes long.
1171 : By extension, if a key is in the map, it will be found in at most
1172 : probe_max probes. */
1173 :
1174 33 : # undef MAP_TEST
1175 :
1176 33 : return 0;
1177 33 : }
1178 :
1179 : #endif
1180 :
1181 : #undef MAP_
1182 : #undef MAP_STATIC
1183 :
1184 : #undef MAP_IMPL_STYLE
1185 : #undef MAP_PREFETCH
1186 : #undef MAP_CTX_MAX
1187 : #undef MAP_ELE_MOVE
1188 : #undef MAP_ELE_FREE
1189 : #undef MAP_ELE_IS_FREE
1190 : #undef MAP_KEY_EQ_IS_SLOW
1191 : #undef MAP_MEMO
1192 : #undef MAP_MEMOIZE
1193 : #undef MAP_KEY_HASH
1194 : #undef MAP_KEY_EQ
1195 : #undef MAP_KEY
1196 : #undef MAP_KEY_T
1197 : #undef MAP_ELE_T
1198 : #undef MAP_NAME
|
