The FreeRADIUS server $Id: 15bac2a4c627c01d1aa2047687b3418955ac7f00 $
Loading...
Searching...
No Matches
heap.h
Go to the documentation of this file.
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 binary heaps
19 *
20 * @file src/lib/util/heap.h
21 *
22 * @copyright 2007 Alan DeKok
23 */
24RCSIDH(heap_h, "$Id: 5c615f0e4fee73795140048ce5b2eac2f3fd941f $")
25
26#ifdef __cplusplus
27extern "C" {
28#endif
29
30#include <freeradius-devel/build.h>
31#include <freeradius-devel/missing.h>
32#include <freeradius-devel/util/talloc.h>
33
34#include <stdint.h>
35#include <sys/types.h>
36
37/*
38 * Allow public and private versions of the same structures
39 */
40#ifdef _CONST
41# error _CONST can only be defined in the local header
42#endif
43#ifndef _HEAP_PRIVATE
44# define _CONST const
45#else
46# define _CONST
47#endif
48
49/** Comparator to order heap elements
50 *
51 * Return negative numbers to put 'a' at the top of the heap.
52 * Return positive numbers to put 'b' at the top of the heap.
53 */
54typedef int8_t (*fr_heap_cmp_t)(void const *a, void const *b);
55
56/** The main heap structure
57 *
58 * A heap entry is made of a pointer to the object, which
59 * contains the key. The heap itself is an array of pointers.
60 *
61 * Heaps normally support only ordered insert, and extraction
62 * of the minimum element. The heap entry can contain an "int"
63 * field that holds the entries position in the heap. The offset
64 * of the field is held inside of the heap structure.
65 */
66typedef struct {
67 unsigned int _CONST size; //!< Number of nodes allocated.
68 unsigned int _CONST min; //!< Minimum number of elements we allow
69 ///< the heap to reduce down to.
70 size_t _CONST offset; //!< Offset of heap index in element structure.
71
72 unsigned int _CONST num_elements; //!< Number of nodes used.
73
74 char const * _CONST type; //!< Talloc type of elements.
75 fr_heap_cmp_t _CONST cmp; //!< Comparator function.
76
77 void * _CONST p[]; //!< Array of nodes.
78} fr_heap_t;
79
80typedef unsigned int fr_heap_index_t;
81typedef unsigned int fr_heap_iter_t;
82
83#define FR_HEAP_INDEX_INVALID (0)
84
85/** How many talloc headers need to be pre-allocated for a heap
86 */
87#define FR_HEAP_TALLOC_HEADERS 2
88
89size_t fr_heap_pre_alloc_size(unsigned int count);
90
91/** Creates a heap that can be used with non-talloced elements
92 *
93 * @param[in] _ctx Talloc ctx to allocate heap in.
94 * @param[in] _cmp Comparator used to compare elements.
95 * @param[in] _type Of elements.
96 * @param[in] _field to store heap indexes in.
97 * @param[in] _init the initial number of elements to allocate.
98 * Pass 0 to use the default.
99 */
100#define fr_heap_alloc(_ctx, _cmp, _type, _field, _init) \
101 _fr_heap_alloc(_ctx, _cmp, NULL, (size_t)offsetof(_type, _field), _init)
102
103/** Creates a heap that verifies elements are of a specific talloc type
104 *
105 * @param[in] _ctx Talloc ctx to allocate heap in.
106 * @param[in] _cmp Comparator used to compare elements.
107 * @param[in] _talloc_type of elements.
108 * @param[in] _field to store heap indexes in.
109 * @param[in] _init the initial number of elements to allocate.
110 * Pass 0 to use the default.
111 * @return
112 * - A new heap.
113 * - NULL on error.
114 */
115#define fr_heap_talloc_alloc(_ctx, _cmp, _talloc_type, _field, _init) \
116 _fr_heap_alloc(_ctx, _cmp, #_talloc_type, (size_t)offsetof(_talloc_type, _field), _init)
117fr_heap_t *_fr_heap_alloc(TALLOC_CTX *ctx, fr_heap_cmp_t cmp, char const *talloc_type,
118 size_t offset, unsigned int init) CC_HINT(nonnull(2));
119
120/** Check if an entry is inserted into a heap
121 *
122 * @param[in] heap_idx from object to check.
123 */
124static inline bool fr_heap_entry_inserted(fr_heap_index_t heap_idx)
125{
126 return (heap_idx != FR_HEAP_INDEX_INVALID);
127}
128
129/** Return the item from the top of the heap but don't pop it
130 *
131 * @param[in] h to return element from.
132 * @return
133 * - Element at the top of the heap.
134 * - NULL if no elements remain in the heap.
135 */
136static inline void *fr_heap_peek(fr_heap_t *h)
137{
138 if (h->num_elements == 0) return NULL;
139
140 return h->p[1];
141}
142
143/** Peek at a specific index in the heap
144 *
145 * @param[in] h to return element from.
146 * @param[in] idx to lookup
147 * @return
148 * - Element at the top of the heap.
149 * - NULL if index outside of the range of the heap.
150 */
151static inline void *fr_heap_peek_at(fr_heap_t *h, fr_heap_index_t idx)
152{
153 if (unlikely(idx > h->num_elements)) return NULL;
154
155 return h->p[idx];
156}
157
158/** Peek at the last element in the heap (not necessarily the bottom)
159 *
160 * @param[in] h to return element from.
161 * @return
162 * - Last element in the heap.
163 * - NULL if no elements remain in the heap.
164 */
165static inline void *fr_heap_peek_tail(fr_heap_t *h)
166{
167 if (h->num_elements == 0) return NULL;
168
169 /*
170 * If this is NULL, we have a problem.
171 */
172 return h->p[h->num_elements];
173}
174
175/** Return the number of elements in the heap
176 *
177 * @param[in] h to return the number of elements from.
178 */
179static inline unsigned int fr_heap_num_elements(fr_heap_t *h)
180{
181 return h->num_elements;
182}
183
184int fr_heap_insert(fr_heap_t **hp, void *data) CC_HINT(nonnull);
185int fr_heap_extract(fr_heap_t **hp, void *data) CC_HINT(nonnull);
186void *fr_heap_pop(fr_heap_t **hp) CC_HINT(nonnull);
187
188void *fr_heap_iter_init(fr_heap_t *hp, fr_heap_iter_t *iter) CC_HINT(nonnull);
189void *fr_heap_iter_next(fr_heap_t *hp, fr_heap_iter_t *iter) CC_HINT(nonnull);
190
191/** Iterate over the contents of a heap
192 *
193 * @note The initializer section of a for loop can't declare variables with distinct
194 * base types, so we require a containing block, and can't follow the standard
195 * do {...} while(0) dodge. The code to be run for each item in the heap should
196 * thus start with one open brace and end with two close braces, and shouldn't
197 * be followed with a semicolon.
198 * This may fake out code formatting programs and code-aware editors.
199 *
200 * @param[in] _heap to iterate over.
201 * @param[in] _type of item the heap contains.
202 * @param[in] _data Name of variable holding a pointer to the heap element.
203 * Will be declared in the scope of the loop.
204 */
205#define fr_heap_foreach(_heap, _type, _data) \
206{ \
207 fr_heap_iter_t _iter; \
208 for (_type *_data = fr_heap_iter_init(_heap, &_iter); _data; _data = fr_heap_iter_next(_heap, &_iter))
209
210#ifndef TALLOC_GET_TYPE_ABORT_NOOP
211void fr_heap_verify(char const *file, int line, fr_heap_t *hp);
212# define FR_HEAP_VERIFY(_heap) fr_heap_verify(__FILE__, __LINE__, _heap)
213#elif !defined(NDEBUG)
214# define FR_HEAP_VERIFY(_heap) fr_assert(_heap)
215#else
216# define FR_HEAP_VERIFY(_heap)
217#endif
218
219#undef _CONST
220#ifdef __cplusplus
221}
222#endif
int const char * file
Definition acutest.h:702
int const char int line
Definition acutest.h:702
static bool init
Definition fuzzer.c:41
#define RCSIDH(h, id)
Definition build.h:484
#define unlikely(_x)
Definition build.h:381
unsigned int fr_heap_index_t
Definition heap.h:80
char const *_CONST type
Talloc type of elements.
Definition heap.h:74
static void * fr_heap_peek(fr_heap_t *h)
Return the item from the top of the heap but don't pop it.
Definition heap.h:136
void fr_heap_verify(char const *file, int line, fr_heap_t *hp)
Definition heap.c:380
unsigned int _CONST min
Minimum number of elements we allow the heap to reduce down to.
Definition heap.h:68
static void * fr_heap_peek_tail(fr_heap_t *h)
Peek at the last element in the heap (not necessarily the bottom)
Definition heap.h:165
void * fr_heap_iter_init(fr_heap_t *hp, fr_heap_iter_t *iter)
Iterate over entries in heap.
Definition heap.c:351
unsigned int fr_heap_iter_t
Definition heap.h:81
unsigned int _CONST size
Number of nodes allocated.
Definition heap.h:67
size_t fr_heap_pre_alloc_size(unsigned int count)
Return how many bytes need to be allocated to hold a heap of a given size.
Definition heap.c:52
int fr_heap_insert(fr_heap_t **hp, void *data)
Insert a new element into the heap.
Definition heap.c:146
#define _CONST
Definition heap.h:44
fr_heap_t * _fr_heap_alloc(TALLOC_CTX *ctx, fr_heap_cmp_t cmp, char const *talloc_type, size_t offset, unsigned int init))
Definition heap.c:57
void * fr_heap_pop(fr_heap_t **hp)
Remove a node from the heap.
Definition heap.c:322
void * fr_heap_iter_next(fr_heap_t *hp, fr_heap_iter_t *iter)
Get the next entry in a heap.
Definition heap.c:371
unsigned int _CONST num_elements
Number of nodes used.
Definition heap.h:72
static bool fr_heap_entry_inserted(fr_heap_index_t heap_idx)
Check if an entry is inserted into a heap.
Definition heap.h:124
static void * fr_heap_peek_at(fr_heap_t *h, fr_heap_index_t idx)
Peek at a specific index in the heap.
Definition heap.h:151
int fr_heap_extract(fr_heap_t **hp, void *data)
Remove a node from the heap.
Definition heap.c:239
static unsigned int fr_heap_num_elements(fr_heap_t *h)
Return the number of elements in the heap.
Definition heap.h:179
void *_CONST p[]
Array of nodes.
Definition heap.h:77
fr_heap_cmp_t _CONST cmp
Comparator function.
Definition heap.h:75
#define FR_HEAP_INDEX_INVALID
Definition heap.h:83
int8_t(* fr_heap_cmp_t)(void const *a, void const *b)
Comparator to order heap elements.
Definition heap.h:54
size_t _CONST offset
Offset of heap index in element structure.
Definition heap.h:70
The main heap structure.
Definition heap.h:66
return count
Definition module.c:163
static fr_slen_t data
Definition value.h:1265
int nonnull(2, 5))