/src/haproxy/src/ebmbtree.c
Line | Count | Source |
1 | | /* |
2 | | * Elastic Binary Trees - exported functions for Multi-Byte data nodes. |
3 | | * Version 6.0.6 |
4 | | * (C) 2002-2011 - Willy Tarreau <w@1wt.eu> |
5 | | * |
6 | | * This library is free software; you can redistribute it and/or |
7 | | * modify it under the terms of the GNU Lesser General Public |
8 | | * License as published by the Free Software Foundation, version 2.1 |
9 | | * exclusively. |
10 | | * |
11 | | * This library is distributed in the hope that it will be useful, |
12 | | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
14 | | * Lesser General Public License for more details. |
15 | | * |
16 | | * You should have received a copy of the GNU Lesser General Public |
17 | | * License along with this library; if not, write to the Free Software |
18 | | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
19 | | */ |
20 | | |
21 | | /* Consult ebmbtree.h for more details about those functions */ |
22 | | |
23 | | #include <import/ebmbtree.h> |
24 | | |
25 | | /* Find the first occurrence of a key of <len> bytes in the tree <root>. |
26 | | * If none can be found, return NULL. |
27 | | */ |
28 | | struct ebmb_node * |
29 | | ebmb_lookup(struct eb_root *root, const void *x, unsigned int len) |
30 | 0 | { |
31 | 0 | return __ebmb_lookup(root, x, len); |
32 | 0 | } |
33 | | |
34 | | /* Insert ebmb_node <new> into subtree starting at node root <root>. |
35 | | * Only new->key needs be set with the key. The ebmb_node is returned. |
36 | | * If root->b[EB_RGHT]==1, the tree may only contain unique keys. The |
37 | | * len is specified in bytes. |
38 | | */ |
39 | | struct ebmb_node * |
40 | | ebmb_insert(struct eb_root *root, struct ebmb_node *new, unsigned int len) |
41 | 0 | { |
42 | 0 | return __ebmb_insert(root, new, len); |
43 | 0 | } |
44 | | |
45 | | /* Find the first occurrence of the longest prefix matching a key <x> in the |
46 | | * tree <root>. It's the caller's responsibility to ensure that key <x> is at |
47 | | * least as long as the keys in the tree. If none can be found, return NULL. |
48 | | */ |
49 | | struct ebmb_node * |
50 | | ebmb_lookup_longest(struct eb_root *root, const void *x) |
51 | 0 | { |
52 | 0 | return __ebmb_lookup_longest(root, x); |
53 | 0 | } |
54 | | |
55 | | /* Find the first occurrence of a prefix matching a key <x> of <pfx> BITS in the |
56 | | * tree <root>. If none can be found, return NULL. |
57 | | */ |
58 | | struct ebmb_node * |
59 | | ebmb_lookup_prefix(struct eb_root *root, const void *x, unsigned int pfx) |
60 | 0 | { |
61 | 0 | return __ebmb_lookup_prefix(root, x, pfx); |
62 | 0 | } |
63 | | |
64 | | /* Insert ebmb_node <new> into a prefix subtree starting at node root <root>. |
65 | | * Only new->key and new->pfx need be set with the key and its prefix length. |
66 | | * Note that bits between <pfx> and <len> are theoretically ignored and should be |
67 | | * zero, as it is not certain yet that they will always be ignored everywhere |
68 | | * (eg in bit compare functions). |
69 | | * The ebmb_node is returned. |
70 | | * If root->b[EB_RGHT]==1, the tree may only contain unique keys. The |
71 | | * len is specified in bytes. |
72 | | */ |
73 | | struct ebmb_node * |
74 | | ebmb_insert_prefix(struct eb_root *root, struct ebmb_node *new, unsigned int len) |
75 | 0 | { |
76 | 0 | return __ebmb_insert_prefix(root, new, len); |
77 | 0 | } |