blob: f86101db0fb59618df213fdda384903baa72e1a0 [file] [log] [blame]
Willy Tarreauc2186022009-10-26 19:48:54 +01001/*
2 * Elastic Binary Trees - macros to manipulate String data nodes.
Willy Tarreauf3bfede2011-07-25 11:38:17 +02003 * Version 6.0.6
Willy Tarreaue1ee9562011-01-04 14:33:13 +01004 * (C) 2002-2011 - Willy Tarreau <w@1wt.eu>
Willy Tarreauc2186022009-10-26 19:48:54 +01005 *
Willy Tarreauf3bfede2011-07-25 11:38:17 +02006 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation, version 2.1
9 * exclusively.
Willy Tarreauc2186022009-10-26 19:48:54 +010010 *
Willy Tarreauf3bfede2011-07-25 11:38:17 +020011 * This library is distributed in the hope that it will be useful,
Willy Tarreauc2186022009-10-26 19:48:54 +010012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
Willy Tarreauf3bfede2011-07-25 11:38:17 +020013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
Willy Tarreauc2186022009-10-26 19:48:54 +010015 *
Willy Tarreauf3bfede2011-07-25 11:38:17 +020016 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
Willy Tarreauc2186022009-10-26 19:48:54 +010019 */
20
21/* These functions and macros rely on Multi-Byte nodes */
22
Willy Tarreau9e2e39e2009-11-02 14:43:39 +010023#ifndef _EBSTTREE_H
24#define _EBSTTREE_H
25
Willy Tarreauc2186022009-10-26 19:48:54 +010026#include "ebtree.h"
27#include "ebmbtree.h"
28
29/* The following functions are not inlined by default. They are declared
30 * in ebsttree.c, which simply relies on their inline version.
31 */
32REGPRM2 struct ebmb_node *ebst_lookup(struct eb_root *root, const char *x);
33REGPRM2 struct ebmb_node *ebst_insert(struct eb_root *root, struct ebmb_node *new);
34
Willy Tarreaue1ee9562011-01-04 14:33:13 +010035/* Find the first occurence of a length <len> string <x> in the tree <root>.
36 * It's the caller's reponsibility to use this function only on trees which
37 * only contain zero-terminated strings, and that no null character is present
38 * in string <x> in the first <len> chars. If none can be found, return NULL.
39 */
40static forceinline struct ebmb_node *
41ebst_lookup_len(struct eb_root *root, const char *x, unsigned int len)
42{
43 struct ebmb_node *node;
44
45 node = ebmb_lookup(root, x, len);
46 if (!node || node->key[len] != 0)
47 return NULL;
48 return node;
49}
50
Willy Tarreauc2186022009-10-26 19:48:54 +010051/* Find the first occurence of a zero-terminated string <x> in the tree <root>.
52 * It's the caller's reponsibility to use this function only on trees which
53 * only contain zero-terminated strings. If none can be found, return NULL.
54 */
55static forceinline struct ebmb_node *__ebst_lookup(struct eb_root *root, const void *x)
56{
57 struct ebmb_node *node;
58 eb_troot_t *troot;
Willy Tarreau3a932442010-05-09 19:29:23 +020059 int bit;
60 int node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +010061
62 troot = root->b[EB_LEFT];
63 if (unlikely(troot == NULL))
64 return NULL;
65
66 bit = 0;
67 while (1) {
68 if ((eb_gettag(troot) == EB_LEAF)) {
69 node = container_of(eb_untag(troot, EB_LEAF),
70 struct ebmb_node, node.branches);
Willy Tarreau4c848222009-10-29 12:00:11 +010071 if (strcmp((char *)node->key, x) == 0)
Willy Tarreauc2186022009-10-26 19:48:54 +010072 return node;
73 else
74 return NULL;
75 }
76 node = container_of(eb_untag(troot, EB_NODE),
77 struct ebmb_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +020078 node_bit = node->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +010079
Willy Tarreau3a932442010-05-09 19:29:23 +020080 if (node_bit < 0) {
Willy Tarreauc2186022009-10-26 19:48:54 +010081 /* We have a dup tree now. Either it's for the same
82 * value, and we walk down left, or it's a different
83 * one and we don't have our key.
84 */
Willy Tarreau4c848222009-10-29 12:00:11 +010085 if (strcmp((char *)node->key, x) != 0)
Willy Tarreauc2186022009-10-26 19:48:54 +010086 return NULL;
87
88 troot = node->node.branches.b[EB_LEFT];
89 while (eb_gettag(troot) != EB_LEAF)
90 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
91 node = container_of(eb_untag(troot, EB_LEAF),
92 struct ebmb_node, node.branches);
93 return node;
94 }
95
Willy Tarreaub55fcf22010-10-28 22:48:29 +020096 /* OK, normal data node, let's walk down but don't compare data
97 * if we already reached the end of the key.
98 */
99 if (likely(bit >= 0)) {
100 bit = string_equal_bits(x, node->key, bit);
101 if (likely(bit < node_bit)) {
102 if (bit >= 0)
103 return NULL; /* no more common bits */
104
105 /* bit < 0 : we reached the end of the key. If we
106 * are in a tree with unique keys, we can return
107 * this node. Otherwise we have to walk it down
108 * and stop comparing bits.
109 */
110 if (eb_gettag(root->b[EB_RGHT]))
111 return node;
112 }
Willy Tarreau007257e2011-11-14 14:09:27 +0100113 /* if the bit is larger than the node's, we must bound it
114 * because we might have compared too many bytes with an
115 * inappropriate leaf. For a test, build a tree from "0",
116 * "WW", "W", "S" inserted in this exact sequence and lookup
117 * "W" => "S" is returned without this assignment.
118 */
119 else
120 bit = node_bit;
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200121 }
Willy Tarreauc2186022009-10-26 19:48:54 +0100122
Willy Tarreau3a932442010-05-09 19:29:23 +0200123 troot = node->node.branches.b[(((unsigned char*)x)[node_bit >> 3] >>
124 (~node_bit & 7)) & 1];
Willy Tarreauc2186022009-10-26 19:48:54 +0100125 }
126}
127
128/* Insert ebmb_node <new> into subtree starting at node root <root>. Only
129 * new->key needs be set with the zero-terminated string key. The ebmb_node is
130 * returned. If root->b[EB_RGHT]==1, the tree may only contain unique keys. The
131 * caller is responsible for properly terminating the key with a zero.
132 */
133static forceinline struct ebmb_node *
134__ebst_insert(struct eb_root *root, struct ebmb_node *new)
135{
136 struct ebmb_node *old;
137 unsigned int side;
138 eb_troot_t *troot;
Willy Tarreau6258f7b2011-09-19 20:48:00 +0200139 eb_troot_t *root_right;
Willy Tarreauc2186022009-10-26 19:48:54 +0100140 int diff;
141 int bit;
Willy Tarreau3a932442010-05-09 19:29:23 +0200142 int old_node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100143
144 side = EB_LEFT;
145 troot = root->b[EB_LEFT];
146 root_right = root->b[EB_RGHT];
147 if (unlikely(troot == NULL)) {
148 /* Tree is empty, insert the leaf part below the left branch */
149 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
150 new->node.leaf_p = eb_dotag(root, EB_LEFT);
151 new->node.node_p = NULL; /* node part unused */
152 return new;
153 }
154
155 /* The tree descent is fairly easy :
156 * - first, check if we have reached a leaf node
157 * - second, check if we have gone too far
158 * - third, reiterate
159 * Everywhere, we use <new> for the node node we are inserting, <root>
160 * for the node we attach it to, and <old> for the node we are
161 * displacing below <new>. <troot> will always point to the future node
162 * (tagged with its type). <side> carries the side the node <new> is
163 * attached to below its parent, which is also where previous node
164 * was attached.
165 */
166
167 bit = 0;
168 while (1) {
169 if (unlikely(eb_gettag(troot) == EB_LEAF)) {
170 eb_troot_t *new_left, *new_rght;
171 eb_troot_t *new_leaf, *old_leaf;
172
173 old = container_of(eb_untag(troot, EB_LEAF),
174 struct ebmb_node, node.branches);
175
176 new_left = eb_dotag(&new->node.branches, EB_LEFT);
177 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
178 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
179 old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
180
181 new->node.node_p = old->node.leaf_p;
182
183 /* Right here, we have 3 possibilities :
184 * - the tree does not contain the key, and we have
185 * new->key < old->key. We insert new above old, on
186 * the left ;
187 *
188 * - the tree does not contain the key, and we have
189 * new->key > old->key. We insert new above old, on
190 * the right ;
191 *
192 * - the tree does contain the key, which implies it
193 * is alone. We add the new key next to it as a
194 * first duplicate.
195 *
196 * The last two cases can easily be partially merged.
197 */
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200198 if (bit >= 0)
199 bit = string_equal_bits(new->key, old->key, bit);
Willy Tarreauc2186022009-10-26 19:48:54 +0100200
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200201 if (bit < 0) {
202 /* key was already there */
203
Willy Tarreauc2186022009-10-26 19:48:54 +0100204 /* we may refuse to duplicate this key if the tree is
205 * tagged as containing only unique keys.
206 */
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200207 if (eb_gettag(root_right))
Willy Tarreauc2186022009-10-26 19:48:54 +0100208 return old;
209
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200210 /* new arbitrarily goes to the right and tops the dup tree */
Willy Tarreauc2186022009-10-26 19:48:54 +0100211 old->node.leaf_p = new_left;
212 new->node.leaf_p = new_rght;
213 new->node.branches.b[EB_LEFT] = old_leaf;
214 new->node.branches.b[EB_RGHT] = new_leaf;
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200215 new->node.bit = -1;
216 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
217 return new;
218 }
Willy Tarreauc2186022009-10-26 19:48:54 +0100219
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200220 diff = cmp_bits(new->key, old->key, bit);
221 if (diff < 0) {
222 /* new->key < old->key, new takes the left */
223 new->node.leaf_p = new_left;
224 old->node.leaf_p = new_rght;
225 new->node.branches.b[EB_LEFT] = new_leaf;
226 new->node.branches.b[EB_RGHT] = old_leaf;
227 } else {
228 /* new->key > old->key, new takes the right */
229 old->node.leaf_p = new_left;
230 new->node.leaf_p = new_rght;
231 new->node.branches.b[EB_LEFT] = old_leaf;
232 new->node.branches.b[EB_RGHT] = new_leaf;
Willy Tarreauc2186022009-10-26 19:48:54 +0100233 }
234 break;
235 }
236
237 /* OK we're walking down this link */
238 old = container_of(eb_untag(troot, EB_NODE),
239 struct ebmb_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200240 old_node_bit = old->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100241
242 /* Stop going down when we don't have common bits anymore. We
243 * also stop in front of a duplicates tree because it means we
244 * have to insert above. Note: we can compare more bits than
245 * the current node's because as long as they are identical, we
246 * know we descend along the correct side.
247 */
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200248 if (bit >= 0 && (bit < old_node_bit || old_node_bit < 0))
Willy Tarreauc2186022009-10-26 19:48:54 +0100249 bit = string_equal_bits(new->key, old->key, bit);
Willy Tarreauc2186022009-10-26 19:48:54 +0100250
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200251 if (unlikely(bit < 0)) {
252 /* Perfect match, we must only stop on head of dup tree
253 * or walk down to a leaf.
254 */
255 if (old_node_bit < 0) {
256 /* We know here that string_equal_bits matched all
257 * bits and that we're on top of a dup tree, then
258 * we can perform the dup insertion and return.
259 */
260 struct eb_node *ret;
261 ret = eb_insert_dup(&old->node, &new->node);
262 return container_of(ret, struct ebmb_node, node);
263 }
264 /* OK so let's walk down */
265 }
266 else if (bit < old_node_bit || old_node_bit < 0) {
267 /* The tree did not contain the key, or we stopped on top of a dup
268 * tree, possibly containing the key. In the former case, we insert
269 * <new> before the node <old>, and set ->bit to designate the lowest
270 * bit position in <new> which applies to ->branches.b[]. In the later
271 * case, we add the key to the existing dup tree. Note that we cannot
272 * enter here if we match an intermediate node's key that is not the
273 * head of a dup tree.
Willy Tarreauc2186022009-10-26 19:48:54 +0100274 */
275 eb_troot_t *new_left, *new_rght;
276 eb_troot_t *new_leaf, *old_node;
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200277
Willy Tarreauc2186022009-10-26 19:48:54 +0100278 new_left = eb_dotag(&new->node.branches, EB_LEFT);
279 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
280 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
281 old_node = eb_dotag(&old->node.branches, EB_NODE);
282
283 new->node.node_p = old->node.node_p;
284
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200285 /* we can never match all bits here */
Willy Tarreauc2186022009-10-26 19:48:54 +0100286 diff = cmp_bits(new->key, old->key, bit);
287 if (diff < 0) {
288 new->node.leaf_p = new_left;
289 old->node.node_p = new_rght;
290 new->node.branches.b[EB_LEFT] = new_leaf;
291 new->node.branches.b[EB_RGHT] = old_node;
292 }
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200293 else {
Willy Tarreauc2186022009-10-26 19:48:54 +0100294 old->node.node_p = new_left;
295 new->node.leaf_p = new_rght;
296 new->node.branches.b[EB_LEFT] = old_node;
297 new->node.branches.b[EB_RGHT] = new_leaf;
298 }
Willy Tarreauc2186022009-10-26 19:48:54 +0100299 break;
300 }
301
302 /* walk down */
303 root = &old->node.branches;
Willy Tarreau3a932442010-05-09 19:29:23 +0200304 side = (new->key[old_node_bit >> 3] >> (~old_node_bit & 7)) & 1;
Willy Tarreauc2186022009-10-26 19:48:54 +0100305 troot = root->b[side];
306 }
307
308 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
309 * parent is already set to <new>, and the <root>'s branch is still in
310 * <side>. Update the root's leaf till we have it. Note that we can also
311 * find the side by checking the side of new->node.node_p.
312 */
313
314 /* We need the common higher bits between new->key and old->key.
315 * This number of bits is already in <bit>.
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200316 * NOTE: we can't get here whit bit < 0 since we found a dup !
Willy Tarreauc2186022009-10-26 19:48:54 +0100317 */
318 new->node.bit = bit;
319 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
320 return new;
321}
322
Willy Tarreau9e2e39e2009-11-02 14:43:39 +0100323#endif /* _EBSTTREE_H */
324