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 * We always align the key since the struct itself will be padded to the same
48 * size anyway.
49 */
50 struct ebpt_node {
51 struct eb_node node; /* the tree node, must be at the beginning */
52 ALWAYS_ALIGN(sizeof(void*));
53 void *key;
54 } ALIGNED(sizeof(void*));
55
56 /*
57 * Exported functions and macros.
58 * Many of them are always inlined because they are extremely small, and
59 * are generally called at most once or twice in a program.
60 */
61
62 /* Return leftmost node in the tree, or NULL if none */
ebpt_first(struct eb_root * root)63 static forceinline struct ebpt_node *ebpt_first(struct eb_root *root)
64 {
65 return ebpt_entry(eb_first(root), struct ebpt_node, node);
66 }
67
68 /* Return rightmost node in the tree, or NULL if none */
ebpt_last(struct eb_root * root)69 static forceinline struct ebpt_node *ebpt_last(struct eb_root *root)
70 {
71 return ebpt_entry(eb_last(root), struct ebpt_node, node);
72 }
73
74 /* Return next node in the tree, or NULL if none */
ebpt_next(struct ebpt_node * ebpt)75 static forceinline struct ebpt_node *ebpt_next(struct ebpt_node *ebpt)
76 {
77 return ebpt_entry(eb_next(&ebpt->node), struct ebpt_node, node);
78 }
79
80 /* Return previous node in the tree, or NULL if none */
ebpt_prev(struct ebpt_node * ebpt)81 static forceinline struct ebpt_node *ebpt_prev(struct ebpt_node *ebpt)
82 {
83 return ebpt_entry(eb_prev(&ebpt->node), struct ebpt_node, node);
84 }
85
86 /* Return next leaf node within a duplicate sub-tree, or NULL if none. */
ebpt_next_dup(struct ebpt_node * ebpt)87 static inline struct ebpt_node *ebpt_next_dup(struct ebpt_node *ebpt)
88 {
89 return ebpt_entry(eb_next_dup(&ebpt->node), struct ebpt_node, node);
90 }
91
92 /* Return previous leaf node within a duplicate sub-tree, or NULL if none. */
ebpt_prev_dup(struct ebpt_node * ebpt)93 static inline struct ebpt_node *ebpt_prev_dup(struct ebpt_node *ebpt)
94 {
95 return ebpt_entry(eb_prev_dup(&ebpt->node), struct ebpt_node, node);
96 }
97
98 /* Return next node in the tree, skipping duplicates, or NULL if none */
ebpt_next_unique(struct ebpt_node * ebpt)99 static forceinline struct ebpt_node *ebpt_next_unique(struct ebpt_node *ebpt)
100 {
101 return ebpt_entry(eb_next_unique(&ebpt->node), struct ebpt_node, node);
102 }
103
104 /* Return previous node in the tree, skipping duplicates, or NULL if none */
ebpt_prev_unique(struct ebpt_node * ebpt)105 static forceinline struct ebpt_node *ebpt_prev_unique(struct ebpt_node *ebpt)
106 {
107 return ebpt_entry(eb_prev_unique(&ebpt->node), struct ebpt_node, node);
108 }
109
110 /* Delete node from the tree if it was linked in. Mark the node unused. Note
111 * that this function relies on a non-inlined generic function: eb_delete.
112 */
ebpt_delete(struct ebpt_node * ebpt)113 static forceinline void ebpt_delete(struct ebpt_node *ebpt)
114 {
115 eb_delete(&ebpt->node);
116 }
117
118 /*
119 * The following functions are inlined but derived from the integer versions.
120 */
ebpt_lookup(struct eb_root * root,void * x)121 static forceinline struct ebpt_node *ebpt_lookup(struct eb_root *root, void *x)
122 {
123 if (sizeof(void *) == 4)
124 return (struct ebpt_node *)eb32_lookup(root, (u32)(PTR_INT_TYPE)x);
125 else
126 return (struct ebpt_node *)eb64_lookup(root, (u64)(PTR_INT_TYPE)x);
127 }
128
ebpt_lookup_le(struct eb_root * root,void * x)129 static forceinline struct ebpt_node *ebpt_lookup_le(struct eb_root *root, void *x)
130 {
131 if (sizeof(void *) == 4)
132 return (struct ebpt_node *)eb32_lookup_le(root, (u32)(PTR_INT_TYPE)x);
133 else
134 return (struct ebpt_node *)eb64_lookup_le(root, (u64)(PTR_INT_TYPE)x);
135 }
136
ebpt_lookup_ge(struct eb_root * root,void * x)137 static forceinline struct ebpt_node *ebpt_lookup_ge(struct eb_root *root, void *x)
138 {
139 if (sizeof(void *) == 4)
140 return (struct ebpt_node *)eb32_lookup_ge(root, (u32)(PTR_INT_TYPE)x);
141 else
142 return (struct ebpt_node *)eb64_lookup_ge(root, (u64)(PTR_INT_TYPE)x);
143 }
144
ebpt_insert(struct eb_root * root,struct ebpt_node * new)145 static forceinline struct ebpt_node *ebpt_insert(struct eb_root *root, struct ebpt_node *new)
146 {
147 if (sizeof(void *) == 4)
148 return (struct ebpt_node *)eb32_insert(root, (struct eb32_node *)new);
149 else
150 return (struct ebpt_node *)eb64_insert(root, (struct eb64_node *)new);
151 }
152
153 /*
154 * The following functions are less likely to be used directly, because
155 * their code is larger. The non-inlined version is preferred.
156 */
157
158 /* Delete node from the tree if it was linked in. Mark the node unused. */
__ebpt_delete(struct ebpt_node * ebpt)159 static forceinline void __ebpt_delete(struct ebpt_node *ebpt)
160 {
161 __eb_delete(&ebpt->node);
162 }
163
__ebpt_lookup(struct eb_root * root,void * x)164 static forceinline struct ebpt_node *__ebpt_lookup(struct eb_root *root, void *x)
165 {
166 if (sizeof(void *) == 4)
167 return (struct ebpt_node *)__eb32_lookup(root, (u32)(PTR_INT_TYPE)x);
168 else
169 return (struct ebpt_node *)__eb64_lookup(root, (u64)(PTR_INT_TYPE)x);
170 }
171
__ebpt_insert(struct eb_root * root,struct ebpt_node * new)172 static forceinline struct ebpt_node *__ebpt_insert(struct eb_root *root, struct ebpt_node *new)
173 {
174 if (sizeof(void *) == 4)
175 return (struct ebpt_node *)__eb32_insert(root, (struct eb32_node *)new);
176 else
177 return (struct ebpt_node *)__eb64_insert(root, (struct eb64_node *)new);
178 }
179
180 #endif /* _EBPT_TREE_H */
181