]>
Commit | Line | Data |
---|---|---|
d76ed9a9 AS |
1 | /* heap.c - Abstract heap type |
2 | * Copyright 2000-2002 srvx Development Team | |
3 | * | |
83ff05c3 | 4 | * This file is part of x3. |
d76ed9a9 | 5 | * |
d0f04f71 | 6 | * x3 is free software; you can redistribute it and/or modify |
d76ed9a9 AS |
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 | int_comparator(const void *a, const void *b) | |
214 | { | |
215 | return (time_t)a-(time_t)b; | |
216 | } |