Coverage Report

Created: 2026-02-26 06:38

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/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: 1c1e9b75fc68a6e073f3e052bc933ccb518ebc38 $")
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
    .iter_init = (fr_htrie_iter_func_t) fr_hash_table_iter_init,
48
    .iter_next = (fr_htrie_iter_func_t) fr_hash_table_iter_next,
49
  },
50
  [FR_HTRIE_RB] = {
51
    .match = (fr_htrie_find_t) fr_rb_find,
52
    FUNC(rb, find),
53
    FUNC(rb, insert),
54
    FUNC(rb, replace),
55
    FUNC(rb, remove),
56
    FUNC(rb, delete),
57
    FUNC(rb, num_elements),
58
    .iter_init = (fr_htrie_iter_func_t) fr_rb_iter_init_inorder,
59
    .iter_next = (fr_htrie_iter_func_t) fr_rb_iter_next_inorder,
60
  },
61
  [FR_HTRIE_TRIE] = {
62
    .match = (fr_htrie_find_t) fr_trie_match,
63
    FUNC(trie, find),
64
    FUNC(trie, insert),
65
    FUNC(trie, replace),
66
    FUNC(trie, remove),
67
    FUNC(trie, delete),
68
    FUNC(trie, num_elements),
69
  }
70
};
71
72
/** An abstraction over our internal hashes, rb trees, and prefix tries
73
 *
74
 * This is useful where the data type being inserted into the tree
75
 * is user controlled, and so we need to pick the most efficient structure
76
 * for a given data type dynamically at runtime.
77
 *
78
 * @param[in] ctx   to bind the htrie's lifetime to.
79
 * @param[in] type    One of:
80
 *        - FR_HTRIE_HASH
81
 *        - FR_HTRIE_RB
82
 *        - FR_HTRIE_TRIE
83
 * @param[in] hash_data   Used by FR_HTRIE_HASH to convert the
84
 *        data into a 32bit integer used for binning.
85
 * @param[in] cmp_data    Used to determine exact matched.
86
 * @param[in] get_key   Used by the prefix trie to extract a key
87
 *        from the data.
88
 * @param[in] free_data   The callback used to free the data if it is
89
 *        deleted or replaced. May be NULL in which
90
 *        case data will not be freed for these operations.
91
 * @return
92
 *  - A new htrie on success.
93
 *  - NULL on failure, either missing functions or a memory allocation error.
94
 */
95
fr_htrie_t *fr_htrie_alloc(TALLOC_CTX *ctx,
96
         fr_htrie_type_t type,
97
         fr_hash_t hash_data,
98
         fr_cmp_t cmp_data,
99
         fr_trie_key_t get_key,
100
         fr_free_t free_data)
101
0
{
102
0
  fr_htrie_t *ht;
103
104
0
  ht = talloc_zero(ctx, fr_htrie_t);
105
0
  if (unlikely(!ht)) {
106
0
    fr_strerror_const("Failed allocating fr_htrie_t");
107
0
    return NULL;
108
0
  }
109
0
  ht->type = type;
110
111
0
  switch (type) {
112
0
  case FR_HTRIE_HASH:
113
0
    if (!hash_data || !cmp_data) {
114
0
      fr_strerror_const("hash_data and cmp_data must not be NULL for FR_HTRIE_HASH");
115
0
      return NULL;
116
0
    }
117
118
0
    ht->store = fr_hash_table_alloc(ht, hash_data, cmp_data, free_data);
119
0
    if (unlikely(!ht->store)) {
120
0
    error:
121
0
      talloc_free(ht);
122
0
      return NULL;
123
0
    }
124
0
    ht->funcs = default_funcs[type];
125
0
    return ht;
126
127
0
  case FR_HTRIE_RB:
128
0
    if (!cmp_data) {
129
0
      fr_strerror_const("cmp_data must not be NULL for FR_HTRIE_RB");
130
0
      return NULL;
131
0
    }
132
133
0
    ht->store = fr_rb_alloc(ht, cmp_data, free_data);
134
0
    if (unlikely(!ht->store)) goto error;
135
0
    ht->funcs = default_funcs[type];
136
0
    return ht;
137
138
0
  case FR_HTRIE_TRIE:
139
0
    if (!get_key) {
140
0
      fr_strerror_const("get_key must not be NULL for FR_HTRIE_TRIE");
141
0
      return NULL;
142
0
    }
143
144
0
    ht->store = fr_trie_alloc(ht, get_key, free_data);
145
0
    if (unlikely(!ht->store)) goto error;
146
0
    ht->funcs = default_funcs[type];
147
0
    return ht;
148
149
0
  case FR_HTRIE_INVALID:
150
0
    fr_assert_msg(0, "FR_TYPE_INVALID passed as htype");
151
0
    return NULL;
152
153
0
  case FR_HTRIE_AUTO:
154
0
    fr_assert_msg(0, "FR_HTRIE_AUTO must be resolved to a concrete htype value using fr_htrie_hint()");
155
0
    return NULL;
156
157
0
  default:
158
    return NULL;
159
0
  }
160
0
}