blob: b10a5ed89627680d39b0b0c88472f948602f4e1d [file] [log] [blame]
Willy Tarreauc2186022009-10-26 19:48:54 +01001/*
2 * Elastic Binary Trees - macros and structures for operations on 32bit 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 _EB32TREE_H
22#define _EB32TREE_H
23
24#include "ebtree.h"
25
26
27/* Return the structure of type <type> whose member <member> points to <ptr> */
28#define eb32_entry(ptr, type, member) container_of(ptr, type, member)
29
30#define EB32_ROOT EB_ROOT
31#define EB32_TREE_HEAD EB_TREE_HEAD
32
33/* These types may sometimes already be defined */
34typedef unsigned int u32;
35typedef signed int s32;
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 eb32_node {
43 struct eb_node node; /* the tree node, must be at the beginning */
Willy Tarreauebf4ba42020-02-22 15:55:33 +010044 MAYBE_ALIGN(sizeof(u32));
Willy Tarreauc2186022009-10-26 19:48:54 +010045 u32 key;
Willy Tarreauebf4ba42020-02-22 15:55:33 +010046} ALIGNED(sizeof(void*));
Willy Tarreauc2186022009-10-26 19:48:54 +010047
48/*
49 * Exported functions and macros.
50 * Many of them are always inlined because they are extremely small, and
51 * are generally called at most once or twice in a program.
52 */
53
54/* Return leftmost node in the tree, or NULL if none */
55static inline struct eb32_node *eb32_first(struct eb_root *root)
56{
57 return eb32_entry(eb_first(root), struct eb32_node, node);
58}
59
60/* Return rightmost node in the tree, or NULL if none */
61static inline struct eb32_node *eb32_last(struct eb_root *root)
62{
63 return eb32_entry(eb_last(root), struct eb32_node, node);
64}
65
66/* Return next node in the tree, or NULL if none */
67static inline struct eb32_node *eb32_next(struct eb32_node *eb32)
68{
69 return eb32_entry(eb_next(&eb32->node), struct eb32_node, node);
70}
71
72/* Return previous node in the tree, or NULL if none */
73static inline struct eb32_node *eb32_prev(struct eb32_node *eb32)
74{
75 return eb32_entry(eb_prev(&eb32->node), struct eb32_node, node);
76}
77
Willy Tarreau2b570202013-05-07 15:58:28 +020078/* Return next leaf node within a duplicate sub-tree, or NULL if none. */
79static inline struct eb32_node *eb32_next_dup(struct eb32_node *eb32)
80{
81 return eb32_entry(eb_next_dup(&eb32->node), struct eb32_node, node);
82}
83
84/* Return previous leaf node within a duplicate sub-tree, or NULL if none. */
85static inline struct eb32_node *eb32_prev_dup(struct eb32_node *eb32)
86{
87 return eb32_entry(eb_prev_dup(&eb32->node), struct eb32_node, node);
88}
89
Willy Tarreauc2186022009-10-26 19:48:54 +010090/* Return next node in the tree, skipping duplicates, or NULL if none */
91static inline struct eb32_node *eb32_next_unique(struct eb32_node *eb32)
92{
93 return eb32_entry(eb_next_unique(&eb32->node), struct eb32_node, node);
94}
95
96/* Return previous node in the tree, skipping duplicates, or NULL if none */
97static inline struct eb32_node *eb32_prev_unique(struct eb32_node *eb32)
98{
99 return eb32_entry(eb_prev_unique(&eb32->node), struct eb32_node, node);
100}
101
102/* Delete node from the tree if it was linked in. Mark the node unused. Note
103 * that this function relies on a non-inlined generic function: eb_delete.
104 */
105static inline void eb32_delete(struct eb32_node *eb32)
106{
107 eb_delete(&eb32->node);
108}
109
110/*
111 * The following functions are not inlined by default. They are declared
112 * in eb32tree.c, which simply relies on their inline version.
113 */
114REGPRM2 struct eb32_node *eb32_lookup(struct eb_root *root, u32 x);
115REGPRM2 struct eb32_node *eb32i_lookup(struct eb_root *root, s32 x);
116REGPRM2 struct eb32_node *eb32_lookup_le(struct eb_root *root, u32 x);
117REGPRM2 struct eb32_node *eb32_lookup_ge(struct eb_root *root, u32 x);
118REGPRM2 struct eb32_node *eb32_insert(struct eb_root *root, struct eb32_node *new);
119REGPRM2 struct eb32_node *eb32i_insert(struct eb_root *root, struct eb32_node *new);
120
121/*
122 * The following functions are less likely to be used directly, because their
123 * code is larger. The non-inlined version is preferred.
124 */
125
126/* Delete node from the tree if it was linked in. Mark the node unused. */
127static forceinline void __eb32_delete(struct eb32_node *eb32)
128{
129 __eb_delete(&eb32->node);
130}
131
132/*
Joseph Herlant7c16c0e2018-11-13 19:55:57 -0800133 * Find the first occurrence of a key in the tree <root>. If none can be
Willy Tarreauc2186022009-10-26 19:48:54 +0100134 * found, return NULL.
135 */
136static forceinline struct eb32_node *__eb32_lookup(struct eb_root *root, u32 x)
137{
138 struct eb32_node *node;
139 eb_troot_t *troot;
140 u32 y;
Willy Tarreau3a932442010-05-09 19:29:23 +0200141 int node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100142
143 troot = root->b[EB_LEFT];
144 if (unlikely(troot == NULL))
145 return NULL;
146
147 while (1) {
148 if ((eb_gettag(troot) == EB_LEAF)) {
149 node = container_of(eb_untag(troot, EB_LEAF),
150 struct eb32_node, node.branches);
151 if (node->key == x)
152 return node;
153 else
154 return NULL;
155 }
156 node = container_of(eb_untag(troot, EB_NODE),
157 struct eb32_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200158 node_bit = node->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100159
160 y = node->key ^ x;
161 if (!y) {
162 /* Either we found the node which holds the key, or
163 * we have a dup tree. In the later case, we have to
164 * walk it down left to get the first entry.
165 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200166 if (node_bit < 0) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100167 troot = node->node.branches.b[EB_LEFT];
168 while (eb_gettag(troot) != EB_LEAF)
169 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
170 node = container_of(eb_untag(troot, EB_LEAF),
171 struct eb32_node, node.branches);
172 }
173 return node;
174 }
175
Willy Tarreau3a932442010-05-09 19:29:23 +0200176 if ((y >> node_bit) >= EB_NODE_BRANCHES)
Willy Tarreauc2186022009-10-26 19:48:54 +0100177 return NULL; /* no more common bits */
178
Willy Tarreau3a932442010-05-09 19:29:23 +0200179 troot = node->node.branches.b[(x >> node_bit) & EB_NODE_BRANCH_MASK];
Willy Tarreauc2186022009-10-26 19:48:54 +0100180 }
181}
182
183/*
Joseph Herlant7c16c0e2018-11-13 19:55:57 -0800184 * Find the first occurrence of a signed key in the tree <root>. If none can
Willy Tarreauc2186022009-10-26 19:48:54 +0100185 * be found, return NULL.
186 */
187static forceinline struct eb32_node *__eb32i_lookup(struct eb_root *root, s32 x)
188{
189 struct eb32_node *node;
190 eb_troot_t *troot;
191 u32 key = x ^ 0x80000000;
192 u32 y;
Willy Tarreau3a932442010-05-09 19:29:23 +0200193 int node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100194
195 troot = root->b[EB_LEFT];
196 if (unlikely(troot == NULL))
197 return NULL;
198
199 while (1) {
200 if ((eb_gettag(troot) == EB_LEAF)) {
201 node = container_of(eb_untag(troot, EB_LEAF),
202 struct eb32_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200203 if (node->key == (u32)x)
Willy Tarreauc2186022009-10-26 19:48:54 +0100204 return node;
205 else
206 return NULL;
207 }
208 node = container_of(eb_untag(troot, EB_NODE),
209 struct eb32_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200210 node_bit = node->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100211
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 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200218 if (node_bit < 0) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100219 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 eb32_node, node.branches);
224 }
225 return node;
226 }
227
Willy Tarreau3a932442010-05-09 19:29:23 +0200228 if ((y >> node_bit) >= EB_NODE_BRANCHES)
Willy Tarreauc2186022009-10-26 19:48:54 +0100229 return NULL; /* no more common bits */
230
Willy Tarreau3a932442010-05-09 19:29:23 +0200231 troot = node->node.branches.b[(key >> node_bit) & EB_NODE_BRANCH_MASK];
Willy Tarreauc2186022009-10-26 19:48:54 +0100232 }
233}
234
235/* Insert eb32_node <new> into subtree starting at node root <root>.
236 * Only new->key needs be set with the key. The eb32_node is returned.
237 * If root->b[EB_RGHT]==1, the tree may only contain unique keys.
238 */
239static forceinline struct eb32_node *
240__eb32_insert(struct eb_root *root, struct eb32_node *new) {
241 struct eb32_node *old;
242 unsigned int side;
Willy Tarreau3a932442010-05-09 19:29:23 +0200243 eb_troot_t *troot, **up_ptr;
Willy Tarreauc2186022009-10-26 19:48:54 +0100244 u32 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 eb_troot_t *new_left, *new_rght;
247 eb_troot_t *new_leaf;
248 int old_node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100249
250 side = EB_LEFT;
251 troot = root->b[EB_LEFT];
252 root_right = root->b[EB_RGHT];
253 if (unlikely(troot == NULL)) {
254 /* Tree is empty, insert the leaf part below the left branch */
255 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
256 new->node.leaf_p = eb_dotag(root, EB_LEFT);
257 new->node.node_p = NULL; /* node part unused */
258 return new;
259 }
260
261 /* The tree descent is fairly easy :
262 * - first, check if we have reached a leaf node
263 * - second, check if we have gone too far
264 * - third, reiterate
265 * Everywhere, we use <new> for the node node we are inserting, <root>
266 * for the node we attach it to, and <old> for the node we are
267 * displacing below <new>. <troot> will always point to the future node
268 * (tagged with its type). <side> carries the side the node <new> is
269 * attached to below its parent, which is also where previous node
270 * was attached. <newkey> carries the key being inserted.
271 */
272 newkey = new->key;
273
274 while (1) {
Willy Tarreau3a932442010-05-09 19:29:23 +0200275 if (eb_gettag(troot) == EB_LEAF) {
276 /* insert above a leaf */
Willy Tarreauc2186022009-10-26 19:48:54 +0100277 old = container_of(eb_untag(troot, EB_LEAF),
278 struct eb32_node, node.branches);
Willy Tarreauc2186022009-10-26 19:48:54 +0100279 new->node.node_p = old->node.leaf_p;
Willy Tarreau3a932442010-05-09 19:29:23 +0200280 up_ptr = &old->node.leaf_p;
Willy Tarreauc2186022009-10-26 19:48:54 +0100281 break;
282 }
283
284 /* OK we're walking down this link */
285 old = container_of(eb_untag(troot, EB_NODE),
286 struct eb32_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200287 old_node_bit = old->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100288
289 /* Stop going down when we don't have common bits anymore. We
290 * also stop in front of a duplicates tree because it means we
291 * have to insert above.
292 */
293
Willy Tarreau3a932442010-05-09 19:29:23 +0200294 if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
295 (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100296 /* The tree did not contain the key, so we insert <new> before the node
297 * <old>, and set ->bit to designate the lowest bit position in <new>
298 * which applies to ->branches.b[].
299 */
Willy Tarreauc2186022009-10-26 19:48:54 +0100300 new->node.node_p = old->node.node_p;
Willy Tarreau3a932442010-05-09 19:29:23 +0200301 up_ptr = &old->node.node_p;
Willy Tarreauc2186022009-10-26 19:48:54 +0100302 break;
303 }
304
305 /* walk down */
306 root = &old->node.branches;
Willy Tarreau3a932442010-05-09 19:29:23 +0200307 side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;
Willy Tarreauc2186022009-10-26 19:48:54 +0100308 troot = root->b[side];
309 }
310
Willy Tarreau3a932442010-05-09 19:29:23 +0200311 new_left = eb_dotag(&new->node.branches, EB_LEFT);
312 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
313 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
Willy Tarreauc2186022009-10-26 19:48:54 +0100314
315 /* We need the common higher bits between new->key and old->key.
316 * What differences are there between new->key and the node here ?
317 * NOTE that bit(new) is always < bit(root) because highest
318 * bit of new->key and old->key are identical here (otherwise they
319 * would sit on different branches).
320 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200321
Willy Tarreauc2186022009-10-26 19:48:54 +0100322 // note that if EB_NODE_BITS > 1, we should check that it's still >= 0
323 new->node.bit = flsnz(new->key ^ old->key) - EB_NODE_BITS;
Willy Tarreau3a932442010-05-09 19:29:23 +0200324
325 if (new->key == old->key) {
326 new->node.bit = -1; /* mark as new dup tree, just in case */
327
328 if (likely(eb_gettag(root_right))) {
329 /* we refuse to duplicate this key if the tree is
330 * tagged as containing only unique keys.
331 */
332 return old;
333 }
334
335 if (eb_gettag(troot) != EB_LEAF) {
336 /* there was already a dup tree below */
337 struct eb_node *ret;
338 ret = eb_insert_dup(&old->node, &new->node);
339 return container_of(ret, struct eb32_node, node);
340 }
341 /* otherwise fall through */
342 }
Willy Tarreauc2186022009-10-26 19:48:54 +0100343
Willy Tarreau3a932442010-05-09 19:29:23 +0200344 if (new->key >= old->key) {
345 new->node.branches.b[EB_LEFT] = troot;
346 new->node.branches.b[EB_RGHT] = new_leaf;
347 new->node.leaf_p = new_rght;
348 *up_ptr = new_left;
349 }
350 else {
351 new->node.branches.b[EB_LEFT] = new_leaf;
352 new->node.branches.b[EB_RGHT] = troot;
353 new->node.leaf_p = new_left;
354 *up_ptr = new_rght;
355 }
356
357 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
358 * parent is already set to <new>, and the <root>'s branch is still in
359 * <side>. Update the root's leaf till we have it. Note that we can also
360 * find the side by checking the side of new->node.node_p.
361 */
362
363 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
Willy Tarreauc2186022009-10-26 19:48:54 +0100364 return new;
365}
366
367/* Insert eb32_node <new> into subtree starting at node root <root>, using
368 * signed keys. Only new->key needs be set with the key. The eb32_node
369 * is returned. If root->b[EB_RGHT]==1, the tree may only contain unique keys.
370 */
371static forceinline struct eb32_node *
372__eb32i_insert(struct eb_root *root, struct eb32_node *new) {
373 struct eb32_node *old;
374 unsigned int side;
Willy Tarreau3a932442010-05-09 19:29:23 +0200375 eb_troot_t *troot, **up_ptr;
Willy Tarreauc2186022009-10-26 19:48:54 +0100376 int newkey; /* caching the key saves approximately one cycle */
Willy Tarreau6258f7b2011-09-19 20:48:00 +0200377 eb_troot_t *root_right;
Willy Tarreau3a932442010-05-09 19:29:23 +0200378 eb_troot_t *new_left, *new_rght;
379 eb_troot_t *new_leaf;
380 int old_node_bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100381
382 side = EB_LEFT;
383 troot = root->b[EB_LEFT];
384 root_right = root->b[EB_RGHT];
385 if (unlikely(troot == NULL)) {
386 /* Tree is empty, insert the leaf part below the left branch */
387 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
388 new->node.leaf_p = eb_dotag(root, EB_LEFT);
389 new->node.node_p = NULL; /* node part unused */
390 return new;
391 }
392
393 /* The tree descent is fairly easy :
394 * - first, check if we have reached a leaf node
395 * - second, check if we have gone too far
396 * - third, reiterate
397 * Everywhere, we use <new> for the node node we are inserting, <root>
398 * for the node we attach it to, and <old> for the node we are
399 * displacing below <new>. <troot> will always point to the future node
400 * (tagged with its type). <side> carries the side the node <new> is
401 * attached to below its parent, which is also where previous node
402 * was attached. <newkey> carries a high bit shift of the key being
403 * inserted in order to have negative keys stored before positive
404 * ones.
405 */
406 newkey = new->key + 0x80000000;
407
408 while (1) {
Willy Tarreau3a932442010-05-09 19:29:23 +0200409 if (eb_gettag(troot) == EB_LEAF) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100410 old = container_of(eb_untag(troot, EB_LEAF),
411 struct eb32_node, node.branches);
Willy Tarreauc2186022009-10-26 19:48:54 +0100412 new->node.node_p = old->node.leaf_p;
Willy Tarreau3a932442010-05-09 19:29:23 +0200413 up_ptr = &old->node.leaf_p;
Willy Tarreauc2186022009-10-26 19:48:54 +0100414 break;
415 }
416
417 /* OK we're walking down this link */
418 old = container_of(eb_untag(troot, EB_NODE),
419 struct eb32_node, node.branches);
Willy Tarreau3a932442010-05-09 19:29:23 +0200420 old_node_bit = old->node.bit;
Willy Tarreauc2186022009-10-26 19:48:54 +0100421
422 /* Stop going down when we don't have common bits anymore. We
423 * also stop in front of a duplicates tree because it means we
424 * have to insert above.
425 */
426
Willy Tarreau3a932442010-05-09 19:29:23 +0200427 if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
428 (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
Willy Tarreauc2186022009-10-26 19:48:54 +0100429 /* The tree did not contain the key, so we insert <new> before the node
430 * <old>, and set ->bit to designate the lowest bit position in <new>
431 * which applies to ->branches.b[].
432 */
Willy Tarreauc2186022009-10-26 19:48:54 +0100433 new->node.node_p = old->node.node_p;
Willy Tarreau3a932442010-05-09 19:29:23 +0200434 up_ptr = &old->node.node_p;
Willy Tarreauc2186022009-10-26 19:48:54 +0100435 break;
436 }
437
438 /* walk down */
439 root = &old->node.branches;
Willy Tarreau3a932442010-05-09 19:29:23 +0200440 side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;
Willy Tarreauc2186022009-10-26 19:48:54 +0100441 troot = root->b[side];
442 }
443
Willy Tarreau3a932442010-05-09 19:29:23 +0200444 new_left = eb_dotag(&new->node.branches, EB_LEFT);
445 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
446 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
Willy Tarreauc2186022009-10-26 19:48:54 +0100447
448 /* We need the common higher bits between new->key and old->key.
449 * What differences are there between new->key and the node here ?
450 * NOTE that bit(new) is always < bit(root) because highest
451 * bit of new->key and old->key are identical here (otherwise they
452 * would sit on different branches).
453 */
Willy Tarreau3a932442010-05-09 19:29:23 +0200454
Willy Tarreauc2186022009-10-26 19:48:54 +0100455 // note that if EB_NODE_BITS > 1, we should check that it's still >= 0
456 new->node.bit = flsnz(new->key ^ old->key) - EB_NODE_BITS;
Willy Tarreau3a932442010-05-09 19:29:23 +0200457
458 if (new->key == old->key) {
459 new->node.bit = -1; /* mark as new dup tree, just in case */
460
461 if (likely(eb_gettag(root_right))) {
462 /* we refuse to duplicate this key if the tree is
463 * tagged as containing only unique keys.
464 */
465 return old;
466 }
467
468 if (eb_gettag(troot) != EB_LEAF) {
469 /* there was already a dup tree below */
470 struct eb_node *ret;
471 ret = eb_insert_dup(&old->node, &new->node);
472 return container_of(ret, struct eb32_node, node);
473 }
474 /* otherwise fall through */
475 }
Willy Tarreauc2186022009-10-26 19:48:54 +0100476
Willy Tarreau3a932442010-05-09 19:29:23 +0200477 if ((s32)new->key >= (s32)old->key) {
478 new->node.branches.b[EB_LEFT] = troot;
479 new->node.branches.b[EB_RGHT] = new_leaf;
480 new->node.leaf_p = new_rght;
481 *up_ptr = new_left;
482 }
483 else {
484 new->node.branches.b[EB_LEFT] = new_leaf;
485 new->node.branches.b[EB_RGHT] = troot;
486 new->node.leaf_p = new_left;
487 *up_ptr = new_rght;
488 }
489
490 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
491 * parent is already set to <new>, and the <root>'s branch is still in
492 * <side>. Update the root's leaf till we have it. Note that we can also
493 * find the side by checking the side of new->node.node_p.
494 */
495
496 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
Willy Tarreauc2186022009-10-26 19:48:54 +0100497 return new;
498}
499
500#endif /* _EB32_TREE_H */