blob: f6e521986e2bde10418973858499ad64239e94ba [file] [log] [blame]
Willy Tarreauc2186022009-10-26 19:48:54 +01001/*
2 * Elastic Binary Trees - macros and structures for operations on pointer nodes.
3 * Version 5.0
4 * (C) 2002-2009 - Willy Tarreau <w@1wt.eu>
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program 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
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, 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
40typedef 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 */
48struct 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 */
60static 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 */
66static 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 */
72static 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 */
78static 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 node in the tree, skipping duplicates, or NULL if none */
84static forceinline struct ebpt_node *ebpt_next_unique(struct ebpt_node *ebpt)
85{
86 return ebpt_entry(eb_next_unique(&ebpt->node), struct ebpt_node, node);
87}
88
89/* Return previous node in the tree, skipping duplicates, or NULL if none */
90static forceinline struct ebpt_node *ebpt_prev_unique(struct ebpt_node *ebpt)
91{
92 return ebpt_entry(eb_prev_unique(&ebpt->node), struct ebpt_node, node);
93}
94
95/* Delete node from the tree if it was linked in. Mark the node unused. Note
96 * that this function relies on a non-inlined generic function: eb_delete.
97 */
98static forceinline void ebpt_delete(struct ebpt_node *ebpt)
99{
100 eb_delete(&ebpt->node);
101}
102
103/*
104 * The following functions are inlined but derived from the integer versions.
105 */
106static forceinline struct ebpt_node *ebpt_lookup(struct eb_root *root, void *x)
107{
108 if (sizeof(void *) == 4)
109 return (struct ebpt_node *)eb32_lookup(root, (u32)(PTR_INT_TYPE)x);
110 else
111 return (struct ebpt_node *)eb64_lookup(root, (u64)(PTR_INT_TYPE)x);
112}
113
114static forceinline struct ebpt_node *ebpt_lookup_le(struct eb_root *root, void *x)
115{
116 if (sizeof(void *) == 4)
117 return (struct ebpt_node *)eb32_lookup_le(root, (u32)(PTR_INT_TYPE)x);
118 else
119 return (struct ebpt_node *)eb64_lookup_le(root, (u64)(PTR_INT_TYPE)x);
120}
121
122static forceinline struct ebpt_node *ebpt_lookup_ge(struct eb_root *root, void *x)
123{
124 if (sizeof(void *) == 4)
125 return (struct ebpt_node *)eb32_lookup_ge(root, (u32)(PTR_INT_TYPE)x);
126 else
127 return (struct ebpt_node *)eb64_lookup_ge(root, (u64)(PTR_INT_TYPE)x);
128}
129
130static forceinline struct ebpt_node *ebpt_insert(struct eb_root *root, struct ebpt_node *new)
131{
132 if (sizeof(void *) == 4)
133 return (struct ebpt_node *)eb32_insert(root, (struct eb32_node *)new);
134 else
135 return (struct ebpt_node *)eb64_insert(root, (struct eb64_node *)new);
136}
137
138/*
139 * The following functions are less likely to be used directly, because
140 * their code is larger. The non-inlined version is preferred.
141 */
142
143/* Delete node from the tree if it was linked in. Mark the node unused. */
144static forceinline void __ebpt_delete(struct ebpt_node *ebpt)
145{
146 __eb_delete(&ebpt->node);
147}
148
149static forceinline struct ebpt_node *__ebpt_lookup(struct eb_root *root, void *x)
150{
151 if (sizeof(void *) == 4)
152 return (struct ebpt_node *)__eb32_lookup(root, (u32)(PTR_INT_TYPE)x);
153 else
154 return (struct ebpt_node *)__eb64_lookup(root, (u64)(PTR_INT_TYPE)x);
155}
156
157static forceinline struct ebpt_node *__ebpt_insert(struct eb_root *root, struct ebpt_node *new)
158{
159 if (sizeof(void *) == 4)
160 return (struct ebpt_node *)__eb32_insert(root, (struct eb32_node *)new);
161 else
162 return (struct ebpt_node *)__eb64_insert(root, (struct eb64_node *)new);
163}
164
165#endif /* _EBPT_TREE_H */