← Back to branch summary

~ubuntu-branches/ubuntu/trusty/haproxy/trusty-backports

« back to all changes in this revision

Viewing changes to include/common/eb32tree.h

  • Committer: Bazaar Package Importer
  • Author(s): Arnaud Cornet
  • Date: 2009-06-26 00:11:01 UTC
  • mfrom: (1.1.6 upstream) (2.1.4 squeeze)
  • Revision ID: james.westby@ubuntu.com-20090626001101-qo261ke2mjh3d8cn
http://bugs.debian.org/534583
* New Upstream Version (Closes: #534583).
* Add contrib directory in docs

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/common/eb32tree.h
1
1
/*
2
2
 * Elastic Binary Trees - macros and structures for operations on 32bit nodes.
3
 
 * (C) 2002-2007 - Willy Tarreau <w@1wt.eu>
 
3
 * Version 4.0
 
4
 * (C) 2002-2008 - Willy Tarreau <w@1wt.eu>
4
5
 *
5
6
 * This program is free software; you can redistribute it and/or modify
6
7
 * it under the terms of the GNU General Public License as published by
99
100
 */
100
101
REGPRM2 struct eb32_node *eb32_lookup(struct eb_root *root, u32 x);
101
102
REGPRM2 struct eb32_node *eb32i_lookup(struct eb_root *root, s32 x);
 
103
REGPRM2 struct eb32_node *eb32_lookup_ge(struct eb_root *root, u32 x);
102
104
REGPRM2 struct eb32_node *eb32_insert(struct eb_root *root, struct eb32_node *new);
103
105
REGPRM2 struct eb32_node *eb32i_insert(struct eb_root *root, struct eb32_node *new);
104
106
 
121
123
{
122
124
        struct eb32_node *node;
123
125
        eb_troot_t *troot;
 
126
        u32 y;
124
127
 
125
128
        troot = root->b[EB_LEFT];
126
129
        if (unlikely(troot == NULL))
138
141
                node = container_of(eb_untag(troot, EB_NODE),
139
142
                                    struct eb32_node, node.branches);
140
143
 
141
 
                if (x == node->key) {
 
144
                y = node->key ^ x;
 
145
                if (!y) {
142
146
                        /* Either we found the node which holds the key, or
143
147
                         * we have a dup tree. In the later case, we have to
144
148
                         * walk it down left to get the first entry.
153
157
                        return node;
154
158
                }
155
159
 
 
160
                if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
 
161
                        return NULL; /* no more common bits */
 
162
 
156
163
                troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
157
164
        }
158
165
}
166
173
        struct eb32_node *node;
167
174
        eb_troot_t *troot;
168
175
        u32 key = x ^ 0x80000000;
 
176
        u32 y;
169
177
 
170
178
        troot = root->b[EB_LEFT];
171
179
        if (unlikely(troot == NULL))
183
191
                node = container_of(eb_untag(troot, EB_NODE),
184
192
                                    struct eb32_node, node.branches);
185
193
 
186
 
                if (x == node->key) {
 
194
                y = node->key ^ x;
 
195
                if (!y) {
187
196
                        /* Either we found the node which holds the key, or
188
197
                         * we have a dup tree. In the later case, we have to
189
198
                         * walk it down left to get the first entry.
198
207
                        return node;
199
208
                }
200
209
 
 
210
                if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
 
211
                        return NULL; /* no more common bits */
 
212
 
201
213
                troot = node->node.branches.b[(key >> node->node.bit) & EB_NODE_BRANCH_MASK];
202
214
        }
203
215
}
204
216
 
205
217
/* Insert eb32_node <new> into subtree starting at node root <root>.
206
218
 * Only new->key needs be set with the key. The eb32_node is returned.
 
219
 * If root->b[EB_RGHT]==1, the tree may only contain unique keys.
207
220
 */
208
221
static forceinline struct eb32_node *
209
222
__eb32_insert(struct eb_root *root, struct eb32_node *new) {
211
224
        unsigned int side;
212
225
        eb_troot_t *troot;
213
226
        u32 newkey; /* caching the key saves approximately one cycle */
 
227
        eb_troot_t *root_right = root;
214
228
 
215
229
        side = EB_LEFT;
216
230
        troot = root->b[EB_LEFT];
 
231
        root_right = root->b[EB_RGHT];
217
232
        if (unlikely(troot == NULL)) {
218
233
                /* Tree is empty, insert the leaf part below the left branch */
219
234
                root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
272
287
                                new->node.branches.b[EB_LEFT] = new_leaf;
273
288
                                new->node.branches.b[EB_RGHT] = old_leaf;
274
289
                        } else {
 
290
                                /* we may refuse to duplicate this key if the tree is
 
291
                                 * tagged as containing only unique keys.
 
292
                                 */
 
293
                                if ((new->key == old->key) && eb_gettag(root_right))
 
294
                                        return old;
 
295
 
275
296
                                /* new->key >= old->key, new goes the right */
276
297
                                old->node.leaf_p = new_left;
277
298
                                new->node.leaf_p = new_rght;
359
380
 
360
381
/* Insert eb32_node <new> into subtree starting at node root <root>, using
361
382
 * signed keys. Only new->key needs be set with the key. The eb32_node
362
 
 * is returned
 
383
 * is returned. If root->b[EB_RGHT]==1, the tree may only contain unique keys.
363
384
 */
364
385
static forceinline struct eb32_node *
365
386
__eb32i_insert(struct eb_root *root, struct eb32_node *new) {
367
388
        unsigned int side;
368
389
        eb_troot_t *troot;
369
390
        int newkey; /* caching the key saves approximately one cycle */
 
391
        eb_troot_t *root_right = root;
370
392
 
371
393
        side = EB_LEFT;
372
394
        troot = root->b[EB_LEFT];
 
395
        root_right = root->b[EB_RGHT];
373
396
        if (unlikely(troot == NULL)) {
374
397
                /* Tree is empty, insert the leaf part below the left branch */
375
398
                root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
430
453
                                new->node.branches.b[EB_LEFT] = new_leaf;
431
454
                                new->node.branches.b[EB_RGHT] = old_leaf;
432
455
                        } else {
 
456
                                /* we may refuse to duplicate this key if the tree is
 
457
                                 * tagged as containing only unique keys.
 
458
                                 */
 
459
                                if ((new->key == old->key) && eb_gettag(root_right))
 
460
                                        return old;
 
461
 
433
462
                                /* new->key >= old->key, new goes the right */
434
463
                                old->node.leaf_p = new_left;
435
464
                                new->node.leaf_p = new_rght;