diff options
author | russell <russell@f38db490-d61c-443f-a65b-d21fe96a405b> | 2009-02-17 20:51:10 +0000 |
---|---|---|
committer | russell <russell@f38db490-d61c-443f-a65b-d21fe96a405b> | 2009-02-17 20:51:10 +0000 |
commit | 18f52ab1e75f994e02b4da7d22c8d41e5b479f6a (patch) | |
tree | cfbb55e6ff6db212e2fdfa882d9d155d6c45a2e5 | |
parent | d6b563a51dd506654db20450a81f668680f45460 (diff) |
Add an implementation of the heap data structure.
A heap is a convenient data structure for implementing a priority queue.
Code from svn/asterisk/team/russell/heap/.
Review: http://reviewboard.digium.com/r/160/
git-svn-id: http://svn.digium.com/svn/asterisk/trunk@176632 f38db490-d61c-443f-a65b-d21fe96a405b
-rw-r--r-- | include/asterisk/heap.h | 218 | ||||
-rw-r--r-- | main/Makefile | 2 | ||||
-rw-r--r-- | main/heap.c | 284 |
3 files changed, 503 insertions, 1 deletions
diff --git a/include/asterisk/heap.h b/include/asterisk/heap.h new file mode 100644 index 000000000..6f6e52b2d --- /dev/null +++ b/include/asterisk/heap.h @@ -0,0 +1,218 @@ +/* + * Asterisk -- An open source telephony toolkit. + * + * Copyright (C) 2009, Digium, Inc. + * + * Russell Bryant <russell@digium.com> + * + * See http://www.asterisk.org for more information about + * the Asterisk project. Please do not directly contact + * any of the maintainers of this project for assistance; + * the project provides a web site, mailing lists and IRC + * channels for your use. + * + * This program is free software, distributed under the terms of + * the GNU General Public License Version 2. See the LICENSE file + * at the top of the source tree. + */ + +/*! + * \file + * \brief Max Heap data structure + * \author Russell Bryant <russell@digium.com> + */ + +#ifndef __AST_HEAP_H__ +#define __AST_HEAP_H__ + +/*! + * \brief A max heap. + * + * \note Thread-safety is left to the user of the API. The heap API provides + * no locking of its own. If the heap will be accessed by multiple threads, + * then a lock must be used to ensure that only a single operation is + * done on the heap at a time. For the sake of convenience, a lock is + * provided for the user of the API to use if another lock is not already + * available to protect the heap. + */ +struct ast_heap; + +/*! + * \brief Function type for comparing nodes in a heap + * + * \param elm1 the first element + * \param elm2 the second element + * + * \retval negative if elm1 < elm2 + * \retval 0 if elm1 == elm2 + * \retval positive if elm1 > elm2 + * + * \note This implementation is of a max heap. However, if a min heap is + * desired, simply swap the return values of this function. + */ +typedef int (*ast_heap_cmp_fn)(void *elm1, void *elm2); + +/*! + * \brief Create a max heap + * + * \param init_height The initial height of the heap to allocate space for. + * To start out, there will be room for (2 ^ init_height) - 1 entries. + * However, the heap will grow as needed. + * \param cmp_fn The function that should be used to compare elements in the heap. + * \param index_offset This parameter is optional, but must be provided to be able + * to use ast_heap_remove(). This is the number of bytes into the element + * where an ssize_t has been made available for the heap's internal + * use. The heap will use this field to keep track of the element's current + * position in the heap. The offsetof() macro is useful for providing a + * proper value for this argument. If ast_heap_remove() will not be used, + * then a negative value can be provided to indicate that no field for an + * offset has been allocated. + * + * Example Usage: + * + * \code + * + * struct myobj { + * int foo; + * int bar; + * char stuff[8]; + * char things[8]; + * ssize_t __heap_index; + * }; + * + * ... + * + * static int myobj_cmp(void *obj1, void *obj2); + * + * ... + * + * struct ast_heap *h; + * + * h = ast_heap_create(8, myobj_cmp, offsetof(struct myobj, __heap_index)); + * + * \endcode + * + * \return An instance of a max heap + */ +struct ast_heap *ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn, + ssize_t index_offset); + +/*! + * \brief Destroy a max heap + * + * \param h the heap to destroy + * + * \return NULL for convenience + */ +struct ast_heap *ast_heap_destroy(struct ast_heap *h); + +/*! + * \brief Push an element on to a heap + * + * \param h the heap being added to + * \param elm the element being put on the heap + * + * \retval 0 success + * \retval non-zero failure + */ +int ast_heap_push(struct ast_heap *h, void *elm); + +/*! + * \brief Pop the max element off of the heap + * + * \param h the heap + * + * \return this will return the element on the top of the heap, which has the + * largest value according to the element comparison function that was + * provided when the heap was created. The element will be removed before + * being returned. + */ +void *ast_heap_pop(struct ast_heap *h); + +/*! + * \brief Remove a specific element from a heap + * + * \param h the heap to remove from + * \param elm the element to remove + * + * \return elm, if the removal was successful, or NULL if it failed + * + * \note the index_offset parameter to ast_heap_create() is required to be able + * to use this function. + */ +void *ast_heap_remove(struct ast_heap *h, void *elm); + +/*! + * \brief Peek at an element on a heap + * + * \param h the heap + * \param index index of the element to return. The first element is at index 1, + * and the last element is at the index == the size of the heap. + * + * \return an element at the specified index on the heap. This element will \b not + * be removed before being returned. + * + * \note If this function is being used in combination with ast_heap_size() for + * purposes of traversing the heap, the heap must be locked for the entire + * duration of the traversal. + */ +void *ast_heap_peek(struct ast_heap *h, unsigned int index); + +/*! + * \brief Get the current size of a heap + * + * \param h the heap + * + * \return the number of elements currently in the heap + */ +size_t ast_heap_size(struct ast_heap *h); + +/*! + * \brief Write-Lock a heap + * + * \arg h the heap + * + * A lock is provided for convenience. It can be assumed that none of the + * ast_heap API calls are thread safe. This lock does not have to be used + * if another one is already available to protect the heap. + * + * \return see the documentation for pthread_rwlock_wrlock() + */ +int ast_heap_wrlock(struct ast_heap *h); + +/*! + * \brief Read-Lock a heap + * + * \arg h the heap + * + * A lock is provided for convenience. It can be assumed that none of the + * ast_heap API calls are thread safe. This lock does not have to be used + * if another one is already available to protect the heap. + * + * \return see the documentation for pthread_rwlock_rdlock() + */ +int ast_heap_rdlock(struct ast_heap *h); + +/*! + * \brief Unlock a heap + * + * \arg h the heap + * + * \return see the documentation for pthread_rwlock_unlock() + */ +int ast_heap_unlock(struct ast_heap *h); + +/*! + * \brief Verify that a heap has been properly constructed + * + * \param h a heap + * + * \retval 0 success + * \retval non-zero failure + * + * \note This function is mostly for debugging purposes. It traverses an existing + * heap and verifies that every node is properly placed relative to its children. + */ +int ast_heap_verify(struct ast_heap *h); + +#endif /* __AST_HEAP_H__ */ diff --git a/main/Makefile b/main/Makefile index 54882f245..7ce62d2ec 100644 --- a/main/Makefile +++ b/main/Makefile @@ -18,7 +18,7 @@ all: asterisk include $(ASTTOPDIR)/Makefile.moddir_rules OBJS= tcptls.o io.o sched.o logger.o frame.o loader.o config.o channel.o \ - translate.o file.o pbx.o cli.o md5.o term.o \ + translate.o file.o pbx.o cli.o md5.o term.o heap.o \ ulaw.o alaw.o callerid.o fskmodem.o image.o app.o \ cdr.o tdd.o acl.o rtp.o udptl.o manager.o asterisk.o \ dsp.o chanvars.o indications.o autoservice.o db.o privacy.o \ diff --git a/main/heap.c b/main/heap.c new file mode 100644 index 000000000..5e8a2baef --- /dev/null +++ b/main/heap.c @@ -0,0 +1,284 @@ +/* + * Asterisk -- An open source telephony toolkit. + * + * Copyright (C) 2009, Digium, Inc. + * + * Russell Bryant <russell@digium.com> + * + * See http://www.asterisk.org for more information about + * the Asterisk project. Please do not directly contact + * any of the maintainers of this project for assistance; + * the project provides a web site, mailing lists and IRC + * channels for your use. + * + * This program is free software, distributed under the terms of + * the GNU General Public License Version 2. See the LICENSE file + * at the top of the source tree. + */ + +/*! \file + * + * \brief Max Heap data structure + * + * \author Russell Bryant <russell@digium.com> + */ + +#include "asterisk.h" + +ASTERISK_FILE_VERSION(__FILE__, "$Revision$") + +#include "asterisk/heap.h" +#include "asterisk/utils.h" +#include "asterisk/cli.h" + +struct ast_heap { + ast_rwlock_t lock; + ast_heap_cmp_fn cmp_fn; + ssize_t index_offset; + size_t cur_len; + size_t avail_len; + void **heap; +}; + +static inline int left_node(int i) +{ + return 2 * i; +} + +static inline int right_node(int i) +{ + return 2 * i + 1; +} + +static inline int parent_node(int i) +{ + return i / 2; +} + +static inline void *heap_get(struct ast_heap *h, int i) +{ + return h->heap[i - 1]; +} + +static inline ssize_t get_index(struct ast_heap *h, void *elm) +{ + ssize_t *index; + + if (h->index_offset < 0) { + return -1; + } + + index = elm + h->index_offset; + + return *index; +} + +static inline void heap_set(struct ast_heap *h, int i, void *elm) +{ + h->heap[i - 1] = elm; + + if (h->index_offset >= 0) { + ssize_t *index = elm + h->index_offset; + *index = i; + } +} + +int ast_heap_verify(struct ast_heap *h) +{ + unsigned int i; + + for (i = 1; i <= (h->cur_len / 2); i++) { + int l = left_node(i); + int r = right_node(i); + + if (l <= h->cur_len) { + if (h->cmp_fn(heap_get(h, i), heap_get(h, l)) <= 0) { + return -1; + } + } + + if (r <= h->cur_len) { + if (h->cmp_fn(heap_get(h, i), heap_get(h, r)) <= 0) { + return -1; + } + } + } + + return 0; +} + +struct ast_heap *ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn, + ssize_t index_offset) +{ + struct ast_heap *h; + + if (!cmp_fn) { + ast_log(LOG_ERROR, "A comparison function must be provided\n"); + return NULL; + } + + if (!init_height) { + init_height = 8; + } + + if (!(h = ast_calloc(1, sizeof(*h)))) { + return NULL; + } + + h->cmp_fn = cmp_fn; + h->index_offset = index_offset; + h->avail_len = (1 << init_height) - 1; + + if (!(h->heap = ast_calloc(1, h->avail_len * sizeof(void *)))) { + ast_free(h); + return NULL; + } + + ast_rwlock_init(&h->lock); + + return h; +} + +struct ast_heap *ast_heap_destroy(struct ast_heap *h) +{ + ast_free(h->heap); + h->heap = NULL; + + ast_rwlock_destroy(&h->lock); + + ast_free(h); + + return NULL; +} + +/*! + * \brief Add a row of additional storage for the heap. + */ +static int grow_heap(struct ast_heap *h) +{ + h->avail_len = h->avail_len * 2 + 1; + + if (!(h->heap = ast_realloc(h->heap, h->avail_len * sizeof(void *)))) { + h->cur_len = h->avail_len = 0; + return -1; + } + + return 0; +} + +static inline void heap_swap(struct ast_heap *h, int i, int j) +{ + void *tmp; + + tmp = heap_get(h, i); + heap_set(h, i, heap_get(h, j)); + heap_set(h, j, tmp); +} + +static inline void max_heapify(struct ast_heap *h, int i) +{ + for (;;) { + int l = left_node(i); + int r = right_node(i); + int max; + + if (l <= h->cur_len && h->cmp_fn(heap_get(h, l), heap_get(h, i)) > 0) { + max = l; + } else { + max = i; + } + + if (r <= h->cur_len && h->cmp_fn(heap_get(h, r), heap_get(h, max)) > 0) { + max = r; + } + + if (max == i) { + break; + } + + heap_swap(h, i, max); + + i = max; + } +} + +int ast_heap_push(struct ast_heap *h, void *elm) +{ + int i; + + if (h->cur_len == h->avail_len && grow_heap(h)) { + return -1; + } + + heap_set(h, ++(h->cur_len), elm); + + for (i = h->cur_len; + i > 1 && h->cmp_fn(heap_get(h, parent_node(i)), heap_get(h, i)) < 0; + i = parent_node(i)) { + heap_swap(h, i, parent_node(i)); + } + + return 0; +} + +static void *_ast_heap_remove(struct ast_heap *h, unsigned int index) +{ + void *ret; + + if (!index || index > h->cur_len) { + return NULL; + } + + ret = heap_get(h, index); + heap_set(h, index, heap_get(h, (h->cur_len)--)); + + max_heapify(h, index); + + return ret; +} + +void *ast_heap_remove(struct ast_heap *h, void *elm) +{ + ssize_t i = get_index(h, elm); + + if (i == -1) { + return NULL; + } + + return _ast_heap_remove(h, i); +} + +void *ast_heap_pop(struct ast_heap *h) +{ + return _ast_heap_remove(h, 1); +} + +void *ast_heap_peek(struct ast_heap *h, unsigned int index) +{ + if (!h->cur_len || !index || index > h->cur_len) { + return NULL; + } + + return heap_get(h, index); +} + +size_t ast_heap_size(struct ast_heap *h) +{ + return h->cur_len; +} + +int ast_heap_wrlock(struct ast_heap *h) +{ + return ast_rwlock_wrlock(&h->lock); +} + +int ast_heap_rdlock(struct ast_heap *h) +{ + return ast_rwlock_rdlock(&h->lock); +} + +int ast_heap_unlock(struct ast_heap *h) +{ + return ast_rwlock_unlock(&h->lock); +} + |