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 : /* Implementation *****************************************************/
125 :
126 6073509720 : #define DEQUE_(x) FD_EXPAND_THEN_CONCAT3(DEQUE_NAME,_,x)
127 :
128 : struct DEQUE_(private) {
129 : ulong max1; /* Max elements in deque minus 1 */
130 : ulong cnt; /* Num elements in deque, in [0,max] */
131 : ulong start; /* Location of current head, in [0,max) */
132 : ulong end; /* Location of current tail, in [0,max) */
133 : DEQUE_T deque[ 1 ]; /* Actually max in size */
134 : };
135 :
136 : typedef struct DEQUE_(private) DEQUE_(private_t);
137 :
138 : FD_PROTOTYPES_BEGIN
139 :
140 : /* private_from_deque returns a pointer to the deque_private given a
141 : pointer to the deque. */
142 :
143 : FD_FN_CONST static inline DEQUE_(private_t) *
144 81102267 : DEQUE_(private_hdr_from_deque)( DEQUE_T * deque ) {
145 81102267 : return (DEQUE_(private_t) *)( (ulong)deque - offsetof(DEQUE_(private_t), deque) );
146 81102267 : }
147 :
148 : /* const-correct version of above */
149 :
150 : FD_FN_CONST static inline DEQUE_(private_t) const *
151 223277481 : DEQUE_(private_const_hdr_from_deque)( DEQUE_T const * deque ) {
152 223277481 : return (DEQUE_(private_t) const *)( (ulong)deque - offsetof(DEQUE_(private_t), deque) );
153 223277481 : }
154 :
155 : /* These move i to the previous or next slot to i for given max.
156 : Input should be in [0,max) and output will be in [0,max). */
157 :
158 280715592 : FD_FN_CONST static inline ulong DEQUE_(private_prev)( ulong i, ulong max1 ) { return fd_ulong_if( i==0UL, max1, i-1UL ); }
159 400260870 : FD_FN_CONST static inline ulong DEQUE_(private_next)( ulong i, ulong max1 ) { return fd_ulong_if( i>=max1, 0UL, i+1UL ); }
160 :
161 0 : FD_FN_CONST static inline ulong DEQUE_(align)( void ) { return alignof(DEQUE_(private_t)); }
162 :
163 : FD_FN_CONST static inline ulong
164 173535 : DEQUE_(footprint)( ulong max ) {
165 173535 : return fd_ulong_align_up( fd_ulong_align_up( 32UL, alignof(DEQUE_T) ) + sizeof(DEQUE_T)*max, alignof(DEQUE_(private_t)) );
166 173535 : }
167 :
168 : static inline void *
169 : DEQUE_(new)( void * shmem,
170 173385 : ulong max ) {
171 173385 : DEQUE_(private_t) * hdr = (DEQUE_(private_t) *)shmem;
172 173385 : hdr->max1 = max-1UL; /* Note: will wrap to ULONG_MAX if max==0 (and ULONG_MAX+1 will wrap back to 0) */
173 173385 : hdr->cnt = 0UL;
174 173385 : hdr->start = 0UL;
175 173385 : hdr->end = 0UL;
176 173385 : return hdr;
177 173385 : }
178 :
179 : static inline DEQUE_T *
180 173457 : DEQUE_(join)( void * shdeque ) {
181 173457 : DEQUE_(private_t) * hdr = (DEQUE_(private_t) *)shdeque;
182 173457 : return hdr->deque;
183 173457 : }
184 :
185 153009 : static inline void * DEQUE_(leave) ( DEQUE_T * deque ) { return (void *)DEQUE_(private_hdr_from_deque)( deque ); }
186 152937 : static inline void * DEQUE_(delete)( void * shdeque ) { return shdeque; }
187 :
188 : FD_FN_PURE static inline ulong
189 300000006 : DEQUE_(max)( DEQUE_T const * deque ) {
190 300000006 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
191 300000006 : return hdr->max1 + 1UL;
192 300000006 : }
193 :
194 : FD_FN_PURE static inline ulong
195 301891266 : DEQUE_(cnt)( DEQUE_T const * deque ) {
196 301891266 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
197 301891266 : return hdr->cnt;
198 301891266 : }
199 :
200 : FD_FN_PURE static inline ulong
201 300000003 : DEQUE_(avail)( DEQUE_T const * deque ) {
202 300000003 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
203 300000003 : return hdr->max1 + 1UL - hdr->cnt;
204 300000003 : }
205 :
206 : FD_FN_PURE static inline int
207 300065121 : DEQUE_(empty)( DEQUE_T const * deque ) {
208 300065121 : return !DEQUE_(private_const_hdr_from_deque)( deque )->cnt;
209 300065121 : }
210 :
211 : FD_FN_PURE static inline int
212 300830598 : DEQUE_(full)( DEQUE_T const * deque ) {
213 300830598 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
214 300830598 : return (hdr->max1 + 1UL)==hdr->cnt;
215 300830598 : }
216 :
217 : static inline DEQUE_T *
218 : DEQUE_(push_head)( DEQUE_T * deque,
219 14490972 : DEQUE_T ele ) {
220 14490972 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
221 14490972 : ulong max1 = hdr->max1;
222 14490972 : ulong cnt = hdr->cnt;
223 14490972 : ulong start = hdr->start;
224 14490972 : start = DEQUE_(private_prev)( start, max1 );
225 14490972 : hdr->deque[ start ] = ele;
226 14490972 : hdr->cnt = cnt+1UL;
227 14490972 : hdr->start = start;
228 14490972 : return deque;
229 14490972 : }
230 :
231 : static inline DEQUE_T *
232 : DEQUE_(push_tail)( DEQUE_T * deque,
233 14517801 : DEQUE_T ele ) {
234 14517801 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
235 14517801 : ulong max1 = hdr->max1;
236 14517801 : ulong cnt = hdr->cnt;
237 14517801 : ulong end = hdr->end;
238 14517801 : hdr->deque[ end ] = ele;
239 14517801 : end = DEQUE_(private_next)( end, max1 );
240 14517801 : hdr->cnt = cnt+1UL;
241 14517801 : hdr->end = end;
242 14517801 : return deque;
243 14517801 : }
244 :
245 : static inline DEQUE_T
246 16553712 : DEQUE_(pop_head)( DEQUE_T * deque ) {
247 16553712 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
248 16553712 : ulong max1 = hdr->max1;
249 16553712 : ulong cnt = hdr->cnt;
250 16553712 : ulong start = hdr->start;
251 16553712 : DEQUE_T ele = hdr->deque[ start ];
252 16553712 : start = DEQUE_(private_next)( start, max1 );
253 16553712 : hdr->cnt = cnt-1UL;
254 16553712 : hdr->start = start;
255 16553712 : return ele;
256 16553712 : }
257 :
258 : static inline DEQUE_T
259 16565442 : DEQUE_(pop_tail)( DEQUE_T * deque ) {
260 16565442 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
261 16565442 : ulong max1 = hdr->max1;
262 16565442 : ulong cnt = hdr->cnt;
263 16565442 : ulong end = hdr->end;
264 16565442 : end = DEQUE_(private_prev)( end, max1 );
265 16565442 : DEQUE_T ele = hdr->deque[ end ];
266 16565442 : hdr->cnt = cnt-1UL;
267 16565442 : hdr->end = end;
268 16565442 : return ele;
269 16565442 : }
270 :
271 : static inline DEQUE_T *
272 : DEQUE_(push_head_wrap)( DEQUE_T * deque,
273 17635728 : DEQUE_T ele ) {
274 17635728 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
275 17635728 : ulong max1 = hdr->max1;
276 17635728 : ulong cnt = hdr->cnt;
277 17635728 : ulong start = hdr->start;
278 17635728 : ulong end = hdr->end;
279 :
280 : # if 0 /* handholding check */
281 : if( FD_UNLIKELY( max1==ULONG_MAX ) ) FD_LOG_CRIT(( "cannot push_head_wrap when max is zero" ));
282 : # endif
283 :
284 : /* If the deque is full, pop and discard the tail. */
285 :
286 17635728 : int is_full = (cnt>max1);
287 17635728 : end = fd_ulong_if( !is_full, end, DEQUE_(private_prev)( end, max1 ) );
288 17635728 : cnt -= (ulong)is_full;
289 :
290 : /* Push the head */
291 :
292 17635728 : start = DEQUE_(private_prev)( start, max1 );
293 17635728 : hdr->deque[ start ] = ele;
294 :
295 17635728 : hdr->cnt = cnt + 1UL;
296 17635728 : hdr->start = start;
297 17635728 : hdr->end = end;
298 17635728 : return deque;
299 17635728 : }
300 :
301 : static inline DEQUE_T *
302 : DEQUE_(push_tail_wrap)( DEQUE_T * deque,
303 17650173 : DEQUE_T ele ) {
304 17650173 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
305 17650173 : ulong max1 = hdr->max1;
306 17650173 : ulong cnt = hdr->cnt;
307 17650173 : ulong start = hdr->start;
308 17650173 : ulong end = hdr->end;
309 :
310 : # if 0 /* handholding check */
311 : if( FD_UNLIKELY( max1==ULONG_MAX ) ) FD_LOG_CRIT(( "cannot push_tail_wrap when max is zero" ));
312 : # endif
313 :
314 : /* If the deque is full, pop and discard the head. */
315 :
316 17650173 : int is_full = (cnt>max1);
317 17650173 : start = fd_ulong_if( !is_full, start, DEQUE_(private_next)( start, max1 ) );
318 17650173 : cnt -= (ulong)is_full;
319 :
320 : /* Push the head */
321 :
322 17650173 : hdr->deque[ end ] = ele;
323 17650173 : end = DEQUE_(private_next)( end, max1 );
324 :
325 17650173 : hdr->cnt = cnt + 1UL;
326 17650173 : hdr->start = start;
327 17650173 : hdr->end = end;
328 17650173 : return deque;
329 17650173 : }
330 :
331 : static inline DEQUE_T
332 16566861 : DEQUE_(pop_idx_tail)( DEQUE_T * deque, ulong idx ) {
333 16566861 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
334 :
335 16566861 : ulong max1 = hdr->max1;
336 :
337 16566861 : ulong slot = hdr->start + idx;
338 16566861 : slot = fd_ulong_if( slot <= max1, slot, slot - max1 - 1UL );
339 16566861 : ulong cnt = --hdr->cnt;
340 16566861 : ulong rem = cnt - idx;
341 :
342 16566861 : hdr->end = DEQUE_(private_prev)( hdr->end, max1 );
343 :
344 16566861 : DEQUE_T * cur = &deque[ slot ];
345 16566861 : DEQUE_T ele = *cur;
346 51242253 : while( rem-- ) {
347 34675392 : slot = DEQUE_(private_next)( slot, max1 );
348 34675392 : DEQUE_T * next = &deque[ slot ];
349 34675392 : *cur = *next;
350 34675392 : cur = next;
351 34675392 : }
352 16566861 : return ele;
353 16566861 : }
354 :
355 : FD_FN_PURE static inline DEQUE_T *
356 14489394 : DEQUE_(peek_head)( DEQUE_T * deque ) {
357 14489394 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
358 14489394 : return hdr->deque + hdr->start;
359 14489394 : }
360 :
361 : FD_FN_PURE static inline DEQUE_T *
362 14532366 : DEQUE_(peek_tail)( DEQUE_T * deque ) {
363 14532366 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
364 14532366 : return hdr->deque + DEQUE_(private_prev)( hdr->end, hdr->max1 );
365 14532366 : }
366 :
367 : FD_FN_PURE static inline DEQUE_T *
368 171963318 : DEQUE_(peek_index)( DEQUE_T * deque, ulong idx ) {
369 171963318 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
370 171963318 : ulong slot = hdr->start + idx;
371 171963318 : slot = fd_ulong_if( slot <= hdr->max1, slot, slot - hdr->max1 - 1UL );
372 171963318 : return hdr->deque + slot;
373 171963318 : }
374 :
375 : FD_FN_PURE static inline DEQUE_T const *
376 16560180 : DEQUE_(peek_head_const)( DEQUE_T const * deque ) {
377 16560180 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
378 16560180 : return hdr->deque + hdr->start;
379 16560180 : }
380 :
381 : FD_FN_PURE static inline DEQUE_T const *
382 16573749 : DEQUE_(peek_tail_const)( DEQUE_T const * deque ) {
383 16573749 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
384 16573749 : return hdr->deque + DEQUE_(private_prev)( hdr->end, hdr->max1 );
385 16573749 : }
386 :
387 : FD_FN_PURE static inline DEQUE_T const *
388 172061193 : DEQUE_(peek_index_const)( DEQUE_T const * deque, ulong idx ) {
389 172061193 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
390 172061193 : ulong slot = hdr->start + idx;
391 172061193 : slot = fd_ulong_if( slot <= hdr->max1, slot, slot - hdr->max1 - 1UL );
392 172061193 : return hdr->deque + slot;
393 172061193 : }
394 :
395 : static inline DEQUE_T *
396 14489388 : DEQUE_(insert_head)( DEQUE_T * deque ) {
397 14489388 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
398 14489388 : ulong max1 = hdr->max1;
399 14489388 : ulong cnt = hdr->cnt;
400 14489388 : ulong start = hdr->start;
401 14489388 : hdr->cnt = cnt + 1UL;
402 14489388 : hdr->start = DEQUE_(private_prev)( start, max1 );
403 14489388 : return deque;
404 14489388 : }
405 :
406 : static inline DEQUE_T *
407 14492730 : DEQUE_(insert_tail)( DEQUE_T * deque ) {
408 14492730 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
409 14492730 : ulong max1 = hdr->max1;
410 14492730 : ulong cnt = hdr->cnt;
411 14492730 : ulong end = hdr->end;
412 14492730 : hdr->cnt = cnt + 1UL;
413 14492730 : hdr->end = DEQUE_(private_next)( end, max1 );
414 14492730 : return deque;
415 14492730 : }
416 :
417 : static inline DEQUE_T *
418 16557435 : DEQUE_(remove_head)( DEQUE_T * deque ) {
419 16557435 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
420 16557435 : ulong max1 = hdr->max1;
421 16557435 : ulong cnt = hdr->cnt;
422 16557435 : ulong start = hdr->start;
423 16557435 : hdr->cnt = cnt - 1UL;
424 16557435 : hdr->start = DEQUE_(private_next)( start, max1 );
425 16557435 : return deque;
426 16557435 : }
427 :
428 : static inline DEQUE_T *
429 16567389 : DEQUE_(remove_tail)( DEQUE_T * deque ) {
430 16567389 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
431 16567389 : ulong max1 = hdr->max1;
432 16567389 : ulong cnt = hdr->cnt;
433 16567389 : ulong end = hdr->end;
434 16567389 : hdr->cnt = cnt - 1UL;
435 16567389 : hdr->end = DEQUE_(private_prev)( end, max1 );
436 16567389 : return deque;
437 16567389 : }
438 :
439 : static inline DEQUE_T *
440 15315594 : DEQUE_(push_head_nocopy)( DEQUE_T * deque ) {
441 15315594 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
442 15315594 : ulong max1 = hdr->max1;
443 15315594 : ulong cnt = hdr->cnt;
444 15315594 : ulong start = hdr->start;
445 15315594 : hdr->cnt = cnt + 1UL;
446 15315594 : hdr->start = DEQUE_(private_prev)( start, max1 );
447 15315594 : return hdr->deque + hdr->start;
448 15315594 : }
449 :
450 : static inline DEQUE_T *
451 18454452 : DEQUE_(push_tail_nocopy)( DEQUE_T * deque ) {
452 18454452 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
453 18454452 : ulong max1 = hdr->max1;
454 18454452 : ulong cnt = hdr->cnt;
455 18454452 : ulong end = hdr->end;
456 18454452 : hdr->cnt = cnt + 1UL;
457 18454452 : DEQUE_T * res = hdr->deque + hdr->end;
458 18454452 : hdr->end = DEQUE_(private_next)( end, max1 );
459 18454452 : return res;
460 18454452 : }
461 :
462 : static inline DEQUE_T *
463 16557555 : DEQUE_(pop_head_nocopy)( DEQUE_T * deque ) {
464 16557555 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
465 16557555 : ulong max1 = hdr->max1;
466 16557555 : ulong cnt = hdr->cnt;
467 16557555 : ulong start = hdr->start;
468 16557555 : hdr->cnt = cnt - 1UL;
469 16557555 : DEQUE_T * res = hdr->deque + hdr->start;
470 16557555 : hdr->start = DEQUE_(private_next)( start, max1 );
471 16557555 : return res;
472 16557555 : }
473 :
474 : static inline DEQUE_T *
475 16763622 : DEQUE_(pop_tail_nocopy)( DEQUE_T * deque ) {
476 16763622 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
477 16763622 : ulong max1 = hdr->max1;
478 16763622 : ulong cnt = hdr->cnt;
479 16763622 : ulong end = hdr->end;
480 16763622 : hdr->cnt = cnt - 1UL;
481 16763622 : hdr->end = DEQUE_(private_prev)( end, max1 );
482 16763622 : return hdr->deque + hdr->end;
483 16763622 : }
484 :
485 : static inline DEQUE_T *
486 4527 : DEQUE_(remove_all)( DEQUE_T * deque ) {
487 4527 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
488 4527 : hdr->cnt = 0UL;
489 4527 : hdr->start = 0UL;
490 4527 : hdr->end = 0UL;
491 4527 : return deque;
492 4527 : }
493 :
494 : typedef struct { ulong rem; ulong idx; } DEQUE_(iter_t);
495 :
496 : static inline DEQUE_(iter_t)
497 19509096 : DEQUE_(iter_init)( DEQUE_T const * deque ) {
498 19509096 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
499 19509096 : DEQUE_(iter_t) iter;
500 19509096 : iter.rem = hdr->cnt;
501 19509096 : iter.idx = hdr->start;
502 19509096 : return iter;
503 19509096 : }
504 :
505 : static inline DEQUE_(iter_t)
506 17651076 : DEQUE_(iter_init_rev)( DEQUE_T const * deque ) {
507 17651076 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
508 17651076 : DEQUE_(iter_t) iter;
509 17651076 : iter.rem = hdr->cnt;
510 17651076 : iter.idx = hdr->end;
511 17651076 : iter.idx = DEQUE_(private_prev)( iter.idx, hdr->max1 );
512 17651076 : return iter;
513 17651076 : }
514 :
515 : static inline int
516 252660543 : DEQUE_(iter_done)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
517 252660543 : (void)deque;
518 252660543 : return !iter.rem;
519 252660543 : }
520 :
521 : static inline int
522 103578753 : DEQUE_(iter_done_rev)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
523 103578753 : (void)deque;
524 103578753 : return !iter.rem;
525 103578753 : }
526 :
527 : static inline DEQUE_(iter_t)
528 233151447 : DEQUE_(iter_next)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
529 233151447 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
530 233151447 : iter.rem--;
531 233151447 : iter.idx = DEQUE_(private_next)( iter.idx, hdr->max1 );
532 233151447 : return iter;
533 233151447 : }
534 :
535 : static inline DEQUE_(iter_t)
536 85927677 : DEQUE_(iter_prev)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
537 85927677 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
538 85927677 : iter.rem--;
539 85927677 : iter.idx = DEQUE_(private_prev)( iter.idx, hdr->max1 );
540 85927677 : return iter;
541 85927677 : }
542 :
543 : static inline DEQUE_T *
544 247762272 : DEQUE_(iter_ele)( DEQUE_T * deque, DEQUE_(iter_t) iter ) {
545 247762272 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
546 247762272 : return hdr->deque + iter.idx;
547 247762272 : }
548 :
549 : static inline DEQUE_T const *
550 71317035 : DEQUE_(iter_ele_const)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
551 71317035 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
552 71317035 : return hdr->deque + iter.idx;
553 71317035 : }
554 :
555 : FD_PROTOTYPES_END
556 :
557 : #undef DEQUE_
558 :
559 : #undef DEQUE_T
560 : #undef DEQUE_NAME
561 :
|
