1 /* heap.c - Abstract heap type
2 * Copyright 2000-2002 srvx Development Team
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.
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.
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.
22 /* Possible optimizations:
24 * Use another type of heap (rather than binary) if our heaps are big enough.
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.
31 comparator_f comparator;
33 unsigned int data_used, data_alloc;
37 * Allocate a new heap.
40 heap_new(comparator_f comparator)
42 heap_t heap = malloc(sizeof(struct heap));
43 heap->comparator = comparator;
46 heap->data = malloc(2*heap->data_alloc*sizeof(void*));
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
56 heap_heapify_up(heap_t heap, unsigned int index)
60 void *last_key, *last_data;
61 last_key = heap->data[index*2];
62 last_data = heap->data[index*2+1];
64 parent = (index - 1) >> 1;
65 res = heap->comparator(last_key, heap->data[parent*2]);
67 heap->data[index*2] = heap->data[parent*2];
68 heap->data[index*2+1] = heap->data[parent*2+1];
71 heap->data[index*2] = last_key;
72 heap->data[index*2+1] = last_data;
76 * Insert a key/data pair into the heap.
79 heap_insert(heap_t heap, void *key, void *data)
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*));
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++);
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.)
97 heap_peek(heap_t heap, void **key, void **data)
99 if (key) *key = heap->data_used ? heap->data[0] : NULL;
100 if (data) *data = heap->data_used ? heap->data[1] : NULL;
104 * Push the element at "pos" down the heap as far as it will go.
107 heap_heapify_down(heap_t heap, int pos)
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;
121 res = heap->comparator(last_key, heap->data[child*2]);
123 heap->data[pos*2] = heap->data[child*2];
124 heap->data[pos*2+1] = heap->data[child*2+1];
127 heap->data[pos*2] = last_key;
128 heap->data[pos*2+1] = last_data;
132 * Remove the element at "index" from the heap (preserving the heap ordering).
135 heap_remove(heap_t heap, unsigned int index)
138 if (heap->data_used <= index) return;
139 /* swap index with last element */
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);
149 * Pop the topmost element from the heap (preserving the heap ordering).
152 heap_pop(heap_t heap)
154 heap_remove(heap, 0);
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.
162 * Returns non-zero if the predicate causes the top of the heap to be
166 heap_remove_pred(heap_t heap, int (*pred)(void *key, void *data, void *extra), void *extra)
168 unsigned int pos, rem_first;
170 if (heap->data_used == 0) return 0;
171 if (pred(heap->data[0], heap->data[1], extra)) {
172 heap_remove(heap, 0);
179 while (pos < heap->data_used) {
180 if (pred(heap->data[pos*2], heap->data[pos*2+1], extra)) {
181 heap_remove(heap, pos);
191 * Remove all entries from a heap.
194 heap_delete(heap_t heap)
201 * Return number of entries in the heap.
204 heap_size(heap_t heap)
206 return heap->data_used;
209 /* prepackaged comparators */
211 int_comparator(const void *a, const void *b)
213 return (time_t)a-(time_t)b;