blob: f36f09a024f3fd1b114ba8a80eac4fbfdc5ed56b [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
77/* Return next node in the tree, skipping duplicates, or NULL if none */
78static inline struct eb32_node *eb32_next_unique(struct eb32_node *eb32)
79{
80 return eb32_entry(eb_next_unique(&eb32->node), struct eb32_node, node);
81}
82
83/* Return previous node in the tree, skipping duplicates, or NULL if none */
84static inline struct eb32_node *eb32_prev_unique(struct eb32_node *eb32)
85{
86 return eb32_entry(eb_prev_unique(&eb32->node), struct eb32_node, node);
87}
88
89/* Delete node from the tree if it was linked in. Mark the node unused. Note
90 * that this function relies on a non-inlined generic function: eb_delete.
91 */
92static inline void eb32_delete(struct eb32_node *eb32)
93{
94 eb_delete(&eb32->node);
95}
96
97/*
98 * The following functions are not inlined by default. They are declared
99 * in eb32tree.c, which simply relies on their inline version.
100 */
101REGPRM2 struct eb32_node *eb32_lookup(struct eb_root *root, u32 x);
102REGPRM2 struct eb32_node *eb32i_lookup(struct eb_root *root, s32 x);
103REGPRM2 struct eb32_node *eb32_lookup_le(struct eb_root *root, u32 x);
104REGPRM2 struct eb32_node *eb32_lookup_ge(struct eb_root *root, u32 x);
105REGPRM2 struct eb32_node *eb32_insert(struct eb_root *root, struct eb32_node *new);
106REGPRM2 struct eb32_node *eb32i_insert(struct eb_root *root, struct eb32_node *new);
107
108/*
109 * The following functions are less likely to be used directly, because their
110 * code is larger. The non-inlined version is preferred.
111 */
112
113/* Delete node from the tree if it was linked in. Mark the node unused. */
114static forceinline void __eb32_delete(struct eb32_node *eb32)
115{
116 __eb_delete(&eb32->node);
117}
118
119/*
120 * Find the first occurence of a key in the tree <root>. If none can be
121 * found, return NULL.
122 */
123static forceinline struct eb32_node *__eb32_lookup(struct eb_root *root, u32 x)
124{
125 struct eb32_node *node;
126 eb_troot_t *troot;
127 u32 y;
Willy Tarreau3a932442010-05-09 19:29:23 +0200128 int node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100129
130 troot = root->b[EB_LEFT];
131 if (unlikely(troot == NULL))
132 return NULL;
133
134 while (1) {
135 if ((eb_gettag(troot) == EB_LEAF)) {
136 node = container_of(eb_untag(troot, EB_LEAF),
137 struct eb32_node, node.branches);
138 if (node->key == x)
139 return node;
140 else
141 return NULL;
142 }
143 node = container_of(eb_untag(troot, EB_NODE),
144 struct eb32_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200145 node_bit = node->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100146
147 y = node->key ^ x;
148 if (!y) {
149 /* Either we found the node which holds the key, or
150 * we have a dup tree. In the later case, we have to
151 * walk it down left to get the first entry.
152 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200153 if (node_bit < 0) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100154 troot = node->node.branches.b[EB_LEFT];
155 while (eb_gettag(troot) != EB_LEAF)
156 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
157 node = container_of(eb_untag(troot, EB_LEAF),
158 struct eb32_node, node.branches);
159 }
160 return node;
161 }
162
Willy Tarreau3a932442010-05-09 19:29:23 +0200163 if ((y >> node_bit) >= EB_NODE_BRANCHES)
Willy Tarreauc2186022009-10-26 19:48:54 +0100164 return NULL; /* no more common bits */
165
Willy Tarreau3a932442010-05-09 19:29:23 +0200166 troot = node->node.branches.b[(x >> node_bit) & EB_NODE_BRANCH_MASK];
Willy Tarreauc2186022009-10-26 19:48:54 +0100167 }
168}
169
170/*
171 * Find the first occurence of a signed key in the tree <root>. If none can
172 * be found, return NULL.
173 */
174static forceinline struct eb32_node *__eb32i_lookup(struct eb_root *root, s32 x)
175{
176 struct eb32_node *node;
177 eb_troot_t *troot;
178 u32 key = x ^ 0x80000000;
179 u32 y;
Willy Tarreau3a932442010-05-09 19:29:23 +0200180 int node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100181
182 troot = root->b[EB_LEFT];
183 if (unlikely(troot == NULL))
184 return NULL;
185
186 while (1) {
187 if ((eb_gettag(troot) == EB_LEAF)) {
188 node = container_of(eb_untag(troot, EB_LEAF),
189 struct eb32_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200190 if (node->key == (u32)x)
Willy Tarreauc2186022009-10-26 19:48:54 +0100191 return node;
192 else
193 return NULL;
194 }
195 node = container_of(eb_untag(troot, EB_NODE),
196 struct eb32_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200197 node_bit = node->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100198
199 y = node->key ^ x;
200 if (!y) {
201 /* Either we found the node which holds the key, or
202 * we have a dup tree. In the later case, we have to
203 * walk it down left to get the first entry.
204 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200205 if (node_bit < 0) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100206 troot = node->node.branches.b[EB_LEFT];
207 while (eb_gettag(troot) != EB_LEAF)
208 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
209 node = container_of(eb_untag(troot, EB_LEAF),
210 struct eb32_node, node.branches);
211 }
212 return node;
213 }
214
Willy Tarreau3a932442010-05-09 19:29:23 +0200215 if ((y >> node_bit) >= EB_NODE_BRANCHES)
Willy Tarreauc2186022009-10-26 19:48:54 +0100216 return NULL; /* no more common bits */
217
Willy Tarreau3a932442010-05-09 19:29:23 +0200218 troot = node->node.branches.b[(key >> node_bit) & EB_NODE_BRANCH_MASK];
Willy Tarreauc2186022009-10-26 19:48:54 +0100219 }
220}
221
222/* Insert eb32_node <new> into subtree starting at node root <root>.
223 * Only new->key needs be set with the key. The eb32_node is returned.
224 * If root->b[EB_RGHT]==1, the tree may only contain unique keys.
225 */
226static forceinline struct eb32_node *
227__eb32_insert(struct eb_root *root, struct eb32_node *new) {
228 struct eb32_node *old;
229 unsigned int side;
Willy Tarreau3a932442010-05-09 19:29:23 +0200230 eb_troot_t *troot, **up_ptr;
Willy Tarreauc2186022009-10-26 19:48:54 +0100231 u32 newkey; /* caching the key saves approximately one cycle */
Willy Tarreau6258f7b2011-09-19 20:48:00 +0200232 eb_troot_t *root_right;
Willy Tarreau3a932442010-05-09 19:29:23 +0200233 eb_troot_t *new_left, *new_rght;
234 eb_troot_t *new_leaf;
235 int old_node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100236
237 side = EB_LEFT;
238 troot = root->b[EB_LEFT];
239 root_right = root->b[EB_RGHT];
240 if (unlikely(troot == NULL)) {
241 /* Tree is empty, insert the leaf part below the left branch */
242 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
243 new->node.leaf_p = eb_dotag(root, EB_LEFT);
244 new->node.node_p = NULL; /* node part unused */
245 return new;
246 }
247
248 /* The tree descent is fairly easy :
249 * - first, check if we have reached a leaf node
250 * - second, check if we have gone too far
251 * - third, reiterate
252 * Everywhere, we use <new> for the node node we are inserting, <root>
253 * for the node we attach it to, and <old> for the node we are
254 * displacing below <new>. <troot> will always point to the future node
255 * (tagged with its type). <side> carries the side the node <new> is
256 * attached to below its parent, which is also where previous node
257 * was attached. <newkey> carries the key being inserted.
258 */
259 newkey = new->key;
260
261 while (1) {
Willy Tarreau3a932442010-05-09 19:29:23 +0200262 if (eb_gettag(troot) == EB_LEAF) {
263 /* insert above a leaf */
Willy Tarreauc2186022009-10-26 19:48:54 +0100264 old = container_of(eb_untag(troot, EB_LEAF),
265 struct eb32_node, node.branches);
Willy Tarreauc2186022009-10-26 19:48:54 +0100266 new->node.node_p = old->node.leaf_p;
Willy Tarreau3a932442010-05-09 19:29:23 +0200267 up_ptr = &old->node.leaf_p;
Willy Tarreauc2186022009-10-26 19:48:54 +0100268 break;
269 }
270
271 /* OK we're walking down this link */
272 old = container_of(eb_untag(troot, EB_NODE),
273 struct eb32_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200274 old_node_bit = old->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100275
276 /* Stop going down when we don't have common bits anymore. We
277 * also stop in front of a duplicates tree because it means we
278 * have to insert above.
279 */
280
Willy Tarreau3a932442010-05-09 19:29:23 +0200281 if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
282 (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100283 /* The tree did not contain the key, so we insert <new> before the node
284 * <old>, and set ->bit to designate the lowest bit position in <new>
285 * which applies to ->branches.b[].
286 */
Willy Tarreauc2186022009-10-26 19:48:54 +0100287 new->node.node_p = old->node.node_p;
Willy Tarreau3a932442010-05-09 19:29:23 +0200288 up_ptr = &old->node.node_p;
Willy Tarreauc2186022009-10-26 19:48:54 +0100289 break;
290 }
291
292 /* walk down */
293 root = &old->node.branches;
Willy Tarreau3a932442010-05-09 19:29:23 +0200294 side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;
Willy Tarreauc2186022009-10-26 19:48:54 +0100295 troot = root->b[side];
296 }
297
Willy Tarreau3a932442010-05-09 19:29:23 +0200298 new_left = eb_dotag(&new->node.branches, EB_LEFT);
299 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
300 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
Willy Tarreauc2186022009-10-26 19:48:54 +0100301
302 /* We need the common higher bits between new->key and old->key.
303 * What differences are there between new->key and the node here ?
304 * NOTE that bit(new) is always < bit(root) because highest
305 * bit of new->key and old->key are identical here (otherwise they
306 * would sit on different branches).
307 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200308
Willy Tarreauc2186022009-10-26 19:48:54 +0100309 // note that if EB_NODE_BITS > 1, we should check that it's still >= 0
310 new->node.bit = flsnz(new->key ^ old->key) - EB_NODE_BITS;
Willy Tarreau3a932442010-05-09 19:29:23 +0200311
312 if (new->key == old->key) {
313 new->node.bit = -1; /* mark as new dup tree, just in case */
314
315 if (likely(eb_gettag(root_right))) {
316 /* we refuse to duplicate this key if the tree is
317 * tagged as containing only unique keys.
318 */
319 return old;
320 }
321
322 if (eb_gettag(troot) != EB_LEAF) {
323 /* there was already a dup tree below */
324 struct eb_node *ret;
325 ret = eb_insert_dup(&old->node, &new->node);
326 return container_of(ret, struct eb32_node, node);
327 }
328 /* otherwise fall through */
329 }
Willy Tarreauc2186022009-10-26 19:48:54 +0100330
Willy Tarreau3a932442010-05-09 19:29:23 +0200331 if (new->key >= old->key) {
332 new->node.branches.b[EB_LEFT] = troot;
333 new->node.branches.b[EB_RGHT] = new_leaf;
334 new->node.leaf_p = new_rght;
335 *up_ptr = new_left;
336 }
337 else {
338 new->node.branches.b[EB_LEFT] = new_leaf;
339 new->node.branches.b[EB_RGHT] = troot;
340 new->node.leaf_p = new_left;
341 *up_ptr = new_rght;
342 }
343
344 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
345 * parent is already set to <new>, and the <root>'s branch is still in
346 * <side>. Update the root's leaf till we have it. Note that we can also
347 * find the side by checking the side of new->node.node_p.
348 */
349
350 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
Willy Tarreauc2186022009-10-26 19:48:54 +0100351 return new;
352}
353
354/* Insert eb32_node <new> into subtree starting at node root <root>, using
355 * signed keys. Only new->key needs be set with the key. The eb32_node
356 * is returned. If root->b[EB_RGHT]==1, the tree may only contain unique keys.
357 */
358static forceinline struct eb32_node *
359__eb32i_insert(struct eb_root *root, struct eb32_node *new) {
360 struct eb32_node *old;
361 unsigned int side;
Willy Tarreau3a932442010-05-09 19:29:23 +0200362 eb_troot_t *troot, **up_ptr;
Willy Tarreauc2186022009-10-26 19:48:54 +0100363 int newkey; /* caching the key saves approximately one cycle */
Willy Tarreau6258f7b2011-09-19 20:48:00 +0200364 eb_troot_t *root_right;
Willy Tarreau3a932442010-05-09 19:29:23 +0200365 eb_troot_t *new_left, *new_rght;
366 eb_troot_t *new_leaf;
367 int old_node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100368
369 side = EB_LEFT;
370 troot = root->b[EB_LEFT];
371 root_right = root->b[EB_RGHT];
372 if (unlikely(troot == NULL)) {
373 /* Tree is empty, insert the leaf part below the left branch */
374 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
375 new->node.leaf_p = eb_dotag(root, EB_LEFT);
376 new->node.node_p = NULL; /* node part unused */
377 return new;
378 }
379
380 /* The tree descent is fairly easy :
381 * - first, check if we have reached a leaf node
382 * - second, check if we have gone too far
383 * - third, reiterate
384 * Everywhere, we use <new> for the node node we are inserting, <root>
385 * for the node we attach it to, and <old> for the node we are
386 * displacing below <new>. <troot> will always point to the future node
387 * (tagged with its type). <side> carries the side the node <new> is
388 * attached to below its parent, which is also where previous node
389 * was attached. <newkey> carries a high bit shift of the key being
390 * inserted in order to have negative keys stored before positive
391 * ones.
392 */
393 newkey = new->key + 0x80000000;
394
395 while (1) {
Willy Tarreau3a932442010-05-09 19:29:23 +0200396 if (eb_gettag(troot) == EB_LEAF) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100397 old = container_of(eb_untag(troot, EB_LEAF),
398 struct eb32_node, node.branches);
Willy Tarreauc2186022009-10-26 19:48:54 +0100399 new->node.node_p = old->node.leaf_p;
Willy Tarreau3a932442010-05-09 19:29:23 +0200400 up_ptr = &old->node.leaf_p;
Willy Tarreauc2186022009-10-26 19:48:54 +0100401 break;
402 }
403
404 /* OK we're walking down this link */
405 old = container_of(eb_untag(troot, EB_NODE),
406 struct eb32_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200407 old_node_bit = old->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100408
409 /* Stop going down when we don't have common bits anymore. We
410 * also stop in front of a duplicates tree because it means we
411 * have to insert above.
412 */
413
Willy Tarreau3a932442010-05-09 19:29:23 +0200414 if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
415 (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100416 /* The tree did not contain the key, so we insert <new> before the node
417 * <old>, and set ->bit to designate the lowest bit position in <new>
418 * which applies to ->branches.b[].
419 */
Willy Tarreauc2186022009-10-26 19:48:54 +0100420 new->node.node_p = old->node.node_p;
Willy Tarreau3a932442010-05-09 19:29:23 +0200421 up_ptr = &old->node.node_p;
Willy Tarreauc2186022009-10-26 19:48:54 +0100422 break;
423 }
424
425 /* walk down */
426 root = &old->node.branches;
Willy Tarreau3a932442010-05-09 19:29:23 +0200427 side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;
Willy Tarreauc2186022009-10-26 19:48:54 +0100428 troot = root->b[side];
429 }
430
Willy Tarreau3a932442010-05-09 19:29:23 +0200431 new_left = eb_dotag(&new->node.branches, EB_LEFT);
432 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
433 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
Willy Tarreauc2186022009-10-26 19:48:54 +0100434
435 /* We need the common higher bits between new->key and old->key.
436 * What differences are there between new->key and the node here ?
437 * NOTE that bit(new) is always < bit(root) because highest
438 * bit of new->key and old->key are identical here (otherwise they
439 * would sit on different branches).
440 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200441
Willy Tarreauc2186022009-10-26 19:48:54 +0100442 // note that if EB_NODE_BITS > 1, we should check that it's still >= 0
443 new->node.bit = flsnz(new->key ^ old->key) - EB_NODE_BITS;
Willy Tarreau3a932442010-05-09 19:29:23 +0200444
445 if (new->key == old->key) {
446 new->node.bit = -1; /* mark as new dup tree, just in case */
447
448 if (likely(eb_gettag(root_right))) {
449 /* we refuse to duplicate this key if the tree is
450 * tagged as containing only unique keys.
451 */
452 return old;
453 }
454
455 if (eb_gettag(troot) != EB_LEAF) {
456 /* there was already a dup tree below */
457 struct eb_node *ret;
458 ret = eb_insert_dup(&old->node, &new->node);
459 return container_of(ret, struct eb32_node, node);
460 }
461 /* otherwise fall through */
462 }
Willy Tarreauc2186022009-10-26 19:48:54 +0100463
Willy Tarreau3a932442010-05-09 19:29:23 +0200464 if ((s32)new->key >= (s32)old->key) {
465 new->node.branches.b[EB_LEFT] = troot;
466 new->node.branches.b[EB_RGHT] = new_leaf;
467 new->node.leaf_p = new_rght;
468 *up_ptr = new_left;
469 }
470 else {
471 new->node.branches.b[EB_LEFT] = new_leaf;
472 new->node.branches.b[EB_RGHT] = troot;
473 new->node.leaf_p = new_left;
474 *up_ptr = new_rght;
475 }
476
477 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
478 * parent is already set to <new>, and the <root>'s branch is still in
479 * <side>. Update the root's leaf till we have it. Note that we can also
480 * find the side by checking the side of new->node.node_p.
481 */
482
483 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
Willy Tarreauc2186022009-10-26 19:48:54 +0100484 return new;
485}
486
487#endif /* _EB32_TREE_H */