]>
jfr.im git - irc/evilnet/x3.git/blob - src/heap.c
1 /* heap.c - Abstract heap type
2 * Copyright 2000-2002 srvx Development Team
4 * This file is part of srvx.
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.
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.
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.
24 /* Possible optimizations:
26 * Use another type of heap (rather than binary) if our heaps are big enough.
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.
33 comparator_f comparator
;
35 unsigned int data_used
, data_alloc
;
39 * Allocate a new heap.
42 heap_new(comparator_f comparator
)
44 heap_t heap
= malloc(sizeof(struct heap
));
45 heap
->comparator
= comparator
;
48 heap
->data
= malloc(2*heap
->data_alloc
*sizeof(void*));
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
58 heap_heapify_up(heap_t heap
, unsigned int idx
)
62 void *last_key
, *last_data
;
64 last_key
= heap
->data
[idx
*2];
65 last_data
= heap
->data
[idx
*2+1];
67 parent
= (idx
- 1) >> 1;
68 res
= heap
->comparator(last_key
, heap
->data
[parent
*2]);
70 heap
->data
[idx
*2] = heap
->data
[parent
*2];
71 heap
->data
[idx
*2+1] = heap
->data
[parent
*2+1];
74 heap
->data
[idx
*2] = last_key
;
75 heap
->data
[idx
*2+1] = last_data
;
79 * Insert a key/data pair into the heap.
82 heap_insert(heap_t heap
, void *key
, void *data
)
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*));
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
++);
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.)
100 heap_peek(heap_t heap
, void **key
, void **data
)
102 if (key
) *key
= heap
->data_used
? heap
->data
[0] : NULL
;
103 if (data
) *data
= heap
->data_used
? heap
->data
[1] : NULL
;
107 * Push the element at "pos" down the heap as far as it will go.
110 heap_heapify_down(heap_t heap
, int pos
)
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;
124 res
= heap
->comparator(last_key
, heap
->data
[child
*2]);
126 heap
->data
[pos
*2] = heap
->data
[child
*2];
127 heap
->data
[pos
*2+1] = heap
->data
[child
*2+1];
130 heap
->data
[pos
*2] = last_key
;
131 heap
->data
[pos
*2+1] = last_data
;
135 * Remove the element at "idx" from the heap (preserving the heap ordering).
138 heap_remove(heap_t heap
, unsigned int idx
)
141 if (heap
->data_used
<= idx
) return;
142 /* swap idx with last element */
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
);
152 * Pop the topmost element from the heap (preserving the heap ordering).
155 heap_pop(heap_t heap
)
157 heap_remove(heap
, 0);
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.
165 * Returns non-zero if the predicate causes the top of the heap to be
169 heap_remove_pred(heap_t heap
, int (*pred
)(void *key
, void *data
, void *extra
), void *extra
)
171 unsigned int pos
, rem_first
;
173 if (heap
->data_used
== 0) return 0;
174 if (pred(heap
->data
[0], heap
->data
[1], extra
)) {
175 heap_remove(heap
, 0);
182 while (pos
< heap
->data_used
) {
183 if (pred(heap
->data
[pos
*2], heap
->data
[pos
*2+1], extra
)) {
184 heap_remove(heap
, pos
);
194 * Remove all entries from a heap.
197 heap_delete(heap_t heap
)
204 * Return number of entries in the heap.
207 heap_size(heap_t heap
)
209 return heap
->data_used
;
212 /* prepackaged comparators */
214 ulong_comparator(const void *a
, const void *b
)
216 return (unsigned long)a
-(unsigned long)b
;