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 : #include "../log/fd_log.h"
226 :
227 : /* Implementation *****************************************************/
228 :
229 : /* Constructors and verification log details on failure (rest only needs
230 : fd_bits.h, consider making logging a compile time option). */
231 :
232 45509733114 : #define SLIST_(n) FD_EXPAND_THEN_CONCAT3(SLIST_NAME,_,n)
233 :
234 : #if SLIST_IMPL_STYLE==0 || SLIST_IMPL_STYLE==1 /* need structures and inlines */
235 :
236 : struct SLIST_(private) {
237 :
238 : /* join points here */
239 :
240 : ulong magic; /* == SLIST_MAGIC */
241 : SLIST_IDX_T head; /* index of first list element (or idx_null if empty list) */
242 : SLIST_IDX_T tail; /* index of last list element (or idx_null if empty list) */
243 : };
244 :
245 : typedef struct SLIST_(private) SLIST_(private_t);
246 :
247 : typedef SLIST_(private_t) SLIST_(t);
248 :
249 : typedef ulong SLIST_(iter_t);
250 :
251 : FD_PROTOTYPES_BEGIN
252 :
253 : /* slist_private returns the location of the slist header for a current
254 : local join. Assumes join is a current local join.
255 : slist_private_const is a const correct version. */
256 :
257 : FD_FN_CONST static inline SLIST_(private_t) *
258 375803571 : SLIST_(private)( SLIST_(t) * join ) {
259 375803571 : return (SLIST_(private_t) *)join;
260 375803571 : }
261 :
262 : FD_FN_CONST static inline SLIST_(private_t) const *
263 13688298153 : SLIST_(private_const)( SLIST_(t) const * join ) {
264 13688298153 : return (SLIST_(private_t) const *)join;
265 13688298153 : }
266 :
267 : /* slist_private_{cidx,idx} compress / decompress 64-bit in-register
268 : indices to/from their in-memory representations. */
269 :
270 939533067 : FD_FN_CONST static inline SLIST_IDX_T SLIST_(private_cidx)( ulong idx ) { return (SLIST_IDX_T)idx; }
271 17064695904 : FD_FN_CONST static inline ulong SLIST_(private_idx) ( SLIST_IDX_T cidx ) { return (ulong) cidx; }
272 :
273 : /* slist_private_idx_null returns the element storage index that
274 : represents NULL. */
275 :
276 438401679 : FD_FN_CONST static inline ulong SLIST_(private_idx_null)( void ) { return (ulong)(SLIST_IDX_T)~0UL; }
277 :
278 : /* slist_private_idx_is_null returns 1 if idx is the NULL slist index
279 : and 0 otherwise. */
280 :
281 5439137136 : FD_FN_CONST static inline int SLIST_(private_idx_is_null)( ulong idx ) { return idx==(ulong)(SLIST_IDX_T)~0UL; }
282 :
283 187540266 : FD_FN_CONST static inline ulong SLIST_(ele_max)( void ) { return (ulong)(SLIST_IDX_T)~0UL; }
284 :
285 : FD_FN_PURE static inline int
286 : SLIST_(is_empty)( SLIST_(t) const * join,
287 1875721860 : SLIST_ELE_T const * pool ) {
288 1875721860 : (void)pool;
289 1875721860 : return SLIST_(private_idx_is_null)( SLIST_(private_idx)( SLIST_(private_const)( join )->head ) );
290 1875721860 : }
291 :
292 : FD_FN_PURE static inline ulong
293 : SLIST_(idx_peek_head)( SLIST_(t) const * join,
294 5625844290 : SLIST_ELE_T const * pool ) {
295 5625844290 : (void)pool;
296 : # if FD_TMPL_USE_HANDHOLDING
297 : if( FD_UNLIKELY( SLIST_(is_empty)( join, pool ) ) ) FD_LOG_CRIT(( "cannot peek on empty slist" ));
298 : # endif
299 5625844290 : return SLIST_(private_idx)( SLIST_(private_const)( join )->head );
300 5625844290 : }
301 :
302 : FD_FN_PURE static inline ulong
303 : SLIST_(idx_peek_tail)( SLIST_(t) const * join,
304 5624272518 : SLIST_ELE_T const * pool ) {
305 5624272518 : (void)pool;
306 : # if FD_TMPL_USE_HANDHOLDING
307 : if( FD_UNLIKELY( SLIST_(is_empty)( join, pool ) ) ) FD_LOG_CRIT(( "cannot peek on empty slist" ));
308 : # endif
309 5624272518 : return SLIST_(private_idx)( SLIST_(private_const)( join )->tail );
310 5624272518 : }
311 :
312 : static inline SLIST_(t) *
313 : SLIST_(idx_push_head)( SLIST_(t) * join,
314 : ulong ele_idx,
315 62499201 : SLIST_ELE_T * pool ) {
316 62499201 : SLIST_(private_t) * slist = SLIST_(private)( join );
317 :
318 62499201 : ulong head_idx = SLIST_(private_idx)( slist->head );
319 :
320 62499201 : pool[ ele_idx ].SLIST_NEXT = SLIST_(private_cidx)( head_idx );
321 :
322 62499201 : SLIST_IDX_T dummy[1];
323 62499201 : *fd_ptr_if( !SLIST_(private_idx_is_null)( head_idx ), dummy+0, &slist->tail ) =
324 62499201 : SLIST_(private_cidx)( ele_idx );
325 :
326 62499201 : slist->head = SLIST_(private_cidx)( ele_idx );
327 62499201 : return join;
328 62499201 : }
329 :
330 : static inline SLIST_(t) *
331 : SLIST_(idx_push_tail)( SLIST_(t) * join,
332 : ulong ele_idx,
333 62935587 : SLIST_ELE_T * pool ) {
334 62935587 : SLIST_(private_t) * slist = SLIST_(private)( join );
335 :
336 62935587 : ulong tail_idx = SLIST_(private_idx)( slist->tail );
337 :
338 62935587 : pool[ ele_idx ].SLIST_NEXT = SLIST_(private_cidx)( SLIST_(private_idx_null)() );
339 :
340 62935587 : *fd_ptr_if( !SLIST_(private_idx_is_null)( tail_idx ), &pool[ tail_idx ].SLIST_NEXT, &slist->head ) =
341 62935587 : SLIST_(private_cidx)( ele_idx );
342 :
343 62935587 : slist->tail = SLIST_(private_cidx)( ele_idx );
344 62935587 : return join;
345 62935587 : }
346 :
347 : static inline ulong
348 : SLIST_(idx_pop_head)( SLIST_(t) * join,
349 187901697 : SLIST_ELE_T * pool ) {
350 : # if FD_TMPL_USE_HANDHOLDING
351 : if( FD_UNLIKELY( SLIST_(is_empty)( join, pool ) ) ) FD_LOG_CRIT(( "cannot pop from empty slist" ));
352 : # endif
353 187901697 : SLIST_(private_t) * slist = SLIST_(private)( join );
354 :
355 187901697 : ulong ele_idx = SLIST_(private_idx)( slist->head ); /* Not NULL as per contract */
356 187901697 : ulong next_idx = SLIST_(private_idx)( pool[ ele_idx ].SLIST_NEXT );
357 :
358 187901697 : SLIST_IDX_T dummy[1];
359 187901697 : *fd_ptr_if( !SLIST_(private_idx_is_null)( next_idx ), dummy+0, &slist->tail ) =
360 187901697 : SLIST_(private_cidx)( SLIST_(private_idx_null)() );
361 :
362 187901697 : slist->head = SLIST_(private_cidx)( next_idx );
363 187901697 : return ele_idx;
364 187901697 : }
365 :
366 : static inline SLIST_(t) *
367 : SLIST_(idx_insert_after)( SLIST_(t) * join,
368 : ulong ele_idx,
369 : ulong prev_idx,
370 62467059 : SLIST_ELE_T * pool ) {
371 62467059 : ulong next_idx = SLIST_(private_idx)( pool[ prev_idx ].SLIST_NEXT );
372 :
373 62467059 : pool[ ele_idx ].SLIST_NEXT = SLIST_(private_cidx)( next_idx );
374 :
375 62467059 : pool[ prev_idx ].SLIST_NEXT = SLIST_(private_cidx)( ele_idx );
376 :
377 62467059 : SLIST_IDX_T dummy[1];
378 62467059 : *fd_ptr_if( !SLIST_(private_idx_is_null)( next_idx ), dummy+0, &SLIST_(private)( join )->tail ) =
379 62467059 : SLIST_(private_cidx)( ele_idx );
380 :
381 62467059 : return join;
382 62467059 : }
383 :
384 : static inline SLIST_(t) *
385 : SLIST_(remove_all)( SLIST_(t) * join,
386 27 : SLIST_ELE_T * pool ) {
387 27 : (void)pool;
388 27 : SLIST_(private_t) * slist = SLIST_(private)( join );
389 27 : slist->head = SLIST_(private_cidx)( SLIST_(private_idx_null)() );
390 27 : slist->tail = SLIST_(private_cidx)( SLIST_(private_idx_null)() );
391 27 : return join;
392 27 : }
393 :
394 : FD_FN_PURE static inline SLIST_(iter_t)
395 : SLIST_(iter_init)( SLIST_(t) const * join,
396 374919222 : SLIST_ELE_T const * pool ) {
397 374919222 : (void)pool;
398 374919222 : return SLIST_(private_idx)( SLIST_(private_const)( join )->head );
399 374919222 : }
400 :
401 : FD_FN_CONST static inline int
402 : SLIST_(iter_done)( SLIST_(iter_t) iter,
403 : SLIST_(t) const * join,
404 1593543513 : SLIST_ELE_T const * pool ) {
405 1593543513 : (void)join; (void)pool;
406 1593543513 : return SLIST_(private_idx_is_null)( iter );
407 1593543513 : }
408 :
409 : FD_FN_PURE static inline SLIST_(iter_t)
410 : SLIST_(iter_next)( SLIST_(iter_t) iter,
411 : SLIST_(t) const * join,
412 1218624291 : SLIST_ELE_T const * pool ) {
413 1218624291 : (void)join;
414 1218624291 : return SLIST_(private_idx)( pool[ iter ].SLIST_NEXT );
415 1218624291 : }
416 :
417 : FD_FN_CONST static inline ulong
418 : SLIST_(iter_idx)( SLIST_(iter_t) iter,
419 : SLIST_(t) const * join,
420 187489653 : SLIST_ELE_T const * pool ) {
421 187489653 : (void)join; (void)pool;
422 187489653 : return iter;
423 187489653 : }
424 :
425 : FD_FN_PURE static inline SLIST_ELE_T *
426 : SLIST_(ele_peek_head)( SLIST_(t) const * join,
427 1876591440 : SLIST_ELE_T * pool ) {
428 1876591440 : return pool + SLIST_(idx_peek_head)( join, pool );
429 1876591440 : }
430 :
431 : FD_FN_PURE static inline SLIST_ELE_T const *
432 : SLIST_(ele_peek_head_const)( SLIST_(t) const * join,
433 1874626416 : SLIST_ELE_T const * pool ) {
434 1874626416 : return pool + SLIST_(idx_peek_head)( join, pool );
435 1874626416 : }
436 :
437 : FD_FN_PURE static inline SLIST_ELE_T *
438 : SLIST_(ele_peek_tail)( SLIST_(t) const * join,
439 1875019686 : SLIST_ELE_T * pool ) {
440 1875019686 : return pool + SLIST_(idx_peek_tail)( join, pool );
441 1875019686 : }
442 :
443 : FD_FN_PURE static inline SLIST_ELE_T const *
444 : SLIST_(ele_peek_tail_const)( SLIST_(t) const * join,
445 1874626416 : SLIST_ELE_T const * pool ) {
446 1874626416 : return pool + SLIST_(idx_peek_tail)( join, pool );
447 1874626416 : }
448 :
449 : static inline SLIST_(t) *
450 : SLIST_(ele_push_head)( SLIST_(t) * join,
451 : SLIST_ELE_T * ele,
452 31246809 : SLIST_ELE_T * pool ) {
453 31246809 : return SLIST_(idx_push_head)( join, (ulong)(ele-pool), pool );
454 31246809 : }
455 :
456 : static inline SLIST_(t) *
457 : SLIST_(ele_push_tail)( SLIST_(t) * join,
458 : SLIST_ELE_T * ele,
459 31680603 : SLIST_ELE_T * pool ) {
460 31680603 : return SLIST_(idx_push_tail)( join, (ulong)(ele-pool), pool );
461 31680603 : }
462 :
463 : static inline SLIST_ELE_T *
464 : SLIST_(ele_pop_head)( SLIST_(t) * join,
465 93740538 : SLIST_ELE_T * pool ) {
466 93740538 : return pool + SLIST_(idx_pop_head)( join, pool );
467 93740538 : }
468 :
469 : static inline SLIST_(t) *
470 : SLIST_(ele_insert_after)( SLIST_(t) * join,
471 : SLIST_ELE_T * ele,
472 : SLIST_ELE_T * prev,
473 31229655 : SLIST_ELE_T * pool ) {
474 31229655 : return SLIST_(idx_insert_after)( join, (ulong)(ele-pool), (ulong)(prev-pool), pool );
475 31229655 : }
476 :
477 : FD_FN_CONST static inline SLIST_ELE_T *
478 : SLIST_(iter_ele)( SLIST_(iter_t) iter,
479 : SLIST_(t) const * join,
480 187429599 : SLIST_ELE_T * pool ) {
481 187429599 : (void)join;
482 187429599 : return pool + iter;
483 187429599 : }
484 :
485 : FD_FN_CONST static inline SLIST_ELE_T const *
486 : SLIST_(iter_ele_const)( SLIST_(iter_t) iter,
487 : SLIST_(t) const * join,
488 0 : SLIST_ELE_T const * pool ) {
489 0 : (void)join;
490 0 : return pool + iter;
491 0 : }
492 :
493 : FD_PROTOTYPES_END
494 :
495 : #endif
496 :
497 : #if SLIST_IMPL_STYLE==1 /* need prototypes */
498 :
499 : FD_PROTOTYPES_BEGIN
500 :
501 : FD_FN_CONST ulong SLIST_(align) ( void );
502 : FD_FN_CONST ulong SLIST_(footprint)( void );
503 : void * SLIST_(new) ( void * shmem );
504 : SLIST_(t) * SLIST_(join) ( void * shslist );
505 : void * SLIST_(leave) ( SLIST_(t) * join );
506 : void * SLIST_(delete) ( void * shslist );
507 :
508 : int
509 : SLIST_(verify)( SLIST_(t) const * join,
510 : ulong ele_cnt,
511 : SLIST_ELE_T const * pool );
512 :
513 : FD_PROTOTYPES_END
514 :
515 : #else /* need implementations */
516 :
517 : #if SLIST_IMPL_STYLE==0 /* local only */
518 : #define SLIST_IMPL_STATIC FD_FN_UNUSED static
519 : #else
520 : #define SLIST_IMPL_STATIC
521 : #endif
522 :
523 : FD_PROTOTYPES_BEGIN
524 :
525 36132 : FD_FN_CONST SLIST_IMPL_STATIC ulong SLIST_(align) ( void ) { return alignof(SLIST_(t)); }
526 3 : FD_FN_CONST SLIST_IMPL_STATIC ulong SLIST_(footprint)( void ) { return sizeof( SLIST_(t)); }
527 :
528 : SLIST_IMPL_STATIC void *
529 12045 : SLIST_(new)( void * shmem ) {
530 :
531 12045 : if( FD_UNLIKELY( !shmem ) ) {
532 3 : FD_LOG_WARNING(( "NULL shmem" ));
533 3 : return NULL;
534 3 : }
535 :
536 12042 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, SLIST_(align)() ) ) ) {
537 3 : FD_LOG_WARNING(( "misaligned shmem" ));
538 3 : return NULL;
539 3 : }
540 :
541 : // Note: Guaranteed non-zero and not otherwise used
542 : //ulong footprint = SLIST_(footprint)();
543 : //if( FD_UNLIKELY( !footprint ) ) {
544 : // FD_LOG_WARNING(( "bad footprint" ));
545 : // return NULL;
546 : //}
547 :
548 12039 : SLIST_(private_t) * slist = (SLIST_(private_t) *)shmem;
549 :
550 12039 : slist->head = SLIST_(private_cidx)( SLIST_(private_idx_null)() );
551 12039 : slist->tail = SLIST_(private_cidx)( SLIST_(private_idx_null)() );
552 :
553 12039 : FD_COMPILER_MFENCE();
554 12039 : FD_VOLATILE( slist->magic ) = SLIST_MAGIC;
555 12039 : FD_COMPILER_MFENCE();
556 :
557 12039 : return shmem;
558 12042 : }
559 :
560 : SLIST_IMPL_STATIC SLIST_(t) *
561 12048 : SLIST_(join)( void * shslist ) {
562 12048 : SLIST_(private_t) * slist = (SLIST_(private_t) *)shslist;
563 :
564 12048 : if( FD_UNLIKELY( !slist ) ) {
565 3 : FD_LOG_WARNING(( "NULL shslist" ));
566 3 : return NULL;
567 3 : }
568 :
569 12045 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)slist, SLIST_(align)() ) ) ) {
570 3 : FD_LOG_WARNING(( "misaligned shslist" ));
571 3 : return NULL;
572 3 : }
573 :
574 12042 : if( FD_UNLIKELY( slist->magic!=SLIST_MAGIC ) ) {
575 3 : FD_LOG_WARNING(( "bad magic" ));
576 3 : return NULL;
577 3 : }
578 :
579 12039 : return (SLIST_(t) *)slist;
580 12042 : }
581 :
582 : SLIST_IMPL_STATIC void *
583 12039 : SLIST_(leave)( SLIST_(t) * join ) {
584 :
585 12039 : if( FD_UNLIKELY( !join ) ) {
586 3 : FD_LOG_WARNING(( "NULL join" ));
587 3 : return NULL;
588 3 : }
589 :
590 12036 : return (void *)join;
591 12039 : }
592 :
593 : SLIST_IMPL_STATIC void *
594 12045 : SLIST_(delete)( void * shslist ) {
595 12045 : SLIST_(private_t) * slist = (SLIST_(private_t) *)shslist;
596 :
597 12045 : if( FD_UNLIKELY( !slist ) ) {
598 3 : FD_LOG_WARNING(( "NULL shslist" ));
599 3 : return NULL;
600 3 : }
601 :
602 12042 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)slist, SLIST_(align)() ) ) ) {
603 3 : FD_LOG_WARNING(( "misaligned shslist" ));
604 3 : return NULL;
605 3 : }
606 :
607 12039 : if( FD_UNLIKELY( slist->magic!=SLIST_MAGIC ) ) {
608 3 : FD_LOG_WARNING(( "bad magic" ));
609 3 : return NULL;
610 3 : }
611 :
612 12036 : FD_COMPILER_MFENCE();
613 12036 : FD_VOLATILE( slist->magic ) = 0UL;
614 12036 : FD_COMPILER_MFENCE();
615 :
616 12036 : return shslist;
617 12039 : }
618 :
619 : SLIST_IMPL_STATIC int
620 : SLIST_(verify)( SLIST_(t) const * join,
621 : ulong ele_cnt,
622 187540263 : SLIST_ELE_T const * pool ) {
623 :
624 3750757227 : # define SLIST_TEST(c) do { \
625 3750757227 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
626 3750757227 : } while(0)
627 :
628 : /* Validate input args */
629 :
630 187540263 : SLIST_TEST( join );
631 187540263 : SLIST_TEST( ele_cnt<=SLIST_(ele_max)() );
632 187540263 : SLIST_TEST( (!!pool) | (!ele_cnt) );
633 :
634 : /* Iterate forward through the slist, validating as we go */
635 :
636 187540263 : SLIST_(private_t) const * slist = SLIST_(private_const)( join );
637 :
638 187540263 : SLIST_TEST( slist->magic==SLIST_MAGIC );
639 :
640 187540263 : ulong rem = ele_cnt;
641 187540263 : ulong prev_idx = SLIST_(private_idx_null)();
642 187540263 : ulong ele_idx = SLIST_(private_idx)( slist->head );
643 1594068219 : while( !SLIST_(private_idx_is_null)( ele_idx ) ) {
644 :
645 : /* Visit ele_idx */
646 :
647 1406527956 : SLIST_TEST( rem ); rem--; /* Test for cycles */
648 1406527956 : SLIST_TEST( ele_idx<ele_cnt ); /* Test valid ele_idx */
649 :
650 : /* Advance to next element */
651 :
652 1406527956 : prev_idx = ele_idx;
653 1406527956 : ele_idx = SLIST_(private_idx)( pool[ ele_idx ].SLIST_NEXT );
654 1406527956 : }
655 :
656 187540263 : SLIST_TEST( SLIST_(private_idx)( slist->tail )==prev_idx );
657 :
658 187540263 : # undef SLIST_TEST
659 :
660 187540263 : return 0;
661 187540263 : }
662 :
663 : FD_PROTOTYPES_END
664 :
665 : #undef SLIST_IMPL_STATIC
666 :
667 : #endif
668 :
669 : #undef SLIST_
670 :
671 : #undef SLIST_IMPL_STYLE
672 : #undef SLIST_MAGIC
673 : #undef SLIST_NEXT
674 : #undef SLIST_IDX_T
675 : #undef SLIST_ELE_T
676 : #undef SLIST_NAME
|
