Add missing permission notice in each source file
[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
28#include <babeltrace/prio_heap.h>
96e1cf26 29#include <babeltrace/babeltrace-internal.h>
1eb0c69c
MD
30#include <errno.h>
31#include <stdlib.h>
32#include <string.h>
eacd552c 33#include <assert.h>
1eb0c69c
MD
34
35#ifndef max_t
36#define max_t(type, a, b) \
37 ((type) (a) > (type) (b) ? (type) (a) : (type) (b))
38#endif
39
eacd552c
MD
40#ifdef DEBUG_HEAP
41void check_heap(const struct ptr_heap *heap)
42{
43 size_t i;
44
45 if (!heap->len)
46 return;
47
48 for (i = 1; i < heap->len; i++)
49 assert(!heap->gt(heap->ptrs[i], heap->ptrs[0]));
50}
51#endif
52
557255e5 53static
1eb0c69c
MD
54size_t parent(size_t i)
55{
eacd552c 56 return (i - 1) >> 1;
1eb0c69c
MD
57}
58
59static
60size_t left(size_t i)
61{
eacd552c 62 return (i << 1) + 1;
1eb0c69c
MD
63}
64
65static
66size_t right(size_t i)
67{
eacd552c 68 return (i << 1) + 2;
1eb0c69c
MD
69}
70
557255e5
MD
71/*
72 * Copy of heap->ptrs pointer is invalid after heap_grow.
73 */
1eb0c69c
MD
74static
75int heap_grow(struct ptr_heap *heap, size_t new_len)
76{
77 void **new_ptrs;
78
96e1cf26 79 if (likely(heap->alloc_len >= new_len))
1eb0c69c
MD
80 return 0;
81
82 heap->alloc_len = max_t(size_t, new_len, heap->alloc_len << 1);
83 new_ptrs = calloc(heap->alloc_len, sizeof(void *));
96e1cf26 84 if (unlikely(!new_ptrs))
1eb0c69c 85 return -ENOMEM;
96e1cf26 86 if (likely(heap->ptrs))
1eb0c69c
MD
87 memcpy(new_ptrs, heap->ptrs, heap->len * sizeof(void *));
88 free(heap->ptrs);
89 heap->ptrs = new_ptrs;
90 return 0;
91}
92
93static
94int heap_set_len(struct ptr_heap *heap, size_t new_len)
95{
96 int ret;
97
98 ret = heap_grow(heap, new_len);
96e1cf26 99 if (unlikely(ret))
1eb0c69c
MD
100 return ret;
101 heap->len = new_len;
102 return 0;
103}
104
105int heap_init(struct ptr_heap *heap, size_t alloc_len,
106 int gt(void *a, void *b))
107{
108 heap->ptrs = NULL;
109 heap->len = 0;
110 heap->alloc_len = 0;
111 heap->gt = gt;
112 /*
113 * Minimum size allocated is 1 entry to ensure memory allocation
114 * never fails within heap_replace_max.
115 */
116 return heap_grow(heap, max_t(size_t, 1, alloc_len));
117}
118
119void heap_free(struct ptr_heap *heap)
120{
121 free(heap->ptrs);
122}
123
124static void heapify(struct ptr_heap *heap, size_t i)
125{
126 void **ptrs = heap->ptrs;
127 size_t l, r, largest;
128
129 for (;;) {
eacd552c
MD
130 void *tmp;
131
1eb0c69c
MD
132 l = left(i);
133 r = right(i);
eacd552c 134 if (l < heap->len && heap->gt(ptrs[l], ptrs[i]))
1eb0c69c
MD
135 largest = l;
136 else
137 largest = i;
eacd552c 138 if (r < heap->len && heap->gt(ptrs[r], ptrs[largest]))
1eb0c69c 139 largest = r;
96e1cf26 140 if (unlikely(largest == i))
1eb0c69c 141 break;
eacd552c
MD
142 tmp = ptrs[i];
143 ptrs[i] = ptrs[largest];
144 ptrs[largest] = tmp;
145 i = largest;
1eb0c69c 146 }
eacd552c 147 check_heap(heap);
1eb0c69c
MD
148}
149
150void *heap_replace_max(struct ptr_heap *heap, void *p)
151{
152 void *res;
1eb0c69c 153
96e1cf26 154 if (unlikely(!heap->len)) {
1eb0c69c 155 (void) heap_set_len(heap, 1);
557255e5 156 heap->ptrs[0] = p;
eacd552c 157 check_heap(heap);
1eb0c69c
MD
158 return NULL;
159 }
160
161 /* Replace the current max and heapify */
557255e5
MD
162 res = heap->ptrs[0];
163 heap->ptrs[0] = p;
1eb0c69c
MD
164 heapify(heap, 0);
165 return res;
166}
167
168int heap_insert(struct ptr_heap *heap, void *p)
169{
557255e5
MD
170 void **ptrs;
171 size_t pos;
1eb0c69c
MD
172 int ret;
173
174 ret = heap_set_len(heap, heap->len + 1);
96e1cf26 175 if (unlikely(ret))
1eb0c69c 176 return ret;
557255e5 177 ptrs = heap->ptrs;
557255e5 178 pos = heap->len - 1;
eacd552c
MD
179 while (pos > 0 && heap->gt(p, ptrs[parent(pos)])) {
180 /* Move parent down until we find the right spot */
181 ptrs[pos] = ptrs[parent(pos)];
182 pos = parent(pos);
557255e5 183 }
eacd552c
MD
184 ptrs[pos] = p;
185 check_heap(heap);
1eb0c69c
MD
186 return 0;
187}
188
189void *heap_remove(struct ptr_heap *heap)
190{
1eb0c69c
MD
191 switch (heap->len) {
192 case 0:
193 return NULL;
194 case 1:
195 (void) heap_set_len(heap, 0);
557255e5 196 return heap->ptrs[0];
1eb0c69c
MD
197 }
198 /* Shrink, replace the current max by previous last entry and heapify */
199 heap_set_len(heap, heap->len - 1);
eacd552c
MD
200 /* len changed. previous last entry is at heap->len */
201 return heap_replace_max(heap, heap->ptrs[heap->len]);
1eb0c69c
MD
202}
203
204void *heap_cherrypick(struct ptr_heap *heap, void *p)
205{
1eb0c69c
MD
206 size_t pos, len = heap->len;
207
208 for (pos = 0; pos < len; pos++)
96e1cf26 209 if (unlikely(heap->ptrs[pos] == p))
1eb0c69c
MD
210 goto found;
211 return NULL;
212found:
96e1cf26 213 if (unlikely(heap->len == 1)) {
1eb0c69c 214 (void) heap_set_len(heap, 0);
eacd552c 215 check_heap(heap);
557255e5 216 return heap->ptrs[0];
1eb0c69c
MD
217 }
218 /* Replace p with previous last entry and heapify. */
219 heap_set_len(heap, heap->len - 1);
eacd552c
MD
220 /* len changed. previous last entry is at heap->len */
221 heap->ptrs[pos] = heap->ptrs[heap->len];
1eb0c69c
MD
222 heapify(heap, pos);
223 return p;
224}
23a151f0
JD
225
226int heap_copy(struct ptr_heap *dst, struct ptr_heap *src)
227{
228 int ret;
229
230 ret = heap_init(dst, src->alloc_len, src->gt);
231 if (ret < 0)
232 goto end;
233
234 ret = heap_set_len(dst, src->len);
235 if (ret < 0)
236 goto end;
237
238 memcpy(dst->ptrs, src->ptrs, src->len * sizeof(void *));
239
240end:
241 return ret;
242}
This page took 0.071058 seconds and 4 git commands to generate.