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 
30 static struct pnode *pnode_merge(
31  struct pnode *n1, struct pnode *n2, pheap_cmp_t *cmp);
32 static struct pnode *pnode_merge_pairs(struct pnode *node, pheap_cmp_t *cmp);
33 
34 void
35 pheap_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 
62 void
63 pheap_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 
95 struct pnode *
96 pheap_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;
114  parent = parent->parent;
115  }
116  }
117  }
118  return node;
119 }
120 
121 int
122 pheap_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 
134 static struct pnode *
135 pnode_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 
156 static struct pnode *
157 pnode_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