queue.c (5521B)
1 #include "queue.h" 2 3 #include "logger.h" 4 #include "memory.h" 5 6 typedef struct QueueItem { 7 struct QueueItem *next; 8 struct QueueItem *prev; 9 void *data; 10 } QueueItem; 11 12 b8 Queue_init(Queue *queue, u32 stride, u32 capacity) 13 { 14 if (!queue) 15 { 16 LOGE("Queue_init: Invalid queue pointer"); 17 return false; 18 } 19 20 queue->length = 0; 21 queue->stride = stride; 22 queue->stride_padded = 2 * sizeof(QueueItem *) + stride; 23 queue->capacity = capacity; 24 queue->cursor = NULL; 25 queue->head = NULL; 26 queue->tail = NULL; 27 queue->data = s_alloc(queue->stride_padded * capacity, MEMORY_TAG_QUEUE); 28 29 return true; 30 } 31 32 b8 Queue_free(Queue *queue) 33 { 34 if (queue) 35 { 36 s_free( 37 queue->data, 38 queue->stride_padded * queue->capacity, 39 MEMORY_TAG_QUEUE 40 ); 41 } 42 return true; 43 } 44 45 b8 Queue_empty(const Queue *queue) 46 { 47 return queue->length == 0; 48 } 49 50 b8 Queue_enqueue(Queue *queue, const void *value) 51 { 52 if (!queue) 53 { 54 LOGE("Queue_enqueue: Invalid queue pointer"); 55 return false; 56 } 57 if (!value) 58 { 59 LOGE("Queue_enqueue: Invalid value pointer"); 60 return false; 61 } 62 63 // Check queue is not full 64 if (queue->length == queue->capacity) 65 { 66 LOGE("Queue_enqueue: Can't enqueue value in full queue"); 67 return false; 68 } 69 70 // Find empty slot in queue memory 71 QueueItem *empty = NULL; 72 for (u32 i = 0; i < queue->capacity; i++) 73 { 74 if (queue->data + i * queue->stride_padded) continue; 75 76 empty = queue->data + i * queue->stride_padded; 77 } 78 79 // Fill empty slot 80 empty->next = NULL; 81 empty->prev = queue->tail; 82 s_copyMemory( 83 empty->data, 84 value, 85 queue->stride 86 ); 87 88 // Add to end of queue 89 if (queue->length == 0) 90 { 91 queue->head = empty; 92 queue->tail = empty; 93 } 94 else 95 { 96 queue->tail->next = empty; 97 queue->tail = empty; 98 } 99 100 queue->length += 1; 101 102 return true; 103 } 104 105 b8 Queue_dequeue(Queue *queue, void *value) 106 { 107 if (!queue) 108 { 109 LOGE("Queue_dequeue: Invalid queue pointer"); 110 return false; 111 } 112 if (!value) 113 { 114 LOGE("Queue_dequeue: Invalid value pointer"); 115 return false; 116 } 117 118 // Check queue is not empty 119 if (queue->length == 0) 120 { 121 LOGE("Queue_dequeue: Can't dequeue value from empty queue"); 122 return false; 123 } 124 125 // Set value 126 s_copyMemory(value, queue->head->data, queue->stride); 127 128 // Save reference for later 129 QueueItem *removed = queue->head; 130 131 // Remove from front of queue 132 if (queue->length == 1) 133 { 134 queue->head = NULL; 135 queue->tail = NULL; 136 } 137 else 138 { 139 queue->head = queue->head->next; 140 } 141 queue->length -= 1; 142 143 // Free memory used by item 144 s_zeroMemory(removed, queue->stride_padded); 145 146 return true; 147 } 148 149 b8 Queue_peek(const Queue *queue, void *value) 150 { 151 if (!queue) 152 { 153 LOGE("Queue_peek: Invalid queue pointer"); 154 return false; 155 } 156 if (!value) 157 { 158 LOGE("Queue_peek: Invalid value pointer"); 159 return false; 160 } 161 162 // Check queue is not empty 163 if (queue->length == 0) 164 { 165 LOGE("Queue_peek: Can't peek value from empty queue"); 166 return false; 167 } 168 169 // Set value 170 s_copyMemory(value, queue->head->data, queue->stride); 171 172 return true; 173 } 174 175 b8 Queue_peekNext(Queue *queue, void *value) 176 { 177 if (!queue) 178 { 179 LOGE("Queue_peekNext: Invalid queue pointer"); 180 return false; 181 } 182 if (!value) 183 { 184 LOGE("Queue_peekNext: Invalid value pointer"); 185 return false; 186 } 187 188 if (queue->length == 0) 189 { 190 LOGE("Queue_peekNext: Can't peek value from empty queue"); 191 return false; 192 } 193 194 // At beginning of queue 195 if (!queue->cursor) 196 { 197 queue->cursor = queue->head; 198 s_copyMemory(value, queue->cursor->data, queue->stride); 199 return true; 200 } 201 202 // In middle of queue 203 if (queue->cursor->next) 204 { 205 queue->cursor = queue->cursor->next; 206 s_copyMemory(value, queue->cursor->data, queue->stride); 207 return true; 208 } 209 210 // At end of queue 211 queue->cursor = NULL; 212 return false; 213 } 214 215 b8 Queue_peekDone(Queue *queue) 216 { 217 if (!queue) 218 { 219 LOGE("Queue_peekDone: Invalid queue pointer"); 220 return false; 221 } 222 223 queue->cursor = NULL; 224 225 return true; 226 } 227 228 b8 Queue_yank(Queue *queue, void *value) 229 { 230 if (!queue) 231 { 232 LOGE("Queue_yank: Invalid queue pointer"); 233 return false; 234 } 235 if (!value) 236 { 237 LOGE("Queue_yank: Invalid value pointer"); 238 return false; 239 } 240 241 // Check we're iterating through the queue 242 if (!queue->cursor) 243 { 244 LOGE("Queue_yank: Queue cursor is not set"); 245 return false; 246 } 247 248 // Set value 249 s_copyMemory(value, queue->cursor->data, queue->stride); 250 251 // Remove item from queue 252 if (queue->cursor->prev) 253 { 254 queue->cursor->prev->next = queue->cursor->next; 255 } 256 else 257 { 258 queue->head = queue->cursor->next; 259 } 260 261 if (queue->cursor->next) 262 263 { 264 queue->cursor->next->prev = queue->cursor->prev; 265 } 266 else 267 { 268 queue->tail = queue->cursor->prev; 269 } 270 queue->length -= 1; 271 272 // Free memory used by item 273 s_zeroMemory(queue->cursor, queue->stride_padded); 274 275 // Move cursor forward 276 queue->cursor = queue->cursor->next; 277 278 return true; 279 } 280