Asterisk - The Open Source Telephony Project  GIT-master-a24979a
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 #define ast_heap_create(init_height, cmp_fn, index_offset) \
101  _ast_heap_create(init_height, cmp_fn, index_offset, __FILE__, __LINE__, __PRETTY_FUNCTION__)
102 struct 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  */
113 struct 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__)
127 int _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  */
140 void *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  */
155 void *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  */
194 void *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  */
204 size_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  */
219 int __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  */
234 int __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  */
245 int __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  */
263 int 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
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
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_rdlock(struct ast_heap *h, const char *file, const char *func, int line)
Read-Lock a heap.
Definition: heap.c:286
void * ast_heap_peek(struct ast_heap *h, unsigned int index)
Peek at an element on a heap.
Definition: heap.c:267
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
void * ast_heap_remove(struct ast_heap *h, void *elm)
Remove a specific element from a heap.
Definition: heap.c:251
int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line)
Write-Lock a heap.
Definition: heap.c:281
void * ast_heap_pop(struct ast_heap *h)
Pop the max element off of the heap.
Definition: heap.c:262
int _ast_heap_push(struct ast_heap *h, void *elm, const char *file, int lineno, const char *func)
Definition: heap.c:222
Definition: heap.c:36
ssize_t index_offset
Definition: heap.c:39
ast_heap_cmp_fn cmp_fn
Definition: heap.c:38