blob: 6a39595b5ce7d6463a94981f40dedd9e24bd9b7f [file] [log] [blame]
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +01001/*
2 * Elastic Binary Trees - macros and structures for operations on 32bit nodes.
Willy Tarreau1fb6c872008-05-16 19:48:20 +02003 * Version 4.0
4 * (C) 2002-2008 - Willy Tarreau <w@1wt.eu>
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +01005 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
Willy Tarreauf56fd8a2007-11-19 18:43:04 +010021#ifndef _COMMON_EB32TREE_H
22#define _COMMON_EB32TREE_H
23
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +010024#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_insert(struct eb_root *root, struct eb32_node *new);
104REGPRM2 struct eb32_node *eb32i_insert(struct eb_root *root, struct eb32_node *new);
105
106/*
107 * The following functions are less likely to be used directly, because their
108 * code is larger. The non-inlined version is preferred.
109 */
110
111/* Delete node from the tree if it was linked in. Mark the node unused. */
112static inline void __eb32_delete(struct eb32_node *eb32)
113{
114 __eb_delete(&eb32->node);
115}
116
117/*
118 * Find the first occurence of a key in the tree <root>. If none can be
119 * found, return NULL.
120 */
121static inline struct eb32_node *__eb32_lookup(struct eb_root *root, u32 x)
122{
123 struct eb32_node *node;
124 eb_troot_t *troot;
125
126 troot = root->b[EB_LEFT];
127 if (unlikely(troot == NULL))
128 return NULL;
129
130 while (1) {
131 if ((eb_gettag(troot) == EB_LEAF)) {
132 node = container_of(eb_untag(troot, EB_LEAF),
133 struct eb32_node, node.branches);
134 if (node->key == x)
135 return node;
136 else
137 return NULL;
138 }
139 node = container_of(eb_untag(troot, EB_NODE),
140 struct eb32_node, node.branches);
141
142 if (x == node->key) {
143 /* Either we found the node which holds the key, or
144 * we have a dup tree. In the later case, we have to
145 * walk it down left to get the first entry.
146 */
147 if (node->node.bit < 0) {
148 troot = node->node.branches.b[EB_LEFT];
149 while (eb_gettag(troot) != EB_LEAF)
150 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
151 node = container_of(eb_untag(troot, EB_LEAF),
152 struct eb32_node, node.branches);
153 }
154 return node;
155 }
156
157 troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
158 }
159}
160
161/*
162 * Find the first occurence of a signed key in the tree <root>. If none can
163 * be found, return NULL.
164 */
165static inline struct eb32_node *__eb32i_lookup(struct eb_root *root, s32 x)
166{
167 struct eb32_node *node;
168 eb_troot_t *troot;
169 u32 key = x ^ 0x80000000;
170
171 troot = root->b[EB_LEFT];
172 if (unlikely(troot == NULL))
173 return NULL;
174
175 while (1) {
176 if ((eb_gettag(troot) == EB_LEAF)) {
177 node = container_of(eb_untag(troot, EB_LEAF),
178 struct eb32_node, node.branches);
179 if (node->key == x)
180 return node;
181 else
182 return NULL;
183 }
184 node = container_of(eb_untag(troot, EB_NODE),
185 struct eb32_node, node.branches);
186
187 if (x == node->key) {
188 /* Either we found the node which holds the key, or
189 * we have a dup tree. In the later case, we have to
190 * walk it down left to get the first entry.
191 */
192 if (node->node.bit < 0) {
193 troot = node->node.branches.b[EB_LEFT];
194 while (eb_gettag(troot) != EB_LEAF)
195 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
196 node = container_of(eb_untag(troot, EB_LEAF),
197 struct eb32_node, node.branches);
198 }
199 return node;
200 }
201
202 troot = node->node.branches.b[(key >> node->node.bit) & EB_NODE_BRANCH_MASK];
203 }
204}
205
206/* Insert eb32_node <new> into subtree starting at node root <root>.
207 * Only new->key needs be set with the key. The eb32_node is returned.
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200208 * If root->b[EB_RGHT]==1, the tree may only contain unique keys.
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100209 */
210static inline struct eb32_node *
211__eb32_insert(struct eb_root *root, struct eb32_node *new) {
212 struct eb32_node *old;
213 unsigned int side;
214 eb_troot_t *troot;
215 u32 newkey; /* caching the key saves approximately one cycle */
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200216 eb_troot_t *root_right = root;
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100217
218 side = EB_LEFT;
219 troot = root->b[EB_LEFT];
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200220 root_right = root->b[EB_RGHT];
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100221 if (unlikely(troot == NULL)) {
222 /* Tree is empty, insert the leaf part below the left branch */
223 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
224 new->node.leaf_p = eb_dotag(root, EB_LEFT);
225 new->node.node_p = NULL; /* node part unused */
226 return new;
227 }
228
229 /* The tree descent is fairly easy :
230 * - first, check if we have reached a leaf node
231 * - second, check if we have gone too far
232 * - third, reiterate
233 * Everywhere, we use <new> for the node node we are inserting, <root>
234 * for the node we attach it to, and <old> for the node we are
235 * displacing below <new>. <troot> will always point to the future node
236 * (tagged with its type). <side> carries the side the node <new> is
237 * attached to below its parent, which is also where previous node
238 * was attached. <newkey> carries the key being inserted.
239 */
240 newkey = new->key;
241
242 while (1) {
243 if (unlikely(eb_gettag(troot) == EB_LEAF)) {
244 eb_troot_t *new_left, *new_rght;
245 eb_troot_t *new_leaf, *old_leaf;
246
247 old = container_of(eb_untag(troot, EB_LEAF),
248 struct eb32_node, node.branches);
249
250 new_left = eb_dotag(&new->node.branches, EB_LEFT);
251 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
252 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
253 old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
254
255 new->node.node_p = old->node.leaf_p;
256
257 /* Right here, we have 3 possibilities :
258 - the tree does not contain the key, and we have
259 new->key < old->key. We insert new above old, on
260 the left ;
261
262 - the tree does not contain the key, and we have
263 new->key > old->key. We insert new above old, on
264 the right ;
265
266 - the tree does contain the key, which implies it
267 is alone. We add the new key next to it as a
268 first duplicate.
269
270 The last two cases can easily be partially merged.
271 */
272
273 if (new->key < old->key) {
274 new->node.leaf_p = new_left;
275 old->node.leaf_p = new_rght;
276 new->node.branches.b[EB_LEFT] = new_leaf;
277 new->node.branches.b[EB_RGHT] = old_leaf;
278 } else {
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200279 /* we may refuse to duplicate this key if the tree is
280 * tagged as containing only unique keys.
281 */
282 if ((new->key == old->key) && eb_gettag(root_right))
283 return old;
284
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100285 /* new->key >= old->key, new goes the right */
286 old->node.leaf_p = new_left;
287 new->node.leaf_p = new_rght;
288 new->node.branches.b[EB_LEFT] = old_leaf;
289 new->node.branches.b[EB_RGHT] = new_leaf;
290
291 if (new->key == old->key) {
292 new->node.bit = -1;
293 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
294 return new;
295 }
296 }
297 break;
298 }
299
300 /* OK we're walking down this link */
301 old = container_of(eb_untag(troot, EB_NODE),
302 struct eb32_node, node.branches);
303
304 /* Stop going down when we don't have common bits anymore. We
305 * also stop in front of a duplicates tree because it means we
306 * have to insert above.
307 */
308
309 if ((old->node.bit < 0) || /* we're above a duplicate tree, stop here */
310 (((new->key ^ old->key) >> old->node.bit) >= EB_NODE_BRANCHES)) {
311 /* The tree did not contain the key, so we insert <new> before the node
312 * <old>, and set ->bit to designate the lowest bit position in <new>
313 * which applies to ->branches.b[].
314 */
315 eb_troot_t *new_left, *new_rght;
316 eb_troot_t *new_leaf, *old_node;
317
318 new_left = eb_dotag(&new->node.branches, EB_LEFT);
319 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
320 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
321 old_node = eb_dotag(&old->node.branches, EB_NODE);
322
323 new->node.node_p = old->node.node_p;
324
325 if (new->key < old->key) {
326 new->node.leaf_p = new_left;
327 old->node.node_p = new_rght;
328 new->node.branches.b[EB_LEFT] = new_leaf;
329 new->node.branches.b[EB_RGHT] = old_node;
330 }
331 else if (new->key > old->key) {
332 old->node.node_p = new_left;
333 new->node.leaf_p = new_rght;
334 new->node.branches.b[EB_LEFT] = old_node;
335 new->node.branches.b[EB_RGHT] = new_leaf;
336 }
337 else {
338 struct eb_node *ret;
339 ret = eb_insert_dup(&old->node, &new->node);
340 return container_of(ret, struct eb32_node, node);
341 }
342 break;
343 }
344
345 /* walk down */
346 root = &old->node.branches;
347 side = (newkey >> old->node.bit) & EB_NODE_BRANCH_MASK;
348 troot = root->b[side];
349 }
350
351 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
352 * parent is already set to <new>, and the <root>'s branch is still in
353 * <side>. Update the root's leaf till we have it. Note that we can also
354 * find the side by checking the side of new->node.node_p.
355 */
356
357 /* We need the common higher bits between new->key and old->key.
358 * What differences are there between new->key and the node here ?
359 * NOTE that bit(new) is always < bit(root) because highest
360 * bit of new->key and old->key are identical here (otherwise they
361 * would sit on different branches).
362 */
363 // note that if EB_NODE_BITS > 1, we should check that it's still >= 0
364 new->node.bit = flsnz(new->key ^ old->key) - EB_NODE_BITS;
365 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
366
367 return new;
368}
369
370/* Insert eb32_node <new> into subtree starting at node root <root>, using
371 * signed keys. Only new->key needs be set with the key. The eb32_node
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200372 * is returned. If root->b[EB_RGHT]==1, the tree may only contain unique keys.
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100373 */
374static inline struct eb32_node *
375__eb32i_insert(struct eb_root *root, struct eb32_node *new) {
376 struct eb32_node *old;
377 unsigned int side;
378 eb_troot_t *troot;
379 int newkey; /* caching the key saves approximately one cycle */
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200380 eb_troot_t *root_right = root;
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100381
382 side = EB_LEFT;
383 troot = root->b[EB_LEFT];
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200384 root_right = root->b[EB_RGHT];
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100385 if (unlikely(troot == NULL)) {
386 /* Tree is empty, insert the leaf part below the left branch */
387 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
388 new->node.leaf_p = eb_dotag(root, EB_LEFT);
389 new->node.node_p = NULL; /* node part unused */
390 return new;
391 }
392
393 /* The tree descent is fairly easy :
394 * - first, check if we have reached a leaf node
395 * - second, check if we have gone too far
396 * - third, reiterate
397 * Everywhere, we use <new> for the node node we are inserting, <root>
398 * for the node we attach it to, and <old> for the node we are
399 * displacing below <new>. <troot> will always point to the future node
400 * (tagged with its type). <side> carries the side the node <new> is
401 * attached to below its parent, which is also where previous node
402 * was attached. <newkey> carries a high bit shift of the key being
403 * inserted in order to have negative keys stored before positive
404 * ones.
405 */
406 newkey = new->key + 0x80000000;
407
408 while (1) {
409 if (unlikely(eb_gettag(troot) == EB_LEAF)) {
410 eb_troot_t *new_left, *new_rght;
411 eb_troot_t *new_leaf, *old_leaf;
412
413 old = container_of(eb_untag(troot, EB_LEAF),
414 struct eb32_node, node.branches);
415
416 new_left = eb_dotag(&new->node.branches, EB_LEFT);
417 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
418 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
419 old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
420
421 new->node.node_p = old->node.leaf_p;
422
423 /* Right here, we have 3 possibilities :
424 - the tree does not contain the key, and we have
425 new->key < old->key. We insert new above old, on
426 the left ;
427
428 - the tree does not contain the key, and we have
429 new->key > old->key. We insert new above old, on
430 the right ;
431
432 - the tree does contain the key, which implies it
433 is alone. We add the new key next to it as a
434 first duplicate.
435
436 The last two cases can easily be partially merged.
437 */
438
439 if ((s32)new->key < (s32)old->key) {
440 new->node.leaf_p = new_left;
441 old->node.leaf_p = new_rght;
442 new->node.branches.b[EB_LEFT] = new_leaf;
443 new->node.branches.b[EB_RGHT] = old_leaf;
444 } else {
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200445 /* we may refuse to duplicate this key if the tree is
446 * tagged as containing only unique keys.
447 */
448 if ((new->key == old->key) && eb_gettag(root_right))
449 return old;
450
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100451 /* new->key >= old->key, new goes the right */
452 old->node.leaf_p = new_left;
453 new->node.leaf_p = new_rght;
454 new->node.branches.b[EB_LEFT] = old_leaf;
455 new->node.branches.b[EB_RGHT] = new_leaf;
456
457 if (new->key == old->key) {
458 new->node.bit = -1;
459 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
460 return new;
461 }
462 }
463 break;
464 }
465
466 /* OK we're walking down this link */
467 old = container_of(eb_untag(troot, EB_NODE),
468 struct eb32_node, node.branches);
469
470 /* Stop going down when we don't have common bits anymore. We
471 * also stop in front of a duplicates tree because it means we
472 * have to insert above.
473 */
474
475 if ((old->node.bit < 0) || /* we're above a duplicate tree, stop here */
476 (((new->key ^ old->key) >> old->node.bit) >= EB_NODE_BRANCHES)) {
477 /* The tree did not contain the key, so we insert <new> before the node
478 * <old>, and set ->bit to designate the lowest bit position in <new>
479 * which applies to ->branches.b[].
480 */
481 eb_troot_t *new_left, *new_rght;
482 eb_troot_t *new_leaf, *old_node;
483
484 new_left = eb_dotag(&new->node.branches, EB_LEFT);
485 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
486 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
487 old_node = eb_dotag(&old->node.branches, EB_NODE);
488
489 new->node.node_p = old->node.node_p;
490
491 if ((s32)new->key < (s32)old->key) {
492 new->node.leaf_p = new_left;
493 old->node.node_p = new_rght;
494 new->node.branches.b[EB_LEFT] = new_leaf;
495 new->node.branches.b[EB_RGHT] = old_node;
496 }
497 else if ((s32)new->key > (s32)old->key) {
498 old->node.node_p = new_left;
499 new->node.leaf_p = new_rght;
500 new->node.branches.b[EB_LEFT] = old_node;
501 new->node.branches.b[EB_RGHT] = new_leaf;
502 }
503 else {
504 struct eb_node *ret;
505 ret = eb_insert_dup(&old->node, &new->node);
506 return container_of(ret, struct eb32_node, node);
507 }
508 break;
509 }
510
511 /* walk down */
512 root = &old->node.branches;
513 side = (newkey >> old->node.bit) & EB_NODE_BRANCH_MASK;
514 troot = root->b[side];
515 }
516
517 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
518 * parent is already set to <new>, and the <root>'s branch is still in
519 * <side>. Update the root's leaf till we have it. Note that we can also
520 * find the side by checking the side of new->node.node_p.
521 */
522
523 /* We need the common higher bits between new->key and old->key.
524 * What differences are there between new->key and the node here ?
525 * NOTE that bit(new) is always < bit(root) because highest
526 * bit of new->key and old->key are identical here (otherwise they
527 * would sit on different branches).
528 */
529 // note that if EB_NODE_BITS > 1, we should check that it's still >= 0
530 new->node.bit = flsnz(new->key ^ old->key) - EB_NODE_BITS;
531 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
532
533 return new;
534}
Willy Tarreauf56fd8a2007-11-19 18:43:04 +0100535
536#endif /* _COMMON_EB32TREE_H */