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