Last active
August 23, 2022 05:58
-
-
Save raylee/67fc4a1fdad447b3f76f4d557e180805 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Ray Lee 2022 August 22 ~ license CC0 | |
| #ifndef circular_queue_h | |
| #define circular_queue_h | |
| #include <stdint.h> | |
| #include <stddef.h> | |
| /* There are two ways a circular queue can deal with a request to enqueue | |
| items when it's full. Either we drop the request on the ground, or we | |
| overwrite old items in the back of the queue to make room for the new | |
| ones. Below enqueue(q, ...) implements the latter behavior. Check for | |
| queue_full(q) before enqueue for the former. | |
| The implementation below lets head and tail be free running. This lets | |
| us easily distinguish queue empty (head==tail) vs queue full, at the | |
| cost of always using a modulo operator to find the correct position in | |
| the backing array. Declaring circular queues of length 2^n is efficient. | |
| */ | |
| #define length_(arr) (sizeof(arr)/sizeof(arr[0])) | |
| #define queue(type, size) \ | |
| struct __queue_of_##size_##type { \ | |
| size_t head, tail; \ | |
| type entry[size]; \ | |
| } | |
| #define queue_count(q) ((q).tail-(q).head) | |
| #define queue_empty(q) (queue_count(q)==0) | |
| #define queue_full(q) (queue_count(q)==length_((q).entry)) | |
| #define queue_size(q) (length_((q).entry)) | |
| #define queue_free(q) (length_((q).entry)-queue_count(q)) | |
| #define enqueue(q, ...) \ | |
| do { \ | |
| __typeof__((q).entry[0]) args[] = {__VA_ARGS__}; \ | |
| for (int i_=0; i_<length_(args); i_++) { \ | |
| (q).entry[(q).tail++ % length_((q).entry)] = args[i_]; \ | |
| } \ | |
| if (queue_count(q) > length_((q).entry)) \ | |
| (q).head = (q).tail - length_((q).entry); \ | |
| } while (0) | |
| #define dequeue(q) ( queue_empty(q) ? NULL : &((q).entry[(q).head++ % length_((q).entry)]) ) | |
| #define queue_peek(q) ((q).entry[(q).head]) | |
| #endif |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // qtest.c | |
| #include <stdio.h> | |
| #include "queue.h" | |
| void queue_wrap_example() { | |
| queue(int, 10) q = {}; | |
| for (int i=0; i<38; i++) { | |
| enqueue(q, i); | |
| } | |
| while (!queue_empty(q)) { | |
| printf("%d\n", *dequeue(q)); | |
| } | |
| } | |
| typedef queue(char, 32) flight_recorder_t; | |
| void record(flight_recorder_t *fr, char *msg) { | |
| while (*msg) { | |
| enqueue(*fr, *msg++); | |
| } | |
| } | |
| void replay(flight_recorder_t *fr) { | |
| while (!queue_empty(*fr)) { | |
| printf("%c", *dequeue(*fr)); | |
| } | |
| } | |
| void queue_string_example() { | |
| flight_recorder_t fr = {}; | |
| record(&fr, "Hello, world!"); | |
| record(&fr, " This is a test."); | |
| record(&fr, " 1234567890"); | |
| record(&fr, " huzzah!\n"); | |
| replay(&fr); | |
| } | |
| int main() { | |
| queue_wrap_example(); | |
| queue_string_example(); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment