Wed Jan 8 2020 09:50:13

Asterisk developer's documentation


heap.c File Reference

Max Heap data structure. More...

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

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...
 
static void * _ast_heap_remove (struct ast_heap *h, unsigned int index)
 
struct ast_heapast_heap_create (unsigned int init_height, ast_heap_cmp_fn cmp_fn, ssize_t index_offset)
 Create a max 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...
 
int ast_heap_push (struct ast_heap *h, void *elm)
 Push an element on to a 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)
 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

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

Read-Lock a heap.

Parameters
hthe 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 319 of file heap.c.

References __ast_rwlock_rdlock(), and ast_heap::lock.

320 {
321  return __ast_rwlock_rdlock(file, line, func, &h->lock, "&h->lock");
322 }
int __ast_rwlock_rdlock(const char *filename, int lineno, const char *func, ast_rwlock_t *t, const char *name)
Definition: lock.c:832
ast_rwlock_t lock
Definition: heap.c:39
int __ast_heap_unlock ( struct ast_heap h,
const char *  file,
const char *  func,
int  line 
)

Unlock a heap.

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

Definition at line 324 of file heap.c.

References __ast_rwlock_unlock(), and ast_heap::lock.

325 {
326  return __ast_rwlock_unlock(file, line, func, &h->lock, "&h->lock");
327 }
ast_rwlock_t lock
Definition: heap.c:39
int __ast_rwlock_unlock(const char *filename, int lineno, const char *func, ast_rwlock_t *t, const char *name)
Definition: lock.c:746
int __ast_heap_wrlock ( struct ast_heap h,
const char *  file,
const char *  func,
int  line 
)

Write-Lock a heap.

Parameters
hthe 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 314 of file heap.c.

References __ast_rwlock_wrlock(), and ast_heap::lock.

315 {
316  return __ast_rwlock_wrlock(file, line, func, &h->lock, "&h->lock");
317 }
ast_rwlock_t lock
Definition: heap.c:39
int __ast_rwlock_wrlock(const char *filename, int lineno, const char *func, ast_rwlock_t *t, const char *name)
Definition: lock.c:959
static void* _ast_heap_remove ( struct ast_heap h,
unsigned int  index 
)
static

Definition at line 268 of file heap.c.

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

Referenced by ast_heap_pop(), and ast_heap_remove().

269 {
270  void *ret;
271 
272  if (!index || index > h->cur_len) {
273  return NULL;
274  }
275 
276  ret = heap_get(h, index);
277  heap_set(h, index, heap_get(h, (h->cur_len)--));
278  index = bubble_up(h, index);
279  max_heapify(h, index);
280 
281  return ret;
282 }
static void max_heapify(struct ast_heap *h, int i)
Definition: heap.c:210
static void * heap_get(struct ast_heap *h, int i)
Definition: heap.c:62
size_t cur_len
Definition: heap.c:42
static int bubble_up(struct ast_heap *h, int i)
Definition: heap.c:237
static void heap_set(struct ast_heap *h, int i, void *elm)
Definition: heap.c:80
struct ast_heap* ast_heap_create ( unsigned int  init_height,
ast_heap_cmp_fn  cmp_fn,
ssize_t  index_offset 
)

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

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

121 {
122  struct ast_heap *h;
123 
124  if (!cmp_fn) {
125  ast_log(LOG_ERROR, "A comparison function must be provided\n");
126  return NULL;
127  }
128 
129  if (!init_height) {
130  init_height = 8;
131  }
132 
133  if (!(h =
134 #ifdef MALLOC_DEBUG
135  __ast_calloc(1, sizeof(*h), file, lineno, func)
136 #else
137  ast_calloc(1, sizeof(*h))
138 #endif
139  )) {
140  return NULL;
141  }
142 
143  h->cmp_fn = cmp_fn;
145  h->avail_len = (1 << init_height) - 1;
146 
147  if (!(h->heap =
148 #ifdef MALLOC_DEBUG
149  __ast_calloc(1, h->avail_len * sizeof(void *), file, lineno, func)
150 #else
151  ast_calloc(1, h->avail_len * sizeof(void *))
152 #endif
153  )) {
154  ast_free(h);
155  return NULL;
156  }
157 
158  ast_rwlock_init(&h->lock);
159 
160  return h;
161 }
ast_heap_cmp_fn cmp_fn
Definition: heap.c:40
Definition: heap.c:38
ast_rwlock_t lock
Definition: heap.c:39
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func)
size_t avail_len
Definition: heap.c:43
void ** heap
Definition: heap.c:44
#define LOG_ERROR
Definition: logger.h:155
#define ast_rwlock_init(rwlock)
wrapper for rwlock with tracking enabled
Definition: lock.h:190
void ast_log(int level, const char *file, int line, const char *function, const char *fmt,...)
Used for sending a log message This is the standard logger function. Probably the only way you will i...
Definition: logger.c:1207
#define ast_free(a)
Definition: astmm.h:97
#define ast_calloc(a, b)
Definition: astmm.h:82
ssize_t index_offset
Definition: heap.c:41
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 163 of file heap.c.

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

