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