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: 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)
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)
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)
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)
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
#define FUNC_ATTR_WARN_UNUSED_RESULT
Definition: func_attr.h:235
#define FUNC_ATTR_PURE
Definition: func_attr.h:233
Definition: queue.h:27
struct _queue * next
Definition: queue.h:28
struct _queue QUEUE
static char size_t n
Definition: memline.c:3251
struct _queue * prev
Definition: queue.h:29
#define FUNC_ATTR_ALWAYS_INLINE
Definition: func_attr.h:236