From 6a5c560c38fc38f9441aeca0393f0e5013023e5f Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=A9mie=20Galarneau?= Date: Tue, 1 Nov 2016 16:34:16 -0400 Subject: [PATCH] Implement the notification heap interface MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérémie Galarneau --- include/Makefile.am | 6 +- .../plugin/notification/heap-internal.h | 40 +++ .../babeltrace/plugin/notification/heap.h | 13 +- lib/plugin-system/notification/Makefile.am | 3 +- lib/plugin-system/notification/heap.c | 259 ++++++++++++++++++ 5 files changed, 312 insertions(+), 9 deletions(-) create mode 100644 include/babeltrace/plugin/notification/heap-internal.h rename plugins/ctf/common/notif-iter/notif-heap.h => include/babeltrace/plugin/notification/heap.h (92%) create mode 100644 lib/plugin-system/notification/heap.c diff --git a/include/Makefile.am b/include/Makefile.am index ecdb3632..837f1f9c 100644 --- a/include/Makefile.am +++ b/include/Makefile.am @@ -52,7 +52,8 @@ babeltraceplugininclude_HEADERS = \ babeltrace/plugin/notification/iterator.h \ babeltrace/plugin/notification/packet.h \ babeltrace/plugin/notification/schema.h \ - babeltrace/plugin/notification/stream.h + babeltrace/plugin/notification/stream.h \ + babeltrace/plugin/notification/heap.h noinst_HEADERS = \ babeltrace/align.h \ @@ -125,4 +126,5 @@ noinst_HEADERS = \ babeltrace/plugin/notification/iterator-internal.h \ babeltrace/plugin/notification/notification-internal.h \ babeltrace/plugin/notification/packet-internal.h \ - babeltrace/plugin/notification/stream-internal.h + babeltrace/plugin/notification/stream-internal.h \ + babeltrace/plugin/notification/heap-internal.h diff --git a/include/babeltrace/plugin/notification/heap-internal.h b/include/babeltrace/plugin/notification/heap-internal.h new file mode 100644 index 00000000..63a82e17 --- /dev/null +++ b/include/babeltrace/plugin/notification/heap-internal.h @@ -0,0 +1,40 @@ +#ifndef CTF_NOTIF_HEAP_INTERNAL_H +#define CTF_NOTIF_HEAP_INTERNAL_H + +/* + * Babeltrace - CTF notification heap priority heap + * + * Copyright (c) 2016 Jérémie Galarneau + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#include +#include +#include +#include + +struct bt_notification_heap { + struct bt_object base; + GPtrArray *ptrs; + size_t count; + bt_notification_time_compare_func compare; +}; + +#endif /* CTF_NOTIF_HEAP_INTERNAL_H */ diff --git a/plugins/ctf/common/notif-iter/notif-heap.h b/include/babeltrace/plugin/notification/heap.h similarity index 92% rename from plugins/ctf/common/notif-iter/notif-heap.h rename to include/babeltrace/plugin/notification/heap.h index 1c877e9f..f56822c9 100644 --- a/plugins/ctf/common/notif-iter/notif-heap.h +++ b/include/babeltrace/plugin/notification/heap.h @@ -1,8 +1,8 @@ -#ifndef BT_NOTIFICATION_PRIO_HEAP_H -#define BT_NOTIFICATION_PRIO_HEAP_H +#ifndef BT_NOTIFICATION_HEAP_H +#define BT_NOTIFICATION_HEAP_H /* - * Babeltrace - Priority Heap + * Babeltrace - Notification Heap * * Copyright (c) 2011 Mathieu Desnoyers * Copyright (c) 2016 Jérémie Galarneau @@ -40,7 +40,7 @@ * used to order the notifications. This criterion shall ensure a consistent * ordering over multiple runs. */ -typedef bool (bt_notification_time_compare_func)( +typedef bool (*bt_notification_time_compare_func)( struct bt_notification *a, struct bt_notification *b); /** @@ -86,6 +86,7 @@ extern struct bt_notification *bt_notification_heap_peek( * heap. Returns NULL if the heap is empty. The returned notification must be * bt_put() by the caller. */ -extern void *bt_notification_heap_pop(struct bt_notification_heap *heap); +extern struct bt_notification *bt_notification_heap_pop( + struct bt_notification_heap *heap); -#endif /* BT_NOTIFICATION_PRIO_HEAP_H */ +#endif /* BT_NOTIFICATION_HEAP_H */ diff --git a/lib/plugin-system/notification/Makefile.am b/lib/plugin-system/notification/Makefile.am index 12cdbf12..dca588ee 100644 --- a/lib/plugin-system/notification/Makefile.am +++ b/lib/plugin-system/notification/Makefile.am @@ -7,4 +7,5 @@ libplugin_system_notification_la_SOURCES = \ notification.c \ packet.c \ event.c \ - stream.c + stream.c \ + heap.c diff --git a/lib/plugin-system/notification/heap.c b/lib/plugin-system/notification/heap.c new file mode 100644 index 00000000..1f919721 --- /dev/null +++ b/lib/plugin-system/notification/heap.c @@ -0,0 +1,259 @@ +/* + * Babeltrace - CTF notification priority heap + * + * Static-sized priority heap containing pointers. Based on CLRS, + * chapter 6. + * + * Copyright (c) 2011 Mathieu Desnoyers + * Copyright (c) 2016 Jérémie Galarneau + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#include +#include +#include +#include + +#ifdef DEBUG_HEAP +static +void check_heap(struct bt_notification_heap *heap) +{ + size_t i; + + if (!heap->count) { + return; + } + + for (i = 1; i < heap->count; i++) { + assert(!heap->compare(g_ptr_array_index(heap->ptrs, i), + g_ptr_array_index(heap->ptrs, 0))); + } +} +#else +void check_heap(struct bt_notification_heap *heap) +{ +} +#endif + +static +size_t parent(size_t i) +{ + return (i - 1) >> 1; +} + +static +size_t left(size_t i) +{ + return (i << 1) + 1; +} + +static +size_t right(size_t i) +{ + return (i << 1) + 2; +} + +/* + * Copy of heap->ptrs pointer is invalid after heap_grow. + */ +static +int heap_grow(struct bt_notification_heap *heap, size_t new_len) +{ + size_t alloc_len; + + if (likely(heap->ptrs->len >= new_len)) { + goto end; + } + + alloc_len = max_t(size_t, new_len, heap->ptrs->len << 1); + g_ptr_array_set_size(heap->ptrs, alloc_len); +end: + return 0; +} + +static +int heap_set_count(struct bt_notification_heap *heap, size_t new_count) +{ + int ret = 0; + + ret = heap_grow(heap, new_count); + if (unlikely(ret)) { + goto end; + } + heap->count = new_count; +end: + return ret; +} + +static +void heapify(struct bt_notification_heap *heap, size_t i) +{ + struct bt_notification **ptrs = + (struct bt_notification **) heap->ptrs->pdata; + + for (;;) { + void *tmp; + size_t l, r, largest; + + l = left(i); + r = right(i); + if (l < heap->count && heap->compare(ptrs[l], ptrs[i])) { + largest = l; + } else { + largest = i; + } + if (r < heap->count && heap->compare(ptrs[r], ptrs[largest])) { + largest = r; + } + if (unlikely(largest == i)) { + break; + } + tmp = ptrs[i]; + ptrs[i] = ptrs[largest]; + ptrs[largest] = tmp; + i = largest; + } + check_heap(heap); +} + +static +struct bt_notification *heap_replace_max(struct bt_notification_heap *heap, + struct bt_notification *notification) +{ + struct bt_notification *res = NULL; + + if (unlikely(!heap->count)) { + (void) heap_set_count(heap, 1); + g_ptr_array_index(heap->ptrs, 0) = notification; + check_heap(heap); + goto end; + } + + /* Replace the current max and heapify. */ + res = g_ptr_array_index(heap->ptrs, 0); + g_ptr_array_index(heap->ptrs, 0) = notification; + heapify(heap, 0); +end: + return res; +} + +static +void bt_notification_heap_destroy(struct bt_object *obj) +{ + struct bt_notification_heap *heap = container_of(obj, + struct bt_notification_heap, base); + + if (heap->ptrs) { + size_t i; + + for (i = 0; i < heap->count; i++) { + bt_put(g_ptr_array_index(heap->ptrs, i)); + } + g_ptr_array_free(heap->ptrs, TRUE); + } + g_free(heap); +} + +struct bt_notification_heap *bt_notification_heap_create( + bt_notification_time_compare_func comparator) +{ + struct bt_notification_heap *heap = NULL; + + if (!comparator) { + goto end; + } + + heap = g_new0(struct bt_notification_heap, 1); + if (!heap) { + goto end; + } + + bt_object_init(&heap->base, bt_notification_heap_destroy); + heap->ptrs = g_ptr_array_new(); + if (!heap->ptrs) { + BT_PUT(heap); + goto end; + } + + heap->compare = comparator; +end: + return heap; +} + +struct bt_notification *bt_notification_heap_peek( + struct bt_notification_heap *heap) +{ + check_heap(heap); + return bt_get(likely(heap->count) ? + g_ptr_array_index(heap->ptrs, 0) : NULL); +} + +int bt_notification_heap_insert(struct bt_notification_heap *heap, + struct bt_notification *notification) +{ + int ret; + size_t pos; + struct bt_notification **ptrs; + + ret = heap_set_count(heap, heap->count + 1); + if (unlikely(ret)) { + goto end; + } + + ptrs = (struct bt_notification **) heap->ptrs->pdata; + pos = heap->count - 1; + while (pos > 0 && heap->compare(notification, ptrs[parent(pos)])) { + /* Move parent down until we find the right spot. */ + ptrs[pos] = ptrs[parent(pos)]; + pos = parent(pos); + } + ptrs[pos] = bt_get(notification); + check_heap(heap); +end: + return ret; +} + +struct bt_notification *bt_notification_heap_pop( + struct bt_notification_heap *heap) +{ + struct bt_notification *ret = NULL; + + switch (heap->count) { + case 0: + goto end; + case 1: + (void) heap_set_count(heap, 0); + ret = g_ptr_array_index(heap->ptrs, 0); + goto end; + } + /* + * Shrink, replace the current max by previous last entry and heapify. + */ + heap_set_count(heap, heap->count - 1); + /* count changed. previous last entry is at heap->count. */ + ret = heap_replace_max(heap, g_ptr_array_index(heap->ptrs, + heap->count)); +end: + /* + * Not taking a supplementary reference since we are relinquishing our + * own to the caller. + */ + return ret; +} -- 2.34.1