Line data Source code
1 : /* Declares a family of functions implementing a single-threaded
2 : compile-time fixed-capacity double-ended queue (deque) designed for
3 : high performance contexts. The deque is implemented with a circular
4 : buffer and can push and pop from both ends. Setting DEQUE_MAX to a
5 : power of two is strongly recommended but not required. Example
6 : usage:
7 :
8 : #define DEQUE_NAME my_deque
9 : #define DEQUE_T my_ele_t
10 : #define DEQUE_MAX 64UL
11 : #include "util/tmpl/fd_deque.c"
12 :
13 : This creates the following API for use in the local compilation unit:
14 :
15 : // Constructors
16 :
17 : ulong my_deque_align ( void ); // required byte alignment of a deque
18 : ulong my_deque_footprint( void ); // required byte footprint of a deque with the given DEQUE_MAX
19 : void * my_deque_new ( void * shmem ); // format memory region into a my_deque, my_deque will be empty
20 : // (caller not joined on return, mem has required align/footprint, etc)
21 : my_ele_t * my_deque_join ( void * shdeque ); // join a my_deque (unlimited joins, etc) (NOT A CAST OF SHDEQUE)
22 : // join can be indexed like a normal array with DEQUE_MAX elements
23 : void * my_deque_leave ( my_ele_t * deque ); // leave a my_deque (matched with join, etc) (NOT A CAST OF DEQUE)
24 : void * my_deque_delete ( void * shdeque ); // unformat memory (no active joins, etc)
25 :
26 : // Accessors
27 :
28 : ulong my_deque_max ( my_ele_t const * deque ); // returns the max elements that could be in the deque (==DEQUE_MAX)
29 : ulong my_deque_cnt ( my_ele_t const * deque ); // returns the number of elements in the deque, in [0,DEQUE_MAX]
30 : ulong my_deque_avail( my_ele_t const * deque ); // returns max-cnt
31 : int my_deque_empty( my_ele_t const * deque ); // returns 1 if deque is empty and 0 otherwise
32 : int my_deque_full ( my_ele_t const * deque ); // returns 1 if deque is full and 0 otherwise
33 :
34 : // Simple API
35 :
36 : // IMPORTANT SAFETY TIP! The wrap APIs discard the value popped on
37 : // wrapping. Thus, these should not be used when a my_ele_t might
38 : // contain the only reference to a resource (memory, file
39 : // descriptors, etc) that might need to be released after popping
40 : // (e.g. use these only if my_ele_t is plain-old-data).
41 :
42 : // IMPORTANT SAFETY TIP! The pop_idx APIs have an O(cnt) worst
43 : // case.
44 :
45 : my_ele_t * my_deque_push_head ( my_ele_t * deque, my_ele_t ele ); // push ele at the deque head, returns deque
46 : my_ele_t * my_deque_push_tail ( my_ele_t * deque, my_ele_t ele ); // push ele at the deque tail, returns deque
47 : my_ele_t my_deque_pop_head ( my_ele_t * deque ); // pops ele from the head of the deque, returns ele
48 : my_ele_t my_deque_pop_tail ( my_ele_t * deque ); // pops ele from the tail of the deque, returns ele
49 : 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
50 : 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
51 : my_ele_t my_deque_pop_idx_tail ( my_ele_t * deque, ulong idx ); // pops ele at idx, returns ele. assumes idx in [0,cnt). shifts head <= tail
52 :
53 : // Advanced API for zero-copy usage
54 :
55 : my_ele_t * my_deque_peek_head ( my_ele_t * deque ); // peeks at head, returned ptr lifetime is until next op on deque
56 : // caller guarantees that deque is not empty
57 : my_ele_t * my_deque_peek_tail ( my_ele_t * deque ); // peeks at tail, returned ptr lifetime is until next op on deque
58 : // caller guarantees that deque is not empty
59 : 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
60 : // caller guarantees that deque is not empty
61 : // idx is wrapped to [0,cnt)
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 : #ifndef DEQUE_MAX
125 : #error "Define DEQUE_MAX or use fd_deque_dynamic"
126 : #endif
127 :
128 : /* Note: we don't support DEQUE_MAX==0 (like we do in fd_deque_dynamic)
129 : because of spotty C++ for zero length array members in the current
130 : implementation (though it would be possible to do so with a different
131 : implementation). */
132 :
133 : #if (DEQUE_MAX)<1UL
134 : #error "DEQUE_MAX must be positive"
135 : #endif
136 :
137 : #if FD_TMPL_USE_HANDHOLDING
138 : #include "../log/fd_log.h"
139 : #endif
140 :
141 : /* Implementation *****************************************************/
142 :
143 4985467269 : #define DEQUE_(x) FD_EXPAND_THEN_CONCAT3(DEQUE_NAME,_,x)
144 :
145 : struct DEQUE_(private) {
146 :
147 : /* The number of elements in the deque is cnt=end-start and cnt will be
148 : in [0,max]. If cnt==0, the deque is empty. If cnt==MAX, the deque
149 : if full.
150 :
151 : For a non-empty deque, the deque head is at element deque[ start % MAX ],
152 : and the deque tail is at element deque[ (end-1UL) % MAX ]
153 :
154 : start and end overflow/underflow are fine if max is a power of two
155 : and start and end are initialized such that overflow / underflow
156 : will not happen for millennia practically anyway. More precisely,
157 : this implementation is guaranteed when max is a power of two and/or
158 : when fewer than 2^63 operations have been done on the deque (which,
159 : practically speaking, would take millennia). If, in some distant
160 : age, a user does want to support doing more than 2^63 operations
161 : when max is not a power of two, this can be done by moving start
162 : and end as close as possible toward 2^63 by the same integer
163 : multiple of max toward 2^63 sporadically (every couple of hundred
164 : years or so). */
165 :
166 : ulong start;
167 : ulong end;
168 : DEQUE_T deque[ (ulong)(DEQUE_MAX) ];
169 : };
170 :
171 : typedef struct DEQUE_(private) DEQUE_(private_t);
172 :
173 : FD_PROTOTYPES_BEGIN
174 :
175 : /* private_from_deque return a pointer to the deque_private given a
176 : pointer to the deque. */
177 :
178 : FD_FN_CONST static inline DEQUE_(private_t) *
179 524997816 : DEQUE_(private_hdr_from_deque)( DEQUE_T * deque ) {
180 524997816 : return (DEQUE_(private_t) *)( (ulong)deque - offsetof(DEQUE_(private_t), deque) );
181 524997816 : }
182 :
183 : /* const-correct version of above */
184 :
185 : FD_FN_CONST static inline DEQUE_(private_t) const *
186 1647519942 : DEQUE_(private_const_hdr_from_deque)( DEQUE_T const * deque ) {
187 1647519942 : return (DEQUE_(private_t) const *)( (ulong)deque - offsetof(DEQUE_(private_t), deque) );
188 1647519942 : }
189 :
190 : /* private_slot maps an index to a slot cnt. The compiler should
191 : optimize this to a bit-and when MAX is a power of 2 and, hopefully,
192 : to optimize this to a magic multiply otherwise. */
193 :
194 702538692 : FD_FN_CONST static inline ulong DEQUE_(private_slot)( ulong i ) { return i % (ulong)(DEQUE_MAX); }
195 :
196 6 : FD_FN_CONST static inline ulong DEQUE_(align) ( void ) { return alignof(DEQUE_(private_t)); }
197 6 : FD_FN_CONST static inline ulong DEQUE_(footprint)( void ) { return sizeof (DEQUE_(private_t)); }
198 :
199 : static inline void *
200 3 : DEQUE_(new)( void * shmem ) {
201 : # if FD_TMPL_USE_HANDHOLDING
202 : if( FD_UNLIKELY( !shmem ) ) FD_LOG_CRIT(( "NULL shmem" ));
203 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, DEQUE_(align)() ) ) ) FD_LOG_CRIT(( "unaligned shmem" ));
204 : # endif
205 3 : DEQUE_(private_t) * hdr = (DEQUE_(private_t) *)shmem;
206 : /* These values are large enough that underflow/overflow will never
207 : happen in practical usage. For example, it would take hundreds of
208 : years if all a core did was a worst case continuous
209 : push_tail/pop_head pairs (or push_head/pop_tail) at 1 Gpair/sec.
210 : So we don't need to do any special handling overflow handling in
211 : practice that might otherwise be required if max is not a
212 : power-of-two MAX). Note also that overflow/underflow doesn't
213 : matter if max is a power of two as per the note above. */
214 3 : hdr->start = 1UL << 63;
215 3 : hdr->end = 1UL << 63;
216 3 : return hdr;
217 3 : }
218 :
219 : static inline DEQUE_T *
220 3 : DEQUE_(join)( void * shdeque ) {
221 3 : DEQUE_(private_t) * hdr = (DEQUE_(private_t) *)shdeque;
222 3 : return hdr->deque;
223 3 : }
224 :
225 3 : static inline void * DEQUE_(leave) ( DEQUE_T * deque ) { return (void *)DEQUE_(private_hdr_from_deque)( deque ); }
226 :
227 : static inline void *
228 3 : DEQUE_(delete)( void * shdeque ) {
229 : # if FD_TMPL_USE_HANDHOLDING
230 : if( FD_UNLIKELY( !shdeque ) ) FD_LOG_CRIT(( "NULL shdeque" ));
231 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shdeque, DEQUE_(align)() ) ) ) FD_LOG_CRIT(( "unaligned shdeque" ));
232 : # endif
233 3 : return shdeque;
234 3 : }
235 :
236 300000003 : FD_FN_CONST static inline ulong DEQUE_(max)( DEQUE_T const * deque ) { (void)deque; return (ulong)(DEQUE_MAX); }
237 :
238 : FD_FN_PURE static inline ulong
239 300000003 : DEQUE_(cnt)( DEQUE_T const * deque ) {
240 300000003 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
241 300000003 : return hdr->end - hdr->start;
242 300000003 : }
243 :
244 : FD_FN_PURE static inline ulong
245 300000000 : DEQUE_(avail)( DEQUE_T const * deque ) {
246 300000000 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
247 300000000 : return ((ulong)(DEQUE_MAX)) - (hdr->end - hdr->start);
248 300000000 : }
249 :
250 : FD_FN_PURE static inline int
251 300000000 : DEQUE_(empty)( DEQUE_T const * deque ) {
252 300000000 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
253 300000000 : return !(hdr->end - hdr->start);
254 300000000 : }
255 :
256 : FD_FN_PURE static inline int
257 300000000 : DEQUE_(full)( DEQUE_T const * deque ) {
258 300000000 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
259 300000000 : return (hdr->end - hdr->start)==((ulong)DEQUE_MAX);
260 300000000 : }
261 :
262 : static inline DEQUE_T *
263 : DEQUE_(push_head)( DEQUE_T * deque,
264 14490972 : DEQUE_T ele ) {
265 : # if FD_TMPL_USE_HANDHOLDING
266 : if( FD_UNLIKELY( DEQUE_(full)( deque ) ) ) FD_LOG_CRIT(( "cannot push to full deque" ));
267 : # endif
268 14490972 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
269 14490972 : hdr->start--;
270 14490972 : hdr->deque[ DEQUE_(private_slot)( hdr->start ) ] = ele;
271 14490972 : return deque;
272 14490972 : }
273 :
274 : static inline DEQUE_T *
275 : DEQUE_(push_tail)( DEQUE_T * deque,
276 14505516 : DEQUE_T ele ) {
277 : # if FD_TMPL_USE_HANDHOLDING
278 : if( FD_UNLIKELY( DEQUE_(full)( deque ) ) ) FD_LOG_CRIT(( "cannot push to full deque" ));
279 : # endif
280 14505516 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
281 14505516 : hdr->deque[ DEQUE_(private_slot)( hdr->end ) ] = ele;
282 14505516 : hdr->end++;
283 14505516 : return deque;
284 14505516 : }
285 :
286 : static inline DEQUE_T
287 16553364 : DEQUE_(pop_head)( DEQUE_T * deque ) {
288 : # if FD_TMPL_USE_HANDHOLDING
289 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot pop from empty deque" ));
290 : # endif
291 16553364 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
292 16553364 : DEQUE_T ele = hdr->deque[ DEQUE_(private_slot)( hdr->start ) ];
293 16553364 : hdr->start++;
294 16553364 : return ele;
295 16553364 : }
296 :
297 : static inline DEQUE_T
298 16565439 : DEQUE_(pop_tail)( DEQUE_T * deque ) {
299 : # if FD_TMPL_USE_HANDHOLDING
300 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot pop from empty deque" ));
301 : # endif
302 16565439 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
303 16565439 : hdr->end--;
304 16565439 : return hdr->deque[ DEQUE_(private_slot)( hdr->end ) ];
305 16565439 : }
306 :
307 : static inline DEQUE_T *
308 : DEQUE_(push_head_wrap)( DEQUE_T * deque,
309 17635728 : DEQUE_T ele ) {
310 17635728 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
311 17635728 : ulong start = hdr->start;
312 17635728 : ulong end = hdr->end;
313 :
314 : /* If the deque is full, pop and discard the tail. Note that
315 : DEQUE_MAX is positive. Thus, deque can never be full and empty at
316 : the same time making it always safe to pop the tail on full. */
317 :
318 17635728 : end -= (ulong)((end-start)==((ulong)DEQUE_MAX));
319 :
320 : /* Push the head */
321 :
322 17635728 : start--;
323 17635728 : hdr->deque[ DEQUE_(private_slot)(start) ] = ele;
324 :
325 17635728 : hdr->start = start;
326 17635728 : hdr->end = end;
327 17635728 : return deque;
328 17635728 : }
329 :
330 : static inline DEQUE_T *
331 : DEQUE_(push_tail_wrap)( DEQUE_T * deque,
332 17650173 : DEQUE_T ele ) {
333 17650173 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
334 17650173 : ulong start = hdr->start;
335 17650173 : ulong end = hdr->end;
336 :
337 : /* If the deque is full, pop and discard the head. Note that
338 : DEQUE_MAX is positive. Thus, deque can never be full and empty at
339 : the same time making it always safe to pop the head on full. */
340 :
341 17650173 : start += (ulong)((end-start)==((ulong)DEQUE_MAX));
342 :
343 : /* Push the tail */
344 :
345 17650173 : hdr->deque[ DEQUE_(private_slot)(end) ] = ele;
346 17650173 : end++;
347 :
348 17650173 : hdr->start = start;
349 17650173 : hdr->end = end;
350 17650173 : return deque;
351 17650173 : }
352 :
353 : static inline DEQUE_T
354 16566648 : DEQUE_(pop_idx_tail)( DEQUE_T * deque, ulong idx ) {
355 : # if FD_TMPL_USE_HANDHOLDING
356 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot pop from empty deque" ));
357 : if( FD_UNLIKELY( idx>=DEQUE_(cnt)( deque ) ) ) FD_LOG_CRIT(( "index out of bounds" ));
358 : # endif
359 16566648 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
360 16566648 : DEQUE_T * cur = &hdr->deque[ DEQUE_(private_slot)( hdr->start + idx ) ];
361 16566648 : DEQUE_T ele = *cur;
362 51241827 : for(;;) {
363 51241827 : idx++;
364 51241827 : if( hdr->start + idx >= hdr->end ) break;
365 34675179 : DEQUE_T * next = &hdr->deque[ DEQUE_(private_slot)( hdr->start + idx ) ];
366 34675179 : *cur = *next;
367 34675179 : cur = next;
368 34675179 : }
369 16566648 : hdr->end--;
370 16566648 : return ele;
371 16566648 : }
372 :
373 : FD_FN_PURE static inline DEQUE_T *
374 14489388 : DEQUE_(peek_head)( DEQUE_T * deque ) {
375 14489388 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
376 14489388 : if( hdr->end == hdr->start )
377 0 : return NULL;
378 14489388 : return hdr->deque + DEQUE_(private_slot)( hdr->start );
379 14489388 : }
380 :
381 : FD_FN_PURE static inline DEQUE_T *
382 14492730 : DEQUE_(peek_tail)( DEQUE_T * deque ) {
383 14492730 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
384 14492730 : if( hdr->end == hdr->start )
385 0 : return NULL;
386 14492730 : return hdr->deque + DEQUE_(private_slot)( hdr->end-1UL );
387 14492730 : }
388 :
389 : FD_FN_PURE static inline DEQUE_T *
390 85926153 : DEQUE_(peek_index)( DEQUE_T * deque, ulong idx ) {
391 : # if FD_TMPL_USE_HANDHOLDING
392 : if( FD_UNLIKELY( idx>=DEQUE_(cnt)( deque ) ) ) FD_LOG_CRIT(( "index out of bounds" ));
393 : # endif
394 85926153 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
395 85926153 : return hdr->deque + DEQUE_(private_slot)( hdr->start + idx );
396 85926153 : }
397 :
398 : FD_FN_PURE static inline DEQUE_T const *
399 16557435 : DEQUE_(peek_head_const)( DEQUE_T const * deque ) {
400 16557435 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
401 16557435 : if( hdr->end == hdr->start )
402 0 : return NULL;
403 16557435 : return hdr->deque + DEQUE_(private_slot)( hdr->start );
404 16557435 : }
405 :
406 : FD_FN_PURE static inline DEQUE_T const *
407 16567389 : DEQUE_(peek_tail_const)( DEQUE_T const * deque ) {
408 16567389 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
409 16567389 : if( hdr->end == hdr->start )
410 0 : return NULL;
411 16567389 : return hdr->deque + DEQUE_(private_slot)( hdr->end-1UL );
412 16567389 : }
413 :
414 : FD_FN_PURE static inline DEQUE_T const *
415 171852306 : DEQUE_(peek_index_const)( DEQUE_T const * deque, ulong idx ) {
416 : # if FD_TMPL_USE_HANDHOLDING
417 : if( FD_UNLIKELY( idx>=DEQUE_(cnt)( deque ) ) ) FD_LOG_CRIT(( "index out of bounds" ));
418 : # endif
419 171852306 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
420 171852306 : return hdr->deque + DEQUE_(private_slot)( hdr->start + idx );
421 171852306 : }
422 :
423 14489388 : static inline DEQUE_T * DEQUE_(insert_head)( DEQUE_T * deque ) { DEQUE_(private_hdr_from_deque)( deque )->start--; return deque; }
424 14492730 : static inline DEQUE_T * DEQUE_(insert_tail)( DEQUE_T * deque ) { DEQUE_(private_hdr_from_deque)( deque )->end++; return deque; }
425 16557435 : static inline DEQUE_T * DEQUE_(remove_head)( DEQUE_T * deque ) { DEQUE_(private_hdr_from_deque)( deque )->start++; return deque; }
426 16567389 : static inline DEQUE_T * DEQUE_(remove_tail)( DEQUE_T * deque ) { DEQUE_(private_hdr_from_deque)( deque )->end--; return deque; }
427 :
428 : static inline DEQUE_T *
429 14484999 : DEQUE_(push_head_nocopy)( DEQUE_T * deque ) {
430 : # if FD_TMPL_USE_HANDHOLDING
431 : if( FD_UNLIKELY( DEQUE_(full)( deque ) ) ) FD_LOG_CRIT(( "cannot push to full deque" ));
432 : # endif
433 14484999 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
434 14484999 : hdr->start--;
435 14484999 : return &hdr->deque[ DEQUE_(private_slot)( hdr->start ) ];
436 14484999 : }
437 :
438 : static inline DEQUE_T *
439 14500395 : DEQUE_(push_tail_nocopy)( DEQUE_T * deque ) {
440 : # if FD_TMPL_USE_HANDHOLDING
441 : if( FD_UNLIKELY( DEQUE_(full)( deque ) ) ) FD_LOG_CRIT(( "cannot push to full deque" ));
442 : # endif
443 14500395 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
444 14500395 : DEQUE_T * ele = &hdr->deque[ DEQUE_(private_slot)( hdr->end ) ];
445 14500395 : hdr->end++;
446 14500395 : return ele;
447 14500395 : }
448 :
449 : static inline DEQUE_T *
450 16557555 : DEQUE_(pop_head_nocopy)( DEQUE_T * deque ) {
451 : # if FD_TMPL_USE_HANDHOLDING
452 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot pop from empty deque" ));
453 : # endif
454 16557555 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
455 16557555 : DEQUE_T * ele = &hdr->deque[ DEQUE_(private_slot)( hdr->start ) ];
456 16557555 : hdr->start++;
457 16557555 : return ele;
458 16557555 : }
459 :
460 : static inline DEQUE_T *
461 16557516 : DEQUE_(pop_tail_nocopy)( DEQUE_T * deque ) {
462 : # if FD_TMPL_USE_HANDHOLDING
463 : if( FD_UNLIKELY( DEQUE_(empty)( deque ) ) ) FD_LOG_CRIT(( "cannot pop from empty deque" ));
464 : # endif
465 16557516 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
466 16557516 : hdr->end--;
467 16557516 : return &hdr->deque[ DEQUE_(private_slot)( hdr->end ) ];
468 16557516 : }
469 :
470 : static inline DEQUE_T *
471 4488 : DEQUE_(remove_all)( DEQUE_T * deque ) {
472 4488 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
473 : /* See note in new */
474 4488 : hdr->start = 1UL << 63;
475 4488 : hdr->end = 1UL << 63;
476 4488 : return deque;
477 4488 : }
478 :
479 : typedef ulong DEQUE_(iter_t);
480 :
481 : static inline DEQUE_(iter_t)
482 17665593 : DEQUE_(iter_init)( DEQUE_T const * deque ) {
483 17665593 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
484 17665593 : return hdr->start;
485 17665593 : }
486 :
487 : static inline DEQUE_(iter_t)
488 17650908 : DEQUE_(iter_init_rev)( DEQUE_T const * deque ) {
489 17650908 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
490 17650908 : return hdr->end - 1;
491 17650908 : }
492 :
493 : static inline int
494 103649247 : DEQUE_(iter_done)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
495 103649247 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
496 103649247 : return iter == hdr->end;
497 103649247 : }
498 :
499 : static inline int
500 103577061 : DEQUE_(iter_done_rev)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
501 103577061 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
502 103577061 : return iter == hdr->start - 1;
503 103577061 : }
504 :
505 : static inline DEQUE_(iter_t)
506 85983654 : DEQUE_(iter_next)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
507 85983654 : (void)deque;
508 85983654 : return iter+1;
509 85983654 : }
510 :
511 : static inline DEQUE_(iter_t)
512 85926153 : DEQUE_(iter_prev)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
513 85926153 : (void)deque;
514 85926153 : return iter-1;
515 85926153 : }
516 :
517 : static inline DEQUE_T *
518 171909807 : DEQUE_(iter_ele)( DEQUE_T * deque, DEQUE_(iter_t) iter ) {
519 171909807 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
520 : # if FD_TMPL_USE_HANDHOLDING
521 : if( FD_UNLIKELY( (iter<hdr->start) | (iter>hdr->end) ) ) FD_LOG_CRIT(( "iter out of bounds" ));
522 : # endif
523 171909807 : return &hdr->deque[ DEQUE_(private_slot)( iter ) ];
524 171909807 : }
525 :
526 : static inline DEQUE_T const *
527 0 : DEQUE_(iter_ele_const)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
528 0 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
529 : # if FD_TMPL_USE_HANDHOLDING
530 : if( FD_UNLIKELY( (iter<hdr->start) | (iter>hdr->end) ) ) FD_LOG_CRIT(( "iter out of bounds" ));
531 : # endif
532 0 : return &hdr->deque[ DEQUE_(private_slot)( iter ) ];
533 0 : }
534 :
535 : FD_PROTOTYPES_END
536 :
537 : #undef DEQUE_
538 :
539 : #undef DEQUE_MAX
540 : #undef DEQUE_T
541 : #undef DEQUE_NAME
|
