Commit | Line | Data |
---|---|---|
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 | |
35 | static | |
36 | void 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 | |
51 | void check_heap(struct bt_notification_heap *heap) | |
52 | { | |
53 | } | |
54 | #endif | |
55 | ||
56 | static | |
57 | size_t parent(size_t i) | |
58 | { | |
59 | return (i - 1) >> 1; | |
60 | } | |
61 | ||
62 | static | |
63 | size_t left(size_t i) | |
64 | { | |
65 | return (i << 1) + 1; | |
66 | } | |
67 | ||
68 | static | |
69 | size_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 | */ | |
77 | static | |
78 | int 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); | |
88 | end: | |
89 | return 0; | |
90 | } | |
91 | ||
92 | static | |
93 | int 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; | |
102 | end: | |
103 | return ret; | |
104 | } | |
105 | ||
106 | static | |
107 | void 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 | ||
139 | static | |
140 | struct 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); | |
156 | end: | |
157 | return res; | |
158 | } | |
159 | ||
160 | static | |
161 | void 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 | ||
177 | struct 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 |
200 | end: |
201 | return heap; | |
202 | } | |
203 | ||
204 | struct 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 | ||
212 | int 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); | |
234 | end: | |
235 | return ret; | |
236 | } | |
237 | ||
238 | struct 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)); | |
258 | end: | |
259 | /* | |
260 | * Not taking a supplementary reference since we are relinquishing our | |
261 | * own to the caller. | |
262 | */ | |
263 | return ret; | |
264 | } |