blob: f33eb86534d93e8086d40e15c968c850444733a0 [file] [log] [blame]
Willy Tarreauc2186022009-10-26 19:48:54 +01001/*
2 * Elastic Binary Trees - macros and structures for operations on 32bit nodes.
Willy Tarreauf3bfede2011-07-25 11:38:17 +02003 * Version 6.0.6
4 * (C) 2002-2011 - Willy Tarreau <w@1wt.eu>
Willy Tarreauc2186022009-10-26 19:48:54 +01005 *
Willy Tarreauf3bfede2011-07-25 11:38:17 +02006 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation, version 2.1
9 * exclusively.
Willy Tarreauc2186022009-10-26 19:48:54 +010010 *
Willy Tarreauf3bfede2011-07-25 11:38:17 +020011 * This library is distributed in the hope that it will be useful,
Willy Tarreauc2186022009-10-26 19:48:54 +010012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
Willy Tarreauf3bfede2011-07-25 11:38:17 +020013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
Willy Tarreauc2186022009-10-26 19:48:54 +010015 *
Willy Tarreauf3bfede2011-07-25 11:38:17 +020016 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
Willy Tarreauc2186022009-10-26 19:48:54 +010019 */
20
21#ifndef _EB32TREE_H
22#define _EB32TREE_H
23
24#include "ebtree.h"
25
26
27/* Return the structure of type <type> whose member <member> points to <ptr> */
28#define eb32_entry(ptr, type, member) container_of(ptr, type, member)
29
30#define EB32_ROOT EB_ROOT
31#define EB32_TREE_HEAD EB_TREE_HEAD
32
33/* These types may sometimes already be defined */
34typedef unsigned int u32;
35typedef signed int s32;
36
37/* This structure carries a node, a leaf, and a key. It must start with the
38 * eb_node so that it can be cast into an eb_node. We could also have put some
39 * sort of transparent union here to reduce the indirection level, but the fact
40 * is, the end user is not meant to manipulate internals, so this is pointless.
41 */
42struct eb32_node {
43 struct eb_node node; /* the tree node, must be at the beginning */
44 u32 key;
45};
46
47/*
48 * Exported functions and macros.
49 * Many of them are always inlined because they are extremely small, and
50 * are generally called at most once or twice in a program.
51 */
52
53/* Return leftmost node in the tree, or NULL if none */
54static inline struct eb32_node *eb32_first(struct eb_root *root)
55{
56 return eb32_entry(eb_first(root), struct eb32_node, node);
57}
58
59/* Return rightmost node in the tree, or NULL if none */
60static inline struct eb32_node *eb32_last(struct eb_root *root)
61{
62 return eb32_entry(eb_last(root), struct eb32_node, node);
63}
64
65/* Return next node in the tree, or NULL if none */
66static inline struct eb32_node *eb32_next(struct eb32_node *eb32)
67{
68 return eb32_entry(eb_next(&eb32->node), struct eb32_node, node);
69}
70
71/* Return previous node in the tree, or NULL if none */
72static inline struct eb32_node *eb32_prev(struct eb32_node *eb32)
73{
74 return eb32_entry(eb_prev(&eb32->node), struct eb32_node, node);
75}
76
Willy Tarreau2b570202013-05-07 15:58:28 +020077/* Return next leaf node within a duplicate sub-tree, or NULL if none. */
78static inline struct eb32_node *eb32_next_dup(struct eb32_node *eb32)
79{
80 return eb32_entry(eb_next_dup(&eb32->node), struct eb32_node, node);
81}
82
83/* Return previous leaf node within a duplicate sub-tree, or NULL if none. */
84static inline struct eb32_node *eb32_prev_dup(struct eb32_node *eb32)
85{
86 return eb32_entry(eb_prev_dup(&eb32->node), struct eb32_node, node);
87}
88
Willy Tarreauc2186022009-10-26 19:48:54 +010089/* Return next node in the tree, skipping duplicates, or NULL if none */
90static inline struct eb32_node *eb32_next_unique(struct eb32_node *eb32)
91{
92 return eb32_entry(eb_next_unique(&eb32->node), struct eb32_node, node);
93}
94
95/* Return previous node in the tree, skipping duplicates, or NULL if none */
96static inline struct eb32_node *eb32_prev_unique(struct eb32_node *eb32)
97{
98 return eb32_entry(eb_prev_unique(&eb32->node), struct eb32_node, node);
99}
100
101/* Delete node from the tree if it was linked in. Mark the node unused. Note
102 * that this function relies on a non-inlined generic function: eb_delete.
103 */
104static inline void eb32_delete(struct eb32_node *eb32)
105{
106 eb_delete(&eb32->node);
107}
108
109/*
110 * The following functions are not inlined by default. They are declared
111 * in eb32tree.c, which simply relies on their inline version.
112 */
113REGPRM2 struct eb32_node *eb32_lookup(struct eb_root *root, u32 x);
114REGPRM2 struct eb32_node *eb32i_lookup(struct eb_root *root, s32 x);
115REGPRM2 struct eb32_node *eb32_lookup_le(struct eb_root *root, u32 x);
116REGPRM2 struct eb32_node *eb32_lookup_ge(struct eb_root *root, u32 x);
117REGPRM2 struct eb32_node *eb32_insert(struct eb_root *root, struct eb32_node *new);
118REGPRM2 struct eb32_node *eb32i_insert(struct eb_root *root, struct eb32_node *new);
119
120/*
121 * The following functions are less likely to be used directly, because their
122 * code is larger. The non-inlined version is preferred.
123 */
124
125/* Delete node from the tree if it was linked in. Mark the node unused. */
126static forceinline void __eb32_delete(struct eb32_node *eb32)
127{
128 __eb_delete(&eb32->node);
129}
130
131/*
132 * Find the first occurence of a key in the tree <root>. If none can be
133 * found, return NULL.
134 */
135static forceinline struct eb32_node *__eb32_lookup(struct eb_root *root, u32 x)
136{
137 struct eb32_node *node;
138 eb_troot_t *troot;
139 u32 y;
Willy Tarreau3a932442010-05-09 19:29:23 +0200140 int node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100141
142 troot = root->b[EB_LEFT];
143 if (unlikely(troot == NULL))
144 return NULL;
145
146 while (1) {
147 if ((eb_gettag(troot) == EB_LEAF)) {
148 node = container_of(eb_untag(troot, EB_LEAF),
149 struct eb32_node, node.branches);
150 if (node->key == x)
151 return node;
152 else
153 return NULL;
154 }
155 node = container_of(eb_untag(troot, EB_NODE),
156 struct eb32_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200157 node_bit = node->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100158
159 y = node->key ^ x;
160 if (!y) {
161 /* Either we found the node which holds the key, or
162 * we have a dup tree. In the later case, we have to
163 * walk it down left to get the first entry.
164 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200165 if (node_bit < 0) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100166 troot = node->node.branches.b[EB_LEFT];
167 while (eb_gettag(troot) != EB_LEAF)
168 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
169 node = container_of(eb_untag(troot, EB_LEAF),
170 struct eb32_node, node.branches);
171 }
172 return node;
173 }
174
Willy Tarreau3a932442010-05-09 19:29:23 +0200175 if ((y >> node_bit) >= EB_NODE_BRANCHES)
Willy Tarreauc2186022009-10-26 19:48:54 +0100176 return NULL; /* no more common bits */
177
Willy Tarreau3a932442010-05-09 19:29:23 +0200178 troot = node->node.branches.b[(x >> node_bit) & EB_NODE_BRANCH_MASK];
Willy Tarreauc2186022009-10-26 19:48:54 +0100179 }
180}
181
182/*
183 * Find the first occurence of a signed key in the tree <root>. If none can
184 * be found, return NULL.
185 */
186static forceinline struct eb32_node *__eb32i_lookup(struct eb_root *root, s32 x)
187{
188 struct eb32_node *node;
189 eb_troot_t *troot;
190 u32 key = x ^ 0x80000000;
191 u32 y;
Willy Tarreau3a932442010-05-09 19:29:23 +0200192 int node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100193
194 troot = root->b[EB_LEFT];
195 if (unlikely(troot == NULL))
196 return NULL;
197
198 while (1) {
199 if ((eb_gettag(troot) == EB_LEAF)) {
200 node = container_of(eb_untag(troot, EB_LEAF),
201 struct eb32_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200202 if (node->key == (u32)x)
Willy Tarreauc2186022009-10-26 19:48:54 +0100203 return node;
204 else
205 return NULL;
206 }
207 node = container_of(eb_untag(troot, EB_NODE),
208 struct eb32_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200209 node_bit = node->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100210
211 y = node->key ^ x;
212 if (!y) {
213 /* Either we found the node which holds the key, or
214 * we have a dup tree. In the later case, we have to
215 * walk it down left to get the first entry.
216 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200217 if (node_bit < 0) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100218 troot = node->node.branches.b[EB_LEFT];
219 while (eb_gettag(troot) != EB_LEAF)
220 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
221 node = container_of(eb_untag(troot, EB_LEAF),
222 struct eb32_node, node.branches);
223 }
224 return node;
225 }
226
Willy Tarreau3a932442010-05-09 19:29:23 +0200227 if ((y >> node_bit) >= EB_NODE_BRANCHES)
Willy Tarreauc2186022009-10-26 19:48:54 +0100228 return NULL; /* no more common bits */
229
Willy Tarreau3a932442010-05-09 19:29:23 +0200230 troot = node->node.branches.b[(key >> node_bit) & EB_NODE_BRANCH_MASK];
Willy Tarreauc2186022009-10-26 19:48:54 +0100231 }
232}
233
234/* Insert eb32_node <new> into subtree starting at node root <root>.
235 * Only new->key needs be set with the key. The eb32_node is returned.
236 * If root->b[EB_RGHT]==1, the tree may only contain unique keys.
237 */
238static forceinline struct eb32_node *
239__eb32_insert(struct eb_root *root, struct eb32_node *new) {
240 struct eb32_node *old;
241 unsigned int side;
Willy Tarreau3a932442010-05-09 19:29:23 +0200242 eb_troot_t *troot, **up_ptr;
Willy Tarreauc2186022009-10-26 19:48:54 +0100243 u32 newkey; /* caching the key saves approximately one cycle */
Willy Tarreau6258f7b2011-09-19 20:48:00 +0200244 eb_troot_t *root_right;
Willy Tarreau3a932442010-05-09 19:29:23 +0200245 eb_troot_t *new_left, *new_rght;
246 eb_troot_t *new_leaf;
247 int old_node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100248
249 side = EB_LEFT;
250 troot = root->b[EB_LEFT];
251 root_right = root->b[EB_RGHT];
252 if (unlikely(troot == NULL)) {
253 /* Tree is empty, insert the leaf part below the left branch */
254 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
255 new->node.leaf_p = eb_dotag(root, EB_LEFT);
256 new->node.node_p = NULL; /* node part unused */
257 return new;
258 }
259
260 /* The tree descent is fairly easy :
261 * - first, check if we have reached a leaf node
262 * - second, check if we have gone too far
263 * - third, reiterate
264 * Everywhere, we use <new> for the node node we are inserting, <root>
265 * for the node we attach it to, and <old> for the node we are
266 * displacing below <new>. <troot> will always point to the future node
267 * (tagged with its type). <side> carries the side the node <new> is
268 * attached to below its parent, which is also where previous node
269 * was attached. <newkey> carries the key being inserted.
270 */
271 newkey = new->key;
272
273 while (1) {
Willy Tarreau3a932442010-05-09 19:29:23 +0200274 if (eb_gettag(troot) == EB_LEAF) {
275 /* insert above a leaf */
Willy Tarreauc2186022009-10-26 19:48:54 +0100276 old = container_of(eb_untag(troot, EB_LEAF),
277 struct eb32_node, node.branches);
Willy Tarreauc2186022009-10-26 19:48:54 +0100278 new->node.node_p = old->node.leaf_p;
Willy Tarreau3a932442010-05-09 19:29:23 +0200279 up_ptr = &old->node.leaf_p;
Willy Tarreauc2186022009-10-26 19:48:54 +0100280 break;
281 }
282
283 /* OK we're walking down this link */
284 old = container_of(eb_untag(troot, EB_NODE),
285 struct eb32_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200286 old_node_bit = old->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100287
288 /* Stop going down when we don't have common bits anymore. We
289 * also stop in front of a duplicates tree because it means we
290 * have to insert above.
291 */
292
Willy Tarreau3a932442010-05-09 19:29:23 +0200293 if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
294 (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100295 /* The tree did not contain the key, so we insert <new> before the node
296 * <old>, and set ->bit to designate the lowest bit position in <new>
297 * which applies to ->branches.b[].
298 */
Willy Tarreauc2186022009-10-26 19:48:54 +0100299 new->node.node_p = old->node.node_p;
Willy Tarreau3a932442010-05-09 19:29:23 +0200300 up_ptr = &old->node.node_p;
Willy Tarreauc2186022009-10-26 19:48:54 +0100301 break;
302 }
303
304 /* walk down */
305 root = &old->node.branches;
Willy Tarreau3a932442010-05-09 19:29:23 +0200306 side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;
Willy Tarreauc2186022009-10-26 19:48:54 +0100307 troot = root->b[side];
308 }
309
Willy Tarreau3a932442010-05-09 19:29:23 +0200310 new_left = eb_dotag(&new->node.branches, EB_LEFT);
311 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
312 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
Willy Tarreauc2186022009-10-26 19:48:54 +0100313
314 /* We need the common higher bits between new->key and old->key.
315 * What differences are there between new->key and the node here ?
316 * NOTE that bit(new) is always < bit(root) because highest
317 * bit of new->key and old->key are identical here (otherwise they
318 * would sit on different branches).
319 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200320
Willy Tarreauc2186022009-10-26 19:48:54 +0100321 // note that if EB_NODE_BITS > 1, we should check that it's still >= 0
322 new->node.bit = flsnz(new->key ^ old->key) - EB_NODE_BITS;
Willy Tarreau3a932442010-05-09 19:29:23 +0200323
324 if (new->key == old->key) {
325 new->node.bit = -1; /* mark as new dup tree, just in case */
326
327 if (likely(eb_gettag(root_right))) {
328 /* we refuse to duplicate this key if the tree is
329 * tagged as containing only unique keys.
330 */
331 return old;
332 }
333
334 if (eb_gettag(troot) != EB_LEAF) {
335 /* there was already a dup tree below */
336 struct eb_node *ret;
337 ret = eb_insert_dup(&old->node, &new->node);
338 return container_of(ret, struct eb32_node, node);
339 }
340 /* otherwise fall through */
341 }
Willy Tarreauc2186022009-10-26 19:48:54 +0100342
Willy Tarreau3a932442010-05-09 19:29:23 +0200343 if (new->key >= old->key) {
344 new->node.branches.b[EB_LEFT] = troot;
345 new->node.branches.b[EB_RGHT] = new_leaf;
346 new->node.leaf_p = new_rght;
347 *up_ptr = new_left;
348 }
349 else {
350 new->node.branches.b[EB_LEFT] = new_leaf;
351 new->node.branches.b[EB_RGHT] = troot;
352 new->node.leaf_p = new_left;
353 *up_ptr = new_rght;
354 }
355
356 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
357 * parent is already set to <new>, and the <root>'s branch is still in
358 * <side>. Update the root's leaf till we have it. Note that we can also
359 * find the side by checking the side of new->node.node_p.
360 */
361
362 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
Willy Tarreauc2186022009-10-26 19:48:54 +0100363 return new;
364}
365
366/* Insert eb32_node <new> into subtree starting at node root <root>, using
367 * signed keys. Only new->key needs be set with the key. The eb32_node
368 * is returned. If root->b[EB_RGHT]==1, the tree may only contain unique keys.
369 */
370static forceinline struct eb32_node *
371__eb32i_insert(struct eb_root *root, struct eb32_node *new) {
372 struct eb32_node *old;
373 unsigned int side;
Willy Tarreau3a932442010-05-09 19:29:23 +0200374 eb_troot_t *troot, **up_ptr;
Willy Tarreauc2186022009-10-26 19:48:54 +0100375 int newkey; /* caching the key saves approximately one cycle */
Willy Tarreau6258f7b2011-09-19 20:48:00 +0200376 eb_troot_t *root_right;
Willy Tarreau3a932442010-05-09 19:29:23 +0200377 eb_troot_t *new_left, *new_rght;
378 eb_troot_t *new_leaf;
379 int old_node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100380
381 side = EB_LEFT;
382 troot = root->b[EB_LEFT];
383 root_right = root->b[EB_RGHT];
384 if (unlikely(troot == NULL)) {
385 /* Tree is empty, insert the leaf part below the left branch */
386 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
387 new->node.leaf_p = eb_dotag(root, EB_LEFT);
388 new->node.node_p = NULL; /* node part unused */
389 return new;
390 }
391
392 /* The tree descent is fairly easy :
393 * - first, check if we have reached a leaf node
394 * - second, check if we have gone too far
395 * - third, reiterate
396 * Everywhere, we use <new> for the node node we are inserting, <root>
397 * for the node we attach it to, and <old> for the node we are
398 * displacing below <new>. <troot> will always point to the future node
399 * (tagged with its type). <side> carries the side the node <new> is
400 * attached to below its parent, which is also where previous node
401 * was attached. <newkey> carries a high bit shift of the key being
402 * inserted in order to have negative keys stored before positive
403 * ones.
404 */
405 newkey = new->key + 0x80000000;
406
407 while (1) {
Willy Tarreau3a932442010-05-09 19:29:23 +0200408 if (eb_gettag(troot) == EB_LEAF) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100409 old = container_of(eb_untag(troot, EB_LEAF),
410 struct eb32_node, node.branches);
Willy Tarreauc2186022009-10-26 19:48:54 +0100411 new->node.node_p = old->node.leaf_p;
Willy Tarreau3a932442010-05-09 19:29:23 +0200412 up_ptr = &old->node.leaf_p;
Willy Tarreauc2186022009-10-26 19:48:54 +0100413 break;
414 }
415
416 /* OK we're walking down this link */
417 old = container_of(eb_untag(troot, EB_NODE),
418 struct eb32_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200419 old_node_bit = old->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100420
421 /* Stop going down when we don't have common bits anymore. We
422 * also stop in front of a duplicates tree because it means we
423 * have to insert above.
424 */
425
Willy Tarreau3a932442010-05-09 19:29:23 +0200426 if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
427 (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100428 /* The tree did not contain the key, so we insert <new> before the node
429 * <old>, and set ->bit to designate the lowest bit position in <new>
430 * which applies to ->branches.b[].
431 */
Willy Tarreauc2186022009-10-26 19:48:54 +0100432 new->node.node_p = old->node.node_p;
Willy Tarreau3a932442010-05-09 19:29:23 +0200433 up_ptr = &old->node.node_p;
Willy Tarreauc2186022009-10-26 19:48:54 +0100434 break;
435 }
436
437 /* walk down */
438 root = &old->node.branches;
Willy Tarreau3a932442010-05-09 19:29:23 +0200439 side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;
Willy Tarreauc2186022009-10-26 19:48:54 +0100440 troot = root->b[side];
441 }
442
Willy Tarreau3a932442010-05-09 19:29:23 +0200443 new_left = eb_dotag(&new->node.branches, EB_LEFT);
444 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
445 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
Willy Tarreauc2186022009-10-26 19:48:54 +0100446
447 /* We need the common higher bits between new->key and old->key.
448 * What differences are there between new->key and the node here ?
449 * NOTE that bit(new) is always < bit(root) because highest
450 * bit of new->key and old->key are identical here (otherwise they
451 * would sit on different branches).
452 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200453
Willy Tarreauc2186022009-10-26 19:48:54 +0100454 // note that if EB_NODE_BITS > 1, we should check that it's still >= 0
455 new->node.bit = flsnz(new->key ^ old->key) - EB_NODE_BITS;
Willy Tarreau3a932442010-05-09 19:29:23 +0200456
457 if (new->key == old->key) {
458 new->node.bit = -1; /* mark as new dup tree, just in case */
459
460 if (likely(eb_gettag(root_right))) {
461 /* we refuse to duplicate this key if the tree is
462 * tagged as containing only unique keys.
463 */
464 return old;
465 }
466
467 if (eb_gettag(troot) != EB_LEAF) {
468 /* there was already a dup tree below */
469 struct eb_node *ret;
470 ret = eb_insert_dup(&old->node, &new->node);
471 return container_of(ret, struct eb32_node, node);
472 }
473 /* otherwise fall through */
474 }
Willy Tarreauc2186022009-10-26 19:48:54 +0100475
Willy Tarreau3a932442010-05-09 19:29:23 +0200476 if ((s32)new->key >= (s32)old->key) {
477 new->node.branches.b[EB_LEFT] = troot;
478 new->node.branches.b[EB_RGHT] = new_leaf;
479 new->node.leaf_p = new_rght;
480 *up_ptr = new_left;
481 }
482 else {
483 new->node.branches.b[EB_LEFT] = new_leaf;
484 new->node.branches.b[EB_RGHT] = troot;
485 new->node.leaf_p = new_left;
486 *up_ptr = new_rght;
487 }
488
489 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
490 * parent is already set to <new>, and the <root>'s branch is still in
491 * <side>. Update the root's leaf till we have it. Note that we can also
492 * find the side by checking the side of new->node.node_p.
493 */
494
495 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
Willy Tarreauc2186022009-10-26 19:48:54 +0100496 return new;
497}
498
499#endif /* _EB32_TREE_H */