src/heap.c

   1 /* heap.c - Abstract heap type
   2  * Copyright 2000-2002 srvx Development Team
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.  Important limitations are
   8  * listed in the COPYING file that accompanies this software.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, email srvx-maintainers@srvx.net.
  17  */
  18
  19 #include "common.h"
  20 #include "heap.h"
  21
  22 /* Possible optimizations:
  23  *
  24  * Use another type of heap (rather than binary) if our heaps are big enough.
  25  *
  26  * Coalesce multiple entries with the same key into the same chunk, and have
  27  * a new API function to return all of the entries at the top of the heap.
  28  */
  29
  30 struct heap {
  31     comparator_f comparator;
  32     void **data;
  33     unsigned int data_used, data_alloc;
  34 };
  35
  36 /*
  37  *  Allocate a new heap.
  38  */
  39 heap_t
  40 heap_new(comparator_f comparator)
  41 {
  42     heap_t heap = malloc(sizeof(struct heap));
  43     heap->comparator = comparator;
  44     heap->data_used = 0;
  45     heap->data_alloc = 8;
  46     heap->data = malloc(2*heap->data_alloc*sizeof(void*));
  47     return heap;
  48 }
  49
  50 /*
  51  *  Move the element at "index" in the heap as far up the heap as is
  52  *  proper (i.e., as long as its parent node is less than or equal to
  53  *  its value).
  54  */
  55 static void
  56 heap_heapify_up(heap_t heap, unsigned int index)
  57 {
  58     int res;
  59     unsigned int parent;
  60     void *last_key, *last_data;
  61     last_key = heap->data[index*2];
  62     last_data = heap->data[index*2+1];
  63     while (index > 0) {
  64         parent = (index - 1) >> 1;
  65         res = heap->comparator(last_key, heap->data[parent*2]);
  66         if (res > 0) break;
  67         heap->data[index*2] = heap->data[parent*2];
  68         heap->data[index*2+1] = heap->data[parent*2+1];
  69         index = parent;
  70     }
  71     heap->data[index*2] = last_key;
  72     heap->data[index*2+1] = last_data;
  73 }
  74
  75 /*
  76  *  Insert a key/data pair into the heap.
  77  */
  78 void
  79 heap_insert(heap_t heap, void *key, void *data)
  80 {
  81     if (heap->data_used == heap->data_alloc) {
  82         heap->data_alloc *= 2;
  83         heap->data = realloc(heap->data, 2*heap->data_alloc*sizeof(void*));
  84     }
  85     heap->data[heap->data_used*2] = key;
  86     heap->data[heap->data_used*2+1] = data;
  87     heap_heapify_up(heap, heap->data_used++);
  88 }
  89
  90 /*
  91  *  Return what's on top of the heap.
  92  *  If the heap is empty, put NULL into *key and *data.
  93  *  (Either key or data may be NULL, in which case the relevant
  94  *  data will not be returned to the caller.)
  95  */
  96 void
  97 heap_peek(heap_t heap, void **key, void **data)
  98 {
  99     if (key) *key = heap->data_used ? heap->data[0] : NULL;
 100     if (data) *data = heap->data_used ? heap->data[1] : NULL;
 101 }
 102
 103 /*
 104  * Push the element at "pos" down the heap as far as it will go.
 105  */
 106 static void
 107 heap_heapify_down(heap_t heap, int pos)
 108 {
 109     int res;
 110     unsigned int child;
 111     void *last_key, *last_data;
 112     last_key = heap->data[pos*2];
 113     last_data = heap->data[pos*2+1];
 114     /* start at left child */
 115     while ((child=pos*2+1) < heap->data_used) {
 116         /* use right child if it exists and is smaller */
 117         if (child+1 < heap->data_used) {
 118             res = heap->comparator(heap->data[(child+1)*2], heap->data[child*2]);
 119             if (res < 0) child = child+1;
 120         }
 121         res = heap->comparator(last_key, heap->data[child*2]);
 122         if (res <= 0) break;
 123         heap->data[pos*2] = heap->data[child*2];
 124         heap->data[pos*2+1] = heap->data[child*2+1];
 125         pos = child;
 126     }
 127     heap->data[pos*2] = last_key;
 128     heap->data[pos*2+1] = last_data;
 129 }
 130
 131 /*
 132  * Remove the element at "index" from the heap (preserving the heap ordering).
 133  */
 134 static void
 135 heap_remove(heap_t heap, unsigned int index)
 136 {
 137     /* sanity check */
 138     if (heap->data_used <= index) return;
 139     /* swap index with last element */
 140     heap->data_used--;
 141     heap->data[index*2] = heap->data[heap->data_used*2];
 142     heap->data[index*2+1] = heap->data[heap->data_used*2+1];
 143     /* heapify down if index has children */
 144     if (heap->data_used >= 2*index+1) heap_heapify_down(heap, index);
 145     if ((index > 0) && (index < heap->data_used)) heap_heapify_up(heap, index);
 146 }
 147
 148 /*
 149  *  Pop the topmost element from the heap (preserving the heap ordering).
 150  */
 151 void
 152 heap_pop(heap_t heap)
 153 {
 154     heap_remove(heap, 0);
 155 }
 156
 157 /*
 158  *  Remove all elements from the heap if pred(key, data, extra) returns
 159  *  non-zero on the element's key/data pair.  Can be abused to iterate
 160  *  over the entire heap, by always returning 0 from pred.
 161  *
 162  *  Returns non-zero if the predicate causes the top of the heap to be
 163  *  removed.
 164  */
 165 int
 166 heap_remove_pred(heap_t heap, int (*pred)(void *key, void *data, void *extra), void *extra)
 167 {
 168     unsigned int pos, rem_first;
 169
 170     if (heap->data_used == 0) return 0;
 171     if (pred(heap->data[0], heap->data[1], extra)) {
 172         heap_remove(heap, 0);
 173         rem_first = 1;
 174         pos = 0;
 175     } else {
 176         rem_first = 0;
 177         pos = 1;
 178     }
 179     while (pos < heap->data_used) {
 180         if (pred(heap->data[pos*2], heap->data[pos*2+1], extra)) {
 181             heap_remove(heap, pos);
 182             pos = 0;
 183         } else {
 184             pos++;
 185         }
 186     }
 187     return rem_first;
 188 }
 189
 190 /*
 191  *  Remove all entries from a heap.
 192  */
 193 void
 194 heap_delete(heap_t heap)
 195 {
 196     free(heap->data);
 197     free(heap);
 198 }
 199
 200 /*
 201  *  Return number of entries in the heap.
 202  */
 203 unsigned int
 204 heap_size(heap_t heap)
 205 {
 206     return heap->data_used;
 207 }
 208
 209 /* prepackaged comparators */
 210 int
 211 int_comparator(const void *a, const void *b)
 212 {
 213     return (time_t)a-(time_t)b;
 214 }