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) \ |
31 | struct { \ |
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 | |