Branch data     Line data    Source code

       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                 :     140194 : static inline void swap(struct heap *h, size_t i, size_t j)
      14                 :            : {
      15                 :     140194 :         void *foo = h->data[i];
      16                 :            : 
      17                 :     140194 :         h->data[i] = h->data[j];
      18                 :     140194 :         h->data[j] = foo;
      19                 :     140194 : }
      20                 :            : 
      21                 :      10068 : static void __up(struct heap *h, size_t j)
      22                 :            : {
      23                 :            :         size_t i; /* parent */
      24                 :            : 
      25                 :      23256 :         while (j) {
      26                 :      23224 :                 i = (j - 1) / 2;
      27                 :            : 
      28                 :      23224 :                 if (h->less(h->data[j], h->data[i])) {
      29                 :      13188 :                         swap(h, i, j);
      30                 :      13188 :                         j = i;
      31                 :            :                 } else {
      32                 :      10036 :                         break;
      33                 :            :                 }
      34                 :            :         }
      35                 :      10068 : }
      36                 :            : 
      37                 :      10068 : int heap_push(struct heap *h, void *data)
      38                 :            : {
      39                 :      10068 :         if (h->len == h->cap) {
      40                 :      10068 :                 void *m = realloc(h->data, (h->cap + 1) * sizeof(void *));
      41                 :      10068 :                 if (m == NULL)
      42                 :          0 :                         return -1;
      43                 :      10068 :                 h->data = m;
      44                 :      10068 :                 h->cap++;
      45                 :            :         }
      46                 :      10068 :         h->data[h->len++] = data;
      47                 :      10068 :         __up(h, h->len - 1);
      48                 :      10068 :         return 0;
      49                 :            : }
      50                 :            : 
      51                 :     137032 : 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                 :     137032 :                 l = 2 * i + 1;
      57                 :     137032 :                 if (l >= h->len)
      58                 :      18554 :                         break;
      59                 :     118478 :                 r = l + 1;
      60                 :     118478 :                 if (r >= h->len)
      61                 :         50 :                         j = l;
      62                 :            :                 else
      63                 :     118428 :                         j = h->less(h->data[l], h->data[r]) ? l : r;
      64                 :            : 
      65                 :     118478 :                 if (h->less(h->data[j], h->data[i])) {
      66                 :     116938 :                         swap(h, i, j);
      67                 :     116938 :                         i = j;
      68                 :            :                 } else {
      69                 :       1540 :                         break;
      70                 :            :                 }
      71                 :            :         }
      72                 :      20094 : }
      73                 :            : 
      74                 :      10068 : void *heap_pop(struct heap *h)
      75                 :            : {
      76                 :      10068 :         void *ret = h->data[0];
      77                 :            :         void *m;
      78                 :            : 
      79                 :      10068 :         swap(h, 0, --h->len);
      80                 :      10068 :         if (h->len) {
      81                 :      10062 :                 __down(h, 0);
      82                 :      10062 :                 if (h->len == h->cap - HEAP_MEM_HYSTERESIS) {
      83                 :          2 :                         m = realloc(h->data, h->len * sizeof(void *));
      84                 :          2 :                         if (m == NULL)
      85                 :          0 :                                 return NULL;
      86                 :          2 :                         h->data = m;
      87                 :          2 :                         h->cap = h->len;
      88                 :            :                 }
      89                 :            :         }
      90                 :            : 
      91                 :      10068 :         return ret;
      92                 :            : }
      93                 :            : 
      94                 :          6 : struct heap *heap_init(heap_less_func_t less)
      95                 :            : {
      96                 :          6 :         struct heap *heap = calloc(1, sizeof(*heap));
      97                 :            : 
      98                 :          6 :         if (heap == NULL)
      99                 :          0 :                 return NULL;
     100                 :          6 :         heap->less = less;
     101                 :          6 :         return heap;
     102                 :            : }
     103                 :            : 
     104                 :         10 : void heap_ify(struct heap *h, heap_less_func_t less)
     105                 :            : {
     106                 :            :         int i;
     107                 :            : 
     108                 :         10 :         if (less)
     109                 :          8 :                 h->less = less;
     110                 :            : 
     111                 :      10042 :         for (i = h->len / 2 - 1; i >= 0; i--)
     112                 :      10032 :                 __down(h, i);
     113                 :         10 : }
     114                 :            : 
     115                 :          6 : void heap_free(struct heap *heap)
     116                 :            : {
     117                 :          6 :         free(heap->data);
     118                 :          6 :         free(heap);
     119                 :          6 : }