1#ifndef JEMALLOC_INTERNAL_QL_H
2#define JEMALLOC_INTERNAL_QL_H
3
4#include "jemalloc/internal/qr.h"
5
6/*
7 * A linked-list implementation.
8 *
9 * This is built on top of the ring implementation, but that can be viewed as an
10 * implementation detail (i.e. trying to advance past the tail of the list
11 * doesn't wrap around).
12 *
13 * You define a struct like so:
14 * typedef strucy my_s my_t;
15 * struct my_s {
16 * int data;
17 * ql_elm(my_t) my_link;
18 * };
19 *
20 * // We wobble between "list" and "head" for this type; we're now mostly
21 * // heading towards "list".
22 * typedef ql_head(my_t) my_list_t;
23 *
24 * You then pass a my_list_t * for a_head arguments, a my_t * for a_elm
25 * arguments, the token "my_link" for a_field arguments, and the token "my_t"
26 * for a_type arguments.
27 */
28
29/* List definitions. */
30#define ql_head(a_type) \
31struct { \
32 a_type *qlh_first; \
33}
34
35/* Static initializer for an empty list. */
36#define ql_head_initializer(a_head) {NULL}
37
38/* The field definition. */
39#define ql_elm(a_type) qr(a_type)
40
41/* A pointer to the first element in the list, or NULL if the list is empty. */
42#define ql_first(a_head) ((a_head)->qlh_first)
43
44/* Dynamically initializes a list. */
45#define ql_new(a_head) do { \
46 ql_first(a_head) = NULL; \
47} while (0)
48
49/*
50 * Sets dest to be the contents of src (overwriting any elements there), leaving
51 * src empty.
52 */
53#define ql_move(a_head_dest, a_head_src) do { \
54 ql_first(a_head_dest) = ql_first(a_head_src); \
55 ql_new(a_head_src); \
56} while (0)
57
58/* True if the list is empty, otherwise false. */
59#define ql_empty(a_head) (ql_first(a_head) == NULL)
60
61/*
62 * Initializes a ql_elm. Must be called even if the field is about to be
63 * overwritten.
64 */
65#define ql_elm_new(a_elm, a_field) qr_new((a_elm), a_field)
66
67/*
68 * Obtains the last item in the list.
69 */
70#define ql_last(a_head, a_field) \
71 (ql_empty(a_head) ? NULL : qr_prev(ql_first(a_head), a_field))
72
73/*
74 * Gets a pointer to the next/prev element in the list. Trying to advance past
75 * the end or retreat before the beginning of the list returns NULL.
76 */
77#define ql_next(a_head, a_elm, a_field) \
78 ((ql_last(a_head, a_field) != (a_elm)) \
79 ? qr_next((a_elm), a_field) : NULL)
80#define ql_prev(a_head, a_elm, a_field) \
81 ((ql_first(a_head) != (a_elm)) ? qr_prev((a_elm), a_field) \
82 : NULL)
83
84/* Inserts a_elm before a_qlelm in the list. */
85#define ql_before_insert(a_head, a_qlelm, a_elm, a_field) do { \
86 qr_before_insert((a_qlelm), (a_elm), a_field); \
87 if (ql_first(a_head) == (a_qlelm)) { \
88 ql_first(a_head) = (a_elm); \
89 } \
90} while (0)
91
92/* Inserts a_elm after a_qlelm in the list. */
93#define ql_after_insert(a_qlelm, a_elm, a_field) \
94 qr_after_insert((a_qlelm), (a_elm), a_field)
95
96/* Inserts a_elm as the first item in the list. */
97#define ql_head_insert(a_head, a_elm, a_field) do { \
98 if (!ql_empty(a_head)) { \
99 qr_before_insert(ql_first(a_head), (a_elm), a_field); \
100 } \
101 ql_first(a_head) = (a_elm); \
102} while (0)
103
104/* Inserts a_elm as the last item in the list. */
105#define ql_tail_insert(a_head, a_elm, a_field) do { \
106 if (!ql_empty(a_head)) { \
107 qr_before_insert(ql_first(a_head), (a_elm), a_field); \
108 } \
109 ql_first(a_head) = qr_next((a_elm), a_field); \
110} while (0)
111
112/*
113 * Given lists a = [a_1, ..., a_n] and [b_1, ..., b_n], results in:
114 * a = [a1, ..., a_n, b_1, ..., b_n] and b = [].
115 */
116#define ql_concat(a_head_a, a_head_b, a_field) do { \
117 if (ql_empty(a_head_a)) { \
118 ql_move(a_head_a, a_head_b); \
119 } else if (!ql_empty(a_head_b)) { \
120 qr_meld(ql_first(a_head_a), ql_first(a_head_b), \
121 a_field); \
122 ql_new(a_head_b); \
123 } \
124} while (0)
125
126/* Removes a_elm from the list. */
127#define ql_remove(a_head, a_elm, a_field) do { \
128 if (ql_first(a_head) == (a_elm)) { \
129 ql_first(a_head) = qr_next(ql_first(a_head), a_field); \
130 } \
131 if (ql_first(a_head) != (a_elm)) { \
132 qr_remove((a_elm), a_field); \
133 } else { \
134 ql_new(a_head); \
135 } \
136} while (0)
137
138/* Removes the first item in the list. */
139#define ql_head_remove(a_head, a_type, a_field) do { \
140 a_type *t = ql_first(a_head); \
141 ql_remove((a_head), t, a_field); \
142} while (0)
143
144/* Removes the last item in the list. */
145#define ql_tail_remove(a_head, a_type, a_field) do { \
146 a_type *t = ql_last(a_head, a_field); \
147 ql_remove((a_head), t, a_field); \
148} while (0)
149
150/*
151 * Given a = [a_1, a_2, ..., a_n-1, a_n, a_n+1, ...],
152 * ql_split(a, a_n, b, some_field) results in
153 * a = [a_1, a_2, ..., a_n-1]
154 * and replaces b's contents with:
155 * b = [a_n, a_n+1, ...]
156 */
157#define ql_split(a_head_a, a_elm, a_head_b, a_field) do { \
158 if (ql_first(a_head_a) == (a_elm)) { \
159 ql_move(a_head_b, a_head_a); \
160 } else { \
161 qr_split(ql_first(a_head_a), (a_elm), a_field); \
162 ql_first(a_head_b) = (a_elm); \
163 } \
164} while (0)
165
166/*
167 * An optimized version of:
168 * a_type *t = ql_first(a_head);
169 * ql_remove((a_head), t, a_field);
170 * ql_tail_insert((a_head), t, a_field);
171 */
172#define ql_rotate(a_head, a_field) do { \
173 ql_first(a_head) = qr_next(ql_first(a_head), a_field); \
174} while (0)
175
176/*
177 * Helper macro to iterate over each element in a list in order, starting from
178 * the head (or in reverse order, starting from the tail). The usage is
179 * (assuming my_t and my_list_t defined as above).
180 *
181 * int sum(my_list_t *list) {
182 * int sum = 0;
183 * my_t *iter;
184 * ql_foreach(iter, list, link) {
185 * sum += iter->data;
186 * }
187 * return sum;
188 * }
189 */
190
191#define ql_foreach(a_var, a_head, a_field) \
192 qr_foreach((a_var), ql_first(a_head), a_field)
193
194#define ql_reverse_foreach(a_var, a_head, a_field) \
195 qr_reverse_foreach((a_var), ql_first(a_head), a_field)
196
197#endif /* JEMALLOC_INTERNAL_QL_H */
198