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 | #ifndef NVIM_LIB_QUEUE_H |
21 | #define NVIM_LIB_QUEUE_H |
22 | |
23 | #include <stddef.h> |
24 | |
25 | #include "nvim/func_attr.h" |
26 | |
27 | typedef struct _queue { |
28 | struct _queue *next; |
29 | struct _queue *prev; |
30 | } QUEUE; |
31 | |
32 | // Public macros. |
33 | #define QUEUE_DATA(ptr, type, field) \ |
34 | ((type *)((char *)(ptr) - offsetof(type, field))) |
35 | |
36 | // Important note: mutating the list while QUEUE_FOREACH is |
37 | // iterating over its elements results in undefined behavior. |
38 | #define QUEUE_FOREACH(q, h) \ |
39 | for ( /* NOLINT(readability/braces) */ \ |
40 | (q) = (h)->next; (q) != (h); (q) = (q)->next) |
41 | |
42 | // ffi.cdef is unable to swallow `bool` in place of `int` here. |
43 | static inline int QUEUE_EMPTY(const QUEUE *const q) |
44 | FUNC_ATTR_ALWAYS_INLINE FUNC_ATTR_PURE FUNC_ATTR_WARN_UNUSED_RESULT |
45 | { |
46 | return q == q->next; |
47 | } |
48 | |
49 | #define QUEUE_HEAD(q) (q)->next |
50 | |
51 | static inline void QUEUE_INIT(QUEUE *const q) FUNC_ATTR_ALWAYS_INLINE |
52 | { |
53 | q->next = q; |
54 | q->prev = q; |
55 | } |
56 | |
57 | static inline void QUEUE_ADD(QUEUE *const h, QUEUE *const n) |
58 | FUNC_ATTR_ALWAYS_INLINE |
59 | { |
60 | h->prev->next = n->next; |
61 | n->next->prev = h->prev; |
62 | h->prev = n->prev; |
63 | h->prev->next = h; |
64 | } |
65 | |
66 | static inline void QUEUE_INSERT_HEAD(QUEUE *const h, QUEUE *const q) |
67 | FUNC_ATTR_ALWAYS_INLINE |
68 | { |
69 | q->next = h->next; |
70 | q->prev = h; |
71 | q->next->prev = q; |
72 | h->next = q; |
73 | } |
74 | |
75 | static inline void QUEUE_INSERT_TAIL(QUEUE *const h, QUEUE *const q) |
76 | FUNC_ATTR_ALWAYS_INLINE |
77 | { |
78 | q->next = h; |
79 | q->prev = h->prev; |
80 | q->prev->next = q; |
81 | h->prev = q; |
82 | } |
83 | |
84 | static inline void QUEUE_REMOVE(QUEUE *const q) FUNC_ATTR_ALWAYS_INLINE |
85 | { |
86 | q->prev->next = q->next; |
87 | q->next->prev = q->prev; |
88 | } |
89 | |
90 | #endif // NVIM_LIB_QUEUE_H |
91 | |