Replace assert() -> BT_ASSERT() and some preconditions with BT_ASSERT_PRE()
[babeltrace.git] / lib / prio_heap / 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.
c462e188
MD
18 *
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
22 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
24 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
25 * SOFTWARE.
1eb0c69c
MD
26 */
27
3d9990ac 28#include <babeltrace/prio-heap-internal.h>
96e1cf26 29#include <babeltrace/babeltrace-internal.h>
f6ccaed9 30#include <babeltrace/assert-internal.h>
1eb0c69c
MD
31#include <errno.h>
32#include <stdlib.h>
33#include <string.h>
34
eacd552c
MD
35#ifdef DEBUG_HEAP
36void check_heap(const struct ptr_heap *heap)
37{
38 size_t i;
39
40 if (!heap->len)
41 return;
42
43 for (i = 1; i < heap->len; i++)
f6ccaed9 44 BT_ASSERT(!heap->gt(heap->ptrs[i], heap->ptrs[0]));
eacd552c
MD
45}
46#endif
47
557255e5 48static
1eb0c69c
MD
49size_t parent(size_t i)
50{
eacd552c 51 return (i - 1) >> 1;
1eb0c69c
MD
52}
53
54static
55size_t left(size_t i)
56{
eacd552c 57 return (i << 1) + 1;
1eb0c69c
MD
58}
59
60static
61size_t right(size_t i)
62{
eacd552c 63 return (i << 1) + 2;
1eb0c69c
MD
64}
65
557255e5
MD
66/*
67 * Copy of heap->ptrs pointer is invalid after heap_grow.
68 */
1eb0c69c
MD
69static
70int heap_grow(struct ptr_heap *heap, size_t new_len)
71{
72 void **new_ptrs;
73
96e1cf26 74 if (likely(heap->alloc_len >= new_len))
1eb0c69c
MD
75 return 0;
76
77 heap->alloc_len = max_t(size_t, new_len, heap->alloc_len << 1);
78 new_ptrs = calloc(heap->alloc_len, sizeof(void *));
96e1cf26 79 if (unlikely(!new_ptrs))
1eb0c69c 80 return -ENOMEM;
96e1cf26 81 if (likely(heap->ptrs))
1eb0c69c
MD
82 memcpy(new_ptrs, heap->ptrs, heap->len * sizeof(void *));
83 free(heap->ptrs);
84 heap->ptrs = new_ptrs;
85 return 0;
86}
87
88static
89int heap_set_len(struct ptr_heap *heap, size_t new_len)
90{
91 int ret;
92
93 ret = heap_grow(heap, new_len);
96e1cf26 94 if (unlikely(ret))
1eb0c69c
MD
95 return ret;
96 heap->len = new_len;
97 return 0;
98}
99
dd06413f 100int bt_heap_init(struct ptr_heap *heap, size_t alloc_len,
1eb0c69c
MD
101 int gt(void *a, void *b))
102{
103 heap->ptrs = NULL;
104 heap->len = 0;
105 heap->alloc_len = 0;
106 heap->gt = gt;
107 /*
108 * Minimum size allocated is 1 entry to ensure memory allocation
dd06413f 109 * never fails within bt_heap_replace_max.
1eb0c69c
MD
110 */
111 return heap_grow(heap, max_t(size_t, 1, alloc_len));
112}
113
dd06413f 114void bt_heap_free(struct ptr_heap *heap)
1eb0c69c
MD
115{
116 free(heap->ptrs);
117}
118
119static void heapify(struct ptr_heap *heap, size_t i)
120{
121 void **ptrs = heap->ptrs;
122 size_t l, r, largest;
123
124 for (;;) {
eacd552c
MD
125 void *tmp;
126
1eb0c69c
MD
127 l = left(i);
128 r = right(i);
eacd552c 129 if (l < heap->len && heap->gt(ptrs[l], ptrs[i]))
1eb0c69c
MD
130 largest = l;
131 else
132 largest = i;
eacd552c 133 if (r < heap->len && heap->gt(ptrs[r], ptrs[largest]))
1eb0c69c 134 largest = r;
96e1cf26 135 if (unlikely(largest == i))
1eb0c69c 136 break;
eacd552c
MD
137 tmp = ptrs[i];
138 ptrs[i] = ptrs[largest];
139 ptrs[largest] = tmp;
140 i = largest;
1eb0c69c 141 }
eacd552c 142 check_heap(heap);
1eb0c69c
MD
143}
144
dd06413f 145void *bt_heap_replace_max(struct ptr_heap *heap, void *p)
1eb0c69c
MD
146{
147 void *res;
1eb0c69c 148
96e1cf26 149 if (unlikely(!heap->len)) {
1eb0c69c 150 (void) heap_set_len(heap, 1);
557255e5 151 heap->ptrs[0] = p;
eacd552c 152 check_heap(heap);
1eb0c69c
MD
153 return NULL;
154 }
155
156 /* Replace the current max and heapify */
557255e5
MD
157 res = heap->ptrs[0];
158 heap->ptrs[0] = p;
1eb0c69c
MD
159 heapify(heap, 0);
160 return res;
161}
162
dd06413f 163int bt_heap_insert(struct ptr_heap *heap, void *p)
1eb0c69c 164{
557255e5
MD
165 void **ptrs;
166 size_t pos;
1eb0c69c
MD
167 int ret;
168
169 ret = heap_set_len(heap, heap->len + 1);
96e1cf26 170 if (unlikely(ret))
1eb0c69c 171 return ret;
557255e5 172 ptrs = heap->ptrs;
557255e5 173 pos = heap->len - 1;
eacd552c
MD
174 while (pos > 0 && heap->gt(p, ptrs[parent(pos)])) {
175 /* Move parent down until we find the right spot */
176 ptrs[pos] = ptrs[parent(pos)];
177 pos = parent(pos);
557255e5 178 }
eacd552c
MD
179 ptrs[pos] = p;
180 check_heap(heap);
1eb0c69c
MD
181 return 0;
182}
183
dd06413f 184void *bt_heap_remove(struct ptr_heap *heap)
1eb0c69c 185{
1eb0c69c
MD
186 switch (heap->len) {
187 case 0:
188 return NULL;
189 case 1:
190 (void) heap_set_len(heap, 0);
557255e5 191 return heap->ptrs[0];
1eb0c69c
MD
192 }
193 /* Shrink, replace the current max by previous last entry and heapify */
194 heap_set_len(heap, heap->len - 1);
eacd552c 195 /* len changed. previous last entry is at heap->len */
dd06413f 196 return bt_heap_replace_max(heap, heap->ptrs[heap->len]);
1eb0c69c
MD
197}
198
dd06413f 199void *bt_heap_cherrypick(struct ptr_heap *heap, void *p)
1eb0c69c 200{
1eb0c69c
MD
201 size_t pos, len = heap->len;
202
203 for (pos = 0; pos < len; pos++)
96e1cf26 204 if (unlikely(heap->ptrs[pos] == p))
1eb0c69c
MD
205 goto found;
206 return NULL;
207found:
96e1cf26 208 if (unlikely(heap->len == 1)) {
1eb0c69c 209 (void) heap_set_len(heap, 0);
eacd552c 210 check_heap(heap);
557255e5 211 return heap->ptrs[0];
1eb0c69c
MD
212 }
213 /* Replace p with previous last entry and heapify. */
214 heap_set_len(heap, heap->len - 1);
eacd552c
MD
215 /* len changed. previous last entry is at heap->len */
216 heap->ptrs[pos] = heap->ptrs[heap->len];
1eb0c69c
MD
217 heapify(heap, pos);
218 return p;
219}
23a151f0 220
dd06413f 221int bt_heap_copy(struct ptr_heap *dst, struct ptr_heap *src)
23a151f0
JD
222{
223 int ret;
224
dd06413f 225 ret = bt_heap_init(dst, src->alloc_len, src->gt);
23a151f0
JD
226 if (ret < 0)
227 goto end;
228
229 ret = heap_set_len(dst, src->len);
230 if (ret < 0)
231 goto end;
232
233 memcpy(dst->ptrs, src->ptrs, src->len * sizeof(void *));
234
235end:
236 return ret;
237}
This page took 0.055261 seconds and 4 git commands to generate.