Wed Oct 28 11:51:04 2009

Asterisk developer's documentation


heap.h

Go to the documentation of this file.
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__ */

Generated on Wed Oct 28 11:51:04 2009 for Asterisk - the Open Source PBX by  doxygen 1.5.6