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 : }