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