queue_defs.h (2606B)
1 // Queue implemented by circularly-linked list. 2 // 3 // Adapted from libuv. Simpler and more efficient than klist.h for implementing 4 // queues that support arbitrary insertion/removal. 5 // 6 // Copyright (c) 2013, Ben Noordhuis <info@bnoordhuis.nl> 7 // 8 // Permission to use, copy, modify, and/or distribute this software for any 9 // purpose with or without fee is hereby granted, provided that the above 10 // copyright notice and this permission notice appear in all copies. 11 // 12 // THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 13 // WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 14 // MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 15 // ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 16 // WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 17 // ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 18 // OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 19 20 #pragma once 21 22 #include <stddef.h> 23 24 typedef struct queue { 25 struct queue *next; 26 struct queue *prev; 27 } QUEUE; 28 29 #include "lib/queue_defs.h.inline.generated.h" 30 31 // Public macros. 32 #define QUEUE_DATA(ptr, type, field) \ 33 ((type *)((char *)(ptr) - offsetof(type, field))) 34 35 // Important note: the node currently being processed can be safely deleted. 36 // otherwise, mutating the list while QUEUE_FOREACH is iterating over its 37 // elements results in undefined behavior. 38 #define QUEUE_FOREACH(q, h, code) \ 39 (q) = (h)->next; \ 40 while ((q) != (h)) { \ 41 QUEUE *next = q->next; \ 42 code \ 43 (q) = next; \ 44 } 45 46 // ffi.cdef is unable to swallow `bool` in place of `int` here. 47 static inline int QUEUE_EMPTY(const QUEUE *const q) 48 FUNC_ATTR_ALWAYS_INLINE FUNC_ATTR_PURE FUNC_ATTR_WARN_UNUSED_RESULT 49 { 50 return q == q->next; 51 } 52 53 #define QUEUE_HEAD(q) (q)->next 54 55 static inline void QUEUE_INIT(QUEUE *const q) 56 FUNC_ATTR_ALWAYS_INLINE 57 { 58 q->next = q; 59 q->prev = q; 60 } 61 62 static inline void QUEUE_ADD(QUEUE *const h, QUEUE *const n) 63 FUNC_ATTR_ALWAYS_INLINE 64 { 65 h->prev->next = n->next; 66 n->next->prev = h->prev; 67 h->prev = n->prev; 68 h->prev->next = h; 69 } 70 71 static inline void QUEUE_INSERT_HEAD(QUEUE *const h, QUEUE *const q) 72 FUNC_ATTR_ALWAYS_INLINE 73 { 74 q->next = h->next; 75 q->prev = h; 76 q->next->prev = q; 77 h->next = q; 78 } 79 80 static inline void QUEUE_INSERT_TAIL(QUEUE *const h, QUEUE *const q) 81 FUNC_ATTR_ALWAYS_INLINE 82 { 83 q->next = h; 84 q->prev = h->prev; 85 q->prev->next = q; 86 h->prev = q; 87 } 88 89 static inline void QUEUE_REMOVE(QUEUE *const q) 90 FUNC_ATTR_ALWAYS_INLINE 91 { 92 q->prev->next = q->next; 93 q->next->prev = q->prev; 94 }