Wed Oct 28 11:52:42 2009

Asterisk developer's documentation


heap.h File Reference

Max Heap data structure. More...

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs

typedef int(* ast_heap_cmp_fn )(void *elm1, void *elm2)
 Function type for comparing nodes in a heap.

Functions

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.
int ast_heap_rdlock (struct ast_heap *h)
 Read-Lock 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_unlock (struct ast_heap *h)
 Unlock a heap.
int ast_heap_verify (struct ast_heap *h)
 Verify that a heap has been properly constructed.
int ast_heap_wrlock (struct ast_heap *h)
 Write-Lock a heap.


Detailed Description

Max Heap data structure.

Author:
Russell Bryant <russell@digium.com>

Definition in file heap.h.


Typedef Documentation

typedef int(* ast_heap_cmp_fn)(void *elm1, void *elm2)

Function type for comparing nodes in a heap.

Parameters:
elm1 the first element
elm2 the second element
Return values:
negative if elm1 < elm2
0 if elm1 == elm2
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.
Since:
1.6.1

Definition at line 55 of file heap.h.


Function Documentation

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 110 of file heap.c.

References 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(), and load_resource_list().

00112 {
00113    struct ast_heap *h;
00114 
00115    if (!cmp_fn) {
00116       ast_log(LOG_ERROR, "A comparison function must be provided\n");
00117       return NULL;
00118    }
00119 
00120    if (!init_height) {
00121       init_height = 8;
00122    }
00123 
00124    if (!(h = ast_calloc(1, sizeof(*h)))) {
00125       return NULL;
00126    }
00127 
00128    h->cmp_fn = cmp_fn;
00129    h->index_offset = index_offset;
00130    h->avail_len = (1 << init_height) - 1;
00131 
00132    if (!(h->heap = ast_calloc(1, h->avail_len * sizeof(void *)))) {
00133       ast_free(h);
00134       return NULL;
00135    }
00136 
00137    ast_rwlock_init(&h->lock);
00138 
00139    return h;
00140 }

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 142 of file heap.c.

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

Referenced by load_resource_list().

00143 {
00144    ast_free(h->heap);
00145    h->heap = NULL;
00146 
00147    ast_rwlock_destroy(&h->lock);
00148 
00149    ast_free(h);
00150 
00151    return NULL;
00152 }

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 256 of file heap.c.

References ast_heap::cur_len, and heap_get().

Referenced by ast_timer_open().

00257 {
00258    if (!h->cur_len || !index || index > h->cur_len) {
00259       return NULL;
00260    }
00261 
00262    return heap_get(h, index);
00263 }

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 251 of file heap.c.

References _ast_heap_remove().

Referenced by load_resource_list().

00252 {
00253    return _ast_heap_remove(h, 1);
00254 }

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 205 of file heap.c.

References ast_heap::avail_len, ast_heap::cmp_fn, ast_heap::cur_len, grow_heap(), heap_get(), heap_set(), heap_swap(), and parent_node().

Referenced by _ast_register_timing_interface(), and load_resource().

00206 {
00207    int i;
00208 
00209    if (h->cur_len == h->avail_len && grow_heap(h)) {
00210       return -1;
00211    }
00212 
00213    heap_set(h, ++(h->cur_len), elm);
00214 
00215    for (i = h->cur_len;
00216          i > 1 && h->cmp_fn(heap_get(h, parent_node(i)), heap_get(h, i)) < 0;
00217          i = parent_node(i)) {
00218       heap_swap(h, i, parent_node(i));
00219    }
00220 
00221    return 0;
00222 }

int ast_heap_rdlock ( struct ast_heap h  ) 

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 277 of file heap.c.

References ast_rwlock_rdlock(), and ast_heap::lock.

Referenced by ast_timer_open().

00278 {
00279    return ast_rwlock_rdlock(&h->lock);
00280 }

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 240 of file heap.c.

References _ast_heap_remove(), and get_index().

Referenced by ast_unregister_timing_interface().

00241 {
00242    ssize_t i = get_index(h, elm);
00243 
00244    if (i == -1) {
00245       return NULL;
00246    }
00247 
00248    return _ast_heap_remove(h, i);
00249 }

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 265 of file heap.c.

References ast_heap::cur_len.

00266 {
00267    return h->cur_len;
00268 }

int ast_heap_unlock ( struct ast_heap h  ) 

Unlock a heap.

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

Definition at line 282 of file heap.c.

References ast_rwlock_unlock(), and ast_heap::lock.

Referenced by _ast_register_timing_interface(), ast_timer_open(), and ast_unregister_timing_interface().

00283 {
00284    return ast_rwlock_unlock(&h->lock);
00285 }

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 86 of file heap.c.

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

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

int ast_heap_wrlock ( struct ast_heap h  ) 

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 272 of file heap.c.

References ast_rwlock_wrlock(), and ast_heap::lock.

Referenced by _ast_register_timing_interface(), and ast_unregister_timing_interface().

00273 {
00274    return ast_rwlock_wrlock(&h->lock);
00275 }


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