Lely core libraries  2.2.5
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 static struct pnode *pnode_find(
34  struct pnode *node, const void *key, pheap_cmp_t *cmp);
35 
36 void
37 pheap_insert(struct pheap *heap, struct pnode *node)
38 {
39  assert(heap);
40  assert(heap->cmp);
41  assert(node);
42 
43  if (!heap->root) {
44  node->parent = NULL;
45  node->child = NULL;
46  node->next = NULL;
47  heap->root = node;
48  } else if (heap->cmp(node->key, heap->root->key) < 0) {
49  node->parent = NULL;
50  node->child = heap->root;
51  node->next = NULL;
52  heap->root->parent = node;
53  heap->root = node;
54  } else {
55  node->parent = heap->root;
56  node->child = NULL;
57  node->next = heap->root->child;
58  heap->root->child = node;
59  }
60 
61  heap->num_nodes++;
62 }
63 
64 void
65 pheap_remove(struct pheap *heap, struct pnode *node)
66 {
67  assert(heap);
68  assert(heap->cmp);
69  assert(node);
70 
71  if (node->parent) {
72  struct pnode **pchild = &node->parent->child;
73  while (*pchild != node)
74  pchild = &(*pchild)->next;
75  *pchild = node->next;
76  node->next = NULL;
77  } else {
78  heap->root = NULL;
79  }
80 
81  node->child = pnode_merge_pairs(node->child, heap->cmp);
82 
83  heap->root = pnode_merge(heap->root, node->child, heap->cmp);
84  if (heap->root)
85  heap->root->parent = NULL;
86 
87  heap->num_nodes--;
88 }
89 
90 struct pnode *
91 pheap_find(const struct pheap *heap, const void *key)
92 {
93  assert(heap);
94 
95  return pnode_find(heap->root, key, heap->cmp);
96 }
97 
98 static struct pnode *
99 pnode_merge(struct pnode *n1, struct pnode *n2, pheap_cmp_t *cmp)
100 {
101  if (!n1)
102  return n2;
103  if (!n2)
104  return n1;
105 
106  assert(cmp);
107  if (cmp(n1->key, n2->key) < 0) {
108  n2->parent = n1;
109  n2->next = n1->child;
110  n1->child = n2;
111  return n1;
112  } else {
113  n1->parent = n2;
114  n1->next = n2->child;
115  n2->child = n1;
116  return n2;
117  }
118 }
119 
120 static struct pnode *
121 pnode_merge_pairs(struct pnode *node, pheap_cmp_t *cmp)
122 {
123  if (!node)
124  return NULL;
125 
126  if (!node->next)
127  return node;
128 
129  struct pnode *next = pnode_merge_pairs(node->next->next, cmp);
130  node = pnode_merge(node, node->next, cmp);
131  node = pnode_merge(node, next, cmp);
132  node->next = NULL;
133 
134  return node;
135 }
136 
137 static struct pnode *
138 pnode_find(struct pnode *node, const void *key, pheap_cmp_t *cmp)
139 {
140  assert(cmp);
141 
142  for (; node; node = node->next) {
143  int c = cmp(key, node->key);
144  if (!c) {
145  return node;
146  } else if (c > 0) {
147  struct pnode *child = pnode_find(node->child, key, cmp);
148  if (child)
149  return child;
150  }
151  }
152 
153  return NULL;
154 }
void pheap_insert(struct pheap *heap, struct pnode *node)
Inserts a node into a pairing heap.
Definition: pheap.c:37
struct pnode * pheap_find(const struct pheap *heap, const void *key)
Finds a node in a pairing heap.
Definition: pheap.c:91
void pheap_remove(struct pheap *heap, struct pnode *node)
Removes a node from a pairing heap.
Definition: pheap.c:65
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:83
This is the internal header file of the utilities library.
A pairing heap.
Definition: pheap.h:86
pheap_cmp_t * cmp
A pointer to the function used to compare two keys.
Definition: pheap.h:88
struct pnode * root
A pointer to the root node of the heap.
Definition: pheap.h:90
size_t num_nodes
The number of nodes stored in the heap.
Definition: pheap.h:92
A node in a pairing heap.
Definition: pheap.h:51
struct pnode * parent
A pointer to the parent node.
Definition: pheap.h:59
struct pnode * child
A pointer to the first child node.
Definition: pheap.h:63
const void * key
A pointer to the key of this node.
Definition: pheap.h:57
struct pnode * next
A pointer to the next sibling node.
Definition: pheap.h:61