The FreeRADIUS server $Id: 15bac2a4c627c01d1aa2047687b3418955ac7f00 $
Loading...
Searching...
No Matches
htrie.c
Go to the documentation of this file.
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 */
23RCSID("$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
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};
37
39 [FR_HTRIE_HASH] = {
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] = {
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 */
91fr_htrie_t *fr_htrie_alloc(TALLOC_CTX *ctx,
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{
98 fr_htrie_t *ht;
99
100 ht = talloc_zero(ctx, fr_htrie_t);
101 if (unlikely(!ht)) {
102 fr_strerror_const("Failed allocating fr_htrie_t");
103 return NULL;
104 }
105 ht->type = type;
106
107 switch (type) {
108 case FR_HTRIE_HASH:
109 if (!hash_data || !cmp_data) {
110 fr_strerror_const("hash_data and cmp_data must not be NULL for FR_HTRIE_HASH");
111 return NULL;
112 }
113
114 ht->store = fr_hash_table_alloc(ht, hash_data, cmp_data, free_data);
115 if (unlikely(!ht->store)) {
116 error:
117 talloc_free(ht);
118 return NULL;
119 }
120 ht->funcs = default_funcs[type];
121 return ht;
122
123 case FR_HTRIE_RB:
124 if (!cmp_data) {
125 fr_strerror_const("cmp_data must not be NULL for FR_HTRIE_RB");
126 return NULL;
127 }
128
129 ht->store = fr_rb_alloc(ht, cmp_data, free_data);
130 if (unlikely(!ht->store)) goto error;
131 ht->funcs = default_funcs[type];
132 return ht;
133
134 case FR_HTRIE_TRIE:
135 if (!get_key) {
136 fr_strerror_const("get_key must not be NULL for FR_HTRIE_TRIE");
137 return NULL;
138 }
139
140 ht->store = fr_trie_alloc(ht, get_key, free_data);
141 if (unlikely(!ht->store)) goto error;
142 ht->funcs = default_funcs[type];
143 return ht;
144
145 case FR_HTRIE_INVALID:
146 fr_assert_msg(0, "FR_TYPE_INVALID passed as htype");
147 return NULL;
148
149 case FR_HTRIE_AUTO:
150 fr_assert_msg(0, "FR_HTRIE_AUTO must be resolved to a concrete htype value using fr_htrie_hint()");
151 return NULL;
152
153 default:
154 return NULL;
155 }
156}
#define RCSID(id)
Definition build.h:485
#define L(_str)
Helper for initialising arrays of string literals.
Definition build.h:209
#define unlikely(_x)
Definition build.h:383
#define NUM_ELEMENTS(_t)
Definition build.h:339
static fr_ring_buffer_t * rb
#define fr_assert_msg(_x, _msg,...)
Calls panic_action ifndef NDEBUG, else logs error and causes the server to exit immediately with code...
Definition debug.h:210
void * fr_hash_table_find(fr_hash_table_t *ht, void const *data)
Find data in a hash table.
Definition hash.c:429
uint32_t(* fr_hash_t)(void const *)
Definition hash.h:36
#define fr_hash_table_alloc(_ctx, _hash_node, _cmp_node, _free_node)
Definition hash.h:58
static fr_htrie_funcs_t const default_funcs[]
Definition htrie.c:38
size_t fr_htrie_type_table_len
Definition htrie.c:36
fr_table_num_sorted_t const fr_htrie_type_table[]
Definition htrie.c:30
#define FUNC(_prefix, _op)
Definition htrie.c:28
fr_htrie_t * fr_htrie_alloc(TALLOC_CTX *ctx, fr_htrie_type_t type, fr_hash_t hash_data, fr_cmp_t cmp_data, fr_trie_key_t get_key, fr_free_t free_data)
An abstraction over our internal hashes, rb trees, and prefix tries.
Definition htrie.c:91
fr_htrie_type_t
Definition htrie.h:49
@ FR_HTRIE_RB
Data is stored in a rb tree.
Definition htrie.h:52
@ FR_HTRIE_TRIE
Data is stored in a prefix trie.
Definition htrie.h:53
@ FR_HTRIE_HASH
Data is stored in a hash.
Definition htrie.h:51
@ FR_HTRIE_AUTO
Automatically choose the best type.
Definition htrie.h:54
@ FR_HTRIE_INVALID
Definition htrie.h:50
void *(* fr_htrie_find_t)(void *ht, void const *data)
Definition htrie.h:37
void * store
What we're using to store node data.
Definition htrie.h:82
fr_htrie_type_t type
type of the htrie
Definition htrie.h:81
fr_htrie_find_t match
exact prefix match
Definition htrie.h:69
fr_htrie_funcs_t funcs
Function pointers for the various operations.
Definition htrie.h:83
Which functions are used for the different operations.
Definition htrie.h:67
A hash/rb/prefix trie abstraction.
Definition htrie.h:80
talloc_free(reap)
int8_t(* fr_cmp_t)(void const *a, void const *b)
Definition misc.h:38
void(* fr_free_t)(void *)
Definition misc.h:39
void * fr_rb_find(fr_rb_tree_t const *tree, void const *data)
Find an element in the tree, returning the data, not the node.
Definition rb.c:577
#define fr_rb_alloc(_ctx, _data_cmp, _data_free)
Allocs a red black tree.
Definition rb.h:223
fr_aka_sim_id_type_t type
An element in a lexicographically sorted array of name to num mappings.
Definition table.h:49
fr_trie_t * fr_trie_alloc(TALLOC_CTX *ctx, fr_trie_key_t get_key, fr_free_t free_data)
Allocate a trie.
Definition trie.c:740
void * fr_trie_match(fr_trie_t *ft, void const *data)
Match an element exactly in the trie, returning the data.
Definition trie.c:2667
int(* fr_trie_key_t)(uint8_t **out, size_t *outlen, void const *data)
Definition trie.h:56
#define fr_strerror_const(_msg)
Definition strerror.h:223