← Back to branch summary

~ubuntu-branches/ubuntu/trusty/haproxy/trusty-updates

« back to all changes in this revision

Viewing changes to ebtree/ebpttree.h

  • 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

Show diffs side-by-side

added added

removed removed

Lines of Context:
ebtree/ebpttree.h
 
1
/*
 
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
 
 
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 node in the tree, skipping duplicates, or NULL if none */
 
84
static 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 */
 
90
static 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
 */
 
98
static 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
 */
 
106
static 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
 
 
114
static 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
 
 
122
static 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
 
 
130
static 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. */
 
144
static forceinline void __ebpt_delete(struct ebpt_node *ebpt)
 
145
{
 
146
        __eb_delete(&ebpt->node);
 
147
}
 
148
 
 
149
static 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
 
 
157
static 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 */