Tue Aug 20 16:35:04 2013

Asterisk developer's documentation


heap.c File Reference

Max Heap data structure. More...

#include "asterisk.h"
#include "asterisk/heap.h"
#include "asterisk/utils.h"
#include "asterisk/cli.h"

Go to the source code of this file.

Data Structures

struct  ast_heap

Functions

int __ast_heap_rdlock (struct ast_heap *h, const char *file, const char *func, int line)
 Read-Lock a heap.
int __ast_heap_unlock (struct ast_heap *h, const char *file, const char *func, int line)
 Unlock a heap.
int __ast_heap_wrlock (struct ast_heap *h, const char *file, const char *func, int line)
 Write-Lock a heap.
static void * _ast_heap_remove (struct ast_heap *h, unsigned int index)
struct ast_heapast_heap_create (unsigned int init_height, ast_heap_cmp_fn cmp_fn, ssize_t index_offset)
 Create a max heap.
struct ast_heapast_heap_destroy (struct ast_heap *h)
 Destroy a max heap.
void * ast_heap_peek (struct ast_heap *h, unsigned int index)
 Peek at an element on a heap.
void * ast_heap_pop (struct ast_heap *h)
 Pop the max element off of the heap.
int ast_heap_push (struct ast_heap *h, void *elm)
 Push an element on to a heap.
void * ast_heap_remove (struct ast_heap *h, void *elm)
 Remove a specific element from a heap.
size_t ast_heap_size (struct ast_heap *h)
 Get the current size of a heap.
int ast_heap_verify (struct ast_heap *h)
 Verify that a heap has been properly constructed.
static int bubble_up (struct ast_heap *h, int i)
static ssize_t get_index (struct ast_heap *h, void *elm)
static int grow_heap (struct ast_heap *h)
 Add a row of additional storage for the heap.
static void * heap_get (struct ast_heap *h, int i)
static void heap_set (struct ast_heap *h, int i, void *elm)
static void heap_swap (struct ast_heap *h, int i, int j)
static int left_node (int i)
static void max_heapify (struct ast_heap *h, int i)
static int parent_node (int i)
static int right_node (int i)

Detailed Description

Max Heap data structure.

Author:
Russell Bryant <russell@digium.com>

Definition in file heap.c.


Function Documentation

int __ast_heap_rdlock ( struct ast_heap h,
const char *  file,
const char *  func,
int  line 
)

Read-Lock a heap.

Parameters:
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.

Returns:
see the documentation for pthread_rwlock_rdlock()
Since:
1.6.1

Definition at line 318 of file heap.c.

References __ast_rwlock_rdlock(), and ast_heap::lock.

00319 {
00320    return __ast_rwlock_rdlock(file, line, func, &h->lock, "&h->lock");
00321 }

int __ast_heap_unlock ( struct ast_heap h,
const char *  file,
const char *  func,
int  line 
)

Unlock a heap.

Parameters:
h the heap
Returns:
see the documentation for pthread_rwlock_unlock()
Since:
1.6.1

Definition at line 323 of file heap.c.

References __ast_rwlock_unlock(), and ast_heap::lock.

00324 {
00325    return __ast_rwlock_unlock(file, line, func, &h->lock, "&h->lock");
00326 }

int __ast_heap_wrlock ( struct ast_heap h,
const char *  file,
const char *  func,
int  line 
)

Write-Lock a heap.

Parameters:
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.

Returns:
see the documentation for pthread_rwlock_wrlock()
Since:
1.6.1

Definition at line 313 of file heap.c.

References __ast_rwlock_wrlock(), and ast_heap::lock.

00314 {
00315    return __ast_rwlock_wrlock(file, line, func, &h->lock, "&h->lock");
00316 }

static void* _ast_heap_remove ( struct ast_heap h,
unsigned int  index 
) [static]

Definition at line 267 of file heap.c.

References bubble_up(), ast_heap::cur_len, heap_get(), heap_set(), and max_heapify().

