13     pheap_t *heap = calloc(1, sizeof(pheap_t));  in ph_create()  local
14     heap->nodes = calloc(max_nodes, sizeof(pheap_node_t));  in ph_create()
15     ph_post_alloc_init(heap, max_nodes, comparator, user_data);  in ph_create()
16     return heap;  in ph_create()
19 void ph_post_alloc_init(pheap_t *heap, uint max_nodes, pheap_comparator comparator, void *user_data…  in ph_post_alloc_init()  argument
21     heap->max_nodes = (pheap_node_id_t) max_nodes;  in ph_post_alloc_init()
22     heap->comparator = comparator;  in ph_post_alloc_init()
23     heap->user_data = user_data;  in ph_post_alloc_init()
24     ph_clear(heap);  in ph_post_alloc_init()
27 void ph_clear(pheap_t *heap) {  in ph_clear()  argument
28     heap->root_id = 0;  in ph_clear()
29     heap->free_head_id = 1;  in ph_clear()
30     heap->free_tail_id = heap->max_nodes;  in ph_clear()
31     for(pheap_node_id_t i = 1; i < heap->max_nodes; i++) {  in ph_clear()
32         ph_get_node(heap, i)->sibling = (pheap_node_id_t)(i + 1);  in ph_clear()
34     ph_get_node(heap, heap->max_nodes)->sibling = 0;  in ph_clear()
37 void ph_destroy(pheap_t *heap) {  in ph_destroy()  argument
38     free(heap->nodes);  in ph_destroy()
39     free(heap);  in ph_destroy()
42 pheap_node_id_t ph_merge_two_pass(pheap_t *heap, pheap_node_id_t id) {  in ph_merge_two_pass()  argument
43     if (!id || !ph_get_node(heap, id)->sibling) {  in ph_merge_two_pass()
48         b = ph_get_node(heap, id)->sibling;  in ph_merge_two_pass()
49         new_node = ph_get_node(heap, b)->sibling;  in ph_merge_two_pass()
50         ph_get_node(heap, a)->sibling = ph_get_node(heap, b)->sibling = 0;  in ph_merge_two_pass()
51         return ph_merge_nodes(heap, ph_merge_nodes(heap, a, b), ph_merge_two_pass(heap, new_node));  in ph_merge_two_pass()
55 static pheap_node_id_t ph_remove_any_head(pheap_t *heap, pheap_node_id_t root_id, bool free) {  in ph_remove_any_head()  argument
58     assert(!ph_get_node(heap, root_id)->sibling);  in ph_remove_any_head()
59     assert(!ph_get_node(heap, root_id)->parent);  in ph_remove_any_head()
60     pheap_node_id_t new_root_id = ph_merge_two_pass(heap, ph_get_node(heap, root_id)->child);  in ph_remove_any_head()
62         if (heap->free_tail_id) {  in ph_remove_any_head()
63             ph_get_node(heap, heap->free_tail_id)->sibling = root_id;  in ph_remove_any_head()
65         if (!heap->free_head_id) {  in ph_remove_any_head()
66             assert(!heap->free_tail_id);  in ph_remove_any_head()
67             heap->free_head_id = root_id;  in ph_remove_any_head()
69         heap->free_tail_id = root_id;  in ph_remove_any_head()
71     if (new_root_id) ph_get_node(heap, new_root_id)->parent = 0;  in ph_remove_any_head()
72     ph_get_node(heap, root_id)->sibling = 0;  in ph_remove_any_head()
76 pheap_node_id_t ph_remove_head(pheap_t *heap, bool free) {  in ph_remove_head()  argument
77     pheap_node_id_t old_root_id = ph_peek_head(heap);  in ph_remove_head()
78     heap->root_id = ph_remove_any_head(heap, old_root_id, free);  in ph_remove_head()
82 bool ph_remove_and_free_node(pheap_t *heap, pheap_node_id_t id) {  in ph_remove_and_free_node()  argument
85     if (id == heap->root_id) {  in ph_remove_and_free_node()
86         ph_remove_and_free_head(heap);  in ph_remove_and_free_node()
90     pheap_node_t *node = ph_get_node(heap, id);  in ph_remove_and_free_node()
92     pheap_node_t *parent = ph_get_node(heap, node->parent);  in ph_remove_and_free_node()
99             pheap_node_t *prev_sibling = ph_get_node(heap, prev_sibling_id);  in ph_remove_and_free_node()
112     pheap_node_id_t new_sub_tree = ph_remove_any_head(heap, id, true);  in ph_remove_and_free_node()
113     assert(new_sub_tree != heap->root_id);  in ph_remove_and_free_node()
114     heap->root_id = ph_merge_nodes(heap, heap->root_id, new_sub_tree);  in ph_remove_and_free_node()
118 static uint ph_dump_node(pheap_t *heap, pheap_node_id_t id, void (*dump_key)(pheap_node_id_t, void …  in ph_dump_node()  argument
125         pheap_node_t *node = ph_get_node(heap, id);  in ph_dump_node()
129         count += ph_dump_node(heap, node->child, dump_key, user_data, indent + 1);  in ph_dump_node()
130         count += ph_dump_node(heap, node->sibling, dump_key, user_data, indent);  in ph_dump_node()
135 void ph_dump(pheap_t *heap, void (*dump_key)(pheap_node_id_t, void *), void *user_data) {  in ph_dump()  argument
136     uint count = ph_dump_node(heap, heap->root_id, dump_key, user_data, 0);  in ph_dump()