← Back to branch summary

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

« back to all changes in this revision

Viewing changes to ebtree/ebimtree.h

  • Committer: Bazaar Package Importer
  • Author(s): Christo Buschek
  • Date: 2011-03-11 12:41:59 UTC
  • mfrom: (1.1.10 upstream)
  • Revision ID: james.westby@ubuntu.com-20110311124159-9foyp4juf1ilqipo
Tags: 1.4.13-1
http://bugs.debian.org/615246
http://bugs.debian.org/581109
* New maintainer upload (Closes: #615246)
* New upstream release
* Standards-version goes 3.9.1 (no change)
* Added patch bashism (Closes: #581109)
* Added a README.source file.

Show diffs side-by-side

added added

removed removed

Lines of Context:
ebtree/ebimtree.h
1
1
/*
2
2
 * Elastic Binary Trees - macros for Indirect Multi-Byte data nodes.
3
 
 * Version 6.0
4
 
 * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
 
3
 * Version 6.0.5
 
4
 * (C) 2002-2011 - Willy Tarreau <w@1wt.eu>
5
5
 *
6
6
 * This program is free software; you can redistribute it and/or modify
7
7
 * it under the terms of the GNU General Public License as published by
32
32
REGPRM3 struct ebpt_node *ebim_lookup(struct eb_root *root, const void *x, unsigned int len);
33
33
REGPRM3 struct ebpt_node *ebim_insert(struct eb_root *root, struct ebpt_node *new, unsigned int len);
34
34
 
35
 
/* Find the first occurence of a key of <len> bytes in the tree <root>.
36
 
 * If none can be found, return NULL.
 
35
/* Find the first occurence of a key of a least <len> bytes matching <x> in the
 
36
 * tree <root>. The caller is responsible for ensuring that <len> will not exceed
 
37
 * the common parts between the tree's keys and <x>. In case of multiple matches,
 
38
 * the leftmost node is returned. This means that this function can be used to
 
39
 * lookup string keys by prefix if all keys in the tree are zero-terminated. If
 
40
 * no match is found, NULL is returned. Returns first node if <len> is zero.
37
41
 */
38
42
static forceinline struct ebpt_node *
39
43
__ebim_lookup(struct eb_root *root, const void *x, unsigned int len)
40
44
{
41
45
        struct ebpt_node *node;
42
46
        eb_troot_t *troot;
43
 
        int bit;
 
47
        int pos, side;
44
48
        int node_bit;
45
49
 
46
50
        troot = root->b[EB_LEFT];
47
51
        if (unlikely(troot == NULL))
48
 
                return NULL;
49
 
 
50
 
        bit = 0;
 
52
                goto ret_null;
 
53
 
 
54
        if (unlikely(len == 0))
 
55
                goto walk_down;
 
56
 
 
57
        pos = 0;
51
58
        while (1) {
52
 
                if ((eb_gettag(troot) == EB_LEAF)) {
 
59
                if (eb_gettag(troot) == EB_LEAF) {
53
60
                        node = container_of(eb_untag(troot, EB_LEAF),
54
61
                                            struct ebpt_node, node.branches);
55
 
                        if (memcmp(node->key, x, len) == 0)
56
 
                                return node;
 
62
                        if (memcmp(node->key + pos, x, len) != 0)
 
63
                                goto ret_null;
57
64
                        else
58
 
                                return NULL;
 
65
                                goto ret_node;
59
66
                }
60
67
                node = container_of(eb_untag(troot, EB_NODE),
61
68
                                    struct ebpt_node, node.branches);
66
73
                         * value, and we walk down left, or it's a different
67
74
                         * one and we don't have our key.
68
75
                         */
69
 
                        if (memcmp(node->key, x, len) != 0)
70
 
                                return NULL;
71
 
 
72
 
                        troot = node->node.branches.b[EB_LEFT];
73
 
                        while (eb_gettag(troot) != EB_LEAF)
74
 
                                troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
75
 
                        node = container_of(eb_untag(troot, EB_LEAF),
76
 
                                            struct ebpt_node, node.branches);
77
 
                        return node;
78
 
                }
79
 
 
80
 
                /* OK, normal data node, let's walk down */
81
 
                bit = equal_bits(x, node->key, bit, node_bit);
82
 
                if (bit < node_bit)
83
 
                        return NULL; /* no more common bits */
84
 
 
85
 
                troot = node->node.branches.b[(((unsigned char*)x)[node_bit >> 3] >>
86
 
                                               (~node_bit & 7)) & 1];
 
76
                        if (memcmp(node->key + pos, x, len) != 0)
 
77
                                goto ret_null;
 
78
                        else
 
79
                                goto walk_left;
 
80
                }
 
81
 
 
82
                /* OK, normal data node, let's walk down. We check if all full
 
83
                 * bytes are equal, and we start from the last one we did not
 
84
                 * completely check. We stop as soon as we reach the last byte,
 
85
                 * because we must decide to go left/right or abort.
 
86
                 */
 
87
                node_bit = ~node_bit + (pos << 3) + 8; // = (pos<<3) + (7 - node_bit)
 
88
                if (node_bit < 0) {
 
89
                        /* This surprizing construction gives better performance
 
90
                         * because gcc does not try to reorder the loop. Tested to
 
91
                         * be fine with 2.95 to 4.2.
 
92
                         */
 
93
                        while (1) {
 
94
                                if (*(unsigned char*)(node->key + pos++) ^ *(unsigned char*)(x++))
 
95
                                        goto ret_null; /* more than one full byte is different */
 
96
                                if (--len == 0)
 
97
                                        goto walk_left; /* return first node if all bytes matched */
 
98
                                node_bit += 8;
 
99
                                if (node_bit >= 0)
 
100
                                        break;
 
101
                        }
 
102
                }
 
103
 
 
104
                /* here we know that only the last byte differs, so node_bit < 8.
 
105
                 * We have 2 possibilities :
 
106
                 *   - more than the last bit differs => return NULL
 
107
                 *   - walk down on side = (x[pos] >> node_bit) & 1
 
108
                 */
 
109
                side = *(unsigned char *)x >> node_bit;
 
110
                if (((*(unsigned char*)(node->key + pos) >> node_bit) ^ side) > 1)
 
111
                        goto ret_null;
 
112
                side &= 1;
 
113
                troot = node->node.branches.b[side];
87
114
        }
 
115
 walk_left:
 
116
        troot = node->node.branches.b[EB_LEFT];
 
117
 walk_down:
 
118
        while (eb_gettag(troot) != EB_LEAF)
 
119
                troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
 
120
        node = container_of(eb_untag(troot, EB_LEAF),
 
121
                            struct ebpt_node, node.branches);
 
122
 ret_node:
 
123
        return node;
 
124
 ret_null:
 
125
        return NULL;
88
126
}
89
127
 
90
128
/* Insert ebpt_node <new> into subtree starting at node root <root>.