← Back to branch summary

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

« back to all changes in this revision

Viewing changes to include/common/eb64tree.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/eb64tree.h
1
1
/*
2
2
 * Elastic Binary Trees - macros and structures for operations on 64bit 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
121
122
{
122
123
        struct eb64_node *node;
123
124
        eb_troot_t *troot;
 
125
        u64 y;
124
126
 
125
127
        troot = root->b[EB_LEFT];
126
128
        if (unlikely(troot == NULL))
138
140
                node = container_of(eb_untag(troot, EB_NODE),
139
141
                                    struct eb64_node, node.branches);
140
142
 
141
 
                if (x == node->key) {
 
143
                y = node->key ^ x;
 
144
                if (!y) {
142
145
                        /* Either we found the node which holds the key, or
143
146
                         * we have a dup tree. In the later case, we have to
144
147
                         * walk it down left to get the first entry.
153
156
                        return node;
154
157
                }
155
158
 
 
159
                if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
 
160
                        return NULL; /* no more common bits */
 
161
 
156
162
                troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
157
163
        }
158
164
}
166
172
        struct eb64_node *node;
167
173
        eb_troot_t *troot;
168
174
        u64 key = x ^ (1ULL << 63);
 
175
        u64 y;
169
176
 
170
177
        troot = root->b[EB_LEFT];
171
178
        if (unlikely(troot == NULL))
183
190
                node = container_of(eb_untag(troot, EB_NODE),
184
191
                                    struct eb64_node, node.branches);
185
192
 
186
 
                if (x == node->key) {
 
193
                y = node->key ^ x;
 
194
                if (!y) {
187
195
                        /* Either we found the node which holds the key, or
188
196
                         * we have a dup tree. In the later case, we have to
189
197
                         * walk it down left to get the first entry.
198
206
                        return node;
199
207
                }
200
208
 
 
209
                if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
 
210
                        return NULL; /* no more common bits */
 
211
 
201
212
                troot = node->node.branches.b[(key >> node->node.bit) & EB_NODE_BRANCH_MASK];
202
213
        }
203
214
}
204
215
 
205
216
/* Insert eb64_node <new> into subtree starting at node root <root>.
206
217
 * Only new->key needs be set with the key. The eb64_node is returned.
 
218
 * If root->b[EB_RGHT]==1, the tree may only contain unique keys.
207
219
 */
208
220
static forceinline struct eb64_node *
209
221
__eb64_insert(struct eb_root *root, struct eb64_node *new) {
211
223
        unsigned int side;
212
224
        eb_troot_t *troot;
213
225
        u64 newkey; /* caching the key saves approximately one cycle */
 
226
        eb_troot_t *root_right = root;
214
227
 
215
228
        side = EB_LEFT;
216
229
        troot = root->b[EB_LEFT];
 
230
        root_right = root->b[EB_RGHT];
217
231
        if (unlikely(troot == NULL)) {
218
232
                /* Tree is empty, insert the leaf part below the left branch */
219
233
                root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
272
286
                                new->node.branches.b[EB_LEFT] = new_leaf;
273
287
                                new->node.branches.b[EB_RGHT] = old_leaf;
274
288
                        } else {
 
289
                                /* we may refuse to duplicate this key if the tree is
 
290
                                 * tagged as containing only unique keys.
 
291
                                 */
 
292
                                if ((new->key == old->key) && eb_gettag(root_right))
 
293
                                        return old;
 
294
 
275
295
                                /* new->key >= old->key, new goes the right */
276
296
                                old->node.leaf_p = new_left;
277
297
                                new->node.leaf_p = new_rght;
369
389
 
370
390
/* Insert eb64_node <new> into subtree starting at node root <root>, using
371
391
 * signed keys. Only new->key needs be set with the key. The eb64_node
372
 
 * is returned.
 
392
 * is returned. If root->b[EB_RGHT]==1, the tree may only contain unique keys.
373
393
 */
374
394
static forceinline struct eb64_node *
375
395
__eb64i_insert(struct eb_root *root, struct eb64_node *new) {
377
397
        unsigned int side;
378
398
        eb_troot_t *troot;
379
399
        u64 newkey; /* caching the key saves approximately one cycle */
 
400
        eb_troot_t *root_right = root;
380
401
 
381
402
        side = EB_LEFT;
382
403
        troot = root->b[EB_LEFT];
 
404
        root_right = root->b[EB_RGHT];
383
405
        if (unlikely(troot == NULL)) {
384
406
                /* Tree is empty, insert the leaf part below the left branch */
385
407
                root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
440
462
                                new->node.branches.b[EB_LEFT] = new_leaf;
441
463
                                new->node.branches.b[EB_RGHT] = old_leaf;
442
464
                        } else {
 
465
                                /* we may refuse to duplicate this key if the tree is
 
466
                                 * tagged as containing only unique keys.
 
467
                                 */
 
468
                                if ((new->key == old->key) && eb_gettag(root_right))
 
469
                                        return old;
 
470
 
443
471
                                /* new->key >= old->key, new goes the right */
444
472
                                old->node.leaf_p = new_left;
445
473
                                new->node.leaf_p = new_rght;