Asterisk - The Open Source Telephony Project  GIT-master-1f78ee9
Macros | Typedefs | Functions
heap.h File Reference

Max Heap data structure. More...

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_heapast_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__)

◆ ast_heap_push

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

◆ 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__)

◆ ast_heap_wrlock

#define ast_heap_wrlock (   h)    __ast_heap_wrlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__)

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
elm1the first element
elm2the second element
Return values
negativeif elm1 < elm2
0if elm1 == elm2
positiveif 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
hthe heap
file,func,lineA 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.

287 {
288  return __ast_rwlock_rdlock(file, line, func, &h->lock, "&h->lock");
289 }
int __ast_rwlock_rdlock(const char *filename, int lineno, const char *func, ast_rwlock_t *t, const char *name)
Definition: lock.c:819
ast_rwlock_t lock
Definition: heap.c:37

◆ __ast_heap_unlock()

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

Unlock a heap.

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

292 {
293  return __ast_rwlock_unlock(file, line, func, &h->lock, "&h->lock");
294 }
ast_rwlock_t lock
Definition: heap.c:37
int __ast_rwlock_unlock(const char *filename, int lineno, const char *func, ast_rwlock_t *t, const char *name)
Definition: lock.c:748

◆ __ast_heap_wrlock()

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

Write-Lock a heap.

Parameters
hthe heap
file,func,lineA 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.

282 {
283  return __ast_rwlock_wrlock(file, line, func, &h->lock, "&h->lock");
284 }
ast_rwlock_t lock
Definition: heap.c:37
int __ast_rwlock_wrlock(const char *filename, int lineno, const char *func, ast_rwlock_t *t, const char *name)
Definition: lock.c:917

◆ _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_heightThe 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_fnThe function that should be used to compare elements in the heap.
index_offsetThis 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.

114 {
115  struct ast_heap *h;
116 
117  if (!cmp_fn) {
118  ast_log(LOG_ERROR, "A comparison function must be provided\n");
119  return NULL;
120  }
121 
122  if (!init_height) {
123  init_height = 8;
124  }
125 
126  h = __ast_calloc(1, sizeof(*h), file, lineno, func);
127  if (!h) {
128  return NULL;
129  }
130 
131  h->cmp_fn = cmp_fn;
133  h->avail_len = (1 << init_height) - 1;
134 
135  h->heap = __ast_malloc(h->avail_len * sizeof(void *), file, lineno, func);
136  if (!h->heap) {
137  ast_free(h);
138  return NULL;
139  }
140 
141  ast_rwlock_init(&h->lock);
142 
143  return h;
144 }
ast_heap_cmp_fn cmp_fn
Definition: heap.c:38
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func) attribute_malloc
Definition: astmm.c:1635
Definition: heap.c:36
ast_rwlock_t lock
Definition: heap.c:37
size_t avail_len
Definition: heap.c:41
#define NULL
Definition: resample.c:96
void ** heap
Definition: heap.c:42
#define ast_log
Definition: astobj2.c:42
#define LOG_ERROR
Definition: logger.h:285
#define ast_rwlock_init(rwlock)
wrapper for rwlock with tracking enabled
Definition: lock.h:222
#define ast_free(a)
Definition: astmm.h:182
ssize_t index_offset
Definition: heap.c:39
void * __ast_malloc(size_t size, const char *file, int lineno, const char *func) attribute_malloc
Definition: astmm.c:1660

◆ _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
hthe heap being added to
elmthe element being put on the heap
Return values
0success
non-zerofailure
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().

223 {
224  if (h->cur_len == h->avail_len && grow_heap(h, file, lineno, func)) {
225  return -1;
226  }
227 
228  heap_set(h, ++(h->cur_len), elm);
229 
230  bubble_up(h, h->cur_len);
231 
232  return 0;
233 }
size_t avail_len
Definition: heap.c:41
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.
Definition: heap.c:161
size_t cur_len
Definition: heap.c:40
static int bubble_up(struct ast_heap *h, int i)
Definition: heap.c:212
static void heap_set(struct ast_heap *h, int i, void *elm)
Definition: heap.c:78

◆ ast_heap_destroy()

struct ast_heap* ast_heap_destroy ( struct ast_heap h)

Destroy a max heap.

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

147 {
148  ast_free(h->heap);
149  h->heap = NULL;
150 
152 
153  ast_free(h);
154 
155  return NULL;
156 }
#define ast_rwlock_destroy(rwlock)
Definition: lock.h:231
ast_rwlock_t lock
Definition: heap.c:37
#define NULL
Definition: resample.c:96
void ** heap
Definition: heap.c:42
#define ast_free(a)
Definition: astmm.h:182

◆ ast_heap_peek()

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

Peek at an element on a heap.

Parameters
hthe heap
indexindex 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;
size = ast_heap_size(h);
for (i = 1; i <= size && (cur_obj = ast_heap_peek(h, i)); i++) {
... Do stuff with cur_obj ...
}
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().

268 {
269  if (!h->cur_len || !index || index > h->cur_len) {
270  return NULL;
271  }
272 
273  return heap_get(h, index);
274 }
static void * heap_get(struct ast_heap *h, int i)
Definition: heap.c:60
#define NULL
Definition: resample.c:96
size_t cur_len
Definition: heap.c:40

◆ ast_heap_pop()

void* ast_heap_pop ( struct ast_heap h)

Pop the max element off of the heap.

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

263 {
264  return _ast_heap_remove(h, 1);
265 }
static void * _ast_heap_remove(struct ast_heap *h, unsigned int index)
Definition: heap.c:235

◆ ast_heap_remove()

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

Remove a specific element from a heap.

Parameters
hthe heap to remove from
elmthe 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().

252 {
253  ssize_t i = get_index(h, elm);
254 
255  if (i == -1) {
256  return NULL;
257  }
258 
259  return _ast_heap_remove(h, i);
260 }
static ssize_t get_index(struct ast_heap *h, void *elm)
Definition: heap.c:65
static void * _ast_heap_remove(struct ast_heap *h, unsigned int index)
Definition: heap.c:235
#define NULL
Definition: resample.c:96

◆ ast_heap_size()

size_t ast_heap_size ( struct ast_heap h)

Get the current size of a heap.

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

277 {
278  return h->cur_len;
279 }
size_t cur_len
Definition: heap.c:40

◆ ast_heap_verify()

int ast_heap_verify ( struct ast_heap h)

Verify that a heap has been properly constructed.

Parameters
ha heap
Return values
0success
non-zerofailure
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().

89 {
90  unsigned int i;
91 
92  for (i = 1; i <= (h->cur_len / 2); i++) {
93  int l = left_node(i);
94  int r = right_node(i);
95 
96  if (l <= h->cur_len) {
97  if (h->cmp_fn(heap_get(h, i), heap_get(h, l)) < 0) {
98  return -1;
99  }
100  }
101 
102  if (r <= h->cur_len) {
103  if (h->cmp_fn(heap_get(h, i), heap_get(h, r)) < 0) {
104  return -1;
105  }
106  }
107  }
108 
109  return 0;
110 }
ast_heap_cmp_fn cmp_fn
Definition: heap.c:38
static void * heap_get(struct ast_heap *h, int i)
Definition: heap.c:60
size_t cur_len
Definition: heap.c:40
static int right_node(int i)
Definition: heap.c:50
static int left_node(int i)
Definition: heap.c:45