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