Line data Source code
1 : /* Generate prototypes, inlines and/or implementations for HPC slingly
2 : linked lists. A slist can store a practically unbounded number of
3 : elements. Typical slist operations are generally a fast O(1) time
4 : and slist element memory overhead is a small O(1) space.
5 :
6 : This API is designed for ultra tight coupling with pools, treaps,
7 : heaps, maps, dlists, etc. Likewise, a slist can be persisted beyond
8 : the lifetime of the creating process, used concurrently in many
9 : common operations, used inter-process, relocated in memory, naively
10 : serialized/deserialized, moved between hosts, supports index
11 : compression for cache and memory bandwidth efficiency, etc.
12 :
13 : Memory efficiency and flexible footprint are prioritized.
14 :
15 : Typical usage:
16 :
17 : struct myele {
18 : ulong next; // Technically "SLIST_IDX_T SLIST_NEXT" (default is ulong next), do not modify while element is in the slist
19 : ... next can be located arbitrarily in the element and can be
20 : ... reused for other purposes when the element is not in a slist.
21 : ... An element should not be moved / released while an element is
22 : ... in a slist
23 : };
24 :
25 : typedef struct myele myele_t;
26 :
27 : #define SLIST_NAME myslist
28 : #define SLIST_ELE_T myele_t
29 : #include "tmpl/fd_slist.c"
30 :
31 : will declare the following APIs as a header only style library in the
32 : compilation unit:
33 :
34 : // myslist_ele_max returns the theoretical maximum number of
35 : // elements that can be held in a myslist.
36 :
37 : ulong myslist_ele_max( void );
38 :
39 : // myslist_{align,footprint} returns the alignment and footprint
40 : // needed for a memory region to be used as a myslist. align will
41 : // be an integer power-of-two and footprint will be a multiple of
42 : // align. The values will be compile-time declaration friendly
43 : // (e.g. "myslist_t mem[1];" will have the correct alignment and
44 : // footprint and not be larger than 4096).
45 : //
46 : // myslist_new formats a memory region with the appropriate
47 : // alignment and footprint whose first byte in the caller's address
48 : // space is pointed to by shmem as a myslist. Returns shmem on
49 : // success and NULL on failure (logs details). Caller is not
50 : // joined on return. The slist will be empty.
51 : //
52 : // myslist_join joins a myslist. Assumes shslist points at a
53 : // memory region formatted as a myslist in the caller's address
54 : // space. Returns a handle to the caller's local join on success
55 : // and NULL on failure (logs details). Do not assume this is a
56 : // simple cast of shslist!
57 : //
58 : // myslist_leave leaves a myslist. Assumes join points to a
59 : // current local join. Returns shslist used on join. Do not
60 : // assume this is a simple cast of join!
61 : //
62 : // myslist_delete unformats a memory region used as a myslist.
63 : // Assumes shslist points to a memory region in the caller's local
64 : // address space formatted as a myslist, that there are no joins to
65 : // the myslist and that any application cleanup of the entries has
66 : // already been done. Returns shslist on success and NULL on
67 : // failure.
68 :
69 : ulong myslist_align ( void );
70 : ulong myslist_footprint( void );
71 : void * myslist_new ( void * shmem );
72 : myslist_t * myslist_join ( void * shslist );
73 : void * myslist_leave ( myslist_t * join );
74 : void * myslist_delete ( void * shslist );
75 :
76 : // The below APIs assume join is a current local join to a myslist
77 : // and pool is a current local join to the element storage backing
78 : // the slist.
79 : //
80 : // myslist_is_empty returns 1 if the slist is empty and 0
81 : // otherwise.
82 : //
83 : // myslist_idx_peek_{head,tail} returns the pool index of the
84 : // slist's {head,tail}. Assumes slist is not empty.
85 :
86 : int myslist_is_empty( myslist_t const * join, myele_t const * pool );
87 :
88 : ulong myslist_idx_peek_head( myslist_t const * join, myele_t const * pool );
89 : ulong myslist_idx_peek_tail( myslist_t const * join, myele_t const * pool );
90 :
91 : // myslist_idx_push_{head,tail} pushes the pool element whose index
92 : // is ele_idx to the slist's {head,tail} and returns join. Assumes
93 : // ele_idx valid and not already in the slist.
94 : // myslist_idx_pop_head pops the pool element at the slist's head
95 : // and returns its pool index. Assumes slist is not empty.
96 : //
97 : // myslist_idx_insert_after inserts the pool element whose index is
98 : // ele_idx into the slist immediately after the pool element whose
99 : // index is prev_idx and returns join. Assumes ele_idx is valid
100 : // and not already in the slist and prev_idx is already in the
101 : // slist.
102 :
103 : myslist_t * myslist_idx_push_head ( myslist_t * join, ulong ele_idx, myele_t * pool );
104 : myslist_t * myslist_idx_push_tail ( myslist_t * join, ulong ele_idx, myele_t * pool );
105 : ulong myslist_idx_pop_head ( myslist_t * join, myele_t * pool );
106 : myslist_t * myslist_idx_insert_after ( myslist_t * join, ulong ele_idx, ulong prev_idx, myele_t * pool );
107 :
108 : // myslist_remove_all removes all elements from the slist and
109 : // returns join. It is the caller's responsibility to release all
110 : // elements to the pool as might be necessary.
111 :
112 : myslist_t * myslist_remove_all( myslist_t * join, myele_t * pool );
113 :
114 : // myslist_iter_* support fast ordered forward (head to tail)
115 : // iteration over all the elements in a slist. Example usage:
116 : //
117 : // for( myslist_iter_t iter = myslist_iter_init( join, pool );
118 : // !myslist_iter_done( iter, join, pool );
119 : // iter = myslist_iter_next( iter, join, pool ) ) {
120 : // ulong ele_idx = myslist_iter_idx( iter, join, pool );
121 : //
122 : // ... process element here
123 : //
124 : // ... IMPORTANT! It is generally safe to insert elements
125 : // ... here (though they might not be covered by this
126 : // ... iteration). It is also generally safe to remove any
127 : // ... element but the current element here (the removed
128 : // ... element might have already been iterated over). It is
129 : // ... straightforward to make a variant of this iterator
130 : // ... that would support removing the current element here
131 : // ... if desired.
132 : // }
133 :
134 : struct myslist_iter_private { ... internal use only ... };
135 : typedef struct myslist_iter_private myslist_iter_t;
136 :
137 : myslist_iter_t myslist_iter_init( myslist_t const * join, myele_t const * pool );
138 : int myslist_iter_done( myslist_iter_t iter, myslist_t const * join, myele_t const * pool );
139 : myslist_iter_t myslist_iter_next( myslist_iter_t iter, myslist_t const * join, myele_t const * pool ); // assumes !done
140 : ulong myslist_iter_idx ( myslist_iter_t iter, myslist_t const * join, myele_t const * pool ); // assumes !done
141 :
142 : // myslist_verify returns 0 if the myslist is not obviously corrupt
143 : // or -1 (i.e. ERR_INVAL) otherwise (logs details).
144 :
145 : int
146 : myslist_verify( myslist_t const * join, // Current local join to a myslist.
147 : ulong ele_cnt, // Element storage size, in [0,myslist_ele_max()]
148 : myele_t const * pool ); // Current local join to element storage, indexed [0,ele_cnt)
149 :
150 : // The above APIs have helpers that operate purely in the caller's
151 : // local address space when applicable. The various elements
152 : // passed to / returned from these functions should be / will be
153 : // from the slist's underlying pool.
154 :
155 : myele_t * myslist_ele_peek_head( myslist_t const * join, myele_t * pool );
156 : myele_t * myslist_ele_peek_tail( myslist_t const * join, myele_t * pool );
157 :
158 : myslist_t * myslist_ele_push_head ( myslist_t * join, myele_t * ele, myele_t * pool );
159 : myslist_t * myslist_ele_push_tail ( myslist_t * join, myele_t * ele, myele_t * pool );
160 : myele_t * myslist_ele_pop_head ( myslist_t * join, myele_t * pool );
161 : myslist_t * myslist_ele_insert_after ( myslist_t * join, myele_t * ele, myele_t * prev, myele_t * pool );
162 :
163 : myele_t * myslist_iter_ele( myslist_iter_t iter, myslist_t const * join, myele_t * pool );
164 :
165 : // ... and const correct helpers when applicable
166 :
167 : myele_t const * myslist_ele_peek_head_const( myslist_t const * join, myele_t const * pool );
168 : myele_t const * myslist_ele_peek_tail_const( myslist_t const * join, myele_t const * pool );
169 :
170 : myele_t const * myslist_iter_ele_const( myslist_iter_t iter, myslist_t const * join, myele_t const * pool );
171 :
172 : You can do this as often as you like in a compilation unit to get
173 : different types of slists. Variants exist for making header
174 : prototypes only and/or implementations only if making a library for
175 : use across multiple compilation units. Further, options exist to use
176 : different hashing functions, comparison functions, etc as detailed
177 : below. */
178 :
179 : /* TODO: DOC CONCURRENCY REQUIREMENTS */
180 :
181 : /* SLIST_NAME gives the API prefix to use for a slist */
182 :
183 : #ifndef SLIST_NAME
184 : #error "Define SLIST_NAME"
185 : #endif
186 :
187 : /* SLIST_ELE_T is the slist element type. */
188 :
189 : #ifndef SLIST_ELE_T
190 : #error "Define SLIST_ELE_T"
191 : #endif
192 :
193 : /* SLIST_IDX_T is the type used for the next field in the SLIST_ELE_T.
194 : Should be a primitive unsigned integer type. Defaults to ulong. A
195 : slist can't use element memory regions with more elements than the
196 : maximum value that can be represented by a SLIST_IDX_T. (E.g. if
197 : ushort, the maximum size element store supported by the slist is
198 : 65535 elements.) */
199 :
200 : #ifndef SLIST_IDX_T
201 : #define SLIST_IDX_T ulong
202 : #endif
203 :
204 : /* SLIST_NEXT is the SLIST_ELE_T next field */
205 :
206 : #ifndef SLIST_NEXT
207 : #define SLIST_NEXT next
208 : #endif
209 :
210 : /* SLIST_MAGIC is the magic number to use for the structure to aid in
211 : persistent and/or IPC usage. */
212 :
213 : #ifndef SLIST_MAGIC
214 12039 : #define SLIST_MAGIC (0xf17eda2c37371570UL) /* firedancer slist version 0 */
215 : #endif
216 :
217 : /* 0 - local use only
218 : 1 - library header declaration
219 : 2 - library implementation */
220 :
221 : #ifndef SLIST_IMPL_STYLE
222 : #define SLIST_IMPL_STYLE 0
223 : #endif
224 :
225 : #if FD_TMPL_USE_HANDHOLDING
226 : #include "../log/fd_log.h"
227 : #endif
228 :
229 : /* Implementation *****************************************************/
230 :
231 : /* Constructors and verification log details on failure (rest only needs
232 : fd_bits.h, consider making logging a compile time option). */
233 :
234 45509733114 : #define SLIST_(n) FD_EXPAND_THEN_CONCAT3(SLIST_NAME,_,n)
235 :
236 : #if SLIST_IMPL_STYLE==0 || SLIST_IMPL_STYLE==1 /* need structures and inlines */
237 :
238 : struct SLIST_(private) {
239 :
240 : /* join points here */
241 :
242 : ulong magic; /* == SLIST_MAGIC */
243 : SLIST_IDX_T head; /* index of first list element (or idx_null if empty list) */
244 : SLIST_IDX_T tail; /* index of last list element (or idx_null if empty list) */
245 : };
246 :
247 : typedef struct SLIST_(private) SLIST_(private_t);
248 :
249 : typedef SLIST_(private_t) SLIST_(t);
250 :
251 : typedef ulong SLIST_(iter_t);
252 :
253 : FD_PROTOTYPES_BEGIN
254 :
255 : /* slist_private returns the location of the slist header for a current
256 : local join. Assumes join is a current local join.
257 : slist_private_const is a const correct version. */
258 :
259 : FD_FN_CONST static inline SLIST_(private_t) *
260 375803571 : SLIST_(private)( SLIST_(t) * join ) {
261 375803571 : return (SLIST_(private_t) *)join;
262 375803571 : }
263 :
264 : FD_FN_CONST static inline SLIST_(private_t) const *
265 13688298153 : SLIST_(private_const)( SLIST_(t) const * join ) {
266 13688298153 : return (SLIST_(private_t) const *)join;
267 13688298153 : }
268 :
269 : /* slist_private_{cidx,idx} compress / decompress 64-bit in-register
270 : indices to/from their in-memory representations. */
271 :
272 939533067 : FD_FN_CONST static inline SLIST_IDX_T SLIST_(private_cidx)( ulong idx ) { return (SLIST_IDX_T)idx; }
273 17064695904 : FD_FN_CONST static inline ulong SLIST_(private_idx) ( SLIST_IDX_T cidx ) { return (ulong) cidx; }
274 :
275 : /* slist_private_idx_null returns the element storage index that
276 : represents NULL. */
277 :
278 438401679 : FD_FN_CONST static inline ulong SLIST_(private_idx_null)( void ) { return (ulong)(SLIST_IDX_T)~0UL; }
279 :
280 : /* slist_private_idx_is_null returns 1 if idx is the NULL slist index
281 : and 0 otherwise. */
282 :
283 5439137136 : FD_FN_CONST static inline int SLIST_(private_idx_is_null)( ulong idx ) { return idx==(ulong)(SLIST_IDX_T)~0UL; }
284 :
285 187540266 : FD_FN_CONST static inline ulong SLIST_(ele_max)( void ) { return (ulong)(SLIST_IDX_T)~0UL; }
286 :
287 : FD_FN_PURE static inline int
288 : SLIST_(is_empty)( SLIST_(t) const * join,
289 1875721860 : SLIST_ELE_T const * pool ) {
290 1875721860 : (void)pool;
291 1875721860 : return SLIST_(private_idx_is_null)( SLIST_(private_idx)( SLIST_(private_const)( join )->head ) );
292 1875721860 : }
293 :
294 : FD_FN_PURE static inline ulong
295 : SLIST_(idx_peek_head)( SLIST_(t) const * join,
296 5625844290 : SLIST_ELE_T const * pool ) {
297 5625844290 : (void)pool;
298 : # if FD_TMPL_USE_HANDHOLDING
299 : if( FD_UNLIKELY( SLIST_(is_empty)( join, pool ) ) ) FD_LOG_CRIT(( "cannot peek on empty slist" ));
300 : # endif
301 5625844290 : return SLIST_(private_idx)( SLIST_(private_const)( join )->head );
302 5625844290 : }
303 :
304 : FD_FN_PURE static inline ulong
305 : SLIST_(idx_peek_tail)( SLIST_(t) const * join,
306 5624272518 : SLIST_ELE_T const * pool ) {
307 5624272518 : (void)pool;
308 : # if FD_TMPL_USE_HANDHOLDING
309 : if( FD_UNLIKELY( SLIST_(is_empty)( join, pool ) ) ) FD_LOG_CRIT(( "cannot peek on empty slist" ));
310 : # endif
311 5624272518 : return SLIST_(private_idx)( SLIST_(private_const)( join )->tail );
312 5624272518 : }
313 :
314 : static inline SLIST_(t) *
315 : SLIST_(idx_push_head)( SLIST_(t) * join,
316 : ulong ele_idx,
317 62499201 : SLIST_ELE_T * pool ) {
318 62499201 : SLIST_(private_t) * slist = SLIST_(private)( join );
319 :
320 62499201 : ulong head_idx = SLIST_(private_idx)( slist->head );
321 :
322 62499201 : pool[ ele_idx ].SLIST_NEXT = SLIST_(private_cidx)( head_idx );
323 :
324 62499201 : SLIST_IDX_T dummy[1];
325 62499201 : *fd_ptr_if( !SLIST_(private_idx_is_null)( head_idx ), dummy+0, &slist->tail ) =
326 62499201 : SLIST_(private_cidx)( ele_idx );
327 :
328 62499201 : slist->head = SLIST_(private_cidx)( ele_idx );
329 62499201 : return join;
330 62499201 : }
331 :
332 : static inline SLIST_(t) *
333 : SLIST_(idx_push_tail)( SLIST_(t) * join,
334 : ulong ele_idx,
335 62935587 : SLIST_ELE_T * pool ) {
336 62935587 : SLIST_(private_t) * slist = SLIST_(private)( join );
337 :
338 62935587 : ulong tail_idx = SLIST_(private_idx)( slist->tail );
339 :
340 62935587 : pool[ ele_idx ].SLIST_NEXT = SLIST_(private_cidx)( SLIST_(private_idx_null)() );
341 :
342 62935587 : *fd_ptr_if( !SLIST_(private_idx_is_null)( tail_idx ), &pool[ tail_idx ].SLIST_NEXT, &slist->head ) =
343 62935587 : SLIST_(private_cidx)( ele_idx );
344 :
345 62935587 : slist->tail = SLIST_(private_cidx)( ele_idx );
346 62935587 : return join;
347 62935587 : }
348 :
349 : static inline ulong
350 : SLIST_(idx_pop_head)( SLIST_(t) * join,
351 187901697 : SLIST_ELE_T * pool ) {
352 : # if FD_TMPL_USE_HANDHOLDING
353 : if( FD_UNLIKELY( SLIST_(is_empty)( join, pool ) ) ) FD_LOG_CRIT(( "cannot pop from empty slist" ));
354 : # endif
355 187901697 : SLIST_(private_t) * slist = SLIST_(private)( join );
356 :
357 187901697 : ulong ele_idx = SLIST_(private_idx)( slist->head ); /* Not NULL as per contract */
358 187901697 : ulong next_idx = SLIST_(private_idx)( pool[ ele_idx ].SLIST_NEXT );
359 :
360 187901697 : SLIST_IDX_T dummy[1];
361 187901697 : *fd_ptr_if( !SLIST_(private_idx_is_null)( next_idx ), dummy+0, &slist->tail ) =
362 187901697 : SLIST_(private_cidx)( SLIST_(private_idx_null)() );
363 :
364 187901697 : slist->head = SLIST_(private_cidx)( next_idx );
365 187901697 : return ele_idx;
366 187901697 : }
367 :
368 : static inline SLIST_(t) *
369 : SLIST_(idx_insert_after)( SLIST_(t) * join,
370 : ulong ele_idx,
371 : ulong prev_idx,
372 62467059 : SLIST_ELE_T * pool ) {
373 62467059 : ulong next_idx = SLIST_(private_idx)( pool[ prev_idx ].SLIST_NEXT );
374 :
375 62467059 : pool[ ele_idx ].SLIST_NEXT = SLIST_(private_cidx)( next_idx );
376 :
377 62467059 : pool[ prev_idx ].SLIST_NEXT = SLIST_(private_cidx)( ele_idx );
378 :
379 62467059 : SLIST_IDX_T dummy[1];
380 62467059 : *fd_ptr_if( !SLIST_(private_idx_is_null)( next_idx ), dummy+0, &SLIST_(private)( join )->tail ) =
381 62467059 : SLIST_(private_cidx)( ele_idx );
382 :
383 62467059 : return join;
384 62467059 : }
385 :
386 : static inline SLIST_(t) *
387 : SLIST_(remove_all)( SLIST_(t) * join,
388 27 : SLIST_ELE_T * pool ) {
389 27 : (void)pool;
390 27 : SLIST_(private_t) * slist = SLIST_(private)( join );
391 27 : slist->head = SLIST_(private_cidx)( SLIST_(private_idx_null)() );
392 27 : slist->tail = SLIST_(private_cidx)( SLIST_(private_idx_null)() );
393 27 : return join;
394 27 : }
395 :
396 : FD_FN_PURE static inline SLIST_(iter_t)
397 : SLIST_(iter_init)( SLIST_(t) const * join,
398 374919222 : SLIST_ELE_T const * pool ) {
399 374919222 : (void)pool;
400 374919222 : return SLIST_(private_idx)( SLIST_(private_const)( join )->head );
401 374919222 : }
402 :
403 : FD_FN_CONST static inline int
404 : SLIST_(iter_done)( SLIST_(iter_t) iter,
405 : SLIST_(t) const * join,
406 1593543513 : SLIST_ELE_T const * pool ) {
407 1593543513 : (void)join; (void)pool;
408 1593543513 : return SLIST_(private_idx_is_null)( iter );
409 1593543513 : }
410 :
411 : FD_FN_PURE static inline SLIST_(iter_t)
412 : SLIST_(iter_next)( SLIST_(iter_t) iter,
413 : SLIST_(t) const * join,
414 1218624291 : SLIST_ELE_T const * pool ) {
415 1218624291 : (void)join;
416 1218624291 : return SLIST_(private_idx)( pool[ iter ].SLIST_NEXT );
417 1218624291 : }
418 :
419 : FD_FN_CONST static inline ulong
420 : SLIST_(iter_idx)( SLIST_(iter_t) iter,
421 : SLIST_(t) const * join,
422 187489653 : SLIST_ELE_T const * pool ) {
423 187489653 : (void)join; (void)pool;
424 187489653 : return iter;
425 187489653 : }
426 :
427 : FD_FN_PURE static inline SLIST_ELE_T *
428 : SLIST_(ele_peek_head)( SLIST_(t) const * join,
429 1876591440 : SLIST_ELE_T * pool ) {
430 1876591440 : return pool + SLIST_(idx_peek_head)( join, pool );
431 1876591440 : }
432 :
433 : FD_FN_PURE static inline SLIST_ELE_T const *
434 : SLIST_(ele_peek_head_const)( SLIST_(t) const * join,
435 1874626416 : SLIST_ELE_T const * pool ) {
436 1874626416 : return pool + SLIST_(idx_peek_head)( join, pool );
437 1874626416 : }
438 :
439 : FD_FN_PURE static inline SLIST_ELE_T *
440 : SLIST_(ele_peek_tail)( SLIST_(t) const * join,
441 1875019686 : SLIST_ELE_T * pool ) {
442 1875019686 : return pool + SLIST_(idx_peek_tail)( join, pool );
443 1875019686 : }
444 :
445 : FD_FN_PURE static inline SLIST_ELE_T const *
446 : SLIST_(ele_peek_tail_const)( SLIST_(t) const * join,
447 1874626416 : SLIST_ELE_T const * pool ) {
448 1874626416 : return pool + SLIST_(idx_peek_tail)( join, pool );
449 1874626416 : }
450 :
451 : static inline SLIST_(t) *
452 : SLIST_(ele_push_head)( SLIST_(t) * join,
453 : SLIST_ELE_T * ele,
454 31246809 : SLIST_ELE_T * pool ) {
455 31246809 : return SLIST_(idx_push_head)( join, (ulong)(ele-pool), pool );
456 31246809 : }
457 :
458 : static inline SLIST_(t) *
459 : SLIST_(ele_push_tail)( SLIST_(t) * join,
460 : SLIST_ELE_T * ele,
461 31680603 : SLIST_ELE_T * pool ) {
462 31680603 : return SLIST_(idx_push_tail)( join, (ulong)(ele-pool), pool );
463 31680603 : }
464 :
465 : static inline SLIST_ELE_T *
466 : SLIST_(ele_pop_head)( SLIST_(t) * join,
467 93740538 : SLIST_ELE_T * pool ) {
468 93740538 : return pool + SLIST_(idx_pop_head)( join, pool );
469 93740538 : }
470 :
471 : static inline SLIST_(t) *
472 : SLIST_(ele_insert_after)( SLIST_(t) * join,
473 : SLIST_ELE_T * ele,
474 : SLIST_ELE_T * prev,
475 31229655 : SLIST_ELE_T * pool ) {
476 31229655 : return SLIST_(idx_insert_after)( join, (ulong)(ele-pool), (ulong)(prev-pool), pool );
477 31229655 : }
478 :
479 : FD_FN_CONST static inline SLIST_ELE_T *
480 : SLIST_(iter_ele)( SLIST_(iter_t) iter,
481 : SLIST_(t) const * join,
482 187429599 : SLIST_ELE_T * pool ) {
483 187429599 : (void)join;
484 187429599 : return pool + iter;
485 187429599 : }
486 :
487 : FD_FN_CONST static inline SLIST_ELE_T const *
488 : SLIST_(iter_ele_const)( SLIST_(iter_t) iter,
489 : SLIST_(t) const * join,
490 0 : SLIST_ELE_T const * pool ) {
491 0 : (void)join;
492 0 : return pool + iter;
493 0 : }
494 :
495 : FD_PROTOTYPES_END
496 :
497 : #endif
498 :
499 : #if SLIST_IMPL_STYLE==1 /* need prototypes */
500 :
501 : FD_PROTOTYPES_BEGIN
502 :
503 : FD_FN_CONST ulong SLIST_(align) ( void );
504 : FD_FN_CONST ulong SLIST_(footprint)( void );
505 : void * SLIST_(new) ( void * shmem );
506 : SLIST_(t) * SLIST_(join) ( void * shslist );
507 : void * SLIST_(leave) ( SLIST_(t) * join );
508 : void * SLIST_(delete) ( void * shslist );
509 :
510 : int
511 : SLIST_(verify)( SLIST_(t) const * join,
512 : ulong ele_cnt,
513 : SLIST_ELE_T const * pool );
514 :
515 : FD_PROTOTYPES_END
516 :
517 : #else /* need implementations */
518 :
519 : #if SLIST_IMPL_STYLE==0 /* local only */
520 : #define SLIST_IMPL_STATIC FD_FN_UNUSED static
521 : #else
522 : #define SLIST_IMPL_STATIC
523 : #endif
524 :
525 : FD_PROTOTYPES_BEGIN
526 :
527 36132 : FD_FN_CONST SLIST_IMPL_STATIC ulong SLIST_(align) ( void ) { return alignof(SLIST_(t)); }
528 3 : FD_FN_CONST SLIST_IMPL_STATIC ulong SLIST_(footprint)( void ) { return sizeof( SLIST_(t)); }
529 :
530 : SLIST_IMPL_STATIC void *
531 12045 : SLIST_(new)( void * shmem ) {
532 :
533 12045 : if( FD_UNLIKELY( !shmem ) ) {
534 3 : FD_LOG_WARNING(( "NULL shmem" ));
535 3 : return NULL;
536 3 : }
537 :
538 12042 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, SLIST_(align)() ) ) ) {
539 3 : FD_LOG_WARNING(( "misaligned shmem" ));
540 3 : return NULL;
541 3 : }
542 :
543 : // Note: Guaranteed non-zero and not otherwise used
544 : //ulong footprint = SLIST_(footprint)();
545 : //if( FD_UNLIKELY( !footprint ) ) {
546 : // FD_LOG_WARNING(( "bad footprint" ));
547 : // return NULL;
548 : //}
549 :
550 12039 : SLIST_(private_t) * slist = (SLIST_(private_t) *)shmem;
551 :
552 12039 : slist->head = SLIST_(private_cidx)( SLIST_(private_idx_null)() );
553 12039 : slist->tail = SLIST_(private_cidx)( SLIST_(private_idx_null)() );
554 :
555 12039 : FD_COMPILER_MFENCE();
556 12039 : FD_VOLATILE( slist->magic ) = SLIST_MAGIC;
557 12039 : FD_COMPILER_MFENCE();
558 :
559 12039 : return shmem;
560 12042 : }
561 :
562 : SLIST_IMPL_STATIC SLIST_(t) *
563 12048 : SLIST_(join)( void * shslist ) {
564 12048 : SLIST_(private_t) * slist = (SLIST_(private_t) *)shslist;
565 :
566 12048 : if( FD_UNLIKELY( !slist ) ) {
567 3 : FD_LOG_WARNING(( "NULL shslist" ));
568 3 : return NULL;
569 3 : }
570 :
571 12045 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)slist, SLIST_(align)() ) ) ) {
572 3 : FD_LOG_WARNING(( "misaligned shslist" ));
573 3 : return NULL;
574 3 : }
575 :
576 12042 : if( FD_UNLIKELY( slist->magic!=SLIST_MAGIC ) ) {
577 3 : FD_LOG_WARNING(( "bad magic" ));
578 3 : return NULL;
579 3 : }
580 :
581 12039 : return (SLIST_(t) *)slist;
582 12042 : }
583 :
584 : SLIST_IMPL_STATIC void *
585 12039 : SLIST_(leave)( SLIST_(t) * join ) {
586 :
587 12039 : if( FD_UNLIKELY( !join ) ) {
588 3 : FD_LOG_WARNING(( "NULL join" ));
589 3 : return NULL;
590 3 : }
591 :
592 12036 : return (void *)join;
593 12039 : }
594 :
595 : SLIST_IMPL_STATIC void *
596 12045 : SLIST_(delete)( void * shslist ) {
597 12045 : SLIST_(private_t) * slist = (SLIST_(private_t) *)shslist;
598 :
599 12045 : if( FD_UNLIKELY( !slist ) ) {
600 3 : FD_LOG_WARNING(( "NULL shslist" ));
601 3 : return NULL;
602 3 : }
603 :
604 12042 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)slist, SLIST_(align)() ) ) ) {
605 3 : FD_LOG_WARNING(( "misaligned shslist" ));
606 3 : return NULL;
607 3 : }
608 :
609 12039 : if( FD_UNLIKELY( slist->magic!=SLIST_MAGIC ) ) {
610 3 : FD_LOG_WARNING(( "bad magic" ));
611 3 : return NULL;
612 3 : }
613 :
614 12036 : FD_COMPILER_MFENCE();
615 12036 : FD_VOLATILE( slist->magic ) = 0UL;
616 12036 : FD_COMPILER_MFENCE();
617 :
618 12036 : return shslist;
619 12039 : }
620 :
621 : SLIST_IMPL_STATIC int
622 : SLIST_(verify)( SLIST_(t) const * join,
623 : ulong ele_cnt,
624 187540263 : SLIST_ELE_T const * pool ) {
625 :
626 3750757227 : # define SLIST_TEST(c) do { \
627 3750757227 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
628 3750757227 : } while(0)
629 :
630 : /* Validate input args */
631 :
632 187540263 : SLIST_TEST( join );
633 187540263 : SLIST_TEST( ele_cnt<=SLIST_(ele_max)() );
634 187540263 : SLIST_TEST( (!!pool) | (!ele_cnt) );
635 :
636 : /* Iterate forward through the slist, validating as we go */
637 :
638 187540263 : SLIST_(private_t) const * slist = SLIST_(private_const)( join );
639 :
640 187540263 : SLIST_TEST( slist->magic==SLIST_MAGIC );
641 :
642 187540263 : ulong rem = ele_cnt;
643 187540263 : ulong prev_idx = SLIST_(private_idx_null)();
644 187540263 : ulong ele_idx = SLIST_(private_idx)( slist->head );
645 1594068219 : while( !SLIST_(private_idx_is_null)( ele_idx ) ) {
646 :
647 : /* Visit ele_idx */
648 :
649 1406527956 : SLIST_TEST( rem ); rem--; /* Test for cycles */
650 1406527956 : SLIST_TEST( ele_idx<ele_cnt ); /* Test valid ele_idx */
651 :
652 : /* Advance to next element */
653 :
654 1406527956 : prev_idx = ele_idx;
655 1406527956 : ele_idx = SLIST_(private_idx)( pool[ ele_idx ].SLIST_NEXT );
656 1406527956 : }
657 :
658 187540263 : SLIST_TEST( SLIST_(private_idx)( slist->tail )==prev_idx );
659 :
660 187540263 : # undef SLIST_TEST
661 :
662 187540263 : return 0;
663 187540263 : }
664 :
665 : FD_PROTOTYPES_END
666 :
667 : #undef SLIST_IMPL_STATIC
668 :
669 : #endif
670 :
671 : #undef SLIST_
672 :
673 : #undef SLIST_IMPL_STYLE
674 : #undef SLIST_MAGIC
675 : #undef SLIST_NEXT
676 : #undef SLIST_IDX_T
677 : #undef SLIST_ELE_T
678 : #undef SLIST_NAME
|
