1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
|
/*
* Elastic Binary Trees - types
* 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
*/
#ifndef _EBTREE_T_H
#define _EBTREE_T_H
#include <haproxy/api-t.h>
/*
* generic types for ebtree
*/
/* Number of bits per node, and number of leaves per node */
#define EB_NODE_BITS 1
#define EB_NODE_BRANCHES (1 << EB_NODE_BITS)
#define EB_NODE_BRANCH_MASK (EB_NODE_BRANCHES - 1)
/* Be careful not to tweak those values. The walking code is optimized for NULL
* detection on the assumption that the following values are intact.
*/
#define EB_LEFT 0
#define EB_RGHT 1
#define EB_LEAF 0
#define EB_NODE 1
/* Tags to set in root->b[EB_RGHT] :
* - EB_NORMAL is a normal tree which stores duplicate keys.
* - EB_UNIQUE is a tree which stores unique keys.
*/
#define EB_NORMAL 0
#define EB_UNIQUE 1
/* This is the same as an eb_node pointer, except that the lower bit embeds
* a tag. See eb_dotag()/eb_untag()/eb_gettag(). This tag has two meanings :
* - 0=left, 1=right to designate the parent's branch for leaf_p/node_p
* - 0=link, 1=leaf to designate the branch's type for branch[]
*/
typedef void eb_troot_t;
/* The eb_root connects the node which contains it, to two nodes below it, one
* of which may be the same node. At the top of the tree, we use an eb_root
* too, which always has its right branch NULL (+/1 low-order bits).
*/
struct eb_root {
eb_troot_t *b[EB_NODE_BRANCHES]; /* left and right branches */
};
/* The eb_node contains the two parts, one for the leaf, which always exists,
* and one for the node, which remains unused in the very first node inserted
* into the tree. This structure is 20 bytes per node on 32-bit machines. Do
* not change the order, benchmarks have shown that it's optimal this way.
* Note: be careful about this struct's alignment if it gets included into
* another struct and some atomic ops are expected on the keys or the node.
*/
struct eb_node {
struct eb_root branches; /* branches, must be at the beginning */
eb_troot_t *node_p; /* link node's parent */
eb_troot_t *leaf_p; /* leaf node's parent */
short int bit; /* link's bit position. */
short unsigned int pfx; /* data prefix length, always related to leaf */
} __attribute__((packed));
/* The root of a tree is an eb_root initialized with both pointers NULL.
* During its life, only the left pointer will change. The right one will
* always remain NULL, which is the way we detect it.
*/
#define EB_ROOT \
(struct eb_root) { \
.b = {[0] = NULL, [1] = NULL }, \
}
#define EB_ROOT_UNIQUE \
(struct eb_root) { \
.b = {[0] = NULL, [1] = (void *)1 }, \
}
#define EB_TREE_HEAD(name) \
struct eb_root name = EB_ROOT
/*
* types for eb32tree
*/
#define EB32_ROOT EB_ROOT
#define EB32_TREE_HEAD EB_TREE_HEAD
/* These types may sometimes already be defined */
typedef unsigned int u32;
typedef signed int s32;
/* This structure carries a node, a leaf, and a key. It must start with the
* eb_node so that it can be cast into an eb_node. We could also have put some
* sort of transparent union here to reduce the indirection level, but the fact
* is, the end user is not meant to manipulate internals, so this is pointless.
*/
struct eb32_node {
struct eb_node node; /* the tree node, must be at the beginning */
MAYBE_ALIGN(sizeof(u32));
u32 key;
} ALIGNED(sizeof(void*));
/* This structure carries a node, a leaf, a scope, and a key. It must start
* with the eb_node so that it can be cast into an eb_node. We could also
* have put some sort of transparent union here to reduce the indirection
* level, but the fact is, the end user is not meant to manipulate internals,
* so this is pointless.
* In case sizeof(void*)>=sizeof(long), we know there will be some padding after
* the leaf if it's unaligned. In this case we force the alignment on void* so
* that we prefer to have the padding before for more efficient accesses.
*/
struct eb32sc_node {
struct eb_node node; /* the tree node, must be at the beginning */
MAYBE_ALIGN(sizeof(u32));
u32 key;
ALWAYS_ALIGN(sizeof(void*));
unsigned long node_s; /* visibility of this node's branches */
unsigned long leaf_s; /* visibility of this node's leaf */
} ALIGNED(sizeof(void*));
/*
* types for eb64tree
*/
#define EB64_ROOT EB_ROOT
#define EB64_TREE_HEAD EB_TREE_HEAD
/* These types may sometimes already be defined */
typedef unsigned long long u64;
typedef signed long long s64;
/* This structure carries a node, a leaf, and a key. It must start with the
* eb_node so that it can be cast into an eb_node. We could also have put some
* sort of transparent union here to reduce the indirection level, but the fact
* is, the end user is not meant to manipulate internals, so this is pointless.
* In case sizeof(void*)>=sizeof(u64), we know there will be some padding after
* the key if it's unaligned. In this case we force the alignment on void* so
* that we prefer to have the padding before for more efficient accesses.
*/
struct eb64_node {
struct eb_node node; /* the tree node, must be at the beginning */
MAYBE_ALIGN(sizeof(u64));
ALWAYS_ALIGN(sizeof(void*));
u64 key;
} ALIGNED(sizeof(void*));
#define EBPT_ROOT EB_ROOT
#define EBPT_TREE_HEAD EB_TREE_HEAD
/* on *almost* all platforms, a pointer can be cast into a size_t which is unsigned */
#ifndef PTR_INT_TYPE
#define PTR_INT_TYPE size_t
#endif
/*
* types for ebpttree
*/
typedef PTR_INT_TYPE ptr_t;
/* This structure carries a node, a leaf, and a key. It must start with the
* eb_node so that it can be cast into an eb_node. We could also have put some
* sort of transparent union here to reduce the indirection level, but the fact
* is, the end user is not meant to manipulate internals, so this is pointless.
* Internally, it is automatically cast as an eb32_node or eb64_node.
* We always align the key since the struct itself will be padded to the same
* size anyway.
*/
struct ebpt_node {
struct eb_node node; /* the tree node, must be at the beginning */
ALWAYS_ALIGN(sizeof(void*));
void *key;
} ALIGNED(sizeof(void*));
/*
* types for ebmbtree
*/
#define EBMB_ROOT EB_ROOT
#define EBMB_TREE_HEAD EB_TREE_HEAD
/* This structure carries a node, a leaf, and a key. It must start with the
* eb_node so that it can be cast into an eb_node. We could also have put some
* sort of transparent union here to reduce the indirection level, but the fact
* is, the end user is not meant to manipulate internals, so this is pointless.
* The 'node.bit' value here works differently from scalar types, as it contains
* the number of identical bits between the two branches.
* Note that we take a great care of making sure the key is located exactly at
* the end of the struct even if that involves holes before it, so that it
* always aliases any external key a user would append after. This is why the
* key uses the same alignment as the struct.
*/
struct ebmb_node {
struct eb_node node; /* the tree node, must be at the beginning */
ALWAYS_ALIGN(sizeof(void*));
unsigned char key[0]; /* the key, its size depends on the application */
} ALIGNED(sizeof(void*));
#endif /* _EB_TREE_T_H */
|
