queue.h
Go to the documentation of this file.
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 <[email protected]>
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: the node currently being processed can be safely deleted.
37 // otherwise, mutating the list while QUEUE_FOREACH is iterating over its
38 // elements results in undefined behavior.
39 #define QUEUE_FOREACH(q, h, code) \
40  (q) = (h)->next; \
41  while ((q) != (h)) { \
42  QUEUE *next = q->next; \
43  code \
44  (q) = next; \
45  }
46 
47 
48 // ffi.cdef is unable to swallow `bool` in place of `int` here.
49 static inline int QUEUE_EMPTY(const QUEUE *const q)
51 {
52  return q == q->next;
53 }
54 
55 #define QUEUE_HEAD(q) (q)->next
56 
57 static inline void QUEUE_INIT(QUEUE *const q) FUNC_ATTR_ALWAYS_INLINE
58 {
59  q->next = q;
60  q->prev = q;
61 }
62 
63 static inline void QUEUE_ADD(QUEUE *const h, QUEUE *const n)
65 {
66  h->prev->next = n->next;
67  n->next->prev = h->prev;
68  h->prev = n->prev;
69  h->prev->next = h;
70 }
71 
72 static inline void QUEUE_INSERT_HEAD(QUEUE *const h, QUEUE *const q)
74 {
75  q->next = h->next;
76  q->prev = h;
77  q->next->prev = q;
78  h->next = q;
79 }
80 
81 static inline void QUEUE_INSERT_TAIL(QUEUE *const h, QUEUE *const q)
83 {
84  q->next = h;
85  q->prev = h->prev;
86  q->prev->next = q;
87  h->prev = q;
88 }
89 
90 static inline void QUEUE_REMOVE(QUEUE *const q) FUNC_ATTR_ALWAYS_INLINE
91 {
92  q->prev->next = q->next;
93  q->next->prev = q->prev;
94 }
95 
96 #endif // NVIM_LIB_QUEUE_H
_queue
Definition: queue.h:27
QUEUE
struct _queue QUEUE
n
int n
Definition: funcs.c:8562
FUNC_ATTR_WARN_UNUSED_RESULT
#define FUNC_ATTR_WARN_UNUSED_RESULT
Definition: func_attr.h:244
FUNC_ATTR_PURE
#define FUNC_ATTR_PURE
Definition: func_attr.h:242
_queue::prev
struct _queue * prev
Definition: queue.h:29
func_attr.h
FUNC_ATTR_ALWAYS_INLINE
#define FUNC_ATTR_ALWAYS_INLINE
Definition: func_attr.h:245
_queue::next
struct _queue * next
Definition: queue.h:28