git.ozlabs.org Git - ccan/blob - heap.c

   1 /* Licensed under BSD-MIT - see LICENSE file for details */
   2 #include <ccan/heap/heap.h>
   3
   4 /*
   5  * Allocating memory in chunks greater than needed does not yield measurable
   6  * speedups of the test program when linking against glibc 2.15.
   7  *
   8  * When the data array has to be shrunk though, limiting calls to realloc
   9  * does help a little bit (~7% speedup), hence the following parameter.
  10  */
  11 #define HEAP_MEM_HYSTERESIS     4096
  12
  13 static inline void swap(struct heap *h, size_t i, size_t j)
  14 {
  15         void *foo = h->data[i];
  16
  17         h->data[i] = h->data[j];
  18         h->data[j] = foo;
  19 }
  20
  21 static void __up(struct heap *h, size_t j)
  22 {
  23         size_t i; /* parent */
  24
  25         while (j) {
  26                 i = (j - 1) / 2;
  27
  28                 if (h->less(h->data[j], h->data[i])) {
  29                         swap(h, i, j);
  30                         j = i;
  31                 } else {
  32                         break;
  33                 }
  34         }
  35 }
  36
  37 int heap_push(struct heap *h, void *data)
  38 {
  39         if (h->len == h->cap) {
  40                 void *m = realloc(h->data, (h->cap + 1) * sizeof(void *));
  41                 if (m == NULL)
  42                         return -1;
  43                 h->data = m;
  44                 h->cap++;
  45         }
  46         h->data[h->len++] = data;
  47         __up(h, h->len - 1);
  48         return 0;
  49 }
  50
  51 static void __down(struct heap *h, size_t i)
  52 {
  53         size_t l, r, j; /* left, right, min child */
  54
  55         while (1) {
  56                 l = 2 * i + 1;
  57                 if (l >= h->len)
  58                         break;
  59                 r = l + 1;
  60                 if (r >= h->len)
  61                         j = l;
  62                 else
  63                         j = h->less(h->data[l], h->data[r]) ? l : r;
  64
  65                 if (h->less(h->data[j], h->data[i])) {
  66                         swap(h, i, j);
  67                         i = j;
  68                 } else {
  69                         break;
  70                 }
  71         }
  72 }
  73
  74 void *heap_pop(struct heap *h)
  75 {
  76         void *ret = h->data[0];
  77         void *m;
  78
  79         swap(h, 0, --h->len);
  80         if (h->len) {
  81                 __down(h, 0);
  82                 if (h->len == h->cap - HEAP_MEM_HYSTERESIS) {
  83                         m = realloc(h->data, h->len * sizeof(void *));
  84                         if (m == NULL)
  85                                 return NULL;
  86                         h->data = m;
  87                         h->cap = h->len;
  88                 }
  89         }
  90
  91         return ret;
  92 }
  93
  94 struct heap *heap_init(heap_less_func_t less)
  95 {
  96         struct heap *heap = calloc(1, sizeof(*heap));
  97
  98         if (heap == NULL)
  99                 return NULL;
 100         heap->less = less;
 101         return heap;
 102 }
 103
 104 void heap_ify(struct heap *h, heap_less_func_t less)
 105 {
 106         int i;
 107
 108         if (less)
 109                 h->less = less;
 110
 111         for (i = h->len / 2 - 1; i >= 0; i--)
 112                 __down(h, i);
 113 }
 114
 115 void heap_free(struct heap *heap)
 116 {
 117         free(heap->data);
 118         free(heap);
 119 }