Referenced by ast_heap_pop(), and ast_heap_remove().

00268 {
00269    void *ret;
00270 
00271    if (!index || index > h->cur_len) {
00272       return NULL;
00273    }
00274 
00275    ret = heap_get(h, index);
00276    heap_set(h, index, heap_get(h, (h->cur_len)--));
00277    index = bubble_up(h, index);
00278    max_heapify(h, index);
00279 
00280    return ret;
00281 }

struct ast_heap* ast_heap_create ( unsigned int  init_height,
ast_heap_cmp_fn  cmp_fn,
ssize_t  index_offset 
) [read]

Create a max heap.

Parameters:
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.
cmp_fn The function that should be used to compare elements in the heap.
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:

 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));
Returns:
An instance of a max heap
Since:
1.6.1

Definition at line 118 of file heap.c.

References __ast_calloc(), ast_calloc, ast_free, ast_log(), ast_rwlock_init, ast_heap::avail_len, ast_heap::cmp_fn, ast_heap::heap, ast_heap::index_offset, ast_heap::lock, and LOG_ERROR.

Referenced by ast_timing_init(), load_resource_list(), and sched_context_create().

00121 {
00122    struct ast_heap *h;
00123 
00124    if (!cmp_fn) {
00125       ast_log(LOG_ERROR, "A comparison function must be provided\n");
00126       return NULL;
00127    }
00128 
00129    if (!init_height) {
00130       init_height = 8;
00131    }
00132 
00133    if (!(h =
00134 #ifdef MALLOC_DEBUG
00135          __ast_calloc(1, sizeof(*h), file, lineno, func)
00136 #else
00137          ast_calloc(1, sizeof(*h))
00138 #endif
00139       )) {
00140       return NULL;
00141    }
00142 
00143    h->cmp_fn = cmp_fn;
00144    h->index_offset = index_offset;
00145    h->avail_len = (1 << init_height) - 1;
00146 
00147    if (!(h->heap =
00148 #ifdef MALLOC_DEBUG
00149          __ast_calloc(1, h->avail_len * sizeof(void *), file, lineno, func)
00150 #else
00151          ast_calloc(1, h->avail_len * sizeof(void *))
00152 #endif
00153       )) {
00154       ast_free(h);
00155       return NULL;
00156    }
00157 
00158    ast_rwlock_init(&h->lock);
00159 
00160    return h;
00161 }

struct ast_heap* ast_heap_destroy ( struct ast_heap h  )  [read]

Destroy a max heap.

Parameters:
h the heap to destroy
Returns:
NULL for convenience
Since:
1.6.1

Definition at line 163 of file heap.c.

References ast_free, ast_rwlock_destroy, ast_heap::heap, and ast_heap::lock.

Referenced by load_resource_list(), sched_context_destroy(), and timing_shutdown().

00164 {
00165    ast_free(h->heap);
00166    h->heap = NULL;
00167 
00168    ast_rwlock_destroy(&h->lock);
00169 
00170    ast_free(h);
00171 
00172    return NULL;
00173 }

void* ast_heap_peek ( struct ast_heap h,
unsigned int  index 
)

Peek at an element on a heap.

Parameters:
h the heap
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.
Returns:
an element at the specified index on the heap. This element will 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.

Example code for a traversal:

 struct ast_heap *h;

 ...

 size_t size, i;
 void *cur_obj;

 ast_heap_rdlock(h);

 size = ast_heap_size(h);

 for (i = 1; i <= size && (cur_obj = ast_heap_peek(h, i)); i++) {
     ... Do stuff with cur_obj ...
 }

 ast_heap_unlock(h);
Since:
1.6.1

Definition at line 299 of file heap.c.

References ast_heap::cur_len, and heap_get().

Referenced by ast_sched_dump(), ast_sched_report(), ast_sched_runq(), ast_sched_wait(), and ast_timer_open().

00300 {
00301    if (!h->cur_len || !index || index > h->cur_len) {
00302       return NULL;
00303    }
00304 
00305    return heap_get(h, index);
00306 }

