| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /*********************************************************************************/ | ||
| 2 | /* Copyright 2009-2024 Barcelona Supercomputing Center */ | ||
| 3 | /* */ | ||
| 4 | /* This file is part of the DLB library. */ | ||
| 5 | /* */ | ||
| 6 | /* DLB is free software: you can redistribute it and/or modify */ | ||
| 7 | /* it under the terms of the GNU Lesser General Public License as published by */ | ||
| 8 | /* the Free Software Foundation, either version 3 of the License, or */ | ||
| 9 | /* (at your option) any later version. */ | ||
| 10 | /* */ | ||
| 11 | /* DLB is distributed in the hope that it will be useful, */ | ||
| 12 | /* but WITHOUT ANY WARRANTY; without even the implied warranty of */ | ||
| 13 | /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */ | ||
| 14 | /* GNU Lesser General Public License for more details. */ | ||
| 15 | /* */ | ||
| 16 | /* You should have received a copy of the GNU Lesser General Public License */ | ||
| 17 | /* along with DLB. If not, see <https://www.gnu.org/licenses/>. */ | ||
| 18 | /*********************************************************************************/ | ||
| 19 | |||
| 20 | /* Credits: https://www.davidpriver.com/ctemplates.html */ | ||
| 21 | |||
| 22 | /* Include this header multiple times to implement a fixed-size circular queue. | ||
| 23 | * Before inclusion define at least QUEUE_T and QUEUE_SIZE to the type the | ||
| 24 | * queue can hold. | ||
| 25 | * | ||
| 26 | * QUEUE_KEY_T can be defined to set the type of the primary key, which should | ||
| 27 | * be either a subtype of QUEUE_T if using structs, or QUEUE_T. | ||
| 28 | */ | ||
| 29 | |||
| 30 | #ifndef QUEUE_TEMPLATE_H | ||
| 31 | #define QUEUE_TEMPLATE_H | ||
| 32 | |||
| 33 | #include "support/debug.h" | ||
| 34 | |||
| 35 | #include <stdlib.h> | ||
| 36 | #include <string.h> | ||
| 37 | |||
| 38 | #define QUEUE_IMPL(word) QUEUE_COMB1(QUEUE_PREFIX,word) | ||
| 39 | #define QUEUE_COMB1(pre, word) QUEUE_COMB2(pre, word) | ||
| 40 | #define QUEUE_COMB2(pre, word) pre##word | ||
| 41 | |||
| 42 | #endif /* QUEUE_TEMPLATE_H */ | ||
| 43 | |||
| 44 | #ifndef QUEUE_T | ||
| 45 | #error "QUEUE_T must be defined" | ||
| 46 | #endif | ||
| 47 | |||
| 48 | #ifndef QUEUE_SIZE | ||
| 49 | #error "QUEUE_SIZE must be defined" | ||
| 50 | #endif | ||
| 51 | |||
| 52 | #ifndef QUEUE_KEY_T | ||
| 53 | #define QUEUE_KEY_T QUEUE_T | ||
| 54 | #endif | ||
| 55 | |||
| 56 | #define QUEUE_NAME QUEUE_COMB1(QUEUE_COMB1(queue,_), QUEUE_T) | ||
| 57 | #define QUEUE_PREFIX QUEUE_COMB1(QUEUE_NAME, _) | ||
| 58 | |||
| 59 | #define QUEUE_init QUEUE_IMPL(init) | ||
| 60 | #define QUEUE_clear QUEUE_IMPL(clear) | ||
| 61 | #define QUEUE_size QUEUE_IMPL(size) | ||
| 62 | #define QUEUE_empty QUEUE_IMPL(empty) | ||
| 63 | #define QUEUE_front QUEUE_IMPL(front) | ||
| 64 | #define QUEUE_back QUEUE_IMPL(back) | ||
| 65 | #define QUEUE_next QUEUE_IMPL(next) | ||
| 66 | #define QUEUE_enqueue QUEUE_IMPL(enqueue) | ||
| 67 | #define QUEUE_dequeue QUEUE_IMPL(dequeue) | ||
| 68 | #define QUEUE_delete QUEUE_IMPL(delete) | ||
| 69 | #define QUEUE_remove QUEUE_IMPL(remove) | ||
| 70 | #define QUEUE_replace QUEUE_IMPL(replace) | ||
| 71 | #define QUEUE_search QUEUE_IMPL(search) | ||
| 72 | |||
| 73 | /* Qeue template: | ||
| 74 | * - items is actually QUEUE_SIZE + 1 because we don't save rear, but next. FIXME | ||
| 75 | * (it simplifies some functions a little bit) | ||
| 76 | * - 'front' points to the first element | ||
| 77 | * - 'next' points to the next spot where to push | ||
| 78 | */ | ||
| 79 | |||
| 80 | typedef struct QUEUE_NAME { | ||
| 81 | QUEUE_T items[QUEUE_SIZE]; | ||
| 82 | size_t front; /* position to the first element */ | ||
| 83 | size_t next; /* position to the last empty spot */ | ||
| 84 | size_t capacity; | ||
| 85 | } QUEUE_NAME; | ||
| 86 | |||
| 87 | |||
| 88 | /* Initializers */ | ||
| 89 | |||
| 90 | 1124 | static inline void QUEUE_init(QUEUE_NAME *queue) { | |
| 91 | 1124 | *queue = (const QUEUE_NAME) { | |
| 92 | .capacity = QUEUE_SIZE, /* mainly for debugging */ | ||
| 93 | }; | ||
| 94 | 1124 | } | |
| 95 | |||
| 96 | 460 | static inline void QUEUE_clear(QUEUE_NAME *queue) { | |
| 97 | 460 | queue->front = 0; | |
| 98 | 460 | queue->next = 0; | |
| 99 | 460 | } | |
| 100 | |||
| 101 | |||
| 102 | /* Capacity */ | ||
| 103 | |||
| 104 | 318 | static inline size_t QUEUE_size(const QUEUE_NAME *queue) { | |
| 105 | 318 | return queue->next >= queue->front | |
| 106 | 318 | ? queue->next - queue->front | |
| 107 |
1/2✓ Branch 0 taken 159 times.
✗ Branch 1 not taken.
|
318 | : QUEUE_SIZE - queue->front + queue->next; |
| 108 | } | ||
| 109 | |||
| 110 | 850 | static inline bool QUEUE_empty(const QUEUE_NAME *queue) { | |
| 111 | 850 | return queue->front == queue->next; | |
| 112 | } | ||
| 113 | |||
| 114 | |||
| 115 | /* Element access */ | ||
| 116 | |||
| 117 | 76 | static inline QUEUE_T* QUEUE_front(QUEUE_NAME *queue) { | |
| 118 |
2/2✓ Branch 1 taken 15 times.
✓ Branch 2 taken 23 times.
|
76 | return QUEUE_empty(queue) ? NULL : &queue->items[queue->front]; |
| 119 | } | ||
| 120 | |||
| 121 | static inline QUEUE_T* QUEUE_back(QUEUE_NAME *queue) { | ||
| 122 | size_t rear = queue->next > 0 ? queue->next-1 : QUEUE_SIZE-1; | ||
| 123 | return QUEUE_empty(queue) ? NULL : &queue->items[rear]; | ||
| 124 | } | ||
| 125 | |||
| 126 | 32 | static inline QUEUE_T* QUEUE_next(QUEUE_NAME *queue, QUEUE_T *item) { | |
| 127 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 16 times.
|
32 | if (QUEUE_empty(queue) ) { |
| 128 | ✗ | return NULL; | |
| 129 | } | ||
| 130 |
1/2✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
|
32 | else if (queue->next > queue->front) { |
| 131 | /* queue is linear */ | ||
| 132 | 32 | size_t next_index = item + 1 - queue->items; | |
| 133 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 15 times.
|
32 | return next_index < queue->next ? item + 1 : NULL; |
| 134 | } | ||
| 135 | else { | ||
| 136 | /* queue is circular */ | ||
| 137 | ✗ | size_t next_index = item + 1 < queue->items + QUEUE_SIZE | |
| 138 | ✗ | ? item + 1 - queue->items | |
| 139 | ✗ | : 0; | |
| 140 | ✗ | return next_index > queue->front || next_index < queue->next | |
| 141 | ✗ | ? &queue->items[next_index] : NULL; | |
| 142 | } | ||
| 143 | } | ||
| 144 | |||
| 145 | |||
| 146 | /* Modifiers */ | ||
| 147 | |||
| 148 | /* Enqueue item to the back of the queue */ | ||
| 149 | 10 | static inline int QUEUE_enqueue(QUEUE_NAME *queue, QUEUE_T item) { | |
| 150 | 10 | size_t new_next = (queue->next + 1) % QUEUE_SIZE; | |
| 151 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
|
10 | if (unlikely(new_next == queue->front)) { |
| 152 | ✗ | return -1; | |
| 153 | } | ||
| 154 | 10 | queue->items[queue->next] = item; | |
| 155 | 10 | queue->next = new_next; | |
| 156 | 10 | return 0; | |
| 157 | } | ||
| 158 | |||
| 159 | /* Dequeue item from the front of the queue */ | ||
| 160 | static inline int QUEUE_dequeue(QUEUE_NAME *queue, QUEUE_T *item) { | ||
| 161 | if (QUEUE_empty(queue)) { | ||
| 162 | return -1; | ||
| 163 | } | ||
| 164 | *item = queue->items[queue->front]; | ||
| 165 | queue->front = (queue->front + 1) % QUEUE_SIZE; | ||
| 166 | return 0; | ||
| 167 | } | ||
| 168 | |||
| 169 | /* Delete element pointed by argument */ | ||
| 170 | ✗ | static inline void QUEUE_delete(QUEUE_NAME *queue, const QUEUE_T *item) { | |
| 171 | ✗ | if (QUEUE_empty(queue)) { | |
| 172 | ✗ | return; | |
| 173 | } | ||
| 174 | |||
| 175 | ✗ | if (item == &queue->items[queue->front]) { | |
| 176 | /* item is first element, just advance front */ | ||
| 177 | ✗ | queue->front = (queue->front + 1) % QUEUE_SIZE; | |
| 178 | ✗ | return; | |
| 179 | } | ||
| 180 | |||
| 181 | ✗ | size_t array_index = item - queue->items; | |
| 182 | |||
| 183 | // FIXME: more efficient? | ||
| 184 | ✗ | if (unlikely( | |
| 185 | /* queue is linear */ | ||
| 186 | (queue->next > queue->front | ||
| 187 | && (array_index < queue->front || array_index >= queue->next)) | ||
| 188 | || | ||
| 189 | /* queue is circular */ | ||
| 190 | (queue->next <= queue->front | ||
| 191 | && (array_index >= queue->next && array_index < queue->front)) | ||
| 192 | )) { | ||
| 193 | /* out of bounds */ | ||
| 194 | ✗ | return; | |
| 195 | } | ||
| 196 | |||
| 197 | ✗ | size_t write_index = array_index; | |
| 198 | ✗ | for (size_t read_index = (array_index + 1) % QUEUE_SIZE; | |
| 199 | ✗ | read_index != queue->next; | |
| 200 | ✗ | read_index = (read_index + 1) % QUEUE_SIZE) { | |
| 201 | /* move items forward in the queue */ | ||
| 202 | ✗ | queue->items[write_index] = queue->items[read_index]; | |
| 203 | ✗ | write_index = (write_index + 1) % QUEUE_SIZE; | |
| 204 | } | ||
| 205 | ✗ | queue->next = write_index; | |
| 206 | } | ||
| 207 | |||
| 208 | /* Remove all items that match with key */ | ||
| 209 | 184 | static inline void QUEUE_remove(QUEUE_NAME *queue, QUEUE_KEY_T key) { | |
| 210 | |||
| 211 | /* advance front for every first item that matches key */ | ||
| 212 | 187 | while (!QUEUE_empty(queue) | |
| 213 | 187 | && memcmp(&queue->items[queue->front], &key, sizeof(QUEUE_KEY_T)) == 0) { | |
| 214 | 3 | queue->front = (queue->front + 1) % QUEUE_SIZE; | |
| 215 | } | ||
| 216 | |||
| 217 | 184 | if (QUEUE_empty(queue)) { | |
| 218 | 181 | return; | |
| 219 | } | ||
| 220 | |||
| 221 | /* front does not match, iterate from 2nd item */ | ||
| 222 | 3 | size_t write_index = (queue->front + 1) % QUEUE_SIZE; | |
| 223 | 3 | for (size_t read_index = write_index; | |
| 224 | 4 | read_index != queue->next; | |
| 225 | 1 | read_index = (read_index + 1) % QUEUE_SIZE) { | |
| 226 | 1 | if (read_index != write_index) { | |
| 227 | /* move items forward in the queue */ | ||
| 228 | ✗ | queue->items[write_index] = queue->items[read_index]; | |
| 229 | } | ||
| 230 | 1 | if (memcmp(&queue->items[read_index], &key, sizeof(QUEUE_KEY_T)) != 0) { | |
| 231 | /* write_index only advances when element is not to be removed */ | ||
| 232 | ✗ | write_index = (write_index + 1) % QUEUE_SIZE; | |
| 233 | } | ||
| 234 | } | ||
| 235 | 3 | queue->next = write_index; | |
| 236 | } | ||
| 237 | |||
| 238 | /* Replace the first item that matches by key */ | ||
| 239 | static inline void QUEUE_replace(QUEUE_NAME *queue, QUEUE_T item) { | ||
| 240 | for (size_t index = queue->front; | ||
| 241 | index != queue->next; | ||
| 242 | index = (index + 1) % QUEUE_SIZE) { | ||
| 243 | if (memcmp(&queue->items[index], &item, sizeof(QUEUE_KEY_T)) == 0) { | ||
| 244 | queue->items[index] = item; | ||
| 245 | return; | ||
| 246 | } | ||
| 247 | } | ||
| 248 | } | ||
| 249 | |||
| 250 | /* Return reference to the first item that matches by key */ | ||
| 251 | static inline QUEUE_T* QUEUE_search(QUEUE_NAME *queue, QUEUE_KEY_T key) { | ||
| 252 | for (size_t index = queue->front; | ||
| 253 | index != queue->next; | ||
| 254 | index = (index + 1) % QUEUE_SIZE) { | ||
| 255 | if (memcmp(&queue->items[index], &key, sizeof(QUEUE_KEY_T)) == 0) { | ||
| 256 | return &queue->items[index]; | ||
| 257 | } | ||
| 258 | } | ||
| 259 | return NULL; | ||
| 260 | } | ||
| 261 | |||
| 262 | #undef QUEUE_T | ||
| 263 | #undef QUEUE_SIZE | ||
| 264 | #undef QUEUE_KEY_T | ||
| 265 | #undef QUEUE_PREFIX | ||
| 266 | #undef QUEUE_NAME | ||
| 267 | #undef QUEUE_init | ||
| 268 | #undef QUEUE_clear | ||
| 269 | #undef QUEUE_size | ||
| 270 | #undef QUEUE_empty | ||
| 271 | #undef QUEUE_front | ||
| 272 | #undef QUEUE_back | ||
| 273 | #undef QUEUE_next | ||
| 274 | #undef QUEUE_enqueue | ||
| 275 | #undef QUEUE_dequeue | ||
| 276 | #undef QUEUE_delete | ||
| 277 | #undef QUEUE_remove | ||
| 278 | #undef QUEUE_replace | ||
| 279 | #undef QUEUE_search | ||
| 280 |