/src/freeradius-server/src/freeradius-devel/util/htrie.h

Source
#pragma once
/*
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
 */

/** Structures and prototypes for hash / rbtree / patricia trie structures
 *
 * @file src/lib/util/htrie.h
 *
 * @copyright 2021 The FreeRADIUS server project
 */
RCSIDH(htrie_h, "$Id: bbad8eae2e110d394f390b8edf77de4b2281136b $")

#ifdef __cplusplus
extern "C" {
#endif

#include <freeradius-devel/util/hash.h>
#include <freeradius-devel/util/rb.h>
#include <freeradius-devel/util/trie.h>
#include <freeradius-devel/util/types.h>

typedef struct fr_htrie_s fr_htrie_t;

typedef void *(*fr_htrie_find_t)(void *ht, void const *data);

typedef bool (*fr_htrie_insert_t)(void *ht, void const *data);

typedef int (*fr_htrie_replace_t)(void **old, void *ht, void const *data);

typedef void *(*fr_htrie_remove_t)(void *ht, void const *data);

typedef bool (*fr_htrie_delete_t)(void *ht, void const *data);

typedef uint32_t (*fr_htrie_num_elements_t)(void *ht);

typedef struct {
  union {
    fr_rb_iter_inorder_t  rb; //!< only in order
    fr_hash_iter_t    hash; //!< effectively random
  };
} fr_htrie_iter_t;

typedef void *(*fr_htrie_iter_func_t)(void *ht, void *iter);

typedef enum {
  FR_HTRIE_INVALID = 0,
  FR_HTRIE_HASH,    //!< Data is stored in a hash.
  FR_HTRIE_RB,    //!< Data is stored in a rb tree.
  FR_HTRIE_TRIE,    //!< Data is stored in a prefix trie.
  FR_HTRIE_AUTO,    //!< Automatically choose the best type.
        ///< Must be not be passed to fr_htrie_alloc().
        ///< If the user selects this, you must
        ///< call fr_htrie_hint() to determine the
        ///< best type.
} fr_htrie_type_t;

extern fr_table_num_sorted_t const fr_htrie_type_table[];
extern size_t fr_htrie_type_table_len;

/** Which functions are used for the different operations
 *
 */
typedef struct {
  fr_htrie_find_t   find;   //!< Absolute or prefix match.
  fr_htrie_find_t   match;    //!< exact prefix match
  fr_htrie_insert_t insert;   //!< Insert a new item into the store.
  fr_htrie_replace_t  replace;  //!< Replace an existing item in store.
  fr_htrie_remove_t remove;   //!< Remove an item from the store.
  fr_htrie_delete_t delete;   //!< Remove (and possibly free) and item from the store.
  fr_htrie_num_elements_t num_elements; //!< Number of elements currently in the store.
  fr_htrie_iter_func_t  iter_init;  //!< Initialize an iterator
  fr_htrie_iter_func_t  iter_next;  //!< go to the next element in an iterator
} fr_htrie_funcs_t;

/** A hash/rb/prefix trie abstraction
 *
 */
struct fr_htrie_s {
  fr_htrie_type_t   type;   //!< type of the htrie
  void      *store;   //!< What we're using to store node data
  fr_htrie_funcs_t  funcs;    //!< Function pointers for the various operations.
};

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);

/** Match data in a htrie
 *
 */
static inline CC_HINT(nonnull) void *fr_htrie_match(fr_htrie_t *ht, void const *data)
{
  return ht->funcs.match(ht->store, data);
}

/** Find data in a htrie
 *
 */
static inline CC_HINT(nonnull) void *fr_htrie_find(fr_htrie_t *ht, void const *data)
{
  return ht->funcs.find(ht->store, data);
}

/** Insert data into a htrie
 *
 */
static inline CC_HINT(nonnull) bool fr_htrie_insert(fr_htrie_t *ht, void const *data)
{
  return ht->funcs.insert(ht->store, data);
}

/** Replace data in a htrie, freeing previous data if free_data cb was passed to fr_htrie_alloc
 *
 */
static inline CC_HINT(nonnull(2,3)) int fr_htrie_replace(void **old, fr_htrie_t *ht, void const *data)
{
  return ht->funcs.replace(old, ht->store, data);
}

/** Remove data from a htrie without freeing it
 *
 */
