heap.c File Reference

Max Heap data structure. More...

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

Include dependency graph for heap.c:

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. 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...
static void *	_ast_heap_remove (struct ast_heap *h, unsigned int index)
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...
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, const char *file, int lineno, const char *func)
	Add a row of additional storage for the heap. More...
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 russe.nosp@m.ll@d.nosp@m.igium.nosp@m..com

Definition in file heap.c.

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

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

static

Definition at line 235 of file heap.c.

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

Referenced by ast_heap_pop(), and ast_heap_remove().

{
   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)--));
   index = bubble_up(h, index);
   max_heapify(h, index);

   return ret;
}

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

bubble_up()

static int bubble_up ( struct ast_heap *  h, int  i  )

static

Definition at line 212 of file heap.c.

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

Referenced by _ast_heap_push(), and _ast_heap_remove().

{
   while (i > 1 && h->cmp_fn(heap_get(h, parent_node(i)), heap_get(h, i)) < 0) {
      heap_swap(h, i, parent_node(i));
      i = parent_node(i);
   }

   return i;
}

get_index()

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

inlinestatic

Definition at line 65 of file heap.c.

References ast_heap::index_offset.

Referenced by ast_heap_remove().

{
   ssize_t *index;

   if (h->index_offset < 0) {
      return -1;
   }

   index = elm + h->index_offset;

   return *index;
}

grow_heap()

static int grow_heap ( struct ast_heap *  h, const char *  file, int  lineno, const char *  func  )

static

Add a row of additional storage for the heap.

Definition at line 161 of file heap.c.

References __ast_realloc(), ast_heap::avail_len, and ast_heap::heap.

Referenced by _ast_heap_push().

{
   void **new_heap;
   size_t new_len = h->avail_len * 2 + 1;

   new_heap = __ast_realloc(h->heap, new_len * sizeof(void *), file, lineno, func);
   if (!new_heap) {
      return -1;
   }
   h->heap = new_heap;
   h->avail_len = new_len;

   return 0;
}

heap_get()

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

inlinestatic

Definition at line 60 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().

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

heap_set()

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

inlinestatic

Definition at line 78 of file heap.c.

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

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

{
   h->heap[i - 1] = elm;

   if (h->index_offset >= 0) {
      ssize_t *index = elm + h->index_offset;
      *index = i;
   }
}

heap_swap()

static void heap_swap ( struct ast_heap *  h, int  i, int  j  )

inlinestatic

Definition at line 176 of file heap.c.

References heap_get(), heap_set(), and tmp().

Referenced by bubble_up(), and max_heapify().

{
   void *tmp;

   tmp = heap_get(h, i);
   heap_set(h, i, heap_get(h, j));
   heap_set(h, j, tmp);
}

left_node()

static int left_node ( int  i )

inlinestatic

Definition at line 45 of file heap.c.

Referenced by ast_heap_verify(), and max_heapify().

{
   return 2 * i;
}

max_heapify()

static void max_heapify ( struct ast_heap *  h, int  i  )

inlinestatic

Definition at line 185 of file heap.c.

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

Referenced by _ast_heap_remove().

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

parent_node()

static int parent_node ( int  i )

inlinestatic

Definition at line 55 of file heap.c.

Referenced by bubble_up().

{
   return i / 2;
}

right_node()

static int right_node ( int  i )

inlinestatic

Definition at line 50 of file heap.c.

Referenced by ast_heap_verify(), and max_heapify().

{
   return 2 * i + 1;
}