/src/haproxy/include/import/ebimtree.h

Source (jump to first uncovered line)
/*
 * Elastic Binary Trees - macros for Indirect Multi-Byte data nodes.
 * Version 6.0.6
 * (C) 2002-2011 - Willy Tarreau <w@1wt.eu>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation, version 2.1
 * exclusively.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

#ifndef _EBIMTREE_H
#define _EBIMTREE_H

#include <string.h>
#include "ebtree.h"
#include "ebpttree.h"

/* These functions and macros rely on Pointer nodes and use the <key> entry as
 * a pointer to an indirect key. Most operations are performed using ebpt_*.
 */

/* The following functions are not inlined by default. They are declared
 * in ebimtree.c, which simply relies on their inline version.
 */
struct ebpt_node *ebim_lookup(struct eb_root *root, const void *x, unsigned int len);
struct ebpt_node *ebim_insert(struct eb_root *root, struct ebpt_node *new, unsigned int len);

/* Find the first occurrence of a key of a least <len> bytes matching <x> in the
 * tree <root>. The caller is responsible for ensuring that <len> will not exceed
 * the common parts between the tree's keys and <x>. In case of multiple matches,
 * the leftmost node is returned. This means that this function can be used to
 * lookup string keys by prefix if all keys in the tree are zero-terminated. If
 * no match is found, NULL is returned. Returns first node if <len> is zero.
 */
static forceinline struct ebpt_node *
__ebim_lookup(struct eb_root *root, const void *x, unsigned int len)
{
  struct ebpt_node *node;
  eb_troot_t *troot;
  int pos, side;
  int node_bit;

  troot = root->b[EB_LEFT];
  if (unlikely(troot == NULL))
    goto ret_null;

  if (unlikely(len == 0))
    goto walk_down;

  pos = 0;
  while (1) {
    if (eb_gettag(troot) == EB_LEAF) {
      node = container_of(eb_untag(troot, EB_LEAF),
              struct ebpt_node, node.branches);
      if (eb_memcmp(node->key + pos, x, len) != 0)
        goto ret_null;
      else
        goto ret_node;
    }
    node = container_of(eb_untag(troot, EB_NODE),
            struct ebpt_node, node.branches);

    node_bit = node->node.bit;
    if (node_bit < 0) {
      /* We have a dup tree now. Either it's for the same
       * value, and we walk down left, or it's a different
       * one and we don't have our key.
       */
      if (eb_memcmp(node->key + pos, x, len) != 0)
        goto ret_null;
      else
        goto walk_left;
    }

    /* OK, normal data node, let's walk down. We check if all full
     * bytes are equal, and we start from the last one we did not
     * completely check. We stop as soon as we reach the last byte,
     * because we must decide to go left/right or abort.
     */
    node_bit = ~node_bit + (pos << 3) + 8; // = (pos<<3) + (7 - node_bit)
    if (node_bit < 0) {
      /* This surprising construction gives better performance
       * because gcc does not try to reorder the loop. Tested to
       * be fine with 2.95 to 4.2.
       */
      while (1) {
        if (*(unsigned char*)(node->key + pos++) ^ *(unsigned char*)(x++))
          goto ret_null; /* more than one full byte is different */
        if (--len == 0)
          goto walk_left; /* return first node if all bytes matched */
        node_bit += 8;
        if (node_bit >= 0)
          break;
      }
    }

    /* here we know that only the last byte differs, so node_bit < 8.
     * We have 2 possibilities :
     *   - more than the last bit differs => return NULL
     *   - walk down on side = (x[pos] >> node_bit) & 1
     */
    side = *(unsigned char *)x >> node_bit;
    if (((*(unsigned char*)(node->key + pos) >> node_bit) ^ side) > 1)
      goto ret_null;
    side &= 1;
    troot = node->node.branches.b[side];
  }
 walk_left:
  troot = node->node.branches.b[EB_LEFT];
 walk_down:
  while (eb_gettag(troot) != EB_LEAF)
    troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
  node = container_of(eb_untag(troot, EB_LEAF),
          struct ebpt_node, node.branches);
 ret_node:
  return node;
 ret_null:
  return NULL;
}

