00001 /* 00002 * Asterisk -- An open source telephony toolkit. 00003 * 00004 * Copyright (C) 2009, Digium, Inc. 00005 * 00006 * Russell Bryant <russell@digium.com> 00007 * 00008 * See http://www.asterisk.org for more information about 00009 * the Asterisk project. Please do not directly contact 00010 * any of the maintainers of this project for assistance; 00011 * the project provides a web site, mailing lists and IRC 00012 * channels for your use. 00013 * 00014 * This program is free software, distributed under the terms of 00015 * the GNU General Public License Version 2. See the LICENSE file 00016 * at the top of the source tree. 00017 */ 00018 00019 /*! 00020 * \file 00021 * \brief Max Heap data structure 00022 * \author Russell Bryant <russell@digium.com> 00023 */ 00024 00025 #ifndef __AST_HEAP_H__ 00026 #define __AST_HEAP_H__ 00027 00028 /*! 00029 * \brief A max heap. 00030 * 00031 * \note Thread-safety is left to the user of the API. The heap API provides 00032 * no locking of its own. If the heap will be accessed by multiple threads, 00033 * then a lock must be used to ensure that only a single operation is 00034 * done on the heap at a time. For the sake of convenience, a lock is 00035 * provided for the user of the API to use if another lock is not already 00036 * available to protect the heap. 00037 */ 00038 struct ast_heap; 00039 00040 /*! 00041 * \brief Function type for comparing nodes in a heap 00042 * 00043 * \param elm1 the first element 00044 * \param elm2 the second element 00045 * 00046 * \retval negative if elm1 < elm2 00047 * \retval 0 if elm1 == elm2 00048 * \retval positive if elm1 > elm2 00049 * 00050 * \note This implementation is of a max heap. However, if a min heap is 00051 * desired, simply swap the return values of this function. 00052 * 00053 * \since 1.6.1 00054 */ 00055 typedef int (*ast_heap_cmp_fn)(void *elm1, void *elm2); 00056 00057 /*! 00058 * \brief Create a max heap 00059 * 00060 * \param init_height The initial height of the heap to allocate space for. 00061 * To start out, there will be room for (2 ^ init_height) - 1 entries. 00062 * However, the heap will grow as needed. 00063 * \param cmp_fn The function that should be used to compare elements in the heap. 00064 * \param index_offset This parameter is optional, but must be provided to be able 00065 * to use ast_heap_remove(). This is the number of bytes into the element 00066 * where an ssize_t has been made available for the heap's internal 00067 * use. The heap will use this field to keep track of the element's current 00068 * position in the heap. The offsetof() macro is useful for providing a 00069 * proper value for this argument. If ast_heap_remove() will not be used, 00070 * then a negative value can be provided to indicate that no field for an 00071 * offset has been allocated. 00072 * 00073 * Example Usage: 00074 * 00075 * \code 00076 * 00077 * struct myobj { 00078 * int foo; 00079 * int bar; 00080 * char stuff[8]; 00081 * char things[8]; 00082 * ssize_t __heap_index; 00083 * }; 00084 * 00085 * ... 00086 * 00087 * static int myobj_cmp(void *obj1, void *obj2); 00088 * 00089 * ... 00090 * 00091 * struct ast_heap *h; 00092 * 00093 * h = ast_heap_create(8, myobj_cmp, offsetof(struct myobj, __heap_index)); 00094 * 00095 * \endcode 00096 * 00097 * \return An instance of a max heap 00098 * \since 1.6.1 00099 */ 00100 #ifdef MALLOC_DEBUG 00101 struct ast_heap *_ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn, 00102 ssize_t index_offset, const char *file, int lineno, const char *func); 00103 #define ast_heap_create(a,b,c) _ast_heap_create(a,b,c,__FILE__,__LINE__,__PRETTY_FUNCTION__) 00104 #else 00105 struct ast_heap *ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn, 00106 ssize_t index_offset); 00107 #endif 00108 00109 /*! 00110 * \brief Destroy a max heap 00111 * 00112 * \param h the heap to destroy 00113 * 00114 * \return NULL for convenience 00115 * \since 1.6.1 00116 */ 00117 struct ast_heap *ast_heap_destroy(struct ast_heap *h); 00118 00119 /*! 00120 * \brief Push an element on to a heap 00121 * 00122 * \param h the heap being added to 00123 * \param elm the element being put on the heap 00124 * 00125 * \retval 0 success 00126 * \retval non-zero failure 00127 * \since 1.6.1 00128 */ 00129 #ifdef MALLOC_DEBUG 00130 int _ast_heap_push(struct ast_heap *h, void *elm, const char *file, int lineno, const char *func); 00131 #define ast_heap_push(a,b) _ast_heap_push(a,b,__FILE__,__LINE__,__PRETTY_FUNCTION__) 00132 #else 00133 int ast_heap_push(struct ast_heap *h, void *elm); 00134 #endif 00135 00136 /*! 00137 * \brief Pop the max element off of the heap 00138 * 00139 * \param h the heap 00140 * 00141 * \return this will return the element on the top of the heap, which has the 00142 * largest value according to the element comparison function that was 00143 * provided when the heap was created. The element will be removed before 00144 * being returned. 00145 * \since 1.6.1 00146 */ 00147 void *ast_heap_pop(struct ast_heap *h); 00148 00149 /*! 00150 * \brief Remove a specific element from a heap 00151 * 00152 * \param h the heap to remove from 00153 * \param elm the element to remove 00154 * 00155 * \return elm, if the removal was successful, or NULL if it failed 00156 * 00157 * \note the index_offset parameter to ast_heap_create() is required to be able 00158 * to use this function. 00159 * \since 1.6.1 00160 */ 00161 void *ast_heap_remove(struct ast_heap *h, void *elm); 00162 00163 /*! 00164 * \brief Peek at an element on a heap 00165 * 00166 * \param h the heap 00167 * \param index index of the element to return. The first element is at index 1, 00168 * and the last element is at the index == the size of the heap. 00169 * 00170 * \return an element at the specified index on the heap. This element will \b not 00171 * be removed before being returned. 00172 * 00173 * \note If this function is being used in combination with ast_heap_size() for 00174 * purposes of traversing the heap, the heap must be locked for the entire 00175 * duration of the traversal. 00176 * 00177 * Example code for a traversal: 00178 * \code 00179 * 00180 * struct ast_heap *h; 00181 * 00182 * ... 00183 * 00184 * size_t size, i; 00185 * void *cur_obj; 00186 * 00187 * ast_heap_rdlock(h); 00188 * 00189 * size = ast_heap_size(h); 00190 * 00191 * for (i = 1; i <= size && (cur_obj = ast_heap_peek(h, i)); i++) { 00192 * ... Do stuff with cur_obj ... 00193 * } 00194 * 00195 * ast_heap_unlock(h); 00196 * 00197 * \endcode 00198 * \since 1.6.1 00199 */ 00200 void *ast_heap_peek(struct ast_heap *h, unsigned int index); 00201 00202 /*! 00203 * \brief Get the current size of a heap 00204 * 00205 * \param h the heap 00206 * 00207 * \return the number of elements currently in the heap 00208 * \since 1.6.1 00209 */ 00210 size_t ast_heap_size(struct ast_heap *h); 00211 00212 /*! 00213 * \brief Write-Lock a heap 00214 * 00215 * \param h the heap 00216 * 00217 * A lock is provided for convenience. It can be assumed that none of the 00218 * ast_heap API calls are thread safe. This lock does not have to be used 00219 * if another one is already available to protect the heap. 00220 * 00221 * \return see the documentation for pthread_rwlock_wrlock() 00222 * \since 1.6.1 00223 */ 00224 int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line); 00225 00226 /*! 00227 * \brief Read-Lock a heap 00228 * 00229 * \param h the heap 00230 * 00231 * A lock is provided for convenience. It can be assumed that none of the 00232 * ast_heap API calls are thread safe. This lock does not have to be used 00233 * if another one is already available to protect the heap. 00234 * 00235 * \return see the documentation for pthread_rwlock_rdlock() 00236 * \since 1.6.1 00237 */ 00238 int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line); 00239 00240 /*! 00241 * \brief Unlock a heap 00242 * 00243 * \param h the heap 00244 * 00245 * \return see the documentation for pthread_rwlock_unlock() 00246 * \since 1.6.1 00247 */ 00248 int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line); 00249 00250 #define ast_heap_wrlock(h) __ast_heap_wrlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__) 00251 #define ast_heap_rdlock(h) __ast_heap_rdlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__) 00252 #define ast_heap_unlock(h) __ast_heap_unlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__) 00253 00254 /*! 00255 * \brief Verify that a heap has been properly constructed 00256 * 00257 * \param h a heap 00258 * 00259 * \retval 0 success 00260 * \retval non-zero failure 00261 * 00262 * \note This function is mostly for debugging purposes. It traverses an existing 00263 * heap and verifies that every node is properly placed relative to its children. 00264 * \since 1.6.1 00265 */ 00266 int ast_heap_verify(struct ast_heap *h); 00267 00268 #endif /* __AST_HEAP_H__ */