2
* Elastic Binary Trees - exported functions for operations on 32bit nodes.
3
* (C) 2002-2009 - Willy Tarreau <w@1wt.eu>
5
* This program is free software; you can redistribute it and/or modify
6
* it under the terms of the GNU General Public License as published by
7
* the Free Software Foundation; either version 2 of the License, or
8
* (at your option) any later version.
10
* This program is distributed in the hope that it will be useful,
11
* but WITHOUT ANY WARRANTY; without even the implied warranty of
12
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13
* GNU General Public License for more details.
15
* You should have received a copy of the GNU General Public License
16
* along with this program; if not, write to the Free Software
17
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20
/* Consult eb32tree.h for more details about those functions */
22
#include <common/eb32tree.h>
24
REGPRM2 struct eb32_node *eb32_insert(struct eb_root *root, struct eb32_node *new)
26
return __eb32_insert(root, new);
29
REGPRM2 struct eb32_node *eb32i_insert(struct eb_root *root, struct eb32_node *new)
31
return __eb32i_insert(root, new);
34
REGPRM2 struct eb32_node *eb32_lookup(struct eb_root *root, u32 x)
36
return __eb32_lookup(root, x);
39
REGPRM2 struct eb32_node *eb32i_lookup(struct eb_root *root, s32 x)
41
return __eb32i_lookup(root, x);
45
* Find the first occurrence of the lowest key in the tree <root>, which is
46
* equal to or greater than <x>. NULL is returned is no key matches.
48
REGPRM2 struct eb32_node *eb32_lookup_ge(struct eb_root *root, u32 x)
50
struct eb32_node *node;
53
troot = root->b[EB_LEFT];
54
if (unlikely(troot == NULL))
58
if ((eb_gettag(troot) == EB_LEAF)) {
59
/* We reached a leaf, which means that the whole upper
60
* parts were common. We will return either the current
61
* node or its next one if the former is too small.
63
node = container_of(eb_untag(troot, EB_LEAF),
64
struct eb32_node, node.branches);
68
troot = node->node.leaf_p;
71
node = container_of(eb_untag(troot, EB_NODE),
72
struct eb32_node, node.branches);
74
if (node->node.bit < 0) {
75
/* We're at the top of a dup tree. Either we got a
76
* matching value and we return the leftmost node, or
77
* we don't and we skip the whole subtree to return the
78
* next node after the subtree. Note that since we're
79
* at the top of the dup tree, we can simply return the
80
* next node without first trying to escape from the
84
troot = node->node.branches.b[EB_LEFT];
85
while (eb_gettag(troot) != EB_LEAF)
86
troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
87
return container_of(eb_untag(troot, EB_LEAF),
88
struct eb32_node, node.branches);
91
troot = node->node.node_p;
95
if (((x ^ node->key) >> node->node.bit) >= EB_NODE_BRANCHES) {
96
/* No more common bits at all. Either this node is too
97
* large and we need to get its lowest value, or it is too
98
* small, and we need to get the next value.
100
if ((node->key >> node->node.bit) > (x >> node->node.bit)) {
101
troot = node->node.branches.b[EB_LEFT];
102
return eb32_entry(eb_walk_down(troot, EB_LEFT), struct eb32_node, node);
105
/* Further values will be too low here, so return the next
106
* unique node (if it exists).
108
troot = node->node.node_p;
111
troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
114
/* If we get here, it means we want to report next node after the
115
* current one which is not below. <troot> is already initialised
116
* to the parent's branches.
118
while (eb_gettag(troot) != EB_LEFT)
119
/* Walking up from right branch, so we cannot be below root */
120
troot = (eb_root_to_node(eb_untag(troot, EB_RGHT)))->node_p;
122
/* Note that <troot> cannot be NULL at this stage */
123
troot = (eb_untag(troot, EB_LEFT))->b[EB_RGHT];
124
if (eb_clrtag(troot) == NULL)
127
node = eb32_entry(eb_walk_down(troot, EB_LEFT), struct eb32_node, node);
added
removed
src/eb32tree.c
