Line data Source code
1 : /* Generate prototypes, inlines and/or implementations for HPC doubly
2 : linked lists. A dlist can store a practically unbounded number of
3 : elements. Typical dlist operations are generally a fast O(1) time
4 : and dlist 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, other dlists, etc. Likewise, a dlist can be persisted
8 : beyond the lifetime of the creating process, used concurrently in
9 : many common operations, used inter-process, relocated in memory,
10 : naively 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 prev; // Technically "DLIST_IDX_T DLIST_PREV" (default is ulong prev), do not modify while element is in the dlist
19 : ulong next; // Technically "DLIST_IDX_T DLIST_NEXT" (default is ulong next), do not modify while element is in the dlist
20 : ... prev and next can be located arbitrarily in the element and
21 : ... can be reused for other purposes when the element is not in a
22 : ... dlist. An element should not be moved / released while an
23 : ... element is in a dlist
24 : };
25 :
26 : typedef struct myele myele_t;
27 :
28 : #define DLIST_NAME mydlist
29 : #define DLIST_ELE_T myele_t
30 : #include "tmpl/fd_dlist.c"
31 :
32 : will declare the following APIs as a header only style library in the
33 : compilation unit:
34 :
35 : // mydlist_ele_max returns the theoretical maximum number of
36 : // elements that can be held in a mydlist.
37 :
38 : ulong mydlist_ele_max( void );
39 :
40 : // mydlist_{align,footprint} returns the alignment and footprint
41 : // needed for a memory region to be used as a mydlist. align will
42 : // be an integer power-of-two and footprint will be a multiple of
43 : // align. The values will be compile-time declaration friendly
44 : // (e.g. "mydlist_t mem[1];" will have the correct alignment and
45 : // footprint and not be larger than 4096).
46 : //
47 : // mydlist_new formats a memory region with the appropriate
48 : // alignment and footprint whose first byte in the caller's address
49 : // space is pointed to by shmem as a mydlist. Returns shmem on
50 : // success and NULL on failure (logs details). Caller is not
51 : // joined on return. The dlist will be empty.
52 : //
53 : // mydlist_join joins a mydlist. Assumes shdlist points at a
54 : // memory region formatted as a mydlist in the caller's address
55 : // space. Returns a handle to the caller's local join on success
56 : // and NULL on failure (logs details). Do not assume this is a
57 : // simple cast of shdlist!
58 : //
59 : // mydlist_leave leaves a mydlist. Assumes join points to a
60 : // current local join. Returns shdlist used on join. Do not
61 : // assume this is a simple cast of join!
62 : //
63 : // mydlist_delete unformats a memory region used as a mydlist.
64 : // Assumes shdlist points to a memory region in the caller's local
65 : // address space formatted as a mydlist, that there are no joins to
66 : // the mydlist and that any application cleanup of the entries has
67 : // already been done. Returns shdlist on success and NULL on
68 : // failure.
69 :
70 : ulong mydlist_align ( void );
71 : ulong mydlist_footprint( void );
72 : void * mydlist_new ( void * shmem );
73 : mydlist_t * mydlist_join ( void * shdlist );
74 : void * mydlist_leave ( mydlist_t * join );
75 : void * mydlist_delete ( void * shdlist );
76 :
77 : // The below APIs assume join is a current local join to a mydlist
78 : // and pool is a current local join to the element storage backing
79 : // the dlist.
80 : //
81 : // mydlist_is_empty returns 1 if the dlist is empty and 0
82 : // otherwise.
83 : //
84 : // mydlist_idx_peek_{head,tail} returns the pool index of the
85 : // dlist's {head,tail}. Assumes dlist is not empty.
86 :
87 : int mydlist_is_empty( mydlist_t const * join, myele_t const * pool );
88 :
89 : ulong mydlist_idx_peek_head( mydlist_t const * join, myele_t const * pool );
90 : ulong mydlist_idx_peek_tail( mydlist_t const * join, myele_t const * pool );
91 :
92 : // mydlist_idx_push_{head,tail} pushes the pool element whose index
93 : // is ele_idx to the dlist's {head,tail} and returns join. Assumes
94 : // ele_idx valid and not already in the dlist.
95 : /
96 : // mydlist_idx_pop_{head,tail} pops the pool element at the dlist's
97 : // {head,tail} and returns its pool index. Assumes dlist is not
98 : // empty.
99 : //
100 : // mydlist_idx_insert_{before,after} inserts the pool element whose
101 : // index is ele_idx into the dlist immediately {before,after} the
102 : // pool element whose index is {next_idx,prev_idx} and returns
103 : // join. Assumes ele_idx is valid and not already in the dlist and
104 : // {next_idx,prev_idx} are already in the dlist.
105 : //
106 : // mydlist_idx_remove removes the pool element whose index is
107 : // ele_idx from the dlist and returns join. Assumes ele_idx is in
108 : // the dlist already.
109 : //
110 : // mydlist_idx_replace replaces the pool element whose index is
111 : // old_idx with the pool element whose index is ele_idx in the
112 : // dlist and returns join. Assumes ele_idx is not in the dlist and
113 : // old_idx is in the dlist already.
114 :
115 : mydlist_t * mydlist_idx_push_head ( mydlist_t * join, ulong ele_idx, myele_t * pool );
116 : mydlist_t * mydlist_idx_push_tail ( mydlist_t * join, ulong ele_idx, myele_t * pool );
117 : ulong mydlist_idx_pop_head ( mydlist_t * join, myele_t * pool );
118 : ulong mydlist_idx_pop_tail ( mydlist_t * join, myele_t * pool );
119 : mydlist_t * mydlist_idx_insert_before( mydlist_t * join, ulong ele_idx, ulong next_idx, myele_t * pool );
120 : mydlist_t * mydlist_idx_insert_after ( mydlist_t * join, ulong ele_idx, ulong prev_idx, myele_t * pool );
121 : mydlist_t * mydlist_idx_remove ( mydlist_t * join, ulong ele_idx, myele_t * pool );
122 : mydlist_t * mydlist_idx_replace ( mydlist_t * join, ulong ele_idx, ulong old_idx, myele_t * pool );
123 :
124 : // mydlist_remove_all removes all elements from the dlist and
125 : // returns join. It is the caller's responsibility to release all
126 : // elements to the pool as might be necessary.
127 :
128 : mydlist_t * mydlist_remove_all( mydlist_t * join, myele_t * pool );
129 :
130 : // mydlist_iter_* support fast ordered forward (head to tail) and
131 : // reverse (tail to head) iteration over all the elements in a
132 : // dlist. Example usage:
133 : //
134 : // for( mydlist_iter_t iter = mydlist_iter_rev_init( join, pool );
135 : // !mydlist_iter_done( iter, join, pool );
136 : // iter = mydlist_iter_rev_next( iter, join, pool ) ) {
137 : // ulong ele_idx = mydlist_iter_idx( iter, join, pool );
138 : //
139 : // ... process element here
140 : //
141 : // ... IMPORTANT! It is generally safe to insert elements
142 : // ... here (though they might not be covered by this
143 : // ... iteration). It is also generally safe to remove any
144 : // ... element but the current element here (the removed
145 : // ... element might have already been iterated over). It is
146 : // ... straightforward to make a variant of this iterator
147 : // ... that would support removing the current element here
148 : // ... if desired.
149 : // }
150 :
151 : struct mydlist_iter_private { ... internal use only ... };
152 : typedef struct mydlist_iter_private mydlist_iter_t;
153 :
154 : mydlist_iter_t mydlist_iter_fwd_init( mydlist_t const * join, myele_t const * pool );
155 : mydlist_iter_t mydlist_iter_rev_init( mydlist_t const * join, myele_t const * pool );
156 : int mydlist_iter_done ( mydlist_iter_t iter, mydlist_t const * join, myele_t const * pool );
157 : mydlist_iter_t mydlist_iter_fwd_next( mydlist_iter_t iter, mydlist_t const * join, myele_t const * pool ); // assumes !done
158 : mydlist_iter_t mydlist_iter_rev_next( mydlist_iter_t iter, mydlist_t const * join, myele_t const * pool ); // assumes !done
159 : ulong mydlist_iter_idx ( mydlist_iter_t iter, mydlist_t const * join, myele_t const * pool ); // assumes !done
160 :
161 : // mydlist_verify returns 0 if the mydlist is not obviously corrupt
162 : // or -1 (i.e. ERR_INVAL) otherwise (logs details).
163 :
164 : int
165 : mydlist_verify( mydlist_t const * join, // Current local join to a mydlist.
166 : ulong ele_cnt, // Element storage size, in [0,mydlist_ele_max()]
167 : myele_t const * pool ); // Current local join to element storage, indexed [0,ele_cnt)
168 :
169 : // The above APIs have helpers that operate purely in the caller's
170 : // local address space when applicable. The various elements
171 : // passed to / returned from these functions should be / will be
172 : // from the dlist's underlying pool.
173 :
174 : myele_t * mydlist_ele_peek_head( mydlist_t const * join, myele_t * pool );
175 : myele_t * mydlist_ele_peek_tail( mydlist_t const * join, myele_t * pool );
176 :
177 : mydlist_t * mydlist_ele_push_head ( mydlist_t * join, myele_t * ele, myele_t * pool );
178 : mydlist_t * mydlist_ele_push_tail ( mydlist_t * join, myele_t * ele, myele_t * pool );
179 : myele_t * mydlist_ele_pop_head ( mydlist_t * join, myele_t * pool );
180 : myele_t * mydlist_ele_pop_tail ( mydlist_t * join, myele_t * pool );
181 : mydlist_t * mydlist_ele_insert_before( mydlist_t * join, myele_t * ele, myele_t * next, myele_t * pool );
182 : mydlist_t * mydlist_ele_insert_after ( mydlist_t * join, myele_t * ele, myele_t * prev, myele_t * pool );
183 : mydlist_t * mydlist_ele_replace ( mydlist_t * join, myele_t * ele, myele_t * old, myele_t * pool );
184 : mydlist_t * mydlist_ele_remove ( mydlist_t * join, myele_t * ele, myele_t * pool );
185 :
186 : myele_t * mydlist_iter_ele( mydlist_iter_t iter, mydlist_t const * join, myele_t * pool );
187 :
188 : // ... and const correct helpers when applicable
189 :
190 : myele_t const * mydlist_ele_peek_head_const( mydlist_t const * join, myele_t const * pool );
191 : myele_t const * mydlist_ele_peek_tail_const( mydlist_t const * join, myele_t const * pool );
192 :
193 : myele_t const * mydlist_iter_ele_const( mydlist_iter_t iter, mydlist_t const * join, myele_t const * pool );
194 :
195 : You can do this as often as you like in a compilation unit to get
196 : different types of dlists. Variants exist for making header
197 : prototypes only and/or implementations only if making a library for
198 : use across multiple compilation units. Further, options exist to use
199 : different hashing functions, comparison functions, etc as detailed
200 : below. */
201 :
202 : /* TODO: DOC CONCURRENCY REQUIREMENTS */
203 :
204 : /* DLIST_NAME gives the API prefix to use for a dlist */
205 :
206 : #ifndef DLIST_NAME
207 : #error "Define DLIST_NAME"
208 : #endif
209 :
210 : /* DLIST_ELE_T is the dlist element type. */
211 :
212 : #ifndef DLIST_ELE_T
213 : #error "Define DLIST_ELE_T"
214 : #endif
215 :
216 : /* DLIST_IDX_T is the type used for the prev and next fields in the
217 : DLIST_ELE_T. Should be a primitive unsigned integer type. Defaults
218 : to ulong. A dlist can't use element memory regions with more
219 : elements than the maximum value that can be represented by a
220 : DLIST_IDX_T. (E.g. if ushort, the maximum size element store
221 : supported by the dlist is 65535 elements.) */
222 :
223 : #ifndef DLIST_IDX_T
224 : #define DLIST_IDX_T ulong
225 : #endif
226 :
227 : /* DLIST_PREV is the DLIST_ELE_T prev field */
228 :
229 : #ifndef DLIST_PREV
230 24315 : #define DLIST_PREV prev
231 : #endif
232 :
233 : /* DLIST_NEXT is the DLIST_ELE_T next field */
234 :
235 : #ifndef DLIST_NEXT
236 24414 : #define DLIST_NEXT next
237 : #endif
238 :
239 : /* DLIST_MAGIC is the magic number to use for the structure to aid in
240 : persistent and/or IPC usage. */
241 :
242 : #ifndef DLIST_MAGIC
243 3381 : #define DLIST_MAGIC (0xf17eda2c37d71570UL) /* firedancer dlist version 0 */
244 : #endif
245 :
246 : /* 0 - local use only
247 : 1 - library header declaration
248 : 2 - library implementation */
249 :
250 : #ifndef DLIST_IMPL_STYLE
251 : #define DLIST_IMPL_STYLE 0
252 : #endif
253 :
254 : #if FD_TMPL_USE_HANDHOLDING
255 : #include "../log/fd_log.h"
256 : #endif
257 :
258 : /* Implementation *****************************************************/
259 :
260 : /* Constructors and verification log details on failure (rest only needs
261 : fd_bits.h, consider making logging a compile time option). */
262 :
263 34565604315 : #define DLIST_(n) FD_EXPAND_THEN_CONCAT3(DLIST_NAME,_,n)
264 :
265 : #if DLIST_IMPL_STYLE==0 || DLIST_IMPL_STYLE==1 /* need structures and inlines */
266 :
267 : struct DLIST_(private) {
268 :
269 : /* join points here */
270 :
271 : ulong magic; /* == DLIST_MAGIC */
272 : DLIST_IDX_T head; /* index of first list element (or idx_null if empty list) */
273 : DLIST_IDX_T tail; /* index of last list element (or idx_null if empty list) */
274 : };
275 :
276 : typedef struct DLIST_(private) DLIST_(private_t);
277 :
278 : typedef DLIST_(private_t) DLIST_(t);
279 :
280 : typedef ulong DLIST_(iter_t);
281 :
282 : FD_PROTOTYPES_BEGIN
283 :
284 : /* dlist_private returns the location of the dlist header for a current
285 : local join. Assumes join is a current local join.
286 : dlist_private_const is a const correct version. */
287 :
288 : FD_FN_CONST static inline DLIST_(private_t) *
289 1331348004 : DLIST_(private)( DLIST_(t) * join ) {
290 1331348004 : return (DLIST_(private_t) *)join;
291 1331348004 : }
292 :
293 : FD_FN_CONST static inline DLIST_(private_t) const *
294 7462087932 : DLIST_(private_const)( DLIST_(t) const * join ) {
295 7462087932 : return (DLIST_(private_t) const *)join;
296 7462087932 : }
297 :
298 : /* dlist_private_{cidx,idx} compress / decompress 64-bit in-register
299 : indices to/from their in-memory representations. */
300 :
301 4125310920 : FD_FN_CONST static inline DLIST_IDX_T DLIST_(private_cidx)( ulong idx ) { return (DLIST_IDX_T)idx; }
302 12374989575 : FD_FN_CONST static inline ulong DLIST_(private_idx) ( DLIST_IDX_T cidx ) { return (ulong) cidx; }
303 :
304 : /* dlist_private_idx_null returns the element storage index that
305 : represents NULL. */
306 :
307 825063822 : FD_FN_CONST static inline ulong DLIST_(private_idx_null)( void ) { return (ulong)(DLIST_IDX_T)~0UL; }
308 :
309 : /* dlist_private_idx_is_null returns 1 if idx is the NULL dlist index
310 : and 0 otherwise. */
311 :
312 5812740267 : FD_FN_CONST static inline int DLIST_(private_idx_is_null)( ulong idx ) { return idx==(ulong)(DLIST_IDX_T)~0UL; }
313 :
314 187477731 : FD_FN_CONST static ulong DLIST_(ele_max)( void ) { return (ulong)(DLIST_IDX_T)~0UL; }
315 :
316 : FD_FN_PURE static inline int
317 : DLIST_(is_empty)( DLIST_(t) const * join,
318 1124963763 : DLIST_ELE_T const * pool ) {
319 1124963763 : (void)pool;
320 1124963763 : return DLIST_(private_idx_is_null)( DLIST_(private_idx)( DLIST_(private_const)( join )->head ) );
321 1124963763 : }
322 :
323 : FD_FN_PURE static inline ulong
324 : DLIST_(idx_peek_head)( DLIST_(t) const * join,
325 2699814876 : DLIST_ELE_T const * pool ) {
326 2699814876 : (void)pool;
327 : # if FD_TMPL_USE_HANDHOLDING
328 : if( FD_UNLIKELY( DLIST_(is_empty)( join, pool ) ) ) FD_LOG_CRIT(( "cannot peek on empty dlist" ));
329 : # endif
330 2699814876 : return DLIST_(private_idx)( DLIST_(private_const)( join )->head );
331 2699814876 : }
332 :
333 : FD_FN_PURE static inline ulong
334 : DLIST_(idx_peek_tail)( DLIST_(t) const * join,
335 2699814870 : DLIST_ELE_T const * pool ) {
336 2699814870 : (void)pool;
337 : # if FD_TMPL_USE_HANDHOLDING
338 : if( FD_UNLIKELY( DLIST_(is_empty)( join, pool ) ) ) FD_LOG_CRIT(( "cannot peek on empty dlist" ));
339 : # endif
340 2699814870 : return DLIST_(private_idx)( DLIST_(private_const)( join )->tail );
341 2699814870 : }
342 :
343 : static inline DLIST_(t) *
344 : DLIST_(idx_push_head)( DLIST_(t) * join,
345 : ulong ele_idx,
346 168756039 : DLIST_ELE_T * pool ) {
347 168756039 : DLIST_(private_t) * dlist = DLIST_(private)( join );
348 :
349 168756039 : ulong head_idx = DLIST_(private_idx)( dlist->head );
350 :
351 168756039 : pool[ ele_idx ].DLIST_PREV = DLIST_(private_cidx)( DLIST_(private_idx_null)() );
352 168756039 : pool[ ele_idx ].DLIST_NEXT = DLIST_(private_cidx)( head_idx );
353 :
354 168756039 : *fd_ptr_if( !DLIST_(private_idx_is_null)( head_idx ), &pool[ head_idx ].DLIST_PREV, &dlist->tail ) =
355 168756039 : DLIST_(private_cidx)( ele_idx );
356 :
357 168756039 : dlist->head = DLIST_(private_cidx)( ele_idx );
358 168756039 : return join;
359 168756039 : }
360 :
361 : static inline DLIST_(t) *
362 : DLIST_(idx_push_tail)( DLIST_(t) * join,
363 : ulong ele_idx,
364 168766356 : DLIST_ELE_T * pool ) {
365 168766356 : DLIST_(private_t) * dlist = DLIST_(private)( join );
366 :
367 168766356 : ulong tail_idx = DLIST_(private_idx)( dlist->tail );
368 :
369 168766356 : pool[ ele_idx ].DLIST_PREV = DLIST_(private_cidx)( tail_idx );
370 168766356 : pool[ ele_idx ].DLIST_NEXT = DLIST_(private_cidx)( DLIST_(private_idx_null)() );
371 :
372 168766356 : *fd_ptr_if( !DLIST_(private_idx_is_null)( tail_idx ), &pool[ tail_idx ].DLIST_NEXT, &dlist->head ) =
373 168766356 : DLIST_(private_cidx)( ele_idx );
374 :
375 168766356 : dlist->tail = DLIST_(private_cidx)( ele_idx );
376 168766356 : return join;
377 168766356 : }
378 :
379 : static inline ulong
380 : DLIST_(idx_pop_head)( DLIST_(t) * join,
381 150031173 : DLIST_ELE_T * pool ) {
382 : # if FD_TMPL_USE_HANDHOLDING
383 : if( FD_UNLIKELY( DLIST_(is_empty)( join, pool ) ) ) FD_LOG_CRIT(( "cannot pop from empty dlist" ));
384 : # endif
385 150031173 : DLIST_(private_t) * dlist = DLIST_(private)( join );
386 :
387 150031173 : ulong ele_idx = DLIST_(private_idx)( dlist->head ); /* Not NULL as per contract */
388 150031173 : ulong next_idx = DLIST_(private_idx)( pool[ ele_idx ].DLIST_NEXT );
389 :
390 150031173 : *fd_ptr_if( !DLIST_(private_idx_is_null)( next_idx ), &pool[ next_idx ].DLIST_PREV, &dlist->tail ) =
391 150031173 : DLIST_(private_cidx)( DLIST_(private_idx_null)() );
392 :
393 150031173 : dlist->head = DLIST_(private_cidx)( next_idx );
394 150031173 : return ele_idx;
395 150031173 : }
396 :
397 : static inline ulong
398 : DLIST_(idx_pop_tail)( DLIST_(t) * join,
399 150025710 : DLIST_ELE_T * pool ) {
400 : # if FD_TMPL_USE_HANDHOLDING
401 : if( FD_UNLIKELY( DLIST_(is_empty)( join, pool ) ) ) FD_LOG_CRIT(( "cannot pop from empty dlist" ));
402 : # endif
403 150025710 : DLIST_(private_t) * dlist = DLIST_(private)( join );
404 :
405 150025710 : ulong ele_idx = DLIST_(private_idx)( dlist->tail ); /* Not NULL as per contract */
406 150025710 : ulong prev_idx = DLIST_(private_idx)( pool[ ele_idx ].DLIST_PREV );
407 :
408 150025710 : *fd_ptr_if( !DLIST_(private_idx_is_null)( prev_idx ), &pool[ prev_idx ].DLIST_NEXT, &dlist->head ) =
409 150025710 : DLIST_(private_cidx)( DLIST_(private_idx_null)() );
410 :
411 150025710 : dlist->tail = DLIST_(private_cidx)( prev_idx );
412 150025710 : return ele_idx;
413 150025710 : }
414 :
415 : static inline DLIST_(t) *
416 : DLIST_(idx_insert_before)( DLIST_(t) * join,
417 : ulong ele_idx,
418 : ulong next_idx,
419 131251101 : DLIST_ELE_T * pool ) {
420 131251101 : ulong prev_idx = DLIST_(private_idx)( pool[ next_idx ].DLIST_PREV );
421 :
422 131251101 : pool[ ele_idx ].DLIST_PREV = DLIST_(private_cidx)( prev_idx );
423 131251101 : pool[ ele_idx ].DLIST_NEXT = DLIST_(private_cidx)( next_idx );
424 :
425 131251101 : pool[ next_idx ].DLIST_PREV = DLIST_(private_cidx)( ele_idx );
426 :
427 131251101 : *fd_ptr_if( !DLIST_(private_idx_is_null)( prev_idx ), &pool[ prev_idx ].DLIST_NEXT, &DLIST_(private)( join )->head ) =
428 131251101 : DLIST_(private_cidx)( ele_idx );
429 :
430 131251101 : return join;
431 131251101 : }
432 :
433 : static inline DLIST_(t) *
434 : DLIST_(idx_insert_after)( DLIST_(t) * join,
435 : ulong ele_idx,
436 : ulong prev_idx,
437 131270532 : DLIST_ELE_T * pool ) {
438 131270532 : ulong next_idx = DLIST_(private_idx)( pool[ prev_idx ].DLIST_NEXT );
439 :
440 131270532 : pool[ ele_idx ].DLIST_PREV = DLIST_(private_cidx)( prev_idx );
441 131270532 : pool[ ele_idx ].DLIST_NEXT = DLIST_(private_cidx)( next_idx );
442 :
443 131270532 : pool[ prev_idx ].DLIST_NEXT = DLIST_(private_cidx)( ele_idx );
444 :
445 131270532 : *fd_ptr_if( !DLIST_(private_idx_is_null)( next_idx ), &pool[ next_idx ].DLIST_PREV, &DLIST_(private)( join )->tail ) =
446 131270532 : DLIST_(private_cidx)( ele_idx );
447 :
448 131270532 : return join;
449 131270532 : }
450 :
451 : static inline DLIST_(t) *
452 : DLIST_(idx_remove)( DLIST_(t) * join,
453 : ulong ele_idx,
454 299987019 : DLIST_ELE_T * pool ) {
455 299987019 : DLIST_(private_t) * dlist = DLIST_(private)( join );
456 :
457 299987019 : ulong prev_idx = DLIST_(private_idx)( pool[ ele_idx ].DLIST_PREV );
458 299987019 : ulong next_idx = DLIST_(private_idx)( pool[ ele_idx ].DLIST_NEXT );
459 :
460 299987019 : *fd_ptr_if( !DLIST_(private_idx_is_null)( next_idx ), &pool[ next_idx ].DLIST_PREV, &dlist->tail ) =
461 299987019 : DLIST_(private_cidx)( prev_idx );
462 :
463 299987019 : *fd_ptr_if( !DLIST_(private_idx_is_null)( prev_idx ), &pool[ prev_idx ].DLIST_NEXT, &dlist->head ) =
464 299987019 : DLIST_(private_cidx)( next_idx );
465 :
466 299987019 : return join;
467 299987019 : }
468 :
469 : static inline DLIST_(t) *
470 : DLIST_(idx_replace)( DLIST_(t) * join,
471 : ulong ele_idx,
472 : ulong old_idx,
473 131260047 : DLIST_ELE_T * pool ) {
474 131260047 : DLIST_(private_t) * dlist = DLIST_(private)( join );
475 :
476 131260047 : ulong prev_idx = DLIST_(private_idx)( pool[ old_idx ].DLIST_PREV );
477 131260047 : ulong next_idx = DLIST_(private_idx)( pool[ old_idx ].DLIST_NEXT );
478 :
479 131260047 : pool[ ele_idx ].DLIST_PREV = DLIST_(private_cidx)( prev_idx );
480 131260047 : pool[ ele_idx ].DLIST_NEXT = DLIST_(private_cidx)( next_idx );
481 :
482 131260047 : *fd_ptr_if( !DLIST_(private_idx_is_null)( next_idx ), &pool[ next_idx ].DLIST_PREV, &dlist->tail ) =
483 131260047 : DLIST_(private_cidx)( ele_idx );
484 :
485 131260047 : *fd_ptr_if( !DLIST_(private_idx_is_null)( prev_idx ), &pool[ prev_idx ].DLIST_NEXT, &dlist->head ) =
486 131260047 : DLIST_(private_cidx)( ele_idx );
487 :
488 131260047 : return join;
489 131260047 : }
490 :
491 : static inline DLIST_(t) *
492 : DLIST_(remove_all)( DLIST_(t) * join,
493 27 : DLIST_ELE_T * pool ) {
494 27 : (void)pool;
495 27 : DLIST_(private_t) * dlist = DLIST_(private)( join );
496 27 : dlist->head = DLIST_(private_cidx)( DLIST_(private_idx_null)() );
497 27 : dlist->tail = DLIST_(private_cidx)( DLIST_(private_idx_null)() );
498 27 : return join;
499 27 : }
500 :
501 : FD_FN_PURE static inline DLIST_(iter_t)
502 : DLIST_(iter_fwd_init)( DLIST_(t) const * join,
503 449975742 : DLIST_ELE_T const * pool ) {
504 449975742 : (void)pool;
505 449975742 : return DLIST_(private_idx)( DLIST_(private_const)( join )->head );
506 449975742 : }
507 :
508 : FD_FN_PURE static inline DLIST_(iter_t)
509 : DLIST_(iter_rev_init)( DLIST_(t) const * join,
510 300040953 : DLIST_ELE_T const * pool ) {
511 300040953 : (void)pool;
512 300040953 : return DLIST_(private_idx)( DLIST_(private_const)( join )->tail );
513 300040953 : }
514 :
515 : FD_FN_CONST static inline int
516 : DLIST_(iter_done)( DLIST_(iter_t) iter,
517 : DLIST_(t) const * join,
518 2062618782 : DLIST_ELE_T const * pool ) {
519 2062618782 : (void)join; (void)pool;
520 2062618782 : return DLIST_(private_idx_is_null)( iter );
521 2062618782 : }
522 :
523 : FD_FN_PURE static inline DLIST_(iter_t)
524 : DLIST_(iter_fwd_next)( DLIST_(iter_t) iter,
525 : DLIST_(t) const * join,
526 787505682 : DLIST_ELE_T const * pool ) {
527 787505682 : (void)join;
528 787505682 : return DLIST_(private_idx)( pool[ iter ].DLIST_NEXT );
529 787505682 : }
530 :
531 : FD_FN_PURE static inline DLIST_(iter_t)
532 : DLIST_(iter_rev_next)( DLIST_(iter_t) iter,
533 : DLIST_(t) const * join,
534 525096405 : DLIST_ELE_T const * pool ) {
535 525096405 : (void)join;
536 525096405 : return DLIST_(private_idx)( pool[ iter ].DLIST_PREV );
537 525096405 : }
538 :
539 : FD_FN_CONST static inline ulong
540 : DLIST_(iter_idx)( DLIST_(iter_t) iter,
541 : DLIST_(t) const * join,
542 375025248 : DLIST_ELE_T const * pool ) {
543 375025248 : (void)join; (void)pool;
544 375025248 : return iter;
545 375025248 : }
546 :
547 : FD_FN_PURE static inline DLIST_ELE_T *
548 : DLIST_(ele_peek_head)( DLIST_(t) const * join,
549 899938296 : DLIST_ELE_T * pool ) {
550 899938296 : return pool + DLIST_(idx_peek_head)( join, pool );
551 899938296 : }
552 :
553 : FD_FN_PURE static inline DLIST_ELE_T const *
554 : DLIST_(ele_peek_head_const)( DLIST_(t) const * join,
555 899938290 : DLIST_ELE_T const * pool ) {
556 899938290 : return pool + DLIST_(idx_peek_head)( join, pool );
557 899938290 : }
558 :
559 : FD_FN_PURE static inline DLIST_ELE_T *
560 : DLIST_(ele_peek_tail)( DLIST_(t) const * join,
561 899938290 : DLIST_ELE_T * pool ) {
562 899938290 : return pool + DLIST_(idx_peek_tail)( join, pool );
563 899938290 : }
564 :
565 : FD_FN_PURE static inline DLIST_ELE_T const *
566 : DLIST_(ele_peek_tail_const)( DLIST_(t) const * join,
567 899938290 : DLIST_ELE_T const * pool ) {
568 899938290 : return pool + DLIST_(idx_peek_tail)( join, pool );
569 899938290 : }
570 :
571 : static inline DLIST_(t) *
572 : DLIST_(ele_push_head)( DLIST_(t) * join,
573 : DLIST_ELE_T * ele,
574 84373425 : DLIST_ELE_T * pool ) {
575 84373425 : return DLIST_(idx_push_head)( join, (ulong)(ele-pool), pool );
576 84373425 : }
577 :
578 : static inline DLIST_(t) *
579 : DLIST_(ele_push_tail)( DLIST_(t) * join,
580 : DLIST_ELE_T * ele,
581 84393804 : DLIST_ELE_T * pool ) {
582 84393804 : return DLIST_(idx_push_tail)( join, (ulong)(ele-pool), pool );
583 84393804 : }
584 :
585 : static inline DLIST_ELE_T *
586 : DLIST_(ele_pop_head)( DLIST_(t) * join,
587 75015066 : DLIST_ELE_T * pool ) {
588 75015066 : return pool + DLIST_(idx_pop_head)( join, pool );
589 75015066 : }
590 :
591 : static inline DLIST_ELE_T*
592 : DLIST_(ele_pop_tail)( DLIST_(t) * join,
593 75016527 : DLIST_ELE_T * pool ) {
594 75016527 : return pool + DLIST_(idx_pop_tail)( join, pool );
595 75016527 : }
596 :
597 : static inline DLIST_(t) *
598 : DLIST_(ele_insert_before)( DLIST_(t) * join,
599 : DLIST_ELE_T * ele,
600 : DLIST_ELE_T * next,
601 65610312 : DLIST_ELE_T * pool ) {
602 65610312 : return DLIST_(idx_insert_before)( join, (ulong)(ele-pool), (ulong)(next-pool), pool );
603 65610312 : }
604 :
605 : static inline DLIST_(t) *
606 : DLIST_(ele_insert_after)( DLIST_(t) * join,
607 : DLIST_ELE_T * ele,
608 : DLIST_ELE_T * prev,
609 65643615 : DLIST_ELE_T * pool ) {
610 65643615 : return DLIST_(idx_insert_after)( join, (ulong)(ele-pool), (ulong)(prev-pool), pool );
611 65643615 : }
612 :
613 : static inline DLIST_(t) *
614 : DLIST_(ele_replace)( DLIST_(t) * join,
615 : DLIST_ELE_T * ele,
616 : DLIST_ELE_T * old,
617 65623485 : DLIST_ELE_T * pool ) {
618 65623485 : return DLIST_(idx_replace)( join, (ulong)(ele-pool), (ulong)(old-pool), pool );
619 65623485 : }
620 :
621 : static inline DLIST_(t) *
622 : DLIST_(ele_remove)( DLIST_(t) * join,
623 : DLIST_ELE_T * ele,
624 149999544 : DLIST_ELE_T * pool ) {
625 149999544 : return DLIST_(idx_remove)( join, (ulong)(ele-pool), pool );
626 149999544 : }
627 :
628 : FD_FN_CONST static inline DLIST_ELE_T *
629 : DLIST_(iter_ele)( DLIST_(iter_t) iter,
630 : DLIST_(t) const * join,
631 150008859 : DLIST_ELE_T * pool ) {
632 150008859 : (void)join;
633 150008859 : return pool + iter;
634 150008859 : }
635 :
636 : FD_FN_CONST static inline DLIST_ELE_T const *
637 : DLIST_(iter_ele_const)( DLIST_(iter_t) iter,
638 : DLIST_(t) const * join,
639 224982660 : DLIST_ELE_T const * pool ) {
640 224982660 : (void)join;
641 224982660 : return pool + iter;
642 224982660 : }
643 :
644 : FD_PROTOTYPES_END
645 :
646 : #endif
647 :
648 : #if DLIST_IMPL_STYLE==1 /* need prototypes */
649 :
650 : FD_PROTOTYPES_BEGIN
651 :
652 : FD_FN_CONST ulong DLIST_(align) ( void );
653 : FD_FN_CONST ulong DLIST_(footprint)( void );
654 : void * DLIST_(new) ( void * shmem );
655 : DLIST_(t) * DLIST_(join) ( void * shdlist );
656 : void * DLIST_(leave) ( DLIST_(t) * join );
657 : void * DLIST_(delete) ( void * shdlist );
658 :
659 : int
660 : DLIST_(verify)( DLIST_(t) const * join,
661 : ulong ele_cnt,
662 : DLIST_ELE_T const * pool );
663 :
664 : FD_PROTOTYPES_END
665 :
666 : #else /* need implementations */
667 :
668 : #if DLIST_IMPL_STYLE==0 /* local only */
669 : #define DLIST_IMPL_STATIC FD_FN_UNUSED static
670 : #else
671 : #define DLIST_IMPL_STATIC
672 : #endif
673 :
674 : FD_PROTOTYPES_BEGIN
675 :
676 10107 : FD_FN_CONST DLIST_IMPL_STATIC ulong DLIST_(align) ( void ) { return alignof(DLIST_(t)); }
677 6 : FD_FN_CONST DLIST_IMPL_STATIC ulong DLIST_(footprint)( void ) { return sizeof( DLIST_(t)); }
678 :
679 : DLIST_IMPL_STATIC void *
680 3387 : DLIST_(new)( void * shmem ) {
681 :
682 3387 : if( FD_UNLIKELY( !shmem ) ) {
683 3 : FD_LOG_WARNING(( "NULL shmem" ));
684 3 : return NULL;
685 3 : }
686 :
687 3384 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, DLIST_(align)() ) ) ) {
688 3 : FD_LOG_WARNING(( "misaligned shmem" ));
689 3 : return NULL;
690 3 : }
691 :
692 : // Note: Guaranteed non-zero and not otherwise used
693 : //ulong footprint = DLIST_(footprint)();
694 : //if( FD_UNLIKELY( !footprint ) ) {
695 : // FD_LOG_WARNING(( "bad footprint" ));
696 : // return NULL;
697 : //}
698 :
699 3381 : DLIST_(private_t) * dlist = (DLIST_(private_t) *)shmem;
700 :
701 3381 : dlist->head = DLIST_(private_cidx)( DLIST_(private_idx_null)() );
702 3381 : dlist->tail = DLIST_(private_cidx)( DLIST_(private_idx_null)() );
703 :
704 3381 : FD_COMPILER_MFENCE();
705 3381 : FD_VOLATILE( dlist->magic ) = DLIST_MAGIC;
706 3381 : FD_COMPILER_MFENCE();
707 :
708 3381 : return shmem;
709 3384 : }
710 :
711 : DLIST_IMPL_STATIC DLIST_(t) *
712 3390 : DLIST_(join)( void * shdlist ) {
713 3390 : DLIST_(private_t) * dlist = (DLIST_(private_t) *)shdlist;
714 :
715 3390 : if( FD_UNLIKELY( !dlist ) ) {
716 3 : FD_LOG_WARNING(( "NULL shdlist" ));
717 3 : return NULL;
718 3 : }
719 :
720 3387 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)dlist, DLIST_(align)() ) ) ) {
721 3 : FD_LOG_WARNING(( "misaligned shdlist" ));
722 3 : return NULL;
723 3 : }
724 :
725 3384 : if( FD_UNLIKELY( dlist->magic!=DLIST_MAGIC ) ) {
726 3 : FD_LOG_WARNING(( "bad magic" ));
727 3 : return NULL;
728 3 : }
729 :
730 3381 : return (DLIST_(t) *)dlist;
731 3384 : }
732 :
733 : DLIST_IMPL_STATIC void *
734 3330 : DLIST_(leave)( DLIST_(t) * join ) {
735 :
736 3330 : if( FD_UNLIKELY( !join ) ) {
737 3 : FD_LOG_WARNING(( "NULL join" ));
738 3 : return NULL;
739 3 : }
740 :
741 3327 : return (void *)join;
742 3330 : }
743 :
744 : DLIST_IMPL_STATIC void *
745 3336 : DLIST_(delete)( void * shdlist ) {
746 3336 : DLIST_(private_t) * dlist = (DLIST_(private_t) *)shdlist;
747 :
748 3336 : if( FD_UNLIKELY( !dlist ) ) {
749 3 : FD_LOG_WARNING(( "NULL shdlist" ));
750 3 : return NULL;
751 3 : }
752 :
753 3333 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)dlist, DLIST_(align)() ) ) ) {
754 3 : FD_LOG_WARNING(( "misaligned shdlist" ));
755 3 : return NULL;
756 3 : }
757 :
758 3330 : if( FD_UNLIKELY( dlist->magic!=DLIST_MAGIC ) ) {
759 3 : FD_LOG_WARNING(( "bad magic" ));
760 3 : return NULL;
761 3 : }
762 :
763 3327 : FD_COMPILER_MFENCE();
764 3327 : FD_VOLATILE( dlist->magic ) = 0UL;
765 3327 : FD_COMPILER_MFENCE();
766 :
767 3327 : return shdlist;
768 3330 : }
769 :
770 : DLIST_IMPL_STATIC int
771 : DLIST_(verify)( DLIST_(t) const * join,
772 : ulong ele_cnt,
773 187477728 : DLIST_ELE_T const * pool ) {
774 :
775 2962643493 : # define DLIST_TEST(c) do { \
776 2962643493 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
777 2962643493 : } while(0)
778 :
779 : /* Validate input args */
780 :
781 187477728 : DLIST_TEST( join );
782 187477728 : DLIST_TEST( ele_cnt<=DLIST_(ele_max)() );
783 187477728 : DLIST_TEST( (!!pool) | (!ele_cnt) );
784 :
785 : /* Iterate forward through the dlist, validating as we go */
786 :
787 187477728 : DLIST_(private_t) const * dlist = DLIST_(private_const)( join );
788 :
789 187477728 : DLIST_TEST( dlist->magic==DLIST_MAGIC );
790 :
791 187477728 : ulong rem = ele_cnt;
792 187477728 : ulong prev_idx = DLIST_(private_idx_null)();
793 187477728 : ulong ele_idx = DLIST_(private_idx)( dlist->head );
794 862562679 : while( !DLIST_(private_idx_is_null)( ele_idx ) ) {
795 :
796 : /* Visit ele_idx */
797 :
798 675084951 : DLIST_TEST( rem ); rem--; /* Test for cycles */
799 675084951 : DLIST_TEST( ele_idx<ele_cnt ); /* Test valid ele_idx */
800 675084951 : DLIST_TEST( DLIST_(private_idx)( pool[ ele_idx ].DLIST_PREV )==prev_idx ); /* Test reverse link integrity */
801 :
802 : /* Advance to next element */
803 :
804 675084951 : prev_idx = ele_idx;
805 675084951 : ele_idx = DLIST_(private_idx)( pool[ ele_idx ].DLIST_NEXT );
806 675084951 : }
807 :
808 187477728 : DLIST_TEST( DLIST_(private_idx)( dlist->tail )==prev_idx );
809 :
810 187477728 : # undef DLIST_TEST
811 :
812 187477728 : return 0;
813 187477728 : }
814 :
815 : FD_PROTOTYPES_END
816 :
817 : #undef DLIST_IMPL_STATIC
818 :
819 : #endif
820 :
821 : #undef DLIST_
822 :
823 : #undef DLIST_IMPL_STYLE
824 : #undef DLIST_MAGIC
825 : #undef DLIST_NEXT
826 : #undef DLIST_PREV
827 : #undef DLIST_IDX_T
828 : #undef DLIST_ELE_T
829 : #undef DLIST_NAME
|
