Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 1 | /* |
| 2 | * Elastic Binary Trees - exported functions for operations on 32bit nodes. |
| 3 | * Version 6.0.6 with backports from v7-dev |
| 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 eb32sctree.h for more details about those functions */ |
| 22 | |
| 23 | #include "eb32sctree.h" |
| 24 | |
| 25 | |
| 26 | /* This function is used to build a tree of duplicates by adding a new node to |
| 27 | * a subtree of at least 2 entries. |
| 28 | */ |
| 29 | REGPRM1 struct eb32sc_node *eb32sc_insert_dup(struct eb_node *sub, struct eb_node *new, unsigned long scope) |
| 30 | { |
Willy Tarreau | 5d19fd4 | 2017-11-05 14:06:50 +0100 | [diff] [blame] | 31 | struct eb32sc_node *eb32; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 32 | struct eb_node *head = sub; |
| 33 | eb_troot_t *new_left = eb_dotag(&new->branches, EB_LEFT); |
| 34 | eb_troot_t *new_rght = eb_dotag(&new->branches, EB_RGHT); |
| 35 | eb_troot_t *new_leaf = eb_dotag(&new->branches, EB_LEAF); |
| 36 | |
| 37 | /* first, identify the deepest hole on the right branch */ |
| 38 | while (eb_gettag(head->branches.b[EB_RGHT]) != EB_LEAF) { |
| 39 | struct eb_node *last = head; |
Willy Tarreau | 5d19fd4 | 2017-11-05 14:06:50 +0100 | [diff] [blame] | 40 | |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 41 | head = container_of(eb_untag(head->branches.b[EB_RGHT], EB_NODE), |
| 42 | struct eb_node, branches); |
Willy Tarreau | d19ec7d | 2017-11-13 16:16:09 +0100 | [diff] [blame^] | 43 | |
| 44 | if (unlikely(head->bit > last->bit + 1)) { |
| 45 | /* there's a hole here, we must assign the top of the |
| 46 | * following sub-tree to <sub> and mark all intermediate |
| 47 | * nodes with the scope mask. |
| 48 | */ |
| 49 | do { |
| 50 | eb32 = container_of(sub, struct eb32sc_node, node); |
| 51 | if (!(eb32->node_s & scope)) |
| 52 | eb32->node_s |= scope; |
Willy Tarreau | 5d19fd4 | 2017-11-05 14:06:50 +0100 | [diff] [blame] | 53 | |
Willy Tarreau | d19ec7d | 2017-11-13 16:16:09 +0100 | [diff] [blame^] | 54 | sub = container_of(eb_untag(sub->branches.b[EB_RGHT], EB_NODE), |
| 55 | struct eb_node, branches); |
| 56 | } while (sub != head); |
| 57 | } |
Willy Tarreau | 5d19fd4 | 2017-11-05 14:06:50 +0100 | [diff] [blame] | 58 | |
Willy Tarreau | d19ec7d | 2017-11-13 16:16:09 +0100 | [diff] [blame^] | 59 | eb32 = container_of(head, struct eb32sc_node, node); |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 60 | } |
| 61 | |
| 62 | /* Here we have a leaf attached to (head)->b[EB_RGHT] */ |
| 63 | if (head->bit < -1) { |
| 64 | /* A hole exists just before the leaf, we insert there */ |
| 65 | new->bit = -1; |
| 66 | sub = container_of(eb_untag(head->branches.b[EB_RGHT], EB_LEAF), |
| 67 | struct eb_node, branches); |
| 68 | head->branches.b[EB_RGHT] = eb_dotag(&new->branches, EB_NODE); |
| 69 | |
| 70 | new->node_p = sub->leaf_p; |
| 71 | new->leaf_p = new_rght; |
| 72 | sub->leaf_p = new_left; |
| 73 | new->branches.b[EB_LEFT] = eb_dotag(&sub->branches, EB_LEAF); |
| 74 | new->branches.b[EB_RGHT] = new_leaf; |
Willy Tarreau | 5d19fd4 | 2017-11-05 14:06:50 +0100 | [diff] [blame] | 75 | eb32 = container_of(new, struct eb32sc_node, node); |
| 76 | eb32->node_s = container_of(sub, struct eb32sc_node, node)->leaf_s | scope; |
| 77 | return eb32; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 78 | } else { |
| 79 | int side; |
| 80 | /* No hole was found before a leaf. We have to insert above |
| 81 | * <sub>. Note that we cannot be certain that <sub> is attached |
| 82 | * to the right of its parent, as this is only true if <sub> |
| 83 | * is inside the dup tree, not at the head. |
| 84 | */ |
| 85 | new->bit = sub->bit - 1; /* install at the lowest level */ |
| 86 | side = eb_gettag(sub->node_p); |
| 87 | head = container_of(eb_untag(sub->node_p, side), struct eb_node, branches); |
| 88 | head->branches.b[side] = eb_dotag(&new->branches, EB_NODE); |
| 89 | |
| 90 | new->node_p = sub->node_p; |
| 91 | new->leaf_p = new_rght; |
| 92 | sub->node_p = new_left; |
| 93 | new->branches.b[EB_LEFT] = eb_dotag(&sub->branches, EB_NODE); |
| 94 | new->branches.b[EB_RGHT] = new_leaf; |
Willy Tarreau | 5d19fd4 | 2017-11-05 14:06:50 +0100 | [diff] [blame] | 95 | eb32 = container_of(new, struct eb32sc_node, node); |
| 96 | eb32->node_s = container_of(sub, struct eb32sc_node, node)->node_s | scope; |
| 97 | return eb32; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 98 | } |
| 99 | } |
| 100 | |
| 101 | /* Insert eb32sc_node <new> into subtree starting at node root <root>. Only |
| 102 | * new->key needs be set with the key. The eb32sc_node is returned. This |
| 103 | * implementation does NOT support unique trees. |
| 104 | */ |
| 105 | REGPRM2 struct eb32sc_node *eb32sc_insert(struct eb_root *root, struct eb32sc_node *new, unsigned long scope) |
| 106 | { |
| 107 | struct eb32sc_node *old; |
| 108 | unsigned int side; |
| 109 | eb_troot_t *troot, **up_ptr; |
| 110 | u32 newkey; /* caching the key saves approximately one cycle */ |
| 111 | eb_troot_t *new_left, *new_rght; |
| 112 | eb_troot_t *new_leaf; |
| 113 | int old_node_bit; |
Willy Tarreau | 5d19fd4 | 2017-11-05 14:06:50 +0100 | [diff] [blame] | 114 | unsigned long old_scope; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 115 | |
| 116 | side = EB_LEFT; |
| 117 | troot = root->b[EB_LEFT]; |
| 118 | if (unlikely(troot == NULL)) { |
| 119 | /* Tree is empty, insert the leaf part below the left branch */ |
| 120 | root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF); |
| 121 | new->node.leaf_p = eb_dotag(root, EB_LEFT); |
| 122 | new->node.node_p = NULL; /* node part unused */ |
Willy Tarreau | 5d19fd4 | 2017-11-05 14:06:50 +0100 | [diff] [blame] | 123 | new->node_s = scope; |
| 124 | new->leaf_s = scope; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 125 | return new; |
| 126 | } |
| 127 | |
| 128 | /* The tree descent is fairly easy : |
| 129 | * - first, check if we have reached a leaf node |
| 130 | * - second, check if we have gone too far |
| 131 | * - third, reiterate |
| 132 | * Everywhere, we use <new> for the node node we are inserting, <root> |
| 133 | * for the node we attach it to, and <old> for the node we are |
| 134 | * displacing below <new>. <troot> will always point to the future node |
| 135 | * (tagged with its type). <side> carries the side the node <new> is |
| 136 | * attached to below its parent, which is also where previous node |
| 137 | * was attached. <newkey> carries the key being inserted. |
| 138 | */ |
| 139 | newkey = new->key; |
| 140 | |
| 141 | while (1) { |
| 142 | if (eb_gettag(troot) == EB_LEAF) { |
| 143 | /* insert above a leaf */ |
| 144 | old = container_of(eb_untag(troot, EB_LEAF), |
| 145 | struct eb32sc_node, node.branches); |
| 146 | new->node.node_p = old->node.leaf_p; |
| 147 | up_ptr = &old->node.leaf_p; |
Willy Tarreau | 5d19fd4 | 2017-11-05 14:06:50 +0100 | [diff] [blame] | 148 | old_scope = old->leaf_s; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 149 | break; |
| 150 | } |
| 151 | |
| 152 | /* OK we're walking down this link */ |
| 153 | old = container_of(eb_untag(troot, EB_NODE), |
| 154 | struct eb32sc_node, node.branches); |
| 155 | old_node_bit = old->node.bit; |
| 156 | |
| 157 | /* Stop going down when we don't have common bits anymore. We |
| 158 | * also stop in front of a duplicates tree because it means we |
| 159 | * have to insert above. |
| 160 | */ |
| 161 | |
| 162 | if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */ |
| 163 | (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) { |
| 164 | /* The tree did not contain the key, so we insert <new> before the node |
| 165 | * <old>, and set ->bit to designate the lowest bit position in <new> |
| 166 | * which applies to ->branches.b[]. |
| 167 | */ |
| 168 | new->node.node_p = old->node.node_p; |
| 169 | up_ptr = &old->node.node_p; |
Willy Tarreau | 5d19fd4 | 2017-11-05 14:06:50 +0100 | [diff] [blame] | 170 | old_scope = old->node_s; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 171 | break; |
| 172 | } |
| 173 | |
| 174 | /* walk down */ |
Willy Tarreau | 5d19fd4 | 2017-11-05 14:06:50 +0100 | [diff] [blame] | 175 | if ((old->node_s | scope) != old->node_s) |
| 176 | old->node_s |= scope; |
| 177 | |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 178 | root = &old->node.branches; |
| 179 | side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK; |
| 180 | troot = root->b[side]; |
| 181 | } |
| 182 | |
| 183 | new_left = eb_dotag(&new->node.branches, EB_LEFT); |
| 184 | new_rght = eb_dotag(&new->node.branches, EB_RGHT); |
| 185 | new_leaf = eb_dotag(&new->node.branches, EB_LEAF); |
| 186 | |
| 187 | /* We need the common higher bits between new->key and old->key. |
| 188 | * What differences are there between new->key and the node here ? |
| 189 | * NOTE that bit(new) is always < bit(root) because highest |
| 190 | * bit of new->key and old->key are identical here (otherwise they |
| 191 | * would sit on different branches). |
| 192 | */ |
| 193 | |
| 194 | // note that if EB_NODE_BITS > 1, we should check that it's still >= 0 |
| 195 | new->node.bit = flsnz(new->key ^ old->key) - EB_NODE_BITS; |
Willy Tarreau | 5d19fd4 | 2017-11-05 14:06:50 +0100 | [diff] [blame] | 196 | new->leaf_s = scope; |
| 197 | new->node_s = old_scope | scope; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 198 | |
| 199 | if (new->key == old->key) { |
| 200 | new->node.bit = -1; /* mark as new dup tree, just in case */ |
| 201 | |
| 202 | if (eb_gettag(troot) != EB_LEAF) { |
| 203 | /* there was already a dup tree below */ |
| 204 | return eb32sc_insert_dup(&old->node, &new->node, scope); |
| 205 | } |
| 206 | /* otherwise fall through */ |
| 207 | } |
| 208 | |
| 209 | if (new->key >= old->key) { |
| 210 | new->node.branches.b[EB_LEFT] = troot; |
| 211 | new->node.branches.b[EB_RGHT] = new_leaf; |
| 212 | new->node.leaf_p = new_rght; |
| 213 | *up_ptr = new_left; |
| 214 | } |
| 215 | else { |
| 216 | new->node.branches.b[EB_LEFT] = new_leaf; |
| 217 | new->node.branches.b[EB_RGHT] = troot; |
| 218 | new->node.leaf_p = new_left; |
| 219 | *up_ptr = new_rght; |
| 220 | } |
| 221 | |
| 222 | /* Ok, now we are inserting <new> between <root> and <old>. <old>'s |
| 223 | * parent is already set to <new>, and the <root>'s branch is still in |
| 224 | * <side>. Update the root's leaf till we have it. Note that we can also |
| 225 | * find the side by checking the side of new->node.node_p. |
| 226 | */ |
| 227 | |
| 228 | root->b[side] = eb_dotag(&new->node.branches, EB_NODE); |
| 229 | return new; |
| 230 | } |
| 231 | |
| 232 | /* |
| 233 | * Find the first occurrence of the lowest key in the tree <root>, which is |
| 234 | * equal to or greater than <x>. NULL is returned is no key matches. |
| 235 | */ |
| 236 | REGPRM2 struct eb32sc_node *eb32sc_lookup_ge(struct eb_root *root, u32 x, unsigned long scope) |
| 237 | { |
| 238 | struct eb32sc_node *node; |
Willy Tarreau | d1d55ac | 2017-11-05 14:33:01 +0100 | [diff] [blame] | 239 | struct eb_root *curr; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 240 | eb_troot_t *troot; |
| 241 | |
| 242 | troot = root->b[EB_LEFT]; |
| 243 | if (unlikely(troot == NULL)) |
| 244 | return NULL; |
| 245 | |
| 246 | while (1) { |
| 247 | if ((eb_gettag(troot) == EB_LEAF)) { |
| 248 | /* We reached a leaf, which means that the whole upper |
| 249 | * parts were common. We will return either the current |
| 250 | * node or its next one if the former is too small. |
| 251 | */ |
| 252 | node = container_of(eb_untag(troot, EB_LEAF), |
| 253 | struct eb32sc_node, node.branches); |
Willy Tarreau | d1d55ac | 2017-11-05 14:33:01 +0100 | [diff] [blame] | 254 | if ((node->leaf_s & scope) && node->key >= x) |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 255 | return node; |
| 256 | /* return next */ |
| 257 | troot = node->node.leaf_p; |
| 258 | break; |
| 259 | } |
| 260 | node = container_of(eb_untag(troot, EB_NODE), |
| 261 | struct eb32sc_node, node.branches); |
| 262 | |
| 263 | if (node->node.bit < 0) { |
| 264 | /* We're at the top of a dup tree. Either we got a |
| 265 | * matching value and we return the leftmost node, or |
| 266 | * we don't and we skip the whole subtree to return the |
| 267 | * next node after the subtree. Note that since we're |
| 268 | * at the top of the dup tree, we can simply return the |
| 269 | * next node without first trying to escape from the |
| 270 | * tree. |
| 271 | */ |
Willy Tarreau | d1d55ac | 2017-11-05 14:33:01 +0100 | [diff] [blame] | 272 | if ((node->node_s & scope) && node->key >= x) |
| 273 | troot = eb_dotag(&node->node.branches, EB_LEFT); |
| 274 | else |
| 275 | troot = node->node.node_p; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 276 | break; |
| 277 | } |
| 278 | |
| 279 | if (((x ^ node->key) >> node->node.bit) >= EB_NODE_BRANCHES) { |
| 280 | /* No more common bits at all. Either this node is too |
| 281 | * large and we need to get its lowest value, or it is too |
| 282 | * small, and we need to get the next value. |
| 283 | */ |
Willy Tarreau | d1d55ac | 2017-11-05 14:33:01 +0100 | [diff] [blame] | 284 | if ((node->node_s & scope) && (node->key >> node->node.bit) > (x >> node->node.bit)) |
| 285 | troot = eb_dotag(&node->node.branches, EB_LEFT); |
| 286 | else |
| 287 | troot = node->node.node_p; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 288 | break; |
| 289 | } |
| 290 | troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK]; |
| 291 | } |
| 292 | |
| 293 | /* If we get here, it means we want to report next node after the |
| 294 | * current one which is not below. <troot> is already initialised |
| 295 | * to the parent's branches. |
| 296 | */ |
Willy Tarreau | d1d55ac | 2017-11-05 14:33:01 +0100 | [diff] [blame] | 297 | for (node = NULL; !node; troot = eb_root_to_node(curr)->node_p) { |
| 298 | if (eb_gettag(troot) != EB_LEFT) { |
| 299 | curr = eb_untag(troot, EB_RGHT); |
| 300 | continue; |
| 301 | } |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 302 | |
Willy Tarreau | d1d55ac | 2017-11-05 14:33:01 +0100 | [diff] [blame] | 303 | /* troot points to the branch location we're attached to by the |
| 304 | * left above, set curr to the corresponding eb_root. |
| 305 | */ |
| 306 | curr = eb_untag(troot, EB_LEFT); |
| 307 | |
| 308 | /* and go down by the right, but stop at the root */ |
| 309 | troot = curr->b[EB_RGHT]; |
| 310 | if (!eb_clrtag(troot)) |
| 311 | break; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 312 | |
Willy Tarreau | d1d55ac | 2017-11-05 14:33:01 +0100 | [diff] [blame] | 313 | node = eb32sc_walk_down_left(troot, scope); |
| 314 | } |
| 315 | return node; |
| 316 | //while (1) { |
| 317 | // while (eb_gettag(troot) != EB_LEFT) |
| 318 | // /* Walking up from right branch, so we cannot be below root */ |
| 319 | // troot = (eb_root_to_node(eb_untag(troot, EB_RGHT)))->node_p; |
| 320 | // |
| 321 | // /* Note that <t> cannot be NULL at this stage */ |
| 322 | // root = eb_untag(troot, EB_LEFT); |
| 323 | // troot = root->b[EB_RGHT]; |
| 324 | // if (eb_clrtag(troot) == NULL) |
| 325 | // return NULL; |
| 326 | // |
| 327 | // /* we can't be below the root here */ |
| 328 | // node = eb32sc_walk_down_left(troot, scope); |
| 329 | // if (node) |
| 330 | // return node; |
| 331 | // /* not found below, this means we have to go up */ |
| 332 | // troot = eb_root_to_node(root)->node_p; |
| 333 | //} |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 334 | } |
| 335 | |
Willy Tarreau | 8878b6c | 2017-11-05 21:23:21 +0100 | [diff] [blame] | 336 | /* |
| 337 | * Find the first occurrence of the lowest key in the tree <root> which is |
| 338 | * equal to or greater than <x>, matching scope <scope>. If not found, it loops |
| 339 | * back to the beginning of the tree. NULL is returned is no key matches. |
| 340 | */ |
| 341 | REGPRM2 struct eb32sc_node *eb32sc_lookup_ge_or_first(struct eb_root *root, u32 x, unsigned long scope) |
| 342 | { |
| 343 | struct eb32sc_node *eb32; |
| 344 | eb_troot_t *troot; |
| 345 | struct eb_root *curr; |
| 346 | |
| 347 | troot = root->b[EB_LEFT]; |
| 348 | if (unlikely(troot == NULL)) |
| 349 | return NULL; |
| 350 | |
| 351 | while (1) { |
| 352 | if ((eb_gettag(troot) == EB_LEAF)) { |
| 353 | /* We reached a leaf, which means that the whole upper |
| 354 | * parts were common. We will return either the current |
| 355 | * node or its next one if the former is too small. |
| 356 | */ |
| 357 | eb32 = container_of(eb_untag(troot, EB_LEAF), |
| 358 | struct eb32sc_node, node.branches); |
| 359 | if ((eb32->leaf_s & scope) && eb32->key >= x) |
| 360 | return eb32; |
| 361 | /* return next */ |
| 362 | troot = eb32->node.leaf_p; |
| 363 | break; |
| 364 | } |
| 365 | eb32 = container_of(eb_untag(troot, EB_NODE), |
| 366 | struct eb32sc_node, node.branches); |
| 367 | |
| 368 | if (eb32->node.bit < 0) { |
| 369 | /* We're at the top of a dup tree. Either we got a |
| 370 | * matching value and we return the leftmost node, or |
| 371 | * we don't and we skip the whole subtree to return the |
| 372 | * next node after the subtree. Note that since we're |
| 373 | * at the top of the dup tree, we can simply return the |
| 374 | * next node without first trying to escape from the |
| 375 | * tree. |
| 376 | */ |
| 377 | if ((eb32->node_s & scope) && eb32->key >= x) |
| 378 | troot = eb_dotag(&eb32->node.branches, EB_LEFT); |
| 379 | else |
| 380 | troot = eb32->node.node_p; |
| 381 | break; |
| 382 | } |
| 383 | |
| 384 | if (((x ^ eb32->key) >> eb32->node.bit) >= EB_NODE_BRANCHES) { |
| 385 | /* No more common bits at all. Either this node is too |
| 386 | * large and we need to get its lowest value, or it is too |
| 387 | * small, and we need to get the next value. |
| 388 | */ |
| 389 | if ((eb32->node_s & scope) && (eb32->key >> eb32->node.bit) > (x >> eb32->node.bit)) |
| 390 | troot = eb_dotag(&eb32->node.branches, EB_LEFT); |
| 391 | else |
| 392 | troot = eb32->node.node_p; |
| 393 | break; |
| 394 | } |
| 395 | troot = eb32->node.branches.b[(x >> eb32->node.bit) & EB_NODE_BRANCH_MASK]; |
| 396 | } |
| 397 | |
| 398 | /* If we get here, it means we want to report next node after the |
| 399 | * current one which is not below. <troot> is already initialised |
| 400 | * to the parent's branches. |
| 401 | */ |
| 402 | for (eb32 = NULL; !eb32; troot = eb_root_to_node(curr)->node_p) { |
| 403 | if (eb_gettag(troot) != EB_LEFT) { |
| 404 | curr = eb_untag(troot, EB_RGHT); |
| 405 | continue; |
| 406 | } |
| 407 | |
| 408 | /* troot points to the branch location we're attached to by the |
| 409 | * left above, set curr to the corresponding eb_root. |
| 410 | */ |
| 411 | curr = eb_untag(troot, EB_LEFT); |
| 412 | |
| 413 | /* and go down by the right, but stop at the root */ |
| 414 | troot = curr->b[EB_RGHT]; |
| 415 | if (!eb_clrtag(troot)) |
| 416 | break; |
| 417 | |
| 418 | eb32 = eb32sc_walk_down_left(troot, scope); |
| 419 | } |
| 420 | |
| 421 | if (!eb32) |
| 422 | eb32 = eb32sc_walk_down_left(root->b[EB_LEFT], scope); |
| 423 | |
| 424 | return eb32; |
| 425 | } |
| 426 | |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 427 | /* Removes a leaf node from the tree if it was still in it. Marks the node |
| 428 | * as unlinked. |
| 429 | */ |
| 430 | void eb32sc_delete(struct eb32sc_node *eb32) |
| 431 | { |
| 432 | struct eb_node *node = &eb32->node; |
| 433 | unsigned int pside, gpside, sibtype; |
| 434 | struct eb_node *parent; |
| 435 | struct eb_root *gparent; |
Willy Tarreau | d19ec7d | 2017-11-13 16:16:09 +0100 | [diff] [blame^] | 436 | unsigned long scope; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 437 | |
| 438 | if (!node->leaf_p) |
| 439 | return; |
| 440 | |
| 441 | /* we need the parent, our side, and the grand parent */ |
| 442 | pside = eb_gettag(node->leaf_p); |
| 443 | parent = eb_root_to_node(eb_untag(node->leaf_p, pside)); |
| 444 | |
| 445 | /* We likely have to release the parent link, unless it's the root, |
| 446 | * in which case we only set our branch to NULL. Note that we can |
| 447 | * only be attached to the root by its left branch. |
| 448 | */ |
| 449 | |
| 450 | if (eb_clrtag(parent->branches.b[EB_RGHT]) == NULL) { |
| 451 | /* we're just below the root, it's trivial. */ |
| 452 | parent->branches.b[EB_LEFT] = NULL; |
| 453 | goto delete_unlink; |
| 454 | } |
| 455 | |
| 456 | /* To release our parent, we have to identify our sibling, and reparent |
| 457 | * it directly to/from the grand parent. Note that the sibling can |
| 458 | * either be a link or a leaf. |
| 459 | */ |
| 460 | |
| 461 | gpside = eb_gettag(parent->node_p); |
| 462 | gparent = eb_untag(parent->node_p, gpside); |
| 463 | |
| 464 | gparent->b[gpside] = parent->branches.b[!pside]; |
| 465 | sibtype = eb_gettag(gparent->b[gpside]); |
| 466 | |
| 467 | if (sibtype == EB_LEAF) { |
| 468 | eb_root_to_node(eb_untag(gparent->b[gpside], EB_LEAF))->leaf_p = |
| 469 | eb_dotag(gparent, gpside); |
| 470 | } else { |
| 471 | eb_root_to_node(eb_untag(gparent->b[gpside], EB_NODE))->node_p = |
| 472 | eb_dotag(gparent, gpside); |
| 473 | } |
| 474 | /* Mark the parent unused. Note that we do not check if the parent is |
| 475 | * our own node, but that's not a problem because if it is, it will be |
| 476 | * marked unused at the same time, which we'll use below to know we can |
| 477 | * safely remove it. |
| 478 | */ |
| 479 | parent->node_p = NULL; |
| 480 | |
| 481 | /* The parent node has been detached, and is currently unused. It may |
| 482 | * belong to another node, so we cannot remove it that way. Also, our |
| 483 | * own node part might still be used. so we can use this spare node |
| 484 | * to replace ours if needed. |
| 485 | */ |
| 486 | |
| 487 | /* If our link part is unused, we can safely exit now */ |
| 488 | if (!node->node_p) |
| 489 | goto delete_unlink; |
| 490 | |
| 491 | /* From now on, <node> and <parent> are necessarily different, and the |
| 492 | * <node>'s node part is in use. By definition, <parent> is at least |
Willy Tarreau | ef8d0dc | 2017-11-05 18:06:22 +0100 | [diff] [blame] | 493 | * below <node>, so keeping its key for the bit string is OK. However |
| 494 | * its scope must be enlarged to cover the new branch it absorbs. |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 495 | */ |
| 496 | |
| 497 | parent->node_p = node->node_p; |
| 498 | parent->branches = node->branches; |
| 499 | parent->bit = node->bit; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 500 | |
| 501 | /* We must now update the new node's parent... */ |
| 502 | gpside = eb_gettag(parent->node_p); |
| 503 | gparent = eb_untag(parent->node_p, gpside); |
| 504 | gparent->b[gpside] = eb_dotag(&parent->branches, EB_NODE); |
| 505 | |
| 506 | /* ... and its branches */ |
Willy Tarreau | d19ec7d | 2017-11-13 16:16:09 +0100 | [diff] [blame^] | 507 | scope = 0; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 508 | for (pside = 0; pside <= 1; pside++) { |
| 509 | if (eb_gettag(parent->branches.b[pside]) == EB_NODE) { |
| 510 | eb_root_to_node(eb_untag(parent->branches.b[pside], EB_NODE))->node_p = |
| 511 | eb_dotag(&parent->branches, pside); |
Willy Tarreau | d19ec7d | 2017-11-13 16:16:09 +0100 | [diff] [blame^] | 512 | scope |= container_of(eb_untag(parent->branches.b[pside], EB_NODE), struct eb32sc_node, node.branches)->node_s; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 513 | } else { |
| 514 | eb_root_to_node(eb_untag(parent->branches.b[pside], EB_LEAF))->leaf_p = |
| 515 | eb_dotag(&parent->branches, pside); |
Willy Tarreau | d19ec7d | 2017-11-13 16:16:09 +0100 | [diff] [blame^] | 516 | scope |= container_of(eb_untag(parent->branches.b[pside], EB_LEAF), struct eb32sc_node, node.branches)->leaf_s; |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 517 | } |
| 518 | } |
Willy Tarreau | d19ec7d | 2017-11-13 16:16:09 +0100 | [diff] [blame^] | 519 | container_of(parent, struct eb32sc_node, node)->node_s = scope; |
| 520 | |
Willy Tarreau | ca30839 | 2017-11-05 13:31:29 +0100 | [diff] [blame] | 521 | delete_unlink: |
| 522 | /* Now the node has been completely unlinked */ |
| 523 | node->leaf_p = NULL; |
| 524 | return; /* tree is not empty yet */ |
| 525 | } |