Lely core libraries 2.3.4
pheap.c
Go to the documentation of this file.
1
24#include "util.h"
25#define LELY_UTIL_PHEAP_INLINE extern inline
26#include <lely/util/pheap.h>
27
28#include <assert.h>
29
30static struct pnode *pnode_merge(
31 struct pnode *n1, struct pnode *n2, pheap_cmp_t *cmp);
32static struct pnode *pnode_merge_pairs(struct pnode *node, pheap_cmp_t *cmp);
33
34void
35pheap_insert(struct pheap *heap, struct pnode *node)
36{
37 assert(heap);
38 assert(heap->cmp);
39 assert(node);
40
41 if (!heap->root) {
42 node->parent = NULL;
43 node->next = NULL;
44 node->child = NULL;
45 heap->root = node;
46 } else if (heap->cmp(node->key, heap->root->key) < 0) {
47 node->parent = NULL;
48 node->next = NULL;
49 node->child = heap->root;
50 heap->root->parent = node;
51 heap->root = node;
52 } else {
53 node->parent = heap->root;
54 node->next = heap->root->child;
55 node->child = NULL;
56 heap->root->child = node;
57 }
58
59 heap->num_nodes++;
60}
61
62void
63pheap_remove(struct pheap *heap, struct pnode *node)
64{
65 assert(heap);
66 assert(heap->cmp);
67 assert(node);
68
69 if (node->parent) {
70 // Obtain the address of the pointer to this node in the parent
71 // or previous sibling.
72 struct pnode **pnode = &node->parent->child;
73 while (*pnode != node)
74 pnode = &(*pnode)->next;
75 // Remove the node from the list.
76 *pnode = node->next;
77 } else {
78 heap->root = NULL;
79 }
80
81 node->parent = NULL;
82 node->next = NULL;
83 struct pnode *child = node->child;
84 node->child = NULL;
85
86 if (child) {
87 child = pnode_merge_pairs(child, heap->cmp);
88 heap->root = pnode_merge(heap->root, child, heap->cmp);
89 heap->root->parent = NULL;
90 }
91
92 heap->num_nodes--;
93}
94
95struct pnode *
96pheap_find(const struct pheap *heap, const void *key)
97{
98 assert(heap);
99 assert(heap->cmp);
100
101 struct pnode *node = heap->root;
102 struct pnode *parent = NULL;
103 while (node) {
104 int c = heap->cmp(key, node->key);
105 if (!c) {
106 return node;
107 } else if (c > 0 && node->child) {
108 parent = node;
109 node = node->child;
110 } else {
111 node = node->next;
112 while (!node && parent) {
113 node = parent->next;
115 }
116 }
117 }
118 return node;
119}
120
121int
122pheap_contains(const struct pheap *heap, const struct pnode *node)
123{
124 assert(heap);
125
126 while (node) {
127 if (node == heap->root)
128 return 1;
129 node = node->parent;
130 }
131 return 0;
132}
133
134static struct pnode *
135pnode_merge(struct pnode *n1, struct pnode *n2, pheap_cmp_t *cmp)
136{
137 assert(n2);
138
139 if (!n1)
140 return n2;
141
142 assert(cmp);
143 if (cmp(n1->key, n2->key) >= 0) {
144 struct pnode *tmp = n1;
145 n1 = n2;
146 n2 = tmp;
147 }
148
149 n2->parent = n1;
150 n2->next = n1->child;
151 n1->child = n2;
152
153 return n1;
154}
155
156static struct pnode *
157pnode_merge_pairs(struct pnode *node, pheap_cmp_t *cmp)
158{
159 assert(node);
160
161 while (node->next) {
162 struct pnode *next = node->next->next;
163 node->next->next = NULL;
164 node = pnode_merge(node, node->next, cmp);
165 node->next = next;
166 }
167 return node;
168}
int pheap_contains(const struct pheap *heap, const struct pnode *node)
Checks if a node is part of a pairing heap.
Definition: pheap.c:122
void pheap_insert(struct pheap *heap, struct pnode *node)
Inserts a node into a pairing heap.
Definition: pheap.c:35
struct pnode * pheap_find(const struct pheap *heap, const void *key)
Finds a node in a pairing heap.
Definition: pheap.c:96
void pheap_remove(struct pheap *heap, struct pnode *node)
Removes a node from a pairing heap.
Definition: pheap.c:63
This header file is part of the utilities library; it contains the pairing heap declarations.
int pheap_cmp_t(const void *p1, const void *p2)
The type of a comparison function suitable for use in a paring heap.
Definition: pheap.h:84
This is the internal header file of the utilities library.
A pairing heap.
Definition: pheap.h:87
pheap_cmp_t * cmp
A pointer to the function used to compare two keys.
Definition: pheap.h:89
struct pnode * root
A pointer to the root node of the heap.
Definition: pheap.h:91
size_t num_nodes
The number of nodes stored in the heap.
Definition: pheap.h:93
A node in a pairing heap.
Definition: pheap.h:52
struct pnode * parent
A pointer to the parent node.
Definition: pheap.h:60
struct pnode * child
A pointer to the first child node.
Definition: pheap.h:64
const void * key
A pointer to the key of this node.
Definition: pheap.h:58
struct pnode * next
A pointer to the next sibling node.
Definition: pheap.h:62