]>
Commit | Line | Data |
---|---|---|
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 | } |