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