blob: a7e6b06f54ec6be29982aa3d9a437222b38482c8 [file] [log] [blame]
Willy Tarreauc2186022009-10-26 19:48:54 +01001/*
2 * Elastic Binary Trees - exported functions for operations on pointer 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/* Consult ebpttree.h for more details about those functions */
22
23#include "ebpttree.h"
24
Willy Tarreau03e78532020-02-25 07:38:05 +010025struct ebpt_node *ebpt_insert(struct eb_root *root, struct ebpt_node *new)
Willy Tarreauc2186022009-10-26 19:48:54 +010026{
27 return __ebpt_insert(root, new);
28}
29
Willy Tarreau03e78532020-02-25 07:38:05 +010030struct ebpt_node *ebpt_lookup(struct eb_root *root, void *x)
Willy Tarreauc2186022009-10-26 19:48:54 +010031{
32 return __ebpt_lookup(root, x);
33}
34
35/*
36 * Find the last occurrence of the highest key in the tree <root>, which is
37 * equal to or less than <x>. NULL is returned is no key matches.
38 */
Willy Tarreau03e78532020-02-25 07:38:05 +010039struct ebpt_node *ebpt_lookup_le(struct eb_root *root, void *x)
Willy Tarreauc2186022009-10-26 19:48:54 +010040{
41 struct ebpt_node *node;
42 eb_troot_t *troot;
43
44 troot = root->b[EB_LEFT];
45 if (unlikely(troot == NULL))
46 return NULL;
47
48 while (1) {
49 if ((eb_gettag(troot) == EB_LEAF)) {
50 /* We reached a leaf, which means that the whole upper
51 * parts were common. We will return either the current
52 * node or its next one if the former is too small.
53 */
54 node = container_of(eb_untag(troot, EB_LEAF),
55 struct ebpt_node, node.branches);
56 if (node->key <= x)
57 return node;
58 /* return prev */
59 troot = node->node.leaf_p;
60 break;
61 }
62 node = container_of(eb_untag(troot, EB_NODE),
63 struct ebpt_node, node.branches);
64
65 if (node->node.bit < 0) {
66 /* We're at the top of a dup tree. Either we got a
67 * matching value and we return the rightmost node, or
68 * we don't and we skip the whole subtree to return the
69 * prev node before the subtree. Note that since we're
70 * at the top of the dup tree, we can simply return the
71 * prev node without first trying to escape from the
72 * tree.
73 */
74 if (node->key <= x) {
75 troot = node->node.branches.b[EB_RGHT];
76 while (eb_gettag(troot) != EB_LEAF)
77 troot = (eb_untag(troot, EB_NODE))->b[EB_RGHT];
78 return container_of(eb_untag(troot, EB_LEAF),
79 struct ebpt_node, node.branches);
80 }
81 /* return prev */
82 troot = node->node.node_p;
83 break;
84 }
85
86 if ((((ptr_t)x ^ (ptr_t)node->key) >> node->node.bit) >= EB_NODE_BRANCHES) {
87 /* No more common bits at all. Either this node is too
88 * small and we need to get its highest value, or it is
89 * too large, and we need to get the prev value.
90 */
Willy Tarreau3a932442010-05-09 19:29:23 +020091 if (((ptr_t)node->key >> node->node.bit) < ((ptr_t)x >> node->node.bit)) {
Willy Tarreauc2186022009-10-26 19:48:54 +010092 troot = node->node.branches.b[EB_RGHT];
93 return ebpt_entry(eb_walk_down(troot, EB_RGHT), struct ebpt_node, node);
94 }
95
96 /* Further values will be too high here, so return the prev
97 * unique node (if it exists).
98 */
99 troot = node->node.node_p;
100 break;
101 }
102 troot = node->node.branches.b[((ptr_t)x >> node->node.bit) & EB_NODE_BRANCH_MASK];
103 }
104
105 /* If we get here, it means we want to report previous node before the
106 * current one which is not above. <troot> is already initialised to
107 * the parent's branches.
108 */
109 while (eb_gettag(troot) == EB_LEFT) {
110 /* Walking up from left branch. We must ensure that we never
111 * walk beyond root.
112 */
113 if (unlikely(eb_clrtag((eb_untag(troot, EB_LEFT))->b[EB_RGHT]) == NULL))
114 return NULL;
115 troot = (eb_root_to_node(eb_untag(troot, EB_LEFT)))->node_p;
116 }
117 /* Note that <troot> cannot be NULL at this stage */
118 troot = (eb_untag(troot, EB_RGHT))->b[EB_LEFT];
119 node = ebpt_entry(eb_walk_down(troot, EB_RGHT), struct ebpt_node, node);
120 return node;
121}
122
123/*
124 * Find the first occurrence of the lowest key in the tree <root>, which is
125 * equal to or greater than <x>. NULL is returned is no key matches.
126 */
Willy Tarreau03e78532020-02-25 07:38:05 +0100127struct ebpt_node *ebpt_lookup_ge(struct eb_root *root, void *x)
Willy Tarreauc2186022009-10-26 19:48:54 +0100128{
129 struct ebpt_node *node;
130 eb_troot_t *troot;
131
132 troot = root->b[EB_LEFT];
133 if (unlikely(troot == NULL))
134 return NULL;
135
136 while (1) {
137 if ((eb_gettag(troot) == EB_LEAF)) {
138 /* We reached a leaf, which means that the whole upper
139 * parts were common. We will return either the current
140 * node or its next one if the former is too small.
141 */
142 node = container_of(eb_untag(troot, EB_LEAF),
143 struct ebpt_node, node.branches);
144 if (node->key >= x)
145 return node;
146 /* return next */
147 troot = node->node.leaf_p;
148 break;
149 }
150 node = container_of(eb_untag(troot, EB_NODE),
151 struct ebpt_node, node.branches);
152
153 if (node->node.bit < 0) {
154 /* We're at the top of a dup tree. Either we got a
155 * matching value and we return the leftmost node, or
156 * we don't and we skip the whole subtree to return the
157 * next node after the subtree. Note that since we're
158 * at the top of the dup tree, we can simply return the
159 * next node without first trying to escape from the
160 * tree.
161 */
162 if (node->key >= x) {
163 troot = node->node.branches.b[EB_LEFT];
164 while (eb_gettag(troot) != EB_LEAF)
165 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
166 return container_of(eb_untag(troot, EB_LEAF),
167 struct ebpt_node, node.branches);
168 }
169 /* return next */
170 troot = node->node.node_p;
171 break;
172 }
173
174 if ((((ptr_t)x ^ (ptr_t)node->key) >> node->node.bit) >= EB_NODE_BRANCHES) {
175 /* No more common bits at all. Either this node is too
176 * large and we need to get its lowest value, or it is too
177 * small, and we need to get the next value.
178 */
179 if (((ptr_t)node->key >> node->node.bit) > ((ptr_t)x >> node->node.bit)) {
180 troot = node->node.branches.b[EB_LEFT];
181 return ebpt_entry(eb_walk_down(troot, EB_LEFT), struct ebpt_node, node);
182 }
183
184 /* Further values will be too low here, so return the next
185 * unique node (if it exists).
186 */
187 troot = node->node.node_p;
188 break;
189 }
190 troot = node->node.branches.b[((ptr_t)x >> node->node.bit) & EB_NODE_BRANCH_MASK];
191 }
192
193 /* If we get here, it means we want to report next node after the
194 * current one which is not below. <troot> is already initialised
195 * to the parent's branches.
196 */
197 while (eb_gettag(troot) != EB_LEFT)
198 /* Walking up from right branch, so we cannot be below root */
199 troot = (eb_root_to_node(eb_untag(troot, EB_RGHT)))->node_p;
200
201 /* Note that <troot> cannot be NULL at this stage */
202 troot = (eb_untag(troot, EB_LEFT))->b[EB_RGHT];
203 if (eb_clrtag(troot) == NULL)
204 return NULL;
205
206 node = ebpt_entry(eb_walk_down(troot, EB_LEFT), struct ebpt_node, node);
207 return node;
208}