/src/freeradius-server/src/lib/util/htrie.c
Line | Count | Source |
1 | | /* |
2 | | * This library is free software; you can redistribute it and/or |
3 | | * modify it under the terms of the GNU Lesser General Public |
4 | | * License as published by the Free Software Foundation; either |
5 | | * version 2.1 of the License, or (at your option) any later version. |
6 | | * |
7 | | * This library is distributed in the hope that it will be useful, |
8 | | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
9 | | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
10 | | * Lesser General Public License for more details. |
11 | | * |
12 | | * You should have received a copy of the GNU Lesser General Public |
13 | | * License along with this library; if not, write to the Free Software |
14 | | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA |
15 | | */ |
16 | | |
17 | | /** hash / rb / patricia trees |
18 | | * |
19 | | * @file src/lib/util/htrie.c |
20 | | * |
21 | | * @copyright 2021 Network RADIUS SAS (legal@networkradius.com) |
22 | | */ |
23 | | RCSID("$Id: 017e773f70672d048933f213446eb48e529516ac $") |
24 | | |
25 | | #include <freeradius-devel/util/debug.h> |
26 | | #include <freeradius-devel/util/htrie.h> |
27 | | |
28 | | #define FUNC(_prefix, _op) ._op = (fr_htrie_ ##_op ## _t) fr_##_prefix##_## _op |
29 | | |
30 | | fr_table_num_sorted_t const fr_htrie_type_table[] = { |
31 | | { L("auto"), FR_HTRIE_AUTO }, |
32 | | { L("hash"), FR_HTRIE_HASH }, |
33 | | { L("rb"), FR_HTRIE_RB }, |
34 | | { L("trie"), FR_HTRIE_TRIE }, |
35 | | }; |
36 | | size_t fr_htrie_type_table_len = NUM_ELEMENTS(fr_htrie_type_table); |
37 | | |
38 | | static fr_htrie_funcs_t const default_funcs[] = { |
39 | | [FR_HTRIE_HASH] = { |
40 | | .match = (fr_htrie_find_t) fr_hash_table_find, |
41 | | FUNC(hash_table, find), |
42 | | FUNC(hash_table, insert), |
43 | | FUNC(hash_table, replace), |
44 | | FUNC(hash_table, remove), |
45 | | FUNC(hash_table, delete), |
46 | | FUNC(hash_table, num_elements) |
47 | | }, |
48 | | [FR_HTRIE_RB] = { |
49 | | .match = (fr_htrie_find_t) fr_rb_find, |
50 | | FUNC(rb, find), |
51 | | FUNC(rb, insert), |
52 | | FUNC(rb, replace), |
53 | | FUNC(rb, remove), |
54 | | FUNC(rb, delete), |
55 | | FUNC(rb, num_elements) |
56 | | }, |
57 | | [FR_HTRIE_TRIE] = { |
58 | | .match = (fr_htrie_find_t) fr_trie_match, |
59 | | FUNC(trie, find), |
60 | | FUNC(trie, insert), |
61 | | FUNC(trie, replace), |
62 | | FUNC(trie, remove), |
63 | | FUNC(trie, delete), |
64 | | FUNC(trie, num_elements) |
65 | | } |
66 | | }; |
67 | | |
68 | | /** An abstraction over our internal hashes, rb trees, and prefix tries |
69 | | * |
70 | | * This is useful where the data type being inserted into the tree |
71 | | * is user controlled, and so we need to pick the most efficient structure |
72 | | * for a given data type dynamically at runtime. |
73 | | * |
74 | | * @param[in] ctx to bind the htrie's lifetime to. |
75 | | * @param[in] type One of: |
76 | | * - FR_HTRIE_HASH |
77 | | * - FR_HTRIE_RB |
78 | | * - FR_HTRIE_TRIE |
79 | | * @param[in] hash_data Used by FR_HTRIE_HASH to convert the |
80 | | * data into a 32bit integer used for binning. |
81 | | * @param[in] cmp_data Used to determine exact matched. |
82 | | * @param[in] get_key Used by the prefix trie to extract a key |
83 | | * from the data. |
84 | | * @param[in] free_data The callback used to free the data if it is |
85 | | * deleted or replaced. May be NULL in which |
86 | | * case data will not be freed for these operations. |
87 | | * @return |
88 | | * - A new htrie on success. |
89 | | * - NULL on failure, either missing functions or a memory allocation error. |
90 | | */ |
91 | | fr_htrie_t *fr_htrie_alloc(TALLOC_CTX *ctx, |
92 | | fr_htrie_type_t type, |
93 | | fr_hash_t hash_data, |
94 | | fr_cmp_t cmp_data, |
95 | | fr_trie_key_t get_key, |
96 | | fr_free_t free_data) |
97 | 0 | { |
98 | 0 | fr_htrie_t *ht; |
99 | |
|
100 | 0 | ht = talloc_zero(ctx, fr_htrie_t); |
101 | 0 | if (unlikely(!ht)) { |
102 | 0 | fr_strerror_const("Failed allocating fr_htrie_t"); |
103 | 0 | return NULL; |
104 | 0 | } |
105 | 0 | ht->type = type; |
106 | |
|
107 | 0 | switch (type) { |
108 | 0 | case FR_HTRIE_HASH: |
109 | 0 | if (!hash_data || !cmp_data) { |
110 | 0 | fr_strerror_const("hash_data and cmp_data must not be NULL for FR_HTRIE_HASH"); |
111 | 0 | return NULL; |
112 | 0 | } |
113 | | |
114 | 0 | ht->store = fr_hash_table_alloc(ht, hash_data, cmp_data, free_data); |
115 | 0 | if (unlikely(!ht->store)) { |
116 | 0 | error: |
117 | 0 | talloc_free(ht); |
118 | 0 | return NULL; |
119 | 0 | } |
120 | 0 | ht->funcs = default_funcs[type]; |
121 | 0 | return ht; |
122 | | |
123 | 0 | case FR_HTRIE_RB: |
124 | 0 | if (!cmp_data) { |
125 | 0 | fr_strerror_const("cmp_data must not be NULL for FR_HTRIE_RB"); |
126 | 0 | return NULL; |
127 | 0 | } |
128 | | |
129 | 0 | ht->store = fr_rb_alloc(ht, cmp_data, free_data); |
130 | 0 | if (unlikely(!ht->store)) goto error; |
131 | 0 | ht->funcs = default_funcs[type]; |
132 | 0 | return ht; |
133 | | |
134 | 0 | case FR_HTRIE_TRIE: |
135 | 0 | if (!get_key) { |
136 | 0 | fr_strerror_const("get_key must not be NULL for FR_HTRIE_TRIE"); |
137 | 0 | return NULL; |
138 | 0 | } |
139 | | |
140 | 0 | ht->store = fr_trie_alloc(ht, get_key, free_data); |
141 | 0 | if (unlikely(!ht->store)) goto error; |
142 | 0 | ht->funcs = default_funcs[type]; |
143 | 0 | return ht; |
144 | | |
145 | 0 | case FR_HTRIE_INVALID: |
146 | 0 | fr_assert_msg(0, "FR_TYPE_INVALID passed as htype"); |
147 | 0 | return NULL; |
148 | | |
149 | 0 | case FR_HTRIE_AUTO: |
150 | 0 | fr_assert_msg(0, "FR_HTRIE_AUTO must be resolved to a concrete htype value using fr_htrie_hint()"); |
151 | 0 | return NULL; |
152 | | |
153 | 0 | default: |
154 | | return NULL; |
155 | 0 | } |
156 | 0 | } |