| /* |
| * Elastic Binary Trees - macros to manipulate Indirect String 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 |
| */ |
| |
| /* These functions and macros rely on Multi-Byte nodes */ |
| |
| #include <string.h> |
| #include "ebtree.h" |
| #include "ebpttree.h" |
| #include "ebimtree.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 ebistree.c, which simply relies on their inline version. |
| */ |
| REGPRM2 struct ebpt_node *ebis_lookup(struct eb_root *root, const char *x); |
| REGPRM2 struct ebpt_node *ebis_insert(struct eb_root *root, struct ebpt_node *new); |
| |
| /* Find the first occurence of a length <len> string <x> in the tree <root>. |
| * It's the caller's reponsibility to use this function only on trees which |
| * only contain zero-terminated strings, and that no null character is present |
| * in string <x> in the first <len> chars. If none can be found, return NULL. |
| */ |
| static forceinline struct ebpt_node * |
| ebis_lookup_len(struct eb_root *root, const char *x, unsigned int len) |
| { |
| struct ebpt_node *node; |
| |
| node = ebim_lookup(root, x, len); |
| if (!node || ((const char *)node->key)[len] != 0) |
| return NULL; |
| return node; |
| } |
| |
| /* Find the first occurence of a zero-terminated string <x> in the tree <root>. |
| * It's the caller's reponsibility to use this function only on trees which |
| * only contain zero-terminated strings. If none can be found, return NULL. |
| */ |
| static forceinline struct ebpt_node *__ebis_lookup(struct eb_root *root, const void *x) |
| { |
| struct ebpt_node *node; |
| eb_troot_t *troot; |
| int bit; |
| int node_bit; |
| |
| troot = root->b[EB_LEFT]; |
| if (unlikely(troot == NULL)) |
| return NULL; |
| |
| bit = 0; |
| while (1) { |
| if ((eb_gettag(troot) == EB_LEAF)) { |
| node = container_of(eb_untag(troot, EB_LEAF), |
| struct ebpt_node, node.branches); |
| if (strcmp(node->key, x) == 0) |
| return node; |
| else |
| return NULL; |
| } |
| 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 (strcmp(node->key, x) != 0) |
| return NULL; |
| |
| troot = node->node.branches.b[EB_LEFT]; |
| 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); |
| return node; |
| } |
| |
| /* OK, normal data node, let's walk down but don't compare data |
| * if we already reached the end of the key. |
| */ |
| if (likely(bit >= 0)) { |
| bit = string_equal_bits(x, node->key, bit); |
| if (likely(bit < node_bit)) { |
| if (bit >= 0) |
| return NULL; /* no more common bits */ |
| |
| /* bit < 0 : we reached the end of the key. If we |
| * are in a tree with unique keys, we can return |
| * this node. Otherwise we have to walk it down |
| * and stop comparing bits. |
| */ |
| if (eb_gettag(root->b[EB_RGHT])) |
| return node; |
| } |
| } |
| |
| troot = node->node.branches.b[(((unsigned char*)x)[node_bit >> 3] >> |
| (~node_bit & 7)) & 1]; |
| } |
| } |
| |
| /* Insert ebpt_node <new> into subtree starting at node root <root>. Only |
| * new->key needs be set with the zero-terminated string key. The ebpt_node is |
| * returned. If root->b[EB_RGHT]==1, the tree may only contain unique keys. The |
| * caller is responsible for properly terminating the key with a zero. |
| */ |
| static forceinline struct ebpt_node * |
| __ebis_insert(struct eb_root *root, struct ebpt_node *new) |
| { |
| 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; |
| } |
| |
| /* 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. |
| */ |
| if (bit >= 0) |
| bit = string_equal_bits(new->key, old->key, bit); |
| |
| if (bit < 0) { |
| /* key was already there */ |
| |
| /* we may refuse to duplicate this key if the tree is |
| * tagged as containing only unique keys. |
| */ |
| if (eb_gettag(root_right)) |
| return old; |
| |
| /* new arbitrarily goes to the right and tops the dup tree */ |
| 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; |
| new->node.bit = -1; |
| root->b[side] = eb_dotag(&new->node.branches, EB_NODE); |
| return new; |
| } |
| |
| diff = cmp_bits(new->key, old->key, bit); |
| if (diff < 0) { |
| /* new->key < old->key, new takes the left */ |
| 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 { |
| /* new->key > old->key, new takes 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; |
| } |
| 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 (bit >= 0 && (bit < old_node_bit || old_node_bit < 0)) |
| bit = string_equal_bits(new->key, old->key, bit); |
| |
| if (unlikely(bit < 0)) { |
| /* Perfect match, we must only stop on head of dup tree |
| * or walk down to a leaf. |
| */ |
| if (old_node_bit < 0) { |
| /* We know here that string_equal_bits matched all |
| * bits and that we're on top of a dup tree, then |
| * we can perform the dup insertion and return. |
| */ |
| struct eb_node *ret; |
| ret = eb_insert_dup(&old->node, &new->node); |
| return container_of(ret, struct ebpt_node, node); |
| } |
| /* OK so let's walk down */ |
| } |
| else if (bit < old_node_bit || old_node_bit < 0) { |
| /* The tree did not contain the key, or we stopped on top of a dup |
| * tree, possibly containing the key. In the former case, we insert |
| * <new> before the node <old>, and set ->bit to designate the lowest |
| * bit position in <new> which applies to ->branches.b[]. In the later |
| * case, we add the key to the existing dup tree. Note that we cannot |
| * enter here if we match an intermediate node's key that is not the |
| * head of a dup tree. |
| */ |
| eb_troot_t *new_left, *new_rght; |
| eb_troot_t *new_leaf, *old_node; |
| |
| 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; |
| |
| /* we can never match all bits here */ |
| 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 { |
| 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; |
| } |
| 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>. |
| * NOTE: we can't get here whit bit < 0 since we found a dup ! |
| */ |
| new->node.bit = bit; |
| root->b[side] = eb_dotag(&new->node.branches, EB_NODE); |
| return new; |
| } |
| |