blob: e0f9a18127b5d16e9fcc08bf89265192318f5bfb [file] [log] [blame]
Willy Tarreauc2186022009-10-26 19:48:54 +01001/*
2 * Elastic Binary Trees - generic macros and structures.
Willy Tarreaufdc10182010-05-16 21:13:24 +02003 * Version 6.0.1
Willy Tarreau3a932442010-05-09 19:29:23 +02004 * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
Willy Tarreauc2186022009-10-26 19:48:54 +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
209 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.
211
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
249 - 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
254 */
255
256#ifndef _EBTREE_H
257#define _EBTREE_H
258
259#include <stdlib.h>
Willy Tarreaucc05fba2009-10-27 21:40:18 +0100260#include "compiler.h"
Willy Tarreauc2186022009-10-26 19:48:54 +0100261
Willy Tarreau3a932442010-05-09 19:29:23 +0200262static inline int flsnz8_generic(unsigned int x)
263{
264 int ret = 0;
265 if (x >> 4) { x >>= 4; ret += 4; }
266 return ret + ((0xFFFFAA50U >> (x << 1)) & 3) + 1;
267}
268
Willy Tarreauc2186022009-10-26 19:48:54 +0100269/* Note: we never need to run fls on null keys, so we can optimize the fls
270 * function by removing a conditional jump.
271 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200272#if defined(__i386__) || defined(__x86_64__)
273/* this code is similar on 32 and 64 bit */
Willy Tarreauc2186022009-10-26 19:48:54 +0100274static inline int flsnz(int x)
275{
276 int r;
277 __asm__("bsrl %1,%0\n"
278 : "=r" (r) : "rm" (x));
279 return r+1;
280}
Willy Tarreau3a932442010-05-09 19:29:23 +0200281
282static inline int flsnz8(unsigned char x)
283{
284 int r;
285 __asm__("movzbl %%al, %%eax\n"
286 "bsrl %%eax,%0\n"
287 : "=r" (r) : "a" (x));
288 return r+1;
289}
290
Willy Tarreauc2186022009-10-26 19:48:54 +0100291#else
292// returns 1 to 32 for 1<<0 to 1<<31. Undefined for 0.
293#define flsnz(___a) ({ \
294 register int ___x, ___bits = 0; \
295 ___x = (___a); \
296 if (___x & 0xffff0000) { ___x &= 0xffff0000; ___bits += 16;} \
297 if (___x & 0xff00ff00) { ___x &= 0xff00ff00; ___bits += 8;} \
298 if (___x & 0xf0f0f0f0) { ___x &= 0xf0f0f0f0; ___bits += 4;} \
299 if (___x & 0xcccccccc) { ___x &= 0xcccccccc; ___bits += 2;} \
300 if (___x & 0xaaaaaaaa) { ___x &= 0xaaaaaaaa; ___bits += 1;} \
301 ___bits + 1; \
302 })
Willy Tarreau3a932442010-05-09 19:29:23 +0200303
304static inline int flsnz8(unsigned int x)
305{
306 return flsnz8_generic(x);
307}
308
309
Willy Tarreauc2186022009-10-26 19:48:54 +0100310#endif
311
312static inline int fls64(unsigned long long x)
313{
314 unsigned int h;
315 unsigned int bits = 32;
316
317 h = x >> 32;
318 if (!h) {
319 h = x;
320 bits = 0;
321 }
322 return flsnz(h) + bits;
323}
324
325#define fls_auto(x) ((sizeof(x) > 4) ? fls64(x) : flsnz(x))
326
327/* Linux-like "container_of". It returns a pointer to the structure of type
328 * <type> which has its member <name> stored at address <ptr>.
329 */
330#ifndef container_of
331#define container_of(ptr, type, name) ((type *)(((void *)(ptr)) - ((long)&((type *)0)->name)))
332#endif
333
Willy Tarreauc2186022009-10-26 19:48:54 +0100334/* Number of bits per node, and number of leaves per node */
335#define EB_NODE_BITS 1
336#define EB_NODE_BRANCHES (1 << EB_NODE_BITS)
337#define EB_NODE_BRANCH_MASK (EB_NODE_BRANCHES - 1)
338
339/* Be careful not to tweak those values. The walking code is optimized for NULL
340 * detection on the assumption that the following values are intact.
341 */
342#define EB_LEFT 0
343#define EB_RGHT 1
344#define EB_LEAF 0
345#define EB_NODE 1
346
347/* Tags to set in root->b[EB_RGHT] :
348 * - EB_NORMAL is a normal tree which stores duplicate keys.
349 * - EB_UNIQUE is a tree which stores unique keys.
350 */
351#define EB_NORMAL 0
352#define EB_UNIQUE 1
353
354/* This is the same as an eb_node pointer, except that the lower bit embeds
355 * a tag. See eb_dotag()/eb_untag()/eb_gettag(). This tag has two meanings :
356 * - 0=left, 1=right to designate the parent's branch for leaf_p/node_p
357 * - 0=link, 1=leaf to designate the branch's type for branch[]
358 */
359typedef void eb_troot_t;
360
361/* The eb_root connects the node which contains it, to two nodes below it, one
362 * of which may be the same node. At the top of the tree, we use an eb_root
363 * too, which always has its right branch NULL (+/1 low-order bits).
364 */
365struct eb_root {
366 eb_troot_t *b[EB_NODE_BRANCHES]; /* left and right branches */
367};
368
369/* The eb_node contains the two parts, one for the leaf, which always exists,
370 * and one for the node, which remains unused in the very first node inserted
371 * into the tree. This structure is 20 bytes per node on 32-bit machines. Do
372 * not change the order, benchmarks have shown that it's optimal this way.
373 */
374struct eb_node {
375 struct eb_root branches; /* branches, must be at the beginning */
376 eb_troot_t *node_p; /* link node's parent */
377 eb_troot_t *leaf_p; /* leaf node's parent */
Willy Tarreau3a932442010-05-09 19:29:23 +0200378 short int bit; /* link's bit position. */
379 short int pfx; /* data prefix length, always related to leaf */
Willy Tarreauc2186022009-10-26 19:48:54 +0100380};
381
382/* Return the structure of type <type> whose member <member> points to <ptr> */
383#define eb_entry(ptr, type, member) container_of(ptr, type, member)
384
385/* The root of a tree is an eb_root initialized with both pointers NULL.
386 * During its life, only the left pointer will change. The right one will
387 * always remain NULL, which is the way we detect it.
388 */
389#define EB_ROOT \
390 (struct eb_root) { \
391 .b = {[0] = NULL, [1] = NULL }, \
392 }
393
394#define EB_ROOT_UNIQUE \
395 (struct eb_root) { \
396 .b = {[0] = NULL, [1] = (void *)1 }, \
397 }
398
399#define EB_TREE_HEAD(name) \
400 struct eb_root name = EB_ROOT
401
402
403/***************************************\
404 * Private functions. Not for end-user *
405\***************************************/
406
407/* Converts a root pointer to its equivalent eb_troot_t pointer,
408 * ready to be stored in ->branch[], leaf_p or node_p. NULL is not
409 * conserved. To be used with EB_LEAF, EB_NODE, EB_LEFT or EB_RGHT in <tag>.
410 */
411static inline eb_troot_t *eb_dotag(const struct eb_root *root, const int tag)
412{
413 return (eb_troot_t *)((void *)root + tag);
414}
415
416/* Converts an eb_troot_t pointer pointer to its equivalent eb_root pointer,
417 * for use with pointers from ->branch[], leaf_p or node_p. NULL is conserved
418 * as long as the tree is not corrupted. To be used with EB_LEAF, EB_NODE,
419 * EB_LEFT or EB_RGHT in <tag>.
420 */
421static inline struct eb_root *eb_untag(const eb_troot_t *troot, const int tag)
422{
423 return (struct eb_root *)((void *)troot - tag);
424}
425
426/* returns the tag associated with an eb_troot_t pointer */
427static inline int eb_gettag(eb_troot_t *troot)
428{
429 return (unsigned long)troot & 1;
430}
431
432/* Converts a root pointer to its equivalent eb_troot_t pointer and clears the
433 * tag, no matter what its value was.
434 */
435static inline struct eb_root *eb_clrtag(const eb_troot_t *troot)
436{
437 return (struct eb_root *)((unsigned long)troot & ~1UL);
438}
439
440/* Returns a pointer to the eb_node holding <root> */
441static inline struct eb_node *eb_root_to_node(struct eb_root *root)
442{
443 return container_of(root, struct eb_node, branches);
444}
445
446/* Walks down starting at root pointer <start>, and always walking on side
447 * <side>. It either returns the node hosting the first leaf on that side,
448 * or NULL if no leaf is found. <start> may either be NULL or a branch pointer.
449 * The pointer to the leaf (or NULL) is returned.
450 */
451static inline struct eb_node *eb_walk_down(eb_troot_t *start, unsigned int side)
452{
453 /* A NULL pointer on an empty tree root will be returned as-is */
454 while (eb_gettag(start) == EB_NODE)
455 start = (eb_untag(start, EB_NODE))->b[side];
456 /* NULL is left untouched (root==eb_node, EB_LEAF==0) */
457 return eb_root_to_node(eb_untag(start, EB_LEAF));
458}
459
460/* This function is used to build a tree of duplicates by adding a new node to
461 * a subtree of at least 2 entries. It will probably never be needed inlined,
462 * and it is not for end-user.
463 */
464static forceinline struct eb_node *
465__eb_insert_dup(struct eb_node *sub, struct eb_node *new)
466{
467 struct eb_node *head = sub;
468
469 struct eb_troot *new_left = eb_dotag(&new->branches, EB_LEFT);
470 struct eb_troot *new_rght = eb_dotag(&new->branches, EB_RGHT);
471 struct eb_troot *new_leaf = eb_dotag(&new->branches, EB_LEAF);
472
473 /* first, identify the deepest hole on the right branch */
474 while (eb_gettag(head->branches.b[EB_RGHT]) != EB_LEAF) {
475 struct eb_node *last = head;
476 head = container_of(eb_untag(head->branches.b[EB_RGHT], EB_NODE),
477 struct eb_node, branches);
478 if (head->bit > last->bit + 1)
479 sub = head; /* there's a hole here */
480 }
481
482 /* Here we have a leaf attached to (head)->b[EB_RGHT] */
483 if (head->bit < -1) {
484 /* A hole exists just before the leaf, we insert there */
485 new->bit = -1;
486 sub = container_of(eb_untag(head->branches.b[EB_RGHT], EB_LEAF),
487 struct eb_node, branches);
488 head->branches.b[EB_RGHT] = eb_dotag(&new->branches, EB_NODE);
489
490 new->node_p = sub->leaf_p;
491 new->leaf_p = new_rght;
492 sub->leaf_p = new_left;
493 new->branches.b[EB_LEFT] = eb_dotag(&sub->branches, EB_LEAF);
494 new->branches.b[EB_RGHT] = new_leaf;
495 return new;
496 } else {
497 int side;
498 /* No hole was found before a leaf. We have to insert above
499 * <sub>. Note that we cannot be certain that <sub> is attached
500 * to the right of its parent, as this is only true if <sub>
501 * is inside the dup tree, not at the head.
502 */
503 new->bit = sub->bit - 1; /* install at the lowest level */
504 side = eb_gettag(sub->node_p);
505 head = container_of(eb_untag(sub->node_p, side), struct eb_node, branches);
506 head->branches.b[side] = eb_dotag(&new->branches, EB_NODE);
507
508 new->node_p = sub->node_p;
509 new->leaf_p = new_rght;
510 sub->node_p = new_left;
511 new->branches.b[EB_LEFT] = eb_dotag(&sub->branches, EB_NODE);
512 new->branches.b[EB_RGHT] = new_leaf;
513 return new;
514 }
515}
516
517
518/**************************************\
519 * Public functions, for the end-user *
520\**************************************/
521
Willy Tarreaufdc10182010-05-16 21:13:24 +0200522/* Return non-zero if the tree is empty, otherwise zero */
523static inline int eb_is_empty(struct eb_root *root)
524{
525 return !root->b[EB_LEFT];
526}
527
Willy Tarreauc2186022009-10-26 19:48:54 +0100528/* Return the first leaf in the tree starting at <root>, or NULL if none */
529static inline struct eb_node *eb_first(struct eb_root *root)
530{
531 return eb_walk_down(root->b[0], EB_LEFT);
532}
533
534/* Return the last leaf in the tree starting at <root>, or NULL if none */
535static inline struct eb_node *eb_last(struct eb_root *root)
536{
537 return eb_walk_down(root->b[0], EB_RGHT);
538}
539
540/* Return previous leaf node before an existing leaf node, or NULL if none. */
541static inline struct eb_node *eb_prev(struct eb_node *node)
542{
543 eb_troot_t *t = node->leaf_p;
544
545 while (eb_gettag(t) == EB_LEFT) {
546 /* Walking up from left branch. We must ensure that we never
547 * walk beyond root.
548 */
549 if (unlikely(eb_clrtag((eb_untag(t, EB_LEFT))->b[EB_RGHT]) == NULL))
550 return NULL;
551 t = (eb_root_to_node(eb_untag(t, EB_LEFT)))->node_p;
552 }
553 /* Note that <t> cannot be NULL at this stage */
554 t = (eb_untag(t, EB_RGHT))->b[EB_LEFT];
555 return eb_walk_down(t, EB_RGHT);
556}
557
558/* Return next leaf node after an existing leaf node, or NULL if none. */
559static inline struct eb_node *eb_next(struct eb_node *node)
560{
561 eb_troot_t *t = node->leaf_p;
562
563 while (eb_gettag(t) != EB_LEFT)
564 /* Walking up from right branch, so we cannot be below root */
565 t = (eb_root_to_node(eb_untag(t, EB_RGHT)))->node_p;
566
567 /* Note that <t> cannot be NULL at this stage */
568 t = (eb_untag(t, EB_LEFT))->b[EB_RGHT];
569 if (eb_clrtag(t) == NULL)
570 return NULL;
571 return eb_walk_down(t, EB_LEFT);
572}
573
574/* Return previous leaf node before an existing leaf node, skipping duplicates,
575 * or NULL if none. */
576static inline struct eb_node *eb_prev_unique(struct eb_node *node)
577{
578 eb_troot_t *t = node->leaf_p;
579
580 while (1) {
581 if (eb_gettag(t) != EB_LEFT) {
582 node = eb_root_to_node(eb_untag(t, EB_RGHT));
583 /* if we're right and not in duplicates, stop here */
584 if (node->bit >= 0)
585 break;
586 t = node->node_p;
587 }
588 else {
589 /* Walking up from left branch. We must ensure that we never
590 * walk beyond root.
591 */
592 if (unlikely(eb_clrtag((eb_untag(t, EB_LEFT))->b[EB_RGHT]) == NULL))
593 return NULL;
594 t = (eb_root_to_node(eb_untag(t, EB_LEFT)))->node_p;
595 }
596 }
597 /* Note that <t> cannot be NULL at this stage */
598 t = (eb_untag(t, EB_RGHT))->b[EB_LEFT];
599 return eb_walk_down(t, EB_RGHT);
600}
601
602/* Return next leaf node after an existing leaf node, skipping duplicates, or
603 * NULL if none.
604 */
605static inline struct eb_node *eb_next_unique(struct eb_node *node)
606{
607 eb_troot_t *t = node->leaf_p;
608
609 while (1) {
610 if (eb_gettag(t) == EB_LEFT) {
611 if (unlikely(eb_clrtag((eb_untag(t, EB_LEFT))->b[EB_RGHT]) == NULL))
612 return NULL; /* we reached root */
613 node = eb_root_to_node(eb_untag(t, EB_LEFT));
614 /* if we're left and not in duplicates, stop here */
615 if (node->bit >= 0)
616 break;
617 t = node->node_p;
618 }
619 else {
620 /* Walking up from right branch, so we cannot be below root */
621 t = (eb_root_to_node(eb_untag(t, EB_RGHT)))->node_p;
622 }
623 }
624
625 /* Note that <t> cannot be NULL at this stage */
626 t = (eb_untag(t, EB_LEFT))->b[EB_RGHT];
627 if (eb_clrtag(t) == NULL)
628 return NULL;
629 return eb_walk_down(t, EB_LEFT);
630}
631
632
633/* Removes a leaf node from the tree if it was still in it. Marks the node
634 * as unlinked.
635 */
636static forceinline void __eb_delete(struct eb_node *node)
637{
638 __label__ delete_unlink;
639 unsigned int pside, gpside, sibtype;
640 struct eb_node *parent;
641 struct eb_root *gparent;
642
643 if (!node->leaf_p)
644 return;
645
646 /* we need the parent, our side, and the grand parent */
647 pside = eb_gettag(node->leaf_p);
648 parent = eb_root_to_node(eb_untag(node->leaf_p, pside));
649
650 /* We likely have to release the parent link, unless it's the root,
651 * in which case we only set our branch to NULL. Note that we can
652 * only be attached to the root by its left branch.
653 */
654
655 if (eb_clrtag(parent->branches.b[EB_RGHT]) == NULL) {
656 /* we're just below the root, it's trivial. */
657 parent->branches.b[EB_LEFT] = NULL;
658 goto delete_unlink;
659 }
660
661 /* To release our parent, we have to identify our sibling, and reparent
662 * it directly to/from the grand parent. Note that the sibling can
663 * either be a link or a leaf.
664 */
665
666 gpside = eb_gettag(parent->node_p);
667 gparent = eb_untag(parent->node_p, gpside);
668
669 gparent->b[gpside] = parent->branches.b[!pside];
670 sibtype = eb_gettag(gparent->b[gpside]);
671
672 if (sibtype == EB_LEAF) {
673 eb_root_to_node(eb_untag(gparent->b[gpside], EB_LEAF))->leaf_p =
674 eb_dotag(gparent, gpside);
675 } else {
676 eb_root_to_node(eb_untag(gparent->b[gpside], EB_NODE))->node_p =
677 eb_dotag(gparent, gpside);
678 }
679 /* Mark the parent unused. Note that we do not check if the parent is
680 * our own node, but that's not a problem because if it is, it will be
681 * marked unused at the same time, which we'll use below to know we can
682 * safely remove it.
683 */
684 parent->node_p = NULL;
685
686 /* The parent node has been detached, and is currently unused. It may
687 * belong to another node, so we cannot remove it that way. Also, our
688 * own node part might still be used. so we can use this spare node
689 * to replace ours if needed.
690 */
691
692 /* If our link part is unused, we can safely exit now */
693 if (!node->node_p)
694 goto delete_unlink;
695
696 /* From now on, <node> and <parent> are necessarily different, and the
697 * <node>'s node part is in use. By definition, <parent> is at least
698 * below <node>, so keeping its key for the bit string is OK.
699 */
700
701 parent->node_p = node->node_p;
702 parent->branches = node->branches;
703 parent->bit = node->bit;
704
705 /* We must now update the new node's parent... */
706 gpside = eb_gettag(parent->node_p);
707 gparent = eb_untag(parent->node_p, gpside);
708 gparent->b[gpside] = eb_dotag(&parent->branches, EB_NODE);
709
710 /* ... and its branches */
711 for (pside = 0; pside <= 1; pside++) {
712 if (eb_gettag(parent->branches.b[pside]) == EB_NODE) {
713 eb_root_to_node(eb_untag(parent->branches.b[pside], EB_NODE))->node_p =
714 eb_dotag(&parent->branches, pside);
715 } else {
716 eb_root_to_node(eb_untag(parent->branches.b[pside], EB_LEAF))->leaf_p =
717 eb_dotag(&parent->branches, pside);
718 }
719 }
720 delete_unlink:
721 /* Now the node has been completely unlinked */
722 node->leaf_p = NULL;
723 return; /* tree is not empty yet */
724}
725
726/* Compare blocks <a> and <b> byte-to-byte, from bit <ignore> to bit <len-1>.
727 * Return the number of equal bits between strings, assuming that the first
728 * <ignore> bits are already identical. It is possible to return slightly more
729 * than <len> bits if <len> does not stop on a byte boundary and we find exact
730 * bytes. Note that parts or all of <ignore> bits may be rechecked. It is only
731 * passed here as a hint to speed up the check.
732 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200733static forceinline int equal_bits(const unsigned char *a,
734 const unsigned char *b,
735 int ignore, int len)
Willy Tarreauc2186022009-10-26 19:48:54 +0100736{
Willy Tarreau3a932442010-05-09 19:29:23 +0200737 for (ignore >>= 3, a += ignore, b += ignore, ignore <<= 3;
738 ignore < len; ) {
739 unsigned char c;
Willy Tarreauc2186022009-10-26 19:48:54 +0100740
Willy Tarreau3a932442010-05-09 19:29:23 +0200741 a++; b++;
742 ignore += 8;
743 c = b[-1] ^ a[-1];
744
745 if (c) {
746 /* OK now we know that old and new differ at byte <ptr> and that <c> holds
747 * the bit differences. We have to find what bit is differing and report
748 * it as the number of identical bits. Note that low bit numbers are
749 * assigned to high positions in the byte, as we compare them as strings.
750 */
751 ignore -= flsnz8(c);
752 break;
753 }
754 }
755 return ignore;
756}
Willy Tarreauc2186022009-10-26 19:48:54 +0100757
Willy Tarreau3a932442010-05-09 19:29:23 +0200758/* check that the two blocks <a> and <b> are equal on <len> bits. If it is known
759 * they already are on some bytes, this number of equal bytes to be skipped may
760 * be passed in <skip>. It returns 0 if they match, otherwise non-zero.
761 */
762static forceinline int check_bits(const unsigned char *a,
763 const unsigned char *b,
764 int skip,
765 int len)
766{
767 int bit, ret;
768
769 /* This uncommon construction gives the best performance on x86 because
770 * it makes heavy use multiple-index addressing and parallel instructions,
771 * and it prevents gcc from reordering the loop since it is already
772 * properly oriented. Tested to be fine with 2.95 to 4.2.
Willy Tarreauc2186022009-10-26 19:48:54 +0100773 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200774 bit = ~len + (skip << 3) + 9; // = (skip << 3) + (8 - len)
775 ret = a[skip] ^ b[skip];
776 if (unlikely(bit >= 0))
777 return ret >> bit;
778 while (1) {
779 skip++;
780 if (ret)
781 return ret;
782 ret = a[skip] ^ b[skip];
783 bit += 8;
784 if (bit >= 0)
785 return ret >> bit;
786 }
Willy Tarreauc2186022009-10-26 19:48:54 +0100787}
788
Willy Tarreau3a932442010-05-09 19:29:23 +0200789
Willy Tarreauc2186022009-10-26 19:48:54 +0100790/* Compare strings <a> and <b> byte-to-byte, from bit <ignore> to the last 0.
791 * Return the number of equal bits between strings, assuming that the first
792 * <ignore> bits are already identical. Note that parts or all of <ignore> bits
793 * may be rechecked. It is only passed here as a hint to speed up the check.
794 * The caller is responsible for not passing an <ignore> value larger than any
795 * of the two strings. However, referencing any bit from the trailing zero is
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200796 * permitted. Equal strings are reported as a negative number of bits, which
797 * indicates the end was reached.
Willy Tarreauc2186022009-10-26 19:48:54 +0100798 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200799static forceinline int string_equal_bits(const unsigned char *a,
800 const unsigned char *b,
801 int ignore)
Willy Tarreauc2186022009-10-26 19:48:54 +0100802{
Willy Tarreau3a932442010-05-09 19:29:23 +0200803 int beg;
Willy Tarreauc2186022009-10-26 19:48:54 +0100804 unsigned char c;
805
806 beg = ignore >> 3;
807
808 /* skip known and identical bits. We stop at the first different byte
809 * or at the first zero we encounter on either side.
810 */
811 while (1) {
812 unsigned char d;
813
814 c = a[beg];
815 d = b[beg];
816 beg++;
817
818 c ^= d;
819 if (c)
820 break;
821 if (!d)
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200822 return -1;
Willy Tarreauc2186022009-10-26 19:48:54 +0100823 }
Willy Tarreauc2186022009-10-26 19:48:54 +0100824 /* OK now we know that a and b differ at byte <beg>, or that both are zero.
825 * We have to find what bit is differing and report it as the number of
826 * identical bits. Note that low bit numbers are assigned to high positions
827 * in the byte, as we compare them as strings.
828 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200829 return (beg << 3) - flsnz8(c);
Willy Tarreauc2186022009-10-26 19:48:54 +0100830}
831
832static forceinline int cmp_bits(const unsigned char *a, const unsigned char *b, unsigned int pos)
833{
834 unsigned int ofs;
835 unsigned char bit_a, bit_b;
836
837 ofs = pos >> 3;
838 pos = ~pos & 7;
839
840 bit_a = (a[ofs] >> pos) & 1;
841 bit_b = (b[ofs] >> pos) & 1;
842
843 return bit_a - bit_b; /* -1: a<b; 0: a=b; 1: a>b */
844}
845
846static forceinline int get_bit(const unsigned char *a, unsigned int pos)
847{
848 unsigned int ofs;
849
850 ofs = pos >> 3;
851 pos = ~pos & 7;
852 return (a[ofs] >> pos) & 1;
853}
854
855/* These functions are declared in ebtree.c */
856void eb_delete(struct eb_node *node);
857REGPRM1 struct eb_node *eb_insert_dup(struct eb_node *sub, struct eb_node *new);
858
859#endif /* _EB_TREE_H */
860
861/*
862 * Local variables:
863 * c-indent-level: 8
864 * c-basic-offset: 8
865 * End:
866 */