Asterisk - The Open Source Telephony Project GIT-master-0bf3178
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 */
38struct 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 */
55typedef 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#define ast_heap_create(init_height, cmp_fn, index_offset) \
101 _ast_heap_create(init_height, cmp_fn, index_offset, __FILE__, __LINE__, __PRETTY_FUNCTION__)
102struct ast_heap *_ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn,
103 ssize_t index_offset, const char *file, int lineno, const char *func);
104
105/*!
106 * \brief Destroy a max heap
107 *
108 * \param h the heap to destroy
109 *
110 * \retval NULL for convenience
111 * \since 1.6.1
112 */
113struct ast_heap *ast_heap_destroy(struct ast_heap *h);
114
115/*!
116 * \brief Push an element on to a heap
117 *
118 * \param h the heap being added to
119 * \param elm the element being put on the heap
120 *
121 * \retval 0 success
122 * \retval non-zero failure
123 * \since 1.6.1
124 */
125#define ast_heap_push(h, elm) \
126 _ast_heap_push(h, elm, __FILE__, __LINE__, __PRETTY_FUNCTION__)
127int _ast_heap_push(struct ast_heap *h, void *elm, const char *file, int lineno, const char *func);
128
129/*!
130 * \brief Pop the max element off of the heap
131 *
132 * \param h the heap
133 *
134 * \return this will return the element on the top of the heap, which has the
135 * largest value according to the element comparison function that was
136 * provided when the heap was created. The element will be removed before
137 * being returned.
138 * \since 1.6.1
139 */
140void *ast_heap_pop(struct ast_heap *h);
141
142/*!
143 * \brief Remove a specific element from a heap
144 *
145 * \param h the heap to remove from
146 * \param elm the element to remove
147 *
148 * \return elm, if the removal was successful
149 * \retval NULL if it failed
150 *
151 * \note the index_offset parameter to ast_heap_create() is required to be able
152 * to use this function.
153 * \since 1.6.1
154 */
155void *ast_heap_remove(struct ast_heap *h, void *elm);
156
157/*!
158 * \brief Peek at an element on a heap
159 *
160 * \param h the heap
161 * \param index index of the element to return. The first element is at index 1,
162 * and the last element is at the index == the size of the heap.
163 *
164 * \return an element at the specified index on the heap. This element will \b not
165 * be removed before being returned.
166 *
167 * \note If this function is being used in combination with ast_heap_size() for
168 * purposes of traversing the heap, the heap must be locked for the entire
169 * duration of the traversal.
170 *
171 * Example code for a traversal:
172 * \code
173 *
174 * struct ast_heap *h;
175 *
176 * ...
177 *
178 * size_t size, i;
179 * void *cur_obj;
180 *
181 * ast_heap_rdlock(h);
182 *
183 * size = ast_heap_size(h);
184 *
185 * for (i = 1; i <= size && (cur_obj = ast_heap_peek(h, i)); i++) {
186 * ... Do stuff with cur_obj ...
187 * }
188 *
189 * ast_heap_unlock(h);
190 *
191 * \endcode
192 * \since 1.6.1
193 */
194void *ast_heap_peek(struct ast_heap *h, unsigned int index);
195
196/*!
197 * \brief Get the current size of a heap
198 *
199 * \param h the heap
200 *
201 * \return the number of elements currently in the heap
202 * \since 1.6.1
203 */
204size_t ast_heap_size(struct ast_heap *h);
205
206/*!
207 * \brief Write-Lock a heap
208 *
209 * \param h the heap
210 * \param file, func, line
211 *
212 * A lock is provided for convenience. It can be assumed that none of the
213 * ast_heap API calls are thread safe. This lock does not have to be used
214 * if another one is already available to protect the heap.
215 *
216 * \return see the documentation for pthread_rwlock_wrlock()
217 * \since 1.6.1
218 */
219int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line);
220
221/*!
222 * \brief Read-Lock a heap
223 *
224 * \param h the heap
225 * \param file, func, line
226 *
227 * A lock is provided for convenience. It can be assumed that none of the
228 * ast_heap API calls are thread safe. This lock does not have to be used
229 * if another one is already available to protect the heap.
230 *
231 * \return see the documentation for pthread_rwlock_rdlock()
232 * \since 1.6.1
233 */
234int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line);
235
236/*!
237 * \brief Unlock a heap
238 *
239 * \param h the heap
240 * \param file, func, line
241 *
242 * \return see the documentation for pthread_rwlock_unlock()
243 * \since 1.6.1
244 */
245int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line);
246
247#define ast_heap_wrlock(h) __ast_heap_wrlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)
248#define ast_heap_rdlock(h) __ast_heap_rdlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)
249#define ast_heap_unlock(h) __ast_heap_unlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)
250
251/*!
252 * \brief Verify that a heap has been properly constructed
253 *
254 * \param h a heap
255 *
256 * \retval 0 success
257 * \retval non-zero failure
258 *
259 * \note This function is mostly for debugging purposes. It traverses an existing
260 * heap and verifies that every node is properly placed relative to its children.
261 * \since 1.6.1
262 */
263int ast_heap_verify(struct ast_heap *h);
264
265#endif /* __AST_HEAP_H__ */
int ast_heap_verify(struct ast_heap *h)
Verify that a heap has been properly constructed.
Definition: heap.c:88
struct ast_heap * _ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn, ssize_t index_offset, const char *file, int lineno, const char *func)
Definition: heap.c:112
int(* ast_heap_cmp_fn)(void *elm1, void *elm2)
Function type for comparing nodes in a heap.
Definition: heap.h:55
struct ast_heap * ast_heap_destroy(struct ast_heap *h)
Destroy a max heap.
Definition: heap.c:146
void * ast_heap_pop(struct ast_heap *h)
Pop the max element off of the heap.
Definition: heap.c:262
void * ast_heap_remove(struct ast_heap *h, void *elm)
Remove a specific element from a heap.
Definition: heap.c:251
int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line)
Read-Lock a heap.
Definition: heap.c:286
int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line)
Unlock a heap.
Definition: heap.c:291
size_t ast_heap_size(struct ast_heap *h)
Get the current size of a heap.
Definition: heap.c:276
int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line)
Write-Lock a heap.
Definition: heap.c:281
int _ast_heap_push(struct ast_heap *h, void *elm, const char *file, int lineno, const char *func)
Definition: heap.c:222
void * ast_heap_peek(struct ast_heap *h, unsigned int index)
Peek at an element on a heap.
Definition: heap.c:267
Definition: heap.c:36
ssize_t index_offset
Definition: heap.c:39
ast_heap_cmp_fn cmp_fn
Definition: heap.c:38