lib/component/notification/heap.c

   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/component/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                                 heap->compare_data));
  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);
 118                 if (l < heap->count && heap->compare(ptrs[l], ptrs[i],
 119                                 heap->compare_data)) {
 120                         largest = l;
 121                 } else {
 122                         largest = i;
 123                 }
 124                 if (r < heap->count && heap->compare(ptrs[r], ptrs[largest],
 125                                 heap->compare_data)) {
 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(
 178                 bt_notification_time_compare_func comparator, void *user_data)
 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;
 199         heap->compare_data = user_data;
 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;
 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)];
 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 }