/* Insert ebpt_node <new> into subtree starting at node root <root>.
 * Only new->key needs be set with the key. The ebpt_node is returned.
 * If root->b[EB_RGHT]==1, the tree may only contain unique keys. The
 * len is specified in bytes.
 */
static forceinline struct ebpt_node *
__ebim_insert(struct eb_root *root, struct ebpt_node *new, unsigned int len)
{
  struct ebpt_node *old;
  unsigned int side;
  eb_troot_t *troot;
  eb_troot_t *root_right;
  int diff;
  int bit;
  int old_node_bit;

  side = EB_LEFT;
  troot = root->b[EB_LEFT];
  root_right = root->b[EB_RGHT];
  if (unlikely(troot == NULL)) {
    /* Tree is empty, insert the leaf part below the left branch */
    root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
    new->node.leaf_p = eb_dotag(root, EB_LEFT);
    new->node.node_p = NULL; /* node part unused */
    return new;
  }

  len <<= 3;

  /* The tree descent is fairly easy :
   *  - first, check if we have reached a leaf node
   *  - second, check if we have gone too far
   *  - third, reiterate
   * Everywhere, we use <new> for the node node we are inserting, <root>
   * for the node we attach it to, and <old> for the node we are
   * displacing below <new>. <troot> will always point to the future node
   * (tagged with its type). <side> carries the side the node <new> is
   * attached to below its parent, which is also where previous node
   * was attached.
   */

  bit = 0;
  while (1) {
    if (unlikely(eb_gettag(troot) == EB_LEAF)) {
      eb_troot_t *new_left, *new_rght;
      eb_troot_t *new_leaf, *old_leaf;

      old = container_of(eb_untag(troot, EB_LEAF),
              struct ebpt_node, node.branches);

      new_left = eb_dotag(&new->node.branches, EB_LEFT);
      new_rght = eb_dotag(&new->node.branches, EB_RGHT);
      new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
      old_leaf = eb_dotag(&old->node.branches, EB_LEAF);

      new->node.node_p = old->node.leaf_p;

      /* Right here, we have 3 possibilities :
       * - the tree does not contain the key, and we have
       *   new->key < old->key. We insert new above old, on
       *   the left ;
       *
       * - the tree does not contain the key, and we have
       *   new->key > old->key. We insert new above old, on
       *   the right ;
       *
       * - the tree does contain the key, which implies it
       *   is alone. We add the new key next to it as a
       *   first duplicate.
       *
       * The last two cases can easily be partially merged.
       */
      bit = equal_bits(new->key, old->key, bit, len);

      /* Note: we can compare more bits than the current node's because as
       * long as they are identical, we know we descend along the correct
       * side. However we don't want to start to compare past the end.
       */
      diff = 0;
      if (((unsigned)bit >> 3) < len)
        diff = cmp_bits(new->key, old->key, bit);

      if (diff < 0) {
        new->node.leaf_p = new_left;
        old->node.leaf_p = new_rght;
        new->node.branches.b[EB_LEFT] = new_leaf;
        new->node.branches.b[EB_RGHT] = old_leaf;
      } else {
        /* we may refuse to duplicate this key if the tree is
         * tagged as containing only unique keys.
         */
        if (diff == 0 && eb_gettag(root_right))
          return old;

        /* new->key >= old->key, new goes the right */
        old->node.leaf_p = new_left;
        new->node.leaf_p = new_rght;
        new->node.branches.b[EB_LEFT] = old_leaf;
        new->node.branches.b[EB_RGHT] = new_leaf;

        if (diff == 0) {
          new->node.bit = -1;
          root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
          return new;
        }
      }
      break;
    }

    /* OK we're walking down this link */
    old = container_of(eb_untag(troot, EB_NODE),
           struct ebpt_node, node.branches);
    old_node_bit = old->node.bit;

    /* Stop going down when we don't have common bits anymore. We
     * also stop in front of a duplicates tree because it means we
     * have to insert above. Note: we can compare more bits than
     * the current node's because as long as they are identical, we
     * know we descend along the correct side.
     */
    if (old_node_bit < 0) {
      /* we're above a duplicate tree, we must compare till the end */
      bit = equal_bits(new->key, old->key, bit, len);
      goto dup_tree;
    }
    else if (bit < old_node_bit) {
      bit = equal_bits(new->key, old->key, bit, old_node_bit);
    }

    if (bit < old_node_bit) { /* we don't have all bits in common */
      /* The tree did not contain the key, so we insert <new> before the node
       * <old>, and set ->bit to designate the lowest bit position in <new>
       * which applies to ->branches.b[].
       */
      eb_troot_t *new_left, *new_rght;
      eb_troot_t *new_leaf, *old_node;

    dup_tree:
      new_left = eb_dotag(&new->node.branches, EB_LEFT);
      new_rght = eb_dotag(&new->node.branches, EB_RGHT);
      new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
      old_node = eb_dotag(&old->node.branches, EB_NODE);

      new->node.node_p = old->node.node_p;

      /* Note: we can compare more bits than the current node's because as
       * long as they are identical, we know we descend along the correct
       * side. However we don't want to start to compare past the end.
       */
      diff = 0;
      if (((unsigned)bit >> 3) < len)
        diff = cmp_bits(new->key, old->key, bit);

      if (diff < 0) {
        new->node.leaf_p = new_left;
        old->node.node_p = new_rght;
        new->node.branches.b[EB_LEFT] = new_leaf;
        new->node.branches.b[EB_RGHT] = old_node;
      }
      else if (diff > 0) {
        old->node.node_p = new_left;
        new->node.leaf_p = new_rght;
        new->node.branches.b[EB_LEFT] = old_node;
        new->node.branches.b[EB_RGHT] = new_leaf;
      }
      else {
        struct eb_node *ret;
        ret = eb_insert_dup(&old->node, &new->node);
        return container_of(ret, struct ebpt_node, node);
      }
      break;
    }

    /* walk down */
    root = &old->node.branches;
    side = (((unsigned char *)new->key)[old_node_bit >> 3] >> (~old_node_bit & 7)) & 1;
    troot = root->b[side];
  }

  /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
   * parent is already set to <new>, and the <root>'s branch is still in
   * <side>. Update the root's leaf till we have it. Note that we can also
   * find the side by checking the side of new->node.node_p.
   */

  /* We need the common higher bits between new->key and old->key.
   * This number of bits is already in <bit>.
   */
  new->node.bit = bit;
  root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
  return new;
}