static inline CC_HINT(nonnull) void *fr_htrie_remove(fr_htrie_t *ht, void const *data)
{
  return ht->funcs.remove(ht->store, data);
}

/** Delete data from a htrie, freeing it if free_data cb was passed to fr_htrie_alloc
 *
 */
static inline CC_HINT(nonnull) bool fr_htrie_delete(fr_htrie_t *ht, void const *data)
{
  return ht->funcs.delete(ht->store, data);
}

/** Return the number of elements in the htrie
 *
 */
static inline CC_HINT(nonnull) int fr_htrie_num_elements(fr_htrie_t *ht)
{
  return ht->funcs.num_elements(ht->store);
}

/** Initialize an iterator
 *
 */
static inline CC_HINT(nonnull) void *fr_htrie_iter_init(fr_htrie_t *ht, fr_htrie_iter_t *iter)
{
  fr_assert(ht->funcs.iter_init != NULL);   /* not currently defined for patricia tries */

  return ht->funcs.iter_init(ht->store, iter);
}

/** Return the next element of an iterator
 *
 */
static inline CC_HINT(nonnull) void *fr_htrie_iter_next(fr_htrie_t *ht, fr_htrie_iter_t *iter)
{
  fr_assert(ht->funcs.iter_next != NULL);   /* not currently defined for patricia tries */

  return ht->funcs.iter_next(ht->store, iter);
}

static inline fr_htrie_type_t fr_htrie_hint(fr_type_t type)
{
  switch (type) {
  case FR_TYPE_STRING:
  case FR_TYPE_OCTETS:
    return FR_HTRIE_HASH;

  /* IPv4/v6 IP and prefix */
  case FR_TYPE_IP:
    return FR_HTRIE_TRIE;

  case FR_TYPE_IFID:
  case FR_TYPE_ETHERNET:
  case FR_TYPE_INTEGER:
  case FR_TYPE_FLOAT32:
  case FR_TYPE_FLOAT64:
    return FR_HTRIE_RB;

  case FR_TYPE_ATTR:
  case FR_TYPE_NON_LEAF:
    break;
  }

  return FR_HTRIE_INVALID;
}

/** Return a static string containing the type name
 *
 * @param[in] type to return name for.
 * @return name of the type
 *
 * @hidecallergraph
 */
static inline char const *fr_htrie_type_to_str(fr_htrie_type_t type)
{
  return fr_table_str_by_value(fr_htrie_type_table, type, "<INVALID>");
}

#ifdef __cplusplus
}
#endif

Coverage Report

Created: 2026-08-08 07:10

