diff options
Diffstat (limited to 'libraries/eina/src/tests/ecore_sheap.c')
-rw-r--r-- | libraries/eina/src/tests/ecore_sheap.c | 467 |
1 files changed, 467 insertions, 0 deletions
diff --git a/libraries/eina/src/tests/ecore_sheap.c b/libraries/eina/src/tests/ecore_sheap.c new file mode 100644 index 0000000..448be97 --- /dev/null +++ b/libraries/eina/src/tests/ecore_sheap.c | |||
@@ -0,0 +1,467 @@ | |||
1 | #ifdef HAVE_CONFIG_H | ||
2 | # include <config.h> | ||
3 | #endif | ||
4 | |||
5 | #include <stdlib.h> | ||
6 | #include <string.h> | ||
7 | |||
8 | #include "Ecore_Data.h" | ||
9 | |||
10 | #define HEAP_INCREMENT 4096 | ||
11 | |||
12 | #define PARENT(i) (i / 2) | ||
13 | #define LEFT(i) (2 * i) | ||
14 | #define RIGHT(i) (2 * i + 1) | ||
15 | |||
16 | static void _ecore_sheap_heapify(Ecore_Sheap *heap, int i); | ||
17 | static void _ecore_sheap_update_data(Ecore_Sheap *heap); | ||
18 | |||
19 | /** | ||
20 | * Allocate and initialize a new binary heap | ||
21 | * @param compare The function for comparing keys, NULL for direct comparison | ||
22 | * @param size The number of elements to allow in the heap | ||
23 | * @return A pointer to the newly allocated binary heap on success, NULL on | ||
24 | * failure. | ||
25 | */ | ||
26 | EAPI Ecore_Sheap * | ||
27 | ecore_sheap_new(Ecore_Compare_Cb compare, int size) | ||
28 | { | ||
29 | Ecore_Sheap *heap = NULL; | ||
30 | |||
31 | heap = (Ecore_Sheap *)malloc(sizeof(Ecore_Sheap)); | ||
32 | if (!heap) | ||
33 | return NULL; | ||
34 | |||
35 | memset(heap, 0, sizeof(Ecore_Sheap)); | ||
36 | |||
37 | if (!ecore_sheap_init(heap, compare, size)) | ||
38 | { | ||
39 | FREE(heap); | ||
40 | return NULL; | ||
41 | } | ||
42 | |||
43 | return heap; | ||
44 | } | ||
45 | |||
46 | /** | ||
47 | * Initialize a binary heap to default values | ||
48 | * @param heap The heap to initialize | ||
49 | * @param compare The function for comparing keys, NULL for direct comparison | ||
50 | * @param size The number of elements to allow in the heap | ||
51 | * @return TRUE on success, FALSE on failure | ||
52 | */ | ||
53 | EAPI int | ||
54 | ecore_sheap_init(Ecore_Sheap *heap, Ecore_Compare_Cb compare, int size) | ||
55 | { | ||
56 | CHECK_PARAM_POINTER_RETURN("heap", heap, FALSE); | ||
57 | |||
58 | heap->space = size; | ||
59 | if (!compare) | ||
60 | heap->compare = ecore_direct_compare; | ||
61 | else | ||
62 | heap->compare = compare; | ||
63 | |||
64 | heap->order = ECORE_SORT_MIN; | ||
65 | |||
66 | heap->data = (void **)malloc(heap->space * sizeof(void *)); | ||
67 | if (!heap->data) | ||
68 | return FALSE; | ||
69 | |||
70 | memset(heap->data, 0, heap->space * sizeof(void *)); | ||
71 | |||
72 | return TRUE; | ||
73 | } | ||
74 | |||
75 | /** | ||
76 | * Free up the memory used by the heap | ||
77 | * | ||
78 | * Frees the memory used by @a heap, calls the destroy function on each data | ||
79 | * item if necessary. | ||
80 | * | ||
81 | * @param heap The heap to be freed | ||
82 | */ | ||
83 | EAPI void | ||
84 | ecore_sheap_destroy(Ecore_Sheap *heap) | ||
85 | { | ||
86 | int i; | ||
87 | |||
88 | CHECK_PARAM_POINTER("heap", heap); | ||
89 | |||
90 | /* | ||
91 | * Free data in heap | ||
92 | */ | ||
93 | if (heap->free_func) | ||
94 | for (i = 0; i < heap->size; i++) | ||
95 | heap->free_func(heap->data[i]); | ||
96 | |||
97 | FREE(heap->data); | ||
98 | |||
99 | FREE(heap); | ||
100 | } | ||
101 | |||
102 | /** | ||
103 | * Set the function for freeing data. | ||
104 | * @param heap The heap that will use this function when nodes are | ||
105 | * destroyed. | ||
106 | * @param free_func The function that will free the key data. | ||
107 | * @return @c TRUE on successful set, @c FALSE otherwise. | ||
108 | */ | ||
109 | EAPI int | ||
110 | ecore_sheap_free_cb_set(Ecore_Sheap *heap, Ecore_Free_Cb free_func) | ||
111 | { | ||
112 | CHECK_PARAM_POINTER_RETURN("heap", heap, FALSE); | ||
113 | |||
114 | heap->free_func = free_func; | ||
115 | |||
116 | return TRUE; | ||
117 | } | ||
118 | |||
119 | /** | ||
120 | * Insert new data into the heap. | ||
121 | * @param heap The heap to insert @a data. | ||
122 | * @param data The data to add to @a heap. | ||
123 | * @return TRUE on success, NULL on failure. Increases the size of the heap if | ||
124 | * it becomes larger than available space. | ||
125 | */ | ||
126 | EAPI int | ||
127 | ecore_sheap_insert(Ecore_Sheap *heap, void *data) | ||
128 | { | ||
129 | int i; | ||
130 | void *temp; | ||
131 | int parent; | ||
132 | int position; | ||
133 | |||
134 | CHECK_PARAM_POINTER_RETURN("heap", heap, FALSE); | ||
135 | |||
136 | /* | ||
137 | * Increase the size of the allocated data area if there isn't enough | ||
138 | * space available to add this data | ||
139 | */ | ||
140 | if (heap->size >= heap->space) | ||
141 | return FALSE; | ||
142 | |||
143 | heap->sorted = FALSE; | ||
144 | |||
145 | /* | ||
146 | * Place the data at the end of the heap initially. Then determine the | ||
147 | * parent and position in the array of it's parent. | ||
148 | */ | ||
149 | heap->data[heap->size] = data; | ||
150 | position = heap->size; | ||
151 | heap->size++; | ||
152 | i = heap->size; | ||
153 | parent = PARENT(i) - 1; | ||
154 | |||
155 | /* | ||
156 | * Check the order of the heap to decide where to place the inserted | ||
157 | * data. The loop is placed inside the if statement to reduce the | ||
158 | * number of branching decisions that must be predicted. | ||
159 | */ | ||
160 | if (heap->order == ECORE_SORT_MIN) | ||
161 | while ((position > 0) && heap->compare(heap->data[parent], | ||
162 | heap->data[position]) > 0) | ||
163 | { | ||
164 | |||
165 | /* | ||
166 | * Swap the data with it's parents to move it up in | ||
167 | * the heap. | ||
168 | */ | ||
169 | temp = heap->data[position]; | ||
170 | heap->data[position] = heap->data[parent]; | ||
171 | heap->data[parent] = temp; | ||
172 | |||
173 | /* | ||
174 | * Now determine the new position for the next | ||
175 | * iteration of the loop, as well as it's parents | ||
176 | * position. | ||
177 | */ | ||
178 | i = PARENT(i); | ||
179 | position = i - 1; | ||
180 | parent = PARENT(i) - 1; | ||
181 | } | ||
182 | else | ||
183 | while ((position > 0) && heap->compare(heap->data[parent], | ||
184 | heap->data[position]) < 0) | ||
185 | { | ||
186 | |||
187 | /* | ||
188 | * Swap the data with it's parents to move it up in | ||
189 | * the heap. | ||
190 | */ | ||
191 | temp = heap->data[position]; | ||
192 | heap->data[position] = heap->data[PARENT(i) - 1]; | ||
193 | heap->data[PARENT(i) - 1] = temp; | ||
194 | |||
195 | /* | ||
196 | * Now determine the new position for the next | ||
197 | * iteration of the loop, as well as it's parents | ||
198 | * position. | ||
199 | */ | ||
200 | i = PARENT(i); | ||
201 | position = i - 1; | ||
202 | parent = PARENT(i) - 1; | ||
203 | } | ||
204 | |||
205 | return TRUE; | ||
206 | } | ||
207 | |||
208 | /** | ||
209 | * Extract the item at the top of the heap | ||
210 | * @param heap The heap to remove the top item | ||
211 | * @return The top item of the heap on success, NULL on failure. | ||
212 | * @note The extract function maintains the heap properties after the | ||
213 | * extract. | ||
214 | */ | ||
215 | EAPI void * | ||
216 | ecore_sheap_extract(Ecore_Sheap *heap) | ||
217 | { | ||
218 | void *extreme; | ||
219 | |||
220 | if (heap->size < 1) | ||
221 | return NULL; | ||
222 | |||
223 | heap->sorted = FALSE; | ||
224 | |||
225 | extreme = heap->data[0]; | ||
226 | heap->size--; | ||
227 | heap->data[0] = heap->data[heap->size]; | ||
228 | |||
229 | _ecore_sheap_heapify(heap, 1); | ||
230 | |||
231 | return extreme; | ||
232 | } | ||
233 | |||
234 | /** | ||
235 | * Examine the item at the top of the heap | ||
236 | * @param heap The heap to examine the top item | ||
237 | * @return The top item of the heap on success, NULL on failure. | ||
238 | * @note The function does not alter the heap. | ||
239 | */ | ||
240 | EAPI void * | ||
241 | ecore_sheap_extreme(Ecore_Sheap *heap) | ||
242 | { | ||
243 | if (heap->size < 1) | ||
244 | return NULL; | ||
245 | |||
246 | return heap->data[0]; | ||
247 | } | ||
248 | |||
249 | /** | ||
250 | * Change the value of the specified item in the heap | ||
251 | * @param heap The heap to search for the item to change | ||
252 | * @param item The item in the heap to change | ||
253 | * @param newval The new value assigned to the item in the heap | ||
254 | * @return TRUE on success, FALSE on failure. | ||
255 | * @note The heap does not free the old data since it must be passed | ||
256 | * in, so the caller can perform the free if desired. | ||
257 | */ | ||
258 | EAPI int | ||
259 | ecore_sheap_change(Ecore_Sheap *heap, void *item, void *newval) | ||
260 | { | ||
261 | int i; | ||
262 | |||
263 | CHECK_PARAM_POINTER_RETURN("heap", heap, FALSE); | ||
264 | |||
265 | for (i = 0; i < heap->size && heap->compare(heap->data[i], item); i++) ; | ||
266 | |||
267 | if (i < heap->size) | ||
268 | heap->data[i] = newval; | ||
269 | else | ||
270 | return FALSE; | ||
271 | |||
272 | /* | ||
273 | * FIXME: This is not the correct procedure when a change occurs. | ||
274 | */ | ||
275 | _ecore_sheap_heapify(heap, 1); | ||
276 | |||
277 | return TRUE; | ||
278 | } | ||
279 | |||
280 | /** | ||
281 | * Change the comparison function for the heap | ||
282 | * @param heap The heap to change comparison function | ||
283 | * @param compare The new function for comparing nodes | ||
284 | * @return TRUE on success, FALSE on failure. | ||
285 | * | ||
286 | * The comparison function is changed to @compare and the heap is heapified | ||
287 | * by the new comparison. | ||
288 | */ | ||
289 | EAPI int | ||
290 | ecore_sheap_compare_set(Ecore_Sheap *heap, Ecore_Compare_Cb compare) | ||
291 | { | ||
292 | CHECK_PARAM_POINTER_RETURN("heap", heap, FALSE); | ||
293 | |||
294 | if (!compare) | ||
295 | heap->compare = ecore_direct_compare; | ||
296 | else | ||
297 | heap->compare = compare; | ||
298 | |||
299 | _ecore_sheap_update_data(heap); | ||
300 | |||
301 | return TRUE; | ||
302 | } | ||
303 | |||
304 | /** | ||
305 | * Change the order of the heap | ||
306 | * @param heap The heap to change the order | ||
307 | * @param order The new order of the heap | ||
308 | * | ||
309 | * Changes the heap order of @heap and re-heapifies the data to this new | ||
310 | * order. The default order is a min heap. | ||
311 | */ | ||
312 | EAPI void | ||
313 | ecore_sheap_order_set(Ecore_Sheap *heap, char order) | ||
314 | { | ||
315 | CHECK_PARAM_POINTER("heap", heap); | ||
316 | |||
317 | heap->order = order; | ||
318 | |||
319 | _ecore_sheap_update_data(heap); | ||
320 | } | ||
321 | |||
322 | /** | ||
323 | * Sort the data in the heap | ||
324 | * @param heap The heap to be sorted | ||
325 | * | ||
326 | * Sorts the data in the heap into the order that is used for the heap's | ||
327 | * data. | ||
328 | */ | ||
329 | EAPI void | ||
330 | ecore_sheap_sort(Ecore_Sheap *heap) | ||
331 | { | ||
332 | int i = 0; | ||
333 | void **new_data; | ||
334 | |||
335 | CHECK_PARAM_POINTER("heap", heap); | ||
336 | |||
337 | new_data = (void **)malloc(heap->size * sizeof(void *)); | ||
338 | |||
339 | /* | ||
340 | * Extract the heap and insert into the new data array in order. | ||
341 | */ | ||
342 | while (heap->size > 0) | ||
343 | new_data[i++] = ecore_sheap_extract(heap); | ||
344 | |||
345 | /* | ||
346 | * Free the old data array and update the heap with the new data, also | ||
347 | * mark as sorted. | ||
348 | */ | ||
349 | FREE(heap->data); | ||
350 | heap->data = new_data; | ||
351 | heap->size = i; | ||
352 | heap->sorted = TRUE; | ||
353 | } | ||
354 | |||
355 | /* | ||
356 | * Access the item at the ith position in the heap | ||
357 | * @param heap The heap to access the internal data | ||
358 | * @param i The index of the data within the heap | ||
359 | * @return The data located at the ith position within @heap on success, | ||
360 | * NULL on failure. | ||
361 | * @note The data is guaranteed to be in sorted order. | ||
362 | */ | ||
363 | EAPI inline void * | ||
364 | ecore_sheap_item(Ecore_Sheap *heap, int i) | ||
365 | { | ||
366 | if (i >= heap->size) | ||
367 | return NULL; | ||
368 | |||
369 | /* | ||
370 | * Make sure the data is sorted so we return the correct value. | ||
371 | */ | ||
372 | if (!heap->sorted) | ||
373 | ecore_sheap_sort(heap); | ||
374 | |||
375 | return heap->data[i]; | ||
376 | } | ||
377 | |||
378 | /* | ||
379 | * Regain the heap properties starting at position i | ||
380 | * @param heap The heap to regain heap properties | ||
381 | * @param i The position to start heapifying | ||
382 | */ | ||
383 | static void | ||
384 | _ecore_sheap_heapify(Ecore_Sheap *heap, int i) | ||
385 | { | ||
386 | int extreme; | ||
387 | int left = LEFT(i); | ||
388 | int right = RIGHT(i); | ||
389 | |||
390 | if (heap->order == ECORE_SORT_MIN) | ||
391 | { | ||
392 | if (left <= heap->size && heap->compare(heap->data[left - 1], | ||
393 | heap->data[i - 1]) < 0) | ||
394 | extreme = left; | ||
395 | else | ||
396 | extreme = i; | ||
397 | |||
398 | if (right <= heap->size && heap->compare(heap->data[right - 1], | ||
399 | heap->data[extreme - 1]) < 0) | ||
400 | extreme = right; | ||
401 | } | ||
402 | else | ||
403 | { | ||
404 | if (left <= heap->size && heap->compare(heap->data[left - 1], | ||
405 | heap->data[i - 1]) > 0) | ||
406 | extreme = left; | ||
407 | else | ||
408 | extreme = i; | ||
409 | |||
410 | if (right <= heap->size && heap->compare(heap->data[right - 1], | ||
411 | heap->data[extreme - 1]) > 0) | ||
412 | extreme = right; | ||
413 | } | ||
414 | |||
415 | /* | ||
416 | * If the data needs to be swapped down the heap, recurse on | ||
417 | * heapifying it's new placement. | ||
418 | */ | ||
419 | if (extreme != i) | ||
420 | { | ||
421 | void *temp; | ||
422 | |||
423 | temp = heap->data[extreme - 1]; | ||
424 | heap->data[extreme - 1] = heap->data[i - 1]; | ||
425 | heap->data[i - 1] = temp; | ||
426 | |||
427 | _ecore_sheap_heapify(heap, extreme); | ||
428 | } | ||
429 | } | ||
430 | |||
431 | static void | ||
432 | _ecore_sheap_update_data(Ecore_Sheap *heap) | ||
433 | { | ||
434 | int i, old_size; | ||
435 | void **data; | ||
436 | |||
437 | /* | ||
438 | * Track the old values from the heap | ||
439 | */ | ||
440 | old_size = heap->size; | ||
441 | data = heap->data; | ||
442 | |||
443 | heap->size = 0; | ||
444 | heap->data = malloc(heap->space * sizeof(void *)); | ||
445 | |||
446 | for (i = 0; i < old_size; i++) | ||
447 | ecore_sheap_insert(heap, data[i]); | ||
448 | |||
449 | FREE(data); | ||
450 | } | ||
451 | |||
452 | int | ||
453 | ecore_direct_compare(const void *key1, const void *key2) | ||
454 | { | ||
455 | unsigned long k1, k2; | ||
456 | |||
457 | k1 = (unsigned long)key1; | ||
458 | k2 = (unsigned long)key2; | ||
459 | |||
460 | if (k1 > k2) | ||
461 | return 1; | ||
462 | |||
463 | if (k1 < k2) | ||
464 | return -1; | ||
465 | |||
466 | return 0; | ||
467 | } | ||