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 struct ast_heap *ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn, 00101 ssize_t index_offset); 00102 00103 /*! 00104 * \brief Destroy a max heap 00105 * 00106 * \param h the heap to destroy 00107 * 00108 * \return NULL for convenience 00109 * \since 1.6.1 00110 */ 00111 struct ast_heap *ast_heap_destroy(struct ast_heap *h); 00112 00113 /*! 00114 * \brief Push an element on to a heap 00115 * 00116 * \param h the heap being added to 00117 * \param elm the element being put on the heap 00118 * 00119 * \retval 0 success 00120 * \retval non-zero failure 00121 * \since 1.6.1 00122 */ 00123 int ast_heap_push(struct ast_heap *h, void *elm); 00124 00125 /*! 00126 * \brief Pop the max element off of the heap 00127 * 00128 * \param h the heap 00129 * 00130 * \return this will return the element on the top of the heap, which has the 00131 * largest value according to the element comparison function that was 00132 * provided when the heap was created. The element will be removed before 00133 * being returned. 00134 * \since 1.6.1 00135 */ 00136 void *ast_heap_pop(struct ast_heap *h); 00137 00138 /*! 00139 * \brief Remove a specific element from a heap 00140 * 00141 * \param h the heap to remove from 00142 * \param elm the element to remove 00143 * 00144 * \return elm, if the removal was successful, or NULL if it failed 00145 * 00146 * \note the index_offset parameter to ast_heap_create() is required to be able 00147 * to use this function. 00148 * \since 1.6.1 00149 */ 00150 void *ast_heap_remove(struct ast_heap *h, void *elm); 00151 00152 /*! 00153 * \brief Peek at an element on a heap 00154 * 00155 * \param h the heap 00156 * \param index index of the element to return. The first element is at index 1, 00157 * and the last element is at the index == the size of the heap. 00158 * 00159 * \return an element at the specified index on the heap. This element will \b not 00160 * be removed before being returned. 00161 * 00162 * \note If this function is being used in combination with ast_heap_size() for 00163 * purposes of traversing the heap, the heap must be locked for the entire 00164 * duration of the traversal. 00165 * 00166 * Example code for a traversal: 00167 * \code 00168 * 00169 * struct ast_heap *h; 00170 * 00171 * ... 00172 * 00173 * size_t size, i; 00174 * void *cur_obj; 00175 * 00176 * ast_heap_rdlock(h); 00177 * 00178 * size = ast_heap_size(h); 00179 * 00180 * for (i = 1; i <= size && (cur_obj = ast_heap_peek(h, i)); i++) { 00181 * ... Do stuff with cur_obj ... 00182 * } 00183 * 00184 * ast_heap_unlock(h); 00185 * 00186 * \endcode 00187 * \since 1.6.1 00188 */ 00189 void *ast_heap_peek(struct ast_heap *h, unsigned int index); 00190 00191 /*! 00192 * \brief Get the current size of a heap 00193 * 00194 * \param h the heap 00195 * 00196 * \return the number of elements currently in the heap 00197 * \since 1.6.1 00198 */ 00199 size_t ast_heap_size(struct ast_heap *h); 00200 00201 #ifndef DEBUG_THREADS 00202 00203 /*! 00204 * \brief Write-Lock a heap 00205 * 00206 * \param h the heap 00207 * 00208 * A lock is provided for convenience. It can be assumed that none of the 00209 * ast_heap API calls are thread safe. This lock does not have to be used 00210 * if another one is already available to protect the heap. 00211 * 00212 * \return see the documentation for pthread_rwlock_wrlock() 00213 * \since 1.6.1 00214 */ 00215 int ast_heap_wrlock(struct ast_heap *h); 00216 00217 /*! 00218 * \brief Read-Lock a heap 00219 * 00220 * \param h the heap 00221 * 00222 * A lock is provided for convenience. It can be assumed that none of the 00223 * ast_heap API calls are thread safe. This lock does not have to be used 00224 * if another one is already available to protect the heap. 00225 * 00226 * \return see the documentation for pthread_rwlock_rdlock() 00227 * \since 1.6.1 00228 */ 00229 int ast_heap_rdlock(struct ast_heap *h); 00230 00231 /*! 00232 * \brief Unlock a heap 00233 * 00234 * \param h the heap 00235 * 00236 * \return see the documentation for pthread_rwlock_unlock() 00237 * \since 1.6.1 00238 */ 00239 int ast_heap_unlock(struct ast_heap *h); 00240 00241 #else /* DEBUG_THREADS */ 00242 00243 #define ast_heap_wrlock(h) __ast_heap_wrlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__) 00244 int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line); 00245 #define ast_heap_rdlock(h) __ast_heap_rdlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__) 00246 int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line); 00247 #define ast_heap_unlock(h) __ast_heap_unlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__) 00248 int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line); 00249 00250 #endif /* DEBUG_THREADS */ 00251 00252 /*! 00253 * \brief Verify that a heap has been properly constructed 00254 * 00255 * \param h a heap 00256 * 00257 * \retval 0 success 00258 * \retval non-zero failure 00259 * 00260 * \note This function is mostly for debugging purposes. It traverses an existing 00261 * heap and verifies that every node is properly placed relative to its children. 00262 * \since 1.6.1 00263 */ 00264 int ast_heap_verify(struct ast_heap *h); 00265 00266 #endif /* __AST_HEAP_H__ */