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.

Macros
#define	ast_heap_create(init_height, cmp_fn, index_offset)    _ast_heap_create(init_height, cmp_fn, index_offset, __FILE__, __LINE__, __PRETTY_FUNCTION__)
	Create a max heap. More...
#define	ast_heap_push(h, elm)    _ast_heap_push(h, elm, __FILE__, __LINE__, __PRETTY_FUNCTION__)
	Push an element on to a heap. More...
#define	ast_heap_rdlock(h)   __ast_heap_rdlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)
#define	ast_heap_unlock(h)   __ast_heap_unlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)
#define	ast_heap_wrlock(h)   __ast_heap_wrlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)

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

Functions
int	__ast_heap_rdlock (struct ast_heap *h, const char *file, const char *func, int line)
	Read-Lock a heap. More...
int	__ast_heap_unlock (struct ast_heap *h, const char *file, const char *func, int line)
	Unlock a heap. More...
int	__ast_heap_wrlock (struct ast_heap *h, const char *file, const char *func, int line)
	Write-Lock a heap. More...
struct ast_heap *	_ast_heap_create (unsigned int init_height, ast_heap_cmp_fn cmp_fn, ssize_t index_offset, const char *file, int lineno, const char *func)
int	_ast_heap_push (struct ast_heap *h, void *elm, const char *file, int lineno, const char *func)
struct ast_heap *	ast_heap_destroy (struct ast_heap *h)
	Destroy a max heap. More...
void *	ast_heap_peek (struct ast_heap *h, unsigned int index)
	Peek at an element on a heap. More...
void *	ast_heap_pop (struct ast_heap *h)
	Pop the max element off of the heap. More...
void *	ast_heap_remove (struct ast_heap *h, void *elm)
	Remove a specific element from a heap. More...
size_t	ast_heap_size (struct ast_heap *h)
	Get the current size of a heap. More...
int	ast_heap_verify (struct ast_heap *h)
	Verify that a heap has been properly constructed. More...

Detailed Description

Max Heap data structure.

Author

Russell Bryant russe.nosp@m.ll@d.nosp@m.igium.nosp@m..com

Definition in file heap.h.

Macro Definition Documentation

ast_heap_create

#define ast_heap_create	(		init_height,
			cmp_fn,
			index_offset
	)		_ast_heap_create(init_height, cmp_fn, index_offset, __FILE__, __LINE__, __PRETTY_FUNCTION__)

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 100 of file heap.h.

ast_heap_push

#define ast_heap_push	(		h,
			elm
	)		_ast_heap_push(h, elm, __FILE__, __LINE__, __PRETTY_FUNCTION__)

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 125 of file heap.h.

ast_heap_rdlock

#define ast_heap_rdlock

(

h

)

__ast_heap_rdlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)

Definition at line 248 of file heap.h.

ast_heap_unlock

#define ast_heap_unlock

(

h

)

__ast_heap_unlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)

Definition at line 249 of file heap.h.

ast_heap_wrlock

#define ast_heap_wrlock

(

h

)

__ast_heap_wrlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)

Definition at line 247 of file heap.h.

Typedef Documentation

ast_heap_cmp_fn

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

__ast_heap_rdlock()

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

Read-Lock a heap.

Parameters

h	the heap
file,func,line

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

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

References __ast_rwlock_rdlock(), make_ari_stubs::file, and ast_heap::lock.

__ast_heap_unlock()

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

Unlock a heap.

Parameters

h	the heap
file,func,line

Returns

see the documentation for pthread_rwlock_unlock()

Since

1.6.1

Definition at line 291 of file heap.c.

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

References __ast_rwlock_unlock(), make_ari_stubs::file, and ast_heap::lock.

__ast_heap_wrlock()

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

Write-Lock a heap.

Parameters

h	the heap
file,func,line

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

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

References __ast_rwlock_wrlock(), make_ari_stubs::file, and ast_heap::lock.

_ast_heap_create()

