blob: ff2feee44eb6a2b3335a581d93a45d62decb381c [file] [log] [blame]
Willy Tarreauc2186022009-10-26 19:48:54 +01001/*
2 * Elastic Binary Trees - macros and structures for operations on 64bit nodes.
Willy Tarreauf3bfede2011-07-25 11:38:17 +02003 * Version 6.0.6
4 * (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#ifndef _EB64TREE_H
22#define _EB64TREE_H
23
24#include "ebtree.h"
25
26
27/* Return the structure of type <type> whose member <member> points to <ptr> */
28#define eb64_entry(ptr, type, member) container_of(ptr, type, member)
29
30#define EB64_ROOT EB_ROOT
31#define EB64_TREE_HEAD EB_TREE_HEAD
32
33/* These types may sometimes already be defined */
34typedef unsigned long long u64;
35typedef signed long long s64;
36
37/* This structure carries a node, a leaf, and a key. It must start with the
38 * eb_node so that it can be cast into an eb_node. We could also have put some
39 * sort of transparent union here to reduce the indirection level, but the fact
40 * is, the end user is not meant to manipulate internals, so this is pointless.
Willy Tarreau41136de2020-02-22 15:55:33 +010041 * In case sizeof(void*)>=sizeof(u64), we know there will be some padding after
42 * the key if it's unaligned. In this case we force the alignment on void* so
43 * that we prefer to have the padding before for more efficient accesses.
Willy Tarreauc2186022009-10-26 19:48:54 +010044 */
45struct eb64_node {
46 struct eb_node node; /* the tree node, must be at the beginning */
Willy Tarreau41136de2020-02-22 15:55:33 +010047 MAYBE_ALIGN(sizeof(u64));
48 ALWAYS_ALIGN(sizeof(void*));
Willy Tarreauc2186022009-10-26 19:48:54 +010049 u64 key;
Willy Tarreau41136de2020-02-22 15:55:33 +010050} ALIGNED(sizeof(void*));
Willy Tarreauc2186022009-10-26 19:48:54 +010051
52/*
53 * Exported functions and macros.
54 * Many of them are always inlined because they are extremely small, and
55 * are generally called at most once or twice in a program.
56 */
57
58/* Return leftmost node in the tree, or NULL if none */
59static inline struct eb64_node *eb64_first(struct eb_root *root)
60{
61 return eb64_entry(eb_first(root), struct eb64_node, node);
62}
63
64/* Return rightmost node in the tree, or NULL if none */
65static inline struct eb64_node *eb64_last(struct eb_root *root)
66{
67 return eb64_entry(eb_last(root), struct eb64_node, node);
68}
69
70/* Return next node in the tree, or NULL if none */
71static inline struct eb64_node *eb64_next(struct eb64_node *eb64)
72{
73 return eb64_entry(eb_next(&eb64->node), struct eb64_node, node);
74}
75
76/* Return previous node in the tree, or NULL if none */
77static inline struct eb64_node *eb64_prev(struct eb64_node *eb64)
78{
79 return eb64_entry(eb_prev(&eb64->node), struct eb64_node, node);
80}
81
Willy Tarreau2b570202013-05-07 15:58:28 +020082/* Return next leaf node within a duplicate sub-tree, or NULL if none. */
83static inline struct eb64_node *eb64_next_dup(struct eb64_node *eb64)
84{
85 return eb64_entry(eb_next_dup(&eb64->node), struct eb64_node, node);
86}
87
88/* Return previous leaf node within a duplicate sub-tree, or NULL if none. */
89static inline struct eb64_node *eb64_prev_dup(struct eb64_node *eb64)
90{
91 return eb64_entry(eb_prev_dup(&eb64->node), struct eb64_node, node);
92}
93
Willy Tarreauc2186022009-10-26 19:48:54 +010094/* Return next node in the tree, skipping duplicates, or NULL if none */
95static inline struct eb64_node *eb64_next_unique(struct eb64_node *eb64)
96{
97 return eb64_entry(eb_next_unique(&eb64->node), struct eb64_node, node);
98}
99
100/* Return previous node in the tree, skipping duplicates, or NULL if none */
101static inline struct eb64_node *eb64_prev_unique(struct eb64_node *eb64)
102{
103 return eb64_entry(eb_prev_unique(&eb64->node), struct eb64_node, node);
104}
105
106/* Delete node from the tree if it was linked in. Mark the node unused. Note
107 * that this function relies on a non-inlined generic function: eb_delete.
108 */
109static inline void eb64_delete(struct eb64_node *eb64)
110{
111 eb_delete(&eb64->node);
112}
113
114/*
115 * The following functions are not inlined by default. They are declared
116 * in eb64tree.c, which simply relies on their inline version.
117 */
Willy Tarreau03e78532020-02-25 07:38:05 +0100118struct eb64_node *eb64_lookup(struct eb_root *root, u64 x);
119struct eb64_node *eb64i_lookup(struct eb_root *root, s64 x);
120struct eb64_node *eb64_lookup_le(struct eb_root *root, u64 x);
121struct eb64_node *eb64_lookup_ge(struct eb_root *root, u64 x);
122struct eb64_node *eb64_insert(struct eb_root *root, struct eb64_node *new);
123struct eb64_node *eb64i_insert(struct eb_root *root, struct eb64_node *new);
Willy Tarreauc2186022009-10-26 19:48:54 +0100124
125/*
126 * The following functions are less likely to be used directly, because their
127 * code is larger. The non-inlined version is preferred.
128 */
129
130/* Delete node from the tree if it was linked in. Mark the node unused. */
131static forceinline void __eb64_delete(struct eb64_node *eb64)
132{
133 __eb_delete(&eb64->node);
134}
135
136/*
Joseph Herlant7c16c0e2018-11-13 19:55:57 -0800137 * Find the first occurrence of a key in the tree <root>. If none can be
Willy Tarreauc2186022009-10-26 19:48:54 +0100138 * found, return NULL.
139 */
140static forceinline struct eb64_node *__eb64_lookup(struct eb_root *root, u64 x)
141{
142 struct eb64_node *node;
143 eb_troot_t *troot;
144 u64 y;
145
146 troot = root->b[EB_LEFT];
147 if (unlikely(troot == NULL))
148 return NULL;
149
150 while (1) {
151 if ((eb_gettag(troot) == EB_LEAF)) {
152 node = container_of(eb_untag(troot, EB_LEAF),
153 struct eb64_node, node.branches);
154 if (node->key == x)
155 return node;
156 else
157 return NULL;
158 }
159 node = container_of(eb_untag(troot, EB_NODE),
160 struct eb64_node, node.branches);
161
162 y = node->key ^ x;
163 if (!y) {
164 /* Either we found the node which holds the key, or
165 * we have a dup tree. In the later case, we have to
166 * walk it down left to get the first entry.
167 */
168 if (node->node.bit < 0) {
169 troot = node->node.branches.b[EB_LEFT];
170 while (eb_gettag(troot) != EB_LEAF)
171 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
172 node = container_of(eb_untag(troot, EB_LEAF),
173 struct eb64_node, node.branches);
174 }
175 return node;
176 }
177
178 if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
179 return NULL; /* no more common bits */
180
181 troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
182 }
183}
184
185/*
Joseph Herlant7c16c0e2018-11-13 19:55:57 -0800186 * Find the first occurrence of a signed key in the tree <root>. If none can
Willy Tarreauc2186022009-10-26 19:48:54 +0100187 * be found, return NULL.
188 */
189static forceinline struct eb64_node *__eb64i_lookup(struct eb_root *root, s64 x)
190{
191 struct eb64_node *node;
192 eb_troot_t *troot;
193 u64 key = x ^ (1ULL << 63);
194 u64 y;
195
196 troot = root->b[EB_LEFT];
197 if (unlikely(troot == NULL))
198 return NULL;
199
200 while (1) {
201 if ((eb_gettag(troot) == EB_LEAF)) {
202 node = container_of(eb_untag(troot, EB_LEAF),
203 struct eb64_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200204 if (node->key == (u64)x)
Willy Tarreauc2186022009-10-26 19:48:54 +0100205 return node;
206 else
207 return NULL;
208 }
209 node = container_of(eb_untag(troot, EB_NODE),
210 struct eb64_node, node.branches);
211
212 y = node->key ^ x;
213 if (!y) {
214 /* Either we found the node which holds the key, or
215 * we have a dup tree. In the later case, we have to
216 * walk it down left to get the first entry.
217 */
218 if (node->node.bit < 0) {
219 troot = node->node.branches.b[EB_LEFT];
220 while (eb_gettag(troot) != EB_LEAF)
221 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
222 node = container_of(eb_untag(troot, EB_LEAF),
223 struct eb64_node, node.branches);
224 }
225 return node;
226 }
227
228 if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
229 return NULL; /* no more common bits */
230
231 troot = node->node.branches.b[(key >> node->node.bit) & EB_NODE_BRANCH_MASK];
232 }
233}
234
235/* Insert eb64_node <new> into subtree starting at node root <root>.
236 * Only new->key needs be set with the key. The eb64_node is returned.
237 * If root->b[EB_RGHT]==1, the tree may only contain unique keys.
238 */
239static forceinline struct eb64_node *
240__eb64_insert(struct eb_root *root, struct eb64_node *new) {
241 struct eb64_node *old;
242 unsigned int side;
243 eb_troot_t *troot;
244 u64 newkey; /* caching the key saves approximately one cycle */
Willy Tarreau6258f7b2011-09-19 20:48:00 +0200245 eb_troot_t *root_right;
Willy Tarreau3a932442010-05-09 19:29:23 +0200246 int old_node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100247
248 side = EB_LEFT;
249 troot = root->b[EB_LEFT];
250 root_right = root->b[EB_RGHT];
251 if (unlikely(troot == NULL)) {
252 /* Tree is empty, insert the leaf part below the left branch */
253 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
254 new->node.leaf_p = eb_dotag(root, EB_LEFT);
255 new->node.node_p = NULL; /* node part unused */
256 return new;
257 }
258
259 /* The tree descent is fairly easy :
260 * - first, check if we have reached a leaf node
261 * - second, check if we have gone too far
262 * - third, reiterate
263 * Everywhere, we use <new> for the node node we are inserting, <root>
264 * for the node we attach it to, and <old> for the node we are
265 * displacing below <new>. <troot> will always point to the future node
266 * (tagged with its type). <side> carries the side the node <new> is
267 * attached to below its parent, which is also where previous node
268 * was attached. <newkey> carries the key being inserted.
269 */
270 newkey = new->key;
271
272 while (1) {
273 if (unlikely(eb_gettag(troot) == EB_LEAF)) {
274 eb_troot_t *new_left, *new_rght;
275 eb_troot_t *new_leaf, *old_leaf;
276
277 old = container_of(eb_untag(troot, EB_LEAF),
278 struct eb64_node, node.branches);
279
280 new_left = eb_dotag(&new->node.branches, EB_LEFT);
281 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
282 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
283 old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
284
285 new->node.node_p = old->node.leaf_p;
286
287 /* Right here, we have 3 possibilities :
288 - the tree does not contain the key, and we have
289 new->key < old->key. We insert new above old, on
290 the left ;
291
292 - the tree does not contain the key, and we have
293 new->key > old->key. We insert new above old, on
294 the right ;
295
296 - the tree does contain the key, which implies it
297 is alone. We add the new key next to it as a
298 first duplicate.
299
300 The last two cases can easily be partially merged.
301 */
302
303 if (new->key < old->key) {
304 new->node.leaf_p = new_left;
305 old->node.leaf_p = new_rght;
306 new->node.branches.b[EB_LEFT] = new_leaf;
307 new->node.branches.b[EB_RGHT] = old_leaf;
308 } else {
309 /* we may refuse to duplicate this key if the tree is
310 * tagged as containing only unique keys.
311 */
312 if ((new->key == old->key) && eb_gettag(root_right))
313 return old;
314
315 /* new->key >= old->key, new goes the right */
316 old->node.leaf_p = new_left;
317 new->node.leaf_p = new_rght;
318 new->node.branches.b[EB_LEFT] = old_leaf;
319 new->node.branches.b[EB_RGHT] = new_leaf;
320
321 if (new->key == old->key) {
322 new->node.bit = -1;
323 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
324 return new;
325 }
326 }
327 break;
328 }
329
330 /* OK we're walking down this link */
331 old = container_of(eb_untag(troot, EB_NODE),
332 struct eb64_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200333 old_node_bit = old->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100334
335 /* Stop going down when we don't have common bits anymore. We
336 * also stop in front of a duplicates tree because it means we
337 * have to insert above.
338 */
339
Willy Tarreau3a932442010-05-09 19:29:23 +0200340 if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
341 (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100342 /* The tree did not contain the key, so we insert <new> before the node
343 * <old>, and set ->bit to designate the lowest bit position in <new>
344 * which applies to ->branches.b[].
345 */
346 eb_troot_t *new_left, *new_rght;
347 eb_troot_t *new_leaf, *old_node;
348
349 new_left = eb_dotag(&new->node.branches, EB_LEFT);
350 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
351 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
352 old_node = eb_dotag(&old->node.branches, EB_NODE);
353
354 new->node.node_p = old->node.node_p;
355
356 if (new->key < old->key) {
357 new->node.leaf_p = new_left;
358 old->node.node_p = new_rght;
359 new->node.branches.b[EB_LEFT] = new_leaf;
360 new->node.branches.b[EB_RGHT] = old_node;
361 }
362 else if (new->key > old->key) {
363 old->node.node_p = new_left;
364 new->node.leaf_p = new_rght;
365 new->node.branches.b[EB_LEFT] = old_node;
366 new->node.branches.b[EB_RGHT] = new_leaf;
367 }
368 else {
369 struct eb_node *ret;
370 ret = eb_insert_dup(&old->node, &new->node);
371 return container_of(ret, struct eb64_node, node);
372 }
373 break;
374 }
375
376 /* walk down */
377 root = &old->node.branches;
378#if BITS_PER_LONG >= 64
Willy Tarreau3a932442010-05-09 19:29:23 +0200379 side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;
Willy Tarreauc2186022009-10-26 19:48:54 +0100380#else
381 side = newkey;
Willy Tarreau3a932442010-05-09 19:29:23 +0200382 side >>= old_node_bit;
383 if (old_node_bit >= 32) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100384 side = newkey >> 32;
Willy Tarreau3a932442010-05-09 19:29:23 +0200385 side >>= old_node_bit & 0x1F;
Willy Tarreauc2186022009-10-26 19:48:54 +0100386 }
387 side &= EB_NODE_BRANCH_MASK;
388#endif
389 troot = root->b[side];
390 }
391
392 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
393 * parent is already set to <new>, and the <root>'s branch is still in
394 * <side>. Update the root's leaf till we have it. Note that we can also
395 * find the side by checking the side of new->node.node_p.
396 */
397
398 /* We need the common higher bits between new->key and old->key.
399 * What differences are there between new->key and the node here ?
400 * NOTE that bit(new) is always < bit(root) because highest
401 * bit of new->key and old->key are identical here (otherwise they
402 * would sit on different branches).
403 */
404 // note that if EB_NODE_BITS > 1, we should check that it's still >= 0
405 new->node.bit = fls64(new->key ^ old->key) - EB_NODE_BITS;
406 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
407
408 return new;
409}
410
411/* Insert eb64_node <new> into subtree starting at node root <root>, using
412 * signed keys. Only new->key needs be set with the key. The eb64_node
413 * is returned. If root->b[EB_RGHT]==1, the tree may only contain unique keys.
414 */
415static forceinline struct eb64_node *
416__eb64i_insert(struct eb_root *root, struct eb64_node *new) {
417 struct eb64_node *old;
418 unsigned int side;
419 eb_troot_t *troot;
420 u64 newkey; /* caching the key saves approximately one cycle */
Willy Tarreau6258f7b2011-09-19 20:48:00 +0200421 eb_troot_t *root_right;
Willy Tarreau3a932442010-05-09 19:29:23 +0200422 int old_node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100423
424 side = EB_LEFT;
425 troot = root->b[EB_LEFT];
426 root_right = root->b[EB_RGHT];
427 if (unlikely(troot == NULL)) {
428 /* Tree is empty, insert the leaf part below the left branch */
429 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
430 new->node.leaf_p = eb_dotag(root, EB_LEFT);
431 new->node.node_p = NULL; /* node part unused */
432 return new;
433 }
434
435 /* The tree descent is fairly easy :
436 * - first, check if we have reached a leaf node
437 * - second, check if we have gone too far
438 * - third, reiterate
439 * Everywhere, we use <new> for the node node we are inserting, <root>
440 * for the node we attach it to, and <old> for the node we are
441 * displacing below <new>. <troot> will always point to the future node
442 * (tagged with its type). <side> carries the side the node <new> is
443 * attached to below its parent, which is also where previous node
444 * was attached. <newkey> carries a high bit shift of the key being
445 * inserted in order to have negative keys stored before positive
446 * ones.
447 */
448 newkey = new->key ^ (1ULL << 63);
449
450 while (1) {
451 if (unlikely(eb_gettag(troot) == EB_LEAF)) {
452 eb_troot_t *new_left, *new_rght;
453 eb_troot_t *new_leaf, *old_leaf;
454
455 old = container_of(eb_untag(troot, EB_LEAF),
456 struct eb64_node, node.branches);
457
458 new_left = eb_dotag(&new->node.branches, EB_LEFT);
459 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
460 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
461 old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
462
463 new->node.node_p = old->node.leaf_p;
464
465 /* Right here, we have 3 possibilities :
466 - the tree does not contain the key, and we have
467 new->key < old->key. We insert new above old, on
468 the left ;
469
470 - the tree does not contain the key, and we have
471 new->key > old->key. We insert new above old, on
472 the right ;
473
474 - the tree does contain the key, which implies it
475 is alone. We add the new key next to it as a
476 first duplicate.
477
478 The last two cases can easily be partially merged.
479 */
480
481 if ((s64)new->key < (s64)old->key) {
482 new->node.leaf_p = new_left;
483 old->node.leaf_p = new_rght;
484 new->node.branches.b[EB_LEFT] = new_leaf;
485 new->node.branches.b[EB_RGHT] = old_leaf;
486 } else {
487 /* we may refuse to duplicate this key if the tree is
488 * tagged as containing only unique keys.
489 */
490 if ((new->key == old->key) && eb_gettag(root_right))
491 return old;
492
493 /* new->key >= old->key, new goes the right */
494 old->node.leaf_p = new_left;
495 new->node.leaf_p = new_rght;
496 new->node.branches.b[EB_LEFT] = old_leaf;
497 new->node.branches.b[EB_RGHT] = new_leaf;
498
499 if (new->key == old->key) {
500 new->node.bit = -1;
501 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
502 return new;
503 }
504 }
505 break;
506 }
507
508 /* OK we're walking down this link */
509 old = container_of(eb_untag(troot, EB_NODE),
510 struct eb64_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200511 old_node_bit = old->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100512
513 /* Stop going down when we don't have common bits anymore. We
514 * also stop in front of a duplicates tree because it means we
515 * have to insert above.
516 */
517
Willy Tarreau3a932442010-05-09 19:29:23 +0200518 if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
519 (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100520 /* The tree did not contain the key, so we insert <new> before the node
521 * <old>, and set ->bit to designate the lowest bit position in <new>
522 * which applies to ->branches.b[].
523 */
524 eb_troot_t *new_left, *new_rght;
525 eb_troot_t *new_leaf, *old_node;
526
527 new_left = eb_dotag(&new->node.branches, EB_LEFT);
528 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
529 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
530 old_node = eb_dotag(&old->node.branches, EB_NODE);
531
532 new->node.node_p = old->node.node_p;
533
534 if ((s64)new->key < (s64)old->key) {
535 new->node.leaf_p = new_left;
536 old->node.node_p = new_rght;
537 new->node.branches.b[EB_LEFT] = new_leaf;
538 new->node.branches.b[EB_RGHT] = old_node;
539 }
540 else if ((s64)new->key > (s64)old->key) {
541 old->node.node_p = new_left;
542 new->node.leaf_p = new_rght;
543 new->node.branches.b[EB_LEFT] = old_node;
544 new->node.branches.b[EB_RGHT] = new_leaf;
545 }
546 else {
547 struct eb_node *ret;
548 ret = eb_insert_dup(&old->node, &new->node);
549 return container_of(ret, struct eb64_node, node);
550 }
551 break;
552 }
553
554 /* walk down */
555 root = &old->node.branches;
556#if BITS_PER_LONG >= 64
Willy Tarreau3a932442010-05-09 19:29:23 +0200557 side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;
Willy Tarreauc2186022009-10-26 19:48:54 +0100558#else
559 side = newkey;
Willy Tarreau3a932442010-05-09 19:29:23 +0200560 side >>= old_node_bit;
561 if (old_node_bit >= 32) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100562 side = newkey >> 32;
Willy Tarreau3a932442010-05-09 19:29:23 +0200563 side >>= old_node_bit & 0x1F;
Willy Tarreauc2186022009-10-26 19:48:54 +0100564 }
565 side &= EB_NODE_BRANCH_MASK;
566#endif
567 troot = root->b[side];
568 }
569
570 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
571 * parent is already set to <new>, and the <root>'s branch is still in
572 * <side>. Update the root's leaf till we have it. Note that we can also
573 * find the side by checking the side of new->node.node_p.
574 */
575
576 /* We need the common higher bits between new->key and old->key.
577 * What differences are there between new->key and the node here ?
578 * NOTE that bit(new) is always < bit(root) because highest
579 * bit of new->key and old->key are identical here (otherwise they
580 * would sit on different branches).
581 */
582 // note that if EB_NODE_BITS > 1, we should check that it's still >= 0
583 new->node.bit = fls64(new->key ^ old->key) - EB_NODE_BITS;
584 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
585
586 return new;
587}
588
589#endif /* _EB64_TREE_H */