blob: 31a3a7147f23f14d7f31201c159030d864cf339c [file] [log] [blame]
Willy Tarreauc2186022009-10-26 19:48:54 +01001/*
2 * Elastic Binary Trees - macros for Indirect Multi-Byte data nodes.
Willy Tarreau414c4b22011-01-04 13:21:06 +01003 * Version 6.0.5
4 * (C) 2002-2011 - 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#include <string.h>
22#include "ebtree.h"
23#include "ebpttree.h"
24
25/* These functions and macros rely on Pointer nodes and use the <key> entry as
26 * a pointer to an indirect key. Most operations are performed using ebpt_*.
27 */
28
29/* The following functions are not inlined by default. They are declared
30 * in ebimtree.c, which simply relies on their inline version.
31 */
32REGPRM3 struct ebpt_node *ebim_lookup(struct eb_root *root, const void *x, unsigned int len);
33REGPRM3 struct ebpt_node *ebim_insert(struct eb_root *root, struct ebpt_node *new, unsigned int len);
34
Willy Tarreau414c4b22011-01-04 13:21:06 +010035/* Find the first occurence of a key of a least <len> bytes matching <x> in the
36 * tree <root>. The caller is responsible for ensuring that <len> will not exceed
37 * the common parts between the tree's keys and <x>. In case of multiple matches,
38 * the leftmost node is returned. This means that this function can be used to
39 * lookup string keys by prefix if all keys in the tree are zero-terminated. If
40 * no match is found, NULL is returned. Returns first node if <len> is zero.
Willy Tarreauc2186022009-10-26 19:48:54 +010041 */
42static forceinline struct ebpt_node *
43__ebim_lookup(struct eb_root *root, const void *x, unsigned int len)
44{
45 struct ebpt_node *node;
46 eb_troot_t *troot;
Willy Tarreau414c4b22011-01-04 13:21:06 +010047 int pos, side;
Willy Tarreau3a932442010-05-09 19:29:23 +020048 int node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +010049
50 troot = root->b[EB_LEFT];
51 if (unlikely(troot == NULL))
Willy Tarreauce3d44a2011-01-04 14:07:36 +010052 goto ret_null;
Willy Tarreauc2186022009-10-26 19:48:54 +010053
Willy Tarreau414c4b22011-01-04 13:21:06 +010054 if (unlikely(len == 0))
55 goto walk_down;
56
57 pos = 0;
Willy Tarreauc2186022009-10-26 19:48:54 +010058 while (1) {
Willy Tarreau414c4b22011-01-04 13:21:06 +010059 if (eb_gettag(troot) == EB_LEAF) {
Willy Tarreauc2186022009-10-26 19:48:54 +010060 node = container_of(eb_untag(troot, EB_LEAF),
61 struct ebpt_node, node.branches);
Willy Tarreau414c4b22011-01-04 13:21:06 +010062 if (memcmp(node->key + pos, x, len) != 0)
Willy Tarreauce3d44a2011-01-04 14:07:36 +010063 goto ret_null;
Willy Tarreau414c4b22011-01-04 13:21:06 +010064 else
Willy Tarreauce3d44a2011-01-04 14:07:36 +010065 goto ret_node;
Willy Tarreauc2186022009-10-26 19:48:54 +010066 }
67 node = container_of(eb_untag(troot, EB_NODE),
68 struct ebpt_node, node.branches);
69
Willy Tarreau3a932442010-05-09 19:29:23 +020070 node_bit = node->node.bit;
71 if (node_bit < 0) {
Willy Tarreauc2186022009-10-26 19:48:54 +010072 /* We have a dup tree now. Either it's for the same
73 * value, and we walk down left, or it's a different
74 * one and we don't have our key.
75 */
Willy Tarreau414c4b22011-01-04 13:21:06 +010076 if (memcmp(node->key + pos, x, len) != 0)
Willy Tarreauce3d44a2011-01-04 14:07:36 +010077 goto ret_null;
78 else
79 goto walk_left;
Willy Tarreauc2186022009-10-26 19:48:54 +010080 }
81
Willy Tarreau414c4b22011-01-04 13:21:06 +010082 /* OK, normal data node, let's walk down. We check if all full
83 * bytes are equal, and we start from the last one we did not
84 * completely check. We stop as soon as we reach the last byte,
85 * because we must decide to go left/right or abort.
86 */
87 node_bit = ~node_bit + (pos << 3) + 8; // = (pos<<3) + (7 - node_bit)
88 if (node_bit < 0) {
89 /* This surprizing construction gives better performance
90 * because gcc does not try to reorder the loop. Tested to
91 * be fine with 2.95 to 4.2.
92 */
93 while (1) {
94 if (*(unsigned char*)(node->key + pos++) ^ *(unsigned char*)(x++))
Willy Tarreauce3d44a2011-01-04 14:07:36 +010095 goto ret_null; /* more than one full byte is different */
Willy Tarreau414c4b22011-01-04 13:21:06 +010096 if (--len == 0)
97 goto walk_left; /* return first node if all bytes matched */
98 node_bit += 8;
99 if (node_bit >= 0)
100 break;
101 }
102 }
Willy Tarreauc2186022009-10-26 19:48:54 +0100103
Willy Tarreau414c4b22011-01-04 13:21:06 +0100104 /* here we know that only the last byte differs, so node_bit < 8.
105 * We have 2 possibilities :
106 * - more than the last bit differs => return NULL
107 * - walk down on side = (x[pos] >> node_bit) & 1
108 */
109 side = *(unsigned char *)x >> node_bit;
110 if (((*(unsigned char*)(node->key + pos) >> node_bit) ^ side) > 1)
Willy Tarreauce3d44a2011-01-04 14:07:36 +0100111 goto ret_null;
Willy Tarreau414c4b22011-01-04 13:21:06 +0100112 side &= 1;
113 troot = node->node.branches.b[side];
Willy Tarreauc2186022009-10-26 19:48:54 +0100114 }
Willy Tarreauce3d44a2011-01-04 14:07:36 +0100115 walk_left:
116 troot = node->node.branches.b[EB_LEFT];
117 walk_down:
118 while (eb_gettag(troot) != EB_LEAF)
119 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
120 node = container_of(eb_untag(troot, EB_LEAF),
121 struct ebpt_node, node.branches);
122 ret_node:
123 return node;
124 ret_null:
125 return NULL;
Willy Tarreauc2186022009-10-26 19:48:54 +0100126}
127
128/* Insert ebpt_node <new> into subtree starting at node root <root>.
129 * Only new->key needs be set with the key. The ebpt_node is returned.
130 * If root->b[EB_RGHT]==1, the tree may only contain unique keys. The
131 * len is specified in bytes.
132 */
133static forceinline struct ebpt_node *
134__ebim_insert(struct eb_root *root, struct ebpt_node *new, unsigned int len)
135{
136 struct ebpt_node *old;
137 unsigned int side;
138 eb_troot_t *troot;
139 eb_troot_t *root_right = root;
140 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 len <<= 3;
156
157 /* The tree descent is fairly easy :
158 * - first, check if we have reached a leaf node
159 * - second, check if we have gone too far
160 * - third, reiterate
161 * Everywhere, we use <new> for the node node we are inserting, <root>
162 * for the node we attach it to, and <old> for the node we are
163 * displacing below <new>. <troot> will always point to the future node
164 * (tagged with its type). <side> carries the side the node <new> is
165 * attached to below its parent, which is also where previous node
166 * was attached.
167 */
168
169 bit = 0;
170 while (1) {
171 if (unlikely(eb_gettag(troot) == EB_LEAF)) {
172 eb_troot_t *new_left, *new_rght;
173 eb_troot_t *new_leaf, *old_leaf;
174
175 old = container_of(eb_untag(troot, EB_LEAF),
176 struct ebpt_node, node.branches);
177
178 new_left = eb_dotag(&new->node.branches, EB_LEFT);
179 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
180 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
181 old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
182
183 new->node.node_p = old->node.leaf_p;
184
185 /* Right here, we have 3 possibilities :
186 * - the tree does not contain the key, and we have
187 * new->key < old->key. We insert new above old, on
188 * the left ;
189 *
190 * - the tree does not contain the key, and we have
191 * new->key > old->key. We insert new above old, on
192 * the right ;
193 *
194 * - the tree does contain the key, which implies it
195 * is alone. We add the new key next to it as a
196 * first duplicate.
197 *
198 * The last two cases can easily be partially merged.
199 */
200 bit = equal_bits(new->key, old->key, bit, len);
201 diff = cmp_bits(new->key, old->key, bit);
202
203 if (diff < 0) {
204 new->node.leaf_p = new_left;
205 old->node.leaf_p = new_rght;
206 new->node.branches.b[EB_LEFT] = new_leaf;
207 new->node.branches.b[EB_RGHT] = old_leaf;
208 } else {
209 /* we may refuse to duplicate this key if the tree is
210 * tagged as containing only unique keys.
211 */
212 if (diff == 0 && eb_gettag(root_right))
213 return old;
214
215 /* new->key >= old->key, new goes the right */
216 old->node.leaf_p = new_left;
217 new->node.leaf_p = new_rght;
218 new->node.branches.b[EB_LEFT] = old_leaf;
219 new->node.branches.b[EB_RGHT] = new_leaf;
220
221 if (diff == 0) {
222 new->node.bit = -1;
223 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
224 return new;
225 }
226 }
227 break;
228 }
229
230 /* OK we're walking down this link */
231 old = container_of(eb_untag(troot, EB_NODE),
232 struct ebpt_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200233 old_node_bit = old->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100234
235 /* Stop going down when we don't have common bits anymore. We
236 * also stop in front of a duplicates tree because it means we
237 * have to insert above. Note: we can compare more bits than
238 * the current node's because as long as they are identical, we
239 * know we descend along the correct side.
240 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200241 if (old_node_bit < 0) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100242 /* we're above a duplicate tree, we must compare till the end */
243 bit = equal_bits(new->key, old->key, bit, len);
244 goto dup_tree;
245 }
Willy Tarreau3a932442010-05-09 19:29:23 +0200246 else if (bit < old_node_bit) {
247 bit = equal_bits(new->key, old->key, bit, old_node_bit);
Willy Tarreauc2186022009-10-26 19:48:54 +0100248 }
249
Willy Tarreau3a932442010-05-09 19:29:23 +0200250 if (bit < old_node_bit) { /* we don't have all bits in common */
Willy Tarreauc2186022009-10-26 19:48:54 +0100251 /* The tree did not contain the key, so we insert <new> before the node
252 * <old>, and set ->bit to designate the lowest bit position in <new>
253 * which applies to ->branches.b[].
254 */
255 eb_troot_t *new_left, *new_rght;
256 eb_troot_t *new_leaf, *old_node;
257
258 dup_tree:
259 new_left = eb_dotag(&new->node.branches, EB_LEFT);
260 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
261 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
262 old_node = eb_dotag(&old->node.branches, EB_NODE);
263
264 new->node.node_p = old->node.node_p;
265
266 diff = cmp_bits(new->key, old->key, bit);
267 if (diff < 0) {
268 new->node.leaf_p = new_left;
269 old->node.node_p = new_rght;
270 new->node.branches.b[EB_LEFT] = new_leaf;
271 new->node.branches.b[EB_RGHT] = old_node;
272 }
273 else if (diff > 0) {
274 old->node.node_p = new_left;
275 new->node.leaf_p = new_rght;
276 new->node.branches.b[EB_LEFT] = old_node;
277 new->node.branches.b[EB_RGHT] = new_leaf;
278 }
279 else {
280 struct eb_node *ret;
281 ret = eb_insert_dup(&old->node, &new->node);
282 return container_of(ret, struct ebpt_node, node);
283 }
284 break;
285 }
286
287 /* walk down */
288 root = &old->node.branches;
Willy Tarreau3a932442010-05-09 19:29:23 +0200289 side = (((unsigned char *)new->key)[old_node_bit >> 3] >> (~old_node_bit & 7)) & 1;
Willy Tarreauc2186022009-10-26 19:48:54 +0100290 troot = root->b[side];
291 }
292
293 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
294 * parent is already set to <new>, and the <root>'s branch is still in
295 * <side>. Update the root's leaf till we have it. Note that we can also
296 * find the side by checking the side of new->node.node_p.
297 */
298
299 /* We need the common higher bits between new->key and old->key.
300 * This number of bits is already in <bit>.
301 */
302 new->node.bit = bit;
303 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
304 return new;
305}