"Fossies" - the Fresh Open Source Software Archive

Member "haproxy-2.0.0/ebtree/ebpttree.h" (16 Jun 2019, 5962 Bytes) of package /linux/misc/haproxy-2.0.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "ebpttree.h" see the Fossies "Dox" file reference documentation.

    1 /*
    2  * Elastic Binary Trees - macros and structures for operations on pointer nodes.
    3  * Version 6.0.6
    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 #ifndef _EBPTTREE_H
   22 #define _EBPTTREE_H
   23 
   24 #include "ebtree.h"
   25 #include "eb32tree.h"
   26 #include "eb64tree.h"
   27 
   28 
   29 /* Return the structure of type <type> whose member <member> points to <ptr> */
   30 #define ebpt_entry(ptr, type, member) container_of(ptr, type, member)
   31 
   32 #define EBPT_ROOT   EB_ROOT
   33 #define EBPT_TREE_HEAD  EB_TREE_HEAD
   34 
   35 /* on *almost* all platforms, a pointer can be cast into a size_t which is unsigned */
   36 #ifndef PTR_INT_TYPE
   37 #define PTR_INT_TYPE    size_t
   38 #endif
   39 
   40 typedef PTR_INT_TYPE ptr_t;
   41 
   42 /* This structure carries a node, a leaf, and a key. It must start with the
   43  * eb_node so that it can be cast into an eb_node. We could also have put some
   44  * sort of transparent union here to reduce the indirection level, but the fact
   45  * is, the end user is not meant to manipulate internals, so this is pointless.
   46  * Internally, it is automatically cast as an eb32_node or eb64_node.
   47  */
   48 struct ebpt_node {
   49     struct eb_node node; /* the tree node, must be at the beginning */
   50     void *key;
   51 };
   52 
   53 /*
   54  * Exported functions and macros.
   55  * Many of them are always inlined because they are extremely small, and
   56  * are generally called at most once or twice in a program.
   57  */
   58 
   59 /* Return leftmost node in the tree, or NULL if none */
   60 static forceinline struct ebpt_node *ebpt_first(struct eb_root *root)
   61 {
   62     return ebpt_entry(eb_first(root), struct ebpt_node, node);
   63 }
   64 
   65 /* Return rightmost node in the tree, or NULL if none */
   66 static forceinline struct ebpt_node *ebpt_last(struct eb_root *root)
   67 {
   68     return ebpt_entry(eb_last(root), struct ebpt_node, node);
   69 }
   70 
   71 /* Return next node in the tree, or NULL if none */
   72 static forceinline struct ebpt_node *ebpt_next(struct ebpt_node *ebpt)
   73 {
   74     return ebpt_entry(eb_next(&ebpt->node), struct ebpt_node, node);
   75 }
   76 
   77 /* Return previous node in the tree, or NULL if none */
   78 static forceinline struct ebpt_node *ebpt_prev(struct ebpt_node *ebpt)
   79 {
   80     return ebpt_entry(eb_prev(&ebpt->node), struct ebpt_node, node);
   81 }
   82 
   83 /* Return next leaf node within a duplicate sub-tree, or NULL if none. */
   84 static inline struct ebpt_node *ebpt_next_dup(struct ebpt_node *ebpt)
   85 {
   86     return ebpt_entry(eb_next_dup(&ebpt->node), struct ebpt_node, node);
   87 }
   88 
   89 /* Return previous leaf node within a duplicate sub-tree, or NULL if none. */
   90 static inline struct ebpt_node *ebpt_prev_dup(struct ebpt_node *ebpt)
   91 {
   92     return ebpt_entry(eb_prev_dup(&ebpt->node), struct ebpt_node, node);
   93 }
   94 
   95 /* Return next node in the tree, skipping duplicates, or NULL if none */
   96 static forceinline struct ebpt_node *ebpt_next_unique(struct ebpt_node *ebpt)
   97 {
   98     return ebpt_entry(eb_next_unique(&ebpt->node), struct ebpt_node, node);
   99 }
  100 
  101 /* Return previous node in the tree, skipping duplicates, or NULL if none */
  102 static forceinline struct ebpt_node *ebpt_prev_unique(struct ebpt_node *ebpt)
  103 {
  104     return ebpt_entry(eb_prev_unique(&ebpt->node), struct ebpt_node, node);
  105 }
  106 
  107 /* Delete node from the tree if it was linked in. Mark the node unused. Note
  108  * that this function relies on a non-inlined generic function: eb_delete.
  109  */
  110 static forceinline void ebpt_delete(struct ebpt_node *ebpt)
  111 {
  112     eb_delete(&ebpt->node);
  113 }
  114 
  115 /*
  116  * The following functions are inlined but derived from the integer versions.
  117  */
  118 static forceinline struct ebpt_node *ebpt_lookup(struct eb_root *root, void *x)
  119 {
  120     if (sizeof(void *) == 4)
  121         return (struct ebpt_node *)eb32_lookup(root, (u32)(PTR_INT_TYPE)x);
  122     else
  123         return (struct ebpt_node *)eb64_lookup(root, (u64)(PTR_INT_TYPE)x);
  124 }
  125 
  126 static forceinline struct ebpt_node *ebpt_lookup_le(struct eb_root *root, void *x)
  127 {
  128     if (sizeof(void *) == 4)
  129         return (struct ebpt_node *)eb32_lookup_le(root, (u32)(PTR_INT_TYPE)x);
  130     else
  131         return (struct ebpt_node *)eb64_lookup_le(root, (u64)(PTR_INT_TYPE)x);
  132 }
  133 
  134 static forceinline struct ebpt_node *ebpt_lookup_ge(struct eb_root *root, void *x)
  135 {
  136     if (sizeof(void *) == 4)
  137         return (struct ebpt_node *)eb32_lookup_ge(root, (u32)(PTR_INT_TYPE)x);
  138     else
  139         return (struct ebpt_node *)eb64_lookup_ge(root, (u64)(PTR_INT_TYPE)x);
  140 }
  141 
  142 static forceinline struct ebpt_node *ebpt_insert(struct eb_root *root, struct ebpt_node *new)
  143 {
  144     if (sizeof(void *) == 4)
  145         return (struct ebpt_node *)eb32_insert(root, (struct eb32_node *)new);
  146     else
  147         return (struct ebpt_node *)eb64_insert(root, (struct eb64_node *)new);
  148 }
  149 
  150 /*
  151  * The following functions are less likely to be used directly, because
  152  * their code is larger. The non-inlined version is preferred.
  153  */
  154 
  155 /* Delete node from the tree if it was linked in. Mark the node unused. */
  156 static forceinline void __ebpt_delete(struct ebpt_node *ebpt)
  157 {
  158     __eb_delete(&ebpt->node);
  159 }
  160 
  161 static forceinline struct ebpt_node *__ebpt_lookup(struct eb_root *root, void *x)
  162 {
  163     if (sizeof(void *) == 4)
  164         return (struct ebpt_node *)__eb32_lookup(root, (u32)(PTR_INT_TYPE)x);
  165     else
  166         return (struct ebpt_node *)__eb64_lookup(root, (u64)(PTR_INT_TYPE)x);
  167 }
  168 
  169 static forceinline struct ebpt_node *__ebpt_insert(struct eb_root *root, struct ebpt_node *new)
  170 {
  171     if (sizeof(void *) == 4)
  172         return (struct ebpt_node *)__eb32_insert(root, (struct eb32_node *)new);
  173     else
  174         return (struct ebpt_node *)__eb64_insert(root, (struct eb64_node *)new);
  175 }
  176 
  177 #endif /* _EBPT_TREE_H */