blob: b737bc915fcd51f2020f9900a27a5a3c6968604e [file] [log] [blame]
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +01001/*
2 * Elastic Binary Trees - generic macros and structures.
Willy Tarreau1fb6c872008-05-16 19:48:20 +02003 * Version 4.0
Willy Tarreau70bcfb72008-01-27 02:21:53 +01004 * (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 *
21 * Short history :
22 *
23 * 2007/09/28: full support for the duplicates tree => v3
24 * 2007/07/08: merge back cleanups from kernel version.
25 * 2007/07/01: merge into Linux Kernel (try 1).
26 * 2007/05/27: version 2: compact everything into one single struct
27 * 2007/05/18: adapted the structure to support embedded nodes
28 * 2007/05/13: adapted to mempools v2.
29 */
30
31
32
33/*
34 General idea:
35 -------------
36 In a radix binary tree, we may have up to 2N-1 nodes for N keys if all of
37 them are leaves. If we find a way to differentiate intermediate nodes (later
38 called "nodes") and final nodes (later called "leaves"), and we associate
39 them by two, it is possible to build sort of a self-contained radix tree with
40 intermediate nodes always present. It will not be as cheap as the ultree for
41 optimal cases as shown below, but the optimal case almost never happens :
42
43 Eg, to store 8, 10, 12, 13, 14 :
44
45 ultree this theorical tree
46
47 8 8
48 / \ / \
49 10 12 10 12
50 / \ / \
51 13 14 12 14
52 / \
53 12 13
54
55 Note that on real-world tests (with a scheduler), is was verified that the
56 case with data on an intermediate node never happens. This is because the
57 data spectrum is too large for such coincidences to happen. It would require
58 for instance that a task has its expiration time at an exact second, with
59 other tasks sharing that second. This is too rare to try to optimize for it.
60
61 What is interesting is that the node will only be added above the leaf when
62 necessary, which implies that it will always remain somewhere above it. So
63 both the leaf and the node can share the exact value of the leaf, because
64 when going down the node, the bit mask will be applied to comparisons. So we
65 are tempted to have one single key shared between the node and the leaf.
66
67 The bit only serves the nodes, and the dups only serve the leaves. So we can
68 put a lot of information in common. This results in one single entity with
69 two branch pointers and two parent pointers, one for the node part, and one
70 for the leaf part :
71
72 node's leaf's
73 parent parent
74 | |
75 [node] [leaf]
76 / \
77 left right
78 branch branch
79
80 The node may very well refer to its leaf counterpart in one of its branches,
81 indicating that its own leaf is just below it :
82
83 node's
84 parent
85 |
86 [node]
87 / \
88 left [leaf]
89 branch
90
91 Adding keys in such a tree simply consists in inserting nodes between
92 other nodes and/or leaves :
93
94 [root]
95 |
96 [node2]
97 / \
98 [leaf1] [node3]
99 / \
100 [leaf2] [leaf3]
101
102 On this diagram, we notice that [node2] and [leaf2] have been pulled away
103 from each other due to the insertion of [node3], just as if there would be
104 an elastic between both parts. This elastic-like behaviour gave its name to
105 the tree : "Elastic Binary Tree", or "EBtree". The entity which associates a
106 node part and a leaf part will be called an "EB node".
107
108 We also notice on the diagram that there is a root entity required to attach
109 the tree. It only contains two branches and there is nothing above it. This
110 is an "EB root". Some will note that [leaf1] has no [node1]. One property of
111 the EBtree is that all nodes have their branches filled, and that if a node
112 has only one branch, it does not need to exist. Here, [leaf1] was added
113 below [root] and did not need any node.
114
115 An EB node contains :
116 - a pointer to the node's parent (node_p)
117 - a pointer to the leaf's parent (leaf_p)
118 - two branches pointing to lower nodes or leaves (branches)
119 - a bit position (bit)
120 - an optional key.
121
122 The key here is optional because it's used only during insertion, in order
123 to classify the nodes. Nothing else in the tree structure requires knowledge
124 of the key. This makes it possible to write type-agnostic primitives for
125 everything, and type-specific insertion primitives. This has led to consider
126 two types of EB nodes. The type-agnostic ones will serve as a header for the
127 other ones, and will simply be called "struct eb_node". The other ones will
128 have their type indicated in the structure name. Eg: "struct eb32_node" for
129 nodes carrying 32 bit keys.
130
131 We will also node that the two branches in a node serve exactly the same
132 purpose as an EB root. For this reason, a "struct eb_root" will be used as
133 well inside the struct eb_node. In order to ease pointer manipulation and
134 ROOT detection when walking upwards, all the pointers inside an eb_node will
135 point to the eb_root part of the referenced EB nodes, relying on the same
136 principle as the linked lists in Linux.
137
138 Another important point to note, is that when walking inside a tree, it is
139 very convenient to know where a node is attached in its parent, and what
140 type of branch it has below it (leaf or node). In order to simplify the
141 operations and to speed up the processing, it was decided in this specific
142 implementation to use the lowest bit from the pointer to designate the side
143 of the upper pointers (left/right) and the type of a branch (leaf/node).
144 This practise is not mandatory by design, but an implementation-specific
145 optimisation permitted on all platforms on which data must be aligned. All
146 known 32 bit platforms align their integers and pointers to 32 bits, leaving
147 the two lower bits unused. So, we say that the pointers are "tagged". And
148 since they designate pointers to root parts, we simply call them
149 "tagged root pointers", or "eb_troot" in the code.
150
151 Duplicate keys are stored in a special manner. When inserting a key, if
152 the same one is found, then an incremental binary tree is built at this
153 place from these keys. This ensures that no special case has to be written
154 to handle duplicates when walking through the tree or when deleting entries.
155 It also guarantees that duplicates will be walked in the exact same order
156 they were inserted. This is very important when trying to achieve fair
157 processing distribution for instance.
158
159 Algorithmic complexity can be derived from 3 variables :
160 - the number of possible different keys in the tree : P
161 - the number of entries in the tree : N
162 - the number of duplicates for one key : D
163
164 Note that this tree is deliberately NOT balanced. For this reason, the worst
165 case may happen with a small tree (eg: 32 distinct keys of one bit). BUT,
166 the operations required to manage such data are so much cheap that they make
167 it worth using it even under such conditions. For instance, a balanced tree
168 may require only 6 levels to store those 32 keys when this tree will
169 require 32. But if per-level operations are 5 times cheaper, it wins.
170
171 Minimal, Maximal and Average times are specified in number of operations.
172 Minimal is given for best condition, Maximal for worst condition, and the
173 average is reported for a tree containing random keys. An operation
174 generally consists in jumping from one node to the other.
175
176 Complexity :
177 - lookup : min=1, max=log(P), avg=log(N)
178 - insertion from root : min=1, max=log(P), avg=log(N)
179 - insertion of dups : min=1, max=log(D), avg=log(D)/2 after lookup
180 - deletion : min=1, max=1, avg=1
181 - prev/next : min=1, max=log(P), avg=2 :
182 N/2 nodes need 1 hop => 1*N/2
183 N/4 nodes need 2 hops => 2*N/4
184 N/8 nodes need 3 hops => 3*N/8
185 ...
186 N/x nodes need log(x) hops => log2(x)*N/x
187 Total cost for all N nodes : sum[i=1..N](log2(i)*N/i) = N*sum[i=1..N](log2(i)/i)
188 Average cost across N nodes = total / N = sum[i=1..N](log2(i)/i) = 2
189
190 This design is currently limited to only two branches per node. Most of the
191 tree descent algorithm would be compatible with more branches (eg: 4, to cut
192 the height in half), but this would probably require more complex operations
193 and the deletion algorithm would be problematic.
194
195 Useful properties :
196 - a node is always added above the leaf it is tied to, and never can get
197 below nor in another branch. This implies that leaves directly attached
198 to the root do not use their node part, which is indicated by a NULL
199 value in node_p. This also enhances the cache efficiency when walking
200 down the tree, because when the leaf is reached, its node part will
201 already have been visited (unless it's the first leaf in the tree).
202
203 - pointers to lower nodes or leaves are stored in "branch" pointers. Only
204 the root node may have a NULL in either branch, it is not possible for
205 other branches. Since the nodes are attached to the left branch of the
206 root, it is not possible to see a NULL left branch when walking up a
207 tree. Thus, an empty tree is immediately identified by a NULL left
208 branch at the root. Conversely, the one and only way to identify the
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200209 root node is to check that it right branch is NULL. Note that the
210 NULL pointer may have a few low-order bits set.
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100211
212 - a node connected to its own leaf will have branch[0|1] pointing to
213 itself, and leaf_p pointing to itself.
214
215 - a node can never have node_p pointing to itself.
216
217 - a node is linked in a tree if and only if it has a non-null leaf_p.
218
219 - a node can never have both branches equal, except for the root which can
220 have them both NULL.
221
222 - deletion only applies to leaves. When a leaf is deleted, its parent must
223 be released too (unless it's the root), and its sibling must attach to
224 the grand-parent, replacing the parent. Also, when a leaf is deleted,
225 the node tied to this leaf will be removed and must be released too. If
226 this node is different from the leaf's parent, the freshly released
227 leaf's parent will be used to replace the node which must go. A released
228 node will never be used anymore, so there's no point in tracking it.
229
230 - the bit index in a node indicates the bit position in the key which is
231 represented by the branches. That means that a node with (bit == 0) is
232 just above two leaves. Negative bit values are used to build a duplicate
233 tree. The first node above two identical leaves gets (bit == -1). This
234 value logarithmically decreases as the duplicate tree grows. During
235 duplicate insertion, a node is inserted above the highest bit value (the
236 lowest absolute value) in the tree during the right-sided walk. If bit
237 -1 is not encountered (highest < -1), we insert above last leaf.
238 Otherwise, we insert above the node with the highest value which was not
239 equal to the one of its parent + 1.
240
241 - the "eb_next" primitive walks from left to right, which means from lower
242 to higher keys. It returns duplicates in the order they were inserted.
243 The "eb_first" primitive returns the left-most entry.
244
245 - the "eb_prev" primitive walks from right to left, which means from
246 higher to lower keys. It returns duplicates in the opposite order they
247 were inserted. The "eb_last" primitive returns the right-most entry.
248
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200249 - a tree which has 1 in the lower bit of its root's right branch is a
250 tree with unique nodes. This means that when a node is inserted with
251 a key which already exists will not be inserted, and the previous
252 entry will be returned.
253
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100254 */
255
Willy Tarreauf56fd8a2007-11-19 18:43:04 +0100256#ifndef _COMMON_EBTREE_H
257#define _COMMON_EBTREE_H
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100258
259#include <stdlib.h>
Willy Tarreaube68e6a2007-11-21 10:34:15 +0100260#include <common/config.h>
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100261
262/* Note: we never need to run fls on null keys, so we can optimize the fls
263 * function by removing a conditional jump.
264 */
265#if defined(__i386__)
266static inline int flsnz(int x)
267{
268 int r;
269 __asm__("bsrl %1,%0\n"
270 : "=r" (r) : "rm" (x));
271 return r+1;
272}
273#else
274// returns 1 to 32 for 1<<0 to 1<<31. Undefined for 0.
275#define flsnz(___a) ({ \
276 register int ___x, ___bits = 0; \
277 ___x = (___a); \
278 if (___x & 0xffff0000) { ___x &= 0xffff0000; ___bits += 16;} \
279 if (___x & 0xff00ff00) { ___x &= 0xff00ff00; ___bits += 8;} \
280 if (___x & 0xf0f0f0f0) { ___x &= 0xf0f0f0f0; ___bits += 4;} \
281 if (___x & 0xcccccccc) { ___x &= 0xcccccccc; ___bits += 2;} \
282 if (___x & 0xaaaaaaaa) { ___x &= 0xaaaaaaaa; ___bits += 1;} \
283 ___bits + 1; \
284 })
285#endif
286
287static inline int fls64(unsigned long long x)
288{
289 unsigned int h;
290 unsigned int bits = 32;
291
292 h = x >> 32;
293 if (!h) {
294 h = x;
295 bits = 0;
296 }
297 return flsnz(h) + bits;
298}
299
300#define fls_auto(x) ((sizeof(x) > 4) ? fls64(x) : flsnz(x))
301
302/* Linux-like "container_of". It returns a pointer to the structure of type
303 * <type> which has its member <name> stored at address <ptr>.
304 */
305#ifndef container_of
306#define container_of(ptr, type, name) ((type *)(((void *)(ptr)) - ((long)&((type *)0)->name)))
307#endif
308
309/*
310 * Gcc >= 3 provides the ability for the program to give hints to the compiler
311 * about what branch of an if is most likely to be taken. This helps the
312 * compiler produce the most compact critical paths, which is generally better
313 * for the cache and to reduce the number of jumps. Be very careful not to use
314 * this in inline functions, because the code reordering it causes very often
315 * has a negative impact on the calling functions.
316 */
Willy Tarreau70bcfb72008-01-27 02:21:53 +0100317#if !defined(likely)
318#if __GNUC__ < 3
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100319#define __builtin_expect(x,y) (x)
Willy Tarreau70bcfb72008-01-27 02:21:53 +0100320#define likely(x) (x)
321#define unlikely(x) (x)
322#elif __GNUC__ < 4
323/* gcc 3.x does the best job at this */
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100324#define likely(x) (__builtin_expect((x) != 0, 1))
325#define unlikely(x) (__builtin_expect((x) != 0, 0))
Willy Tarreau70bcfb72008-01-27 02:21:53 +0100326#else
327/* GCC 4.x is stupid, it performs the comparison then compares it to 1,
328 * so we cheat in a dirty way to prevent it from doing this. This will
329 * only work with ints and booleans though.
330 */
331#define likely(x) (x)
Willy Tarreau75875a72008-07-06 15:18:50 +0200332#define unlikely(x) (__builtin_expect((unsigned long)(x), 0))
Willy Tarreau70bcfb72008-01-27 02:21:53 +0100333#endif
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100334#endif
335
336/* Support passing function parameters in registers. For this, the
337 * CONFIG_EBTREE_REGPARM macro has to be set to the maximal number of registers
338 * allowed. Some functions have intentionally received a regparm lower than
339 * their parameter count, it is in order to avoid register clobbering where
340 * they are called.
341 */
342#ifndef REGPRM1
343#if CONFIG_EBTREE_REGPARM >= 1
344#define REGPRM1 __attribute__((regparm(1)))
345#else
346#define REGPRM1
347#endif
348#endif
349
350#ifndef REGPRM2
351#if CONFIG_EBTREE_REGPARM >= 2
352#define REGPRM2 __attribute__((regparm(2)))
353#else
354#define REGPRM2 REGPRM1
355#endif
356#endif
357
358#ifndef REGPRM3
359#if CONFIG_EBTREE_REGPARM >= 3
360#define REGPRM3 __attribute__((regparm(3)))
361#else
362#define REGPRM3 REGPRM2
363#endif
364#endif
365
366/* Number of bits per node, and number of leaves per node */
367#define EB_NODE_BITS 1
368#define EB_NODE_BRANCHES (1 << EB_NODE_BITS)
369#define EB_NODE_BRANCH_MASK (EB_NODE_BRANCHES - 1)
370
371/* Be careful not to tweak those values. The walking code is optimized for NULL
372 * detection on the assumption that the following values are intact.
373 */
374#define EB_LEFT 0
375#define EB_RGHT 1
376#define EB_LEAF 0
377#define EB_NODE 1
378
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200379/* Tags to set in root->b[EB_RGHT] :
380 * - EB_NORMAL is a normal tree which stores duplicate keys.
381 * - EB_UNIQUE is a tree which stores unique keys.
382 */
383#define EB_NORMAL 0
384#define EB_UNIQUE 1
385
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100386/* This is the same as an eb_node pointer, except that the lower bit embeds
387 * a tag. See eb_dotag()/eb_untag()/eb_gettag(). This tag has two meanings :
388 * - 0=left, 1=right to designate the parent's branch for leaf_p/node_p
389 * - 0=link, 1=leaf to designate the branch's type for branch[]
390 */
391typedef void eb_troot_t;
392
393/* The eb_root connects the node which contains it, to two nodes below it, one
394 * of which may be the same node. At the top of the tree, we use an eb_root
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200395 * too, which always has its right branch NULL (+/1 low-order bits).
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100396 */
397struct eb_root {
398 eb_troot_t *b[EB_NODE_BRANCHES]; /* left and right branches */
399};
400
401/* The eb_node contains the two parts, one for the leaf, which always exists,
402 * and one for the node, which remains unused in the very first node inserted
403 * into the tree. This structure is 20 bytes per node on 32-bit machines. Do
404 * not change the order, benchmarks have shown that it's optimal this way.
405 */
406struct eb_node {
407 struct eb_root branches; /* branches, must be at the beginning */
408 eb_troot_t *node_p; /* link node's parent */
409 eb_troot_t *leaf_p; /* leaf node's parent */
410 int bit; /* link's bit position. */
411};
412
413/* Return the structure of type <type> whose member <member> points to <ptr> */
414#define eb_entry(ptr, type, member) container_of(ptr, type, member)
415
416/* The root of a tree is an eb_root initialized with both pointers NULL.
417 * During its life, only the left pointer will change. The right one will
418 * always remain NULL, which is the way we detect it.
419 */
420#define EB_ROOT \
421 (struct eb_root) { \
422 .b = {[0] = NULL, [1] = NULL }, \
423 }
424
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200425#define EB_ROOT_UNIQUE \
426 (struct eb_root) { \
427 .b = {[0] = NULL, [1] = (void *)1 }, \
428 }
429
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100430#define EB_TREE_HEAD(name) \
431 struct eb_root name = EB_ROOT
432
433
434/***************************************\
435 * Private functions. Not for end-user *
436\***************************************/
437
438/* Converts a root pointer to its equivalent eb_troot_t pointer,
439 * ready to be stored in ->branch[], leaf_p or node_p. NULL is not
440 * conserved. To be used with EB_LEAF, EB_NODE, EB_LEFT or EB_RGHT in <tag>.
441 */
442static inline eb_troot_t *eb_dotag(const struct eb_root *root, const int tag)
443{
444 return (eb_troot_t *)((void *)root + tag);
445}
446
447/* Converts an eb_troot_t pointer pointer to its equivalent eb_root pointer,
448 * for use with pointers from ->branch[], leaf_p or node_p. NULL is conserved
449 * as long as the tree is not corrupted. To be used with EB_LEAF, EB_NODE,
450 * EB_LEFT or EB_RGHT in <tag>.
451 */
452static inline struct eb_root *eb_untag(const eb_troot_t *troot, const int tag)
453{
454 return (struct eb_root *)((void *)troot - tag);
455}
456
457/* returns the tag associated with an eb_troot_t pointer */
458static inline int eb_gettag(eb_troot_t *troot)
459{
460 return (unsigned long)troot & 1;
461}
462
463/* Converts a root pointer to its equivalent eb_troot_t pointer and clears the
464 * tag, no matter what its value was.
465 */
466static inline struct eb_root *eb_clrtag(const eb_troot_t *troot)
467{
468 return (struct eb_root *)((unsigned long)troot & ~1UL);
469}
470
471/* Returns a pointer to the eb_node holding <root> */
472static inline struct eb_node *eb_root_to_node(struct eb_root *root)
473{
474 return container_of(root, struct eb_node, branches);
475}
476
477/* Walks down starting at root pointer <start>, and always walking on side
478 * <side>. It either returns the node hosting the first leaf on that side,
479 * or NULL if no leaf is found. <start> may either be NULL or a branch pointer.
480 * The pointer to the leaf (or NULL) is returned.
481 */
482static inline struct eb_node *eb_walk_down(eb_troot_t *start, unsigned int side)
483{
484 /* A NULL pointer on an empty tree root will be returned as-is */
485 while (eb_gettag(start) == EB_NODE)
486 start = (eb_untag(start, EB_NODE))->b[side];
487 /* NULL is left untouched (root==eb_node, EB_LEAF==0) */
488 return eb_root_to_node(eb_untag(start, EB_LEAF));
489}
490
491/* This function is used to build a tree of duplicates by adding a new node to
492 * a subtree of at least 2 entries. It will probably never be needed inlined,
493 * and it is not for end-user.
494 */
495static inline struct eb_node *
496__eb_insert_dup(struct eb_node *sub, struct eb_node *new)
497{
498 struct eb_node *head = sub;
499
500 struct eb_troot *new_left = eb_dotag(&new->branches, EB_LEFT);
501 struct eb_troot *new_rght = eb_dotag(&new->branches, EB_RGHT);
502 struct eb_troot *new_leaf = eb_dotag(&new->branches, EB_LEAF);
503
504 /* first, identify the deepest hole on the right branch */
505 while (eb_gettag(head->branches.b[EB_RGHT]) != EB_LEAF) {
506 struct eb_node *last = head;
507 head = container_of(eb_untag(head->branches.b[EB_RGHT], EB_NODE),
508 struct eb_node, branches);
509 if (head->bit > last->bit + 1)
510 sub = head; /* there's a hole here */
511 }
512
513 /* Here we have a leaf attached to (head)->b[EB_RGHT] */
514 if (head->bit < -1) {
515 /* A hole exists just before the leaf, we insert there */
516 new->bit = -1;
517 sub = container_of(eb_untag(head->branches.b[EB_RGHT], EB_LEAF),
518 struct eb_node, branches);
519 head->branches.b[EB_RGHT] = eb_dotag(&new->branches, EB_NODE);
520
521 new->node_p = sub->leaf_p;
522 new->leaf_p = new_rght;
523 sub->leaf_p = new_left;
524 new->branches.b[EB_LEFT] = eb_dotag(&sub->branches, EB_LEAF);
525 new->branches.b[EB_RGHT] = new_leaf;
526 return new;
527 } else {
528 int side;
529 /* No hole was found before a leaf. We have to insert above
530 * <sub>. Note that we cannot be certain that <sub> is attached
531 * to the right of its parent, as this is only true if <sub>
532 * is inside the dup tree, not at the head.
533 */
534 new->bit = sub->bit - 1; /* install at the lowest level */
535 side = eb_gettag(sub->node_p);
536 head = container_of(eb_untag(sub->node_p, side), struct eb_node, branches);
537 head->branches.b[side] = eb_dotag(&new->branches, EB_NODE);
538
539 new->node_p = sub->node_p;
540 new->leaf_p = new_rght;
541 sub->node_p = new_left;
542 new->branches.b[EB_LEFT] = eb_dotag(&sub->branches, EB_NODE);
543 new->branches.b[EB_RGHT] = new_leaf;
544 return new;
545 }
546}
547
548
549/**************************************\
550 * Public functions, for the end-user *
551\**************************************/
552
553/* Return the first leaf in the tree starting at <root>, or NULL if none */
554static inline struct eb_node *eb_first(struct eb_root *root)
555{
556 return eb_walk_down(root->b[0], EB_LEFT);
557}
558
559/* Return the last leaf in the tree starting at <root>, or NULL if none */
560static inline struct eb_node *eb_last(struct eb_root *root)
561{
562 return eb_walk_down(root->b[0], EB_RGHT);
563}
564
565/* Return previous leaf node before an existing leaf node, or NULL if none. */
566static inline struct eb_node *eb_prev(struct eb_node *node)
567{
568 eb_troot_t *t = node->leaf_p;
569
570 while (eb_gettag(t) == EB_LEFT) {
571 /* Walking up from left branch. We must ensure that we never
572 * walk beyond root.
573 */
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200574 if (unlikely(eb_clrtag((eb_untag(t, EB_LEFT))->b[EB_RGHT]) == NULL))
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100575 return NULL;
576 t = (eb_root_to_node(eb_untag(t, EB_LEFT)))->node_p;
577 }
578 /* Note that <t> cannot be NULL at this stage */
579 t = (eb_untag(t, EB_RGHT))->b[EB_LEFT];
580 return eb_walk_down(t, EB_RGHT);
581}
582
583/* Return next leaf node after an existing leaf node, or NULL if none. */
584static inline struct eb_node *eb_next(struct eb_node *node)
585{
586 eb_troot_t *t = node->leaf_p;
587
588 while (eb_gettag(t) != EB_LEFT)
589 /* Walking up from right branch, so we cannot be below root */
590 t = (eb_root_to_node(eb_untag(t, EB_RGHT)))->node_p;
591
592 /* Note that <t> cannot be NULL at this stage */
593 t = (eb_untag(t, EB_LEFT))->b[EB_RGHT];
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200594 if (eb_clrtag(t) == NULL)
595 return NULL;
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100596 return eb_walk_down(t, EB_LEFT);
597}
598
599/* Return previous leaf node before an existing leaf node, skipping duplicates,
600 * or NULL if none. */
601static inline struct eb_node *eb_prev_unique(struct eb_node *node)
602{
603 eb_troot_t *t = node->leaf_p;
604
605 while (1) {
606 if (eb_gettag(t) != EB_LEFT) {
607 node = eb_root_to_node(eb_untag(t, EB_RGHT));
608 /* if we're right and not in duplicates, stop here */
609 if (node->bit >= 0)
610 break;
611 t = node->node_p;
612 }
613 else {
614 /* Walking up from left branch. We must ensure that we never
615 * walk beyond root.
616 */
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200617 if (unlikely(eb_clrtag((eb_untag(t, EB_LEFT))->b[EB_RGHT]) == NULL))
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100618 return NULL;
619 t = (eb_root_to_node(eb_untag(t, EB_LEFT)))->node_p;
620 }
621 }
622 /* Note that <t> cannot be NULL at this stage */
623 t = (eb_untag(t, EB_RGHT))->b[EB_LEFT];
624 return eb_walk_down(t, EB_RGHT);
625}
626
627/* Return next leaf node after an existing leaf node, skipping duplicates, or
628 * NULL if none.
629 */
630static inline struct eb_node *eb_next_unique(struct eb_node *node)
631{
632 eb_troot_t *t = node->leaf_p;
633
634 while (1) {
635 if (eb_gettag(t) == EB_LEFT) {
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200636 if (unlikely(eb_clrtag((eb_untag(t, EB_LEFT))->b[EB_RGHT]) == NULL))
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100637 return NULL; /* we reached root */
638 node = eb_root_to_node(eb_untag(t, EB_LEFT));
639 /* if we're left and not in duplicates, stop here */
640 if (node->bit >= 0)
641 break;
642 t = node->node_p;
643 }
644 else {
645 /* Walking up from right branch, so we cannot be below root */
646 t = (eb_root_to_node(eb_untag(t, EB_RGHT)))->node_p;
647 }
648 }
649
650 /* Note that <t> cannot be NULL at this stage */
651 t = (eb_untag(t, EB_LEFT))->b[EB_RGHT];
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200652 if (eb_clrtag(t) == NULL)
653 return NULL;
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100654 return eb_walk_down(t, EB_LEFT);
655}
656
657
658/* Removes a leaf node from the tree if it was still in it. Marks the node
659 * as unlinked.
660 */
661static inline void __eb_delete(struct eb_node *node)
662{
663 __label__ delete_unlink;
664 unsigned int pside, gpside, sibtype;
665 struct eb_node *parent;
666 struct eb_root *gparent;
667
668 if (!node->leaf_p)
669 return;
670
671 /* we need the parent, our side, and the grand parent */
672 pside = eb_gettag(node->leaf_p);
673 parent = eb_root_to_node(eb_untag(node->leaf_p, pside));
674
675 /* We likely have to release the parent link, unless it's the root,
676 * in which case we only set our branch to NULL. Note that we can
677 * only be attached to the root by its left branch.
678 */
679
Willy Tarreau1fb6c872008-05-16 19:48:20 +0200680 if (eb_clrtag(parent->branches.b[EB_RGHT]) == NULL) {
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100681 /* we're just below the root, it's trivial. */
682 parent->branches.b[EB_LEFT] = NULL;
683 goto delete_unlink;
684 }
685
686 /* To release our parent, we have to identify our sibling, and reparent
687 * it directly to/from the grand parent. Note that the sibling can
688 * either be a link or a leaf.
689 */
690
691 gpside = eb_gettag(parent->node_p);
692 gparent = eb_untag(parent->node_p, gpside);
693
694 gparent->b[gpside] = parent->branches.b[!pside];
695 sibtype = eb_gettag(gparent->b[gpside]);
696
697 if (sibtype == EB_LEAF) {
698 eb_root_to_node(eb_untag(gparent->b[gpside], EB_LEAF))->leaf_p =
699 eb_dotag(gparent, gpside);
700 } else {
701 eb_root_to_node(eb_untag(gparent->b[gpside], EB_NODE))->node_p =
702 eb_dotag(gparent, gpside);
703 }
704 /* Mark the parent unused. Note that we do not check if the parent is
705 * our own node, but that's not a problem because if it is, it will be
706 * marked unused at the same time, which we'll use below to know we can
707 * safely remove it.
708 */
709 parent->node_p = NULL;
710
711 /* The parent node has been detached, and is currently unused. It may
712 * belong to another node, so we cannot remove it that way. Also, our
713 * own node part might still be used. so we can use this spare node
714 * to replace ours if needed.
715 */
716
717 /* If our link part is unused, we can safely exit now */
718 if (!node->node_p)
719 goto delete_unlink;
720
721 /* From now on, <node> and <parent> are necessarily different, and the
722 * <node>'s node part is in use. By definition, <parent> is at least
723 * below <node>, so keeping its key for the bit string is OK.
724 */
725
726 parent->node_p = node->node_p;
727 parent->branches = node->branches;
728 parent->bit = node->bit;
729
730 /* We must now update the new node's parent... */
731 gpside = eb_gettag(parent->node_p);
732 gparent = eb_untag(parent->node_p, gpside);
733 gparent->b[gpside] = eb_dotag(&parent->branches, EB_NODE);
734
735 /* ... and its branches */
736 for (pside = 0; pside <= 1; pside++) {
737 if (eb_gettag(parent->branches.b[pside]) == EB_NODE) {
738 eb_root_to_node(eb_untag(parent->branches.b[pside], EB_NODE))->node_p =
739 eb_dotag(&parent->branches, pside);
740 } else {
741 eb_root_to_node(eb_untag(parent->branches.b[pside], EB_LEAF))->leaf_p =
742 eb_dotag(&parent->branches, pside);
743 }
744 }
745 delete_unlink:
746 /* Now the node has been completely unlinked */
747 node->leaf_p = NULL;
748 return; /* tree is not empty yet */
749}
750
751/* These functions are declared in ebtree.c */
752void eb_delete(struct eb_node *node);
753REGPRM1 struct eb_node *eb_insert_dup(struct eb_node *sub, struct eb_node *new);
754
Willy Tarreauf56fd8a2007-11-19 18:43:04 +0100755#endif /* _COMMON_EBTREE_H */
Willy Tarreaue6d2e4d2007-11-15 23:56:17 +0100756
757/*
758 * Local variables:
759 * c-indent-level: 8
760 * c-basic-offset: 8
761 * End:
762 */