Line data Source code
1 : /* Declares a family of functions implementing a single-threaded 2 : compile-time fixed-capacity queue designed for high performance 3 : contexts. Example usage: 4 : 5 : #define QUEUE_NAME my_queue 6 : #define QUEUE_T my_ele_t 7 : #define QUEUE_MAX 64UL 8 : #include "util/tmpl/fd_queue.c" 9 : 10 : This creates the following API for use in the local compilation unit: 11 : 12 : ulong my_queue_align ( void ); // required byte alignment of a queue 13 : ulong my_queue_footprint( void ); // required byte footprint of a queue with the given QUEUE_MAX 14 : void * my_queue_new ( void * shmem ); // format memory region into a my_queue, my_queue will be empty 15 : // (caller not joined on return, mem has required align/footprint, etc) 16 : my_ele_t * my_queue_join ( void * shqueue ); // join a my_queue (unlimited joins, etc) (NOT A CAST OF SHQUEUE) 17 : // join can be indexed like a normal array with QUEUE_MAX elements 18 : void * my_queue_leave ( my_ele_t * queue ); // leave a my_queue (matched with join, etc) (NOT A CAST OF QUEUE) 19 : void * my_queue_delete ( void * shqueue ); // unformat memory (no active joins, etc) 20 : 21 : // Accessors 22 : 23 : ulong my_queue_max ( my_ele_t const * queue ); // returns the max elements that could be in the queue (==QUEUE_MAX) 24 : ulong my_queue_cnt ( my_ele_t const * queue ); // returns the number of elements in the queue, in [0,QUEUE_MAX] 25 : ulong my_queue_avail( my_ele_t const * queue ); // returns max-cnt 26 : int my_queue_empty( my_ele_t const * queue ); // returns 1 if queue is empty and 0 otherwise 27 : int my_queue_full ( my_ele_t const * queue ); // returns 1 if queue is full and 0 otherwise 28 : 29 : // Simple API 30 : 31 : my_ele_t * my_queue_push( my_ele_t * queue, my_ele_t ele ); // push ele to queue, returns queue 32 : my_ele_t my_queue_pop ( my_ele_t * queue ); // pop ele from queue, returns ele 33 : 34 : // Advanced API for zero-copy usage 35 : 36 : my_ele_t * my_queue_peek_insert( my_ele_t * queue ); // peeks at most recent insert/push, 37 : // returned ptr lifetime is until next op on queue 38 : my_ele_t * my_queue_peek_remove( my_ele_t * queue ); // peeks at least recent insert/push, 39 : // returned ptr lifetime is until next op on queue 40 : my_ele_t * my_queue_insert ( my_ele_t * queue ); // push uninitialized element, returns queue 41 : my_ele_t * my_queue_remove ( my_ele_t * queue ); // pops queue, returns queue 42 : my_ele_t * my_queue_remove_all ( my_ele_t * queue ); // removes all, returns queue, fast O(1) 43 : 44 : my_ele_t const * my_queue_peek_insert_const( my_ele_t const * queue ); // const version of peek_insert 45 : my_ele_t const * my_queue_peek_remove_const( my_ele_t const * queue ); // const version of peek_remove 46 : 47 : For performance, none of the functions do any error checking. 48 : Specifically, the caller promises that MAX is such that footprint 49 : will not overflow 2^64 (e.g. MAX << (2^64)/sizeof(my_ele_t)), cnt<max 50 : for any push or insert operation and cnt>0 for any pop, peek or 51 : remove operation (remove_all is fine on an empty queue). */ 52 : 53 : #include "../bits/fd_bits.h" 54 : #include <stddef.h> 55 : 56 : #ifndef QUEUE_NAME 57 : #error "Define QUEUE_NAME" 58 : #endif 59 : 60 : #ifndef QUEUE_T 61 : #error "Define QUEUE_T" 62 : #endif 63 : 64 : #ifndef QUEUE_MAX 65 : #error "Define QUEUE_MAX or use fd_queue_dynamic" 66 : #endif 67 : 68 : #if (QUEUE_MAX)<1UL 69 : #error "QUEUE_MAX must be positive" 70 : #endif 71 : 72 : /* Implementation *****************************************************/ 73 : 74 3933355065 : #define QUEUE_(x) FD_EXPAND_THEN_CONCAT3(QUEUE_NAME,_,x) 75 : 76 : struct QUEUE_(private) { 77 : 78 : /* The number of elements in the queue is cnt=end-start and cnt will be 79 : in [0,max]. If cnt==0, the queue is empty. If cnt==MAX, the queue 80 : if full. 81 : 82 : For a non-empty queue, the next to pop is at element queue[ start % MAX ], 83 : and the next to push is at element queue[ (end-1UL) % MAX ] 84 : 85 : start and end overflow/underflow are fine if max is a power of two 86 : and start and end are initialized such that overflow / underflow 87 : will not happen for millennia practically anyway. More precisely, 88 : this implementation is guaranteed when max is a power of two and/or 89 : when fewer than 2^63 operations have been done on the queue (which, 90 : practically speaking, would take millennia). If, in some distant 91 : age, a user does want to support doing more than 2^63 operations 92 : when max is not a power of two, this can be done by moving start 93 : and end as close as possible toward 2^63 by the same integer 94 : multiple of max toward 2^63 sporadically (every couple of hundred 95 : years or so). */ 96 : 97 : ulong start; 98 : ulong end; 99 : QUEUE_T queue[ (ulong)(QUEUE_MAX) ]; 100 : }; 101 : 102 : typedef struct QUEUE_(private) QUEUE_(private_t); 103 : 104 : FD_PROTOTYPES_BEGIN 105 : 106 : /* private_from_queue return a pointer to the queue_private given a 107 : pointer to the queue. */ 108 : 109 : FD_FN_CONST static inline QUEUE_(private_t) * 110 0 : QUEUE_(private_hdr_from_queue)( QUEUE_T * queue ) { 111 0 : return (QUEUE_(private_t) *)( (ulong)queue - offsetof(QUEUE_(private_t), queue) ); 112 0 : } 113 : 114 : /* const-correct version of above */ 115 : 116 : FD_FN_CONST static inline QUEUE_(private_t) const * 117 0 : QUEUE_(private_const_hdr_from_queue)( QUEUE_T const * queue ) { 118 0 : return (QUEUE_(private_t) const *)( (ulong)queue - offsetof(QUEUE_(private_t), queue) ); 119 0 : } 120 : 121 : /* private_slot maps an index to a slot cnt. The compiler should 122 : optimize this to a bit-and when MAX is a power of 2 and, hopefully, 123 : to optimize this to a magic multiply otherwise. */ 124 : 125 466674195 : FD_FN_CONST static inline ulong QUEUE_(private_slot)( ulong i ) { return i % (ulong)(QUEUE_MAX); } 126 : 127 0 : FD_FN_CONST static inline ulong QUEUE_(align) ( void ) { return alignof(QUEUE_(private_t)); } 128 0 : FD_FN_CONST static inline ulong QUEUE_(footprint)( void ) { return sizeof (QUEUE_(private_t)); } 129 : 130 : static inline void * 131 3 : QUEUE_(new)( void * shmem ) { 132 3 : QUEUE_(private_t) * hdr = (QUEUE_(private_t) *)shmem; 133 : /* These values are large enough that underflow/overflow will never 134 : happen in practical usage. For example, it would take hundreds of 135 : years if all a core did was a worst case continuous push/pop pairs 136 : at 1 Gpair/sec. So we don't need to do any special handling 137 : overflow handling in practice that might otherwise be required if 138 : max is not a power-of-two MAX). Note also that overflow/underflow 139 : doesn't matter if max is a power of two as per the note above. */ 140 3 : hdr->start = 1UL << 63; 141 3 : hdr->end = 1UL << 63; 142 3 : return hdr; 143 3 : } 144 : 145 : static inline QUEUE_T * 146 3 : QUEUE_(join)( void * shqueue ) { 147 3 : QUEUE_(private_t) * hdr = (QUEUE_(private_t) *)shqueue; 148 3 : return hdr->queue; 149 3 : } 150 : 151 3 : static inline void * QUEUE_(leave) ( QUEUE_T * queue ) { return (void *)QUEUE_(private_hdr_from_queue)( queue ); } 152 3 : static inline void * QUEUE_(delete)( void * shqueue ) { return shqueue; } 153 : 154 0 : FD_FN_CONST static inline ulong QUEUE_(max)( QUEUE_T const * queue ) { (void)queue; return (ulong)(QUEUE_MAX); } 155 : 156 : FD_FN_PURE static inline ulong 157 300000003 : QUEUE_(cnt)( QUEUE_T const * queue ) { 158 300000003 : QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue ); 159 300000003 : return hdr->end - hdr->start; 160 300000003 : } 161 : 162 : FD_FN_PURE static inline ulong 163 300000000 : QUEUE_(avail)( QUEUE_T const * queue ) { 164 300000000 : QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue ); 165 300000000 : return ((ulong)(QUEUE_MAX)) - (hdr->end - hdr->start); 166 300000000 : } 167 : 168 : FD_FN_PURE static inline int 169 300000000 : QUEUE_(empty)( QUEUE_T const * queue ) { 170 300000000 : QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue ); 171 300000000 : return !(hdr->end - hdr->start); 172 300000000 : } 173 : 174 : FD_FN_PURE static inline int 175 300000000 : QUEUE_(full)( QUEUE_T const * queue ) { 176 300000000 : QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue ); 177 300000000 : return (hdr->end - hdr->start)==((ulong)QUEUE_MAX); 178 300000000 : } 179 : 180 : static inline QUEUE_T * 181 : QUEUE_(push)( QUEUE_T * queue, 182 66667296 : QUEUE_T ele ) { 183 66667296 : QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue ); 184 66667296 : hdr->queue[ QUEUE_(private_slot)( hdr->end ) ] = ele; 185 66667296 : hdr->end++; 186 66667296 : return queue; 187 66667296 : } 188 : 189 : static inline QUEUE_T 190 66682113 : QUEUE_(pop)( QUEUE_T * queue ) { 191 66682113 : QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue ); 192 66682113 : QUEUE_T ele = hdr->queue[ QUEUE_(private_slot)( hdr->start ) ]; 193 66682113 : hdr->start++; 194 66682113 : return ele; 195 66682113 : } 196 : 197 : FD_FN_PURE static inline QUEUE_T * 198 66645321 : QUEUE_(peek_remove)( QUEUE_T * queue ) { 199 66645321 : QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue ); 200 66645321 : return hdr->queue + QUEUE_(private_slot)( hdr->start ); 201 66645321 : } 202 : 203 : FD_FN_PURE static inline QUEUE_T * 204 133356096 : QUEUE_(peek_insert)( QUEUE_T * queue ) { 205 133356096 : QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue ); 206 133356096 : return hdr->queue + QUEUE_(private_slot)( hdr->end-1UL ); 207 133356096 : } 208 : 209 : FD_FN_PURE static inline QUEUE_T const * 210 66678048 : QUEUE_(peek_insert_const)( QUEUE_T * queue ) { 211 66678048 : QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue ); 212 66678048 : return hdr->queue + QUEUE_(private_slot)( hdr->end-1UL ); 213 66678048 : } 214 : 215 : FD_FN_PURE static inline QUEUE_T const * 216 66645321 : QUEUE_(peek_remove_const)( QUEUE_T const * queue ) { 217 66645321 : QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue ); 218 66645321 : return hdr->queue + QUEUE_(private_slot)( hdr->start ); 219 66645321 : } 220 : 221 66678048 : static inline QUEUE_T * QUEUE_(insert)( QUEUE_T * queue ) { QUEUE_(private_hdr_from_queue)( queue )->end++; return queue; } 222 66645321 : static inline QUEUE_T * QUEUE_(remove)( QUEUE_T * queue ) { QUEUE_(private_hdr_from_queue)( queue )->start++; return queue; } 223 : 224 : static inline QUEUE_T * 225 4548 : QUEUE_(remove_all)( QUEUE_T * queue ) { 226 4548 : QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue ); 227 : /* See note in new */ 228 4548 : hdr->start = 1UL << 63; 229 4548 : hdr->end = 1UL << 63; 230 4548 : return queue; 231 4548 : } 232 : 233 : FD_PROTOTYPES_END 234 : 235 : #undef QUEUE_ 236 : 237 : #undef QUEUE_MAX 238 : #undef QUEUE_T 239 : #undef QUEUE_NAME 240 :
