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 | ||
29 | #include <assert.h> | |
30 | #include <stddef.h> | |
31 | #include <babeltrace/compiler.h> | |
32 | #include <babeltrace/plugin/notification/heap-internal.h> | |
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++) { | |
45 | assert(!heap->compare(g_ptr_array_index(heap->ptrs, i), | |
46 | g_ptr_array_index(heap->ptrs, 0))); | |
47 | } | |
48 | } | |
49 | #else | |
50 | void check_heap(struct bt_notification_heap *heap) | |
51 | { | |
52 | } | |
53 | #endif | |
54 | ||
55 | static | |
56 | size_t parent(size_t i) | |
57 | { | |
58 | return (i - 1) >> 1; | |
59 | } | |
60 | ||
61 | static | |
62 | size_t left(size_t i) | |
63 | { | |
64 | return (i << 1) + 1; | |
65 | } | |
66 | ||
67 | static | |
68 | size_t right(size_t i) | |
69 | { | |
70 | return (i << 1) + 2; | |
71 | } | |
72 | ||
73 | /* | |
74 | * Copy of heap->ptrs pointer is invalid after heap_grow. | |
75 | */ | |
76 | static | |
77 | int heap_grow(struct bt_notification_heap *heap, size_t new_len) | |
78 | { | |
79 | size_t alloc_len; | |
80 | ||
81 | if (likely(heap->ptrs->len >= new_len)) { | |
82 | goto end; | |
83 | } | |
84 | ||
85 | alloc_len = max_t(size_t, new_len, heap->ptrs->len << 1); | |
86 | g_ptr_array_set_size(heap->ptrs, alloc_len); | |
87 | end: | |
88 | return 0; | |
89 | } | |
90 | ||
91 | static | |
92 | int heap_set_count(struct bt_notification_heap *heap, size_t new_count) | |
93 | { | |
94 | int ret = 0; | |
95 | ||
96 | ret = heap_grow(heap, new_count); | |
97 | if (unlikely(ret)) { | |
98 | goto end; | |
99 | } | |
100 | heap->count = new_count; | |
101 | end: | |
102 | return ret; | |
103 | } | |
104 | ||
105 | static | |
106 | void heapify(struct bt_notification_heap *heap, size_t i) | |
107 | { | |
108 | struct bt_notification **ptrs = | |
109 | (struct bt_notification **) heap->ptrs->pdata; | |
110 | ||
111 | for (;;) { | |
112 | void *tmp; | |
113 | size_t l, r, largest; | |
114 | ||
115 | l = left(i); | |
116 | r = right(i); | |
117 | if (l < heap->count && heap->compare(ptrs[l], ptrs[i])) { | |
118 | largest = l; | |
119 | } else { | |
120 | largest = i; | |
121 | } | |
122 | if (r < heap->count && heap->compare(ptrs[r], ptrs[largest])) { | |
123 | largest = r; | |
124 | } | |
125 | if (unlikely(largest == i)) { | |
126 | break; | |
127 | } | |
128 | tmp = ptrs[i]; | |
129 | ptrs[i] = ptrs[largest]; | |
130 | ptrs[largest] = tmp; | |
131 | i = largest; | |
132 | } | |
133 | check_heap(heap); | |
134 | } | |
135 | ||
136 | static | |
137 | struct bt_notification *heap_replace_max(struct bt_notification_heap *heap, | |
138 | struct bt_notification *notification) | |
139 | { | |
140 | struct bt_notification *res = NULL; | |
141 | ||
142 | if (unlikely(!heap->count)) { | |
143 | (void) heap_set_count(heap, 1); | |
144 | g_ptr_array_index(heap->ptrs, 0) = notification; | |
145 | check_heap(heap); | |
146 | goto end; | |
147 | } | |
148 | ||
149 | /* Replace the current max and heapify. */ | |
150 | res = g_ptr_array_index(heap->ptrs, 0); | |
151 | g_ptr_array_index(heap->ptrs, 0) = notification; | |
152 | heapify(heap, 0); | |
153 | end: | |
154 | return res; | |
155 | } | |
156 | ||
157 | static | |
158 | void bt_notification_heap_destroy(struct bt_object *obj) | |
159 | { | |
160 | struct bt_notification_heap *heap = container_of(obj, | |
161 | struct bt_notification_heap, base); | |
162 | ||
163 | if (heap->ptrs) { | |
164 | size_t i; | |
165 | ||
166 | for (i = 0; i < heap->count; i++) { | |
167 | bt_put(g_ptr_array_index(heap->ptrs, i)); | |
168 | } | |
169 | g_ptr_array_free(heap->ptrs, TRUE); | |
170 | } | |
171 | g_free(heap); | |
172 | } | |
173 | ||
174 | struct bt_notification_heap *bt_notification_heap_create( | |
175 | bt_notification_time_compare_func comparator) | |
176 | { | |
177 | struct bt_notification_heap *heap = NULL; | |
178 | ||
179 | if (!comparator) { | |
180 | goto end; | |
181 | } | |
182 | ||
183 | heap = g_new0(struct bt_notification_heap, 1); | |
184 | if (!heap) { | |
185 | goto end; | |
186 | } | |
187 | ||
188 | bt_object_init(&heap->base, bt_notification_heap_destroy); | |
189 | heap->ptrs = g_ptr_array_new(); | |
190 | if (!heap->ptrs) { | |
191 | BT_PUT(heap); | |
192 | goto end; | |
193 | } | |
194 | ||
195 | heap->compare = comparator; | |
196 | end: | |
197 | return heap; | |
198 | } | |
199 | ||
200 | struct bt_notification *bt_notification_heap_peek( | |
201 | struct bt_notification_heap *heap) | |
202 | { | |
203 | check_heap(heap); | |
204 | return bt_get(likely(heap->count) ? | |
205 | g_ptr_array_index(heap->ptrs, 0) : NULL); | |
206 | } | |
207 | ||
208 | int bt_notification_heap_insert(struct bt_notification_heap *heap, | |
209 | struct bt_notification *notification) | |
210 | { | |
211 | int ret; | |
212 | size_t pos; | |
213 | struct bt_notification **ptrs; | |
214 | ||
215 | ret = heap_set_count(heap, heap->count + 1); | |
216 | if (unlikely(ret)) { | |
217 | goto end; | |
218 | } | |
219 | ||
220 | ptrs = (struct bt_notification **) heap->ptrs->pdata; | |
221 | pos = heap->count - 1; | |
222 | while (pos > 0 && heap->compare(notification, ptrs[parent(pos)])) { | |
223 | /* Move parent down until we find the right spot. */ | |
224 | ptrs[pos] = ptrs[parent(pos)]; | |
225 | pos = parent(pos); | |
226 | } | |
227 | ptrs[pos] = bt_get(notification); | |
228 | check_heap(heap); | |
229 | end: | |
230 | return ret; | |
231 | } | |
232 | ||
233 | struct bt_notification *bt_notification_heap_pop( | |
234 | struct bt_notification_heap *heap) | |
235 | { | |
236 | struct bt_notification *ret = NULL; | |
237 | ||
238 | switch (heap->count) { | |
239 | case 0: | |
240 | goto end; | |
241 | case 1: | |
242 | (void) heap_set_count(heap, 0); | |
243 | ret = g_ptr_array_index(heap->ptrs, 0); | |
244 | goto end; | |
245 | } | |
246 | /* | |
247 | * Shrink, replace the current max by previous last entry and heapify. | |
248 | */ | |
249 | heap_set_count(heap, heap->count - 1); | |
250 | /* count changed. previous last entry is at heap->count. */ | |
251 | ret = heap_replace_max(heap, g_ptr_array_index(heap->ptrs, | |
252 | heap->count)); | |
253 | end: | |
254 | /* | |
255 | * Not taking a supplementary reference since we are relinquishing our | |
256 | * own to the caller. | |
257 | */ | |
258 | return ret; | |
259 | } |