← Back to branch summary

~ubuntu-branches/ubuntu/utopic/haproxy/utopic-proposed

« back to all changes in this revision

Viewing changes to include/common/ebpttree.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/ebpttree.h
1
1
/*
2
2
 * Elastic Binary Trees - macros and structures for operations on pointer 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
122
123
{
123
124
        struct ebpt_node *node;
124
125
        eb_troot_t *troot;
 
126
        ptr_t y;
125
127
 
126
128
        troot = root->b[EB_LEFT];
127
129
        if (unlikely(troot == NULL))
139
141
                node = container_of(eb_untag(troot, EB_NODE),
140
142
                                    struct ebpt_node, node.branches);
141
143
 
142
 
                if (x == node->key) {
 
144
                y = (ptr_t)node->key ^ (ptr_t)x;
 
145
                if (!y) {
143
146
                        /* Either we found the node which holds the key, or
144
147
                         * we have a dup tree. In the later case, we have to
145
148
                         * walk it down left to get the first entry.
154
157
                        return node;
155
158
                }
156
159
 
 
160
                if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
 
161
                        return NULL; /* no more common bits */
 
162
 
157
163
                troot = node->node.branches.b[((ptr_t)x >> node->node.bit) & EB_NODE_BRANCH_MASK];
158
164
        }
159
165
}
160
166
 
161
167
/* Insert ebpt_node <new> into subtree starting at node root <root>.
162
168
 * Only new->key needs be set with the key. The ebpt_node is returned.
 
169
 * If root->b[EB_RGHT]==1, the tree may only contain unique keys.
163
170
 */
164
171
static forceinline struct ebpt_node *
165
172
__ebpt_insert(struct eb_root *root, struct ebpt_node *new) {
167
174
        unsigned int side;
168
175
        eb_troot_t *troot;
169
176
        void *newkey; /* caching the key saves approximately one cycle */
 
177
        eb_troot_t *root_right = root;
170
178
 
171
179
        side = EB_LEFT;
172
180
        troot = root->b[EB_LEFT];
 
181
        root_right = root->b[EB_RGHT];
173
182
        if (unlikely(troot == NULL)) {
174
183
                /* Tree is empty, insert the leaf part below the left branch */
175
184
                root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
228
237
                                new->node.branches.b[EB_LEFT] = new_leaf;
229
238
                                new->node.branches.b[EB_RGHT] = old_leaf;
230
239
                        } else {
 
240
                                /* we may refuse to duplicate this key if the tree is
 
241
                                 * tagged as containing only unique keys.
 
242
                                 */
 
243
                                if ((new->key == old->key) && eb_gettag(root_right))
 
244
                                        return old;
 
245
 
231
246
                                /* new->key >= old->key, new goes the right */
232
247
                                old->node.leaf_p = new_left;
233
248
                                new->node.leaf_p = new_rght;