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__)
#define	ast_heap_push(h, elm)   _ast_heap_push(h, elm, __FILE__, __LINE__, __PRETTY_FUNCTION__)
#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)
	Create a max heap. More...
int	_ast_heap_push (struct ast_heap *h, void *elm, const char *file, int lineno, const char *func)
	Push an element on to a heap. More...
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__)

Definition at line 102 of file heap.h.

Referenced by ast_bridge_features_init(), ast_sched_context_create(), AST_TEST_DEFINE(), ast_timing_init(), and sorcery_memory_cache_open().

ast_heap_push

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

Definition at line 126 of file heap.h.

Referenced by _ast_register_timing_interface(), add_to_cache(), ast_bridge_interval_hook(), AST_TEST_DEFINE(), bridge_channel_handle_interval(), and schedule().

ast_heap_rdlock

#define ast_heap_rdlock

(

h

)

__ast_heap_rdlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)

Definition at line 247 of file heap.h.

Referenced by ast_timer_open().

ast_heap_unlock

#define ast_heap_unlock

(

h

)

__ast_heap_unlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)

Definition at line 248 of file heap.h.

Referenced by _ast_register_timing_interface(), ast_bridge_features_merge(), ast_bridge_interval_hook(), ast_timer_open(), ast_unregister_timing_interface(), bridge_channel_handle_interval(), bridge_channel_next_interval(), and hooks_remove_heap().

ast_heap_wrlock

#define ast_heap_wrlock

(

h

)

__ast_heap_wrlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)

Definition at line 246 of file heap.h.

Referenced by _ast_register_timing_interface(), ast_bridge_features_merge(), ast_bridge_interval_hook(), ast_unregister_timing_interface(), bridge_channel_handle_interval(), bridge_channel_next_interval(), and hooks_remove_heap().

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.

References __ast_rwlock_rdlock(), and ast_heap::lock.

{
   return __ast_rwlock_rdlock(file, line, func, &h->lock, "&h->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.

References __ast_rwlock_unlock(), and ast_heap::lock.

{
   return __ast_rwlock_unlock(file, line, func, &h->lock, "&h->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.

References __ast_rwlock_wrlock(), and ast_heap::lock.

{
   return __ast_rwlock_wrlock(file, line, func, &h->lock, "&h->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
	)

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

References __ast_calloc(), __ast_malloc(), 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, LOG_ERROR, and NULL.

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

_ast_heap_push()

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

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

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

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

ast_heap_destroy()

struct ast_heap* ast_heap_destroy

(

struct ast_heap *

h

)

Destroy a max heap.

Parameters

h	the heap to destroy

Returns

NULL for convenience

Since

1.6.1

Definition at line 146 of file heap.c.

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_free(h->heap);
   h->heap = NULL;

   ast_rwlock_destroy(&h->lock);

   ast_free(h);

   return NULL;
}

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.

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().

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

   return heap_get(h, index);
}

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.

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().

{
   return _ast_heap_remove(h, 1);
}

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

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

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

{
   ssize_t i = get_index(h, elm);

   if (i == -1) {
      return NULL;
   }

   return _ast_heap_remove(h, i);
}

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.

References ast_heap::cur_len.

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

{
   return h->cur_len;
}

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.

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

Referenced by AST_TEST_DEFINE().

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