1#ifndef JEMALLOC_INTERNAL_QR_H
2#define JEMALLOC_INTERNAL_QR_H
3
4/*
5 * A ring implementation based on an embedded circular doubly-linked list.
6 *
7 * You define your struct like so:
8 *
9 * typedef struct my_s my_t;
10 * struct my_s {
11 * int data;
12 * qr(my_t) my_link;
13 * };
14 *
15 * And then pass a my_t * into macros for a_qr arguments, and the token
16 * "my_link" into a_field fields.
17 */
18
19/* Ring definitions. */
20#define qr(a_type) \
21struct { \
22 a_type *qre_next; \
23 a_type *qre_prev; \
24}
25
26/*
27 * Initialize a qr link. Every link must be initialized before being used, even
28 * if that initialization is going to be immediately overwritten (say, by being
29 * passed into an insertion macro).
30 */
31#define qr_new(a_qr, a_field) do { \
32 (a_qr)->a_field.qre_next = (a_qr); \
33 (a_qr)->a_field.qre_prev = (a_qr); \
34} while (0)
35
36/*
37 * Go forwards or backwards in the ring. Note that (the ring being circular), this
38 * always succeeds -- you just keep looping around and around the ring if you
39 * chase pointers without end.
40 */
41#define qr_next(a_qr, a_field) ((a_qr)->a_field.qre_next)
42#define qr_prev(a_qr, a_field) ((a_qr)->a_field.qre_prev)
43
44/*
45 * Given two rings:
46 * a -> a_1 -> ... -> a_n --
47 * ^ |
48 * |------------------------
49 *
50 * b -> b_1 -> ... -> b_n --
51 * ^ |
52 * |------------------------
53 *
54 * Results in the ring:
55 * a -> a_1 -> ... -> a_n -> b -> b_1 -> ... -> b_n --
56 * ^ |
57 * |-------------------------------------------------|
58 *
59 * a_qr_a can directly be a qr_next() macro, but a_qr_b cannot.
60 */
61#define qr_meld(a_qr_a, a_qr_b, a_field) do { \
62 (a_qr_b)->a_field.qre_prev->a_field.qre_next = \
63 (a_qr_a)->a_field.qre_prev; \
64 (a_qr_a)->a_field.qre_prev = (a_qr_b)->a_field.qre_prev; \
65 (a_qr_b)->a_field.qre_prev = \
66 (a_qr_b)->a_field.qre_prev->a_field.qre_next; \
67 (a_qr_a)->a_field.qre_prev->a_field.qre_next = (a_qr_a); \
68 (a_qr_b)->a_field.qre_prev->a_field.qre_next = (a_qr_b); \
69} while (0)
70
71/*
72 * Logically, this is just a meld. The intent, though, is that a_qrelm is a
73 * single-element ring, so that "before" has a more obvious interpretation than
74 * meld.
75 */
76#define qr_before_insert(a_qrelm, a_qr, a_field) \
77 qr_meld((a_qrelm), (a_qr), a_field)
78
79/* Ditto, but inserting after rather than before. */
80#define qr_after_insert(a_qrelm, a_qr, a_field) \
81 qr_before_insert(qr_next(a_qrelm, a_field), (a_qr), a_field)
82
83/*
84 * Inverts meld; given the ring:
85 * a -> a_1 -> ... -> a_n -> b -> b_1 -> ... -> b_n --
86 * ^ |
87 * |-------------------------------------------------|
88 *
89 * Results in two rings:
90 * a -> a_1 -> ... -> a_n --
91 * ^ |
92 * |------------------------
93 *
94 * b -> b_1 -> ... -> b_n --
95 * ^ |
96 * |------------------------
97 *
98 * qr_meld() and qr_split() are functionally equivalent, so there's no need to
99 * have two copies of the code.
100 */
101#define qr_split(a_qr_a, a_qr_b, a_field) \
102 qr_meld((a_qr_a), (a_qr_b), a_field)
103
104/*
105 * Splits off a_qr from the rest of its ring, so that it becomes a
106 * single-element ring.
107 */
108#define qr_remove(a_qr, a_field) \
109 qr_split(qr_next(a_qr, a_field), (a_qr), a_field)
110
111/*
112 * Helper macro to iterate over each element in a ring exactly once, starting
113 * with a_qr. The usage is (assuming my_t defined as above):
114 *
115 * int sum(my_t *item) {
116 * int sum = 0;
117 * my_t *iter;
118 * qr_foreach(iter, item, link) {
119 * sum += iter->data;
120 * }
121 * return sum;
122 * }
123 */
124#define qr_foreach(var, a_qr, a_field) \
125 for ((var) = (a_qr); \
126 (var) != NULL; \
127 (var) = (((var)->a_field.qre_next != (a_qr)) \
128 ? (var)->a_field.qre_next : NULL))
129
130/*
131 * The same (and with the same usage) as qr_foreach, but in the opposite order,
132 * ending with a_qr.
133 */
134#define qr_reverse_foreach(var, a_qr, a_field) \
135 for ((var) = ((a_qr) != NULL) ? qr_prev(a_qr, a_field) : NULL; \
136 (var) != NULL; \
137 (var) = (((var) != (a_qr)) \
138 ? (var)->a_field.qre_prev : NULL))
139
140#endif /* JEMALLOC_INTERNAL_QR_H */
141