blob: 1abb4c8b86e29440db77fa30f2973b7d8cd3c1da [file] [log] [blame]
Willy Tarreauc2186022009-10-26 19:48:54 +01001/*
2 * Elastic Binary Trees - exported functions for operations on 64bit nodes.
3 * (C) 2002-2007 - Willy Tarreau <w@1wt.eu>
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18 */
19
20/* Consult eb64tree.h for more details about those functions */
21
22#include "eb64tree.h"
23
24REGPRM2 struct eb64_node *eb64_insert(struct eb_root *root, struct eb64_node *new)
25{
26 return __eb64_insert(root, new);
27}
28
29REGPRM2 struct eb64_node *eb64i_insert(struct eb_root *root, struct eb64_node *new)
30{
31 return __eb64i_insert(root, new);
32}
33
34REGPRM2 struct eb64_node *eb64_lookup(struct eb_root *root, u64 x)
35{
36 return __eb64_lookup(root, x);
37}
38
39REGPRM2 struct eb64_node *eb64i_lookup(struct eb_root *root, s64 x)
40{
41 return __eb64i_lookup(root, x);
42}
43
44/*
45 * Find the last occurrence of the highest key in the tree <root>, which is
46 * equal to or less than <x>. NULL is returned is no key matches.
47 */
48REGPRM2 struct eb64_node *eb64_lookup_le(struct eb_root *root, u64 x)
49{
50 struct eb64_node *node;
51 eb_troot_t *troot;
52
53 troot = root->b[EB_LEFT];
54 if (unlikely(troot == NULL))
55 return NULL;
56
57 while (1) {
58 if ((eb_gettag(troot) == EB_LEAF)) {
59 /* We reached a leaf, which means that the whole upper
60 * parts were common. We will return either the current
61 * node or its next one if the former is too small.
62 */
63 node = container_of(eb_untag(troot, EB_LEAF),
64 struct eb64_node, node.branches);
65 if (node->key <= x)
66 return node;
67 /* return prev */
68 troot = node->node.leaf_p;
69 break;
70 }
71 node = container_of(eb_untag(troot, EB_NODE),
72 struct eb64_node, node.branches);
73
74 if (node->node.bit < 0) {
75 /* We're at the top of a dup tree. Either we got a
76 * matching value and we return the rightmost node, or
77 * we don't and we skip the whole subtree to return the
78 * prev node before the subtree. Note that since we're
79 * at the top of the dup tree, we can simply return the
80 * prev node without first trying to escape from the
81 * tree.
82 */
83 if (node->key <= x) {
84 troot = node->node.branches.b[EB_RGHT];
85 while (eb_gettag(troot) != EB_LEAF)
86 troot = (eb_untag(troot, EB_NODE))->b[EB_RGHT];
87 return container_of(eb_untag(troot, EB_LEAF),
88 struct eb64_node, node.branches);
89 }
90 /* return prev */
91 troot = node->node.node_p;
92 break;
93 }
94
95 if (((x ^ node->key) >> node->node.bit) >= EB_NODE_BRANCHES) {
96 /* No more common bits at all. Either this node is too
97 * small and we need to get its highest value, or it is
98 * too large, and we need to get the prev value.
99 */
100 if ((node->key >> node->node.bit) > (x >> node->node.bit)) {
101 troot = node->node.branches.b[EB_RGHT];
102 return eb64_entry(eb_walk_down(troot, EB_RGHT), struct eb64_node, node);
103 }
104
105 /* Further values will be too high here, so return the prev
106 * unique node (if it exists).
107 */
108 troot = node->node.node_p;
109 break;
110 }
111 troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
112 }
113
114 /* If we get here, it means we want to report previous node before the
115 * current one which is not above. <troot> is already initialised to
116 * the parent's branches.
117 */
118 while (eb_gettag(troot) == EB_LEFT) {
119 /* Walking up from left branch. We must ensure that we never
120 * walk beyond root.
121 */
122 if (unlikely(eb_clrtag((eb_untag(troot, EB_LEFT))->b[EB_RGHT]) == NULL))
123 return NULL;
124 troot = (eb_root_to_node(eb_untag(troot, EB_LEFT)))->node_p;
125 }
126 /* Note that <troot> cannot be NULL at this stage */
127 troot = (eb_untag(troot, EB_RGHT))->b[EB_LEFT];
128 node = eb64_entry(eb_walk_down(troot, EB_RGHT), struct eb64_node, node);
129 return node;
130}
131
132/*
133 * Find the first occurrence of the lowest key in the tree <root>, which is
134 * equal to or greater than <x>. NULL is returned is no key matches.
135 */
136REGPRM2 struct eb64_node *eb64_lookup_ge(struct eb_root *root, u64 x)
137{
138 struct eb64_node *node;
139 eb_troot_t *troot;
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 /* We reached a leaf, which means that the whole upper
148 * parts were common. We will return either the current
149 * node or its next one if the former is too small.
150 */
151 node = container_of(eb_untag(troot, EB_LEAF),
152 struct eb64_node, node.branches);
153 if (node->key >= x)
154 return node;
155 /* return next */
156 troot = node->node.leaf_p;
157 break;
158 }
159 node = container_of(eb_untag(troot, EB_NODE),
160 struct eb64_node, node.branches);
161
162 if (node->node.bit < 0) {
163 /* We're at the top of a dup tree. Either we got a
164 * matching value and we return the leftmost node, or
165 * we don't and we skip the whole subtree to return the
166 * next node after the subtree. Note that since we're
167 * at the top of the dup tree, we can simply return the
168 * next node without first trying to escape from the
169 * tree.
170 */
171 if (node->key >= x) {
172 troot = node->node.branches.b[EB_LEFT];
173 while (eb_gettag(troot) != EB_LEAF)
174 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
175 return container_of(eb_untag(troot, EB_LEAF),
176 struct eb64_node, node.branches);
177 }
178 /* return next */
179 troot = node->node.node_p;
180 break;
181 }
182
183 if (((x ^ node->key) >> node->node.bit) >= EB_NODE_BRANCHES) {
184 /* No more common bits at all. Either this node is too
185 * large and we need to get its lowest value, or it is too
186 * small, and we need to get the next value.
187 */
188 if ((node->key >> node->node.bit) > (x >> node->node.bit)) {
189 troot = node->node.branches.b[EB_LEFT];
190 return eb64_entry(eb_walk_down(troot, EB_LEFT), struct eb64_node, node);
191 }
192
193 /* Further values will be too low here, so return the next
194 * unique node (if it exists).
195 */
196 troot = node->node.node_p;
197 break;
198 }
199 troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
200 }
201
202 /* If we get here, it means we want to report next node after the
203 * current one which is not below. <troot> is already initialised
204 * to the parent's branches.
205 */
206 while (eb_gettag(troot) != EB_LEFT)
207 /* Walking up from right branch, so we cannot be below root */
208 troot = (eb_root_to_node(eb_untag(troot, EB_RGHT)))->node_p;
209
210 /* Note that <troot> cannot be NULL at this stage */
211 troot = (eb_untag(troot, EB_LEFT))->b[EB_RGHT];
212 if (eb_clrtag(troot) == NULL)
213 return NULL;
214
215 node = eb64_entry(eb_walk_down(troot, EB_LEFT), struct eb64_node, node);
216 return node;
217}