Go to the source code of this file.
Macros | |
| #define | mutex_lock(m) (void)0 |
| #define | mutex_unlock(m) (void)0 |
| #define | mutex_trylock(m) (void)0 |
| #define | mutex_init(m) ((m)=123456) |
| #define | Left(x) (2 * (x) + 1) |
| #define | Right(x) (2 * (x) + 2) |
| #define | Parent(x) ((int)((x)-1)/2) |
| #define | Threshold 10000 |
| #define | NormalRate 2 |
| #define | SlowRate 1.5 |
| #define | MinSize 32 |
Functions | |
| static void | _heap_ify_up (heap *hp, heap_node *elm) |
| static void | _heap_ify_down (heap *hp, heap_node *elm) |
| static int | _heap_should_grow (heap *hp) |
| static void | _heap_grow (heap *hp) |
| static void | _heap_swap_element (heap *hp, heap_node *elm1, heap_node *elm2) |
| static int | _heap_node_exist (heap *hp, int id) |
| heap * | new_heap (int initSize, heap_key_func gen_key) |
| void | delete_heap (heap *hp) |
| heap_node * | heap_insert (heap *hp, void *dat) |
| heap_t | heap_delete (heap *hp, heap_node *elm) |
| heap_key | heap_gen_key (heap *hp, heap_t dat) |
| heap_t | heap_extractmin (heap *hp) |
| heap_t | heap_extractlast (heap *hp) |
| heap_t | heap_update (heap *hp, heap_node *elm, void *dat) |
| void * | heap_peepmin (heap *hp) |
| heap_key | heap_peepminkey (heap *hp) |
| heap_key | heap_peepkey (heap *hp, int n) |
| void * | heap_peep (heap *hp, int n) |
| int | heap_nodes (heap *hp) |
| int | heap_empty (heap *hp) |
| static void | heap_print_inorder (heap *hp, int id) |
| int | verify_heap_property (heap *hp) |
Macro Definition Documentation
◆ Left
◆ MinSize
◆ mutex_init
◆ mutex_lock
◆ mutex_trylock
◆ mutex_unlock
◆ NormalRate
◆ Parent
◆ Right
◆ SlowRate
◆ Threshold
Function Documentation
◆ _heap_grow()
|
static |
Definition at line 392 of file heap.c.
References _heap::nodes, NormalRate, _heap::size, SlowRate, Threshold, and xrealloc().
Referenced by heap_insert().
◆ _heap_ify_down()
Definition at line 319 of file heap.c.
References _heap_node_exist(), _heap_swap_element(), assert, _heap_node::id, _heap_node::key, Left, _heap::nodes, and Right.
Referenced by heap_delete(), and heap_update().
◆ _heap_ify_up()
Definition at line 352 of file heap.c.
References _heap_swap_element(), _heap_node::id, _heap_node::key, _heap::nodes, and Parent.
Referenced by heap_delete(), heap_insert(), and heap_update().
◆ _heap_node_exist()
Definition at line 409 of file heap.c.
References _heap::last, _heap::nodes, and NULL.
Referenced by _heap_ify_down(), heap_delete(), heap_extractlast(), heap_peep(), heap_peepkey(), heap_peepmin(), heap_peepminkey(), and verify_heap_property().
◆ _heap_should_grow()
Definition at line 381 of file heap.c.
References _heap::last, and _heap::size.
Referenced by heap_insert().
◆ _heap_swap_element()
Definition at line 368 of file heap.c.
References _heap_node::id, and _heap::nodes.
Referenced by _heap_ify_down(), _heap_ify_up(), and heap_delete().
◆ delete_heap()
| void delete_heap | ( | heap * | hp | ) |
Definition at line 95 of file heap.c.
References assert, _heap::last, _heap::nodes, NULL, and xfree.
◆ heap_delete()
Definition at line 142 of file heap.c.
References _heap_ify_down(), _heap_ify_up(), _heap_node_exist(), _heap_swap_element(), assert, _heap_node::data, heap_extractlast(), _heap_node::id, _heap_node::key, _heap::last, and _heap::nodes.
Referenced by heap_extractmin(), and heap_remove().
◆ heap_empty()
◆ heap_extractlast()
Definition at line 210 of file heap.c.
References _heap_node_exist(), assert, _heap_node::data, _heap::last, _heap::nodes, and xfree.
Referenced by heap_delete().
◆ heap_extractmin()
Definition at line 188 of file heap.c.
References _heap_node::data, heap_delete(), _heap::last, _heap::lock, mutex_lock, mutex_unlock, _heap::nodes, and NULL.
Referenced by heap_purgeNext().
◆ heap_gen_key()
Definition at line 177 of file heap.c.
References _heap::age, and _heap::gen_key.
Referenced by heap_insert(), and heap_update().
◆ heap_insert()
Definition at line 117 of file heap.c.
References _heap_grow(), _heap_ify_up(), _heap_should_grow(), _heap_node::data, heap_gen_key(), _heap_node::id, _heap_node::key, _heap::last, _heap::nodes, and xmalloc.
Referenced by heap_add(), and heap_purgeDone().
◆ heap_nodes()
◆ heap_peep()
Definition at line 281 of file heap.c.
References _heap_node_exist(), assert, _heap_node::data, and _heap::nodes.
Referenced by heap_walkNext().
◆ heap_peepkey()
Definition at line 268 of file heap.c.
References _heap_node_exist(), assert, _heap_node::key, and _heap::nodes.
◆ heap_peepmin()
| void * heap_peepmin | ( | heap * | hp | ) |
Definition at line 247 of file heap.c.
References _heap_node_exist(), assert, _heap_node::data, and _heap::nodes.
◆ heap_peepminkey()
Definition at line 257 of file heap.c.
References _heap_node_exist(), assert, _heap_node::key, and _heap::nodes.
Referenced by heap_purgeNext().
◆ heap_print_inorder()
Definition at line 424 of file heap.c.
References _heap_node::key, last, and _heap::nodes.
Referenced by verify_heap_property().
◆ heap_update()
Definition at line 228 of file heap.c.
References _heap_ify_down(), _heap_ify_up(), _heap_node::data, heap_gen_key(), _heap_node::id, _heap_node::key, and _heap::nodes.
Referenced by heap_referenced().
◆ new_heap()
| heap * new_heap | ( | int | initSize, |
| heap_key_func | gen_key | ||
| ) |
Definition at line 72 of file heap.c.
References _heap::age, assert, _heap::gen_key, _heap::last, MinSize, _heap::nodes, NULL, _heap::size, xcalloc(), and xmalloc.
Referenced by createRemovalPolicy_heap().
◆ verify_heap_property()
Definition at line 436 of file heap.c.
References _heap_node_exist(), heap_print_inorder(), _heap_node::key, _heap::last, Left, _heap::nodes, and Right.