core: Remove ABI effects of MALLOC_DEBUG.
[asterisk/asterisk.git] / include / asterisk / heap.h
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 struct ast_heap *_ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn,
101                 ssize_t index_offset, const char *file, int lineno, const char *func);
102 #define ast_heap_create(init_height, cmp_fn, index_offset) \
103         _ast_heap_create(init_height, cmp_fn, index_offset, __FILE__, __LINE__, __PRETTY_FUNCTION__)
104
105 /*!
106  * \brief Destroy a max heap
107  *
108  * \param h the heap to destroy
109  *
110  * \return 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 int _ast_heap_push(struct ast_heap *h, void *elm, const char *file, int lineno, const char *func);
126 #define ast_heap_push(h, elm) \
127         _ast_heap_push(h, elm, __FILE__, __LINE__, __PRETTY_FUNCTION__)
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, or NULL if it failed
149  *
150  * \note the index_offset parameter to ast_heap_create() is required to be able
151  *       to use this function.
152  * \since 1.6.1
153  */
154 void *ast_heap_remove(struct ast_heap *h, void *elm);
155
156 /*!
157  * \brief Peek at an element on a heap
158  *
159  * \param h the heap
160  * \param index index of the element to return.  The first element is at index 1,
161  *        and the last element is at the index == the size of the heap.
162  *
163  * \return an element at the specified index on the heap.  This element will \b not
164  *         be removed before being returned.
165  *
166  * \note If this function is being used in combination with ast_heap_size() for
167  *       purposes of traversing the heap, the heap must be locked for the entire
168  *       duration of the traversal.
169  *
170  * Example code for a traversal:
171  * \code
172  *
173  * struct ast_heap *h;
174  *
175  * ...
176  *
177  * size_t size, i;
178  * void *cur_obj;
179  *
180  * ast_heap_rdlock(h);
181  *
182  * size = ast_heap_size(h);
183  *
184  * for (i = 1; i <= size && (cur_obj = ast_heap_peek(h, i)); i++) {
185  *     ... Do stuff with cur_obj ...
186  * }
187  *
188  * ast_heap_unlock(h);
189  *
190  * \endcode
191  * \since 1.6.1
192  */
193 void *ast_heap_peek(struct ast_heap *h, unsigned int index);
194
195 /*!
196  * \brief Get the current size of a heap
197  *
198  * \param h the heap
199  *
200  * \return the number of elements currently in the heap
201  * \since 1.6.1
202  */
203 size_t ast_heap_size(struct ast_heap *h);
204
205 /*!
206  * \brief Write-Lock a heap
207  *
208  * \param h the heap
209  * \param file, func, line
210  *
211  * A lock is provided for convenience.  It can be assumed that none of the
212  * ast_heap API calls are thread safe.  This lock does not have to be used
213  * if another one is already available to protect the heap.
214  *
215  * \return see the documentation for pthread_rwlock_wrlock()
216  * \since 1.6.1
217  */
218 int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line);
219
220 /*!
221  * \brief Read-Lock a heap
222  *
223  * \param h the heap
224  * \param file, func, line
225  *
226  * A lock is provided for convenience.  It can be assumed that none of the
227  * ast_heap API calls are thread safe.  This lock does not have to be used
228  * if another one is already available to protect the heap.
229  *
230  * \return see the documentation for pthread_rwlock_rdlock()
231  * \since 1.6.1
232  */
233 int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line);
234
235 /*!
236  * \brief Unlock a heap
237  *
238  * \param h the heap
239  * \param file, func, line
240  *
241  * \return see the documentation for pthread_rwlock_unlock()
242  * \since 1.6.1
243  */
244 int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line);
245
246 #define ast_heap_wrlock(h) __ast_heap_wrlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)
247 #define ast_heap_rdlock(h) __ast_heap_rdlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)
248 #define ast_heap_unlock(h) __ast_heap_unlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)
249
250 /*!
251  * \brief Verify that a heap has been properly constructed
252  *
253  * \param h a heap
254  *
255  * \retval 0 success
256  * \retval non-zero failure
257  *
258  * \note This function is mostly for debugging purposes.  It traverses an existing
259  *       heap and verifies that every node is properly placed relative to its children.
260  * \since 1.6.1
261  */
262 int ast_heap_verify(struct ast_heap *h);
263
264 #endif /* __AST_HEAP_H__ */