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 : compresson 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 a in
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 be 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 0 : #define DLIST_PREV prev
231 : #endif
232 :
233 : /* DLIST_NEXT is the DLIST_ELE_T next field */
234 :
235 : #ifndef DLIST_NEXT
236 0 : #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 3 : #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 : /* Implementation *****************************************************/
255 :
256 : /* Constructors and verification log details on failure (rest only needs
257 : fd_bits.h, consider making logging a compile time option). */
258 :
259 : #include "../log/fd_log.h"
260 :
261 34565385909 : #define DLIST_(n) FD_EXPAND_THEN_CONCAT3(DLIST_NAME,_,n)
262 :
263 : #if DLIST_IMPL_STYLE==0 || DLIST_IMPL_STYLE==1 /* need structures and inlines */
264 :
265 : struct DLIST_(private) {
266 :
267 : /* join points here */
268 :
269 : ulong magic; /* == DLIST_MAGIC */
270 : DLIST_IDX_T head; /* index of first list element (or idx_null if empty list) */
271 : DLIST_IDX_T tail; /* index of last list element (or idx_null if empty list) */
272 : };
273 :
274 : typedef struct DLIST_(private) DLIST_(private_t);
275 :
276 : typedef DLIST_(private_t) DLIST_(t);
277 :
278 : typedef ulong DLIST_(iter_t);
279 :
280 : FD_PROTOTYPES_BEGIN
281 :
282 : /* dlist_private returns the location of the dlist header for a current
283 : local join. Assumes join is a current local join.
284 : dlist_private_const is a const correct version. */
285 :
286 : FD_FN_CONST static inline DLIST_(private_t) *
287 1331323689 : DLIST_(private)( DLIST_(t) * join ) {
288 1331323689 : return (DLIST_(private_t) *)join;
289 1331323689 : }
290 :
291 : FD_FN_CONST static inline DLIST_(private_t) const *
292 7462087899 : DLIST_(private_const)( DLIST_(t) const * join ) {
293 7462087899 : return (DLIST_(private_t) const *)join;
294 7462087899 : }
295 :
296 : /* dlist_private_{cidx,idx} compress / decompress 64-bit in-register
297 : indices to/from their in-memory representations. */
298 :
299 3393939273 : FD_FN_CONST static inline DLIST_IDX_T DLIST_(private_cidx)( ulong idx ) { return (DLIST_IDX_T)idx; }
300 12374952969 : FD_FN_CONST static inline ulong DLIST_(private_idx) ( DLIST_IDX_T cidx ) { return (ulong) cidx; }
301 :
302 : /* dlist_private_idx_null returns the element storage index that
303 : represents NULL. */
304 :
305 0 : FD_FN_CONST static inline ulong DLIST_(private_idx_null)( void ) { return (ulong)(DLIST_IDX_T)~0UL; }
306 :
307 : /* dlist_private_idx_is_null returns 1 if idx is the NULL dlist index
308 : and 0 otherwise. */
309 :
310 5812703667 : FD_FN_CONST static inline int DLIST_(private_idx_is_null)( ulong idx ) { return idx==(ulong)(DLIST_IDX_T)~0UL; }
311 :
312 0 : FD_FN_CONST static ulong DLIST_(ele_max)( void ) { return (ulong)(DLIST_IDX_T)~0UL; }
313 :
314 : FD_FN_PURE static inline int
315 : DLIST_(is_empty)( DLIST_(t) const * join,
316 1124963763 : DLIST_ELE_T const * pool ) {
317 1124963763 : (void)pool;
318 1124963763 : return DLIST_(private_idx_is_null)( DLIST_(private_idx)( DLIST_(private_const)( join )->head ) );
319 1124963763 : }
320 :
321 : FD_FN_PURE static inline ulong
322 : DLIST_(idx_peek_head)( DLIST_(t) const * join,
323 2699814870 : DLIST_ELE_T const * pool ) {
324 2699814870 : (void)pool;
325 2699814870 : return DLIST_(private_idx)( DLIST_(private_const)( join )->head );
326 2699814870 : }
327 :
328 : FD_FN_PURE static inline ulong
329 : DLIST_(idx_peek_tail)( DLIST_(t) const * join,
330 2699814870 : DLIST_ELE_T const * pool ) {
331 2699814870 : (void)pool;
332 2699814870 : return DLIST_(private_idx)( DLIST_(private_const)( join )->tail );
333 2699814870 : }
334 :
335 : static inline DLIST_(t) *
336 : DLIST_(idx_push_head)( DLIST_(t) * join,
337 : ulong ele_idx,
338 168756039 : DLIST_ELE_T * pool ) {
339 168756039 : DLIST_(private_t) * dlist = DLIST_(private)( join );
340 :
341 168756039 : ulong head_idx = DLIST_(private_idx)( dlist->head );
342 :
343 168756039 : pool[ ele_idx ].DLIST_PREV = DLIST_(private_cidx)( DLIST_(private_idx_null)() );
344 168756039 : pool[ ele_idx ].DLIST_NEXT = DLIST_(private_cidx)( head_idx );
345 :
346 168756039 : *fd_ptr_if( !DLIST_(private_idx_is_null)( head_idx ), &pool[ head_idx ].DLIST_PREV, &dlist->tail ) =
347 168756039 : DLIST_(private_cidx)( ele_idx );
348 :
349 168756039 : dlist->head = DLIST_(private_cidx)( ele_idx );
350 168756039 : return join;
351 168756039 : }
352 :
353 : static inline DLIST_(t) *
354 : DLIST_(idx_push_tail)( DLIST_(t) * join,
355 : ulong ele_idx,
356 168754200 : DLIST_ELE_T * pool ) {
357 168754200 : DLIST_(private_t) * dlist = DLIST_(private)( join );
358 :
359 168754200 : ulong tail_idx = DLIST_(private_idx)( dlist->tail );
360 :
361 168754200 : pool[ ele_idx ].DLIST_PREV = DLIST_(private_cidx)( tail_idx );
362 168754200 : pool[ ele_idx ].DLIST_NEXT = DLIST_(private_cidx)( DLIST_(private_idx_null)() );
363 :
364 168754200 : *fd_ptr_if( !DLIST_(private_idx_is_null)( tail_idx ), &pool[ tail_idx ].DLIST_NEXT, &dlist->head ) =
365 168754200 : DLIST_(private_cidx)( ele_idx );
366 :
367 168754200 : dlist->tail = DLIST_(private_cidx)( ele_idx );
368 168754200 : return join;
369 168754200 : }
370 :
371 : static inline ulong
372 : DLIST_(idx_pop_head)( DLIST_(t) * join,
373 150031173 : DLIST_ELE_T * pool ) {
374 150031173 : DLIST_(private_t) * dlist = DLIST_(private)( join );
375 :
376 150031173 : ulong ele_idx = DLIST_(private_idx)( dlist->head ); /* Not NULL as per contract */
377 150031173 : ulong next_idx = DLIST_(private_idx)( pool[ ele_idx ].DLIST_NEXT );
378 :
379 150031173 : *fd_ptr_if( !DLIST_(private_idx_is_null)( next_idx ), &pool[ next_idx ].DLIST_PREV, &dlist->tail ) =
380 150031173 : DLIST_(private_cidx)( DLIST_(private_idx_null)() );
381 :
382 150031173 : dlist->head = DLIST_(private_cidx)( next_idx );
383 150031173 : return ele_idx;
384 150031173 : }
385 :
386 : static inline ulong
387 : DLIST_(idx_pop_tail)( DLIST_(t) * join,
388 150025710 : DLIST_ELE_T * pool ) {
389 150025710 : DLIST_(private_t) * dlist = DLIST_(private)( join );
390 :
391 150025710 : ulong ele_idx = DLIST_(private_idx)( dlist->tail ); /* Not NULL as per contract */
392 150025710 : ulong prev_idx = DLIST_(private_idx)( pool[ ele_idx ].DLIST_PREV );
393 :
394 150025710 : *fd_ptr_if( !DLIST_(private_idx_is_null)( prev_idx ), &pool[ prev_idx ].DLIST_NEXT, &dlist->head ) =
395 150025710 : DLIST_(private_cidx)( DLIST_(private_idx_null)() );
396 :
397 150025710 : dlist->tail = DLIST_(private_cidx)( prev_idx );
398 150025710 : return ele_idx;
399 150025710 : }
400 :
401 : static inline DLIST_(t) *
402 : DLIST_(idx_insert_before)( DLIST_(t) * join,
403 : ulong ele_idx,
404 : ulong next_idx,
405 131251101 : DLIST_ELE_T * pool ) {
406 131251101 : ulong prev_idx = DLIST_(private_idx)( pool[ next_idx ].DLIST_PREV );
407 :
408 131251101 : pool[ ele_idx ].DLIST_PREV = DLIST_(private_cidx)( prev_idx );
409 131251101 : pool[ ele_idx ].DLIST_NEXT = DLIST_(private_cidx)( next_idx );
410 :
411 131251101 : pool[ next_idx ].DLIST_PREV = DLIST_(private_cidx)( ele_idx );
412 :
413 131251101 : *fd_ptr_if( !DLIST_(private_idx_is_null)( prev_idx ), &pool[ prev_idx ].DLIST_NEXT, &DLIST_(private)( join )->head ) =
414 131251101 : DLIST_(private_cidx)( ele_idx );
415 :
416 131251101 : return join;
417 131251101 : }
418 :
419 : static inline DLIST_(t) *
420 : DLIST_(idx_insert_after)( DLIST_(t) * join,
421 : ulong ele_idx,
422 : ulong prev_idx,
423 131270532 : DLIST_ELE_T * pool ) {
424 131270532 : ulong next_idx = DLIST_(private_idx)( pool[ prev_idx ].DLIST_NEXT );
425 :
426 131270532 : pool[ ele_idx ].DLIST_PREV = DLIST_(private_cidx)( prev_idx );
427 131270532 : pool[ ele_idx ].DLIST_NEXT = DLIST_(private_cidx)( next_idx );
428 :
429 131270532 : pool[ prev_idx ].DLIST_NEXT = DLIST_(private_cidx)( ele_idx );
430 :
431 131270532 : *fd_ptr_if( !DLIST_(private_idx_is_null)( next_idx ), &pool[ next_idx ].DLIST_PREV, &DLIST_(private)( join )->tail ) =
432 131270532 : DLIST_(private_cidx)( ele_idx );
433 :
434 131270532 : return join;
435 131270532 : }
436 :
437 : static inline DLIST_(t) *
438 : DLIST_(idx_remove)( DLIST_(t) * join,
439 : ulong ele_idx,
440 299974860 : DLIST_ELE_T * pool ) {
441 299974860 : DLIST_(private_t) * dlist = DLIST_(private)( join );
442 :
443 299974860 : ulong prev_idx = DLIST_(private_idx)( pool[ ele_idx ].DLIST_PREV );
444 299974860 : ulong next_idx = DLIST_(private_idx)( pool[ ele_idx ].DLIST_NEXT );
445 :
446 299974860 : *fd_ptr_if( !DLIST_(private_idx_is_null)( next_idx ), &pool[ next_idx ].DLIST_PREV, &dlist->tail ) =
447 299974860 : DLIST_(private_cidx)( prev_idx );
448 :
449 299974860 : *fd_ptr_if( !DLIST_(private_idx_is_null)( prev_idx ), &pool[ prev_idx ].DLIST_NEXT, &dlist->head ) =
450 299974860 : DLIST_(private_cidx)( next_idx );
451 :
452 299974860 : return join;
453 299974860 : }
454 :
455 : static inline DLIST_(t) *
456 : DLIST_(idx_replace)( DLIST_(t) * join,
457 : ulong ele_idx,
458 : ulong old_idx,
459 131260047 : DLIST_ELE_T * pool ) {
460 131260047 : DLIST_(private_t) * dlist = DLIST_(private)( join );
461 :
462 131260047 : ulong prev_idx = DLIST_(private_idx)( pool[ old_idx ].DLIST_PREV );
463 131260047 : ulong next_idx = DLIST_(private_idx)( pool[ old_idx ].DLIST_NEXT );
464 :
465 131260047 : pool[ ele_idx ].DLIST_PREV = DLIST_(private_cidx)( prev_idx );
466 131260047 : pool[ ele_idx ].DLIST_NEXT = DLIST_(private_cidx)( next_idx );
467 :
468 131260047 : *fd_ptr_if( !DLIST_(private_idx_is_null)( next_idx ), &pool[ next_idx ].DLIST_PREV, &dlist->tail ) =
469 131260047 : DLIST_(private_cidx)( ele_idx );
470 :
471 131260047 : *fd_ptr_if( !DLIST_(private_idx_is_null)( prev_idx ), &pool[ prev_idx ].DLIST_NEXT, &dlist->head ) =
472 131260047 : DLIST_(private_cidx)( ele_idx );
473 :
474 131260047 : return join;
475 131260047 : }
476 :
477 : static inline DLIST_(t) *
478 : DLIST_(remove_all)( DLIST_(t) * join,
479 27 : DLIST_ELE_T * pool ) {
480 27 : (void)pool;
481 27 : DLIST_(private_t) * dlist = DLIST_(private)( join );
482 27 : dlist->head = DLIST_(private_cidx)( DLIST_(private_idx_null)() );
483 27 : dlist->tail = DLIST_(private_cidx)( DLIST_(private_idx_null)() );
484 27 : return join;
485 27 : }
486 :
487 : FD_FN_PURE static inline DLIST_(iter_t)
488 : DLIST_(iter_fwd_init)( DLIST_(t) const * join,
489 449975715 : DLIST_ELE_T const * pool ) {
490 449975715 : (void)pool;
491 449975715 : return DLIST_(private_idx)( DLIST_(private_const)( join )->head );
492 449975715 : }
493 :
494 : FD_FN_PURE static inline DLIST_(iter_t)
495 : DLIST_(iter_rev_init)( DLIST_(t) const * join,
496 300040953 : DLIST_ELE_T const * pool ) {
497 300040953 : (void)pool;
498 300040953 : return DLIST_(private_idx)( DLIST_(private_const)( join )->tail );
499 300040953 : }
500 :
501 : FD_FN_CONST static inline int
502 : DLIST_(iter_done)( DLIST_(iter_t) iter,
503 : DLIST_(t) const * join,
504 2062618656 : DLIST_ELE_T const * pool ) {
505 2062618656 : (void)join; (void)pool;
506 2062618656 : return DLIST_(private_idx_is_null)( iter );
507 2062618656 : }
508 :
509 : FD_FN_PURE static inline DLIST_(iter_t)
510 : DLIST_(iter_fwd_next)( DLIST_(iter_t) iter,
511 : DLIST_(t) const * join,
512 787505583 : DLIST_ELE_T const * pool ) {
513 787505583 : (void)join;
514 787505583 : return DLIST_(private_idx)( pool[ iter ].DLIST_NEXT );
515 787505583 : }
516 :
517 : FD_FN_PURE static inline DLIST_(iter_t)
518 : DLIST_(iter_rev_next)( DLIST_(iter_t) iter,
519 : DLIST_(t) const * join,
520 525096405 : DLIST_ELE_T const * pool ) {
521 525096405 : (void)join;
522 525096405 : return DLIST_(private_idx)( pool[ iter ].DLIST_PREV );
523 525096405 : }
524 :
525 : FD_FN_CONST static inline ulong
526 : DLIST_(iter_idx)( DLIST_(iter_t) iter,
527 : DLIST_(t) const * join,
528 375025248 : DLIST_ELE_T const * pool ) {
529 375025248 : (void)join; (void)pool;
530 375025248 : return iter;
531 375025248 : }
532 :
533 : FD_FN_PURE static inline DLIST_ELE_T *
534 : DLIST_(ele_peek_head)( DLIST_(t) const * join,
535 899938290 : DLIST_ELE_T * pool ) {
536 899938290 : return pool + DLIST_(idx_peek_head)( join, pool );
537 899938290 : }
538 :
539 : FD_FN_PURE static inline DLIST_ELE_T const *
540 : DLIST_(ele_peek_head_const)( DLIST_(t) const * join,
541 899938290 : DLIST_ELE_T const * pool ) {
542 899938290 : return pool + DLIST_(idx_peek_head)( join, pool );
543 899938290 : }
544 :
545 : FD_FN_PURE static inline DLIST_ELE_T *
546 : DLIST_(ele_peek_tail)( DLIST_(t) const * join,
547 899938290 : DLIST_ELE_T * pool ) {
548 899938290 : return pool + DLIST_(idx_peek_tail)( join, pool );
549 899938290 : }
550 :
551 : FD_FN_PURE static inline DLIST_ELE_T const *
552 : DLIST_(ele_peek_tail_const)( DLIST_(t) const * join,
553 899938290 : DLIST_ELE_T const * pool ) {
554 899938290 : return pool + DLIST_(idx_peek_tail)( join, pool );
555 899938290 : }
556 :
557 : static inline DLIST_(t) *
558 : DLIST_(ele_push_head)( DLIST_(t) * join,
559 : DLIST_ELE_T * ele,
560 84373425 : DLIST_ELE_T * pool ) {
561 84373425 : return DLIST_(idx_push_head)( join, (ulong)(ele-pool), pool );
562 84373425 : }
563 :
564 : static inline DLIST_(t) *
565 : DLIST_(ele_push_tail)( DLIST_(t) * join,
566 : DLIST_ELE_T * ele,
567 84381648 : DLIST_ELE_T * pool ) {
568 84381648 : return DLIST_(idx_push_tail)( join, (ulong)(ele-pool), pool );
569 84381648 : }
570 :
571 : static inline DLIST_ELE_T *
572 : DLIST_(ele_pop_head)( DLIST_(t) * join,
573 75015066 : DLIST_ELE_T * pool ) {
574 75015066 : return pool + DLIST_(idx_pop_head)( join, pool );
575 75015066 : }
576 :
577 : static inline DLIST_ELE_T*
578 : DLIST_(ele_pop_tail)( DLIST_(t) * join,
579 75016527 : DLIST_ELE_T * pool ) {
580 75016527 : return pool + DLIST_(idx_pop_tail)( join, pool );
581 75016527 : }
582 :
583 : static inline DLIST_(t) *
584 : DLIST_(ele_insert_before)( DLIST_(t) * join,
585 : DLIST_ELE_T * ele,
586 : DLIST_ELE_T * next,
587 65610312 : DLIST_ELE_T * pool ) {
588 65610312 : return DLIST_(idx_insert_before)( join, (ulong)(ele-pool), (ulong)(next-pool), pool );
589 65610312 : }
590 :
591 : static inline DLIST_(t) *
592 : DLIST_(ele_insert_after)( DLIST_(t) * join,
593 : DLIST_ELE_T * ele,
594 : DLIST_ELE_T * prev,
595 65643615 : DLIST_ELE_T * pool ) {
596 65643615 : return DLIST_(idx_insert_after)( join, (ulong)(ele-pool), (ulong)(prev-pool), pool );
597 65643615 : }
598 :
599 : static inline DLIST_(t) *
600 : DLIST_(ele_replace)( DLIST_(t) * join,
601 : DLIST_ELE_T * ele,
602 : DLIST_ELE_T * old,
603 65623485 : DLIST_ELE_T * pool ) {
604 65623485 : return DLIST_(idx_replace)( join, (ulong)(ele-pool), (ulong)(old-pool), pool );
605 65623485 : }
606 :
607 : static inline DLIST_(t) *
608 : DLIST_(ele_remove)( DLIST_(t) * join,
609 : DLIST_ELE_T * ele,
610 149987385 : DLIST_ELE_T * pool ) {
611 149987385 : return DLIST_(idx_remove)( join, (ulong)(ele-pool), pool );
612 149987385 : }
613 :
614 : FD_FN_CONST static inline DLIST_ELE_T *
615 : DLIST_(iter_ele)( DLIST_(iter_t) iter,
616 : DLIST_(t) const * join,
617 150008760 : DLIST_ELE_T * pool ) {
618 150008760 : (void)join; (void)pool;
619 150008760 : return pool + iter;
620 150008760 : }
621 :
622 : FD_FN_CONST static inline DLIST_ELE_T const *
623 : DLIST_(iter_ele_const)( DLIST_(iter_t) iter,
624 : DLIST_(t) const * join,
625 224982660 : DLIST_ELE_T const * pool ) {
626 224982660 : (void)join; (void)pool;
627 224982660 : return pool + iter;
628 224982660 : }
629 :
630 : FD_PROTOTYPES_END
631 :
632 : #endif
633 :
634 : #if DLIST_IMPL_STYLE==1 /* need prototypes */
635 :
636 : FD_PROTOTYPES_BEGIN
637 :
638 : FD_FN_CONST ulong DLIST_(align) ( void );
639 : FD_FN_CONST ulong DLIST_(footprint)( void );
640 : void * DLIST_(new) ( void * shmem );
641 : DLIST_(t) * DLIST_(join) ( void * shdlist );
642 : void * DLIST_(leave) ( DLIST_(t) * join );
643 : void * DLIST_(delete) ( void * shdlist );
644 :
645 : FD_FN_PURE int
646 : DLIST_(verify)( DLIST_(t) const * join,
647 : ulong ele_cnt,
648 : DLIST_ELE_T const * pool );
649 :
650 : FD_PROTOTYPES_END
651 :
652 : #else /* need implementations */
653 :
654 : #if DLIST_IMPL_STYLE==0 /* local only */
655 : #define DLIST_IMPL_STATIC FD_FN_UNUSED static
656 : #else
657 : #define DLIST_IMPL_STATIC
658 : #endif
659 :
660 : FD_PROTOTYPES_BEGIN
661 :
662 0 : FD_FN_CONST DLIST_IMPL_STATIC ulong DLIST_(align) ( void ) { return alignof(DLIST_(t)); }
663 0 : FD_FN_CONST DLIST_IMPL_STATIC ulong DLIST_(footprint)( void ) { return sizeof( DLIST_(t)); }
664 :
665 : DLIST_IMPL_STATIC void *
666 9 : DLIST_(new)( void * shmem ) {
667 :
668 9 : if( FD_UNLIKELY( !shmem ) ) {
669 3 : FD_LOG_WARNING(( "NULL shmem" ));
670 3 : return NULL;
671 3 : }
672 :
673 6 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, DLIST_(align)() ) ) ) {
674 3 : FD_LOG_WARNING(( "misaligned shmem" ));
675 3 : return NULL;
676 3 : }
677 :
678 : // Note: Guaranteed non-zero and not otherwise used
679 : //ulong footprint = DLIST_(footprint)();
680 : //if( FD_UNLIKELY( !footprint ) ) {
681 : // FD_LOG_WARNING(( "bad footprint" ));
682 : // return NULL;
683 : //}
684 :
685 3 : DLIST_(private_t) * dlist = (DLIST_(private_t) *)shmem;
686 :
687 3 : dlist->head = DLIST_(private_cidx)( DLIST_(private_idx_null)() );
688 3 : dlist->tail = DLIST_(private_cidx)( DLIST_(private_idx_null)() );
689 :
690 3 : FD_COMPILER_MFENCE();
691 3 : FD_VOLATILE( dlist->magic ) = DLIST_MAGIC;
692 3 : FD_COMPILER_MFENCE();
693 :
694 3 : return shmem;
695 6 : }
696 :
697 : DLIST_IMPL_STATIC DLIST_(t) *
698 12 : DLIST_(join)( void * shdlist ) {
699 12 : DLIST_(private_t) * dlist = (DLIST_(private_t) *)shdlist;
700 :
701 12 : if( FD_UNLIKELY( !dlist ) ) {
702 3 : FD_LOG_WARNING(( "NULL shdlist" ));
703 3 : return NULL;
704 3 : }
705 :
706 9 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)dlist, DLIST_(align)() ) ) ) {
707 3 : FD_LOG_WARNING(( "misaligned shdlist" ));
708 3 : return NULL;
709 3 : }
710 :
711 6 : if( FD_UNLIKELY( dlist->magic!=DLIST_MAGIC ) ) {
712 3 : FD_LOG_WARNING(( "bad magic" ));
713 3 : return NULL;
714 3 : }
715 :
716 3 : return (DLIST_(t) *)dlist;
717 6 : }
718 :
719 : DLIST_IMPL_STATIC void *
720 6 : DLIST_(leave)( DLIST_(t) * join ) {
721 :
722 6 : if( FD_UNLIKELY( !join ) ) {
723 3 : FD_LOG_WARNING(( "NULL join" ));
724 3 : return NULL;
725 3 : }
726 :
727 3 : return (void *)join;
728 6 : }
729 :
730 : DLIST_IMPL_STATIC void *
731 12 : DLIST_(delete)( void * shdlist ) {
732 12 : DLIST_(private_t) * dlist = (DLIST_(private_t) *)shdlist;
733 :
734 12 : if( FD_UNLIKELY( !dlist ) ) {
735 3 : FD_LOG_WARNING(( "NULL shdlist" ));
736 3 : return NULL;
737 3 : }
738 :
739 9 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)dlist, DLIST_(align)() ) ) ) {
740 3 : FD_LOG_WARNING(( "misaligned shdlist" ));
741 3 : return NULL;
742 3 : }
743 :
744 6 : if( FD_UNLIKELY( dlist->magic!=DLIST_MAGIC ) ) {
745 3 : FD_LOG_WARNING(( "bad magic" ));
746 3 : return NULL;
747 3 : }
748 :
749 3 : FD_COMPILER_MFENCE();
750 3 : FD_VOLATILE( dlist->magic ) = 0UL;
751 3 : FD_COMPILER_MFENCE();
752 :
753 3 : return shdlist;
754 6 : }
755 :
756 : FD_FN_PURE DLIST_IMPL_STATIC int
757 : DLIST_(verify)( DLIST_(t) const * join,
758 : ulong ele_cnt,
759 187477728 : DLIST_ELE_T const * pool ) {
760 :
761 2962643493 : # define DLIST_TEST(c) do { \
762 2962643493 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
763 2962643493 : } while(0)
764 :
765 : /* Validate input args */
766 :
767 187477728 : DLIST_TEST( join );
768 187477728 : DLIST_TEST( ele_cnt<=DLIST_(ele_max)() );
769 187477728 : DLIST_TEST( (!!pool) | (!ele_cnt) );
770 :
771 : /* Iterate forward through the dlist, validating as we go */
772 :
773 187477728 : DLIST_(private_t) const * dlist = DLIST_(private_const)( join );
774 :
775 187477728 : DLIST_TEST( dlist->magic==DLIST_MAGIC );
776 :
777 187477728 : ulong rem = ele_cnt;
778 187477728 : ulong prev_idx = DLIST_(private_idx_null)();
779 187477728 : ulong ele_idx = DLIST_(private_idx)( dlist->head );
780 862562679 : while( !DLIST_(private_idx_is_null)( ele_idx ) ) {
781 :
782 : /* Visit ele_idx */
783 :
784 675084951 : DLIST_TEST( rem ); rem--; /* Test for cycles */
785 675084951 : DLIST_TEST( ele_idx<ele_cnt ); /* Test valid ele_idx */
786 675084951 : DLIST_TEST( DLIST_(private_idx)( pool[ ele_idx ].DLIST_PREV )==prev_idx ); /* Test reverse link integrity */
787 :
788 : /* Advance to next element */
789 :
790 675084951 : prev_idx = ele_idx;
791 675084951 : ele_idx = DLIST_(private_idx)( pool[ ele_idx ].DLIST_NEXT );
792 675084951 : }
793 :
794 187477728 : DLIST_TEST( DLIST_(private_idx)( dlist->tail )==prev_idx );
795 :
796 187477728 : # undef DLIST_TEST
797 :
798 187477728 : return 0;
799 187477728 : }
800 :
801 : FD_PROTOTYPES_END
802 :
803 : #undef DLIST_IMPL_STATIC
804 :
805 : #endif
806 :
807 : #undef DLIST_
808 :
809 : #undef DLIST_IMPL_STYLE
810 : #undef DLIST_MAGIC
811 : #undef DLIST_NEXT
812 : #undef DLIST_PREV
813 : #undef DLIST_IDX_T
814 : #undef DLIST_ELE_T
815 : #undef DLIST_NAME
|
