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

Source (jump to first uncovered line)
#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 binary heaps
 *
 * @file src/lib/util/heap.h
 *
 * @copyright 2007 Alan DeKok
 */
RCSIDH(heap_h, "$Id: 5c615f0e4fee73795140048ce5b2eac2f3fd941f $")

#ifdef __cplusplus
extern "C" {
#endif

#include <freeradius-devel/build.h>
#include <freeradius-devel/missing.h>
#include <freeradius-devel/util/talloc.h>

#include <stdint.h>
#include <sys/types.h>

/*
 *  Allow public and private versions of the same structures
 */
#ifdef _CONST
#  error _CONST can only be defined in the local header
#endif
#ifndef _HEAP_PRIVATE
#  define _CONST const
#else
#  define _CONST
#endif

/** Comparator to order heap elements
 *
 *  Return negative numbers to put 'a' at the top of the heap.
 *  Return positive numbers to put 'b' at the top of the heap.
 */
typedef int8_t (*fr_heap_cmp_t)(void const *a, void const *b);

/** The main heap structure
 *
 * A heap entry is made of a pointer to the object, which
 * contains the key.  The heap itself is an array of pointers.
 *
 * Heaps normally support only ordered insert, and extraction
 * of the minimum element.  The heap entry can contain an "int"
 * field that holds the entries position in the heap.  The offset
 * of the field is held inside of the heap structure.
 */
typedef struct {
  unsigned int  _CONST size;    //!< Number of nodes allocated.
  unsigned int  _CONST min;   //!< Minimum number of elements we allow
            ///< the heap to reduce down to.
  size_t    _CONST offset;    //!< Offset of heap index in element structure.

  unsigned int  _CONST num_elements;  //!< Number of nodes used.

  char const  * _CONST type;    //!< Talloc type of elements.
  fr_heap_cmp_t _CONST cmp;   //!< Comparator function.

  void    * _CONST p[];   //!< Array of nodes.
} fr_heap_t;

typedef unsigned int fr_heap_index_t;
typedef unsigned int fr_heap_iter_t;

#define FR_HEAP_INDEX_INVALID (0)

/** How many talloc headers need to be pre-allocated for a heap
 */
#define FR_HEAP_TALLOC_HEADERS 2

size_t fr_heap_pre_alloc_size(unsigned int count);

/** Creates a heap that can be used with non-talloced elements
 *
 * @param[in] _ctx    Talloc ctx to allocate heap in.
 * @param[in] _cmp    Comparator used to compare elements.
 * @param[in] _type   Of elements.
 * @param[in] _field    to store heap indexes in.
 * @param[in] _init   the initial number of elements to allocate.
 *        Pass 0 to use the default.
 */
#define fr_heap_alloc(_ctx, _cmp, _type, _field, _init) \
  _fr_heap_alloc(_ctx, _cmp, NULL, (size_t)offsetof(_type, _field), _init)

/** Creates a heap that verifies elements are of a specific talloc type
 *
 * @param[in] _ctx    Talloc ctx to allocate heap in.
 * @param[in] _cmp    Comparator used to compare elements.
 * @param[in] _talloc_type  of elements.
 * @param[in] _field    to store heap indexes in.
 * @param[in] _init   the initial number of elements to allocate.
 *        Pass 0 to use the default.
 * @return
 *  - A new heap.
 *  - NULL on error.
 */
#define fr_heap_talloc_alloc(_ctx, _cmp, _talloc_type, _field, _init) \
  _fr_heap_alloc(_ctx, _cmp, #_talloc_type, (size_t)offsetof(_talloc_type, _field), _init)
fr_heap_t *_fr_heap_alloc(TALLOC_CTX *ctx, fr_heap_cmp_t cmp, char const *talloc_type,
        size_t offset, unsigned int init) CC_HINT(nonnull(2));

/** Check if an entry is inserted into a heap
 *
 * @param[in] heap_idx from object to check.
 */
static inline bool fr_heap_entry_inserted(fr_heap_index_t heap_idx)
{
  return (heap_idx != FR_HEAP_INDEX_INVALID);
}

/** Return the item from the top of the heap but don't pop it
 *
 * @param[in] h   to return element from.
 * @return
 *  - Element at the top of the heap.
 *  - NULL if no elements remain in the heap.
 */
static inline void *fr_heap_peek(fr_heap_t *h)
{
  if (h->num_elements == 0) return NULL;

  return h->p[1];
}

/** Peek at a specific index in the heap
 *
 * @param[in] h   to return element from.
 * @param[in] idx to lookup
 * @return
 *  - Element at the top of the heap.
 *  - NULL if index outside of the range of the heap.
 */
static inline void *fr_heap_peek_at(fr_heap_t *h, fr_heap_index_t idx)
{
  if (unlikely(idx > h->num_elements)) return NULL;

  return h->p[idx];
}

/** Peek at the last element in the heap (not necessarily the bottom)
 *
 * @param[in] h   to return element from.
 * @return
 *  - Last element in the heap.
 *  - NULL if no elements remain in the heap.
 */
static inline void *fr_heap_peek_tail(fr_heap_t *h)
{
  if (h->num_elements == 0) return NULL;

  /*
   *  If this is NULL, we have a problem.
   */
  return h->p[h->num_elements];
}

/** Return the number of elements in the heap
 *
 * @param[in] h   to return the number of elements from.
 */
static inline unsigned int fr_heap_num_elements(fr_heap_t *h)
{
  return h->num_elements;
}

int   fr_heap_insert(fr_heap_t **hp, void *data) CC_HINT(nonnull);
int   fr_heap_extract(fr_heap_t **hp, void *data) CC_HINT(nonnull);
void    *fr_heap_pop(fr_heap_t **hp) CC_HINT(nonnull);

void    *fr_heap_iter_init(fr_heap_t *hp, fr_heap_iter_t *iter) CC_HINT(nonnull);
void    *fr_heap_iter_next(fr_heap_t *hp, fr_heap_iter_t *iter) CC_HINT(nonnull);

/** Iterate over the contents of a heap
 *
 * @note The initializer section of a for loop can't declare variables with distinct
 *   base types, so we require a containing block, and can't follow the standard
 *   do {...} while(0) dodge. The code to be run for each item in the heap should
 *   thus start with one open brace and end with two close braces, and shouldn't
 *   be followed with a semicolon.
 *   This may fake out code formatting programs and code-aware editors.
 *
 * @param[in] _heap   to iterate over.
 * @param[in] _type   of item the heap contains.
 * @param[in] _data   Name of variable holding a pointer to the heap element.
 *        Will be declared in the scope of the loop.
 */
#define fr_heap_foreach(_heap, _type, _data) \
{ \
  fr_heap_iter_t _iter; \
  for (_type *_data = fr_heap_iter_init(_heap, &_iter); _data; _data = fr_heap_iter_next(_heap, &_iter))

#ifndef TALLOC_GET_TYPE_ABORT_NOOP
void fr_heap_verify(char const *file, int line, fr_heap_t *hp);
#  define FR_HEAP_VERIFY(_heap) fr_heap_verify(__FILE__, __LINE__, _heap)
#elif !defined(NDEBUG)
#  define FR_HEAP_VERIFY(_heap) fr_assert(_heap)
#else
#  define FR_HEAP_VERIFY(_heap)
#endif

#undef _CONST
#ifdef __cplusplus
}
#endif

Coverage Report

Created: 2024-08-28 06:17

Line	Count	Source (jump to first uncovered line)
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		*/
24		RCSIDH(heap_h, "$Id: 5c615f0e4fee73795140048ce5b2eac2f3fd941f $")
25
26		#ifdef __cplusplus
27		extern "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		*/
54		typedef 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		*/
66		typedef 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
80		typedef unsigned int fr_heap_index_t;
81		typedef unsigned int fr_heap_iter_t;
82
83	0	#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
89		size_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)
117		fr_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		*/
124		static inline bool fr_heap_entry_inserted(fr_heap_index_t heap_idx)
125	0	{
126	0	return (heap_idx != FR_HEAP_INDEX_INVALID);
127	0	} Unexecuted instantiation: fuzzer_tacacs.c:fr_heap_entry_inserted Unexecuted instantiation: fuzzer_vmps.c:fr_heap_entry_inserted Unexecuted instantiation: fuzzer_tftp.c:fr_heap_entry_inserted Unexecuted instantiation: fuzzer_dns.c:fr_heap_entry_inserted Unexecuted instantiation: fuzzer_dhcpv6.c:fr_heap_entry_inserted Unexecuted instantiation: fuzzer_radius.c:fr_heap_entry_inserted Unexecuted instantiation: fuzzer_util.c:fr_heap_entry_inserted Unexecuted instantiation: fuzzer_dhcpv4.c:fr_heap_entry_inserted Unexecuted instantiation: fuzzer_bfd.c:fr_heap_entry_inserted Unexecuted instantiation: decode.c:fr_heap_entry_inserted Unexecuted instantiation: dl.c:fr_heap_entry_inserted Unexecuted instantiation: encode.c:fr_heap_entry_inserted Unexecuted instantiation: heap.c:fr_heap_entry_inserted Unexecuted instantiation: struct.c:fr_heap_entry_inserted Unexecuted instantiation: fuzzer.c:fr_heap_entry_inserted Unexecuted instantiation: vmps.c:fr_heap_entry_inserted Unexecuted instantiation: base.c:fr_heap_entry_inserted
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		*/
136		static inline void fr_heap_peek(fr_heap_t h)
137	0	{
138	0	if (h->num_elements == 0) return NULL;
139	0
140	0	return h->p[1];
141	0	} Unexecuted instantiation: fuzzer_tacacs.c:fr_heap_peek Unexecuted instantiation: fuzzer_vmps.c:fr_heap_peek Unexecuted instantiation: fuzzer_tftp.c:fr_heap_peek Unexecuted instantiation: fuzzer_dns.c:fr_heap_peek Unexecuted instantiation: fuzzer_dhcpv6.c:fr_heap_peek Unexecuted instantiation: fuzzer_radius.c:fr_heap_peek Unexecuted instantiation: fuzzer_util.c:fr_heap_peek Unexecuted instantiation: fuzzer_dhcpv4.c:fr_heap_peek Unexecuted instantiation: fuzzer_bfd.c:fr_heap_peek Unexecuted instantiation: decode.c:fr_heap_peek Unexecuted instantiation: dl.c:fr_heap_peek Unexecuted instantiation: encode.c:fr_heap_peek Unexecuted instantiation: heap.c:fr_heap_peek Unexecuted instantiation: struct.c:fr_heap_peek Unexecuted instantiation: fuzzer.c:fr_heap_peek Unexecuted instantiation: vmps.c:fr_heap_peek Unexecuted instantiation: base.c:fr_heap_peek
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		*/
151		static inline void fr_heap_peek_at(fr_heap_t h, fr_heap_index_t idx)
152	0	{
153	0	if (unlikely(idx > h->num_elements)) return NULL;
154	0
155	0	return h->p[idx];
156	0	} Unexecuted instantiation: fuzzer_tacacs.c:fr_heap_peek_at Unexecuted instantiation: fuzzer_vmps.c:fr_heap_peek_at Unexecuted instantiation: fuzzer_tftp.c:fr_heap_peek_at Unexecuted instantiation: fuzzer_dns.c:fr_heap_peek_at Unexecuted instantiation: fuzzer_dhcpv6.c:fr_heap_peek_at Unexecuted instantiation: fuzzer_radius.c:fr_heap_peek_at Unexecuted instantiation: fuzzer_util.c:fr_heap_peek_at Unexecuted instantiation: fuzzer_dhcpv4.c:fr_heap_peek_at Unexecuted instantiation: fuzzer_bfd.c:fr_heap_peek_at Unexecuted instantiation: decode.c:fr_heap_peek_at Unexecuted instantiation: dl.c:fr_heap_peek_at Unexecuted instantiation: encode.c:fr_heap_peek_at Unexecuted instantiation: heap.c:fr_heap_peek_at Unexecuted instantiation: struct.c:fr_heap_peek_at Unexecuted instantiation: fuzzer.c:fr_heap_peek_at Unexecuted instantiation: vmps.c:fr_heap_peek_at Unexecuted instantiation: base.c:fr_heap_peek_at
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		*/
165		static inline void fr_heap_peek_tail(fr_heap_t h)
166	0	{
167	0	if (h->num_elements == 0) return NULL;
168	0
169	0	/*
170	0	* If this is NULL, we have a problem.
171	0	*/
172	0	return h->p[h->num_elements];
173	0	} Unexecuted instantiation: fuzzer_tacacs.c:fr_heap_peek_tail Unexecuted instantiation: fuzzer_vmps.c:fr_heap_peek_tail Unexecuted instantiation: fuzzer_tftp.c:fr_heap_peek_tail Unexecuted instantiation: fuzzer_dns.c:fr_heap_peek_tail Unexecuted instantiation: fuzzer_dhcpv6.c:fr_heap_peek_tail Unexecuted instantiation: fuzzer_radius.c:fr_heap_peek_tail Unexecuted instantiation: fuzzer_util.c:fr_heap_peek_tail Unexecuted instantiation: fuzzer_dhcpv4.c:fr_heap_peek_tail Unexecuted instantiation: fuzzer_bfd.c:fr_heap_peek_tail Unexecuted instantiation: decode.c:fr_heap_peek_tail Unexecuted instantiation: dl.c:fr_heap_peek_tail Unexecuted instantiation: encode.c:fr_heap_peek_tail Unexecuted instantiation: heap.c:fr_heap_peek_tail Unexecuted instantiation: struct.c:fr_heap_peek_tail Unexecuted instantiation: fuzzer.c:fr_heap_peek_tail Unexecuted instantiation: vmps.c:fr_heap_peek_tail Unexecuted instantiation: base.c:fr_heap_peek_tail
174
175		/** Return the number of elements in the heap
176		*
177		* @param[in] h to return the number of elements from.
178		*/
179		static inline unsigned int fr_heap_num_elements(fr_heap_t *h)
180	0	{
181	0	return h->num_elements;
182	0	} Unexecuted instantiation: fuzzer_tacacs.c:fr_heap_num_elements Unexecuted instantiation: fuzzer_vmps.c:fr_heap_num_elements Unexecuted instantiation: fuzzer_tftp.c:fr_heap_num_elements Unexecuted instantiation: fuzzer_dns.c:fr_heap_num_elements Unexecuted instantiation: fuzzer_dhcpv6.c:fr_heap_num_elements Unexecuted instantiation: fuzzer_radius.c:fr_heap_num_elements Unexecuted instantiation: fuzzer_util.c:fr_heap_num_elements Unexecuted instantiation: fuzzer_dhcpv4.c:fr_heap_num_elements Unexecuted instantiation: fuzzer_bfd.c:fr_heap_num_elements Unexecuted instantiation: decode.c:fr_heap_num_elements Unexecuted instantiation: dl.c:fr_heap_num_elements Unexecuted instantiation: encode.c:fr_heap_num_elements Unexecuted instantiation: heap.c:fr_heap_num_elements Unexecuted instantiation: struct.c:fr_heap_num_elements Unexecuted instantiation: fuzzer.c:fr_heap_num_elements Unexecuted instantiation: vmps.c:fr_heap_num_elements Unexecuted instantiation: base.c:fr_heap_num_elements
183
184		int fr_heap_insert(fr_heap_t *hp, void data) CC_HINT(nonnull);
185		int fr_heap_extract(fr_heap_t *hp, void data) CC_HINT(nonnull);
186		void fr_heap_pop(fr_heap_t *hp) CC_HINT(nonnull);
187
188		void fr_heap_iter_init(fr_heap_t hp, fr_heap_iter_t *iter) CC_HINT(nonnull);
189		void 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
211		void 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