--- /dev/null
+/*
+ * Babeltrace - CTF notification priority heap
+ *
+ * Static-sized priority heap containing pointers. Based on CLRS,
+ * chapter 6.
+ *
+ * Copyright (c) 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+ * Copyright (c) 2016 Jérémie Galarneau <jeremie.galarneau@efficios.com>
+ *
+ * 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 <assert.h>
+#include <stddef.h>
+#include <babeltrace/compiler.h>
+#include <babeltrace/plugin/notification/heap-internal.h>
+
+#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;
+}
projects / babeltrace.git / blobdiff