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 3 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 idx)
  59 {
  60     int res;
  61     unsigned int parent;
  62     void *last_key, *last_data;
  63
  64     last_key = heap->data[idx*2];
  65     last_data = heap->data[idx*2+1];
  66     while (idx > 0) {
  67         parent = (idx - 1) >> 1;
  68         res = heap->comparator(last_key, heap->data[parent*2]);
  69         if (res > 0) break;
  70         heap->data[idx*2] = heap->data[parent*2];
  71         heap->data[idx*2+1] = heap->data[parent*2+1];
  72         idx = parent;
  73     }
  74     heap->data[idx*2] = last_key;
  75     heap->data[idx*2+1] = last_data;
  76 }
  77
  78 /*
  79  *  Insert a key/data pair into the heap.
  80  */
  81 void
  82 heap_insert(heap_t heap, void *key, void *data)
  83 {
  84     if (heap->data_used == heap->data_alloc) {
  85         heap->data_alloc *= 2;
  86         heap->data = realloc(heap->data, 2*heap->data_alloc*sizeof(void*));
  87     }
  88     heap->data[heap->data_used*2] = key;
  89     heap->data[heap->data_used*2+1] = data;
  90     heap_heapify_up(heap, heap->data_used++);
  91 }
  92
  93 /*
  94  *  Return what's on top of the heap.
  95  *  If the heap is empty, put NULL into *key and *data.
  96  *  (Either key or data may be NULL, in which case the relevant
  97  *  data will not be returned to the caller.)
  98  */
  99 void
 100 heap_peek(heap_t heap, void **key, void **data)
 101 {
 102     if (key) *key = heap->data_used ? heap->data[0] : NULL;
 103     if (data) *data = heap->data_used ? heap->data[1] : NULL;
 104 }
 105
 106 /*
 107  * Push the element at "pos" down the heap as far as it will go.
 108  */
 109 static void
 110 heap_heapify_down(heap_t heap, int pos)
 111 {
 112     int res;
 113     unsigned int child;
 114     void *last_key, *last_data;
 115     last_key = heap->data[pos*2];
 116     last_data = heap->data[pos*2+1];
 117     /* start at left child */
 118     while ((child=pos*2+1) < heap->data_used) {
 119         /* use right child if it exists and is smaller */
 120         if (child+1 < heap->data_used) {
 121             res = heap->comparator(heap->data[(child+1)*2], heap->data[child*2]);
 122             if (res < 0) child = child+1;
 123         }
 124         res = heap->comparator(last_key, heap->data[child*2]);
 125         if (res <= 0) break;
 126         heap->data[pos*2] = heap->data[child*2];
 127         heap->data[pos*2+1] = heap->data[child*2+1];
 128         pos = child;
 129     }
 130     heap->data[pos*2] = last_key;
 131     heap->data[pos*2+1] = last_data;
 132 }
 133
 134 /*
 135  * Remove the element at "idx" from the heap (preserving the heap ordering).
 136  */
 137 static void
 138 heap_remove(heap_t heap, unsigned int idx)
 139 {
 140     /* sanity check */
 141     if (heap->data_used <= idx) return;
 142     /* swap idx with last element */
 143     heap->data_used--;
 144     heap->data[idx*2] = heap->data[heap->data_used*2];
 145     heap->data[idx*2+1] = heap->data[heap->data_used*2+1];
 146     /* heapify down if idx has children */
 147     if (heap->data_used >= 2*idx+1) heap_heapify_down(heap, idx);
 148     if ((idx > 0) && (idx < heap->data_used)) heap_heapify_up(heap, idx);
 149 }
 150
 151 /*
 152  *  Pop the topmost element from the heap (preserving the heap ordering).
 153  */
 154 void
 155 heap_pop(heap_t heap)
 156 {
 157     heap_remove(heap, 0);
 158 }
 159
 160 /*
 161  *  Remove all elements from the heap if pred(key, data, extra) returns
 162  *  non-zero on the element's key/data pair.  Can be abused to iterate
 163  *  over the entire heap, by always returning 0 from pred.
 164  *
 165  *  Returns non-zero if the predicate causes the top of the heap to be
 166  *  removed.
 167  */
 168 int
 169 heap_remove_pred(heap_t heap, int (*pred)(void *key, void *data, void *extra), void *extra)
 170 {
 171     unsigned int pos, rem_first;
 172
 173     if (heap->data_used == 0) return 0;
 174     if (pred(heap->data[0], heap->data[1], extra)) {
 175         heap_remove(heap, 0);
 176         rem_first = 1;
 177         pos = 0;
 178     } else {
 179         rem_first = 0;
 180         pos = 1;
 181     }
 182     while (pos < heap->data_used) {
 183         if (pred(heap->data[pos*2], heap->data[pos*2+1], extra)) {
 184             heap_remove(heap, pos);
 185             pos = 0;
 186         } else {
 187             pos++;
 188         }
 189     }
 190     return rem_first;
 191 }
 192
 193 /*
 194  *  Remove all entries from a heap.
 195  */
 196 void
 197 heap_delete(heap_t heap)
 198 {
 199     free(heap->data);
 200     free(heap);
 201 }
 202
 203 /*
 204  *  Return number of entries in the heap.
 205  */
 206 unsigned int
 207 heap_size(heap_t heap)
 208 {
 209     return heap->data_used;
 210 }
 211
 212 /* prepackaged comparators */
 213 int
 214 ulong_comparator(const void *a, const void *b)
 215 {
 216     return (unsigned long)a-(unsigned long)b;
 217 }