void* ast_heap_pop ( struct ast_heap h  ) 

Pop the max element off of the heap.

Parameters:
h the heap
Returns:
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.
Since:
1.6.1

Definition at line 294 of file heap.c.

References _ast_heap_remove().

Referenced by ast_sched_runq(), load_resource_list(), and sched_context_destroy().

00295 {
00296    return _ast_heap_remove(h, 1);
00297 }

int ast_heap_push ( struct ast_heap h,
void *  elm 
)

Push an element on to a heap.

Parameters:
h the heap being added to
elm the element being put on the heap
Return values:
0 success
non-zero failure
Since:
1.6.1

Definition at line 249 of file heap.c.

References ast_heap::avail_len, bubble_up(), ast_heap::cur_len, grow_heap(), and heap_set().

Referenced by _ast_register_timing_interface(), load_resource(), and schedule().

00251 {
00252    if (h->cur_len == h->avail_len && grow_heap(h
00253 #ifdef MALLOC_DEBUG
00254       , file, lineno, func
00255 #endif
00256       )) {
00257       return -1;
00258    }
00259 
00260    heap_set(h, ++(h->cur_len), elm);
00261 
00262    bubble_up(h, h->cur_len);
00263 
00264    return 0;
00265 }

void* ast_heap_remove ( struct ast_heap h,
void *  elm 
)

Remove a specific element from a heap.

Parameters:
h the heap to remove from
elm the element to remove
Returns:
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.
Since:
1.6.1

Definition at line 283 of file heap.c.

References _ast_heap_remove(), and get_index().

Referenced by ast_sched_del(), and ast_unregister_timing_interface().

00284 {
00285    ssize_t i = get_index(h, elm);
00286 
00287    if (i == -1) {
00288       return NULL;
00289    }
00290 
00291    return _ast_heap_remove(h, i);
00292 }

size_t ast_heap_size ( struct ast_heap h  ) 

Get the current size of a heap.

Parameters:
h the heap
Returns:
the number of elements currently in the heap
Since:
1.6.1

Definition at line 308 of file heap.c.

References ast_heap::cur_len.

Referenced by ast_sched_dump(), and ast_sched_report().

00309 {
00310    return h->cur_len;
00311 }

int ast_heap_verify ( struct ast_heap h  ) 

Verify that a heap has been properly constructed.

Parameters:
h a heap
Return values:
0 success
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.
Since:
1.6.1

Definition at line 90 of file heap.c.

References ast_heap::cmp_fn, ast_heap::cur_len, heap_get(), left_node(), and right_node().

00091 {
00092    unsigned int i;
00093 
00094    for (i = 1; i <= (h->cur_len / 2); i++) {
00095       int l = left_node(i);
00096       int r = right_node(i);
00097 
00098       if (l <= h->cur_len) {
00099          if (h->cmp_fn(heap_get(h, i), heap_get(h, l)) < 0) {
00100             return -1;
00101          }
00102       }
00103 
00104       if (r <= h->cur_len) {
00105          if (h->cmp_fn(heap_get(h, i), heap_get(h, r)) < 0) {
00106             return -1;
00107          }
00108       }
00109    }
00110 
00111    return 0;
00112 }

static int bubble_up ( struct ast_heap h,
int  i 
) [static]

Definition at line 236 of file heap.c.

References ast_heap::cmp_fn, heap_get(), heap_swap(), and parent_node().

Referenced by _ast_heap_remove(), and ast_heap_push().

00237 {
00238    while (i > 1 && h->cmp_fn(heap_get(h, parent_node(i)), heap_get(h, i)) < 0) {
00239       heap_swap(h, i, parent_node(i));
00240       i = parent_node(i);
00241    }
00242 
00243    return i;
00244 }

static ssize_t get_index ( struct ast_heap h,
void *  elm 
) [inline, static]

Definition at line 67 of file heap.c.

