Add heap debug option, fix heap
[babeltrace.git] / lib / prio_heap.c
CommitLineData
1eb0c69c
MD
1/*
2 * prio_heap.c
3 *
4 * Static-sized priority heap containing pointers. Based on CLRS,
5 * chapter 6.
6 *
7 * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
8 *
9 * Permission is hereby granted, free of charge, to any person obtaining a copy
10 * of this software and associated documentation files (the "Software"), to deal
11 * in the Software without restriction, including without limitation the rights
12 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
13 * copies of the Software, and to permit persons to whom the Software is
14 * furnished to do so, subject to the following conditions:
15 *
16 * The above copyright notice and this permission notice shall be included in
17 * all copies or substantial portions of the Software.
18 */
19
20#include <babeltrace/prio_heap.h>
21#include <errno.h>
22#include <stdlib.h>
23#include <string.h>
eacd552c 24#include <assert.h>
1eb0c69c
MD
25
26#ifndef max_t
27#define max_t(type, a, b) \
28 ((type) (a) > (type) (b) ? (type) (a) : (type) (b))
29#endif
30
eacd552c
MD
31#ifdef DEBUG_HEAP
32void check_heap(const struct ptr_heap *heap)
33{
34 size_t i;
35
36 if (!heap->len)
37 return;
38
39 for (i = 1; i < heap->len; i++)
40 assert(!heap->gt(heap->ptrs[i], heap->ptrs[0]));
41}
42#endif
43
557255e5 44static
1eb0c69c
MD
45size_t parent(size_t i)
46{
eacd552c 47 return (i - 1) >> 1;
1eb0c69c
MD
48}
49
50static
51size_t left(size_t i)
52{
eacd552c 53 return (i << 1) + 1;
1eb0c69c
MD
54}
55
56static
57size_t right(size_t i)
58{
eacd552c 59 return (i << 1) + 2;
1eb0c69c
MD
60}
61
557255e5
MD
62/*
63 * Copy of heap->ptrs pointer is invalid after heap_grow.
64 */
1eb0c69c
MD
65static
66int heap_grow(struct ptr_heap *heap, size_t new_len)
67{
68 void **new_ptrs;
69
70 if (heap->alloc_len >= new_len)
71 return 0;
72
73 heap->alloc_len = max_t(size_t, new_len, heap->alloc_len << 1);
74 new_ptrs = calloc(heap->alloc_len, sizeof(void *));
75 if (!new_ptrs)
76 return -ENOMEM;
77 if (heap->ptrs)
78 memcpy(new_ptrs, heap->ptrs, heap->len * sizeof(void *));
79 free(heap->ptrs);
80 heap->ptrs = new_ptrs;
81 return 0;
82}
83
84static
85int heap_set_len(struct ptr_heap *heap, size_t new_len)
86{
87 int ret;
88
89 ret = heap_grow(heap, new_len);
90 if (ret)
91 return ret;
92 heap->len = new_len;
93 return 0;
94}
95
96int heap_init(struct ptr_heap *heap, size_t alloc_len,
97 int gt(void *a, void *b))
98{
99 heap->ptrs = NULL;
100 heap->len = 0;
101 heap->alloc_len = 0;
102 heap->gt = gt;
103 /*
104 * Minimum size allocated is 1 entry to ensure memory allocation
105 * never fails within heap_replace_max.
106 */
107 return heap_grow(heap, max_t(size_t, 1, alloc_len));
108}
109
110void heap_free(struct ptr_heap *heap)
111{
112 free(heap->ptrs);
113}
114
115static void heapify(struct ptr_heap *heap, size_t i)
116{
117 void **ptrs = heap->ptrs;
118 size_t l, r, largest;
119
120 for (;;) {
eacd552c
MD
121 void *tmp;
122
1eb0c69c
MD
123 l = left(i);
124 r = right(i);
eacd552c 125 if (l < heap->len && heap->gt(ptrs[l], ptrs[i]))
1eb0c69c
MD
126 largest = l;
127 else
128 largest = i;
eacd552c 129 if (r < heap->len && heap->gt(ptrs[r], ptrs[largest]))
1eb0c69c 130 largest = r;
eacd552c 131 if (largest == i)
1eb0c69c 132 break;
eacd552c
MD
133 tmp = ptrs[i];
134 ptrs[i] = ptrs[largest];
135 ptrs[largest] = tmp;
136 i = largest;
1eb0c69c 137 }
eacd552c 138 check_heap(heap);
1eb0c69c
MD
139}
140
141void *heap_replace_max(struct ptr_heap *heap, void *p)
142{
143 void *res;
1eb0c69c
MD
144
145 if (!heap->len) {
146 (void) heap_set_len(heap, 1);
557255e5 147 heap->ptrs[0] = p;
eacd552c 148 check_heap(heap);
1eb0c69c
MD
149 return NULL;
150 }
151
152 /* Replace the current max and heapify */
557255e5
MD
153 res = heap->ptrs[0];
154 heap->ptrs[0] = p;
1eb0c69c
MD
155 heapify(heap, 0);
156 return res;
157}
158
159int heap_insert(struct ptr_heap *heap, void *p)
160{
557255e5
MD
161 void **ptrs;
162 size_t pos;
1eb0c69c
MD
163 int ret;
164
165 ret = heap_set_len(heap, heap->len + 1);
166 if (ret)
167 return ret;
557255e5 168 ptrs = heap->ptrs;
557255e5 169 pos = heap->len - 1;
eacd552c
MD
170 while (pos > 0 && heap->gt(p, ptrs[parent(pos)])) {
171 /* Move parent down until we find the right spot */
172 ptrs[pos] = ptrs[parent(pos)];
173 pos = parent(pos);
557255e5 174 }
eacd552c
MD
175 ptrs[pos] = p;
176 check_heap(heap);
1eb0c69c
MD
177 return 0;
178}
179
180void *heap_remove(struct ptr_heap *heap)
181{
1eb0c69c
MD
182 switch (heap->len) {
183 case 0:
184 return NULL;
185 case 1:
186 (void) heap_set_len(heap, 0);
557255e5 187 return heap->ptrs[0];
1eb0c69c
MD
188 }
189 /* Shrink, replace the current max by previous last entry and heapify */
190 heap_set_len(heap, heap->len - 1);
eacd552c
MD
191 /* len changed. previous last entry is at heap->len */
192 return heap_replace_max(heap, heap->ptrs[heap->len]);
1eb0c69c
MD
193}
194
195void *heap_cherrypick(struct ptr_heap *heap, void *p)
196{
1eb0c69c
MD
197 size_t pos, len = heap->len;
198
199 for (pos = 0; pos < len; pos++)
557255e5 200 if (heap->ptrs[pos] == p)
1eb0c69c
MD
201 goto found;
202 return NULL;
203found:
204 if (heap->len == 1) {
205 (void) heap_set_len(heap, 0);
eacd552c 206 check_heap(heap);
557255e5 207 return heap->ptrs[0];
1eb0c69c
MD
208 }
209 /* Replace p with previous last entry and heapify. */
210 heap_set_len(heap, heap->len - 1);
eacd552c
MD
211 /* len changed. previous last entry is at heap->len */
212 heap->ptrs[pos] = heap->ptrs[heap->len];
1eb0c69c
MD
213 heapify(heap, pos);
214 return p;
215}
This page took 0.046613 seconds and 4 git commands to generate.