2 * Babeltrace - CTF notification priority heap
4 * Static-sized priority heap containing pointers. Based on CLRS,
7 * Copyright (c) 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
8 * Copyright (c) 2016 Jérémie Galarneau <jeremie.galarneau@efficios.com>
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:
17 * The above copyright notice and this permission notice shall be included in
18 * all copies or substantial portions of the Software.
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
31 #include <babeltrace/compiler-internal.h>
32 #include <babeltrace/graph/notification-heap-internal.h>
36 void check_heap(struct bt_notification_heap
*heap
)
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),
51 void check_heap(struct bt_notification_heap
*heap
)
57 size_t parent(size_t i
)
69 size_t right(size_t i
)
75 * Copy of heap->ptrs pointer is invalid after heap_grow.
78 int heap_grow(struct bt_notification_heap
*heap
, size_t new_len
)
82 if (likely(heap
->ptrs
->len
>= new_len
)) {
86 alloc_len
= max_t(size_t, new_len
, heap
->ptrs
->len
<< 1);
87 g_ptr_array_set_size(heap
->ptrs
, alloc_len
);
93 int heap_set_count(struct bt_notification_heap
*heap
, size_t new_count
)
97 ret
= heap_grow(heap
, new_count
);
101 heap
->count
= new_count
;
107 void heapify(struct bt_notification_heap
*heap
, size_t i
)
109 struct bt_notification
**ptrs
=
110 (struct bt_notification
**) heap
->ptrs
->pdata
;
114 size_t l
, r
, largest
;
118 if (l
< heap
->count
&& heap
->compare(ptrs
[l
], ptrs
[i
],
119 heap
->compare_data
)) {
124 if (r
< heap
->count
&& heap
->compare(ptrs
[r
], ptrs
[largest
],
125 heap
->compare_data
)) {
128 if (unlikely(largest
== i
)) {
132 ptrs
[i
] = ptrs
[largest
];
140 struct bt_notification
*heap_replace_max(struct bt_notification_heap
*heap
,
141 struct bt_notification
*notification
)
143 struct bt_notification
*res
= NULL
;
145 if (unlikely(!heap
->count
)) {
146 (void) heap_set_count(heap
, 1);
147 g_ptr_array_index(heap
->ptrs
, 0) = notification
;
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
;
161 void bt_notification_heap_destroy(struct bt_object
*obj
)
163 struct bt_notification_heap
*heap
= container_of(obj
,
164 struct bt_notification_heap
, base
);
169 for (i
= 0; i
< heap
->count
; i
++) {
170 bt_put(g_ptr_array_index(heap
->ptrs
, i
));
172 g_ptr_array_free(heap
->ptrs
, TRUE
);
177 struct bt_notification_heap
*bt_notification_heap_create(
178 bt_notification_time_compare_func comparator
, void *user_data
)
180 struct bt_notification_heap
*heap
= NULL
;
186 heap
= g_new0(struct bt_notification_heap
, 1);
191 bt_object_init(&heap
->base
, bt_notification_heap_destroy
);
192 heap
->ptrs
= g_ptr_array_new();
198 heap
->compare
= comparator
;
199 heap
->compare_data
= user_data
;
204 struct bt_notification
*bt_notification_heap_peek(
205 struct bt_notification_heap
*heap
)
208 return bt_get(likely(heap
->count
) ?
209 g_ptr_array_index(heap
->ptrs
, 0) : NULL
);
212 int bt_notification_heap_insert(struct bt_notification_heap
*heap
,
213 struct bt_notification
*notification
)
217 struct bt_notification
**ptrs
;
219 ret
= heap_set_count(heap
, heap
->count
+ 1);
224 ptrs
= (struct bt_notification
**) heap
->ptrs
->pdata
;
225 pos
= heap
->count
- 1;
226 while (pos
> 0 && heap
->compare(notification
, ptrs
[parent(pos
)],
227 heap
->compare_data
)) {
228 /* Move parent down until we find the right spot. */
229 ptrs
[pos
] = ptrs
[parent(pos
)];
232 ptrs
[pos
] = bt_get(notification
);
238 struct bt_notification
*bt_notification_heap_pop(
239 struct bt_notification_heap
*heap
)
241 struct bt_notification
*ret
= NULL
;
243 switch (heap
->count
) {
247 (void) heap_set_count(heap
, 0);
248 ret
= g_ptr_array_index(heap
->ptrs
, 0);
252 * Shrink, replace the current max by previous last entry and heapify.
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
,
260 * Not taking a supplementary reference since we are relinquishing our