lib/prio_heap/lttng_prio_heap.c

   1 /*
   2  * lttng_prio_heap.c
   3  *
   4  * Priority heap containing pointers. Based on CLRS, chapter 6.
   5  *
   6  * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   7  *
   8  * Permission is hereby granted, free of charge, to any person obtaining a copy
   9  * of this software and associated documentation files (the "Software"), to deal
  10  * in the Software without restriction, including without limitation the rights
  11  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  12  * copies of the Software, and to permit persons to whom the Software is
  13  * furnished to do so, subject to the following conditions:
  14  *
  15  * The above copyright notice and this permission notice shall be included in
  16  * all copies or substantial portions of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  19  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  20  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  21  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  22  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  23  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  24  * SOFTWARE.
  25  */
  26
  27 #include <linux/slab.h>
  28 #include <lib/prio_heap/lttng_prio_heap.h>
  29 #include <wrapper/vmalloc.h>
  30
  31 #ifdef DEBUG_HEAP
  32 void lttng_check_heap(const struct lttng_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                 WARN_ON_ONCE(!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 lttng_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 = lttng_kvmalloc(heap->alloc_len * sizeof(void *), heap->gfpmask);
  75         if (!new_ptrs)
  76                 return -ENOMEM;
  77         if (heap->ptrs)
  78                 memcpy(new_ptrs, heap->ptrs, heap->len * sizeof(void *));
  79         lttng_kvfree(heap->ptrs);
  80         heap->ptrs = new_ptrs;
  81         return 0;
  82 }
  83
  84 static
  85 int heap_set_len(struct lttng_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 lttng_heap_init(struct lttng_ptr_heap *heap, size_t alloc_len,
  97               gfp_t gfpmask, 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         heap->gfpmask = gfpmask;
 104         /*
 105          * Minimum size allocated is 1 entry to ensure memory allocation
 106          * never fails within heap_replace_max.
 107          */
 108         return heap_grow(heap, max_t(size_t, 1, alloc_len));
 109 }
 110
 111 void lttng_heap_free(struct lttng_ptr_heap *heap)
 112 {
 113         lttng_kvfree(heap->ptrs);
 114 }
 115
 116 static void heapify(struct lttng_ptr_heap *heap, size_t i)
 117 {
 118         void **ptrs = heap->ptrs;
 119         size_t l, r, largest;
 120
 121         for (;;) {
 122                 void *tmp;
 123
 124                 l = left(i);
 125                 r = right(i);
 126                 if (l < heap->len && heap->gt(ptrs[l], ptrs[i]))
 127                         largest = l;
 128                 else
 129                         largest = i;
 130                 if (r < heap->len && heap->gt(ptrs[r], ptrs[largest]))
 131                         largest = r;
 132                 if (largest == i)
 133                         break;
 134                 tmp = ptrs[i];
 135                 ptrs[i] = ptrs[largest];
 136                 ptrs[largest] = tmp;
 137                 i = largest;
 138         }
 139         lttng_check_heap(heap);
 140 }
 141
 142 void *lttng_heap_replace_max(struct lttng_ptr_heap *heap, void *p)
 143 {
 144         void *res;
 145
 146         if (!heap->len) {
 147                 (void) heap_set_len(heap, 1);
 148                 heap->ptrs[0] = p;
 149                 lttng_check_heap(heap);
 150                 return NULL;
 151         }
 152
 153         /* Replace the current max and heapify */
 154         res = heap->ptrs[0];
 155         heap->ptrs[0] = p;
 156         heapify(heap, 0);
 157         return res;
 158 }
 159
 160 int lttng_heap_insert(struct lttng_ptr_heap *heap, void *p)
 161 {
 162         void **ptrs;
 163         size_t pos;
 164         int ret;
 165
 166         ret = heap_set_len(heap, heap->len + 1);
 167         if (ret)
 168                 return ret;
 169         ptrs = heap->ptrs;
 170         pos = heap->len - 1;
 171         while (pos > 0 && heap->gt(p, ptrs[parent(pos)])) {
 172                 /* Move parent down until we find the right spot */
 173                 ptrs[pos] = ptrs[parent(pos)];
 174                 pos = parent(pos);
 175         }
 176         ptrs[pos] = p;
 177         lttng_check_heap(heap);
 178         return 0;
 179 }
 180
 181 void *lttng_heap_remove(struct lttng_ptr_heap *heap)
 182 {
 183         switch (heap->len) {
 184         case 0:
 185                 return NULL;
 186         case 1:
 187                 (void) heap_set_len(heap, 0);
 188                 return heap->ptrs[0];
 189         }
 190         /* Shrink, replace the current max by previous last entry and heapify */
 191         heap_set_len(heap, heap->len - 1);
 192         /* len changed. previous last entry is at heap->len */
 193         return lttng_heap_replace_max(heap, heap->ptrs[heap->len]);
 194 }
 195
 196 void *lttng_heap_cherrypick(struct lttng_ptr_heap *heap, void *p)
 197 {
 198         size_t pos, len = heap->len;
 199
 200         for (pos = 0; pos < len; pos++)
 201                 if (heap->ptrs[pos] == p)
 202                         goto found;
 203         return NULL;
 204 found:
 205         if (heap->len == 1) {
 206                 (void) heap_set_len(heap, 0);
 207                 lttng_check_heap(heap);
 208                 return heap->ptrs[0];
 209         }
 210         /* Replace p with previous last entry and heapify. */
 211         heap_set_len(heap, heap->len - 1);
 212         /* len changed. previous last entry is at heap->len */
 213         heap->ptrs[pos] = heap->ptrs[heap->len];
 214         heapify(heap, pos);
 215         return p;
 216 }