blob: 3d18fb28eb3f5f80065854bd0e741e02f06c5288 [file] [log] [blame]
Willy Tarreauc2186022009-10-26 19:48:54 +01001/*
2 * Elastic Binary Trees - exported functions for operations on 64bit nodes.
Willy Tarreau3a932442010-05-09 19:29:23 +02003 * Version 6.0
4 * (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/* Consult eb64tree.h for more details about those functions */
22
23#include "eb64tree.h"
24
25REGPRM2 struct eb64_node *eb64_insert(struct eb_root *root, struct eb64_node *new)
26{
27 return __eb64_insert(root, new);
28}
29
30REGPRM2 struct eb64_node *eb64i_insert(struct eb_root *root, struct eb64_node *new)
31{
32 return __eb64i_insert(root, new);
33}
34
35REGPRM2 struct eb64_node *eb64_lookup(struct eb_root *root, u64 x)
36{
37 return __eb64_lookup(root, x);
38}
39
40REGPRM2 struct eb64_node *eb64i_lookup(struct eb_root *root, s64 x)
41{
42 return __eb64i_lookup(root, x);
43}
44
45/*
46 * Find the last occurrence of the highest key in the tree <root>, which is
47 * equal to or less than <x>. NULL is returned is no key matches.
48 */
49REGPRM2 struct eb64_node *eb64_lookup_le(struct eb_root *root, u64 x)
50{
51 struct eb64_node *node;
52 eb_troot_t *troot;
53
54 troot = root->b[EB_LEFT];
55 if (unlikely(troot == NULL))
56 return NULL;
57
58 while (1) {
59 if ((eb_gettag(troot) == EB_LEAF)) {
60 /* We reached a leaf, which means that the whole upper
61 * parts were common. We will return either the current
62 * node or its next one if the former is too small.
63 */
64 node = container_of(eb_untag(troot, EB_LEAF),
65 struct eb64_node, node.branches);
66 if (node->key <= x)
67 return node;
68 /* return prev */
69 troot = node->node.leaf_p;
70 break;
71 }
72 node = container_of(eb_untag(troot, EB_NODE),
73 struct eb64_node, node.branches);
74
75 if (node->node.bit < 0) {
76 /* We're at the top of a dup tree. Either we got a
77 * matching value and we return the rightmost node, or
78 * we don't and we skip the whole subtree to return the
79 * prev node before the subtree. Note that since we're
80 * at the top of the dup tree, we can simply return the
81 * prev node without first trying to escape from the
82 * tree.
83 */
84 if (node->key <= x) {
85 troot = node->node.branches.b[EB_RGHT];
86 while (eb_gettag(troot) != EB_LEAF)
87 troot = (eb_untag(troot, EB_NODE))->b[EB_RGHT];
88 return container_of(eb_untag(troot, EB_LEAF),
89 struct eb64_node, node.branches);
90 }
91 /* return prev */
92 troot = node->node.node_p;
93 break;
94 }
95
96 if (((x ^ node->key) >> node->node.bit) >= EB_NODE_BRANCHES) {
97 /* No more common bits at all. Either this node is too
98 * small and we need to get its highest value, or it is
99 * too large, and we need to get the prev value.
100 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200101 if ((node->key >> node->node.bit) < (x >> node->node.bit)) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100102 troot = node->node.branches.b[EB_RGHT];
103 return eb64_entry(eb_walk_down(troot, EB_RGHT), struct eb64_node, node);
104 }
105
106 /* Further values will be too high here, so return the prev
107 * unique node (if it exists).
108 */
109 troot = node->node.node_p;
110 break;
111 }
112 troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
113 }
114
115 /* If we get here, it means we want to report previous node before the
116 * current one which is not above. <troot> is already initialised to
117 * the parent's branches.
118 */
119 while (eb_gettag(troot) == EB_LEFT) {
120 /* Walking up from left branch. We must ensure that we never
121 * walk beyond root.
122 */
123 if (unlikely(eb_clrtag((eb_untag(troot, EB_LEFT))->b[EB_RGHT]) == NULL))
124 return NULL;
125 troot = (eb_root_to_node(eb_untag(troot, EB_LEFT)))->node_p;
126 }
127 /* Note that <troot> cannot be NULL at this stage */
128 troot = (eb_untag(troot, EB_RGHT))->b[EB_LEFT];
129 node = eb64_entry(eb_walk_down(troot, EB_RGHT), struct eb64_node, node);
130 return node;
131}
132
133/*
134 * Find the first occurrence of the lowest key in the tree <root>, which is
135 * equal to or greater than <x>. NULL is returned is no key matches.
136 */
137REGPRM2 struct eb64_node *eb64_lookup_ge(struct eb_root *root, u64 x)
138{
139 struct eb64_node *node;
140 eb_troot_t *troot;
141
142 troot = root->b[EB_LEFT];
143 if (unlikely(troot == NULL))
144 return NULL;
145
146 while (1) {
147 if ((eb_gettag(troot) == EB_LEAF)) {
148 /* We reached a leaf, which means that the whole upper
149 * parts were common. We will return either the current
150 * node or its next one if the former is too small.
151 */
152 node = container_of(eb_untag(troot, EB_LEAF),
153 struct eb64_node, node.branches);
154 if (node->key >= x)
155 return node;
156 /* return next */
157 troot = node->node.leaf_p;
158 break;
159 }
160 node = container_of(eb_untag(troot, EB_NODE),
161 struct eb64_node, node.branches);
162
163 if (node->node.bit < 0) {
164 /* We're at the top of a dup tree. Either we got a
165 * matching value and we return the leftmost node, or
166 * we don't and we skip the whole subtree to return the
167 * next node after the subtree. Note that since we're
168 * at the top of the dup tree, we can simply return the
169 * next node without first trying to escape from the
170 * tree.
171 */
172 if (node->key >= x) {
173 troot = node->node.branches.b[EB_LEFT];
174 while (eb_gettag(troot) != EB_LEAF)
175 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
176 return container_of(eb_untag(troot, EB_LEAF),
177 struct eb64_node, node.branches);
178 }
179 /* return next */
180 troot = node->node.node_p;
181 break;
182 }
183
184 if (((x ^ node->key) >> node->node.bit) >= EB_NODE_BRANCHES) {
185 /* No more common bits at all. Either this node is too
186 * large and we need to get its lowest value, or it is too
187 * small, and we need to get the next value.
188 */
189 if ((node->key >> node->node.bit) > (x >> node->node.bit)) {
190 troot = node->node.branches.b[EB_LEFT];
191 return eb64_entry(eb_walk_down(troot, EB_LEFT), struct eb64_node, node);
192 }
193
194 /* Further values will be too low here, so return the next
195 * unique node (if it exists).
196 */
197 troot = node->node.node_p;
198 break;
199 }
200 troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
201 }
202
203 /* If we get here, it means we want to report next node after the
204 * current one which is not below. <troot> is already initialised
205 * to the parent's branches.
206 */
207 while (eb_gettag(troot) != EB_LEFT)
208 /* Walking up from right branch, so we cannot be below root */
209 troot = (eb_root_to_node(eb_untag(troot, EB_RGHT)))->node_p;
210
211 /* Note that <troot> cannot be NULL at this stage */
212 troot = (eb_untag(troot, EB_LEFT))->b[EB_RGHT];
213 if (eb_clrtag(troot) == NULL)
214 return NULL;
215
216 node = eb64_entry(eb_walk_down(troot, EB_LEFT), struct eb64_node, node);
217 return node;
218}