]>
Commit | Line | Data |
---|---|---|
951f3164 JE |
1 | /* |
2 | * C macro implementation of treaps. | |
3 | * | |
4 | * Usage: | |
5 | * #include <stdint.h> | |
6 | * #include "trp.h" | |
7 | * trp_gen(...) | |
8 | * | |
9 | * Licensed under a two-clause BSD-style license. | |
10 | * See LICENSE for details. | |
11 | */ | |
12 | ||
13 | #ifndef TRP_H_ | |
14 | #define TRP_H_ | |
15 | ||
16 | #define MAYBE_UNUSED __attribute__((__unused__)) | |
17 | ||
18 | /* Node structure. */ | |
19 | struct trp_node { | |
20 | uint32_t trpn_left; | |
21 | uint32_t trpn_right; | |
22 | }; | |
23 | ||
24 | /* Root structure. */ | |
25 | struct trp_root { | |
26 | uint32_t trp_root; | |
27 | }; | |
28 | ||
29 | /* Pointer/Offset conversion. */ | |
30 | #define trpn_pointer(a_base, a_offset) (a_base##_pointer(a_offset)) | |
31 | #define trpn_offset(a_base, a_pointer) (a_base##_offset(a_pointer)) | |
32 | #define trpn_modify(a_base, a_offset) \ | |
33 | do { \ | |
34 | if ((a_offset) < a_base##_pool.committed) { \ | |
35 | uint32_t old_offset = (a_offset);\ | |
36 | (a_offset) = a_base##_alloc(1); \ | |
37 | *trpn_pointer(a_base, a_offset) = \ | |
38 | *trpn_pointer(a_base, old_offset); \ | |
39 | } \ | |
6ad263ce | 40 | } while (0) |
951f3164 JE |
41 | |
42 | /* Left accessors. */ | |
43 | #define trp_left_get(a_base, a_field, a_node) \ | |
44 | (trpn_pointer(a_base, a_node)->a_field.trpn_left) | |
45 | #define trp_left_set(a_base, a_field, a_node, a_left) \ | |
46 | do { \ | |
47 | trpn_modify(a_base, a_node); \ | |
48 | trp_left_get(a_base, a_field, a_node) = (a_left); \ | |
6ad263ce | 49 | } while (0) |
951f3164 JE |
50 | |
51 | /* Right accessors. */ | |
52 | #define trp_right_get(a_base, a_field, a_node) \ | |
53 | (trpn_pointer(a_base, a_node)->a_field.trpn_right) | |
54 | #define trp_right_set(a_base, a_field, a_node, a_right) \ | |
55 | do { \ | |
56 | trpn_modify(a_base, a_node); \ | |
57 | trp_right_get(a_base, a_field, a_node) = (a_right); \ | |
6ad263ce | 58 | } while (0) |
951f3164 JE |
59 | |
60 | /* | |
61 | * Fibonacci hash function. | |
62 | * The multiplier is the nearest prime to (2^32 times (√5 - 1)/2). | |
63 | * See Knuth §6.4: volume 3, 3rd ed, p518. | |
64 | */ | |
65 | #define trpn_hash(a_node) (uint32_t) (2654435761u * (a_node)) | |
66 | ||
67 | /* Priority accessors. */ | |
68 | #define trp_prio_get(a_node) trpn_hash(a_node) | |
69 | ||
70 | /* Node initializer. */ | |
71 | #define trp_node_new(a_base, a_field, a_node) \ | |
72 | do { \ | |
73 | trp_left_set(a_base, a_field, (a_node), ~0); \ | |
74 | trp_right_set(a_base, a_field, (a_node), ~0); \ | |
6ad263ce | 75 | } while (0) |
951f3164 JE |
76 | |
77 | /* Internal utility macros. */ | |
78 | #define trpn_first(a_base, a_field, a_root, r_node) \ | |
79 | do { \ | |
80 | (r_node) = (a_root); \ | |
81 | if ((r_node) == ~0) \ | |
82 | return NULL; \ | |
83 | while (~trp_left_get(a_base, a_field, (r_node))) \ | |
84 | (r_node) = trp_left_get(a_base, a_field, (r_node)); \ | |
85 | } while (0) | |
86 | ||
87 | #define trpn_rotate_left(a_base, a_field, a_node, r_node) \ | |
88 | do { \ | |
89 | (r_node) = trp_right_get(a_base, a_field, (a_node)); \ | |
90 | trp_right_set(a_base, a_field, (a_node), \ | |
91 | trp_left_get(a_base, a_field, (r_node))); \ | |
92 | trp_left_set(a_base, a_field, (r_node), (a_node)); \ | |
6ad263ce | 93 | } while (0) |
951f3164 JE |
94 | |
95 | #define trpn_rotate_right(a_base, a_field, a_node, r_node) \ | |
96 | do { \ | |
97 | (r_node) = trp_left_get(a_base, a_field, (a_node)); \ | |
98 | trp_left_set(a_base, a_field, (a_node), \ | |
99 | trp_right_get(a_base, a_field, (r_node))); \ | |
100 | trp_right_set(a_base, a_field, (r_node), (a_node)); \ | |
6ad263ce | 101 | } while (0) |
951f3164 JE |
102 | |
103 | #define trp_gen(a_attr, a_pre, a_type, a_field, a_base, a_cmp) \ | |
104 | a_attr a_type MAYBE_UNUSED *a_pre##first(struct trp_root *treap) \ | |
105 | { \ | |
106 | uint32_t ret; \ | |
107 | trpn_first(a_base, a_field, treap->trp_root, ret); \ | |
108 | return trpn_pointer(a_base, ret); \ | |
109 | } \ | |
110 | a_attr a_type MAYBE_UNUSED *a_pre##next(struct trp_root *treap, a_type *node) \ | |
111 | { \ | |
112 | uint32_t ret; \ | |
113 | uint32_t offset = trpn_offset(a_base, node); \ | |
114 | if (~trp_right_get(a_base, a_field, offset)) { \ | |
115 | trpn_first(a_base, a_field, \ | |
116 | trp_right_get(a_base, a_field, offset), ret); \ | |
117 | } else { \ | |
118 | uint32_t tnode = treap->trp_root; \ | |
119 | ret = ~0; \ | |
120 | while (1) { \ | |
121 | int cmp = (a_cmp)(trpn_pointer(a_base, offset), \ | |
122 | trpn_pointer(a_base, tnode)); \ | |
123 | if (cmp < 0) { \ | |
124 | ret = tnode; \ | |
125 | tnode = trp_left_get(a_base, a_field, tnode); \ | |
126 | } else if (cmp > 0) { \ | |
127 | tnode = trp_right_get(a_base, a_field, tnode); \ | |
128 | } else { \ | |
129 | break; \ | |
130 | } \ | |
131 | } \ | |
132 | } \ | |
133 | return trpn_pointer(a_base, ret); \ | |
134 | } \ | |
135 | a_attr a_type MAYBE_UNUSED *a_pre##search(struct trp_root *treap, a_type *key) \ | |
136 | { \ | |
137 | int cmp; \ | |
138 | uint32_t ret = treap->trp_root; \ | |
6ad263ce | 139 | while (~ret && (cmp = (a_cmp)(key, trpn_pointer(a_base, ret)))) { \ |
951f3164 JE |
140 | if (cmp < 0) { \ |
141 | ret = trp_left_get(a_base, a_field, ret); \ | |
142 | } else { \ | |
143 | ret = trp_right_get(a_base, a_field, ret); \ | |
144 | } \ | |
145 | } \ | |
146 | return trpn_pointer(a_base, ret); \ | |
147 | } \ | |
148 | a_attr a_type MAYBE_UNUSED *a_pre##nsearch(struct trp_root *treap, a_type *key) \ | |
149 | { \ | |
150 | int cmp; \ | |
151 | uint32_t ret = treap->trp_root; \ | |
6ad263ce | 152 | while (~ret && (cmp = (a_cmp)(key, trpn_pointer(a_base, ret)))) { \ |
951f3164 JE |
153 | if (cmp < 0) { \ |
154 | if (!~trp_left_get(a_base, a_field, ret)) \ | |
155 | break; \ | |
156 | ret = trp_left_get(a_base, a_field, ret); \ | |
157 | } else { \ | |
158 | ret = trp_right_get(a_base, a_field, ret); \ | |
159 | } \ | |
160 | } \ | |
161 | return trpn_pointer(a_base, ret); \ | |
162 | } \ | |
163 | a_attr uint32_t MAYBE_UNUSED a_pre##insert_recurse(uint32_t cur_node, uint32_t ins_node) \ | |
164 | { \ | |
165 | if (cur_node == ~0) { \ | |
6ad263ce | 166 | return ins_node; \ |
951f3164 JE |
167 | } else { \ |
168 | uint32_t ret; \ | |
169 | int cmp = (a_cmp)(trpn_pointer(a_base, ins_node), \ | |
170 | trpn_pointer(a_base, cur_node)); \ | |
171 | if (cmp < 0) { \ | |
172 | uint32_t left = a_pre##insert_recurse( \ | |
173 | trp_left_get(a_base, a_field, cur_node), ins_node); \ | |
174 | trp_left_set(a_base, a_field, cur_node, left); \ | |
175 | if (trp_prio_get(left) < trp_prio_get(cur_node)) \ | |
176 | trpn_rotate_right(a_base, a_field, cur_node, ret); \ | |
177 | else \ | |
178 | ret = cur_node; \ | |
179 | } else { \ | |
180 | uint32_t right = a_pre##insert_recurse( \ | |
181 | trp_right_get(a_base, a_field, cur_node), ins_node); \ | |
182 | trp_right_set(a_base, a_field, cur_node, right); \ | |
183 | if (trp_prio_get(right) < trp_prio_get(cur_node)) \ | |
184 | trpn_rotate_left(a_base, a_field, cur_node, ret); \ | |
185 | else \ | |
186 | ret = cur_node; \ | |
187 | } \ | |
6ad263ce | 188 | return ret; \ |
951f3164 JE |
189 | } \ |
190 | } \ | |
97a5e345 | 191 | a_attr a_type *MAYBE_UNUSED a_pre##insert(struct trp_root *treap, a_type *node) \ |
951f3164 JE |
192 | { \ |
193 | uint32_t offset = trpn_offset(a_base, node); \ | |
194 | trp_node_new(a_base, a_field, offset); \ | |
195 | treap->trp_root = a_pre##insert_recurse(treap->trp_root, offset); \ | |
97a5e345 | 196 | return trpn_pointer(a_base, offset); \ |
951f3164 JE |
197 | } \ |
198 | a_attr uint32_t MAYBE_UNUSED a_pre##remove_recurse(uint32_t cur_node, uint32_t rem_node) \ | |
199 | { \ | |
200 | int cmp = a_cmp(trpn_pointer(a_base, rem_node), \ | |
201 | trpn_pointer(a_base, cur_node)); \ | |
202 | if (cmp == 0) { \ | |
203 | uint32_t ret; \ | |
204 | uint32_t left = trp_left_get(a_base, a_field, cur_node); \ | |
205 | uint32_t right = trp_right_get(a_base, a_field, cur_node); \ | |
206 | if (left == ~0) { \ | |
207 | if (right == ~0) \ | |
6ad263ce | 208 | return ~0; \ |
951f3164 JE |
209 | } else if (right == ~0 || trp_prio_get(left) < trp_prio_get(right)) { \ |
210 | trpn_rotate_right(a_base, a_field, cur_node, ret); \ | |
211 | right = a_pre##remove_recurse(cur_node, rem_node); \ | |
212 | trp_right_set(a_base, a_field, ret, right); \ | |
6ad263ce | 213 | return ret; \ |
951f3164 JE |
214 | } \ |
215 | trpn_rotate_left(a_base, a_field, cur_node, ret); \ | |
216 | left = a_pre##remove_recurse(cur_node, rem_node); \ | |
217 | trp_left_set(a_base, a_field, ret, left); \ | |
6ad263ce | 218 | return ret; \ |
951f3164 JE |
219 | } else if (cmp < 0) { \ |
220 | uint32_t left = a_pre##remove_recurse( \ | |
221 | trp_left_get(a_base, a_field, cur_node), rem_node); \ | |
222 | trp_left_set(a_base, a_field, cur_node, left); \ | |
6ad263ce | 223 | return cur_node; \ |
951f3164 JE |
224 | } else { \ |
225 | uint32_t right = a_pre##remove_recurse( \ | |
226 | trp_right_get(a_base, a_field, cur_node), rem_node); \ | |
227 | trp_right_set(a_base, a_field, cur_node, right); \ | |
6ad263ce | 228 | return cur_node; \ |
951f3164 JE |
229 | } \ |
230 | } \ | |
231 | a_attr void MAYBE_UNUSED a_pre##remove(struct trp_root *treap, a_type *node) \ | |
232 | { \ | |
233 | treap->trp_root = a_pre##remove_recurse(treap->trp_root, \ | |
234 | trpn_offset(a_base, node)); \ | |
235 | } \ | |
236 | ||
237 | #endif |