/src/haproxy/src/eb64tree.c

Source
/*
 * Elastic Binary Trees - exported functions for operations on 64bit 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
 */

/* Consult eb64tree.h for more details about those functions */

#include <import/eb64tree.h>

struct eb64_node *eb64_insert(struct eb_root *root, struct eb64_node *new)
{
  return __eb64_insert(root, new);
}

struct eb64_node *eb64i_insert(struct eb_root *root, struct eb64_node *new)
{
  return __eb64i_insert(root, new);
}

struct eb64_node *eb64_lookup(struct eb_root *root, u64 x)
{
  return __eb64_lookup(root, x);
}

struct eb64_node *eb64i_lookup(struct eb_root *root, s64 x)
{
  return __eb64i_lookup(root, x);
}

/*
 * Find the last occurrence of the highest key in the tree <root>, which is
 * equal to or less than <x>. NULL is returned is no key matches.
 */
struct eb64_node *eb64_lookup_le(struct eb_root *root, u64 x)
{
  struct eb64_node *node;
  eb_troot_t *troot;
  u64 y, z;

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

  while (1) {
    if (unlikely(eb_gettag(troot) == EB_LEAF)) {
      /* We reached a leaf, which means that the whole upper
       * parts were common. We will return either the current
       * node or its next one if the former is too small.
       */
      node = container_of(eb_untag(troot, EB_LEAF),
              struct eb64_node, node.branches);
      if (node->key <= x)
        return node;
      /* return prev */
      troot = node->node.leaf_p;
      break;
    }
    node = container_of(eb_untag(troot, EB_NODE),
            struct eb64_node, node.branches);

    eb_prefetch(node->node.branches.b[0], 0);
    eb_prefetch(node->node.branches.b[1], 0);

    y = node->key;
    z = 1ULL << (node->node.bit & 63);
    troot = (x & z) ? node->node.branches.b[1] : node->node.branches.b[0];

    if (node->node.bit < 0) {
      /* We're at the top of a dup tree. Either we got a
       * matching value and we return the rightmost node, or
       * we don't and we skip the whole subtree to return the
       * prev node before the subtree. Note that since we're
       * at the top of the dup tree, we can simply return the
       * prev node without first trying to escape from the
       * tree.
       */
      if (node->key <= x) {
        troot = node->node.branches.b[EB_RGHT];
        while (eb_gettag(troot) != EB_LEAF)
          troot = (eb_untag(troot, EB_NODE))->b[EB_RGHT];
        return container_of(eb_untag(troot, EB_LEAF),
                struct eb64_node, node.branches);
      }
      /* return prev */
      troot = node->node.node_p;
      break;
    }

    if ((x ^ y) & -(z << 1)) {
      /* No more common bits at all. Either this node is too
       * small and we need to get its highest value, or it is
       * too large, and we need to get the prev value.
       */
      if ((node->key >> node->node.bit) < (x >> node->node.bit)) {
        troot = node->node.branches.b[EB_RGHT];
        return eb64_entry(eb_walk_down(troot, EB_RGHT), struct eb64_node, node);
      }

      /* Further values will be too high here, so return the prev
       * unique node (if it exists).
       */
      troot = node->node.node_p;
      break;
    }
  }

  /* If we get here, it means we want to report previous node before the
   * current one which is not above. <troot> is already initialised to
   * the parent's branches.
   */
  while (eb_gettag(troot) == EB_LEFT) {
    /* Walking up from left branch. We must ensure that we never
     * walk beyond root.
     */
    if (unlikely(eb_clrtag((eb_untag(troot, EB_LEFT))->b[EB_RGHT]) == NULL))
      return NULL;
    troot = (eb_root_to_node(eb_untag(troot, EB_LEFT)))->node_p;
  }
  /* Note that <troot> cannot be NULL at this stage */
  troot = (eb_untag(troot, EB_RGHT))->b[EB_LEFT];
  node = eb64_entry(eb_walk_down(troot, EB_RGHT), struct eb64_node, node);
  return node;
}

