Gitiles

/* | |

* 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 "eb64tree.h" | |

REGPRM2 struct eb64_node *eb64_insert(struct eb_root *root, struct eb64_node *new) | |

{ | |

return __eb64_insert(root, new); | |

} | |

REGPRM2 struct eb64_node *eb64i_insert(struct eb_root *root, struct eb64_node *new) | |

{ | |

return __eb64i_insert(root, new); | |

} | |

REGPRM2 struct eb64_node *eb64_lookup(struct eb_root *root, u64 x) | |

{ | |

return __eb64_lookup(root, x); | |

} | |

REGPRM2 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. | |

*/ | |

REGPRM2 struct eb64_node *eb64_lookup_le(struct eb_root *root, u64 x) | |

{ | |

struct eb64_node *node; | |

eb_troot_t *troot; | |

troot = root->b[EB_LEFT]; | |

if (unlikely(troot == NULL)) | |

return NULL; | |

while (1) { | |

if ((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); | |

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 ^ node->key) >> node->node.bit) >= EB_NODE_BRANCHES) { | |

/* 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; | |

} | |

troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK]; | |

} | |

/* 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. | |

*/ | |

REGPRM2 struct eb64_node *eb64_lookup_ge(struct eb_root *root, u64 x) | |

{ | |

struct eb64_node *node; | |

eb_troot_t *troot; | |

troot = root->b[EB_LEFT]; | |

if (unlikely(troot == NULL)) | |

return NULL; | |

while (1) { | |

if ((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); | |

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 ^ node->key) >> node->node.bit) >= EB_NODE_BRANCHES) { | |

/* 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; | |

} | |

troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK]; | |

} | |

/* 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; | |

} |