struct ast_heap * _ast_heap_create	(	unsigned int	init_height,
		ast_heap_cmp_fn	cmp_fn,
		ssize_t	index_offset,
		const char *	file,
		int	lineno,
		const char *	func
	)

Definition at line 112 of file heap.c.

{
    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;
    }
 
    h = __ast_calloc(1, sizeof(*h), file, lineno, func);
    if (!h) {
        return NULL;
    }
 
    h->cmp_fn = cmp_fn;
    h->index_offset = index_offset;
    h->avail_len = (1 << init_height) - 1;
 
    h->heap = __ast_malloc(h->avail_len * sizeof(void *), file, lineno, func);
    if (!h->heap) {
        ast_free(h);
        return NULL;
    }
 
    ast_rwlock_init(&h->lock);
 
    return h;
}

References __ast_calloc(), __ast_malloc(), ast_free, ast_log, ast_rwlock_init, ast_heap::avail_len, ast_heap::cmp_fn, make_ari_stubs::file, ast_heap::heap, ast_heap::index_offset, ast_heap::lock, LOG_ERROR, and NULL.

_ast_heap_push()

int _ast_heap_push	(	struct ast_heap *	h,
		void *	elm,
		const char *	file,
		int	lineno,
		const char *	func
	)

Definition at line 222 of file heap.c.

{
    if (h->cur_len == h->avail_len && grow_heap(h, file, lineno, func)) {
        return -1;
    }
 
    heap_set(h, ++(h->cur_len), elm);
 
    bubble_up(h, h->cur_len);
 
    return 0;
}

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

ast_heap_destroy()

struct ast_heap * ast_heap_destroy

(

struct ast_heap *

h

)

Destroy a max heap.

Parameters

h	the heap to destroy

Return values

NULL	for convenience

Since

1.6.1

Definition at line 146 of file heap.c.

{
    ast_free(h->heap);
    h->heap = NULL;
 
    ast_rwlock_destroy(&h->lock);
 
    ast_free(h);
 
    return NULL;
}

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

Referenced by ast_bridge_features_cleanup(), ast_sched_context_destroy(), AST_TEST_DEFINE(), sorcery_memory_cache_destructor(), and timing_shutdown().

ast_heap_peek()

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

{
    if (!h->cur_len || !index || index > h->cur_len) {
        return NULL;
    }
 
    return heap_get(h, index);
}

References ast_heap::cur_len, heap_get(), and NULL.

Referenced by add_to_cache(), ast_bridge_features_merge(), ast_sched_clean_by_callback(), ast_sched_dump(), ast_sched_report(), ast_sched_runq(), ast_sched_wait(), ast_timer_open(), bridge_channel_handle_interval(), bridge_channel_next_interval(), expire_objects_from_cache(), hooks_remove_heap(), memory_cache_stale_check(), remove_from_cache(), sched_find(), and schedule_cache_expiration().

ast_heap_pop()

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

{
    return _ast_heap_remove(h, 1);
}

References _ast_heap_remove().

Referenced by ast_bridge_features_cleanup(), ast_sched_context_destroy(), ast_sched_runq(), AST_TEST_DEFINE(), remove_all_from_cache(), and remove_oldest_from_cache().

ast_heap_remove()

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

Return values

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

{
    ssize_t i = get_index(h, elm);
 
    if (i == -1) {
        return NULL;
    }
 
    return _ast_heap_remove(h, i);
}

References _ast_heap_remove(), get_index(), and NULL.

Referenced by ast_sched_clean_by_callback(), ast_sched_del_nonrunning(), AST_TEST_DEFINE(), ast_unregister_timing_interface(), bridge_channel_handle_interval(), hooks_remove_heap(), and remove_from_cache().

ast_heap_size()

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

{
    return h->cur_len;
}

References ast_heap::cur_len.

Referenced by ast_sched_dump(), ast_sched_report(), hooks_remove_heap(), sched_find(), and schedule().

ast_heap_verify()

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

{
    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;
}

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

Referenced by AST_TEST_DEFINE().