blob: 6d0d03910e0c8c8530cf1d1f06b3917c39c82ef7 [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.
41 */
42struct eb64_node {
43 struct eb_node node; /* the tree node, must be at the beginning */
44 u64 key;
45};
46
47/*
48 * Exported functions and macros.
49 * Many of them are always inlined because they are extremely small, and
50 * are generally called at most once or twice in a program.
51 */
52
53/* Return leftmost node in the tree, or NULL if none */
54static inline struct eb64_node *eb64_first(struct eb_root *root)
55{
56 return eb64_entry(eb_first(root), struct eb64_node, node);
57}
58
59/* Return rightmost node in the tree, or NULL if none */
60static inline struct eb64_node *eb64_last(struct eb_root *root)
61{
62 return eb64_entry(eb_last(root), struct eb64_node, node);
63}
64
65/* Return next node in the tree, or NULL if none */
66static inline struct eb64_node *eb64_next(struct eb64_node *eb64)
67{
68 return eb64_entry(eb_next(&eb64->node), struct eb64_node, node);
69}
70
71/* Return previous node in the tree, or NULL if none */
72static inline struct eb64_node *eb64_prev(struct eb64_node *eb64)
73{
74 return eb64_entry(eb_prev(&eb64->node), struct eb64_node, node);
75}
76
Willy Tarreau2b570202013-05-07 15:58:28 +020077/* Return next leaf node within a duplicate sub-tree, or NULL if none. */
78static inline struct eb64_node *eb64_next_dup(struct eb64_node *eb64)
79{
80 return eb64_entry(eb_next_dup(&eb64->node), struct eb64_node, node);
81}
82
83/* Return previous leaf node within a duplicate sub-tree, or NULL if none. */
84static inline struct eb64_node *eb64_prev_dup(struct eb64_node *eb64)
85{
86 return eb64_entry(eb_prev_dup(&eb64->node), struct eb64_node, node);
87}
88
Willy Tarreauc2186022009-10-26 19:48:54 +010089/* Return next node in the tree, skipping duplicates, or NULL if none */
90static inline struct eb64_node *eb64_next_unique(struct eb64_node *eb64)
91{
92 return eb64_entry(eb_next_unique(&eb64->node), struct eb64_node, node);
93}
94
95/* Return previous node in the tree, skipping duplicates, or NULL if none */
96static inline struct eb64_node *eb64_prev_unique(struct eb64_node *eb64)
97{
98 return eb64_entry(eb_prev_unique(&eb64->node), struct eb64_node, node);
99}
100
101/* Delete node from the tree if it was linked in. Mark the node unused. Note
102 * that this function relies on a non-inlined generic function: eb_delete.
103 */
104static inline void eb64_delete(struct eb64_node *eb64)
105{
106 eb_delete(&eb64->node);
107}
108
109/*
110 * The following functions are not inlined by default. They are declared
111 * in eb64tree.c, which simply relies on their inline version.
112 */
113REGPRM2 struct eb64_node *eb64_lookup(struct eb_root *root, u64 x);
114REGPRM2 struct eb64_node *eb64i_lookup(struct eb_root *root, s64 x);
115REGPRM2 struct eb64_node *eb64_lookup_le(struct eb_root *root, u64 x);
116REGPRM2 struct eb64_node *eb64_lookup_ge(struct eb_root *root, u64 x);
117REGPRM2 struct eb64_node *eb64_insert(struct eb_root *root, struct eb64_node *new);
118REGPRM2 struct eb64_node *eb64i_insert(struct eb_root *root, struct eb64_node *new);
119
120/*
121 * The following functions are less likely to be used directly, because their
122 * code is larger. The non-inlined version is preferred.
123 */
124
125/* Delete node from the tree if it was linked in. Mark the node unused. */
126static forceinline void __eb64_delete(struct eb64_node *eb64)
127{
128 __eb_delete(&eb64->node);
129}
130
131/*
Joseph Herlant7c16c0e2018-11-13 19:55:57 -0800132 * Find the first occurrence of a key in the tree <root>. If none can be
Willy Tarreauc2186022009-10-26 19:48:54 +0100133 * found, return NULL.
134 */
135static forceinline struct eb64_node *__eb64_lookup(struct eb_root *root, u64 x)
136{
137 struct eb64_node *node;
138 eb_troot_t *troot;
139 u64 y;
140
141 troot = root->b[EB_LEFT];
142 if (unlikely(troot == NULL))
143 return NULL;
144
145 while (1) {
146 if ((eb_gettag(troot) == EB_LEAF)) {
147 node = container_of(eb_untag(troot, EB_LEAF),
148 struct eb64_node, node.branches);
149 if (node->key == x)
150 return node;
151 else
152 return NULL;
153 }
154 node = container_of(eb_untag(troot, EB_NODE),
155 struct eb64_node, node.branches);
156
157 y = node->key ^ x;
158 if (!y) {
159 /* Either we found the node which holds the key, or
160 * we have a dup tree. In the later case, we have to
161 * walk it down left to get the first entry.
162 */
163 if (node->node.bit < 0) {
164 troot = node->node.branches.b[EB_LEFT];
165 while (eb_gettag(troot) != EB_LEAF)
166 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
167 node = container_of(eb_untag(troot, EB_LEAF),
168 struct eb64_node, node.branches);
169 }
170 return node;
171 }
172
173 if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
174 return NULL; /* no more common bits */
175
176 troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
177 }
178}
179
180/*
Joseph Herlant7c16c0e2018-11-13 19:55:57 -0800181 * Find the first occurrence of a signed key in the tree <root>. If none can
Willy Tarreauc2186022009-10-26 19:48:54 +0100182 * be found, return NULL.
183 */
184static forceinline struct eb64_node *__eb64i_lookup(struct eb_root *root, s64 x)
185{
186 struct eb64_node *node;
187 eb_troot_t *troot;
188 u64 key = x ^ (1ULL << 63);
189 u64 y;
190
191 troot = root->b[EB_LEFT];
192 if (unlikely(troot == NULL))
193 return NULL;
194
195 while (1) {
196 if ((eb_gettag(troot) == EB_LEAF)) {
197 node = container_of(eb_untag(troot, EB_LEAF),
198 struct eb64_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200199 if (node->key == (u64)x)
Willy Tarreauc2186022009-10-26 19:48:54 +0100200 return node;
201 else
202 return NULL;
203 }
204 node = container_of(eb_untag(troot, EB_NODE),
205 struct eb64_node, node.branches);
206
207 y = node->key ^ x;
208 if (!y) {
209 /* Either we found the node which holds the key, or
210 * we have a dup tree. In the later case, we have to
211 * walk it down left to get the first entry.
212 */
213 if (node->node.bit < 0) {
214 troot = node->node.branches.b[EB_LEFT];
215 while (eb_gettag(troot) != EB_LEAF)
216 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
217 node = container_of(eb_untag(troot, EB_LEAF),
218 struct eb64_node, node.branches);
219 }
220 return node;
221 }
222
223 if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
224 return NULL; /* no more common bits */
225
226 troot = node->node.branches.b[(key >> node->node.bit) & EB_NODE_BRANCH_MASK];
227 }
228}
229
230/* Insert eb64_node <new> into subtree starting at node root <root>.
231 * Only new->key needs be set with the key. The eb64_node is returned.
232 * If root->b[EB_RGHT]==1, the tree may only contain unique keys.
233 */
234static forceinline struct eb64_node *
235__eb64_insert(struct eb_root *root, struct eb64_node *new) {
236 struct eb64_node *old;
237 unsigned int side;
238 eb_troot_t *troot;
239 u64 newkey; /* caching the key saves approximately one cycle */
Willy Tarreau6258f7b2011-09-19 20:48:00 +0200240 eb_troot_t *root_right;
Willy Tarreau3a932442010-05-09 19:29:23 +0200241 int old_node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100242
243 side = EB_LEFT;
244 troot = root->b[EB_LEFT];
245 root_right = root->b[EB_RGHT];
246 if (unlikely(troot == NULL)) {
247 /* Tree is empty, insert the leaf part below the left branch */
248 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
249 new->node.leaf_p = eb_dotag(root, EB_LEFT);
250 new->node.node_p = NULL; /* node part unused */
251 return new;
252 }
253
254 /* The tree descent is fairly easy :
255 * - first, check if we have reached a leaf node
256 * - second, check if we have gone too far
257 * - third, reiterate
258 * Everywhere, we use <new> for the node node we are inserting, <root>
259 * for the node we attach it to, and <old> for the node we are
260 * displacing below <new>. <troot> will always point to the future node
261 * (tagged with its type). <side> carries the side the node <new> is
262 * attached to below its parent, which is also where previous node
263 * was attached. <newkey> carries the key being inserted.
264 */
265 newkey = new->key;
266
267 while (1) {
268 if (unlikely(eb_gettag(troot) == EB_LEAF)) {
269 eb_troot_t *new_left, *new_rght;
270 eb_troot_t *new_leaf, *old_leaf;
271
272 old = container_of(eb_untag(troot, EB_LEAF),
273 struct eb64_node, node.branches);
274
275 new_left = eb_dotag(&new->node.branches, EB_LEFT);
276 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
277 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
278 old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
279
280 new->node.node_p = old->node.leaf_p;
281
282 /* Right here, we have 3 possibilities :
283 - the tree does not contain the key, and we have
284 new->key < old->key. We insert new above old, on
285 the left ;
286
287 - the tree does not contain the key, and we have
288 new->key > old->key. We insert new above old, on
289 the right ;
290
291 - the tree does contain the key, which implies it
292 is alone. We add the new key next to it as a
293 first duplicate.
294
295 The last two cases can easily be partially merged.
296 */
297
298 if (new->key < old->key) {
299 new->node.leaf_p = new_left;
300 old->node.leaf_p = new_rght;
301 new->node.branches.b[EB_LEFT] = new_leaf;
302 new->node.branches.b[EB_RGHT] = old_leaf;
303 } else {
304 /* we may refuse to duplicate this key if the tree is
305 * tagged as containing only unique keys.
306 */
307 if ((new->key == old->key) && eb_gettag(root_right))
308 return old;
309
310 /* new->key >= old->key, new goes the right */
311 old->node.leaf_p = new_left;
312 new->node.leaf_p = new_rght;
313 new->node.branches.b[EB_LEFT] = old_leaf;
314 new->node.branches.b[EB_RGHT] = new_leaf;
315
316 if (new->key == old->key) {
317 new->node.bit = -1;
318 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
319 return new;
320 }
321 }
322 break;
323 }
324
325 /* OK we're walking down this link */
326 old = container_of(eb_untag(troot, EB_NODE),
327 struct eb64_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200328 old_node_bit = old->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100329
330 /* Stop going down when we don't have common bits anymore. We
331 * also stop in front of a duplicates tree because it means we
332 * have to insert above.
333 */
334
Willy Tarreau3a932442010-05-09 19:29:23 +0200335 if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
336 (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100337 /* The tree did not contain the key, so we insert <new> before the node
338 * <old>, and set ->bit to designate the lowest bit position in <new>
339 * which applies to ->branches.b[].
340 */
341 eb_troot_t *new_left, *new_rght;
342 eb_troot_t *new_leaf, *old_node;
343
344 new_left = eb_dotag(&new->node.branches, EB_LEFT);
345 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
346 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
347 old_node = eb_dotag(&old->node.branches, EB_NODE);
348
349 new->node.node_p = old->node.node_p;
350
351 if (new->key < old->key) {
352 new->node.leaf_p = new_left;
353 old->node.node_p = new_rght;
354 new->node.branches.b[EB_LEFT] = new_leaf;
355 new->node.branches.b[EB_RGHT] = old_node;
356 }
357 else if (new->key > old->key) {
358 old->node.node_p = new_left;
359 new->node.leaf_p = new_rght;
360 new->node.branches.b[EB_LEFT] = old_node;
361 new->node.branches.b[EB_RGHT] = new_leaf;
362 }
363 else {
364 struct eb_node *ret;
365 ret = eb_insert_dup(&old->node, &new->node);
366 return container_of(ret, struct eb64_node, node);
367 }
368 break;
369 }
370
371 /* walk down */
372 root = &old->node.branches;
373#if BITS_PER_LONG >= 64
Willy Tarreau3a932442010-05-09 19:29:23 +0200374 side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;
Willy Tarreauc2186022009-10-26 19:48:54 +0100375#else
376 side = newkey;
Willy Tarreau3a932442010-05-09 19:29:23 +0200377 side >>= old_node_bit;
378 if (old_node_bit >= 32) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100379 side = newkey >> 32;
Willy Tarreau3a932442010-05-09 19:29:23 +0200380 side >>= old_node_bit & 0x1F;
Willy Tarreauc2186022009-10-26 19:48:54 +0100381 }
382 side &= EB_NODE_BRANCH_MASK;
383#endif
384 troot = root->b[side];
385 }
386
387 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
388 * parent is already set to <new>, and the <root>'s branch is still in
389 * <side>. Update the root's leaf till we have it. Note that we can also
390 * find the side by checking the side of new->node.node_p.
391 */
392
393 /* We need the common higher bits between new->key and old->key.
394 * What differences are there between new->key and the node here ?
395 * NOTE that bit(new) is always < bit(root) because highest
396 * bit of new->key and old->key are identical here (otherwise they
397 * would sit on different branches).
398 */
399 // note that if EB_NODE_BITS > 1, we should check that it's still >= 0
400 new->node.bit = fls64(new->key ^ old->key) - EB_NODE_BITS;
401 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
402
403 return new;
404}
405
406/* Insert eb64_node <new> into subtree starting at node root <root>, using
407 * signed keys. Only new->key needs be set with the key. The eb64_node
408 * is returned. If root->b[EB_RGHT]==1, the tree may only contain unique keys.
409 */
410static forceinline struct eb64_node *
411__eb64i_insert(struct eb_root *root, struct eb64_node *new) {
412 struct eb64_node *old;
413 unsigned int side;
414 eb_troot_t *troot;
415 u64 newkey; /* caching the key saves approximately one cycle */
Willy Tarreau6258f7b2011-09-19 20:48:00 +0200416 eb_troot_t *root_right;
Willy Tarreau3a932442010-05-09 19:29:23 +0200417 int old_node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100418
419 side = EB_LEFT;
420 troot = root->b[EB_LEFT];
421 root_right = root->b[EB_RGHT];
422 if (unlikely(troot == NULL)) {
423 /* Tree is empty, insert the leaf part below the left branch */
424 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
425 new->node.leaf_p = eb_dotag(root, EB_LEFT);
426 new->node.node_p = NULL; /* node part unused */
427 return new;
428 }
429
430 /* The tree descent is fairly easy :
431 * - first, check if we have reached a leaf node
432 * - second, check if we have gone too far
433 * - third, reiterate
434 * Everywhere, we use <new> for the node node we are inserting, <root>
435 * for the node we attach it to, and <old> for the node we are
436 * displacing below <new>. <troot> will always point to the future node
437 * (tagged with its type). <side> carries the side the node <new> is
438 * attached to below its parent, which is also where previous node
439 * was attached. <newkey> carries a high bit shift of the key being
440 * inserted in order to have negative keys stored before positive
441 * ones.
442 */
443 newkey = new->key ^ (1ULL << 63);
444
445 while (1) {
446 if (unlikely(eb_gettag(troot) == EB_LEAF)) {
447 eb_troot_t *new_left, *new_rght;
448 eb_troot_t *new_leaf, *old_leaf;
449
450 old = container_of(eb_untag(troot, EB_LEAF),
451 struct eb64_node, node.branches);
452
453 new_left = eb_dotag(&new->node.branches, EB_LEFT);
454 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
455 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
456 old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
457
458 new->node.node_p = old->node.leaf_p;
459
460 /* Right here, we have 3 possibilities :
461 - the tree does not contain the key, and we have
462 new->key < old->key. We insert new above old, on
463 the left ;
464
465 - the tree does not contain the key, and we have
466 new->key > old->key. We insert new above old, on
467 the right ;
468
469 - the tree does contain the key, which implies it
470 is alone. We add the new key next to it as a
471 first duplicate.
472
473 The last two cases can easily be partially merged.
474 */
475
476 if ((s64)new->key < (s64)old->key) {
477 new->node.leaf_p = new_left;
478 old->node.leaf_p = new_rght;
479 new->node.branches.b[EB_LEFT] = new_leaf;
480 new->node.branches.b[EB_RGHT] = old_leaf;
481 } else {
482 /* we may refuse to duplicate this key if the tree is
483 * tagged as containing only unique keys.
484 */
485 if ((new->key == old->key) && eb_gettag(root_right))
486 return old;
487
488 /* new->key >= old->key, new goes the right */
489 old->node.leaf_p = new_left;
490 new->node.leaf_p = new_rght;
491 new->node.branches.b[EB_LEFT] = old_leaf;
492 new->node.branches.b[EB_RGHT] = new_leaf;
493
494 if (new->key == old->key) {
495 new->node.bit = -1;
496 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
497 return new;
498 }
499 }
500 break;
501 }
502
503 /* OK we're walking down this link */
504 old = container_of(eb_untag(troot, EB_NODE),
505 struct eb64_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200506 old_node_bit = old->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100507
508 /* Stop going down when we don't have common bits anymore. We
509 * also stop in front of a duplicates tree because it means we
510 * have to insert above.
511 */
512
Willy Tarreau3a932442010-05-09 19:29:23 +0200513 if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
514 (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100515 /* The tree did not contain the key, so we insert <new> before the node
516 * <old>, and set ->bit to designate the lowest bit position in <new>
517 * which applies to ->branches.b[].
518 */
519 eb_troot_t *new_left, *new_rght;
520 eb_troot_t *new_leaf, *old_node;
521
522 new_left = eb_dotag(&new->node.branches, EB_LEFT);
523 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
524 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
525 old_node = eb_dotag(&old->node.branches, EB_NODE);
526
527 new->node.node_p = old->node.node_p;
528
529 if ((s64)new->key < (s64)old->key) {
530 new->node.leaf_p = new_left;
531 old->node.node_p = new_rght;
532 new->node.branches.b[EB_LEFT] = new_leaf;
533 new->node.branches.b[EB_RGHT] = old_node;
534 }
535 else if ((s64)new->key > (s64)old->key) {
536 old->node.node_p = new_left;
537 new->node.leaf_p = new_rght;
538 new->node.branches.b[EB_LEFT] = old_node;
539 new->node.branches.b[EB_RGHT] = new_leaf;
540 }
541 else {
542 struct eb_node *ret;
543 ret = eb_insert_dup(&old->node, &new->node);
544 return container_of(ret, struct eb64_node, node);
545 }
546 break;
547 }
548
549 /* walk down */
550 root = &old->node.branches;
551#if BITS_PER_LONG >= 64
Willy Tarreau3a932442010-05-09 19:29:23 +0200552 side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;
Willy Tarreauc2186022009-10-26 19:48:54 +0100553#else
554 side = newkey;
Willy Tarreau3a932442010-05-09 19:29:23 +0200555 side >>= old_node_bit;
556 if (old_node_bit >= 32) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100557 side = newkey >> 32;
Willy Tarreau3a932442010-05-09 19:29:23 +0200558 side >>= old_node_bit & 0x1F;
Willy Tarreauc2186022009-10-26 19:48:54 +0100559 }
560 side &= EB_NODE_BRANCH_MASK;
561#endif
562 troot = root->b[side];
563 }
564
565 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
566 * parent is already set to <new>, and the <root>'s branch is still in
567 * <side>. Update the root's leaf till we have it. Note that we can also
568 * find the side by checking the side of new->node.node_p.
569 */
570
571 /* We need the common higher bits between new->key and old->key.
572 * What differences are there between new->key and the node here ?
573 * NOTE that bit(new) is always < bit(root) because highest
574 * bit of new->key and old->key are identical here (otherwise they
575 * would sit on different branches).
576 */
577 // note that if EB_NODE_BITS > 1, we should check that it's still >= 0
578 new->node.bit = fls64(new->key ^ old->key) - EB_NODE_BITS;
579 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
580
581 return new;
582}
583
584#endif /* _EB64_TREE_H */