Line	Count	Source
1		#pragma once
2		/*
3		* This program is free software; you can redistribute it and/or modify
4		* it under the terms of the GNU General Public License as published by
5		* the Free Software Foundation; either version 2 of the License, or
6		* (at your option) any later version.
7		*
8		* This program is distributed in the hope that it will be useful,
9		* but WITHOUT ANY WARRANTY; without even the implied warranty of
10		* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11		* GNU General Public License for more details.
12		*
13		* You should have received a copy of the GNU General Public License
14		* along with this program; if not, write to the Free Software
15		* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
16		*/
17
18		/** Structures and prototypes for hash / rbtree / patricia trie structures
19		*
20		* @file src/lib/util/htrie.h
21		*
22		* @copyright 2021 The FreeRADIUS server project
23		*/
24		RCSIDH(htrie_h, "$Id: bbad8eae2e110d394f390b8edf77de4b2281136b $")
25
26		#ifdef __cplusplus
27		extern "C" {
28		#endif
29
30		#include <freeradius-devel/util/hash.h>
31		#include <freeradius-devel/util/rb.h>
32		#include <freeradius-devel/util/trie.h>
33		#include <freeradius-devel/util/types.h>
34
35		typedef struct fr_htrie_s fr_htrie_t;
36
37		typedef void (fr_htrie_find_t)(void ht, void const data);
38
39		typedef bool (fr_htrie_insert_t)(void ht, void const *data);
40
41		typedef int (fr_htrie_replace_t)(void old, void ht, void const *data);
42
43		typedef void (fr_htrie_remove_t)(void ht, void const data);
44
45		typedef bool (fr_htrie_delete_t)(void ht, void const *data);
46
47		typedef uint32_t (fr_htrie_num_elements_t)(void ht);
48
49		typedef struct {
50		union {
51		fr_rb_iter_inorder_t rb; //!< only in order
52		fr_hash_iter_t hash; //!< effectively random
53		};
54		} fr_htrie_iter_t;
55
56		typedef void (fr_htrie_iter_func_t)(void ht, void iter);
57
58		typedef enum {
59		FR_HTRIE_INVALID = 0,
60		FR_HTRIE_HASH, //!< Data is stored in a hash.
61		FR_HTRIE_RB, //!< Data is stored in a rb tree.
62		FR_HTRIE_TRIE, //!< Data is stored in a prefix trie.
63		FR_HTRIE_AUTO, //!< Automatically choose the best type.
64		///< Must be not be passed to fr_htrie_alloc().
65		///< If the user selects this, you must
66		///< call fr_htrie_hint() to determine the
67		///< best type.
68		} fr_htrie_type_t;
69
70		extern fr_table_num_sorted_t const fr_htrie_type_table[];
71		extern size_t fr_htrie_type_table_len;
72
73		/** Which functions are used for the different operations
74		*
75		*/
76		typedef struct {
77		fr_htrie_find_t find; //!< Absolute or prefix match.
78		fr_htrie_find_t match; //!< exact prefix match
79		fr_htrie_insert_t insert; //!< Insert a new item into the store.
80		fr_htrie_replace_t replace; //!< Replace an existing item in store.
81		fr_htrie_remove_t remove; //!< Remove an item from the store.
82		fr_htrie_delete_t delete; //!< Remove (and possibly free) and item from the store.
83		fr_htrie_num_elements_t num_elements; //!< Number of elements currently in the store.
84		fr_htrie_iter_func_t iter_init; //!< Initialize an iterator
85		fr_htrie_iter_func_t iter_next; //!< go to the next element in an iterator
86		} fr_htrie_funcs_t;
87
88		/** A hash/rb/prefix trie abstraction
89		*
90		*/
91		struct fr_htrie_s {
92		fr_htrie_type_t type; //!< type of the htrie
93		void *store; //!< What we're using to store node data
94		fr_htrie_funcs_t funcs; //!< Function pointers for the various operations.
95		};
96
97		fr_htrie_t fr_htrie_alloc(TALLOC_CTX ctx,
98		fr_htrie_type_t type,
99		fr_hash_t hash_data,
100		fr_cmp_t cmp_data,
101		fr_trie_key_t get_key,
102		fr_free_t free_data);
103
104		/** Match data in a htrie
105		*
106		*/
107		static inline CC_HINT(nonnull) void fr_htrie_match(fr_htrie_t ht, void const *data)
108	0	{
109	0	return ht->funcs.match(ht->store, data);
110	0	} Unexecuted instantiation: htrie.c:fr_htrie_match Unexecuted instantiation: compile.c:fr_htrie_match Unexecuted instantiation: switch.c:fr_htrie_match
111
112		/** Find data in a htrie
113		*
114		*/
115		static inline CC_HINT(nonnull) void fr_htrie_find(fr_htrie_t ht, void const *data)
116	0	{
117	0	return ht->funcs.find(ht->store, data);
118	0	} Unexecuted instantiation: htrie.c:fr_htrie_find Unexecuted instantiation: compile.c:fr_htrie_find Unexecuted instantiation: switch.c:fr_htrie_find
119
120		/** Insert data into a htrie
121		*
122		*/
123		static inline CC_HINT(nonnull) bool fr_htrie_insert(fr_htrie_t ht, void const data)
124	0	{
125	0	return ht->funcs.insert(ht->store, data);
126	0	} Unexecuted instantiation: htrie.c:fr_htrie_insert Unexecuted instantiation: compile.c:fr_htrie_insert Unexecuted instantiation: switch.c:fr_htrie_insert
127
128		/** Replace data in a htrie, freeing previous data if free_data cb was passed to fr_htrie_alloc
129		*
130		*/
131		static inline CC_HINT(nonnull(2,3)) int fr_htrie_replace(void *old, fr_htrie_t ht, void const *data)
132	0	{
133	0	return ht->funcs.replace(old, ht->store, data);
134	0	} Unexecuted instantiation: htrie.c:fr_htrie_replace Unexecuted instantiation: compile.c:fr_htrie_replace Unexecuted instantiation: switch.c:fr_htrie_replace
135
136		/** Remove data from a htrie without freeing it
137		*
138		*/
139		static inline CC_HINT(nonnull) void fr_htrie_remove(fr_htrie_t ht, void const *data)
140	0	{
141	0	return ht->funcs.remove(ht->store, data);
142	0	} Unexecuted instantiation: htrie.c:fr_htrie_remove Unexecuted instantiation: compile.c:fr_htrie_remove Unexecuted instantiation: switch.c:fr_htrie_remove
143
144		/** Delete data from a htrie, freeing it if free_data cb was passed to fr_htrie_alloc
145		*
146		*/
147		static inline CC_HINT(nonnull) bool fr_htrie_delete(fr_htrie_t ht, void const data)
148	0	{
149	0	return ht->funcs.delete(ht->store, data);
150	0	} Unexecuted instantiation: htrie.c:fr_htrie_delete Unexecuted instantiation: compile.c:fr_htrie_delete Unexecuted instantiation: switch.c:fr_htrie_delete
151
152		/** Return the number of elements in the htrie
153		*
154		*/
155		static inline CC_HINT(nonnull) int fr_htrie_num_elements(fr_htrie_t *ht)
156	0	{
157	0	return ht->funcs.num_elements(ht->store);
158	0	} Unexecuted instantiation: htrie.c:fr_htrie_num_elements Unexecuted instantiation: compile.c:fr_htrie_num_elements Unexecuted instantiation: switch.c:fr_htrie_num_elements
159
160		/** Initialize an iterator
161		*
162		*/
163		static inline CC_HINT(nonnull) void fr_htrie_iter_init(fr_htrie_t ht, fr_htrie_iter_t *iter)
164	0	{
165	0	fr_assert(ht->funcs.iter_init != NULL); /* not currently defined for patricia tries */
166	0
167	0	return ht->funcs.iter_init(ht->store, iter);
168	0	} Unexecuted instantiation: htrie.c:fr_htrie_iter_init Unexecuted instantiation: compile.c:fr_htrie_iter_init Unexecuted instantiation: switch.c:fr_htrie_iter_init
169
170		/** Return the next element of an iterator
171		*
172		*/
173		static inline CC_HINT(nonnull) void fr_htrie_iter_next(fr_htrie_t ht, fr_htrie_iter_t *iter)
174	0	{
175	0	fr_assert(ht->funcs.iter_next != NULL); /* not currently defined for patricia tries */
176	0
177	0	return ht->funcs.iter_next(ht->store, iter);
178	0	} Unexecuted instantiation: htrie.c:fr_htrie_iter_next Unexecuted instantiation: compile.c:fr_htrie_iter_next Unexecuted instantiation: switch.c:fr_htrie_iter_next
179
180		static inline fr_htrie_type_t fr_htrie_hint(fr_type_t type)
181	0	{
182	0	switch (type) {
183	0	case FR_TYPE_STRING:
184	0	case FR_TYPE_OCTETS:
185	0	return FR_HTRIE_HASH;
186
187		/* IPv4/v6 IP and prefix */
188	0	case FR_TYPE_IP:
189	0	return FR_HTRIE_TRIE;
190
191	0	case FR_TYPE_IFID:
192	0	case FR_TYPE_ETHERNET:
193	0	case FR_TYPE_INTEGER:
194	0	case FR_TYPE_FLOAT32:
195	0	case FR_TYPE_FLOAT64:
196	0	return FR_HTRIE_RB;
197
198	0	case FR_TYPE_ATTR:
199	0	case FR_TYPE_NON_LEAF:
200	0	break;
201	0	}
202
203	0	return FR_HTRIE_INVALID;
204	0	} Unexecuted instantiation: htrie.c:fr_htrie_hint Unexecuted instantiation: compile.c:fr_htrie_hint Unexecuted instantiation: switch.c:fr_htrie_hint
205
206		/** Return a static string containing the type name
207		*
208		* @param[in] type to return name for.
209		* @return name of the type
210		*
211		* @hidecallergraph
212		*/
213		static inline char const *fr_htrie_type_to_str(fr_htrie_type_t type)
214	0	{
215	0	return fr_table_str_by_value(fr_htrie_type_table, type, "<INVALID>");
216	0	} Unexecuted instantiation: htrie.c:fr_htrie_type_to_str Unexecuted instantiation: compile.c:fr_htrie_type_to_str Unexecuted instantiation: switch.c:fr_htrie_type_to_str
217
218		#ifdef __cplusplus
219		}
220		#endif