Referenced by load_resource_list(), sched_context_destroy(), and timing_shutdown().

164 {
165  ast_free(h->heap);
166  h->heap = NULL;
167 
169 
170  ast_free(h);
171 
172  return NULL;
173 }
#define ast_rwlock_destroy(rwlock)
Definition: lock.h:199
ast_rwlock_t lock
Definition: heap.c:39
void ** heap
Definition: heap.c:44
#define ast_free(a)
Definition: astmm.h:97
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 300 of file heap.c.

References ast_heap::cur_len, and heap_get().

Referenced by ast_sched_dump(), ast_sched_report(), ast_sched_runq(), ast_sched_wait(), and ast_timer_open().

301 {
302  if (!h->cur_len || !index || index > h->cur_len) {
303  return NULL;
304  }
305 
306  return heap_get(h, index);
307 }
static void * heap_get(struct ast_heap *h, int i)
Definition: heap.c:62
size_t cur_len
Definition: heap.c:42
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 295 of file heap.c.

References _ast_heap_remove().

Referenced by ast_sched_runq(), load_resource_list(), and sched_context_destroy().

296 {
297  return _ast_heap_remove(h, 1);
298 }
static void * _ast_heap_remove(struct ast_heap *h, unsigned int index)
Definition: heap.c:268
int ast_heap_push ( struct ast_heap h,
void *  elm 
)

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

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

Referenced by _ast_register_timing_interface(), load_resource(), and schedule().

252 {
253  if (h->cur_len == h->avail_len && grow_heap(h
254 #ifdef MALLOC_DEBUG
255  , file, lineno, func
256 #endif
257  )) {
258  return -1;
259  }
260 
261  heap_set(h, ++(h->cur_len), elm);
262 
263  bubble_up(h, h->cur_len);
264 
265  return 0;
266 }
static int grow_heap(struct ast_heap *h)
Add a row of additional storage for the heap.
Definition: heap.c:178
size_t avail_len
Definition: heap.c:43
size_t cur_len
Definition: heap.c:42
static int bubble_up(struct ast_heap *h, int i)
Definition: heap.c:237
static void heap_set(struct ast_heap *h, int i, void *elm)
Definition: heap.c:80
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 284 of file heap.c.

References _ast_heap_remove(), and get_index().

Referenced by ast_sched_del(), and ast_unregister_timing_interface().

285 {
286  ssize_t i = get_index(h, elm);
287 
288  if (i == -1) {
289  return NULL;
290  }
291 
292  return _ast_heap_remove(h, i);
293 }
static ssize_t get_index(struct ast_heap *h, void *elm)
Definition: heap.c:67
static void * _ast_heap_remove(struct ast_heap *h, unsigned int index)
Definition: heap.c:268
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 309 of file heap.c.

References ast_heap::cur_len.

Referenced by ast_sched_dump(), and ast_sched_report().

310 {
311  return h->cur_len;
312 }
size_t cur_len
Definition: heap.c:42
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 90 of file heap.c.

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

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

Definition at line 237 of file heap.c.

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

Referenced by _ast_heap_remove(), and ast_heap_push().

238 {
239  while (i > 1 && h->cmp_fn(heap_get(h, parent_node(i)), heap_get(h, i)) < 0) {
240  heap_swap(h, i, parent_node(i));
241  i = parent_node(i);
242  }
243 
244  return i;
245 }
ast_heap_cmp_fn cmp_fn
Definition: heap.c:40
static void * heap_get(struct ast_heap *h, int i)
Definition: heap.c:62
static int parent_node(int i)
Definition: heap.c:57
static void heap_swap(struct ast_heap *h, int i, int j)
Definition: heap.c:201
static ssize_t get_index ( struct ast_heap h,
void *  elm 
)
inlinestatic

