Replace assert() -> BT_ASSERT() and some preconditions with BT_ASSERT_PRE()
[babeltrace.git] / lib / graph / notification / heap.c
CommitLineData
6a5c560c
JG
1/*
2 * Babeltrace - CTF notification priority heap
3 *
4 * Static-sized priority heap containing pointers. Based on CLRS,
5 * chapter 6.
6 *
7 * Copyright (c) 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
8 * Copyright (c) 2016 Jérémie Galarneau <jeremie.galarneau@efficios.com>
9 *
10 * Permission is hereby granted, free of charge, to any person obtaining a copy
11 * of this software and associated documentation files (the "Software"), to deal
12 * in the Software without restriction, including without limitation the rights
13 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
14 * copies of the Software, and to permit persons to whom the Software is
15 * furnished to do so, subject to the following conditions:
16 *
17 * The above copyright notice and this permission notice shall be included in
18 * all copies or substantial portions of the Software.
19 *
20 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
21 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
23 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
24 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
25 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
26 * SOFTWARE.
27 */
28
6a5c560c 29#include <stddef.h>
3d9990ac 30#include <babeltrace/compiler-internal.h>
b2e0c907 31#include <babeltrace/graph/notification-heap-internal.h>
f6ccaed9 32#include <babeltrace/assert-internal.h>
6a5c560c
JG
33
34#ifdef DEBUG_HEAP
35static
36void check_heap(struct bt_notification_heap *heap)
37{
38 size_t i;
39
40 if (!heap->count) {
41 return;
42 }
43
44 for (i = 1; i < heap->count; i++) {
f6ccaed9 45 BT_ASSERT(!heap->compare(g_ptr_array_index(heap->ptrs, i),
352fe16f
JG
46 g_ptr_array_index(heap->ptrs, 0),
47 heap->compare_data));
6a5c560c
JG
48 }
49}
50#else
51void check_heap(struct bt_notification_heap *heap)
52{
53}
54#endif
55
56static
57size_t parent(size_t i)
58{
59 return (i - 1) >> 1;
60}
61
62static
63size_t left(size_t i)
64{
65 return (i << 1) + 1;
66}
67
68static
69size_t right(size_t i)
70{
71 return (i << 1) + 2;
72}
73
74/*
75 * Copy of heap->ptrs pointer is invalid after heap_grow.
76 */
77static
78int heap_grow(struct bt_notification_heap *heap, size_t new_len)
79{
80 size_t alloc_len;
81
82 if (likely(heap->ptrs->len >= new_len)) {
83 goto end;
84 }
85
86 alloc_len = max_t(size_t, new_len, heap->ptrs->len << 1);
87 g_ptr_array_set_size(heap->ptrs, alloc_len);
88end:
89 return 0;
90}
91
92static
93int heap_set_count(struct bt_notification_heap *heap, size_t new_count)
94{
95 int ret = 0;
96
97 ret = heap_grow(heap, new_count);
98 if (unlikely(ret)) {
99 goto end;
100 }
101 heap->count = new_count;
102end:
103 return ret;
104}
105
106static
107void heapify(struct bt_notification_heap *heap, size_t i)
108{
109 struct bt_notification **ptrs =
110 (struct bt_notification **) heap->ptrs->pdata;
111
112 for (;;) {
113 void *tmp;
114 size_t l, r, largest;
115
116 l = left(i);
117 r = right(i);
352fe16f
JG
118 if (l < heap->count && heap->compare(ptrs[l], ptrs[i],
119 heap->compare_data)) {
6a5c560c
JG
120 largest = l;
121 } else {
122 largest = i;
123 }
352fe16f
JG
124 if (r < heap->count && heap->compare(ptrs[r], ptrs[largest],
125 heap->compare_data)) {
6a5c560c
JG
126 largest = r;
127 }
128 if (unlikely(largest == i)) {
129 break;
130 }
131 tmp = ptrs[i];
132 ptrs[i] = ptrs[largest];
133 ptrs[largest] = tmp;
134 i = largest;
135 }
136 check_heap(heap);
137}
138
139static
140struct bt_notification *heap_replace_max(struct bt_notification_heap *heap,
141 struct bt_notification *notification)
142{
143 struct bt_notification *res = NULL;
144
145 if (unlikely(!heap->count)) {
146 (void) heap_set_count(heap, 1);
147 g_ptr_array_index(heap->ptrs, 0) = notification;
148 check_heap(heap);
149 goto end;
150 }
151
152 /* Replace the current max and heapify. */
153 res = g_ptr_array_index(heap->ptrs, 0);
154 g_ptr_array_index(heap->ptrs, 0) = notification;
155 heapify(heap, 0);
156end:
157 return res;
158}
159
160static
161void bt_notification_heap_destroy(struct bt_object *obj)
162{
163 struct bt_notification_heap *heap = container_of(obj,
164 struct bt_notification_heap, base);
165
166 if (heap->ptrs) {
167 size_t i;
168
169 for (i = 0; i < heap->count; i++) {
170 bt_put(g_ptr_array_index(heap->ptrs, i));
171 }
172 g_ptr_array_free(heap->ptrs, TRUE);
173 }
174 g_free(heap);
175}
176
177struct bt_notification_heap *bt_notification_heap_create(
352fe16f 178 bt_notification_time_compare_func comparator, void *user_data)
6a5c560c
JG
179{
180 struct bt_notification_heap *heap = NULL;
181
182 if (!comparator) {
183 goto end;
184 }
185
186 heap = g_new0(struct bt_notification_heap, 1);
187 if (!heap) {
188 goto end;
189 }
190
191 bt_object_init(&heap->base, bt_notification_heap_destroy);
192 heap->ptrs = g_ptr_array_new();
193 if (!heap->ptrs) {
194 BT_PUT(heap);
195 goto end;
196 }
197
198 heap->compare = comparator;
352fe16f 199 heap->compare_data = user_data;
6a5c560c
JG
200end:
201 return heap;
202}
203
204struct bt_notification *bt_notification_heap_peek(
205 struct bt_notification_heap *heap)
206{
207 check_heap(heap);
208 return bt_get(likely(heap->count) ?
209 g_ptr_array_index(heap->ptrs, 0) : NULL);
210}
211
212int bt_notification_heap_insert(struct bt_notification_heap *heap,
213 struct bt_notification *notification)
214{
215 int ret;
216 size_t pos;
217 struct bt_notification **ptrs;
218
219 ret = heap_set_count(heap, heap->count + 1);
220 if (unlikely(ret)) {
221 goto end;
222 }
223
224 ptrs = (struct bt_notification **) heap->ptrs->pdata;
225 pos = heap->count - 1;
352fe16f
JG
226 while (pos > 0 && heap->compare(notification, ptrs[parent(pos)],
227 heap->compare_data)) {
6a5c560c
JG
228 /* Move parent down until we find the right spot. */
229 ptrs[pos] = ptrs[parent(pos)];
230 pos = parent(pos);
231 }
232 ptrs[pos] = bt_get(notification);
233 check_heap(heap);
234end:
235 return ret;
236}
237
238struct bt_notification *bt_notification_heap_pop(
239 struct bt_notification_heap *heap)
240{
241 struct bt_notification *ret = NULL;
242
243 switch (heap->count) {
244 case 0:
245 goto end;
246 case 1:
247 (void) heap_set_count(heap, 0);
248 ret = g_ptr_array_index(heap->ptrs, 0);
249 goto end;
250 }
251 /*
252 * Shrink, replace the current max by previous last entry and heapify.
253 */
254 heap_set_count(heap, heap->count - 1);
255 /* count changed. previous last entry is at heap->count. */
256 ret = heap_replace_max(heap, g_ptr_array_index(heap->ptrs,
257 heap->count));
258end:
259 /*
260 * Not taking a supplementary reference since we are relinquishing our
261 * own to the caller.
262 */
263 return ret;
264}
This page took 0.043933 seconds and 4 git commands to generate.