lib/prio_heap.c

   1 /*
   2  * prio_heap.c
   3  *
   4  * Static-sized priority heap containing pointers. Based on CLRS,
   5  * chapter 6.
   6  *
   7  * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   8  *
   9  * Permission is hereby granted, free of charge, to any person obtaining a copy
  10  * of this software and associated documentation files (the "Software"), to deal
  11  * in the Software without restriction, including without limitation the rights
  12  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  13  * copies of the Software, and to permit persons to whom the Software is
  14  * furnished to do so, subject to the following conditions:
  15  *
  16  * The above copyright notice and this permission notice shall be included in
  17  * all copies or substantial portions of the Software.
  18  */
  19
  20 #include <babeltrace/prio_heap.h>
  21 #include <errno.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include <assert.h>
  25
  26 #ifndef max_t
  27 #define max_t(type, a, b)       \
  28         ((type) (a) > (type) (b) ? (type) (a) : (type) (b))
  29 #endif
  30
  31 #ifdef DEBUG_HEAP
  32 void check_heap(const struct ptr_heap *heap)
  33 {
  34         size_t i;
  35
  36         if (!heap->len)
  37                 return;
  38
  39         for (i = 1; i < heap->len; i++)
  40                 assert(!heap->gt(heap->ptrs[i], heap->ptrs[0]));
  41 }
  42 #endif
  43
  44 static
  45 size_t parent(size_t i)
  46 {
  47         return (i - 1) >> 1;
  48 }
  49
  50 static
  51 size_t left(size_t i)
  52 {
  53         return (i << 1) + 1;
  54 }
  55
  56 static
  57 size_t right(size_t i)
  58 {
  59         return (i << 1) + 2;
  60 }
  61
  62 /*
  63  * Copy of heap->ptrs pointer is invalid after heap_grow.
  64  */
  65 static
  66 int heap_grow(struct ptr_heap *heap, size_t new_len)
  67 {
  68         void **new_ptrs;
  69
  70         if (heap->alloc_len >= new_len)
  71                 return 0;
  72
  73         heap->alloc_len = max_t(size_t, new_len, heap->alloc_len << 1);
  74         new_ptrs = calloc(heap->alloc_len, sizeof(void *));
  75         if (!new_ptrs)
  76                 return -ENOMEM;
  77         if (heap->ptrs)
  78                 memcpy(new_ptrs, heap->ptrs, heap->len * sizeof(void *));
  79         free(heap->ptrs);
  80         heap->ptrs = new_ptrs;
  81         return 0;
  82 }
  83
  84 static
  85 int heap_set_len(struct ptr_heap *heap, size_t new_len)
  86 {
  87         int ret;
  88
  89         ret = heap_grow(heap, new_len);
  90         if (ret)
  91                 return ret;
  92         heap->len = new_len;
  93         return 0;
  94 }
  95
  96 int heap_init(struct ptr_heap *heap, size_t alloc_len,
  97               int gt(void *a, void *b))
  98 {
  99         heap->ptrs = NULL;
 100         heap->len = 0;
 101         heap->alloc_len = 0;
 102         heap->gt = gt;
 103         /*
 104          * Minimum size allocated is 1 entry to ensure memory allocation
 105          * never fails within heap_replace_max.
 106          */
 107         return heap_grow(heap, max_t(size_t, 1, alloc_len));
 108 }
 109
 110 void heap_free(struct ptr_heap *heap)
 111 {
 112         free(heap->ptrs);
 113 }
 114
 115 static void heapify(struct ptr_heap *heap, size_t i)
 116 {
 117         void **ptrs = heap->ptrs;
 118         size_t l, r, largest;
 119
 120         for (;;) {
 121                 void *tmp;
 122
 123                 l = left(i);
 124                 r = right(i);
 125                 if (l < heap->len && heap->gt(ptrs[l], ptrs[i]))
 126                         largest = l;
 127                 else
 128                         largest = i;
 129                 if (r < heap->len && heap->gt(ptrs[r], ptrs[largest]))
 130                         largest = r;
 131                 if (largest == i)
 132                         break;
 133                 tmp = ptrs[i];
 134                 ptrs[i] = ptrs[largest];
 135                 ptrs[largest] = tmp;
 136                 i = largest;
 137         }
 138         check_heap(heap);
 139 }
 140
 141 void *heap_replace_max(struct ptr_heap *heap, void *p)
 142 {
 143         void *res;
 144
 145         if (!heap->len) {
 146                 (void) heap_set_len(heap, 1);
 147                 heap->ptrs[0] = p;
 148                 check_heap(heap);
 149                 return NULL;
 150         }
 151
 152         /* Replace the current max and heapify */
 153         res = heap->ptrs[0];
 154         heap->ptrs[0] = p;
 155         heapify(heap, 0);
 156         return res;
 157 }
 158
 159 int heap_insert(struct ptr_heap *heap, void *p)
 160 {
 161         void **ptrs;
 162         size_t pos;
 163         int ret;
 164
 165         ret = heap_set_len(heap, heap->len + 1);
 166         if (ret)
 167                 return ret;
 168         ptrs = heap->ptrs;
 169         pos = heap->len - 1;
 170         while (pos > 0 && heap->gt(p, ptrs[parent(pos)])) {
 171                 /* Move parent down until we find the right spot */
 172                 ptrs[pos] = ptrs[parent(pos)];
 173                 pos = parent(pos);
 174         }
 175         ptrs[pos] = p;
 176         check_heap(heap);
 177         return 0;
 178 }
 179
 180 void *heap_remove(struct ptr_heap *heap)
 181 {
 182         switch (heap->len) {
 183         case 0:
 184                 return NULL;
 185         case 1:
 186                 (void) heap_set_len(heap, 0);
 187                 return heap->ptrs[0];
 188         }
 189         /* Shrink, replace the current max by previous last entry and heapify */
 190         heap_set_len(heap, heap->len - 1);
 191         /* len changed. previous last entry is at heap->len */
 192         return heap_replace_max(heap, heap->ptrs[heap->len]);
 193 }
 194
 195 void *heap_cherrypick(struct ptr_heap *heap, void *p)
 196 {
 197         size_t pos, len = heap->len;
 198
 199         for (pos = 0; pos < len; pos++)
 200                 if (heap->ptrs[pos] == p)
 201                         goto found;
 202         return NULL;
 203 found:
 204         if (heap->len == 1) {
 205                 (void) heap_set_len(heap, 0);
 206                 check_heap(heap);
 207                 return heap->ptrs[0];
 208         }
 209         /* Replace p with previous last entry and heapify. */
 210         heap_set_len(heap, heap->len - 1);
 211         /* len changed. previous last entry is at heap->len */
 212         heap->ptrs[pos] = heap->ptrs[heap->len];
 213         heapify(heap, pos);
 214         return p;
 215 }