src/heap.c

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