blob: e1bcbc708866f374e6c6e7ca03145654e9db9906 [file] [log] [blame]
Willy Tarreauc2186022009-10-26 19:48:54 +01001/*
2 * Elastic Binary Trees - macros to manipulate Indirect 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 Tarreau20a81c22014-03-15 07:43:05 +010023#ifndef _EBISTREE_H
24#define _EBISTREE_H
25
Willy Tarreauc2186022009-10-26 19:48:54 +010026#include <string.h>
27#include "ebtree.h"
28#include "ebpttree.h"
Willy Tarreaue1ee9562011-01-04 14:33:13 +010029#include "ebimtree.h"
Willy Tarreauc2186022009-10-26 19:48:54 +010030
31/* These functions and macros rely on Pointer nodes and use the <key> entry as
32 * a pointer to an indirect key. Most operations are performed using ebpt_*.
33 */
34
35/* The following functions are not inlined by default. They are declared
36 * in ebistree.c, which simply relies on their inline version.
37 */
38REGPRM2 struct ebpt_node *ebis_lookup(struct eb_root *root, const char *x);
Willy Tarreauc2186022009-10-26 19:48:54 +010039REGPRM2 struct ebpt_node *ebis_insert(struct eb_root *root, struct ebpt_node *new);
40
Willy Tarreaue1ee9562011-01-04 14:33:13 +010041/* Find the first occurence of a length <len> string <x> in the tree <root>.
42 * It's the caller's reponsibility to use this function only on trees which
43 * only contain zero-terminated strings, and that no null character is present
44 * in string <x> in the first <len> chars. If none can be found, return NULL.
45 */
46static forceinline struct ebpt_node *
47ebis_lookup_len(struct eb_root *root, const char *x, unsigned int len)
48{
49 struct ebpt_node *node;
50
51 node = ebim_lookup(root, x, len);
52 if (!node || ((const char *)node->key)[len] != 0)
53 return NULL;
54 return node;
55}
56
Willy Tarreauc2186022009-10-26 19:48:54 +010057/* Find the first occurence of a zero-terminated string <x> in the tree <root>.
58 * It's the caller's reponsibility to use this function only on trees which
59 * only contain zero-terminated strings. If none can be found, return NULL.
60 */
61static forceinline struct ebpt_node *__ebis_lookup(struct eb_root *root, const void *x)
62{
63 struct ebpt_node *node;
64 eb_troot_t *troot;
Willy Tarreau3a932442010-05-09 19:29:23 +020065 int bit;
66 int node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +010067
68 troot = root->b[EB_LEFT];
69 if (unlikely(troot == NULL))
70 return NULL;
71
72 bit = 0;
73 while (1) {
74 if ((eb_gettag(troot) == EB_LEAF)) {
75 node = container_of(eb_untag(troot, EB_LEAF),
76 struct ebpt_node, node.branches);
77 if (strcmp(node->key, x) == 0)
78 return node;
79 else
80 return NULL;
81 }
82 node = container_of(eb_untag(troot, EB_NODE),
83 struct ebpt_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +020084 node_bit = node->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +010085
Willy Tarreau3a932442010-05-09 19:29:23 +020086 if (node_bit < 0) {
Willy Tarreauc2186022009-10-26 19:48:54 +010087 /* We have a dup tree now. Either it's for the same
88 * value, and we walk down left, or it's a different
89 * one and we don't have our key.
90 */
91 if (strcmp(node->key, x) != 0)
92 return NULL;
93
94 troot = node->node.branches.b[EB_LEFT];
95 while (eb_gettag(troot) != EB_LEAF)
96 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
97 node = container_of(eb_untag(troot, EB_LEAF),
98 struct ebpt_node, node.branches);
99 return node;
100 }
101
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200102 /* OK, normal data node, let's walk down but don't compare data
103 * if we already reached the end of the key.
104 */
105 if (likely(bit >= 0)) {
106 bit = string_equal_bits(x, node->key, bit);
107 if (likely(bit < node_bit)) {
108 if (bit >= 0)
109 return NULL; /* no more common bits */
110
111 /* bit < 0 : we reached the end of the key. If we
112 * are in a tree with unique keys, we can return
113 * this node. Otherwise we have to walk it down
114 * and stop comparing bits.
115 */
116 if (eb_gettag(root->b[EB_RGHT]))
117 return node;
118 }
Willy Tarreau007257e2011-11-14 14:09:27 +0100119 /* if the bit is larger than the node's, we must bound it
120 * because we might have compared too many bytes with an
121 * inappropriate leaf. For a test, build a tree from "0",
122 * "WW", "W", "S" inserted in this exact sequence and lookup
123 * "W" => "S" is returned without this assignment.
124 */
125 else
126 bit = node_bit;
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200127 }
Willy Tarreauc2186022009-10-26 19:48:54 +0100128
Willy Tarreau3a932442010-05-09 19:29:23 +0200129 troot = node->node.branches.b[(((unsigned char*)x)[node_bit >> 3] >>
130 (~node_bit & 7)) & 1];
Willy Tarreauc2186022009-10-26 19:48:54 +0100131 }
132}
133
134/* Insert ebpt_node <new> into subtree starting at node root <root>. Only
135 * new->key needs be set with the zero-terminated string key. The ebpt_node is
136 * returned. If root->b[EB_RGHT]==1, the tree may only contain unique keys. The
137 * caller is responsible for properly terminating the key with a zero.
138 */
139static forceinline struct ebpt_node *
140__ebis_insert(struct eb_root *root, struct ebpt_node *new)
141{
142 struct ebpt_node *old;
143 unsigned int side;
144 eb_troot_t *troot;
Willy Tarreau6258f7b2011-09-19 20:48:00 +0200145 eb_troot_t *root_right;
Willy Tarreauc2186022009-10-26 19:48:54 +0100146 int diff;
147 int bit;
Willy Tarreau3a932442010-05-09 19:29:23 +0200148 int old_node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100149
150 side = EB_LEFT;
151 troot = root->b[EB_LEFT];
152 root_right = root->b[EB_RGHT];
153 if (unlikely(troot == NULL)) {
154 /* Tree is empty, insert the leaf part below the left branch */
155 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
156 new->node.leaf_p = eb_dotag(root, EB_LEFT);
157 new->node.node_p = NULL; /* node part unused */
158 return new;
159 }
160
161 /* The tree descent is fairly easy :
162 * - first, check if we have reached a leaf node
163 * - second, check if we have gone too far
164 * - third, reiterate
165 * Everywhere, we use <new> for the node node we are inserting, <root>
166 * for the node we attach it to, and <old> for the node we are
167 * displacing below <new>. <troot> will always point to the future node
168 * (tagged with its type). <side> carries the side the node <new> is
169 * attached to below its parent, which is also where previous node
170 * was attached.
171 */
172
173 bit = 0;
174 while (1) {
175 if (unlikely(eb_gettag(troot) == EB_LEAF)) {
176 eb_troot_t *new_left, *new_rght;
177 eb_troot_t *new_leaf, *old_leaf;
178
179 old = container_of(eb_untag(troot, EB_LEAF),
180 struct ebpt_node, node.branches);
181
182 new_left = eb_dotag(&new->node.branches, EB_LEFT);
183 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
184 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
185 old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
186
187 new->node.node_p = old->node.leaf_p;
188
189 /* Right here, we have 3 possibilities :
190 * - the tree does not contain the key, and we have
191 * new->key < old->key. We insert new above old, on
192 * the left ;
193 *
194 * - the tree does not contain the key, and we have
195 * new->key > old->key. We insert new above old, on
196 * the right ;
197 *
198 * - the tree does contain the key, which implies it
199 * is alone. We add the new key next to it as a
200 * first duplicate.
201 *
202 * The last two cases can easily be partially merged.
203 */
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200204 if (bit >= 0)
205 bit = string_equal_bits(new->key, old->key, bit);
Willy Tarreauc2186022009-10-26 19:48:54 +0100206
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200207 if (bit < 0) {
208 /* key was already there */
209
Willy Tarreauc2186022009-10-26 19:48:54 +0100210 /* we may refuse to duplicate this key if the tree is
211 * tagged as containing only unique keys.
212 */
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200213 if (eb_gettag(root_right))
Willy Tarreauc2186022009-10-26 19:48:54 +0100214 return old;
215
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200216 /* new arbitrarily goes to the right and tops the dup tree */
Willy Tarreauc2186022009-10-26 19:48:54 +0100217 old->node.leaf_p = new_left;
218 new->node.leaf_p = new_rght;
219 new->node.branches.b[EB_LEFT] = old_leaf;
220 new->node.branches.b[EB_RGHT] = new_leaf;
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200221 new->node.bit = -1;
222 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
223 return new;
224 }
Willy Tarreauc2186022009-10-26 19:48:54 +0100225
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200226 diff = cmp_bits(new->key, old->key, bit);
227 if (diff < 0) {
228 /* new->key < old->key, new takes the left */
229 new->node.leaf_p = new_left;
230 old->node.leaf_p = new_rght;
231 new->node.branches.b[EB_LEFT] = new_leaf;
232 new->node.branches.b[EB_RGHT] = old_leaf;
233 } else {
234 /* new->key > old->key, new takes the right */
235 old->node.leaf_p = new_left;
236 new->node.leaf_p = new_rght;
237 new->node.branches.b[EB_LEFT] = old_leaf;
238 new->node.branches.b[EB_RGHT] = new_leaf;
Willy Tarreauc2186022009-10-26 19:48:54 +0100239 }
240 break;
241 }
242
243 /* OK we're walking down this link */
244 old = container_of(eb_untag(troot, EB_NODE),
245 struct ebpt_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200246 old_node_bit = old->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100247
248 /* Stop going down when we don't have common bits anymore. We
249 * also stop in front of a duplicates tree because it means we
250 * have to insert above. Note: we can compare more bits than
251 * the current node's because as long as they are identical, we
252 * know we descend along the correct side.
253 */
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200254 if (bit >= 0 && (bit < old_node_bit || old_node_bit < 0))
Willy Tarreauc2186022009-10-26 19:48:54 +0100255 bit = string_equal_bits(new->key, old->key, bit);
Willy Tarreauc2186022009-10-26 19:48:54 +0100256
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200257 if (unlikely(bit < 0)) {
258 /* Perfect match, we must only stop on head of dup tree
259 * or walk down to a leaf.
260 */
261 if (old_node_bit < 0) {
262 /* We know here that string_equal_bits matched all
263 * bits and that we're on top of a dup tree, then
264 * we can perform the dup insertion and return.
265 */
266 struct eb_node *ret;
267 ret = eb_insert_dup(&old->node, &new->node);
268 return container_of(ret, struct ebpt_node, node);
269 }
270 /* OK so let's walk down */
271 }
272 else if (bit < old_node_bit || old_node_bit < 0) {
273 /* The tree did not contain the key, or we stopped on top of a dup
274 * tree, possibly containing the key. In the former case, we insert
275 * <new> before the node <old>, and set ->bit to designate the lowest
276 * bit position in <new> which applies to ->branches.b[]. In the later
277 * case, we add the key to the existing dup tree. Note that we cannot
278 * enter here if we match an intermediate node's key that is not the
279 * head of a dup tree.
Willy Tarreauc2186022009-10-26 19:48:54 +0100280 */
281 eb_troot_t *new_left, *new_rght;
282 eb_troot_t *new_leaf, *old_node;
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200283
Willy Tarreauc2186022009-10-26 19:48:54 +0100284 new_left = eb_dotag(&new->node.branches, EB_LEFT);
285 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
286 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
287 old_node = eb_dotag(&old->node.branches, EB_NODE);
288
289 new->node.node_p = old->node.node_p;
290
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200291 /* we can never match all bits here */
Willy Tarreauc2186022009-10-26 19:48:54 +0100292 diff = cmp_bits(new->key, old->key, bit);
293 if (diff < 0) {
294 new->node.leaf_p = new_left;
295 old->node.node_p = new_rght;
296 new->node.branches.b[EB_LEFT] = new_leaf;
297 new->node.branches.b[EB_RGHT] = old_node;
298 }
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200299 else {
Willy Tarreauc2186022009-10-26 19:48:54 +0100300 old->node.node_p = new_left;
301 new->node.leaf_p = new_rght;
302 new->node.branches.b[EB_LEFT] = old_node;
303 new->node.branches.b[EB_RGHT] = new_leaf;
304 }
Willy Tarreauc2186022009-10-26 19:48:54 +0100305 break;
306 }
307
308 /* walk down */
309 root = &old->node.branches;
Willy Tarreau3a932442010-05-09 19:29:23 +0200310 side = (((unsigned char *)new->key)[old_node_bit >> 3] >> (~old_node_bit & 7)) & 1;
Willy Tarreauc2186022009-10-26 19:48:54 +0100311 troot = root->b[side];
312 }
313
314 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
315 * parent is already set to <new>, and the <root>'s branch is still in
316 * <side>. Update the root's leaf till we have it. Note that we can also
317 * find the side by checking the side of new->node.node_p.
318 */
319
320 /* We need the common higher bits between new->key and old->key.
321 * This number of bits is already in <bit>.
Willy Tarreaub55fcf22010-10-28 22:48:29 +0200322 * NOTE: we can't get here whit bit < 0 since we found a dup !
Willy Tarreauc2186022009-10-26 19:48:54 +0100323 */
324 new->node.bit = bit;
325 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
326 return new;
327}
328
Willy Tarreau20a81c22014-03-15 07:43:05 +0100329#endif /* _EBISTREE_H */