← Back to branch summary

~ubuntu-branches/ubuntu/precise/haproxy/precise-updates

« back to all changes in this revision

Viewing changes to ebtree/ebpttree.c

  • Committer: Bazaar Package Importer
  • Author(s): Arnaud Cornet
  • Date: 2010-04-15 20:00:34 UTC
  • mfrom: (1.1.8 upstream) (2.1.7 sid)
  • Revision ID: james.westby@ubuntu.com-20100415200034-is2r38tyvmtvi3ml
Tags: 1.4.4-1
* New upstream release
* Add splice and tproxy support
* Add regparm optimization on i386
* Switch to dpkg-source 3.0 (quilt) format

Show diffs side-by-side

added added

removed removed

Lines of Context:
ebtree/ebpttree.c
 
1
/*
 
2
 * Elastic Binary Trees - exported functions for operations on pointer nodes.
 
3
 * (C) 2002-2007 - Willy Tarreau <w@1wt.eu>
 
4
 *
 
5
 * This program is free software; you can redistribute it and/or modify
 
6
 * it under the terms of the GNU General Public License as published by
 
7
 * the Free Software Foundation; either version 2 of the License, or
 
8
 * (at your option) any later version.
 
9
 *
 
10
 * This program is distributed in the hope that it will be useful,
 
11
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
13
 * GNU General Public License for more details.
 
14
 *
 
15
 * You should have received a copy of the GNU General Public License
 
16
 * along with this program; if not, write to the Free Software
 
17
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 
18
 */
 
19
 
 
20
/* Consult ebpttree.h for more details about those functions */
 
21
 
 
22
#include "ebpttree.h"
 
23
 
 
24
REGPRM2 struct ebpt_node *ebpt_insert(struct eb_root *root, struct ebpt_node *new)
 
25
{
 
26
        return __ebpt_insert(root, new);
 
27
}
 
28
 
 
29
REGPRM2 struct ebpt_node *ebpt_lookup(struct eb_root *root, void *x)
 
30
{
 
31
        return __ebpt_lookup(root, x);
 
32
}
 
33
 
 
34
/*
 
35
 * Find the last occurrence of the highest key in the tree <root>, which is
 
36
 * equal to or less than <x>. NULL is returned is no key matches.
 
37
 */
 
38
REGPRM2 struct ebpt_node *ebpt_lookup_le(struct eb_root *root, void *x)
 
39
{
 
40
        struct ebpt_node *node;
 
41
        eb_troot_t *troot;
 
42
 
 
43
        troot = root->b[EB_LEFT];
 
44
        if (unlikely(troot == NULL))
 
45
                return NULL;
 
46
 
 
47
        while (1) {
 
48
                if ((eb_gettag(troot) == EB_LEAF)) {
 
49
                        /* We reached a leaf, which means that the whole upper
 
50
                         * parts were common. We will return either the current
 
51
                         * node or its next one if the former is too small.
 
52
                         */
 
53
                        node = container_of(eb_untag(troot, EB_LEAF),
 
54
                                            struct ebpt_node, node.branches);
 
55
                        if (node->key <= x)
 
56
                                return node;
 
57
                        /* return prev */
 
58
                        troot = node->node.leaf_p;
 
59
                        break;
 
60
                }
 
61
                node = container_of(eb_untag(troot, EB_NODE),
 
62
                                    struct ebpt_node, node.branches);
 
63
 
 
64
                if (node->node.bit < 0) {
 
65
                        /* We're at the top of a dup tree. Either we got a
 
66
                         * matching value and we return the rightmost node, or
 
67
                         * we don't and we skip the whole subtree to return the
 
68
                         * prev node before the subtree. Note that since we're
 
69
                         * at the top of the dup tree, we can simply return the
 
70
                         * prev node without first trying to escape from the
 
71
                         * tree.
 
72
                         */
 
73
                        if (node->key <= x) {
 
74
                                troot = node->node.branches.b[EB_RGHT];
 
75
                                while (eb_gettag(troot) != EB_LEAF)
 
76
                                        troot = (eb_untag(troot, EB_NODE))->b[EB_RGHT];
 
77
                                return container_of(eb_untag(troot, EB_LEAF),
 
78
                                                    struct ebpt_node, node.branches);
 
79
                        }
 
80
                        /* return prev */
 
81
                        troot = node->node.node_p;
 
82
                        break;
 
83
                }
 
84
 
 
85
                if ((((ptr_t)x ^ (ptr_t)node->key) >> node->node.bit) >= EB_NODE_BRANCHES) {
 
86
                        /* No more common bits at all. Either this node is too
 
87
                         * small and we need to get its highest value, or it is
 
88
                         * too large, and we need to get the prev value.
 
89
                         */
 
90
                        if (((ptr_t)node->key >> node->node.bit) > ((ptr_t)x >> node->node.bit)) {
 
91
                                troot = node->node.branches.b[EB_RGHT];
 
92
                                return ebpt_entry(eb_walk_down(troot, EB_RGHT), struct ebpt_node, node);
 
93
                        }
 
94
 
 
95
                        /* Further values will be too high here, so return the prev
 
96
                         * unique node (if it exists).
 
97
                         */
 
98
                        troot = node->node.node_p;
 
99
                        break;
 
100
                }
 
101
                troot = node->node.branches.b[((ptr_t)x >> node->node.bit) & EB_NODE_BRANCH_MASK];
 
102
        }
 
103
 
 
104
        /* If we get here, it means we want to report previous node before the
 
105
         * current one which is not above. <troot> is already initialised to
 
106
         * the parent's branches.
 
107
         */
 
108
        while (eb_gettag(troot) == EB_LEFT) {
 
109
                /* Walking up from left branch. We must ensure that we never
 
110
                 * walk beyond root.
 
111
                 */
 
112
                if (unlikely(eb_clrtag((eb_untag(troot, EB_LEFT))->b[EB_RGHT]) == NULL))
 
113
                        return NULL;
 
114
                troot = (eb_root_to_node(eb_untag(troot, EB_LEFT)))->node_p;
 
115
        }
 
116
        /* Note that <troot> cannot be NULL at this stage */
 
117
        troot = (eb_untag(troot, EB_RGHT))->b[EB_LEFT];
 
118
        node = ebpt_entry(eb_walk_down(troot, EB_RGHT), struct ebpt_node, node);
 
119
        return node;
 
120
}
 
