« back to all changes in this revision
Viewing changes to ebtree/eb32tree.h
- browse files at revision 1.1.8
- compare with another revision
- download diff
- download tarball
- view history from revision 1.1.8
- Committer: Bazaar Package Importer
- Author(s): Arnaud Cornet
- Date: 2010-04-15 20:00:34 UTC
- mfrom: (1.2.6 upstream)
- mto: This revision was merged to the branch mainline in revision 11.
- Revision ID: james.westby@ubuntu.com-20100415200034-mtlky4sy39tk0dfi
Tags: upstream-1.4.4
Import upstream version 1.4.4
- files added:
- .gitignore
- contrib/base64
- ebtree
- files removed:
- doc/internals/ebtree
- files modified:
- CHANGELOG
added
removed
ebtree/eb32tree.h
1
/*
2
* Elastic Binary Trees - macros and structures for operations on 32bit 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 _EB32TREE_H
22
#define _EB32TREE_H
23
24
#include "ebtree.h"
25
26
27
/* Return the structure of type <type> whose member <member> points to <ptr> */
28
#define eb32_entry(ptr, type, member) container_of(ptr, type, member)
29
30
#define EB32_ROOT EB_ROOT
31
#define EB32_TREE_HEAD EB_TREE_HEAD
32
33
/* These types may sometimes already be defined */
34
typedef unsigned int u32;
35
typedef signed int s32;
36
37
/* This structure carries a node, a leaf, and a key. It must start with the
38
* eb_node so that it can be cast into an eb_node. We could also have put some
39
* sort of transparent union here to reduce the indirection level, but the fact
40
* is, the end user is not meant to manipulate internals, so this is pointless.
41
*/
42
struct eb32_node {
43
struct eb_node node; /* the tree node, must be at the beginning */
44
u32 key;
45
};
46
47
/*
48
* Exported functions and macros.
49
* Many of them are always inlined because they are extremely small, and
50
* are generally called at most once or twice in a program.
51
*/
52
53
/* Return leftmost node in the tree, or NULL if none */
54
static inline struct eb32_node *eb32_first(struct eb_root *root)
55
{
56
return eb32_entry(eb_first(root), struct eb32_node, node);
57
}
58
59
/* Return rightmost node in the tree, or NULL if none */
60
static inline struct eb32_node *eb32_last(struct eb_root *root)
61
{
62
return eb32_entry(eb_last(root), struct eb32_node, node);
63
}
64
65
/* Return next node in the tree, or NULL if none */
66
static inline struct eb32_node *eb32_next(struct eb32_node *eb32)
67
{
68
return eb32_entry(eb_next(&eb32->node), struct eb32_node, node);
69
}
70
71
/* Return previous node in the tree, or NULL if none */
72
static inline struct eb32_node *eb32_prev(struct eb32_node *eb32)
73
{
74
return eb32_entry(eb_prev(&eb32->node), struct eb32_node, node);
75
}
76
77
/* Return next node in the tree, skipping duplicates, or NULL if none */
78
static inline struct eb32_node *eb32_next_unique(struct eb32_node *eb32)
79
{
80
return eb32_entry(eb_next_unique(&eb32->node), struct eb32_node, node);
81
}
82
83
/* Return previous node in the tree, skipping duplicates, or NULL if none */
84
static inline struct eb32_node *eb32_prev_unique(struct eb32_node *eb32)
85
{
86
return eb32_entry(eb_prev_unique(&eb32->node), struct eb32_node, node);
87
}
88
89
/* Delete node from the tree if it was linked in. Mark the node unused. Note
90
* that this function relies on a non-inlined generic function: eb_delete.
91
*/
92
static inline void eb32_delete(struct eb32_node *eb32)
93
{
94
eb_delete(&eb32->node);
95
}
96
97
/*
98
* The following functions are not inlined by default. They are declared
99
* in eb32tree.c, which simply relies on their inline version.
100
*/
101
REGPRM2 struct eb32_node *eb32_lookup(struct eb_root *root, u32 x);
102
REGPRM2 struct eb32_node *eb32i_lookup(struct eb_root *root, s32 x);
103
REGPRM2 struct eb32_node *eb32_lookup_le(struct eb_root *root, u32 x);
104
REGPRM2 struct eb32_node *eb32_lookup_ge(struct eb_root *root, u32 x);
105
REGPRM2 struct eb32_node *eb32_insert(struct eb_root *root, struct eb32_node *new);
106
REGPRM2 struct eb32_node *eb32i_insert(struct eb_root *root, struct eb32_node *new);
107
108
/*
109
* The following functions are less likely to be used directly, because their
110
* code is larger. The non-inlined version is preferred.
111
*/
112
113
/* Delete node from the tree if it was linked in. Mark the node unused. */
114
static forceinline void __eb32_delete(struct eb32_node *eb32)
115
{
116
__eb_delete(&eb32->node);
117
}
118
119
/*
120
* Find the first occurence of a key in the tree <root>. If none can be
121
* found, return NULL.
122
*/
123
static forceinline struct eb32_node *__eb32_lookup(struct eb_root *root, u32 x)
124
{
125
struct eb32_node *node;
126
eb_troot_t *troot;
127
u32 y;
128
129
troot = root->b[EB_LEFT];
130
if (unlikely(troot == NULL))
131
return NULL;
132
133
while (1) {
134
if ((eb_gettag(troot) == EB_LEAF)) {
135
node = container_of(eb_untag(troot, EB_LEAF),
136
struct eb32_node, node.branches);
137
if (node->key == x)
138
return node;
139
else
140
return NULL;
141
}
142
node = container_of(eb_untag(troot, EB_NODE),
143
struct eb32_node, node.branches);
144
145
y = node->key ^ x;
146
if (!y) {
147
/* Either we found the node which holds the key, or
148
* we have a dup tree. In the later case, we have to
149
* walk it down left to get the first entry.
150
*/
151
if (node->node.bit < 0) {
152
troot = node->node.branches.b[EB_LEFT];
153
while (eb_gettag(troot) != EB_LEAF)
154
troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
155
node = container_of(eb_untag(troot, EB_LEAF),
156
struct eb32_node, node.branches);
157
}
158
return node;
159
}
160
161
if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
162
return NULL; /* no more common bits */
163
164
troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
165
}
166
}
167
168
/*
169
* Find the first occurence of a signed key in the tree <root>. If none can
170
* be found, return NULL.
171
*/
172
static forceinline struct eb32_node *__eb32i_lookup(struct eb_root *root, s32 x)
173
{
174
struct eb32_node *node;
175
eb_troot_t *troot;
176
u32 key = x ^ 0x80000000;
177
u32 y;
178
179
troot = root->b[EB_LEFT];
180
if (unlikely(troot == NULL))
181
return NULL;
182
183
while (1) {
184
if ((eb_gettag(troot) == EB_LEAF)) {
185
node = container_of(eb_untag(troot, EB_LEAF),
186
struct eb32_node, node.branches);
187
if (node->key == x)
188
return node;
189
else
190
return NULL;
191
}
192
node = container_of(eb_untag(troot, EB_NODE),
193
struct eb32_node, node.branches);
194
195
y = node->key ^ x;
196
if (!y) {
197
/* Either we found the node which holds the key, or
198
* we have a dup tree. In the later case, we have to
199
* walk it down left to get the first entry.
200
*/
201
if (node->node.bit < 0) {
202
troot = node->node.branches.b[EB_LEFT];
203
while (eb_gettag(troot) != EB_LEAF)
204
troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
205
node = container_of(eb_untag(troot, EB_LEAF),
206
struct eb32_node, node.branches);
207
}
208
return node;
209
}
210
211
if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
212
return NULL; /* no more common bits */
213
214
troot = node->node.branches.b[(key >> node->node.bit) & EB_NODE_BRANCH_MASK];
215
}
216
}
217
218
/* Insert eb32_node <new> into subtree starting at node root <root>.
219
* Only new->key needs be set with the key. The eb32_node is returned.
220
* If root->b[EB_RGHT]==1, the tree may only contain unique keys.
221
*/
222
static forceinline struct eb32_node *
223
__eb32_insert(struct eb_root *root, struct eb32_node *new) {
224
struct eb32_node *old;
225
unsigned int side;
226
eb_troot_t *troot;
227
u32 newkey; /* caching the key saves approximately one cycle */
228
eb_troot_t *root_right = root;
229
230
side = EB_LEFT;
231
troot = root->b[EB_LEFT];
232
root_right = root->b[EB_RGHT];
233
if (unlikely(troot == NULL)) {
234
/* Tree is empty, insert the leaf part below the left branch */
235
root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
236
new->node.leaf_p = eb_dotag(root, EB_LEFT);
237
new->node.node_p = NULL; /* node part unused */
238
return new;
239
}
240
241
/* The tree descent is fairly easy :
242
* - first, check if we have reached a leaf node
243
* - second, check if we have gone too far
244
* - third, reiterate
245
* Everywhere, we use <new> for the node node we are inserting, <root>
246
* for the node we attach it to, and <old> for the node we are
247
* displacing below <new>. <troot> will always point to the future node
248
* (tagged with its type). <side> carries the side the node <new> is
249
* attached to below its parent, which is also where previous node
250
* was attached. <newkey> carries the key being inserted.
251
*/
252
newkey = new->key;
253
254
while (1) {
255
if (unlikely(eb_gettag(troot) == EB_LEAF)) {
256
eb_troot_t *new_left, *new_rght;
257
eb_troot_t *new_leaf, *old_leaf;
258
259
old = container_of(eb_untag(troot, EB_LEAF),
260
struct eb32_node, node.branches);
261
262
new_left = eb_dotag(&new->node.branches, EB_LEFT);
263
new_rght = eb_dotag(&new->node.branches, EB_RGHT);
264
new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
265
old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
266
267
new->node.node_p = old->node.leaf_p;
268
269
/* Right here, we have 3 possibilities :
270
- the tree does not contain the key, and we have
271
new->key < old->key. We insert new above old, on
272
the left ;
273
274
- the tree does not contain the key, and we have
275
new->key > old->key. We insert new above old, on
276
the right ;
277
278
- the tree does contain the key, which implies it
279
is alone. We add the new key next to it as a
280
first duplicate.
281
282
The last two cases can easily be partially merged.
283
*/
284
285
if (new->key < old->key) {
286
new->node.leaf_p = new_left;
287
old->node.leaf_p = new_rght;
288
new->node.branches.b[EB_LEFT] = new_leaf;
289
new->node.branches.b[EB_RGHT] = old_leaf;
290
} else {
291
/* we may refuse to duplicate this key if the tree is
292
* tagged as containing only unique keys.
293
*/
294
if ((new->key == old->key) && eb_gettag(root_right))
295
return old;
296
297
/* new->key >= old->key, new goes the right */
298
old->node.leaf_p = new_left;
299
new->node.leaf_p = new_rght;
300
new->node.branches.b[EB_LEFT] = old_leaf;
301
new->node.branches.b[EB_RGHT] = new_leaf;
302
303
if (new->key == old->key) {
304
new->node.bit = -1;
305
root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
306
return new;
307
}
308
}
309
break;
310
}
311
312
/* OK we're walking down this link */
313
old = container_of(eb_untag(troot, EB_NODE),
314
struct eb32_node, node.branches);
315
316
/* Stop going down when we don't have common bits anymore. We
317
* also stop in front of a duplicates tree because it means we
318
* have to insert above.
319
*/
320
321
if ((old->node.bit < 0) || /* we're above a duplicate tree, stop here */
322
(((new->key ^ old->key) >> old->node.bit) >= EB_NODE_BRANCHES)) {
323
/* The tree did not contain the key, so we insert <new> before the node
324
* <old>, and set ->bit to designate the lowest bit position in <new>
325
* which applies to ->branches.b[].
326
*/
327
eb_troot_t *new_left, *new_rght;
328
eb_troot_t *new_leaf, *old_node;
329
330
new_left = eb_dotag(&new->node.branches, EB_LEFT);
331
new_rght = eb_dotag(&new->node.branches, EB_RGHT);
332
new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
333
old_node = eb_dotag(&old->node.branches, EB_NODE);
334
335
new->node.node_p = old->node.node_p;
336
337
if (new->key < old->key) {
338
new->node.leaf_p = new_left;
339
old->node.node_p = new_rght;
340
new->node.branches.b[EB_LEFT] = new_leaf;
341
new->node.branches.b[EB_RGHT] = old_node;
342
}
343
else if (new->key > old->key) {
344
old->node.node_p = new_left;
345
new->node.leaf_p = new_rght;
346
new->node.branches.b[EB_LEFT] = old_node;
347
new->node.branches.b[EB_RGHT] = new_leaf;
348
}
349
else {
350
struct eb_node *ret;
351
ret = eb_insert_dup(&old->node, &new->node);
352
return container_of(ret, struct eb32_node, node);
353
}
354
break;
355
}
356
357
/* walk down */
358
root = &old->node.branches;
359
side = (newkey >> old->node.bit) & EB_NODE_BRANCH_MASK;
360
troot = root->b[side];
361
}
362
363
/* Ok, now we are inserting <new> between <root> and <old>. <old>'s
364
* parent is already set to <new>, and the <root>'s branch is still in
365
* <side>. Update the root's leaf till we have it. Note that we can also
366
* find the side by checking the side of new->node.node_p.
367
*/
368
369
/* We need the common higher bits between new->key and old->key.
370
* What differences are there between new->key and the node here ?
371
* NOTE that bit(new) is always < bit(root) because highest
372
* bit of new->key and old->key are identical here (otherwise they
373
* would sit on different branches).
374
*/
375
// note that if EB_NODE_BITS > 1, we should check that it's still >= 0
376
new->node.bit = flsnz(new->key ^ old->key) - EB_NODE_BITS;
377
root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
378
379
return new;
380
}
381
382
/* Insert eb32_node <new> into subtree starting at node root <root>, using
383
* signed keys. Only new->key needs be set with the key. The eb32_node
384
* is returned. If root->b[EB_RGHT]==1, the tree may only contain unique keys.
385
*/
386
static forceinline struct eb32_node *
387
__eb32i_insert(struct eb_root *root, struct eb32_node *new) {
388
struct eb32_node *old;
389
unsigned int side;
390
eb_troot_t *troot;
391
int newkey; /* caching the key saves approximately one cycle */
392
eb_troot_t *root_right = root;
393
394
side = EB_LEFT;
395
troot = root->b[EB_LEFT];
396
root_right = root->b[EB_RGHT];
397
if (unlikely(troot == NULL)) {
398
/* Tree is empty, insert the leaf part below the left branch */
399
root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
400
new->node.leaf_p = eb_dotag(root, EB_LEFT);
401
new->node.node_p = NULL; /* node part unused */
402
return new;
403
}
404
405
/* The tree descent is fairly easy :
406
* - first, check if we have reached a leaf node
407
* - second, check if we have gone too far
408
* - third, reiterate
409
* Everywhere, we use <new> for the node node we are inserting, <root>
410
* for the node we attach it to, and <old> for the node we are
411
* displacing below <new>. <troot> will always point to the future node
412
* (tagged with its type). <side> carries the side the node <new> is
413
* attached to below its parent, which is also where previous node
414
* was attached. <newkey> carries a high bit shift of the key being
415
* inserted in order to have negative keys stored before positive
416
* ones.
417
*/
418
newkey = new->key + 0x80000000;
419
420
while (1) {
421
if (unlikely(eb_gettag(troot) == EB_LEAF)) {
422
eb_troot_t *new_left, *new_rght;
423
eb_troot_t *new_leaf, *old_leaf;
424
425
old = container_of(eb_untag(troot, EB_LEAF),
426
struct eb32_node, node.branches);
427
428
new_left = eb_dotag(&new->node.branches, EB_LEFT);
429
new_rght = eb_dotag(&new->node.branches, EB_RGHT);
430
new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
431
old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
432
433
new->node.node_p = old->node.leaf_p;
434
435
/* Right here, we have 3 possibilities :
436
- the tree does not contain the key, and we have
437
new->key < old->key. We insert new above old, on
438
the left ;
439
440
- the tree does not contain the key, and we have
441
new->key > old->key. We insert new above old, on
442
the right ;
443
444
- the tree does contain the key, which implies it
445
is alone. We add the new key next to it as a
446
first duplicate.
447
448
The last two cases can easily be partially merged.
449
*/
450
451
if ((s32)new->key < (s32)old->key) {
452
new->node.leaf_p = new_left;
453
old->node.leaf_p = new_rght;
454
new->node.branches.b[EB_LEFT] = new_leaf;
455
new->node.branches.b[EB_RGHT] = old_leaf;
456
} else {
457
/* we may refuse to duplicate this key if the tree is
458
* tagged as containing only unique keys.
459
*/
460
if ((new->key == old->key) && eb_gettag(root_right))
461
return old;
462
463
/* new->key >= old->key, new goes the right */
464
old->node.leaf_p = new_left;
465
new->node.leaf_p = new_rght;
466
new->node.branches.b[EB_LEFT] = old_leaf;
467
new->node.branches.b[EB_RGHT] = new_leaf;
468
469
if (new->key == old->key) {
470
new->node.bit = -1;
471
root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
472
return new;
473
}
474
}
475
break;
476
}
477
478
/* OK we're walking down this link */
479
old = container_of(eb_untag(troot, EB_NODE),
480
struct eb32_node, node.branches);
481
482
/* Stop going down when we don't have common bits anymore. We
483
* also stop in front of a duplicates tree because it means we
484
* have to insert above.
485
*/
486
487
if ((old->node.bit < 0) || /* we're above a duplicate tree, stop here */
488
(((new->key ^ old->key) >> old->node.bit) >= EB_NODE_BRANCHES)) {
489
/* The tree did not contain the key, so we insert <new> before the node
490
* <old>, and set ->bit to designate the lowest bit position in <new>
491
* which applies to ->branches.b[].
492
*/
493
eb_troot_t *new_left, *new_rght;
494
eb_troot_t *new_leaf, *old_node;
495
496
new_left = eb_dotag(&new->node.branches, EB_LEFT);
497
new_rght = eb_dotag(&new->node.branches, EB_RGHT);
498
new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
499
old_node = eb_dotag(&old->node.branches, EB_NODE);
500
501
new->node.node_p = old->node.node_p;
502
503
if ((s32)new->key < (s32)old->key) {
504
new->node.leaf_p = new_left;
505
old->node.node_p = new_rght;
506
new->node.branches.b[EB_LEFT] = new_leaf;
507
new->node.branches.b[EB_RGHT] = old_node;
508
}
509
else if ((s32)new->key > (s32)old->key) {
510
old->node.node_p = new_left;
511
new->node.leaf_p = new_rght;
512
new->node.branches.b[EB_LEFT] = old_node;
513
new->node.branches.b[EB_RGHT] = new_leaf;
514
}
515
else {
516
struct eb_node *ret;
517
ret = eb_insert_dup(&old->node, &new->node);
518
return container_of(ret, struct eb32_node, node);
519
}
520
break;
521
}
522
523
/* walk down */
524
root = &old->node.branches;
525
side = (newkey >> old->node.bit) & EB_NODE_BRANCH_MASK;
526
troot = root->b[side];
527
}
528
529
/* Ok, now we are inserting <new> between <root> and <old>. <old>'s
530
* parent is already set to <new>, and the <root>'s branch is still in
531
* <side>. Update the root's leaf till we have it. Note that we can also
532
* find the side by checking the side of new->node.node_p.
533
*/
534
535
/* We need the common higher bits between new->key and old->key.
536
* What differences are there between new->key and the node here ?
537
* NOTE that bit(new) is always < bit(root) because highest
538
* bit of new->key and old->key are identical here (otherwise they
539
* would sit on different branches).
540
*/
541
// note that if EB_NODE_BITS > 1, we should check that it's still >= 0
542
new->node.bit = flsnz(new->key ^ old->key) - EB_NODE_BITS;
543
root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
544
545
return new;
546
}
547
548
#endif /* _EB32_TREE_H */
Loggerhead is a web-based interface for Breezy
Version: 2.0.1