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 : my_ele_t * my_deque_peek_tail ( my_ele_t * deque ); // peeks at tail, returned ptr lifetime is until next op on deque
57 : 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
58 : my_ele_t * my_deque_insert_head( my_ele_t * deque ); // inserts uninitialized element at head, returns deque
59 : my_ele_t * my_deque_insert_tail( my_ele_t * deque ); // inserts uninitialized element at tail, returns deque
60 : my_ele_t * my_deque_remove_head( my_ele_t * deque ); // removes head, returns deque
61 : my_ele_t * my_deque_remove_tail( my_ele_t * deque ); // removes tail, returns deque
62 : my_ele_t * my_deque_remove_all ( my_ele_t * deque ); // removes all, returns deque, fast O(1)
63 :
64 : my_ele_t * my_deque_push_head_nocopy( my_ele_t * deque ); // push the head, returns the new uninitialized element
65 : my_ele_t * my_deque_push_tail_nocopy( my_ele_t * deque ); // push the tail, returns the new uninitialized element
66 : my_ele_t * my_deque_pop_head_nocopy ( my_ele_t * deque ); // pops the head, returns the deleted element
67 : my_ele_t * my_deque_pop_tail_nocopy ( my_ele_t * deque ); // pops the tail, returns the deleted element
68 :
69 : my_ele_t const * my_deque_peek_head_const ( my_ele_t const * deque ); // const version of peek_head
70 : my_ele_t const * my_deque_peek_tail_const ( my_ele_t const * deque ); // const version of peek_tail
71 : my_ele_t const * my_deque_peek_index_const( my_ele_t const * deque, ulong idx ); // const version of peek_index
72 :
73 : // my_deque_iter_* allow for iteration over all the elements in
74 : // a my_deque. The iteration will be in order from head to tail.
75 : // Example usage:
76 : //
77 : // for( my_deque_iter_t iter = my_deque_iter_init( deque ); !my_deque_iter_done( deque, iter ); iter = my_deque_iter_next( deque, iter ) ) {
78 : // my_deque_t * ele = my_deque_iter_ele( deque, iter );
79 : //
80 : // ... process ele here
81 : // }
82 :
83 : my_deque_iter_t my_deque_iter_init ( my_deque_t const * deque );
84 : int my_deque_iter_done ( my_deque_t const * deque, my_deque_iter_t iter ); // returns 1 if no more iterations, 0 o.w.
85 : my_deque_iter_t my_deque_iter_next ( my_deque_t const * deque, my_deque_iter_t iter ); // returns next iter value iter
86 : my_ele_t * my_deque_iter_ele ( my_deque_t * deque, my_deque_iter_t iter ); // assumes not done, return non-NULL ele
87 : 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
88 :
89 : // my_deque_iter_rev_* allow for iteration similar to the above, but
90 : // in reverse order from tail to head.
91 : // Example usage:
92 : //
93 : // 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 ) ) {
94 : // my_deque_t * ele = my_deque_iter_ele( deque, iter );
95 : //
96 : // ... process ele here
97 : // }
98 :
99 : my_deque_iter_t my_deque_iter_init_rev ( my_deque_t const * deque );
100 : 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.
101 : my_deque_iter_t my_deque_iter_prev ( my_deque_t const * deque, my_deque_iter_t iter ); // returns prev iter value iter
102 :
103 : For performance, none of the functions do any error checking.
104 : Specifically, the caller promises that MAX is such that footprint
105 : will not overflow 2^64 (e.g. MAX << (2^64)/sizeof(my_ele_t)), cnt<max
106 : for any push or insert operation and cnt>0 for any pop, peek or
107 : remove operation (remove_all is fine on an empty deque). */
108 :
109 : #include "../bits/fd_bits.h"
110 :
111 : #include <stddef.h>
112 :
113 : #ifndef DEQUE_NAME
114 : #error "Define DEQUE_NAME"
115 : #endif
116 :
117 : #ifndef DEQUE_T
118 : #error "Define DEQUE_T"
119 : #endif
120 :
121 : #ifndef DEQUE_MAX
122 : #error "Define DEQUE_MAX or use fd_deque_dynamic"
123 : #endif
124 :
125 : /* Note: we don't support DEQUE_MAX==0 (like we do in fd_deque_dynamic)
126 : because of spotty C++ for zero length array members in the current
127 : implementation (though it would be possible to do so with a different
128 : implementation). */
129 :
130 : #if (DEQUE_MAX)<1UL
131 : #error "DEQUE_MAX must be positive"
132 : #endif
133 :
134 : /* Implementation *****************************************************/
135 :
136 4727688810 : #define DEQUE_(x) FD_EXPAND_THEN_CONCAT3(DEQUE_NAME,_,x)
137 :
138 : struct DEQUE_(private) {
139 :
140 : /* The number of elements in the deque is cnt=end-start and cnt will be
141 : in [0,max]. If cnt==0, the deque is empty. If cnt==MAX, the deque
142 : if full.
143 :
144 : For a non-empty deque, the deque head is at element deque[ start % MAX ],
145 : and the deque tail is at element deque[ (end-1UL) % MAX ]
146 :
147 : start and end overflow/underflow are fine if max is a power of two
148 : and start and end are initialized such that overflow / underflow
149 : will not happen for millennia practically anyway. More precisely,
150 : this implementation is guaranteed when max is a power of two and/or
151 : when fewer than 2^63 operations have been done on the deque (which,
152 : practically speaking, would take millennia). If, in some distant
153 : age, a user does want to support doing more than 2^63 operations
154 : when max is not a power of two, this can be done by moving start
155 : and end as close as possible toward 2^63 by the same integer
156 : multiple of max toward 2^63 sporadically (every couple of hundred
157 : years or so). */
158 :
159 : ulong start;
160 : ulong end;
161 : DEQUE_T deque[ (ulong)(DEQUE_MAX) ];
162 : };
163 :
164 : typedef struct DEQUE_(private) DEQUE_(private_t);
165 :
166 : FD_PROTOTYPES_BEGIN
167 :
168 : /* private_from_deque return a pointer to the deque_private given a
169 : pointer to the deque. */
170 :
171 : FD_FN_CONST static inline DEQUE_(private_t) *
172 0 : DEQUE_(private_hdr_from_deque)( DEQUE_T * deque ) {
173 0 : return (DEQUE_(private_t) *)( (ulong)deque - offsetof(DEQUE_(private_t), deque) );
174 0 : }
175 :
176 : /* const-correct version of above */
177 :
178 : FD_FN_CONST static inline DEQUE_(private_t) const *
179 0 : DEQUE_(private_const_hdr_from_deque)( DEQUE_T const * deque ) {
180 0 : return (DEQUE_(private_t) const *)( (ulong)deque - offsetof(DEQUE_(private_t), deque) );
181 0 : }
182 :
183 : /* private_slot maps an index to a slot cnt. The compiler should
184 : optimize this to a bit-and when MAX is a power of 2 and, hopefully,
185 : to optimize this to a magic multiply otherwise. */
186 :
187 616612539 : FD_FN_CONST static inline ulong DEQUE_(private_slot)( ulong i ) { return i % (ulong)(DEQUE_MAX); }
188 :
189 0 : FD_FN_CONST static inline ulong DEQUE_(align) ( void ) { return alignof(DEQUE_(private_t)); }
190 0 : FD_FN_CONST static inline ulong DEQUE_(footprint)( void ) { return sizeof (DEQUE_(private_t)); }
191 :
192 : static inline void *
193 3 : DEQUE_(new)( void * shmem ) {
194 3 : DEQUE_(private_t) * hdr = (DEQUE_(private_t) *)shmem;
195 : /* These values are large enough that underflow/overflow will never
196 : happen in practical usage. For example, it would take hundreds of
197 : years if all a core did was a worst case continuous
198 : push_tail/pop_head pairs (or push_head/pop_tail) at 1 Gpair/sec.
199 : So we don't need to do any special handling overflow handling in
200 : practice that might otherwise be required if max is not a
201 : power-of-two MAX). Note also that overflow/underflow doesn't
202 : matter if max is a power of two as per the note above. */
203 3 : hdr->start = 1UL << 63;
204 3 : hdr->end = 1UL << 63;
205 3 : return hdr;
206 3 : }
207 :
208 : static inline DEQUE_T *
209 3 : DEQUE_(join)( void * shdeque ) {
210 3 : DEQUE_(private_t) * hdr = (DEQUE_(private_t) *)shdeque;
211 3 : return hdr->deque;
212 3 : }
213 :
214 3 : static inline void * DEQUE_(leave) ( DEQUE_T * deque ) { return (void *)DEQUE_(private_hdr_from_deque)( deque ); }
215 3 : static inline void * DEQUE_(delete)( void * shdeque ) { return shdeque; }
216 :
217 0 : FD_FN_CONST static inline ulong DEQUE_(max)( DEQUE_T const * deque ) { (void)deque; return (ulong)(DEQUE_MAX); }
218 :
219 : FD_FN_PURE static inline ulong
220 300000003 : DEQUE_(cnt)( DEQUE_T const * deque ) {
221 300000003 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
222 300000003 : return hdr->end - hdr->start;
223 300000003 : }
224 :
225 : FD_FN_PURE static inline ulong
226 300000000 : DEQUE_(avail)( DEQUE_T const * deque ) {
227 300000000 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
228 300000000 : return ((ulong)(DEQUE_MAX)) - (hdr->end - hdr->start);
229 300000000 : }
230 :
231 : FD_FN_PURE static inline int
232 300000000 : DEQUE_(empty)( DEQUE_T const * deque ) {
233 300000000 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
234 300000000 : return !(hdr->end - hdr->start);
235 300000000 : }
236 :
237 : FD_FN_PURE static inline int
238 300000000 : DEQUE_(full)( DEQUE_T const * deque ) {
239 300000000 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
240 300000000 : return (hdr->end - hdr->start)==((ulong)DEQUE_MAX);
241 300000000 : }
242 :
243 : static inline DEQUE_T *
244 : DEQUE_(push_head)( DEQUE_T * deque,
245 14490972 : DEQUE_T ele ) {
246 14490972 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
247 14490972 : hdr->start--;
248 14490972 : hdr->deque[ DEQUE_(private_slot)( hdr->start ) ] = ele;
249 14490972 : return deque;
250 14490972 : }
251 :
252 : static inline DEQUE_T *
253 : DEQUE_(push_tail)( DEQUE_T * deque,
254 14505516 : DEQUE_T ele ) {
255 14505516 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
256 14505516 : hdr->deque[ DEQUE_(private_slot)( hdr->end ) ] = ele;
257 14505516 : hdr->end++;
258 14505516 : return deque;
259 14505516 : }
260 :
261 : static inline DEQUE_T
262 16553364 : DEQUE_(pop_head)( DEQUE_T * deque ) {
263 16553364 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
264 16553364 : DEQUE_T ele = hdr->deque[ DEQUE_(private_slot)( hdr->start ) ];
265 16553364 : hdr->start++;
266 16553364 : return ele;
267 16553364 : }
268 :
269 : static inline DEQUE_T
270 16565439 : DEQUE_(pop_tail)( DEQUE_T * deque ) {
271 16565439 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
272 16565439 : hdr->end--;
273 16565439 : return hdr->deque[ DEQUE_(private_slot)( hdr->end ) ];
274 16565439 : }
275 :
276 : static inline DEQUE_T *
277 : DEQUE_(push_head_wrap)( DEQUE_T * deque,
278 17635728 : DEQUE_T ele ) {
279 17635728 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
280 17635728 : ulong start = hdr->start;
281 17635728 : ulong end = hdr->end;
282 :
283 : /* If the deque is full, pop and discard the tail. Note that
284 : DEQUE_MAX is positive. Thus, deque can never be full and empty at
285 : the same time making it always safe to pop the tail on full. */
286 :
287 17635728 : end -= (ulong)((end-start)==((ulong)DEQUE_MAX));
288 :
289 : /* Push the head */
290 :
291 17635728 : start--;
292 17635728 : hdr->deque[ DEQUE_(private_slot)(start) ] = ele;
293 :
294 17635728 : hdr->start = start;
295 17635728 : hdr->end = end;
296 17635728 : return deque;
297 17635728 : }
298 :
299 : static inline DEQUE_T *
300 : DEQUE_(push_tail_wrap)( DEQUE_T * deque,
301 17650173 : DEQUE_T ele ) {
302 17650173 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
303 17650173 : ulong start = hdr->start;
304 17650173 : ulong end = hdr->end;
305 :
306 : /* If the deque is full, pop and discard the head. Note that
307 : DEQUE_MAX is positive. Thus, deque can never be full and empty at
308 : the same time making it always safe to pop the head on full. */
309 :
310 17650173 : start += (ulong)((end-start)==((ulong)DEQUE_MAX));
311 :
312 : /* Push the tail */
313 :
314 17650173 : hdr->deque[ DEQUE_(private_slot)(end) ] = ele;
315 17650173 : end++;
316 :
317 17650173 : hdr->start = start;
318 17650173 : hdr->end = end;
319 17650173 : return deque;
320 17650173 : }
321 :
322 : static inline DEQUE_T
323 16566648 : DEQUE_(pop_idx_tail)( DEQUE_T * deque, ulong idx ) {
324 16566648 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
325 16566648 : DEQUE_T * cur = &hdr->deque[ DEQUE_(private_slot)( hdr->start + idx ) ];
326 16566648 : DEQUE_T ele = *cur;
327 51241827 : for(;;) {
328 51241827 : idx++;
329 51241827 : if( hdr->start + idx >= hdr->end ) break;
330 34675179 : DEQUE_T * next = &hdr->deque[ DEQUE_(private_slot)( hdr->start + idx ) ];
331 34675179 : *cur = *next;
332 34675179 : cur = next;
333 34675179 : }
334 16566648 : hdr->end--;
335 16566648 : return ele;
336 16566648 : }
337 :
338 : FD_FN_PURE static inline DEQUE_T *
339 14489388 : DEQUE_(peek_head)( DEQUE_T * deque ) {
340 14489388 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
341 14489388 : if( hdr->end == hdr->start )
342 0 : return NULL;
343 14489388 : return hdr->deque + DEQUE_(private_slot)( hdr->start );
344 14489388 : }
345 :
346 : FD_FN_PURE static inline DEQUE_T *
347 14492730 : DEQUE_(peek_tail)( DEQUE_T * deque ) {
348 14492730 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
349 14492730 : if( hdr->end == hdr->start )
350 0 : return NULL;
351 14492730 : return hdr->deque + DEQUE_(private_slot)( hdr->end-1UL );
352 14492730 : }
353 :
354 : FD_FN_PURE static inline DEQUE_T *
355 85926153 : DEQUE_(peek_index)( DEQUE_T * deque, ulong idx ) {
356 85926153 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
357 85926153 : return hdr->deque + DEQUE_(private_slot)( hdr->start + idx );
358 85926153 : }
359 :
360 : FD_FN_PURE static inline DEQUE_T const *
361 16557435 : DEQUE_(peek_head_const)( DEQUE_T const * deque ) {
362 16557435 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
363 16557435 : if( hdr->end == hdr->start )
364 0 : return NULL;
365 16557435 : return hdr->deque + DEQUE_(private_slot)( hdr->start );
366 16557435 : }
367 :
368 : FD_FN_PURE static inline DEQUE_T const *
369 16567389 : DEQUE_(peek_tail_const)( DEQUE_T const * deque ) {
370 16567389 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
371 16567389 : if( hdr->end == hdr->start )
372 0 : return NULL;
373 16567389 : return hdr->deque + DEQUE_(private_slot)( hdr->end-1UL );
374 16567389 : }
375 :
376 : FD_FN_PURE static inline DEQUE_T const *
377 85926153 : DEQUE_(peek_index_const)( DEQUE_T const * deque, ulong idx ) {
378 85926153 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
379 85926153 : return hdr->deque + DEQUE_(private_slot)( hdr->start + idx );
380 85926153 : }
381 :
382 14489388 : static inline DEQUE_T * DEQUE_(insert_head)( DEQUE_T * deque ) { DEQUE_(private_hdr_from_deque)( deque )->start--; return deque; }
383 14492730 : static inline DEQUE_T * DEQUE_(insert_tail)( DEQUE_T * deque ) { DEQUE_(private_hdr_from_deque)( deque )->end++; return deque; }
384 16557435 : static inline DEQUE_T * DEQUE_(remove_head)( DEQUE_T * deque ) { DEQUE_(private_hdr_from_deque)( deque )->start++; return deque; }
385 16567389 : static inline DEQUE_T * DEQUE_(remove_tail)( DEQUE_T * deque ) { DEQUE_(private_hdr_from_deque)( deque )->end--; return deque; }
386 :
387 : static inline DEQUE_T *
388 14484999 : DEQUE_(push_head_nocopy)( DEQUE_T * deque ) {
389 14484999 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
390 14484999 : hdr->start--;
391 14484999 : return &hdr->deque[ DEQUE_(private_slot)( hdr->start ) ];
392 14484999 : }
393 :
394 : static inline DEQUE_T *
395 14500395 : DEQUE_(push_tail_nocopy)( DEQUE_T * deque ) {
396 14500395 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
397 14500395 : DEQUE_T * ele = &hdr->deque[ DEQUE_(private_slot)( hdr->end ) ];
398 14500395 : hdr->end++;
399 14500395 : return ele;
400 14500395 : }
401 :
402 : static inline DEQUE_T *
403 16557555 : DEQUE_(pop_head_nocopy)( DEQUE_T * deque ) {
404 16557555 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
405 16557555 : DEQUE_T * ele = &hdr->deque[ DEQUE_(private_slot)( hdr->start ) ];
406 16557555 : hdr->start++;
407 16557555 : return ele;
408 16557555 : }
409 :
410 : static inline DEQUE_T *
411 16557516 : DEQUE_(pop_tail_nocopy)( DEQUE_T * deque ) {
412 16557516 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
413 16557516 : hdr->end--;
414 16557516 : return &hdr->deque[ DEQUE_(private_slot)( hdr->end ) ];
415 16557516 : }
416 :
417 : static inline DEQUE_T *
418 4488 : DEQUE_(remove_all)( DEQUE_T * deque ) {
419 4488 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
420 : /* See note in new */
421 4488 : hdr->start = 1UL << 63;
422 4488 : hdr->end = 1UL << 63;
423 4488 : return deque;
424 4488 : }
425 :
426 : typedef ulong DEQUE_(iter_t);
427 :
428 : static inline DEQUE_(iter_t)
429 17665593 : DEQUE_(iter_init)( DEQUE_T const * deque ) {
430 17665593 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
431 17665593 : return hdr->start;
432 17665593 : }
433 :
434 : static inline DEQUE_(iter_t)
435 17650908 : DEQUE_(iter_init_rev)( DEQUE_T const * deque ) {
436 17650908 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
437 17650908 : return hdr->end - 1;
438 17650908 : }
439 :
440 : static inline int
441 103649247 : DEQUE_(iter_done)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
442 103649247 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
443 103649247 : return iter == hdr->end;
444 103649247 : }
445 :
446 : static inline int
447 103577061 : DEQUE_(iter_done_rev)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
448 103577061 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
449 103577061 : return iter == hdr->start - 1;
450 103577061 : }
451 :
452 : static inline DEQUE_(iter_t)
453 85983654 : DEQUE_(iter_next)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
454 85983654 : (void)deque;
455 85983654 : return iter+1;
456 85983654 : }
457 :
458 : static inline DEQUE_(iter_t)
459 85926153 : DEQUE_(iter_prev)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
460 85926153 : (void)deque;
461 85926153 : return iter-1;
462 85926153 : }
463 :
464 : static inline DEQUE_T *
465 171909807 : DEQUE_(iter_ele)( DEQUE_T * deque, DEQUE_(iter_t) iter ) {
466 171909807 : DEQUE_(private_t) * hdr = DEQUE_(private_hdr_from_deque)( deque );
467 171909807 : return &hdr->deque[ DEQUE_(private_slot)( iter ) ];
468 171909807 : }
469 :
470 : static inline DEQUE_T const *
471 0 : DEQUE_(iter_ele_const)( DEQUE_T const * deque, DEQUE_(iter_t) iter ) {
472 0 : DEQUE_(private_t) const * hdr = DEQUE_(private_const_hdr_from_deque)( deque );
473 0 : return &hdr->deque[ DEQUE_(private_slot)( iter ) ];
474 0 : }
475 :
476 : FD_PROTOTYPES_END
477 :
478 : #undef DEQUE_
479 :
480 : #undef DEQUE_MAX
481 : #undef DEQUE_T
482 : #undef DEQUE_NAME
|
