Line data Source code
1 : /* Declares a family of functions implementing a single-threaded
2 : run-time fixed-capacity double-ended queue (deque) designed for high
3 : performance contexts. Example usage:
4 :
5 : #define DEQUE_NAME my_deque
6 : #define DEQUE_T my_ele_t
7 : #include "util/tmpl/fd_deque.c"
8 :
9 : This creates the following API for use in the local compilation unit:
10 :
11 : // Constructors
12 :
13 : // IMPORTANT SAFETY TIP! max==0 is fine for this API. Calling
14 : // most APIs on such a deque will be a violation of the API
15 : // pre-requisites (e.g. push_head and pop_tail are not valid
16 : // because a max==0 deque is simultaneously full and empty). The
17 : // accessors (max==0, cnt==0, avail==0, empty==true, full==true),
18 : // remove_all (no-op) and iterators (will indicate nothing to
19 : // iterator over) are still valid to use.
20 :
21 : ulong my_deque_align ( void ); // required byte alignment of a deque
22 : ulong my_deque_footprint( ulong max ); // required byte footprint of a deque with max capacity
23 : void * my_deque_new ( void * shmem, // format memory region into a my_deque, my_deque will be empty
24 : ulong max ); // (caller not joined on return, mem has required align/footprint, etc)
25 : my_ele_t * my_deque_join ( void * shdeque ); // join a my_deque (unlimited joins, etc) (NOT A CAST OF SHDEQUE)
26 : // join can be indexed like a normal array with max elements
27 : void * my_deque_leave ( my_ele_t * deque ); // leave a my_deque (matched with join, etc) (NOT A CAST OF DEQUE)
28 : void * my_deque_delete ( void * shdeque ); // unformat memory (no active joins, etc)
29 :
30 : // Accessors
31 :
32 : ulong my_deque_max ( my_ele_t const * deque ); // returns the max elements that could be in the deque
33 : ulong my_deque_cnt ( my_ele_t const * deque ); // returns the number of elements in the deque, in [0,max]
34 : ulong my_deque_avail( my_ele_t const * deque ); // returns max-cnt
35 : int my_deque_empty( my_ele_t const * deque ); // returns 1 if deque is empty and 0 otherwise
36 : int my_deque_full ( my_ele_t const * deque ); // returns 1 if deque is full and 0 otherwise
37 :
38 : // Simple API
39 :
40 : // IMPORTANT SAFETY TIP! The wrap APIs discard the value popped on
41 : // wrapping. Thus, these should not be used when a my_ele_t might
42 : // contain the only reference to a resource (memory, file
43 : // descriptors, etc) that might need to be released after popping
44 : // (e.g. use these only if my_ele_t is plain-old-data).
45 :
46 : // IMPORTANT SAFETY TIP! The pop_idx APIs have an O(cnt) worst
47 : // case.
48 :
49 : my_ele_t * my_deque_push_head ( my_ele_t * deque, my_ele_t ele ); // push ele at the deque head, returns deque
50 : my_ele_t * my_deque_push_tail ( my_ele_t * deque, my_ele_t ele ); // push ele at the deque tail, returns deque
51 : my_ele_t my_deque_pop_head ( my_ele_t * deque ); // pops ele from the head of the deque, returns ele
52 : my_ele_t my_deque_pop_tail ( my_ele_t * deque ); // pops ele from the tail of the deque, returns ele
53 : my_ele_t * my_deque_push_head_wrap( my_ele_t * deque, my_ele_t ele ); // push ele at the deque head (pops tail first if deque full), returns deque, assumes deque has a positive max
54 : my_ele_t * my_deque_push_tail_wrap( my_ele_t * deque, my_ele_t ele ); // push ele at the deque tail (pops head first if deque full), returns deque, assumes deque has a positive max
55 : my_ele_t my_deque_pop_idx_tail ( my_ele_t * deque, ulong idx ); // pops ele at idx, returns ele. idx in [0,cnt). shifts head <= tail
56 :
57 : // Advanced API for zero-copy usage
58 :
59 : my_ele_t * my_deque_peek_head ( my_ele_t * deque ); // peeks at head, returned ptr lifetime is until next op on deque
60 : my_ele_t * my_deque_peek_tail ( my_ele_t * deque ); // peeks at tail, returned ptr lifetime is until next op on deque
61 : my_ele_t * my_deque_peek_index ( my_ele_t * deque, ulong idx ); // peeks at index, returned ptr lifetime is until next op on deque
62 : my_ele_t * my_deque_insert_head( my_ele_t * deque ); // inserts uninitialized element at head, returns deque
63 : my_ele_t * my_deque_insert_tail( my_ele_t * deque ); // inserts uninitialized element at tail, returns deque
64 : my_ele_t * my_deque_remove_head( my_ele_t * deque ); // removes head, returns deque
65 : my_ele_t * my_deque_remove_tail( my_ele_t * deque ); // removes tail, returns deque
66 : my_ele_t * my_deque_remove_all ( my_ele_t * deque ); // removes all, returns deque, fast O(1)
67 :
68 : my_ele_t * my_deque_push_head_nocopy( my_ele_t * deque ); // push the head, returns the new uninitialized element
69 : my_ele_t * my_deque_push_tail_nocopy( my_ele_t * deque ); // push the tail, returns the new uninitialized element
70 : my_ele_t * my_deque_pop_head_nocopy ( my_ele_t * deque ); // pops the head, returns the deleted element
71 : my_ele_t * my_deque_pop_tail_nocopy ( my_ele_t * deque ); // pops the tail, returns the deleted element
72 :
73 : my_ele_t const * my_deque_peek_head_const( my_ele_t const * deque ); // const version of peek_head
74 : my_ele_t const * my_deque_peek_tail_const( my_ele_t const * deque ); // const version of peek_tail
75 : my_ele_t const * my_deque_peek_index_const( my_ele_t const * deque, ulong idx ); // const version of peek_index
76 :
77 : // my_deque_iter_* allow for iteration over all the elements in
78 : // a my_deque. The iteration will be in order from head to tail.
79 : // Example usage:
80 : //
81 : // for( my_deque_iter_t iter = my_deque_iter_init( deque ); !my_deque_iter_done( deque, iter ); iter = my_deque_iter_next( deque, iter ) ) {
82 : // my_deque_t * ele = my_deque_iter_ele( deque, iter );
83 : //
84 : // ... process ele here
85 : // }
86 :
87 : my_deque_iter_t my_deque_iter_init ( my_deque_t const * deque );
88 : int my_deque_iter_done ( my_deque_t const * deque, my_deque_iter_t iter ); // returns 1 if no more iterations, 0 o.w.
89 : my_deque_iter_t my_deque_iter_next ( my_deque_t const * deque, my_deque_iter_t iter ); // returns next iter value iter
90 : my_ele_t * my_deque_iter_ele ( my_deque_t * deque, my_deque_iter_t iter ); // assumes not done, return non-NULL ele
91 : my_ele_t const * my_deque_iter_ele_const( my_deque_t const * deque, my_deque_iter_t iter ); // assumes not done, return non-NULL ele
92 :
93 : // my_deque_iter_rev_* allow for iteration similar to the above, but
94 : // in reverse order from tail to head.
95 : // Example usage:
96 : //
97 : // for( my_deque_iter_t iter = my_deque_iter_init_rev( deque ); !my_deque_iter_done_rev( deque, iter ); iter = my_deque_iter_prev( deque, iter ) ) {
98 : // my_deque_t * ele = my_deque_iter_ele( deque, iter );
99 : //
100 : // ... process ele here
101 : // }
102 :
103 : my_deque_iter_t my_deque_iter_init_rev ( my_deque_t const * deque );
104 : int my_deque_iter_done_rev ( my_deque_t const * deque, my_deque_iter_t iter ); // returns 1 if no more iterations, 0 o.w.
105 : my_deque_iter_t my_deque_iter_prev ( my_deque_t const * deque, my_deque_iter_t iter ); // returns prev iter value iter
106 :
107 : For performance, none of the functions do any error checking.
108 : Specifically, the caller promises that max is such that footprint
109 : will not overflow 2^64 (e.g. max << (2^64)/sizeof(my_ele_t)), cnt<max
110 : for any push or insert operation and cnt>0 for any pop, peek or
111 : remove operation (remove_all is fine on an empty deque). */
112 :
113 : #include "../bits/fd_bits.h"
114 : #include <stddef.h>
115 :
116 : #ifndef DEQUE_NAME
117 : #error "Define DEQUE_NAME"
118 : #endif
119 :
120 : #ifndef DEQUE_T
121 : #error "Define DEQUE_T"
122 : #endif
123 :
124 : #if FD_TMPL_USE_HANDHOLDING
125 : #include "../log/fd_log.h"
126 : #endif
127 :
128 : /* Implementation *****************************************************/
129 :
130 5654395602 : #define DEQUE_(x) FD_EXPAND_THEN_CONCAT3(DEQUE_NAME,_,x)
131 :
132 : struct DEQUE_(private) {
133 : ulong max1; /* Max elements in deque minus 1 */
134 : ulong cnt; /* Num elements in deque, in [0,max] */
135 : ulong start; /* Location of current head, in [0,max) */
136 : ulong end; /* Location of current tail, in [0,max) */
137 : DEQUE_T deque[ 1 ]; /* Actually max in size */
138 : };
139 :
140 : typedef struct DEQUE_(private) DEQUE_(private_t);
141 :
142 : FD_PROTOTYPES_BEGIN
143 :
144 : /* private_from_deque returns a pointer to the deque_private given a
145 : pointer to the deque. */
146 :
147 : FD_FN_CONST static inline DEQUE_(private_t) *
148 610986366 : DEQUE_(private_hdr_from_deque)( DEQUE_T * deque ) {
149 610986366 : return (DEQUE_(private_t) *)( (ulong)deque - offsetof(DEQUE_(private_t), deque) );
150 610986366 : }
151 :
152 : /* const-correct version of above */
153 :
154 : FD_FN_CONST static inline DEQUE_(private_t) const *
155 2084171997 : DEQUE_(private_const_hdr_from_deque)( DEQUE_T const * deque ) {
156 2084171997 : return (DEQUE_(private_t) const *)( (ulong)deque - offsetof(DEQUE_(private_t), deque) );
157 2084171997 : }
158 :
159 : /* These move i to the previous or next slot to i for given max.
160 : Input should be in [0,max) and output will be in [0,max). */
161 :
162 279630990 : FD_FN_CONST static inline ulong DEQUE_(private_prev)( ulong i, ulong max1 ) { return fd_ulong_if( i==0UL, max1, i-1UL ); }
163 249130386 : FD_FN_CONST static inline ulong DEQUE_(private_next)( ulong i, ulong max1 ) { return fd_ulong_if( i>=max1, 0UL, i+1UL ); }
164 :
165 3276 : FD_FN_CONST static inline ulong DEQUE_(align)( void ) { return alignof(DEQUE_(private_t)); }
166 :
167 : FD_FN_CONST static inline ulong
168 1665 : DEQUE_(footprint)( ulong max ) {
169 1665 : return fd_ulong_align_up( fd_ulong_align_up( 32UL, alignof(DEQUE_T) ) + sizeof(DEQUE_T)*max, alignof(DEQUE_(private_t)) );
170 1665 : }
171 :
172 : static inline void *
173 : DEQUE_(new)( void * shmem,
174 660 : ulong max ) {
175 : # if FD_TMPL_USE_HANDHOLDING
176 : if( FD_UNLIKELY( !shmem ) ) FD_LOG_CRIT(( "NULL shmem" ));
177 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, DEQUE_(align)() ) ) ) FD_LOG_CRIT(( "unaligned shmem" ));
178 : # endif
179 660 : DEQUE_(private_t) * hdr = (DEQUE_(private_t) *)shmem;
180 660 : hdr->max1 = max-1UL; /* Note: will wrap to ULONG_MAX if max==0 (and ULONG_MAX+1 will wrap back to 0) */
181 660 : hdr->cnt = 0UL;
182 660 : hdr->start = 0UL;
183 660 : hdr->end = 0UL;
184 660 : return hdr;
185 660 : }
186 :
187 : static inline DEQUE_T *
188 1290 : DEQUE_(join)( void * shdeque ) {
189 1290 : DEQUE_(private_t) * hdr = (DEQUE_(private_t) *)shdeque;
190 1290 : return hdr->deque;
191 1290 : }
192 :
193 978 : static inline void * DEQUE_(leave) ( DEQUE_T * deque ) { return (void *)DEQUE_(private_hdr_from_deque)( deque ); }
194 :
195 : static inline void *
196 348 : DEQUE_(delete)( void * shdeque ) {
197 : # if FD_TMPL_USE_HANDHOLDING
198 : if( FD_UNLIKELY( !shdeque ) ) FD_LOG_CRIT(( "NULL shdeque" ));
199 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shdeque, DEQUE_(align)() ) ) ) FD_LOG_CRIT(( "unaligned shmem" ));
200 : # endif
201 348 : return shdeque;
202 348 : }
203 :
204 : FD_FN_PURE static inline ulong
205 300000006 : DEQUE_(max)( DEQUE_T const * deque ) {
206 300000006 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
207 300000006 : return hdr->max1 + 1UL;
208 300000006 : }
209 :
210 : FD_FN_PURE static inline ulong
211 300000333 : DEQUE_(cnt)( DEQUE_T const * deque ) {
212 300000333 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
213 300000333 : return hdr->cnt;
214 300000333 : }
215 :
216 : FD_FN_PURE static inline ulong
217 300000003 : DEQUE_(avail)( DEQUE_T const * deque ) {
218 300000003 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
219 300000003 : return hdr->max1 + 1UL - hdr->cnt;
220 300000003 : }
221 :
222 : FD_FN_PURE static inline int
223 300000003 : DEQUE_(empty)( DEQUE_T const * deque ) {
224 300000003 : return !DEQUE_(private_const_hdr_from_deque)( deque )->cnt;
225 300000003 : }
226 :
227 : FD_FN_PURE static inline int
228 300000003 : DEQUE_(full)( DEQUE_T const * deque ) {
229 300000003 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
230 300000003 : return (hdr->max1 + 1UL)==hdr->cnt;
231 300000003 : }
232 :
233 : static inline DEQUE_T *
234 : DEQUE_(push_head)( DEQUE_T * deque,
235 14490972 : DEQUE_T ele ) {
236 : # if FD_TMPL_USE_HANDHOLDING
237 : if( FD_UNLIKELY( DEQUE_(full)( deque ) ) ) FD_LOG_CRIT(( "cannot push to full deque" ));
238 : # endif
239 14490972 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
240 14490972 : ulong max1 = hdr->max1;
241 14490972 : ulong cnt = hdr->cnt;
242 14490972 : ulong start = hdr->start;
243 14490972 : start = DEQUE_(private_prev)( start, max1 );
244 14490972 : hdr->deque[ start ] = ele;
245 14490972 : hdr->cnt = cnt+1UL;
246 14490972 : hdr->start = start;
247 14490972 : return deque;
248 14490972 : }
249 :
250 : static inline DEQUE_T *
251 : DEQUE_(push_tail)( DEQUE_T * deque,
252 14507661 : DEQUE_T ele ) {
253 : # if FD_TMPL_USE_HANDHOLDING
254 : if( FD_UNLIKELY( DEQUE_(full)( deque ) ) ) FD_LOG_CRIT(( "cannot push to full deque" ));
255 : # endif
256 14507661 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
257 14507661 : ulong max1 = hdr->max1;
258 14507661 : ulong cnt = hdr->cnt;
259 14507661 : ulong end = hdr->end;
260 14507661 : hdr->deque[ end ] = ele;
261 14507661 : end = DEQUE_(private_next)( end, max1 );
262 14507661 : hdr->cnt = cnt+1UL;
263 14507661 : hdr->end = end;
264 14507661 : return deque;
265 14507661 : }
266 :
267 : static inline DEQUE_T
268 16554267 : DEQUE_(pop_head)( DEQUE_T * deque ) {
269 16554267 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
270 : # if FD_TMPL_USE_HANDHOLDING
271 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot pop from empty deque" ));
272 : # endif
273 16554267 : ulong max1 = hdr->max1;
274 16554267 : ulong cnt = hdr->cnt;
275 16554267 : ulong start = hdr->start;
276 16554267 : DEQUE_T ele = hdr->deque[ start ];
277 16554267 : start = DEQUE_(private_next)( start, max1 );
278 16554267 : hdr->cnt = cnt-1UL;
279 16554267 : hdr->start = start;
280 16554267 : return ele;
281 16554267 : }
282 :
283 : static inline DEQUE_T
284 16565439 : DEQUE_(pop_tail)( DEQUE_T * deque ) {
285 : # if FD_TMPL_USE_HANDHOLDING
286 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot pop from empty deque" ));
287 : # endif
288 16565439 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
289 16565439 : ulong max1 = hdr->max1;
290 16565439 : ulong cnt = hdr->cnt;
291 16565439 : ulong end = hdr->end;
292 16565439 : end = DEQUE_(private_prev)( end, max1 );
293 16565439 : DEQUE_T ele = hdr->deque[ end ];
294 16565439 : hdr->cnt = cnt-1UL;
295 16565439 : hdr->end = end;
296 16565439 : return ele;
297 16565439 : }
298 :
299 : static inline DEQUE_T *
300 : DEQUE_(push_head_wrap)( DEQUE_T * deque,
301 17635728 : DEQUE_T ele ) {
302 17635728 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
303 17635728 : ulong max1 = hdr->max1;
304 17635728 : ulong cnt = hdr->cnt;
305 17635728 : ulong start = hdr->start;
306 17635728 : ulong end = hdr->end;
307 :
308 : # if FD_TMPL_USE_HANDHOLDING
309 : if( FD_UNLIKELY( max1==ULONG_MAX ) ) FD_LOG_CRIT(( "cannot push_head_wrap when max is zero" ));
310 : # endif
311 :
312 : /* If the deque is full, pop and discard the tail. */
313 :
314 17635728 : int is_full = (cnt>max1);
315 17635728 : end = fd_ulong_if( !is_full, end, DEQUE_(private_prev)( end, max1 ) );
316 17635728 : cnt -= (ulong)is_full;
317 :
318 : /* Push the head */
319 :
320 17635728 : start = DEQUE_(private_prev)( start, max1 );
321 17635728 : hdr->deque[ start ] = ele;
322 :
323 17635728 : hdr->cnt = cnt + 1UL;
324 17635728 : hdr->start = start;
325 17635728 : hdr->end = end;
326 17635728 : return deque;
327 17635728 : }
328 :
329 : static inline DEQUE_T *
330 : DEQUE_(push_tail_wrap)( DEQUE_T * deque,
331 17650173 : DEQUE_T ele ) {
332 17650173 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
333 17650173 : ulong max1 = hdr->max1;
334 17650173 : ulong cnt = hdr->cnt;
335 17650173 : ulong start = hdr->start;
336 17650173 : ulong end = hdr->end;
337 :
338 : # if FD_TMPL_USE_HANDHOLDING
339 : if( FD_UNLIKELY( max1==ULONG_MAX ) ) FD_LOG_CRIT(( "cannot push_tail_wrap when max is zero" ));
340 : # endif
341 :
342 : /* If the deque is full, pop and discard the head. */
343 :
344 17650173 : int is_full = (cnt>max1);
345 17650173 : start = fd_ulong_if( !is_full, start, DEQUE_(private_next)( start, max1 ) );
346 17650173 : cnt -= (ulong)is_full;
347 :
348 : /* Push the head */
349 :
350 17650173 : hdr->deque[ end ] = ele;
351 17650173 : end = DEQUE_(private_next)( end, max1 );
352 :
353 17650173 : hdr->cnt = cnt + 1UL;
354 17650173 : hdr->start = start;
355 17650173 : hdr->end = end;
356 17650173 : return deque;
357 17650173 : }
358 :
359 : static inline DEQUE_T
360 16566648 : DEQUE_(pop_idx_tail)( DEQUE_T * deque, ulong idx ) {
361 : # if FD_TMPL_USE_HANDHOLDING
362 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot pop from empty deque" ));
363 : if( FD_UNLIKELY( idx>=DEQUE_(cnt)( deque ) ) ) FD_LOG_CRIT(( "index out of bounds" ));
364 : # endif
365 16566648 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
366 :
367 16566648 : ulong max1 = hdr->max1;
368 :
369 16566648 : ulong slot = hdr->start + idx;
370 16566648 : slot = fd_ulong_if( slot <= max1, slot, slot - max1 - 1UL );
371 16566648 : ulong cnt = --hdr->cnt;
372 16566648 : ulong rem = cnt - idx;
373 :
374 16566648 : hdr->end = DEQUE_(private_prev)( hdr->end, max1 );
375 :
376 16566648 : DEQUE_T * cur = &deque[ slot ];
377 16566648 : DEQUE_T ele = *cur;
378 51241827 : while( rem-- ) {
379 34675179 : slot = DEQUE_(private_next)( slot, max1 );
380 34675179 : DEQUE_T * next = &deque[ slot ];
381 34675179 : *cur = *next;
382 34675179 : cur = next;
383 34675179 : }
384 16566648 : return ele;
385 16566648 : }
386 :
387 : FD_FN_PURE static inline DEQUE_T *
388 14489388 : DEQUE_(peek_head)( DEQUE_T * deque ) {
389 : # if FD_TMPL_USE_HANDHOLDING
390 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot peek on empty deque" ));
391 : # endif
392 14489388 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
393 14489388 : return hdr->deque + hdr->start;
394 14489388 : }
395 :
396 : FD_FN_PURE static inline DEQUE_T *
397 14492730 : DEQUE_(peek_tail)( DEQUE_T * deque ) {
398 : # if FD_TMPL_USE_HANDHOLDING
399 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot peek on empty deque" ));
400 : # endif
401 14492730 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
402 14492730 : return hdr->deque + DEQUE_(private_prev)( hdr->end, hdr->max1 );
403 14492730 : }
404 :
405 : FD_FN_PURE static inline DEQUE_T *
406 171909807 : DEQUE_(peek_index)( DEQUE_T * deque, ulong idx ) {
407 : # if FD_TMPL_USE_HANDHOLDING
408 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot peek on empty deque" ));
409 : # endif
410 171909807 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
411 171909807 : ulong slot = hdr->start + idx;
412 171909807 : slot = fd_ulong_if( slot <= hdr->max1, slot, slot - hdr->max1 - 1UL );
413 171909807 : return hdr->deque + slot;
414 171909807 : }
415 :
416 : FD_FN_PURE static inline DEQUE_T const *
417 16557435 : DEQUE_(peek_head_const)( DEQUE_T const * deque ) {
418 : # if FD_TMPL_USE_HANDHOLDING
419 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot peek on empty deque" ));
420 : # endif
421 16557435 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
422 16557435 : return hdr->deque + hdr->start;
423 16557435 : }
424 :
425 : FD_FN_PURE static inline DEQUE_T const *
426 16567389 : DEQUE_(peek_tail_const)( DEQUE_T const * deque ) {
427 : # if FD_TMPL_USE_HANDHOLDING
428 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot peek on empty deque" ));
429 : # endif
430 16567389 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
431 16567389 : return hdr->deque + DEQUE_(private_prev)( hdr->end, hdr->max1 );
432 16567389 : }
433 :
434 : FD_FN_PURE static inline DEQUE_T const *
435 343819614 : DEQUE_(peek_index_const)( DEQUE_T const * deque, ulong idx ) {
436 : # if FD_TMPL_USE_HANDHOLDING
437 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot peek on empty deque" ));
438 : # endif
439 343819614 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
440 343819614 : ulong slot = hdr->start + idx;
441 343819614 : slot = fd_ulong_if( slot <= hdr->max1, slot, slot - hdr->max1 - 1UL );
442 343819614 : return hdr->deque + slot;
443 343819614 : }
444 :
445 : static inline DEQUE_T *
446 14489388 : DEQUE_(insert_head)( DEQUE_T * deque ) {
447 : # if FD_TMPL_USE_HANDHOLDING
448 : if( FD_UNLIKELY( DEQUE_(full)( deque ) ) ) FD_LOG_CRIT(( "cannot insert into full deque" ));
449 : # endif
450 14489388 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
451 14489388 : ulong max1 = hdr->max1;
452 14489388 : ulong cnt = hdr->cnt;
453 14489388 : ulong start = hdr->start;
454 14489388 : hdr->cnt = cnt + 1UL;
455 14489388 : hdr->start = DEQUE_(private_prev)( start, max1 );
456 14489388 : return deque;
457 14489388 : }
458 :
459 : static inline DEQUE_T *
460 14492730 : DEQUE_(insert_tail)( DEQUE_T * deque ) {
461 : # if FD_TMPL_USE_HANDHOLDING
462 : if( FD_UNLIKELY( DEQUE_(full)( deque ) ) ) FD_LOG_CRIT(( "cannot insert into full deque" ));
463 : # endif
464 14492730 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
465 14492730 : ulong max1 = hdr->max1;
466 14492730 : ulong cnt = hdr->cnt;
467 14492730 : ulong end = hdr->end;
468 14492730 : hdr->cnt = cnt + 1UL;
469 14492730 : hdr->end = DEQUE_(private_next)( end, max1 );
470 14492730 : return deque;
471 14492730 : }
472 :
473 : static inline DEQUE_T *
474 16557435 : DEQUE_(remove_head)( DEQUE_T * deque ) {
475 : # if FD_TMPL_USE_HANDHOLDING
476 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot remove from empty deque" ));
477 : # endif
478 16557435 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
479 16557435 : ulong max1 = hdr->max1;
480 16557435 : ulong cnt = hdr->cnt;
481 16557435 : ulong start = hdr->start;
482 16557435 : hdr->cnt = cnt - 1UL;
483 16557435 : hdr->start = DEQUE_(private_next)( start, max1 );
484 16557435 : return deque;
485 16557435 : }
486 :
487 : static inline DEQUE_T *
488 16567389 : DEQUE_(remove_tail)( DEQUE_T * deque ) {
489 : # if FD_TMPL_USE_HANDHOLDING
490 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot remove from empty deque" ));
491 : # endif
492 16567389 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
493 16567389 : ulong max1 = hdr->max1;
494 16567389 : ulong cnt = hdr->cnt;
495 16567389 : ulong end = hdr->end;
496 16567389 : hdr->cnt = cnt - 1UL;
497 16567389 : hdr->end = DEQUE_(private_prev)( end, max1 );
498 16567389 : return deque;
499 16567389 : }
500 :
501 : static inline DEQUE_T *
502 14484999 : DEQUE_(push_head_nocopy)( DEQUE_T * deque ) {
503 : # if FD_TMPL_USE_HANDHOLDING
504 : if( FD_UNLIKELY( DEQUE_(full)( deque ) ) ) FD_LOG_CRIT(( "cannot push to full deque" ));
505 : # endif
506 14484999 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
507 14484999 : ulong max1 = hdr->max1;
508 14484999 : ulong cnt = hdr->cnt;
509 14484999 : ulong start = hdr->start;
510 14484999 : hdr->cnt = cnt + 1UL;
511 14484999 : hdr->start = DEQUE_(private_prev)( start, max1 );
512 14484999 : return hdr->deque + hdr->start;
513 14484999 : }
514 :
515 : static inline DEQUE_T *
516 14500977 : DEQUE_(push_tail_nocopy)( DEQUE_T * deque ) {
517 : # if FD_TMPL_USE_HANDHOLDING
518 : if( FD_UNLIKELY( DEQUE_(full)( deque ) ) ) FD_LOG_CRIT(( "cannot push to full deque" ));
519 : # endif
520 14500977 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
521 14500977 : ulong max1 = hdr->max1;
522 14500977 : ulong cnt = hdr->cnt;
523 14500977 : ulong end = hdr->end;
524 14500977 : hdr->cnt = cnt + 1UL;
525 14500977 : DEQUE_T * res = hdr->deque + hdr->end;
526 14500977 : hdr->end = DEQUE_(private_next)( end, max1 );
527 14500977 : return res;
528 14500977 : }
529 :
530 : static inline DEQUE_T *
531 16557555 : DEQUE_(pop_head_nocopy)( DEQUE_T * deque ) {
532 : # if FD_TMPL_USE_HANDHOLDING
533 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot pop from empty deque" ));
534 : # endif
535 16557555 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
536 16557555 : ulong max1 = hdr->max1;
537 16557555 : ulong cnt = hdr->cnt;
538 16557555 : ulong start = hdr->start;
539 16557555 : hdr->cnt = cnt - 1UL;
540 16557555 : DEQUE_T * res = hdr->deque + hdr->start;
541 16557555 : hdr->start = DEQUE_(private_next)( start, max1 );
542 16557555 : return res;
543 16557555 : }
544 :
545 : static inline DEQUE_T *
546 16557516 : DEQUE_(pop_tail_nocopy)( DEQUE_T * deque ) {
547 : # if FD_TMPL_USE_HANDHOLDING
548 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot pop from empty deque" ));
549 : # endif
550 16557516 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
551 16557516 : ulong max1 = hdr->max1;
552 16557516 : ulong cnt = hdr->cnt;
553 16557516 : ulong end = hdr->end;
554 16557516 : hdr->cnt = cnt - 1UL;
555 16557516 : hdr->end = DEQUE_(private_prev)( end, max1 );
556 16557516 : return hdr->deque + hdr->end;
557 16557516 : }
558 :
559 : static inline DEQUE_T *
560 4488 : DEQUE_(remove_all)( DEQUE_T * deque ) {
561 4488 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
562 4488 : hdr->cnt = 0UL;
563 4488 : hdr->start = 0UL;
564 4488 : hdr->end = 0UL;
565 4488 : return deque;
566 4488 : }
567 :
568 : typedef struct { ulong rem; ulong idx; } DEQUE_(iter_t);
569 :
570 : static inline DEQUE_(iter_t)
571 17665620 : DEQUE_(iter_init)( DEQUE_T const * deque ) {
572 17665620 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
573 17665620 : DEQUE_(iter_t) iter;
574 17665620 : iter.rem = hdr->cnt;
575 17665620 : iter.idx = hdr->start;
576 17665620 : return iter;
577 17665620 : }
578 :
579 : static inline DEQUE_(iter_t)
580 17650911 : DEQUE_(iter_init_rev)( DEQUE_T const * deque ) {
581 17650911 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
582 17650911 : DEQUE_(iter_t) iter;
583 17650911 : iter.rem = hdr->cnt;
584 17650911 : iter.idx = hdr->end;
585 17650911 : iter.idx = DEQUE_(private_prev)( iter.idx, hdr->max1 );
586 17650911 : return iter;
587 17650911 : }
588 :
589 : static inline int
590 103649856 : DEQUE_(iter_done)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
591 103649856 : (void)deque;
592 103649856 : return !iter.rem;
593 103649856 : }
594 :
595 : static inline int
596 103577064 : DEQUE_(iter_done_rev)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
597 103577064 : (void)deque;
598 103577064 : return !iter.rem;
599 103577064 : }
600 :
601 : static inline DEQUE_(iter_t)
602 85984236 : DEQUE_(iter_next)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
603 85984236 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
604 85984236 : iter.rem--;
605 85984236 : iter.idx = DEQUE_(private_next)( iter.idx, hdr->max1 );
606 85984236 : return iter;
607 85984236 : }
608 :
609 : static inline DEQUE_(iter_t)
610 85926153 : DEQUE_(iter_prev)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
611 85926153 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
612 85926153 : iter.rem--;
613 85926153 : iter.idx = DEQUE_(private_prev)( iter.idx, hdr->max1 );
614 85926153 : return iter;
615 85926153 : }
616 :
617 : static inline DEQUE_T *
618 171910098 : DEQUE_(iter_ele)( DEQUE_T * deque, DEQUE_(iter_t) iter ) {
619 171910098 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
620 : # if FD_TMPL_USE_HANDHOLDING
621 : if( FD_UNLIKELY( (iter.rem==0) | (iter.rem>hdr->cnt) ) ) FD_LOG_CRIT(( "iter out of bounds" ));
622 : # endif
623 171910098 : return hdr->deque + iter.idx;
624 171910098 : }
625 :
626 : static inline DEQUE_T const *
627 291 : DEQUE_(iter_ele_const)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
628 291 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
629 : # if FD_TMPL_USE_HANDHOLDING
630 : if( FD_UNLIKELY( (iter.rem==0) | (iter.rem>hdr->cnt) ) ) FD_LOG_CRIT(( "iter out of bounds" ));
631 : # endif
632 291 : return hdr->deque + iter.idx;
633 291 : }
634 :
635 : FD_PROTOTYPES_END
636 :
637 : #undef DEQUE_
638 :
639 : #undef DEQUE_T
640 : #undef DEQUE_NAME
|
