Wed Jan 8 2020 09:49:48

Asterisk developer's documentation


heap.h
Go to the documentation of this file.
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 2009, Digium, Inc.
5  *
6  * Russell Bryant <russell@digium.com>
7  *
8  * See http://www.asterisk.org for more information about
9  * the Asterisk project. Please do not directly contact
10  * any of the maintainers of this project for assistance;
11  * the project provides a web site, mailing lists and IRC
12  * channels for your use.
13  *
14  * This program is free software, distributed under the terms of
15  * the GNU General Public License Version 2. See the LICENSE file
16  * at the top of the source tree.
17  */
18 
19 /*!
20  * \file
21  * \brief Max Heap data structure
22  * \author Russell Bryant <russell@digium.com>
23  */
24 
25 #ifndef __AST_HEAP_H__
26 #define __AST_HEAP_H__
27 
28 /*!
29  * \brief A max heap.
30  *
31  * \note Thread-safety is left to the user of the API. The heap API provides
32  * no locking of its own. If the heap will be accessed by multiple threads,
33  * then a lock must be used to ensure that only a single operation is
34  * done on the heap at a time. For the sake of convenience, a lock is
35  * provided for the user of the API to use if another lock is not already
36  * available to protect the heap.
37  */
38 struct ast_heap;
39 
40 /*!
41  * \brief Function type for comparing nodes in a heap
42  *
43  * \param elm1 the first element
44  * \param elm2 the second element
45  *
46  * \retval negative if elm1 < elm2
47  * \retval 0 if elm1 == elm2
48  * \retval positive if elm1 > elm2
49  *
50  * \note This implementation is of a max heap. However, if a min heap is
51  * desired, simply swap the return values of this function.
52  *
53  * \since 1.6.1
54  */
55 typedef int (*ast_heap_cmp_fn)(void *elm1, void *elm2);
56 
57 /*!
58  * \brief Create a max heap
59  *
60  * \param init_height The initial height of the heap to allocate space for.
61  * To start out, there will be room for (2 ^ init_height) - 1 entries.
62  * However, the heap will grow as needed.
63  * \param cmp_fn The function that should be used to compare elements in the heap.
64  * \param index_offset This parameter is optional, but must be provided to be able
65  * to use ast_heap_remove(). This is the number of bytes into the element
66  * where an ssize_t has been made available for the heap's internal
67  * use. The heap will use this field to keep track of the element's current
68  * position in the heap. The offsetof() macro is useful for providing a
69  * proper value for this argument. If ast_heap_remove() will not be used,
70  * then a negative value can be provided to indicate that no field for an
71  * offset has been allocated.
72  *
73  * Example Usage:
74  *
75  * \code
76  *
77  * struct myobj {
78  * int foo;
79  * int bar;
80  * char stuff[8];
81  * char things[8];
82  * ssize_t __heap_index;
83  * };
84  *
85  * ...
86  *
87  * static int myobj_cmp(void *obj1, void *obj2);
88  *
89  * ...
90  *
91  * struct ast_heap *h;
92  *
93  * h = ast_heap_create(8, myobj_cmp, offsetof(struct myobj, __heap_index));
94  *
95  * \endcode
96  *
97  * \return An instance of a max heap
98  * \since 1.6.1
99  */
100 #ifdef MALLOC_DEBUG
101 struct ast_heap *_ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn,
102  ssize_t index_offset, const char *file, int lineno, const char *func);
103 #define ast_heap_create(a,b,c) _ast_heap_create(a,b,c,__FILE__,__LINE__,__PRETTY_FUNCTION__)
104 #else
105 struct ast_heap *ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn,
106  ssize_t index_offset);
107 #endif
108 
109 /*!
110  * \brief Destroy a max heap
111  *
112  * \param h the heap to destroy
113  *
114  * \return NULL for convenience
115  * \since 1.6.1
116  */
117 struct ast_heap *ast_heap_destroy(struct ast_heap *h);
118 
119 /*!
120  * \brief Push an element on to a heap
121  *
122  * \param h the heap being added to
123  * \param elm the element being put on the heap
124  *
125  * \retval 0 success
126  * \retval non-zero failure
127  * \since 1.6.1
128  */
129 #ifdef MALLOC_DEBUG
130 int _ast_heap_push(struct ast_heap *h, void *elm, const char *file, int lineno, const char *func);
131 #define ast_heap_push(a,b) _ast_heap_push(a,b,__FILE__,__LINE__,__PRETTY_FUNCTION__)
132 #else
133 int ast_heap_push(struct ast_heap *h, void *elm);
134 #endif
135 
136 /*!
137  * \brief Pop the max element off of the heap
138  *
139  * \param h the heap
140  *
141  * \return this will return the element on the top of the heap, which has the
142  * largest value according to the element comparison function that was
143  * provided when the heap was created. The element will be removed before
144  * being returned.
145  * \since 1.6.1
146  */
147 void *ast_heap_pop(struct ast_heap *h);
148 
149 /*!
150  * \brief Remove a specific element from a heap
151  *
152  * \param h the heap to remove from
153  * \param elm the element to remove
154  *
155  * \return elm, if the removal was successful, or NULL if it failed
156  *
157  * \note the index_offset parameter to ast_heap_create() is required to be able
158  * to use this function.
159  * \since 1.6.1
160  */
161 void *ast_heap_remove(struct ast_heap *h, void *elm);
162 
163 /*!
164  * \brief Peek at an element on a heap
165  *
166  * \param h the heap
167  * \param index index of the element to return. The first element is at index 1,
168  * and the last element is at the index == the size of the heap.
169  *
170  * \return an element at the specified index on the heap. This element will \b not
171  * be removed before being returned.
172  *
173  * \note If this function is being used in combination with ast_heap_size() for
174  * purposes of traversing the heap, the heap must be locked for the entire
175  * duration of the traversal.
176  *
177  * Example code for a traversal:
178  * \code
179  *
180  * struct ast_heap *h;
181  *
182  * ...
183  *
184  * size_t size, i;
185  * void *cur_obj;
186  *
187  * ast_heap_rdlock(h);
188  *
189  * size = ast_heap_size(h);
190  *
191  * for (i = 1; i <= size && (cur_obj = ast_heap_peek(h, i)); i++) {
192  * ... Do stuff with cur_obj ...
193  * }
194  *
195  * ast_heap_unlock(h);
196  *
197  * \endcode
198  * \since 1.6.1
199  */
200 void *ast_heap_peek(struct ast_heap *h, unsigned int index);
201 
202 /*!
203  * \brief Get the current size of a heap
204  *
205  * \param h the heap
206  *
207  * \return the number of elements currently in the heap
208  * \since 1.6.1
209  */
210 size_t ast_heap_size(struct ast_heap *h);
211 
212 /*!
213  * \brief Write-Lock a heap
214  *
215  * \param h the heap
216  *
217  * A lock is provided for convenience. It can be assumed that none of the
218  * ast_heap API calls are thread safe. This lock does not have to be used
219  * if another one is already available to protect the heap.
220  *
221  * \return see the documentation for pthread_rwlock_wrlock()
222  * \since 1.6.1
223  */
224 int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line);
225 
226 /*!
227  * \brief Read-Lock a heap
228  *
229  * \param h the heap
230  *
231  * A lock is provided for convenience. It can be assumed that none of the
232  * ast_heap API calls are thread safe. This lock does not have to be used
233  * if another one is already available to protect the heap.
234  *
235  * \return see the documentation for pthread_rwlock_rdlock()
236  * \since 1.6.1
237  */
238 int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line);
239 
240 /*!
241  * \brief Unlock a heap
242  *
243  * \param h the heap
244  *
245  * \return see the documentation for pthread_rwlock_unlock()
246  * \since 1.6.1
247  */
248 int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line);
249 
250 #define ast_heap_wrlock(h) __ast_heap_wrlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)
251 #define ast_heap_rdlock(h) __ast_heap_rdlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)
252 #define ast_heap_unlock(h) __ast_heap_unlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)
253 
254 /*!
255  * \brief Verify that a heap has been properly constructed
256  *
257  * \param h a heap
258  *
259  * \retval 0 success
260  * \retval non-zero failure
261  *
262  * \note This function is mostly for debugging purposes. It traverses an existing
263  * heap and verifies that every node is properly placed relative to its children.
264  * \since 1.6.1
265  */
266 int ast_heap_verify(struct ast_heap *h);
267 
268 #endif /* __AST_HEAP_H__ */
ast_heap_cmp_fn cmp_fn
Definition: heap.c:40
int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line)
Write-Lock a heap.
Definition: heap.c:314
int ast_heap_push(struct ast_heap *h, void *elm)
Push an element on to a heap.
Definition: heap.c:250
Definition: heap.c:38
struct ast_heap * ast_heap_destroy(struct ast_heap *h)
Destroy a max heap.
Definition: heap.c:163
void * ast_heap_pop(struct ast_heap *h)
Pop the max element off of the heap.
Definition: heap.c:295
int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line)
Unlock a heap.
Definition: heap.c:324
int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line)
Read-Lock a heap.
Definition: heap.c:319
int(* ast_heap_cmp_fn)(void *elm1, void *elm2)
Function type for comparing nodes in a heap.
Definition: heap.h:55
void * ast_heap_remove(struct ast_heap *h, void *elm)
Remove a specific element from a heap.
Definition: heap.c:284
size_t ast_heap_size(struct ast_heap *h)
Get the current size of a heap.
Definition: heap.c:309
struct ast_heap * ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn, ssize_t index_offset)
Create a max heap.
Definition: heap.c:118
void * ast_heap_peek(struct ast_heap *h, unsigned int index)
Peek at an element on a heap.
Definition: heap.c:300
ssize_t index_offset
Definition: heap.c:41
int ast_heap_verify(struct ast_heap *h)
Verify that a heap has been properly constructed.
Definition: heap.c:90