Line data Source code
1 : /* Declares a family of functions implementing a single-threaded 2 : run-time fixed-capacity queue designed for high performance contexts. 3 : Example usage: 4 : 5 : #define QUEUE_NAME my_queue 6 : #define QUEUE_T my_ele_t 7 : #include "util/tmpl/fd_queue.c" 8 : 9 : This creates the following API for use in the local compilation unit: 10 : 11 : ulong my_queue_align ( void ); // required byte alignment of a queue 12 : ulong my_queue_footprint( ulong max ); // required byte footprint of a queue with max capacity 13 : void * my_queue_new ( void * shmem, // format memory region into a my_queue, my_queue will be empty 14 : ulong max ); // (caller not joined on return, mem has required align/footprint, etc) 15 : my_ele_t * my_queue_join ( void * shqueue ); // join a my_queue (unlimited joins, etc) (NOT A CAST OF SHQUEUE) 16 : // join can be indexed like a normal array with max elements 17 : void * my_queue_leave ( my_ele_t * queue ); // leave a my_queue (matched with join, etc) (NOT A CAST OF QUEUE) 18 : void * my_queue_delete ( void * shqueue ); // unformat memory (no active joins, etc) 19 : 20 : // Accessors 21 : 22 : ulong my_queue_max ( my_ele_t const * queue ); // returns the max elements that could be in the queue 23 : ulong my_queue_cnt ( my_ele_t const * queue ); // returns the number of elements in the queue, in [0,max] 24 : ulong my_queue_avail( my_ele_t const * queue ); // returns max-cnt 25 : int my_queue_empty( my_ele_t const * queue ); // returns 1 if queue is empty and 0 otherwise 26 : int my_queue_full ( my_ele_t const * queue ); // returns 1 if queue is full and 0 otherwise 27 : 28 : // Simple API 29 : 30 : my_ele_t * my_queue_push( my_ele_t * queue, my_ele_t ele ); // push ele to queue, returns queue 31 : my_ele_t my_queue_pop ( my_ele_t * queue ); // pop ele from queue, returns ele 32 : 33 : // Advanced API for zero-copy usage 34 : 35 : my_ele_t * my_queue_peek_insert( my_ele_t * queue ); // peeks at most recent insert/push, 36 : // returned ptr lifetime is until next op on queue 37 : my_ele_t * my_queue_peek_remove( my_ele_t * queue ); // peeks at least recent insert/push, 38 : // returned ptr lifetime is until next op on queue 39 : my_ele_t * my_queue_insert ( my_ele_t * queue ); // push uninitialized element, returns queue 40 : my_ele_t * my_queue_remove ( my_ele_t * queue ); // pops queue, returns queue 41 : my_ele_t * my_queue_remove_all ( my_ele_t * queue ); // removes all, returns queue, fast O(1) 42 : 43 : my_ele_t const * my_queue_peek_insert_const( my_ele_t const * queue ); // const version of peek_insert 44 : my_ele_t const * my_queue_peek_remove_const( my_ele_t const * queue ); // const version of peek_remove 45 : 46 : For performance, none of the functions do any error checking. 47 : Specifically, the caller promises that max is such that footprint 48 : will not overflow 2^64 (e.g. max << (2^64)/sizeof(my_ele_t)), cnt<max 49 : for any push or insert operation and cnt>0 for any pop, peek or 50 : remove operation (remove_all is fine on an empty queue). */ 51 : 52 : #include "../bits/fd_bits.h" 53 : #include <stddef.h> 54 : 55 : #ifndef QUEUE_NAME 56 : #error "Define QUEUE_NAME" 57 : #endif 58 : 59 : #ifndef QUEUE_T 60 : #error "Define QUEUE_T" 61 : #endif 62 : 63 : /* Implementation *****************************************************/ 64 : 65 4366711167 : #define QUEUE_(x) FD_EXPAND_THEN_CONCAT3(QUEUE_NAME,_,x) 66 : 67 : struct QUEUE_(private) { 68 : ulong max1; /* Max elements in queue minus 1 */ 69 : ulong cnt; /* Num elements in queue, in [0,max] */ 70 : ulong start; /* Index of next to pop, in [0,max) */ 71 : ulong end; /* Index of next to push, in [0,max) */ 72 : QUEUE_T queue[ 1 ]; /* Actually max in size */ 73 : }; 74 : 75 : typedef struct QUEUE_(private) QUEUE_(private_t); 76 : 77 : FD_PROTOTYPES_BEGIN 78 : 79 : /* private_from_queue returns a pointer to the queue_private given a 80 : pointer to the queue. */ 81 : 82 : FD_FN_CONST static inline QUEUE_(private_t) * 83 0 : QUEUE_(private_hdr_from_queue)( QUEUE_T * queue ) { 84 0 : return (QUEUE_(private_t) *)( (ulong)queue - offsetof(QUEUE_(private_t), queue) ); 85 0 : } 86 : 87 : /* const-correct version of above */ 88 : 89 : FD_FN_CONST static inline QUEUE_(private_t) const * 90 0 : QUEUE_(private_const_hdr_from_queue)( QUEUE_T const * queue ) { 91 0 : return (QUEUE_(private_t) const *)( (ulong)queue - offsetof(QUEUE_(private_t), queue) ); 92 0 : } 93 : 94 : /* These move i to the previous or next slot to i for given max. 95 : Input should be in [0,max) and output will be in [0,max). */ 96 : 97 200034144 : FD_FN_CONST static inline ulong QUEUE_(private_prev)( ulong i, ulong max1 ) { return fd_ulong_if( i==0UL, max1, i-1UL ); } 98 266672778 : FD_FN_CONST static inline ulong QUEUE_(private_next)( ulong i, ulong max1 ) { return fd_ulong_if( i>=max1, 0UL, i+1UL ); } 99 : 100 0 : FD_FN_CONST static inline ulong QUEUE_(align)( void ) { return alignof(QUEUE_(private_t)); } 101 : 102 : FD_FN_CONST static inline ulong 103 3 : QUEUE_(footprint)( ulong max ) { 104 3 : return fd_ulong_align_up( fd_ulong_align_up( 32UL, alignof(QUEUE_T) ) + sizeof(QUEUE_T)*max, alignof(QUEUE_(private_t)) ); 105 3 : } 106 : 107 : static inline void * 108 : QUEUE_(new)( void * shmem, 109 3 : ulong max ) { 110 3 : QUEUE_(private_t) * hdr = (QUEUE_(private_t) *)shmem; 111 3 : hdr->max1 = max-1UL; 112 3 : hdr->cnt = 0UL; 113 3 : hdr->start = 0UL; 114 3 : hdr->end = 0UL; 115 3 : return hdr; 116 3 : } 117 : 118 : static inline QUEUE_T * 119 3 : QUEUE_(join)( void * shqueue ) { 120 3 : QUEUE_(private_t) * hdr = (QUEUE_(private_t) *)shqueue; 121 3 : return hdr->queue; 122 3 : } 123 : 124 3 : static inline void * QUEUE_(leave) ( QUEUE_T * queue ) { return (void *)QUEUE_(private_hdr_from_queue)( queue ); } 125 3 : static inline void * QUEUE_(delete)( void * shqueue ) { return shqueue; } 126 : 127 : FD_FN_PURE static inline ulong 128 300000003 : QUEUE_(max)( QUEUE_T const * queue ) { 129 300000003 : QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue ); 130 300000003 : return hdr->max1 + 1UL; 131 300000003 : } 132 : 133 : FD_FN_PURE static inline ulong 134 300000003 : QUEUE_(cnt)( QUEUE_T const * queue ) { 135 300000003 : QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue ); 136 300000003 : return hdr->cnt; 137 300000003 : } 138 : 139 : FD_FN_PURE static inline ulong 140 300000000 : QUEUE_(avail)( QUEUE_T const * queue ) { 141 300000000 : QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue ); 142 300000000 : return hdr->max1 + 1UL - hdr->cnt; 143 300000000 : } 144 : 145 : FD_FN_PURE static inline int 146 300000000 : QUEUE_(empty)( QUEUE_T const * queue ) { 147 300000000 : return !QUEUE_(private_const_hdr_from_queue)( queue )->cnt; 148 300000000 : } 149 : 150 : FD_FN_PURE static inline int 151 300000000 : QUEUE_(full)( QUEUE_T const * queue ) { 152 300000000 : QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue ); 153 300000000 : return (hdr->max1 + 1UL)==hdr->cnt; 154 300000000 : } 155 : 156 : static inline QUEUE_T * 157 : QUEUE_(push)( QUEUE_T * queue, 158 66667296 : QUEUE_T ele ) { 159 66667296 : QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue ); 160 66667296 : ulong max1 = hdr->max1; 161 66667296 : ulong cnt = hdr->cnt; 162 66667296 : ulong end = hdr->end; 163 66667296 : hdr->queue[ end ] = ele; 164 66667296 : end = QUEUE_(private_next)( end, max1 ); 165 66667296 : hdr->cnt = cnt+1UL; 166 66667296 : hdr->end = end; 167 66667296 : return queue; 168 66667296 : } 169 : 170 : static inline QUEUE_T 171 66682113 : QUEUE_(pop)( QUEUE_T * queue ) { 172 66682113 : QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue ); 173 66682113 : ulong max1 = hdr->max1; 174 66682113 : ulong cnt = hdr->cnt; 175 66682113 : ulong start = hdr->start; 176 66682113 : QUEUE_T ele = hdr->queue[ start ]; 177 66682113 : start = QUEUE_(private_next)( start, max1 ); 178 66682113 : hdr->cnt = cnt-1UL; 179 66682113 : hdr->start = start; 180 66682113 : return ele; 181 66682113 : } 182 : 183 : FD_FN_PURE static inline QUEUE_T * 184 133356096 : QUEUE_(peek_insert)( QUEUE_T * queue ) { 185 133356096 : QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue ); 186 133356096 : return hdr->queue + QUEUE_(private_prev)( hdr->end, hdr->max1 ); 187 133356096 : } 188 : 189 : FD_FN_PURE static inline QUEUE_T * 190 66645321 : QUEUE_(peek_remove)( QUEUE_T * queue ) { 191 66645321 : QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue ); 192 66645321 : return hdr->queue + hdr->start; 193 66645321 : } 194 : 195 : FD_FN_PURE static inline QUEUE_T const * 196 66678048 : QUEUE_(peek_insert_const)( QUEUE_T const * queue ) { 197 66678048 : QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue ); 198 66678048 : return hdr->queue + QUEUE_(private_prev)( hdr->end, hdr->max1 ); 199 66678048 : } 200 : 201 : FD_FN_PURE static inline QUEUE_T const * 202 66645321 : QUEUE_(peek_remove_const)( QUEUE_T const * queue ) { 203 66645321 : QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue ); 204 66645321 : return hdr->queue + hdr->start; 205 66645321 : } 206 : 207 : static inline QUEUE_T * 208 66678048 : QUEUE_(insert)( QUEUE_T * queue ) { 209 66678048 : QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue ); 210 66678048 : ulong max1 = hdr->max1; 211 66678048 : ulong cnt = hdr->cnt; 212 66678048 : ulong end = hdr->end; 213 66678048 : hdr->cnt = cnt + 1UL; 214 66678048 : hdr->end = QUEUE_(private_next)( end, max1 ); 215 66678048 : return queue; 216 66678048 : } 217 : 218 : static inline QUEUE_T * 219 66645321 : QUEUE_(remove)( QUEUE_T * queue ) { 220 66645321 : QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue ); 221 66645321 : ulong max1 = hdr->max1; 222 66645321 : ulong cnt = hdr->cnt; 223 66645321 : ulong start = hdr->start; 224 66645321 : hdr->cnt = cnt - 1UL; 225 66645321 : hdr->start = QUEUE_(private_next)( start, max1 ); 226 66645321 : return queue; 227 66645321 : } 228 : 229 : static inline QUEUE_T * 230 4548 : QUEUE_(remove_all)( QUEUE_T * queue ) { 231 4548 : QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue ); 232 4548 : hdr->cnt = 0UL; 233 4548 : hdr->start = 0UL; 234 4548 : hdr->end = 0UL; 235 4548 : return queue; 236 4548 : } 237 : 238 : FD_PROTOTYPES_END 239 : 240 : #undef QUEUE_ 241 : 242 : #undef QUEUE_T 243 : #undef QUEUE_NAME 244 :