Line data Source code
1 : /* Generate prototypes, inlines and/or implementations for ultra high
2 : performance maps based on hash chains. A map can store a practically
3 : unbounded number of elements but, if sized on creation for the
4 : maximum number of mapped elements, typical map operations are a fast
5 : O(1) time and map element overhead is a small O(1) space.
6 :
7 : This API is designed for ultra tight coupling with pools, treaps,
8 : heaps, lists, other maps, etc. Likewise, a map can be persisted
9 : beyond the lifetime of the creating process, used concurrently in
10 : many common operations, used inter-process, relocated in memory,
11 : naively serialized/deserialized, moved between hosts, supports index
12 : compression for cache and memory bandwidth efficiency, etc.
13 :
14 : Memory efficiency and flexible footprint are prioritized. Elements
15 : that are recently queried can be optionally moved to the front of
16 : hash chains to adaptively optimize the maps for recent queries in
17 : non-concurrent use cases.
18 :
19 : Typical usage:
20 :
21 : struct myele {
22 : ulong key; // Technically "MAP_KEY_T MAP_KEY" (default is ulong key), do not modify while the element is in the map
23 : ulong next; // Technically "MAP_IDX_T MAP_NEXT" (default is ulong next), do not modify while the element is in the map
24 : ... key and next can be located arbitrarily in the element and
25 : ... can be reused for other purposes when the element is not in a
26 : ... map. The mapping of a key to an element storage index is
27 : ... arbitrary but an element should not be moved / released while
28 : ... an element is in a map.
29 : };
30 :
31 : typedef struct myele myele_t;
32 :
33 : #define MAP_NAME mymap
34 : #define MAP_ELE_T myele_t
35 : #include "tmpl/fd_map_chain.c"
36 :
37 : will declare the following APIs as a header only style library in the
38 : compilation unit:
39 :
40 : // mymap_ele_max returns the theoretical maximum number of elements
41 : // that can be mapped by a mymap.
42 :
43 : ulong mymap_ele_max( void );
44 :
45 : // mymap_chain_max returns the theoretical maximum number possible
46 : // chains in a mymap. Will be an integer power-of-two.
47 :
48 : ulong mymap_chain_max( void );
49 :
50 : // mymap_chain_cnt_est returns a reasonable number of chains to use
51 : // for a map that is expected to hold up to ele_max_est elements.
52 : // ele_max_est will be clamped to be in [1,mymap_ele_max()] and the
53 : // return value will be a integer power-of-two in
54 : // [1,mymap_chain_max()].
55 :
56 : ulong mymap_chain_cnt_est( ulong ele_max_est );
57 :
58 : // mymap_{align,footprint} returns the alignment and footprint
59 : // needed for a memory region to be used as a mymap. align will be
60 : // an integer power-of-two and footprint will be a multiple of
61 : // align. footprint returns 0 if chain_cnt is not an integer
62 : // power-of-two in [1,mymap_chain_max()].
63 : //
64 : // mymap_new formats a memory region with the appropriate alignment
65 : // and footprint whose first byte in the caller's address space is
66 : // pointed by shmem for use as a mymap. Returns shmem on success
67 : // and NULL on failure (logs details). Caller is not joined on
68 : // return. The map will be empty.
69 : //
70 : // mymap_join joins a mymap. Assumes shmap points at a memory
71 : // region formatted as a mymap in the caller's address space.
72 : // Returns a handle to the caller's local join on success and NULL
73 : // on failure (logs details). Do not assume this is a simple cast
74 : // of shmap!
75 : //
76 : // mymap_leave leaves a mymap. Assumes join points to a current
77 : // local join. Returns shmap used on join. Do not assume this is
78 : // a simple cast of join!
79 : //
80 : // mymap_delete unformats a memory region used as a mymap. Assumes
81 : // shmap points to a memory region in the caller's local address
82 : // space formatted as a mymap, that there are no joins to the mymap
83 : // and that any application cleanup of the entries has already been
84 : // done. Returns shmap on success and NULL on failure.
85 :
86 : ulong mymap_align ( void );
87 : ulong mymap_footprint( ulong chain_cnt );
88 : void * mymap_new ( void * shmem, ulong chain_cnt, ulong seed );
89 : mymap_t * mymap_join ( void * shmap );
90 : void * mymap_leave ( mymap_t * join );
91 : void * mymap_delete ( void * shmap );
92 :
93 : // mymap_{chain_cnt,seed} return the values used to construct the
94 : // map. They assume join is a current local join. The values will
95 : // be constant for the map lifetime.
96 :
97 : ulong mymap_chain_cnt( mymap_t const * join );
98 : ulong mymap_seed ( mymap_t const * join );
99 :
100 : // mymap_key_{eq,hash} expose the provided MAP_KEY_{EQ,HASH} macros
101 : // as inline functions with strict semantics. They assume that the
102 : // provided pointers are in the caller's address space to keys that
103 : // will not be changed concurrently. They retain no interest in
104 : // any keys on return.
105 : //
106 : // mymap_key_eq returns 1 if *k0 and *k1 are equal and 0 otherwise.
107 : //
108 : // mymap_key_hash returns the hash of *key using the hash function
109 : // seed. Should ideally be a random mapping from MAP_KEY_T to
110 : // ulong but this depends on what the user actually passed in for
111 : // MAP_KEY_HASH. The seed used by a particular instance of a map
112 : // can be obtained above.
113 :
114 : int mymap_key_eq ( ulong * k0, ulong * k1 );
115 : ulong mymap_key_hash( ulong * key, ulong seed );
116 :
117 : // mymap_idx_insert inserts an element into the map. The caller
118 : // promises the element is not currently in the map and that
119 : // element key is not equal to the key of any other element
120 : // currently in the map. Assumes there are no concurrent
121 : // operations on the map. This always succeeds.
122 :
123 : mymap_t * // Returns join
124 : mymap_idx_insert( mymap_t * join, // Current local join to element map
125 : ulong ele_idx, // Index of element to insert
126 : myele_t * pool ); // Current local join to element storage
127 :
128 : // mymap_idx_remove removes the mapping of a key to an element.
129 : // Assumes there are no concurrent operations on the map and that
130 : // *key will not be modified during the remove. The map retains no
131 : // interest in key. On success, the map will no longer have an
132 : // interest in the returned element. On failure, the returned
133 : // index lifetime will be that of the sentinel.
134 :
135 : ulong // Index of removed element on success, sentinel on failure
136 : mymap_idx_remove( mymap_t * join, // Current local join to element map
137 : ulong const * key, // Points to the key to remove in the caller's address space
138 : ulong sentinel, // Value to return if key not in map
139 : myele_t * pool ); // Current local join to element storage
140 :
141 : // mymap_idx_query finds the element corresponding to key. Assumes
142 : // there are no concurrent operations on the map and that *key will
143 : // not be modified during the query. The map retains no interest
144 : // in key. On success, the returned index lifetime will be at
145 : // least as long as the corresponding element is still in the map.
146 : // On failure, the returned index lifetime will be that of the
147 : // sentinel.
148 :
149 : ulong // Index of found element on success, sentinel on failure
150 : mymap_idx_query( mymap_t * join, // Current local join to the element map
151 : ulong const * key, // Points to the key to find in the caller's address space
152 : ulong sentinel, // Value to return on failure
153 : myele_t * pool ); // Current local join to element storage
154 :
155 : // mymap_idx_query_const is the same as mymap_idx_query but
156 : // supports concurrent queries so long as there no concurrently
157 : // running insert/remove/query operations. The value fields of the
158 : // element returned by this function can be changed by the
159 : // application but it is up to the application to manage
160 : // concurrency between different users modifying the same element.
161 :
162 : ulong // Index of found element on success, sentinel on failure
163 : mymap_idx_query_const( mymap_t const * join, // Current local join to element map
164 : ulong const * key, // Points to the key to find in the caller's address space
165 : ulong sentinel, // Value to return on failure
166 : myele_t const * pool ); // Current local join to element storage
167 :
168 : // The mymap_ele_{insert,remove,query,query_const} variants are the
169 : // same as the above but use pointers in the caller's address
170 : // instead of pool element storage indices.
171 :
172 : mymap_t * // Returns join
173 : mymap_ele_insert( mymap_t * join, // Current local join to element map
174 : myele_t * ele, // Element to insert (assumed to be in pool)
175 : myele_t * pool ); // Current local join to element storage
176 :
177 : myele_t * // Removed element on success (will be from pool), sentinel on failure
178 : mymap_ele_remove( mymap_t * join, // Current local join to element map
179 : ulong const * key, // Points to the key to remove in the caller's address space
180 : myele_t * sentinel, // Value to return if key not in map
181 : myele_t * pool ); // Current local join to element storage
182 :
183 : myele_t * // Found element on success (will be from pool), sentinel on failure
184 : mymap_ele_query( mymap_t * join, // Current local join to element map
185 : ulong const * key, // Points to the key to find in the caller's address space
186 : myele_t * sentinel, // Value to return if key not in map
187 : myele_t * pool ); // Current local join to element storage
188 :
189 : myele_t const * // Found element on success (will be from pool), sentinel on failure
190 : mymap_ele_query_const( mymap_t const * join, // Current local join to element map
191 : ulong const * key, // Points to the key to find in the caller's address space
192 : myele_t const * sentinel, // Value to return if key not in map
193 : myele_t const * pool ); // Current local join to element storage
194 :
195 : // mymap_iter_* support fast iteration over all the elements in a
196 : // map. The iteration will be in a random order but the order will
197 : // be identical if repeated with no insert/remove/query operations
198 : // done in between. Assumes no concurrent insert/remove/query
199 : // operations (query_const is fine). Example usage:
200 : //
201 : // for( mymap_iter_t iter = mymap_iter_init( join, pool );
202 : // !mymap_iter_done( iter, join, pool );
203 : // iter = mymap_iter_next( iter, join, pool ) ) {
204 : // ulong ele_idx = mymap_iter_idx( iter, join, pool );
205 : //
206 : // ... process element here
207 : //
208 : // ... IMPORTANT! It is _not_ _safe_ to insert, remove
209 : // ... or query here (query_const is fine).
210 : // }
211 :
212 : struct mymap_iter_private { ... internal use only ... };
213 : typedef struct mymap_iter_private mymap_iter_t;
214 :
215 : mymap_iter_t mymap_iter_init ( mymap_t const * join, myele_t const * pool );
216 : int mymap_iter_done ( mymap_iter_t iter, mymap_t const * join, myele_t const * pool );
217 : mymap_iter_t mymap_iter_next ( mymap_iter_t iter, mymap_t const * join, myele_t const * pool ); // assumes not done
218 : ulong mymap_iter_idx ( mymap_iter_t iter, mymap_t const * join, myele_t const * pool ); // assumes not done
219 : myele_t * mymap_iter_ele ( mymap_iter_t iter, mymap_t const * join, myele_t * pool ); // assumes not done
220 : myele_t const * mymap_iter_ele_const( mymap_iter_t iter, mymap_t const * join, myele_t const * pool ); // assumes not done
221 :
222 : // mymap_verify returns 0 if the mymap is not obviously corrupt or
223 : // -1 (i.e. ERR_INVAL) otherwise (logs details).
224 :
225 : int
226 : mymap_verify( mymap_t const * join, // Current local join to a mymap.
227 : ulong ele_cnt, // Element storage size, in [0,mymap_ele_max()]
228 : myele_t const * pool ); // Current local join to element storage, indexed [0,ele_cnt)
229 :
230 : You can do this as often as you like in a compilation unit to get
231 : different types of maps. Variants exist for making header prototypes
232 : only and/or implementations if doing a library with multiple
233 : compilation units. Further, options exist to use index compression,
234 : different hashing functions, comparison functions, etc as detailed
235 : below.
236 :
237 : If MAP_MULTI is defined to be 1, the map will support multiple
238 : entries for the same key. In this case, the existing API works as
239 : is, but new methods are provided:
240 :
241 : ulong // Index of found element on success, sentinel on failure
242 : mymap_idx_next_const( ulong prev, // Previous result of mymap_idx_query_const
243 : ulong sentinel, // Value to return on failure
244 : myele_t const * pool ); // Current local join to element storage
245 :
246 : myele_t const * // Found element on success (will be from pool), sentinel on failure
247 : mymap_ele_next_const( myele_t const * prev, // Previous result of mymap_ele_query_const
248 : myele_t const * sentinel, // Value to return if key not in map
249 : myele_t const * pool ); // Current local join to element storage
250 :
251 : These take a previous result from query_const (or next_const) and
252 : return the next element with the same key in the chain.
253 : */
254 :
255 : /* MAP_NAME gives the API prefix to use for map */
256 :
257 : #ifndef MAP_NAME
258 : #error "Define MAP_NAME"
259 : #endif
260 :
261 : /* MAP_ELE_T is the map element type. */
262 :
263 : #ifndef MAP_ELE_T
264 : #error "Define MAP_ELE_T"
265 : #endif
266 :
267 : /* MAP_KEY_T is the map key type */
268 :
269 : #ifndef MAP_KEY_T
270 : #define MAP_KEY_T ulong
271 : #endif
272 :
273 : /* MAP_KEY is the MAP_ELE_T key field */
274 :
275 : #ifndef MAP_KEY
276 0 : #define MAP_KEY key
277 : #endif
278 :
279 : /* MAP_IDX_T is the type used for the next field in the MAP_ELE_T.
280 : Should be a primitive unsigned integer type. Defaults to ulong. A
281 : map can't use element stores with more elements than the maximum
282 : value that can be represented by a MAP_IDX_T. (E.g. if ushort, the
283 : maximum size element store usable by the map is 65535 elements.) */
284 :
285 : #ifndef MAP_IDX_T
286 0 : #define MAP_IDX_T ulong
287 : #endif
288 :
289 : /* MAP_NEXT is the MAP_ELE_T next field */
290 :
291 : #ifndef MAP_NEXT
292 0 : #define MAP_NEXT next
293 : #endif
294 :
295 : /* MAP_KEY_EQ returns 0/1 if *k0 is the same/different as *k1 */
296 :
297 : #ifndef MAP_KEY_EQ
298 5651997804 : #define MAP_KEY_EQ(k0,k1) ((*(k0))==(*(k1)))
299 : #endif
300 :
301 : /* MAP_KEY_HASH maps *key into ulong uniform pseudo randomly. */
302 :
303 : #ifndef MAP_KEY_HASH
304 0 : #define MAP_KEY_HASH(key,seed) fd_ulong_hash( (*(key)) ^ (seed) )
305 : #endif
306 :
307 : /* MAP_MAGIC is the magic number to use for the structure to aid in
308 : persistent and or IPC usage. */
309 :
310 : #ifndef MAP_MAGIC
311 6 : #define MAP_MAGIC (0xf17eda2c37c3a900UL) /* firedancer cmap version 0 */
312 : #endif
313 :
314 : /* 0 - local use only
315 : 1 - library header declaration
316 : 2 - library implementation */
317 :
318 : #ifndef MAP_IMPL_STYLE
319 : #define MAP_IMPL_STYLE 0
320 : #endif
321 :
322 : /* 0 - do NOT support multiple values with the same key
323 : 1 - support multiple values with the same key */
324 :
325 : #ifndef MAP_MULTI
326 : #define MAP_MULTI 0
327 : #endif
328 :
329 : /* Implementation *****************************************************/
330 :
331 : /* Constructors and verification log details on failure (rest only needs
332 : fd_bits.h, consider making logging a compile time option). */
333 :
334 : #include "../log/fd_log.h"
335 :
336 41637022824 : #define MAP_(n) FD_EXPAND_THEN_CONCAT3(MAP_NAME,_,n)
337 :
338 : #if MAP_IMPL_STYLE==0 || MAP_IMPL_STYLE==1 /* need structures and inlines */
339 :
340 : struct MAP_(private) {
341 :
342 : /* join points here */
343 :
344 : /* FIXME: consider having an ele_cnt for number of elements in the
345 : underlying storage? (probably not) consider having a memo of the
346 : chain in which an element is stored and/or using doubly linked
347 : chains? We could do a faster remove by index then. */
348 :
349 : ulong magic; /* == MAP_MAGIC */
350 : ulong seed; /* Hash seed, arbitrary */
351 : ulong chain_cnt; /* Number of chains, positive integer power-of-two */
352 :
353 : /* MAP_IDX_T chain[ chain_cnt ] here */
354 :
355 : };
356 :
357 : typedef struct MAP_(private) MAP_(private_t);
358 :
359 : typedef MAP_(private_t) MAP_(t);
360 :
361 : struct MAP_(iter) {
362 : ulong chain_rem;
363 : ulong ele_idx;
364 : };
365 :
366 : typedef struct MAP_(iter) MAP_(iter_t);
367 :
368 : FD_PROTOTYPES_BEGIN
369 :
370 : /* map_private returns the location of the map private for a current
371 : local join. Assumes join is a current local join. map_private_const
372 : is a const correct version. */
373 :
374 1192704000 : FD_FN_CONST static inline MAP_(private_t) * MAP_(private) ( MAP_(t) * join ) { return join; }
375 2582811585 : FD_FN_CONST static inline MAP_(private_t) const * MAP_(private_const)( MAP_(t) const * join ) { return join; }
376 :
377 : /* map_private_chain returns the location in the caller's address space
378 : of the map chains. Assumes map is valid. map_private_chain_const is
379 : a const correct version. */
380 :
381 : FD_FN_CONST static inline MAP_IDX_T *
382 1192704006 : MAP_(private_chain)( MAP_(private_t) * map ) {
383 1192704006 : return (MAP_IDX_T *)(map+1);
384 1192704006 : }
385 :
386 : FD_FN_CONST static inline MAP_IDX_T const *
387 2582811573 : MAP_(private_chain_const)( MAP_(private_t) const * map ) {
388 2582811573 : return (MAP_IDX_T const *)(map+1);
389 2582811573 : }
390 :
391 : /* map_private_chain_idx returns the index of the chain (in
392 : [0,chain_cnt) that will contain the element corresponding to key (if
393 : present at all) for a map with chain_cnt elements and seed. Assumes
394 : chain_cnt is an integer power-of-two. Assumes key points to a key is
395 : in the caller's address space that will not be changed concurrently.
396 : Retains no interest in key on return. */
397 :
398 : FD_FN_PURE static inline ulong
399 : MAP_(private_chain_idx)( MAP_KEY_T const * key,
400 : ulong seed,
401 4788560532 : ulong chain_cnt ) {
402 4788560532 : return (MAP_KEY_HASH( (key), (seed) )) & (chain_cnt-1UL);
403 4788560532 : }
404 :
405 : /* map_private_{box,unbox} compress / decompress 64-bit in-register
406 : indices to/from their in-memory representations. */
407 :
408 286433040 : FD_FN_CONST static inline MAP_IDX_T MAP_(private_box) ( ulong idx ) { return (MAP_IDX_T)idx; }
409 11450182032 : FD_FN_CONST static inline ulong MAP_(private_unbox)( MAP_IDX_T cidx ) { return (ulong) cidx; }
410 :
411 : /* map_private_idx_null returns the element storage index that
412 : represents NULL. */
413 :
414 0 : FD_FN_CONST static inline ulong MAP_(private_idx_null)( void ) { return (ulong)(MAP_IDX_T)(~0UL); }
415 :
416 : /* map_private_idx_is_null returns 1 if idx is the NULL map index
417 : and 0 otherwise. */
418 :
419 13688762262 : FD_FN_CONST static inline int MAP_(private_idx_is_null)( ulong idx ) { return idx==(ulong)(MAP_IDX_T)(~0UL); }
420 :
421 0 : FD_FN_CONST static inline ulong MAP_(ele_max)( void ) { return (ulong)(MAP_IDX_T)(~0UL); }
422 :
423 : FD_FN_CONST static inline ulong
424 0 : MAP_(chain_max)( void ) {
425 0 : return fd_ulong_pow2_dn( (ULONG_MAX + 1UL - alignof(MAP_(t)) - sizeof(MAP_(t))) / sizeof(MAP_IDX_T) );
426 0 : }
427 :
428 : FD_FN_CONST static inline ulong
429 6000030 : MAP_(chain_cnt_est)( ulong ele_max_est ) {
430 :
431 : /* Clamp to be in [1,ele_max] (as ele_max_est 0 is degenerate and as
432 : the map is guaranteed to hold at most ele_max keys). */
433 :
434 6000030 : ele_max_est = fd_ulong_min( fd_ulong_max( ele_max_est, 1UL ), MAP_(ele_max)() );
435 :
436 : /* Compute the number of chains as the power of 2 that makes the
437 : average chain length between ~1 and ~2 when ele_max_est are stored
438 : in the map and then clamp to the chain max. */
439 :
440 6000030 : ulong chain_min = (ele_max_est>>1) + (ele_max_est&1UL); /* chain_min = ceil(ele_max_est/2), in [1,2^63], computed w/o overflow */
441 6000030 : ulong chain_cnt = fd_ulong_pow2_up( chain_min ); /* Power of 2 in [1,2^63] */
442 :
443 6000030 : return fd_ulong_min( chain_cnt, MAP_(chain_max)() );
444 6000030 : }
445 :
446 6 : FD_FN_PURE static inline ulong MAP_(chain_cnt)( MAP_(t) const * join ) { return MAP_(private_const)( join )->chain_cnt; }
447 6 : FD_FN_PURE static inline ulong MAP_(seed) ( MAP_(t) const * join ) { return MAP_(private_const)( join )->seed; }
448 :
449 : FD_FN_PURE static inline int
450 : MAP_(key_eq)( MAP_KEY_T const * k0,
451 5651997804 : MAP_KEY_T const * k1 ) {
452 5651997804 : return !!(MAP_KEY_EQ( (k0), (k1) ));
453 5651997804 : }
454 :
455 : FD_FN_PURE static inline ulong
456 : MAP_(key_hash)( MAP_KEY_T const * key,
457 6000000 : ulong seed ) {
458 6000000 : return (MAP_KEY_HASH( (key), (seed) ));
459 6000000 : }
460 :
461 : FD_FN_PURE static inline MAP_(iter_t)
462 : MAP_(iter_init)( MAP_(t) const * join,
463 3078000 : MAP_ELE_T const * pool ) {
464 3078000 : (void)pool;
465 :
466 3078000 : MAP_(private_t) const * map = MAP_(private_const)( join );
467 3078000 : MAP_IDX_T const * chain = MAP_(private_chain_const)( map );
468 :
469 : /* Find first element. If the map is empty, chain_rem will be 0 and
470 : ele_idx will be idx_null. */
471 :
472 3078000 : ulong chain_rem = map->chain_cnt; /* At least 1 */
473 3078000 : ulong ele_idx;
474 10746801 : do {
475 10746801 : ele_idx = MAP_(private_unbox)( chain[ chain_rem-1UL ] );
476 10746801 : if( !MAP_(private_idx_is_null)( ele_idx ) ) break;
477 10746801 : } while( --chain_rem );
478 :
479 3078000 : MAP_(iter_t) iter;
480 3078000 : iter.chain_rem = chain_rem;
481 3078000 : iter.ele_idx = ele_idx;
482 3078000 : return iter;
483 3078000 : }
484 :
485 : FD_FN_CONST static inline int
486 : MAP_(iter_done)( MAP_(iter_t) iter,
487 : MAP_(t) const * join,
488 791046000 : MAP_ELE_T const * pool ) {
489 791046000 : (void)join; (void)pool;
490 791046000 : return !iter.chain_rem;
491 791046000 : }
492 :
493 : FD_FN_PURE static inline MAP_(iter_t)
494 : MAP_(iter_next)( MAP_(iter_t) iter,
495 : MAP_(t) const * join,
496 787968000 : MAP_ELE_T const * pool ) {
497 787968000 : ulong chain_rem = iter.chain_rem;
498 787968000 : ulong ele_idx = iter.ele_idx;
499 :
500 : /* At this point, we are just finished iterating over element ele_idx
501 : on chain chain_rem-1 and we already iterated over all elements in
502 : chains (chain_rem,chain_cnt] and all elements in chain chain_rem-1
503 : before this element. As such, ele_idx is in [0,ele_cnt) and
504 : chain_rem is in (0,chain_cnt]. Get the next element in the chain
505 : chain_rem-1. */
506 :
507 787968000 : ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT );
508 787968000 : if( MAP_(private_idx_is_null)( ele_idx ) ) {
509 :
510 : /* There were no more elements in chain chain_rem-1. Find the next
511 : chain to start processing. If all unprocessed chains are empty,
512 : then we are done. */
513 :
514 380909301 : MAP_IDX_T const * chain = MAP_(private_chain_const)( MAP_(private_const)( join ) );
515 780293199 : while( --chain_rem ) {
516 777221199 : ele_idx = MAP_(private_unbox)( chain[ chain_rem-1UL ] );
517 777221199 : if( !MAP_(private_idx_is_null)( ele_idx ) ) break;
518 777221199 : }
519 :
520 380909301 : }
521 :
522 787968000 : iter.chain_rem = chain_rem;
523 787968000 : iter.ele_idx = ele_idx;
524 787968000 : return iter;
525 787968000 : }
526 :
527 : FD_FN_CONST static inline ulong
528 : MAP_(iter_idx)( MAP_(iter_t) iter,
529 : MAP_(t) const * join,
530 787968000 : MAP_ELE_T * pool ) {
531 787968000 : (void)join; (void)pool;
532 787968000 : return iter.ele_idx;
533 787968000 : }
534 :
535 : FD_FN_CONST static inline MAP_ELE_T *
536 : MAP_(iter_ele)( MAP_(iter_t) iter,
537 : MAP_(t) const * join,
538 787968000 : MAP_ELE_T * pool ) {
539 787968000 : (void)join; (void)pool;
540 787968000 : return pool + iter.ele_idx;
541 787968000 : }
542 :
543 : FD_FN_CONST static inline MAP_ELE_T const *
544 : MAP_(iter_ele_const) ( MAP_(iter_t) iter,
545 : MAP_(t) const * join,
546 787968000 : MAP_ELE_T const * pool ) {
547 787968000 : (void)join; (void)pool;
548 787968000 : return pool + iter.ele_idx;
549 787968000 : }
550 :
551 : FD_PROTOTYPES_END
552 :
553 : #endif
554 :
555 : #if MAP_IMPL_STYLE==1 /* need prototypes */
556 :
557 : FD_PROTOTYPES_BEGIN
558 :
559 : FD_FN_CONST ulong MAP_(align) ( void );
560 : FD_FN_CONST ulong MAP_(footprint)( ulong chain_cnt );
561 : void * MAP_(new) ( void * shmem, ulong chain_cnt, ulong seed );
562 : MAP_(t) * MAP_(join) ( void * shmap );
563 : void * MAP_(leave) ( MAP_(t) * join );
564 : void * MAP_(delete) ( void * shmap );
565 :
566 : MAP_(t) *
567 : MAP_(idx_insert)( MAP_(t) * join,
568 : ulong ele_idx,
569 : MAP_ELE_T * pool );
570 :
571 : ulong
572 : MAP_(idx_remove)( MAP_(t) * join,
573 : MAP_KEY_T const * key,
574 : ulong sentinel,
575 : MAP_ELE_T * pool );
576 :
577 : FD_FN_PURE ulong
578 : MAP_(idx_query)( MAP_(t) * join,
579 : MAP_KEY_T const * key,
580 : ulong sentinel,
581 : MAP_ELE_T * pool );
582 :
583 : FD_FN_PURE ulong
584 : MAP_(idx_query_const)( MAP_(t) const * join,
585 : MAP_KEY_T const * key,
586 : ulong sentinel,
587 : MAP_ELE_T const * pool );
588 :
589 : #if MAP_MULTI!=0
590 :
591 : FD_FN_PURE ulong
592 : MAP_(idx_next_const)( ulong prev, // Previous result of mymap_idx_query_const
593 : ulong sentinel, // Value to return on failure
594 : MAP_ELE_T const * pool ); // Current local join to element storage
595 :
596 : #endif /* MAP_MULTI!=0 */
597 :
598 : FD_FN_PURE int
599 : MAP_(verify)( MAP_(t) const * join,
600 : ulong ele_cnt,
601 : MAP_ELE_T const * pool );
602 :
603 : FD_PROTOTYPES_END
604 :
605 : #else /* need implementations */
606 :
607 : #if MAP_IMPL_STYLE==0 /* local only */
608 : #define MAP_IMPL_STATIC FD_FN_UNUSED static
609 : #else
610 : #define MAP_IMPL_STATIC
611 : #endif
612 :
613 0 : FD_FN_CONST MAP_IMPL_STATIC ulong MAP_(align)( void ) { return alignof(MAP_(t)); }
614 :
615 : FD_FN_CONST MAP_IMPL_STATIC ulong
616 48 : MAP_(footprint)( ulong chain_cnt ) {
617 48 : if( !(fd_ulong_is_pow2( chain_cnt ) & (chain_cnt<=MAP_(chain_max)())) ) return 0UL;
618 12 : return fd_ulong_align_up( sizeof(MAP_(t)) + chain_cnt*sizeof(MAP_IDX_T), alignof(MAP_(t)) ); /* no overflow */
619 48 : }
620 :
621 : MAP_IMPL_STATIC void *
622 : MAP_(new)( void * shmap,
623 : ulong chain_cnt,
624 36 : ulong seed ) {
625 :
626 36 : if( FD_UNLIKELY( !shmap ) ) {
627 6 : FD_LOG_WARNING(( "NULL shmap" ));
628 6 : return NULL;
629 6 : }
630 :
631 30 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmap, MAP_(align)() ) ) ) {
632 6 : FD_LOG_WARNING(( "misaligned shmap" ));
633 6 : return NULL;
634 6 : }
635 :
636 24 : ulong footprint = MAP_(footprint)( chain_cnt );
637 24 : if( FD_UNLIKELY( !footprint ) ) {
638 18 : FD_LOG_WARNING(( "bad footprint" ));
639 18 : return NULL;
640 18 : }
641 :
642 : /* seed is arbitrary */
643 :
644 : /* Init the metadata */
645 :
646 6 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
647 :
648 6 : map->seed = seed;
649 6 : map->chain_cnt = chain_cnt;
650 :
651 : /* Set all the chains to NULL */
652 :
653 6 : MAP_IDX_T * chain = MAP_(private_chain)( map );
654 1542 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) chain[ chain_idx ] = MAP_(private_box)( MAP_(private_idx_null)() );
655 :
656 6 : FD_COMPILER_MFENCE();
657 6 : FD_VOLATILE( map->magic ) = MAP_MAGIC;
658 6 : FD_COMPILER_MFENCE();
659 :
660 6 : return shmap;
661 24 : }
662 :
663 : MAP_IMPL_STATIC MAP_(t) *
664 24 : MAP_(join)( void * shmap ) {
665 24 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
666 :
667 24 : if( FD_UNLIKELY( !map ) ) {
668 6 : FD_LOG_WARNING(( "NULL shmap" ));
669 6 : return NULL;
670 6 : }
671 :
672 18 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) ) ) {
673 6 : FD_LOG_WARNING(( "misaligned shmap" ));
674 6 : return NULL;
675 6 : }
676 :
677 12 : if( FD_UNLIKELY( map->magic!=MAP_MAGIC ) ) {
678 6 : FD_LOG_WARNING(( "bad magic" ));
679 6 : return NULL;
680 6 : }
681 :
682 6 : return (MAP_(t) *)map;
683 12 : }
684 :
685 : MAP_IMPL_STATIC void *
686 12 : MAP_(leave)( MAP_(t) * join ) {
687 :
688 12 : if( FD_UNLIKELY( !join ) ) {
689 6 : FD_LOG_WARNING(( "NULL join" ));
690 6 : return NULL;
691 6 : }
692 :
693 6 : return (void *)join;
694 12 : }
695 :
696 : MAP_IMPL_STATIC void *
697 24 : MAP_(delete)( void * shmap ) {
698 24 : MAP_(private_t) * map = (MAP_(private_t) *)shmap;
699 :
700 24 : if( FD_UNLIKELY( !map ) ) {
701 6 : FD_LOG_WARNING(( "NULL shmap" ));
702 6 : return NULL;
703 6 : }
704 :
705 18 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)map, MAP_(align)() ) ) ) {
706 6 : FD_LOG_WARNING(( "misaligned shmap" ));
707 6 : return NULL;
708 6 : }
709 :
710 12 : if( FD_UNLIKELY( map->magic!=MAP_MAGIC ) ) {
711 6 : FD_LOG_WARNING(( "bad magic" ));
712 6 : return NULL;
713 6 : }
714 :
715 6 : FD_COMPILER_MFENCE();
716 6 : FD_VOLATILE( map->magic ) = 0UL;
717 6 : FD_COMPILER_MFENCE();
718 :
719 6 : return shmap;
720 12 : }
721 :
722 : MAP_IMPL_STATIC MAP_(t) *
723 : MAP_(idx_insert)( MAP_(t) * join,
724 : ulong ele_idx,
725 3072000 : MAP_ELE_T * pool ) {
726 3072000 : MAP_(private_t) * map = MAP_(private)( join );
727 :
728 3072000 : MAP_IDX_T * head = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( &pool[ ele_idx ].MAP_KEY, map->seed, map->chain_cnt );
729 :
730 3072000 : pool[ ele_idx ].MAP_NEXT = *head;
731 3072000 : *head = MAP_(private_box)( ele_idx );
732 :
733 3072000 : return join;
734 3072000 : }
735 :
736 : MAP_IMPL_STATIC ulong
737 : MAP_(idx_remove)( MAP_(t) * join,
738 : MAP_KEY_T const * key,
739 : ulong sentinel,
740 7680000 : MAP_ELE_T * pool ) {
741 7680000 : MAP_(private_t) * map = MAP_(private)( join );
742 :
743 : /* Find the key */
744 :
745 7680000 : MAP_IDX_T * cur = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
746 11787072 : for(;;) {
747 11787072 : ulong ele_idx = MAP_(private_unbox)( *cur );
748 11787072 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found (it is remove after all) */
749 7179072 : if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) { /* " */
750 3072000 : *cur = pool[ ele_idx ].MAP_NEXT;
751 3072000 : return ele_idx;
752 3072000 : }
753 4107072 : cur = &pool[ ele_idx ].MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
754 4107072 : }
755 :
756 : /* Not found */
757 :
758 4608000 : return sentinel;
759 7680000 : }
760 :
761 : FD_FN_PURE MAP_IMPL_STATIC ulong
762 : MAP_(idx_query)( MAP_(t) * join,
763 : MAP_KEY_T const * key,
764 : ulong sentinel,
765 1181952000 : MAP_ELE_T * pool ) {
766 1181952000 : MAP_(private_t) * map = MAP_(private)( join );
767 :
768 : /* Find the key */
769 :
770 1181952000 : MAP_IDX_T * head = MAP_(private_chain)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
771 1181952000 : MAP_IDX_T * cur = head;
772 2077807389 : for(;;) {
773 2077807389 : ulong ele_idx = MAP_(private_unbox)( *cur );
774 2077807389 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
775 1289839389 : if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) { /* optimize for found */
776 : /* Found, move it to the front of the chain */
777 393984000 : if( FD_UNLIKELY( cur!=head ) ) { /* Assume already at head from previous query */
778 283359504 : *cur = pool[ ele_idx ].MAP_NEXT;
779 283359504 : pool[ ele_idx ].MAP_NEXT = *head;
780 283359504 : *head = MAP_(private_box)( ele_idx );
781 283359504 : }
782 393984000 : return ele_idx;
783 393984000 : }
784 895855389 : cur = &pool[ ele_idx ].MAP_NEXT; /* Retain the pointer to next so we can rewrite it later. */
785 895855389 : }
786 :
787 : /* Not found */
788 :
789 787968000 : return sentinel;
790 1181952000 : }
791 :
792 : FD_FN_PURE MAP_IMPL_STATIC ulong
793 : MAP_(idx_query_const)( MAP_(t) const * join,
794 : MAP_KEY_T const * key,
795 : ulong sentinel,
796 2192680266 : MAP_ELE_T const * pool ) {
797 2192680266 : MAP_(private_t) const * map = MAP_(private_const)( join );
798 :
799 : /* Find the key */
800 :
801 2192680266 : MAP_IDX_T const * cur = MAP_(private_chain_const)( map ) + MAP_(private_chain_idx)( key, map->seed, map->chain_cnt );
802 3404266695 : for(;;) {
803 3404266695 : ulong ele_idx = MAP_(private_unbox)( *cur );
804 3404266695 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
805 3402730695 : if( FD_LIKELY( MAP_(key_eq)( key, &pool[ ele_idx ].MAP_KEY ) ) ) return ele_idx; /* optimize for found */
806 1211586429 : cur = &pool[ ele_idx ].MAP_NEXT;
807 1211586429 : }
808 :
809 : /* Not found */
810 :
811 1536000 : return sentinel;
812 2192680266 : }
813 :
814 : #if MAP_MULTI!=0
815 :
816 : FD_FN_PURE MAP_IMPL_STATIC ulong
817 : MAP_(idx_next_const)( ulong prev, // Previous result of mymap_idx_query_const
818 : ulong sentinel, // Value to return on failure
819 688806852 : MAP_ELE_T const * pool ) { // Current local join to element storage
820 : /* Go to next element in chain */
821 :
822 688806852 : MAP_ELE_T const * prev_ele = &pool[ prev ];
823 688806852 : MAP_IDX_T const * cur = &prev_ele->MAP_NEXT;
824 928248648 : for(;;) {
825 928248648 : ulong ele_idx = MAP_(private_unbox)( *cur );
826 928248648 : if( FD_UNLIKELY( MAP_(private_idx_is_null)( ele_idx ) ) ) break; /* optimize for found */
827 928248648 : if( FD_LIKELY( MAP_(key_eq)( &prev_ele->MAP_KEY, &pool[ ele_idx ].MAP_KEY ) ) ) return ele_idx; /* optimize for found */
828 239441796 : cur = &pool[ ele_idx ].MAP_NEXT;
829 239441796 : }
830 :
831 : /* Not found */
832 :
833 0 : return sentinel;
834 688806852 : }
835 :
836 : #endif /* MAP_MULTI!=0 */
837 :
838 : FD_FN_PURE MAP_IMPL_STATIC int
839 : MAP_(verify)( MAP_(t) const * join,
840 : ulong ele_cnt,
841 6144024 : MAP_ELE_T const * pool ) {
842 :
843 5649569136 : # define MAP_TEST(c) do { \
844 5649569136 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
845 5649569136 : } while(0)
846 :
847 : /* Validate input arguments */
848 :
849 6144024 : MAP_TEST( join );
850 6144018 : MAP_TEST( ele_cnt<=MAP_(ele_max)() );
851 6144012 : MAP_TEST( (!!pool) | (!ele_cnt) );
852 :
853 : /* Validate metadata */
854 :
855 6144006 : MAP_(private_t) const * map = MAP_(private_const)( join );
856 :
857 6144006 : MAP_TEST( map->magic==MAP_MAGIC );
858 :
859 6144006 : ulong seed = map->seed;
860 : /* seed is arbitrary */
861 :
862 6144006 : ulong chain_cnt = map->chain_cnt;
863 6144006 : MAP_TEST( fd_ulong_is_pow2( chain_cnt ) );
864 6144006 : MAP_TEST( chain_cnt<=MAP_(chain_max)() );
865 :
866 : /* Visit each map entry, doing simple chain integrity checks */
867 :
868 6144006 : MAP_IDX_T const * chain = MAP_(private_chain_const)( map );
869 :
870 6144006 : ulong rem = ele_cnt; /* We can visit at most ele_cnt elements */
871 1579009542 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ )
872 1572865536 : for( ulong ele_idx = MAP_(private_unbox)( chain[ chain_idx ] );
873 2976041802 : !MAP_(private_idx_is_null)( ele_idx );
874 1572865536 : ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT ) ) {
875 1403176266 : MAP_TEST( rem ); rem--; /* Check for cycles */
876 1403176266 : MAP_TEST( ele_idx<ele_cnt ); /* Check valid element index */
877 1403176266 : MAP_TEST( MAP_(private_chain_idx)( &pool[ ele_idx ].MAP_KEY, seed, chain_cnt )==chain_idx ); /* Check in correct chain */
878 1403176266 : }
879 :
880 : /* At this point, we know that there are no cycles in the map chains,
881 : all indices are inbounds and elements are in the correct chains for
882 : probes. It is possible for there to be keys that have been
883 : inserted more than once though. We visit all the nodes a second
884 : time and make sure each probe resolves to itself to prove the key
885 : of every element in the map is unique. (We could do this faster if
886 : we could tag the elements but this verify is written to not modify
887 : any memory.) */
888 :
889 1579009542 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ )
890 1572865536 : for( ulong ele_idx = MAP_(private_unbox)( chain[ chain_idx ] );
891 2976041802 : !MAP_(private_idx_is_null)( ele_idx );
892 1572865536 : ele_idx = MAP_(private_unbox)( pool[ ele_idx ].MAP_NEXT ) ) {
893 : #if MAP_MULTI==0
894 786432000 : MAP_TEST( MAP_(idx_query_const)( join, &pool[ ele_idx ].MAP_KEY, ULONG_MAX, pool )==ele_idx );
895 : #else
896 : ulong idx2;
897 616744266 : for (idx2 = MAP_(idx_query_const)( join, &pool[ ele_idx ].MAP_KEY, ULONG_MAX, pool );
898 1046106888 : idx2 != ULONG_MAX && idx2 != ele_idx;
899 429362622 : idx2 = MAP_(idx_next_const)( idx2, ULONG_MAX, pool )) ;
900 616744266 : MAP_TEST( idx2 == ele_idx );
901 : #endif
902 1403176266 : }
903 :
904 6144006 : # undef MAP_TEST
905 :
906 6144006 : return 0;
907 6144006 : }
908 :
909 : #undef MAP_IMPL_STATIC
910 :
911 : #endif
912 :
913 : #if MAP_IMPL_STYLE==0 || MAP_IMPL_STYLE==1 /* need inlines */
914 :
915 : FD_PROTOTYPES_BEGIN
916 :
917 : static inline MAP_(t) *
918 : MAP_(ele_insert)( MAP_(t) * join,
919 : MAP_ELE_T * ele,
920 3072000 : MAP_ELE_T * pool ) {
921 3072000 : return MAP_(idx_insert)( join, (ulong)(ele-pool), pool );
922 3072000 : }
923 :
924 : static inline MAP_ELE_T *
925 : MAP_(ele_remove)( MAP_(t) * join,
926 : MAP_KEY_T const * key,
927 : MAP_ELE_T * sentinel,
928 7680000 : MAP_ELE_T * pool ) {
929 7680000 : ulong ele_idx = MAP_(idx_remove)( join, key, MAP_(private_idx_null)(), pool );
930 7680000 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
931 7680000 : }
932 :
933 : FD_FN_PURE static inline MAP_ELE_T *
934 : MAP_(ele_query)( MAP_(t) * join,
935 : MAP_KEY_T const * key,
936 : MAP_ELE_T * sentinel,
937 1181952000 : MAP_ELE_T * pool ) {
938 1181952000 : ulong ele_idx = MAP_(idx_query)( join, key, MAP_(private_idx_null)(), pool );
939 1181952000 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
940 1181952000 : }
941 :
942 : FD_FN_PURE static inline MAP_ELE_T const *
943 : MAP_(ele_query_const)( MAP_(t) const * join,
944 : MAP_KEY_T const * key,
945 : MAP_ELE_T const * sentinel,
946 789504000 : MAP_ELE_T const * pool ) {
947 789504000 : ulong ele_idx = MAP_(idx_query_const)( join, key, MAP_(private_idx_null)(), pool );
948 789504000 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), (MAP_ELE_T const *)( (ulong)pool + (ele_idx * sizeof(MAP_ELE_T)) ), sentinel );
949 789504000 : }
950 :
951 : #if MAP_MULTI!=0
952 :
953 : FD_FN_PURE static inline MAP_ELE_T const * // Found element on success (will be from pool), sentinel on failure
954 : MAP_(ele_next_const)( MAP_ELE_T const * prev, // Previous result of mymap_ele_query_const
955 : MAP_ELE_T const * sentinel, // Value to return if key not in map
956 259444230 : MAP_ELE_T const * pool ) { // Current local join to element storage
957 259444230 : ulong ele_idx = MAP_(idx_next_const)( (ulong)(prev-pool), MAP_(private_idx_null)(), pool );
958 259444230 : return fd_ptr_if( !MAP_(private_idx_is_null)( ele_idx ), pool + ele_idx, sentinel );
959 259444230 : }
960 :
961 : #endif /* MAP_MULTI!=0 */
962 :
963 : FD_PROTOTYPES_END
964 :
965 : #endif
966 :
967 : #undef MAP_
968 :
969 : #undef MAP_IMPL_STYLE
970 : #undef MAP_MAGIC
971 : #undef MAP_KEY_HASH
972 : #undef MAP_KEY_EQ
973 : #undef MAP_NEXT
974 : #undef MAP_IDX_T
975 : #undef MAP_KEY
976 : #undef MAP_KEY_T
977 : #undef MAP_ELE_T
978 : #undef MAP_NAME
979 : #undef MAP_MULTI
|
