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
27typedef 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.
43static 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
51static inline void QUEUE_INIT(QUEUE *const q) FUNC_ATTR_ALWAYS_INLINE
52{
53 q->next = q;
54 q->prev = q;
55}
56
57static 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
66static 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
75static 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
84static 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