Definition at line 67 of file heap.c.

References ast_heap::index_offset.

Referenced by ast_heap_remove().

68 {
69  ssize_t *index;
70 
71  if (h->index_offset < 0) {
72  return -1;
73  }
74 
75  index = elm + h->index_offset;
76 
77  return *index;
78 }
ssize_t index_offset
Definition: heap.c:41
static int grow_heap ( struct ast_heap h)
static

Add a row of additional storage for the heap.

Definition at line 178 of file heap.c.

References __ast_realloc(), and ast_realloc.

Referenced by ast_heap_push().

183 {
184  void **new_heap;
185  size_t new_len = h->avail_len * 2 + 1;
186 
187 #ifdef MALLOC_DEBUG
188  new_heap = __ast_realloc(h->heap, new_len * sizeof(void *), file, lineno, func);
189 #else
190  new_heap = ast_realloc(h->heap, new_len * sizeof(void *));
191 #endif
192  if (!new_heap) {
193  return -1;
194  }
195  h->heap = new_heap;
196  h->avail_len = new_len;
197 
198  return 0;
199 }
size_t avail_len
Definition: heap.c:43
void ** heap
Definition: heap.c:44
void * __ast_realloc(void *ptr, size_t size, const char *file, int lineno, const char *func)
#define ast_realloc(a, b)
Definition: astmm.h:103
static void* heap_get ( struct ast_heap h,
int  i 
)
inlinestatic

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

63 {
64  return h->heap[i - 1];
65 }
void ** heap
Definition: heap.c:44
static void heap_set ( struct ast_heap h,
int  i,
void *  elm 
)
inlinestatic

Definition at line 80 of file heap.c.

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

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

81 {
82  h->heap[i - 1] = elm;
83 
84  if (h->index_offset >= 0) {
85  ssize_t *index = elm + h->index_offset;
86  *index = i;
87  }
88 }
void ** heap
Definition: heap.c:44
ssize_t index_offset
Definition: heap.c:41
static void heap_swap ( struct ast_heap h,
int  i,
int  j 
)
inlinestatic

Definition at line 201 of file heap.c.

References heap_get(), and heap_set().

Referenced by bubble_up(), and max_heapify().

202 {
203  void *tmp;
204 
205  tmp = heap_get(h, i);
206  heap_set(h, i, heap_get(h, j));
207  heap_set(h, j, tmp);
208 }
static void * heap_get(struct ast_heap *h, int i)
Definition: heap.c:62
static void heap_set(struct ast_heap *h, int i, void *elm)
Definition: heap.c:80
static int left_node ( int  i)
inlinestatic

Definition at line 47 of file heap.c.

Referenced by ast_heap_verify(), and max_heapify().

48 {
49  return 2 * i;
50 }
static void max_heapify ( struct ast_heap h,
int  i 
)
inlinestatic

Definition at line 210 of file heap.c.

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

Referenced by _ast_heap_remove().

211 {
212  for (;;) {
213  int l = left_node(i);
214  int r = right_node(i);
215  int max;
216 
217  if (l <= h->cur_len && h->cmp_fn(heap_get(h, l), heap_get(h, i)) > 0) {
218  max = l;
219  } else {
220  max = i;
221  }
222 
223  if (r <= h->cur_len && h->cmp_fn(heap_get(h, r), heap_get(h, max)) > 0) {
224  max = r;
225  }
226 
227  if (max == i) {
228  break;
229  }
230 
231  heap_swap(h, i, max);
232 
233  i = max;
234  }
235 }
ast_heap_cmp_fn cmp_fn
Definition: heap.c:40
static void * heap_get(struct ast_heap *h, int i)
Definition: heap.c:62
size_t cur_len
Definition: heap.c:42
static int right_node(int i)
Definition: heap.c:52
static void heap_swap(struct ast_heap *h, int i, int j)
Definition: heap.c:201
static int left_node(int i)
Definition: heap.c:47
static int parent_node ( int  i)
inlinestatic

Definition at line 57 of file heap.c.

Referenced by bubble_up().

58 {
59  return i / 2;
60 }
static int right_node ( int  i)
inlinestatic

Definition at line 52 of file heap.c.

Referenced by ast_heap_verify(), and max_heapify().

53 {
54  return 2 * i + 1;
55 }