#endif /* _EBIMTREE_H */

Coverage Report

Created: 2025-06-13 06:13

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Elastic Binary Trees - macros for Indirect Multi-Byte data nodes.
3		* Version 6.0.6
4		* (C) 2002-2011 - Willy Tarreau <w@1wt.eu>
5		*
6		* 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.
10		*
11		* This library 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 GNU
14		* Lesser General Public License for more details.
15		*
16		* 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
19		*/
20
21		#ifndef _EBIMTREE_H
22		#define _EBIMTREE_H
23
24		#include <string.h>
25		#include "ebtree.h"
26		#include "ebpttree.h"
27
28		/* These functions and macros rely on Pointer nodes and use the <key> entry as
29		* a pointer to an indirect key. Most operations are performed using ebpt_*.
30		*/
31
32		/* The following functions are not inlined by default. They are declared
33		* in ebimtree.c, which simply relies on their inline version.
34		*/
35		struct ebpt_node ebim_lookup(struct eb_root root, const void *x, unsigned int len);
36		struct ebpt_node ebim_insert(struct eb_root root, struct ebpt_node *new, unsigned int len);
37
38		/* Find the first occurrence of a key of a least <len> bytes matching <x> in the
39		* tree <root>. The caller is responsible for ensuring that <len> will not exceed
40		* the common parts between the tree's keys and <x>. In case of multiple matches,
41		* the leftmost node is returned. This means that this function can be used to
42		* lookup string keys by prefix if all keys in the tree are zero-terminated. If
43		* no match is found, NULL is returned. Returns first node if <len> is zero.
44		*/
45		static forceinline struct ebpt_node *
46		__ebim_lookup(struct eb_root root, const void x, unsigned int len)
47	0	{
48	0	struct ebpt_node *node;
49	0	eb_troot_t *troot;
50	0	int pos, side;
51	0	int node_bit;
52
53	0	troot = root->b[EB_LEFT];
54	0	if (unlikely(troot == NULL))
55	0	goto ret_null;
56
57	0	if (unlikely(len == 0))
58	0	goto walk_down;
59
60	0	pos = 0;
61	0	while (1) {
62	0	if (eb_gettag(troot) == EB_LEAF) {
63	0	node = container_of(eb_untag(troot, EB_LEAF),
64	0	struct ebpt_node, node.branches);
65	0	if (eb_memcmp(node->key + pos, x, len) != 0)
66	0	goto ret_null;
67	0	else
68	0	goto ret_node;
69	0	}
70	0	node = container_of(eb_untag(troot, EB_NODE),
71	0	struct ebpt_node, node.branches);
72
73	0	node_bit = node->node.bit;
74	0	if (node_bit < 0) {
75		/* We have a dup tree now. Either it's for the same
76		* value, and we walk down left, or it's a different
77		* one and we don't have our key.
78		*/
79	0	if (eb_memcmp(node->key + pos, x, len) != 0)
80	0	goto ret_null;
81	0	else
82	0	goto walk_left;
83	0	}
84
85		/* OK, normal data node, let's walk down. We check if all full
86		* bytes are equal, and we start from the last one we did not
87		* completely check. We stop as soon as we reach the last byte,
88		* because we must decide to go left/right or abort.
89		*/
90	0	node_bit = ~node_bit + (pos << 3) + 8; // = (pos<<3) + (7 - node_bit)
91	0	if (node_bit < 0) {
92		/* This surprising construction gives better performance
93		* because gcc does not try to reorder the loop. Tested to
94		* be fine with 2.95 to 4.2.
95		*/
96	0	while (1) {
97	0	if ((unsigned char)(node->key + pos++) ^ (unsigned char)(x++))
98	0	goto ret_null; /* more than one full byte is different */
99	0	if (--len == 0)
100	0	goto walk_left; /* return first node if all bytes matched */
101	0	node_bit += 8;
102	0	if (node_bit >= 0)
103	0	break;
104	0	}
105	0	}
106
107		/* here we know that only the last byte differs, so node_bit < 8.
108		* We have 2 possibilities :
109		* - more than the last bit differs => return NULL
110		* - walk down on side = (x[pos] >> node_bit) & 1
111		*/
112	0	side = (unsigned char )x >> node_bit;
113	0	if ((((unsigned char)(node->key + pos) >> node_bit) ^ side) > 1)
114	0	goto ret_null;
115	0	side &= 1;
116	0	troot = node->node.branches.b[side];
117	0	}
118	0	walk_left:
119	0	troot = node->node.branches.b[EB_LEFT];
120	0	walk_down:
121	0	while (eb_gettag(troot) != EB_LEAF)
122	0	troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
123	0	node = container_of(eb_untag(troot, EB_LEAF),
124	0	struct ebpt_node, node.branches);
125	0	ret_node:
126	0	return node;
127	0	ret_null:
128	0	return NULL;
129	0	} Unexecuted instantiation: cfgparse.c:__ebim_lookup Unexecuted instantiation: connection.c:__ebim_lookup Unexecuted instantiation: filters.c:__ebim_lookup Unexecuted instantiation: flt_http_comp.c:__ebim_lookup Unexecuted instantiation: haproxy.c:__ebim_lookup Unexecuted instantiation: http_ana.c:__ebim_lookup Unexecuted instantiation: http_ext.c:__ebim_lookup Unexecuted instantiation: http_htx.c:__ebim_lookup Unexecuted instantiation: proxy.c:__ebim_lookup Unexecuted instantiation: resolvers.c:__ebim_lookup Unexecuted instantiation: server.c:__ebim_lookup Unexecuted instantiation: sock.c:__ebim_lookup Unexecuted instantiation: sock_inet.c:__ebim_lookup Unexecuted instantiation: stats-html.c:__ebim_lookup Unexecuted instantiation: stats.c:__ebim_lookup Unexecuted instantiation: stick_table.c:__ebim_lookup Unexecuted instantiation: stream.c:__ebim_lookup Unexecuted instantiation: tcpcheck.c:__ebim_lookup Unexecuted instantiation: tools.c:__ebim_lookup Unexecuted instantiation: backend.c:__ebim_lookup Unexecuted instantiation: cache.c:__ebim_lookup Unexecuted instantiation: cfgparse-listen.c:__ebim_lookup Unexecuted instantiation: check.c:__ebim_lookup Unexecuted instantiation: dict.c:__ebim_lookup Unexecuted instantiation: ebimtree.c:__ebim_lookup Unexecuted instantiation: ebistree.c:__ebim_lookup Unexecuted instantiation: fcgi-app.c:__ebim_lookup Unexecuted instantiation: guid.c:__ebim_lookup Unexecuted instantiation: http_fetch.c:__ebim_lookup Unexecuted instantiation: pattern.c:__ebim_lookup Unexecuted instantiation: proto_tcp.c:__ebim_lookup Unexecuted instantiation: h1_htx.c:__ebim_lookup
130
131		/* Insert ebpt_node <new> into subtree starting at node root <root>.
132		* Only new->key needs be set with the key. The ebpt_node is returned.
133		* If root->b[EB_RGHT]==1, the tree may only contain unique keys. The
134		* len is specified in bytes.
135		*/
136		static forceinline struct ebpt_node *
137		__ebim_insert(struct eb_root root, struct ebpt_node new, unsigned int len)
138	0	{
139	0	struct ebpt_node *old;
140	0	unsigned int side;
141	0	eb_troot_t *troot;
142	0	eb_troot_t *root_right;
143	0	int diff;
144	0	int bit;
145	0	int old_node_bit;
146
147	0	side = EB_LEFT;
148	0	troot = root->b[EB_LEFT];
149	0	root_right = root->b[EB_RGHT];
150	0	if (unlikely(troot == NULL)) {
151		/* Tree is empty, insert the leaf part below the left branch */
152	0	root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
153	0	new->node.leaf_p = eb_dotag(root, EB_LEFT);
154	0	new->node.node_p = NULL; /* node part unused */
155	0	return new;
156	0	}
157
158	0	len <<= 3;
159
160		/* The tree descent is fairly easy :
161		* - first, check if we have reached a leaf node
162		* - second, check if we have gone too far
163		* - third, reiterate
164		* Everywhere, we use <new> for the node node we are inserting, <root>
165		* for the node we attach it to, and <old> for the node we are
166		* displacing below <new>. <troot> will always point to the future node
167		* (tagged with its type). <side> carries the side the node <new> is
168		* attached to below its parent, which is also where previous node
169		* was attached.
170		*/
171
172	0	bit = 0;
173	0	while (1) {
174	0	if (unlikely(eb_gettag(troot) == EB_LEAF)) {
175	0	eb_troot_t new_left, new_rght;
176	0	eb_troot_t new_leaf, old_leaf;
177
178	0	old = container_of(eb_untag(troot, EB_LEAF),
179	0	struct ebpt_node, node.branches);
180
181	0	new_left = eb_dotag(&new->node.branches, EB_LEFT);
182	0	new_rght = eb_dotag(&new->node.branches, EB_RGHT);
183	0	new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
184	0	old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
185
186	0	new->node.node_p = old->node.leaf_p;
187
188		/* Right here, we have 3 possibilities :
189		* - the tree does not contain the key, and we have
190		* new->key < old->key. We insert new above old, on
191		* the left ;
192		*
193		* - the tree does not contain the key, and we have
194		* new->key > old->key. We insert new above old, on
195		* the right ;
196		*
197		* - the tree does contain the key, which implies it
198		* is alone. We add the new key next to it as a
199		* first duplicate.
200		*
201		* The last two cases can easily be partially merged.
202		*/
203	0	bit = equal_bits(new->key, old->key, bit, len);
204
205		/* Note: we can compare more bits than the current node's because as
206		* long as they are identical, we know we descend along the correct
207		* side. However we don't want to start to compare past the end.
208		*/
209	0	diff = 0;
210	0	if (((unsigned)bit >> 3) < len)
211	0	diff = cmp_bits(new->key, old->key, bit);
212
213	0	if (diff < 0) {
214	0	new->node.leaf_p = new_left;
215	0	old->node.leaf_p = new_rght;
216	0	new->node.branches.b[EB_LEFT] = new_leaf;
217	0	new->node.branches.b[EB_RGHT] = old_leaf;
218	0	} else {
219		/* we may refuse to duplicate this key if the tree is
220		* tagged as containing only unique keys.
221		*/
222	0	if (diff == 0 && eb_gettag(root_right))
223	0	return old;
224
225		/* new->key >= old->key, new goes the right */
226	0	old->node.leaf_p = new_left;
227	0	new->node.leaf_p = new_rght;
228	0	new->node.branches.b[EB_LEFT] = old_leaf;
229	0	new->node.branches.b[EB_RGHT] = new_leaf;
230
231	0	if (diff == 0) {
232	0	new->node.bit = -1;
233	0	root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
234	0	return new;
235	0	}
236	0	}
237	0	break;
238	0	}
239
240		/* OK we're walking down this link */
241	0	old = container_of(eb_untag(troot, EB_NODE),
242	0	struct ebpt_node, node.branches);
243	0	old_node_bit = old->node.bit;
244
245		/* Stop going down when we don't have common bits anymore. We
246		* also stop in front of a duplicates tree because it means we
247		* have to insert above. Note: we can compare more bits than
248		* the current node's because as long as they are identical, we
249		* know we descend along the correct side.
250		*/
251	0	if (old_node_bit < 0) {
252		/* we're above a duplicate tree, we must compare till the end */
253	0	bit = equal_bits(new->key, old->key, bit, len);
254	0	goto dup_tree;
255	0	}
256	0	else if (bit < old_node_bit) {
257	0	bit = equal_bits(new->key, old->key, bit, old_node_bit);
258	0	}
259
260	0	if (bit < old_node_bit) { /* we don't have all bits in common */
261		/* The tree did not contain the key, so we insert <new> before the node
262		* <old>, and set ->bit to designate the lowest bit position in <new>
263		* which applies to ->branches.b[].
264		*/
265	0	eb_troot_t new_left, new_rght;
266	0	eb_troot_t new_leaf, old_node;
267
268	0	dup_tree:
269	0	new_left = eb_dotag(&new->node.branches, EB_LEFT);
270	0	new_rght = eb_dotag(&new->node.branches, EB_RGHT);
271	0	new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
272	0	old_node = eb_dotag(&old->node.branches, EB_NODE);
273
274	0	new->node.node_p = old->node.node_p;
275
276		/* Note: we can compare more bits than the current node's because as
277		* long as they are identical, we know we descend along the correct
278		* side. However we don't want to start to compare past the end.
279		*/
280	0	diff = 0;
281	0	if (((unsigned)bit >> 3) < len)
282	0	diff = cmp_bits(new->key, old->key, bit);
283
284	0	if (diff < 0) {
285	0	new->node.leaf_p = new_left;
286	0	old->node.node_p = new_rght;
287	0	new->node.branches.b[EB_LEFT] = new_leaf;
288	0	new->node.branches.b[EB_RGHT] = old_node;
289	0	}
290	0	else if (diff > 0) {
291	0	old->node.node_p = new_left;
292	0	new->node.leaf_p = new_rght;
293	0	new->node.branches.b[EB_LEFT] = old_node;
294	0	new->node.branches.b[EB_RGHT] = new_leaf;
295	0	}
296	0	else {
297	0	struct eb_node *ret;
298	0	ret = eb_insert_dup(&old->node, &new->node);
299	0	return container_of(ret, struct ebpt_node, node);
300	0	}
301	0	break;
302	0	}
303
304		/* walk down */
305	0	root = &old->node.branches;
306	0	side = (((unsigned char *)new->key)[old_node_bit >> 3] >> (~old_node_bit & 7)) & 1;
307	0	troot = root->b[side];
308	0	}
309
310		/* Ok, now we are inserting <new> between <root> and <old>. <old>'s
311		* parent is already set to <new>, and the <root>'s branch is still in
312		* <side>. Update the root's leaf till we have it. Note that we can also
313		* find the side by checking the side of new->node.node_p.
314		*/
315
316		/* We need the common higher bits between new->key and old->key.
317		* This number of bits is already in <bit>.
318		*/
319	0	new->node.bit = bit;
320	0	root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
321	0	return new;
322	0	} Unexecuted instantiation: cfgparse.c:__ebim_insert Unexecuted instantiation: connection.c:__ebim_insert Unexecuted instantiation: filters.c:__ebim_insert Unexecuted instantiation: flt_http_comp.c:__ebim_insert Unexecuted instantiation: haproxy.c:__ebim_insert Unexecuted instantiation: http_ana.c:__ebim_insert Unexecuted instantiation: http_ext.c:__ebim_insert Unexecuted instantiation: http_htx.c:__ebim_insert Unexecuted instantiation: proxy.c:__ebim_insert Unexecuted instantiation: resolvers.c:__ebim_insert Unexecuted instantiation: server.c:__ebim_insert Unexecuted instantiation: sock.c:__ebim_insert Unexecuted instantiation: sock_inet.c:__ebim_insert Unexecuted instantiation: stats-html.c:__ebim_insert Unexecuted instantiation: stats.c:__ebim_insert Unexecuted instantiation: stick_table.c:__ebim_insert Unexecuted instantiation: stream.c:__ebim_insert Unexecuted instantiation: tcpcheck.c:__ebim_insert Unexecuted instantiation: tools.c:__ebim_insert Unexecuted instantiation: backend.c:__ebim_insert Unexecuted instantiation: cache.c:__ebim_insert Unexecuted instantiation: cfgparse-listen.c:__ebim_insert Unexecuted instantiation: check.c:__ebim_insert Unexecuted instantiation: dict.c:__ebim_insert Unexecuted instantiation: ebimtree.c:__ebim_insert Unexecuted instantiation: ebistree.c:__ebim_insert Unexecuted instantiation: fcgi-app.c:__ebim_insert Unexecuted instantiation: guid.c:__ebim_insert Unexecuted instantiation: http_fetch.c:__ebim_insert Unexecuted instantiation: pattern.c:__ebim_insert Unexecuted instantiation: proto_tcp.c:__ebim_insert Unexecuted instantiation: h1_htx.c:__ebim_insert
323
324		#endif /* _EBIMTREE_H */