/*
 * Find the first occurrence of the lowest key in the tree <root>, which is
 * equal to or greater than <x>. NULL is returned is no key matches.
 */
struct eb64_node *eb64_lookup_ge(struct eb_root *root, u64 x)
{
  struct eb64_node *node;
  eb_troot_t *troot;
  u64 y, z;

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

  while (1) {
    if (unlikely(eb_gettag(troot) == EB_LEAF)) {
      /* We reached a leaf, which means that the whole upper
       * parts were common. We will return either the current
       * node or its next one if the former is too small.
       */
      node = container_of(eb_untag(troot, EB_LEAF),
              struct eb64_node, node.branches);
      if (node->key >= x)
        return node;
      /* return next */
      troot = node->node.leaf_p;
      break;
    }
    node = container_of(eb_untag(troot, EB_NODE),
            struct eb64_node, node.branches);

    eb_prefetch(node->node.branches.b[0], 0);
    eb_prefetch(node->node.branches.b[1], 0);

    y = node->key;
    z = 1ULL << (node->node.bit & 63);
    troot = (x & z) ? node->node.branches.b[1] : node->node.branches.b[0];

    if (node->node.bit < 0) {
      /* We're at the top of a dup tree. Either we got a
       * matching value and we return the leftmost node, or
       * we don't and we skip the whole subtree to return the
       * next node after the subtree. Note that since we're
       * at the top of the dup tree, we can simply return the
       * next node without first trying to escape from the
       * tree.
       */
      if (node->key >= x) {
        troot = node->node.branches.b[EB_LEFT];
        while (eb_gettag(troot) != EB_LEAF)
          troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
        return container_of(eb_untag(troot, EB_LEAF),
                struct eb64_node, node.branches);
      }
      /* return next */
      troot = node->node.node_p;
      break;
    }

    if ((x ^ y) & -(z << 1)) {
      /* No more common bits at all. Either this node is too
       * large and we need to get its lowest value, or it is too
       * small, and we need to get the next value.
       */
      if ((node->key >> node->node.bit) > (x >> node->node.bit)) {
        troot = node->node.branches.b[EB_LEFT];
        return eb64_entry(eb_walk_down(troot, EB_LEFT), struct eb64_node, node);
      }

      /* Further values will be too low here, so return the next
       * unique node (if it exists).
       */
      troot = node->node.node_p;
      break;
    }
  }

  /* If we get here, it means we want to report next node after the
   * current one which is not below. <troot> is already initialised
   * to the parent's branches.
   */
  while (eb_gettag(troot) != EB_LEFT)
    /* Walking up from right branch, so we cannot be below root */
    troot = (eb_root_to_node(eb_untag(troot, EB_RGHT)))->node_p;

  /* Note that <troot> cannot be NULL at this stage */
  troot = (eb_untag(troot, EB_LEFT))->b[EB_RGHT];
  if (eb_clrtag(troot) == NULL)
    return NULL;

  node = eb64_entry(eb_walk_down(troot, EB_LEFT), struct eb64_node, node);
  return node;
}

Coverage Report

Created: 2025-12-14 06:30