References ast_heap::index_offset.

Referenced by ast_heap_remove().

00068 {
00069    ssize_t *index;
00070 
00071    if (h->index_offset < 0) {
00072       return -1;
00073    }
00074 
00075    index = elm + h->index_offset;
00076 
00077    return *index;
00078 }

static int grow_heap ( struct ast_heap h  )  [static]

Add a row of additional storage for the heap.

Definition at line 178 of file heap.c.

References __ast_realloc(), and ast_realloc.

Referenced by ast_heap_push().

00183 {
00184    h->avail_len = h->avail_len * 2 + 1;
00185 
00186    if (!(h->heap =
00187 #ifdef MALLOC_DEBUG
00188          __ast_realloc(h->heap, h->avail_len * sizeof(void *), file, lineno, func)
00189 #else
00190          ast_realloc(h->heap, h->avail_len * sizeof(void *))
00191 #endif
00192       )) {
00193       h->cur_len = h->avail_len = 0;
00194       return -1;
00195    }
00196 
00197    return 0;
00198 }

static void* heap_get ( struct ast_heap h,
int  i 
) [inline, static]

Definition at line 62 of file heap.c.

References ast_heap::heap.

Referenced by _ast_heap_remove(), ast_heap_peek(), ast_heap_verify(), bubble_up(), heap_swap(), and max_heapify().

00063 {
00064    return h->heap[i - 1];
00065 }

static void heap_set ( struct ast_heap h,
int  i,
void *  elm 
) [inline, static]

Definition at line 80 of file heap.c.

References ast_heap::heap, and ast_heap::index_offset.

Referenced by _ast_heap_remove(), ast_heap_push(), and heap_swap().

00081 {
00082    h->heap[i - 1] = elm;
00083 
00084    if (h->index_offset >= 0) {
00085       ssize_t *index = elm + h->index_offset;
00086       *index = i;
00087    }
00088 }

static void heap_swap ( struct ast_heap h,
int  i,
int  j 
) [inline, static]

Definition at line 200 of file heap.c.

References heap_get(), and heap_set().

Referenced by bubble_up(), and max_heapify().

00201 {
00202    void *tmp;
00203 
00204    tmp = heap_get(h, i);
00205    heap_set(h, i, heap_get(h, j));
00206    heap_set(h, j, tmp);
00207 }

static int left_node ( int  i  )  [inline, static]

Definition at line 47 of file heap.c.

Referenced by ast_heap_verify(), and max_heapify().

00048 {
00049    return 2 * i;
00050 }

static void max_heapify ( struct ast_heap h,
int  i 
) [inline, static]

Definition at line 209 of file heap.c.

References ast_heap::cmp_fn, ast_heap::cur_len, heap_get(), heap_swap(), left_node(), and right_node().

Referenced by _ast_heap_remove().

00210 {
00211    for (;;) {
00212       int l = left_node(i);
00213       int r = right_node(i);
00214       int max;
00215 
00216       if (l <= h->cur_len && h->cmp_fn(heap_get(h, l), heap_get(h, i)) > 0) {
00217          max = l;
00218       } else {
00219          max = i;
00220       }
00221 
00222       if (r <= h->cur_len && h->cmp_fn(heap_get(h, r), heap_get(h, max)) > 0) {
00223          max = r;
00224       }
00225 
00226       if (max == i) {
00227          break;
00228       }
00229 
00230       heap_swap(h, i, max);
00231 
00232       i = max;
00233    }
00234 }

static int parent_node ( int  i  )  [inline, static]

Definition at line 57 of file heap.c.

Referenced by bubble_up().

00058 {
00059    return i / 2;
00060 }

static int right_node ( int  i  )  [inline, static]

Definition at line 52 of file heap.c.

Referenced by ast_heap_verify(), and max_heapify().

00053 {
00054    return 2 * i + 1;
00055 }


Generated on 20 Aug 2013 for Asterisk - The Open Source Telephony Project by  doxygen 1.6.1