121
 
 
122
/*
 
123
 * Find the first occurrence of the lowest key in the tree <root>, which is
 
124
 * equal to or greater than <x>. NULL is returned is no key matches.
 
125
 */
 
126
REGPRM2 struct ebpt_node *ebpt_lookup_ge(struct eb_root *root, void *x)
 
127
{
 
128
        struct ebpt_node *node;
 
129
        eb_troot_t *troot;
 
130
 
 
131
        troot = root->b[EB_LEFT];
 
132
        if (unlikely(troot == NULL))
 
133
                return NULL;
 
134
 
 
135
        while (1) {
 
136
                if ((eb_gettag(troot) == EB_LEAF)) {
 
137
                        /* We reached a leaf, which means that the whole upper
 
138
                         * parts were common. We will return either the current
 
139
                         * node or its next one if the former is too small.
 
140
                         */
 
141
                        node = container_of(eb_untag(troot, EB_LEAF),
 
142
                                            struct ebpt_node, node.branches);
 
143
                        if (node->key >= x)
 
144
                                return node;
 
145
                        /* return next */
 
146
                        troot = node->node.leaf_p;
 
147
                        break;
 
148
                }
 
149
                node = container_of(eb_untag(troot, EB_NODE),
 
150
                                    struct ebpt_node, node.branches);
 
151
 
 
152
                if (node->node.bit < 0) {
 
153
                        /* We're at the top of a dup tree. Either we got a
 
154
                         * matching value and we return the leftmost node, or
 
155
                         * we don't and we skip the whole subtree to return the
 
156
                         * next node after the subtree. Note that since we're
 
157
                         * at the top of the dup tree, we can simply return the
 
158
                         * next node without first trying to escape from the
 
159
                         * tree.
 
160
                         */
 
161
                        if (node->key >= x) {
 
162
                                troot = node->node.branches.b[EB_LEFT];
 
163
                                while (eb_gettag(troot) != EB_LEAF)
 
164
                                        troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
 
165
                                return container_of(eb_untag(troot, EB_LEAF),
 
166
                                                    struct ebpt_node, node.branches);
 
167
                        }
 
168
                        /* return next */
 
169
                        troot = node->node.node_p;
 
170
                        break;
 
171
                }
 
172
 
 
173
                if ((((ptr_t)x ^ (ptr_t)node->key) >> node->node.bit) >= EB_NODE_BRANCHES) {
 
174
                        /* No more common bits at all. Either this node is too
 
175
                         * large and we need to get its lowest value, or it is too
 
176
                         * small, and we need to get the next value.
 
177
                         */
 
178
                        if (((ptr_t)node->key >> node->node.bit) > ((ptr_t)x >> node->node.bit)) {
 
179
                                troot = node->node.branches.b[EB_LEFT];
 
180
                                return ebpt_entry(eb_walk_down(troot, EB_LEFT), struct ebpt_node, node);
 
181
                        }
 
182
 
 
183
                        /* Further values will be too low here, so return the next
 
184
                         * unique node (if it exists).
 
185
                         */
 
186
                        troot = node->node.node_p;
 
187
                        break;
 
188
                }
 
189
                troot = node->node.branches.b[((ptr_t)x >> node->node.bit) & EB_NODE_BRANCH_MASK];
 
190
        }
 
191
 
 
192
        /* If we get here, it means we want to report next node after the
 
193
         * current one which is not below. <troot> is already initialised
 
194
         * to the parent's branches.
 
195
         */
 
196
        while (eb_gettag(troot) != EB_LEFT)
 
197
                /* Walking up from right branch, so we cannot be below root */
 
198
                troot = (eb_root_to_node(eb_untag(troot, EB_RGHT)))->node_p;
 
199
 
 
200
        /* Note that <troot> cannot be NULL at this stage */
 
201
        troot = (eb_untag(troot, EB_LEFT))->b[EB_RGHT];
 
202
        if (eb_clrtag(troot) == NULL)
 
203
                return NULL;
 
204
 
 
205
        node = ebpt_entry(eb_walk_down(troot, EB_LEFT), struct ebpt_node, node);
 
206
        return node;
 
207
}