Line	Count	Source
1		/*
2		* Elastic Binary Trees - exported functions for operations on 64bit 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		/* Consult eb64tree.h for more details about those functions */
22
23		#include <import/eb64tree.h>
24
25		struct eb64_node eb64_insert(struct eb_root root, struct eb64_node *new)
26	0	{
27	0	return __eb64_insert(root, new);
28	0	}
29
30		struct eb64_node eb64i_insert(struct eb_root root, struct eb64_node *new)
31	0	{
32	0	return __eb64i_insert(root, new);
33	0	}
34
35		struct eb64_node eb64_lookup(struct eb_root root, u64 x)
36	0	{
37	0	return __eb64_lookup(root, x);
38	0	}
39
40		struct eb64_node eb64i_lookup(struct eb_root root, s64 x)
41	0	{
42	0	return __eb64i_lookup(root, x);
43	0	}
44
45		/*
46		* Find the last occurrence of the highest key in the tree <root>, which is
47		* equal to or less than <x>. NULL is returned is no key matches.
48		*/
49		struct eb64_node eb64_lookup_le(struct eb_root root, u64 x)
50	0	{
51	0	struct eb64_node *node;
52	0	eb_troot_t *troot;
53	0	u64 y, z;
54
55	0	troot = root->b[EB_LEFT];
56	0	if (unlikely(troot == NULL))
57	0	return NULL;
58
59	0	while (1) {
60	0	if (unlikely(eb_gettag(troot) == EB_LEAF)) {
61		/* We reached a leaf, which means that the whole upper
62		* parts were common. We will return either the current
63		* node or its next one if the former is too small.
64		*/
65	0	node = container_of(eb_untag(troot, EB_LEAF),
66	0	struct eb64_node, node.branches);
67	0	if (node->key <= x)
68	0	return node;
69		/* return prev */
70	0	troot = node->node.leaf_p;
71	0	break;
72	0	}
73	0	node = container_of(eb_untag(troot, EB_NODE),
74	0	struct eb64_node, node.branches);
75
76	0	eb_prefetch(node->node.branches.b[0], 0);
77	0	eb_prefetch(node->node.branches.b[1], 0);
78
79	0	y = node->key;
80	0	z = 1ULL << (node->node.bit & 63);
81	0	troot = (x & z) ? node->node.branches.b[1] : node->node.branches.b[0];
82
83	0	if (node->node.bit < 0) {
84		/* We're at the top of a dup tree. Either we got a
85		* matching value and we return the rightmost node, or
86		* we don't and we skip the whole subtree to return the
87		* prev node before the subtree. Note that since we're
88		* at the top of the dup tree, we can simply return the
89		* prev node without first trying to escape from the
90		* tree.
91		*/
92	0	if (node->key <= x) {
93	0	troot = node->node.branches.b[EB_RGHT];
94	0	while (eb_gettag(troot) != EB_LEAF)
95	0	troot = (eb_untag(troot, EB_NODE))->b[EB_RGHT];
96	0	return container_of(eb_untag(troot, EB_LEAF),
97	0	struct eb64_node, node.branches);
98	0	}
99		/* return prev */
100	0	troot = node->node.node_p;
101	0	break;
102	0	}
103
104	0	if ((x ^ y) & -(z << 1)) {
105		/* No more common bits at all. Either this node is too
106		* small and we need to get its highest value, or it is
107		* too large, and we need to get the prev value.
108		*/
109	0	if ((node->key >> node->node.bit) < (x >> node->node.bit)) {
110	0	troot = node->node.branches.b[EB_RGHT];
111	0	return eb64_entry(eb_walk_down(troot, EB_RGHT), struct eb64_node, node);
112	0	}
113
114		/* Further values will be too high here, so return the prev
115		* unique node (if it exists).
116		*/
117	0	troot = node->node.node_p;
118	0	break;
119	0	}
120	0	}
121
122		/* If we get here, it means we want to report previous node before the
123		* current one which is not above. <troot> is already initialised to
124		* the parent's branches.
125		*/
126	0	while (eb_gettag(troot) == EB_LEFT) {
127		/* Walking up from left branch. We must ensure that we never
128		* walk beyond root.
129		*/
130	0	if (unlikely(eb_clrtag((eb_untag(troot, EB_LEFT))->b[EB_RGHT]) == NULL))
131	0	return NULL;
132	0	troot = (eb_root_to_node(eb_untag(troot, EB_LEFT)))->node_p;
133	0	}
134		/* Note that <troot> cannot be NULL at this stage */
135	0	troot = (eb_untag(troot, EB_RGHT))->b[EB_LEFT];
136	0	node = eb64_entry(eb_walk_down(troot, EB_RGHT), struct eb64_node, node);
137	0	return node;
138	0	}
139
140		/*
141		* Find the first occurrence of the lowest key in the tree <root>, which is
142		* equal to or greater than <x>. NULL is returned is no key matches.
143		*/
144		struct eb64_node eb64_lookup_ge(struct eb_root root, u64 x)
145	0	{
146	0	struct eb64_node *node;
147	0	eb_troot_t *troot;
148	0	u64 y, z;
149
150	0	troot = root->b[EB_LEFT];
151	0	if (unlikely(troot == NULL))
152	0	return NULL;
153
154	0	while (1) {
155	0	if (unlikely(eb_gettag(troot) == EB_LEAF)) {
156		/* We reached a leaf, which means that the whole upper
157		* parts were common. We will return either the current
158		* node or its next one if the former is too small.
159		*/
160	0	node = container_of(eb_untag(troot, EB_LEAF),
161	0	struct eb64_node, node.branches);
162	0	if (node->key >= x)
163	0	return node;
164		/* return next */
165	0	troot = node->node.leaf_p;
166	0	break;
167	0	}
168	0	node = container_of(eb_untag(troot, EB_NODE),
169	0	struct eb64_node, node.branches);
170
171	0	eb_prefetch(node->node.branches.b[0], 0);
172	0	eb_prefetch(node->node.branches.b[1], 0);
173
174	0	y = node->key;
175	0	z = 1ULL << (node->node.bit & 63);
176	0	troot = (x & z) ? node->node.branches.b[1] : node->node.branches.b[0];
177
178	0	if (node->node.bit < 0) {
179		/* We're at the top of a dup tree. Either we got a
180		* matching value and we return the leftmost node, or
181		* we don't and we skip the whole subtree to return the
182		* next node after the subtree. Note that since we're
183		* at the top of the dup tree, we can simply return the
184		* next node without first trying to escape from the
185		* tree.
186		*/
187	0	if (node->key >= x) {
188	0	troot = node->node.branches.b[EB_LEFT];
189	0	while (eb_gettag(troot) != EB_LEAF)
190	0	troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
191	0	return container_of(eb_untag(troot, EB_LEAF),
192	0	struct eb64_node, node.branches);
193	0	}
194		/* return next */
195	0	troot = node->node.node_p;
196	0	break;
197	0	}
198
199	0	if ((x ^ y) & -(z << 1)) {
200		/* No more common bits at all. Either this node is too
201		* large and we need to get its lowest value, or it is too
202		* small, and we need to get the next value.
203		*/
204	0	if ((node->key >> node->node.bit) > (x >> node->node.bit)) {
205	0	troot = node->node.branches.b[EB_LEFT];
206	0	return eb64_entry(eb_walk_down(troot, EB_LEFT), struct eb64_node, node);
207	0	}
208
209		/* Further values will be too low here, so return the next
210		* unique node (if it exists).
211		*/
212	0	troot = node->node.node_p;
213	0	break;
214	0	}
215	0	}
216
217		/* If we get here, it means we want to report next node after the
218		* current one which is not below. <troot> is already initialised
219		* to the parent's branches.
220		*/
221	0	while (eb_gettag(troot) != EB_LEFT)
222		/* Walking up from right branch, so we cannot be below root */
223	0	troot = (eb_root_to_node(eb_untag(troot, EB_RGHT)))->node_p;
224
225		/* Note that <troot> cannot be NULL at this stage */
226	0	troot = (eb_untag(troot, EB_LEFT))->b[EB_RGHT];
227	0	if (eb_clrtag(troot) == NULL)
228	0	return NULL;
229
230	0	node = eb64_entry(eb_walk_down(troot, EB_LEFT), struct eb64_node, node);
231	0	return node;
232	0	}