efl

1
#ifdef HAVE_CONFIG_H
2
# include <config.h>
3
#endif
4

5
#include <stdlib.h>
6
#include <string.h>
7
#include <stdint.h>
8

9
#include "Ecore_Data.h"
10

11
#define HEAP_INCREMENT 4096
12

13
#define PARENT(i) (i / 2)
14
#define LEFT(i) (2 * i)
15
#define RIGHT(i) (2 * i + 1)
16

17
static void _ecore_sheap_heapify(Ecore_Sheap *heap, int i);
18
static void _ecore_sheap_update_data(Ecore_Sheap *heap);
19

20
/**
21
 * Allocate and initialize a new binary heap
22
 * @param compare The function for comparing keys, NULL for direct comparison
23
 * @param size    The number of elements to allow in the heap
24
 * @return A pointer to the newly allocated binary heap on success, NULL on
25
 * failure.
26
 */
27
EAPI Ecore_Sheap *
28
ecore_sheap_new(Ecore_Compare_Cb compare, int size)
29
{
30
   Ecore_Sheap *heap = NULL;
31

32
   heap = (Ecore_Sheap *)malloc(sizeof(Ecore_Sheap));
33
   if (!heap)
34
      return NULL;
35

36
   memset(heap, 0, sizeof(Ecore_Sheap));
37

38
   if (!ecore_sheap_init(heap, compare, size))
39
     {
40
        FREE(heap);
41
        return NULL;
42
     }
43

44
   return heap;
45
}
46

47
/**
48
 * Initialize a binary heap to default values
49
 * @param heap    The heap to initialize
50
 * @param compare The function for comparing keys, NULL for direct comparison
51
 * @param size    The number of elements to allow in the heap
52
 * @return        TRUE on success, FALSE on failure
53
 */
54
EAPI int
55
ecore_sheap_init(Ecore_Sheap *heap, Ecore_Compare_Cb compare, int size)
56
{
57
   CHECK_PARAM_POINTER_RETURN("heap", heap, FALSE);
58

59
   heap->space = size;
60
   if (!compare)
61
      heap->compare = ecore_direct_compare;
62
   else
63
      heap->compare = compare;
64

65
   heap->order = ECORE_SORT_MIN;
66

67
   heap->data = (void **)malloc(heap->space * sizeof(void *));
68
   if (!heap->data)
69
      return FALSE;
70

71
   memset(heap->data, 0, heap->space * sizeof(void *));
72

73
   return TRUE;
74
}
75

76
/**
77
 * Free up the memory used by the heap
78
 *
79
 * Frees the memory used by @a heap, calls the destroy function on each data
80
 * item if necessary.
81
 *
82
 * @param  heap The heap to be freed
83
 */
84
EAPI void
85
ecore_sheap_destroy(Ecore_Sheap *heap)
86
{
87
   int i;
88

89
   CHECK_PARAM_POINTER("heap", heap);
90

91
   /*
92
    * Free data in heap
93
    */
94
   if (heap->free_func)
95
      for (i = 0; i < heap->size; i++)
96
         heap->free_func(heap->data[i]);
97

98
   FREE(heap->data);
99

100
   FREE(heap);
101
}
102

103
/**
104
 * Set the function for freeing data.
105
 * @param  heap      The heap that will use this function when nodes are
106
 *                   destroyed.
107
 * @param  free_func The function that will free the key data.
108
 * @return @c TRUE on successful set, @c FALSE otherwise.
109
 */
110
EAPI int
111
ecore_sheap_free_cb_set(Ecore_Sheap *heap, Ecore_Free_Cb free_func)
112
{
113
   CHECK_PARAM_POINTER_RETURN("heap", heap, FALSE);
114

115
   heap->free_func = free_func;
116

117
   return TRUE;
118
}
119

120
/**
121
 * Insert new data into the heap.
122
 * @param  heap The heap to insert @a data.
123
 * @param  data The data to add to @a heap.
124
 * @return TRUE on success, NULL on failure. Increases the size of the heap if
125
 *         it becomes larger than available space.
126
 */
127
EAPI int
128
ecore_sheap_insert(Ecore_Sheap *heap, void *data)
129
{
130
   int i;
131
   void *temp;
132
   int parent;
133
   int position;
134

135
   CHECK_PARAM_POINTER_RETURN("heap", heap, FALSE);
136

137
   /*
138
    * Increase the size of the allocated data area if there isn't enough
139
    * space available to add this data
140
    */
141
   if (heap->size >= heap->space)
142
      return FALSE;
143

144
   heap->sorted = FALSE;
145

146
   /*
147
    * Place the data at the end of the heap initially. Then determine the
148
    * parent and position in the array of it's parent.
149
    */
150
   heap->data[heap->size] = data;
151
   position = heap->size;
152
   heap->size++;
153
   i = heap->size;
154
   parent = PARENT(i) - 1;
155

156
   /*
157
    * Check the order of the heap to decide where to place the inserted
158
    * data. The loop is placed inside the if statement to reduce the
159
    * number of branching decisions that must be predicted.
160
    */
161
   if (heap->order == ECORE_SORT_MIN)
162
      while ((position > 0) && heap->compare(heap->data[parent],
163
                                             heap->data[position]) > 0)
164
        {
165

166
           /*
167
            * Swap the data with it's parents to move it up in
168
            * the heap.
169
            */
170
           temp = heap->data[position];
171
           heap->data[position] = heap->data[parent];
172
           heap->data[parent] = temp;
173

174
           /*
175
            * Now determine the new position for the next
176
            * iteration of the loop, as well as it's parents
177
            * position.
178
            */
179
           i = PARENT(i);
180
           position = i - 1;
181
           parent = PARENT(i) - 1;
182
        }
183
   else
184
      while ((position > 0) && heap->compare(heap->data[parent],
185
                                             heap->data[position]) < 0)
186
        {
187

188
           /*
189
            * Swap the data with it's parents to move it up in
190
            * the heap.
191
            */
192
           temp = heap->data[position];
193
           heap->data[position] = heap->data[PARENT(i) - 1];
194
           heap->data[PARENT(i) - 1] = temp;
195

196
           /*
197
            * Now determine the new position for the next
198
            * iteration of the loop, as well as it's parents
199
            * position.
200
            */
201
           i = PARENT(i);
202
           position = i - 1;
203
           parent = PARENT(i) - 1;
204
        }
205

206
   return TRUE;
207
}
208

209
/**
210
 * Extract the item at the top of the heap
211
 * @param  heap The heap to remove the top item
212
 * @return The top item of the heap on success, NULL on failure.
213
 * @note   The extract function maintains the heap properties after the
214
 *         extract.
215
 */
216
EAPI void *
217
ecore_sheap_extract(Ecore_Sheap *heap)
218
{
219
   void *extreme;
220

221
   if (heap->size < 1)
222
      return NULL;
223

224
   heap->sorted = FALSE;
225

226
   extreme = heap->data[0];
227
   heap->size--;
228
   heap->data[0] = heap->data[heap->size];
229

230
   _ecore_sheap_heapify(heap, 1);
231

232
   return extreme;
233
}
234

235
/**
236
 * Examine the item at the top of the heap
237
 * @param  heap The heap to examine the top item
238
 * @return The top item of the heap on success, NULL on failure.
239
 * @note   The function does not alter the heap.
240
 */
241
EAPI void *
242
ecore_sheap_extreme(Ecore_Sheap *heap)
243
{
244
   if (heap->size < 1)
245
      return NULL;
246

247
   return heap->data[0];
248
}
249

250
/**
251
 * Change the value of the specified item in the heap
252
 * @param heap   The heap to search for the item to change
253
 * @param item   The item in the heap to change
254
 * @param newval The new value assigned to the item in the heap
255
 * @return       TRUE on success, FALSE on failure.
256
 * @note         The heap does not free the old data since it must be passed
257
 *               in, so the caller can perform the free if desired.
258
 */
259
EAPI int
260
ecore_sheap_change(Ecore_Sheap *heap, void *item, void *newval)
261
{
262
   int i;
263

264
   CHECK_PARAM_POINTER_RETURN("heap", heap, FALSE);
265

266
   for (i = 0; i < heap->size && heap->compare(heap->data[i], item); i++) ;
267

268
   if (i < heap->size)
269
      heap->data[i] = newval;
270
   else
271
      return FALSE;
272

273
   /*
274
    * FIXME: This is not the correct procedure when a change occurs.
275
    */
276
   _ecore_sheap_heapify(heap, 1);
277

278
   return TRUE;
279
}
280

281
/**
282
 * Change the comparison function for the heap
283
 * @param  heap    The heap to change comparison function
284
 * @param  compare The new function for comparing nodes
285
 * @return TRUE on success, FALSE on failure.
286
 *
287
 * The comparison function is changed to @compare and the heap is heapified
288
 * by the new comparison.
289
 */
290
EAPI int
291
ecore_sheap_compare_set(Ecore_Sheap *heap, Ecore_Compare_Cb compare)
292
{
293
   CHECK_PARAM_POINTER_RETURN("heap", heap, FALSE);
294

295
   if (!compare)
296
      heap->compare = ecore_direct_compare;
297
   else
298
      heap->compare = compare;
299

300
   _ecore_sheap_update_data(heap);
301

302
   return TRUE;
303
}
304

305
/**
306
 * Change the order of the heap
307
 * @param  heap  The heap to change the order
308
 * @param  order The new order of the heap
309
 *
310
 * Changes the heap order of @heap and re-heapifies the data to this new
311
 * order. The default order is a min heap.
312
 */
313
EAPI void
314
ecore_sheap_order_set(Ecore_Sheap *heap, char order)
315
{
316
   CHECK_PARAM_POINTER("heap", heap);
317

318
   heap->order = order;
319

320
   _ecore_sheap_update_data(heap);
321
}
322

323
/**
324
 * Sort the data in the heap
325
 * @param  heap The heap to be sorted
326
 *
327
 * Sorts the data in the heap into the order that is used for the heap's
328
 * data.
329
 */
330
EAPI void
331
ecore_sheap_sort(Ecore_Sheap *heap)
332
{
333
   int i = 0;
334
   void **new_data;
335

336
   CHECK_PARAM_POINTER("heap", heap);
337

338
   new_data = (void **)malloc(heap->size * sizeof(void *));
339

340
   /*
341
    * Extract the heap and insert into the new data array in order.
342
    */
343
   while (heap->size > 0)
344
      new_data[i++] = ecore_sheap_extract(heap);
345

346
   /*
347
    * Free the old data array and update the heap with the new data, also
348
    * mark as sorted.
349
    */
350
   FREE(heap->data);
351
   heap->data = new_data;
352
   heap->size = i;
353
   heap->sorted = TRUE;
354
}
355

356
/*
357
 * Access the item at the ith position in the heap
358
 * @param  heap The heap to access the internal data
359
 * @param  i    The index of the data within the heap
360
 * @return The data located at the ith position within @heap on success,
361
 *         NULL on failure.
362
 * @note   The data is guaranteed to be in sorted order.
363
 */
364
EAPI inline void *
365
ecore_sheap_item(Ecore_Sheap *heap, int i)
366
{
367
   if (i >= heap->size)
368
      return NULL;
369

370
   /*
371
    * Make sure the data is sorted so we return the correct value.
372
    */
373
   if (!heap->sorted)
374
      ecore_sheap_sort(heap);
375

376
   return heap->data[i];
377
}
378

379
/*
380
 * Regain the heap properties starting at position i
381
 * @param  heap The heap to regain heap properties
382
 * @param  i    The position to start heapifying
383
 */
384
static void
385
_ecore_sheap_heapify(Ecore_Sheap *heap, int i)
386
{
387
   int extreme;
388
   int left = LEFT(i);
389
   int right = RIGHT(i);
390

391
   if (heap->order == ECORE_SORT_MIN)
392
     {
393
        if (left <= heap->size && heap->compare(heap->data[left - 1],
394
                                                heap->data[i - 1]) < 0)
395
           extreme = left;
396
        else
397
           extreme = i;
398

399
        if (right <= heap->size && heap->compare(heap->data[right - 1],
400
                                                 heap->data[extreme - 1]) < 0)
401
           extreme = right;
402
     }
403
   else
404
     {
405
        if (left <= heap->size && heap->compare(heap->data[left - 1],
406
                                                heap->data[i - 1]) > 0)
407
           extreme = left;
408
        else
409
           extreme = i;
410

411
        if (right <= heap->size && heap->compare(heap->data[right - 1],
412
                                                 heap->data[extreme - 1]) > 0)
413
           extreme = right;
414
     }
415

416
   /*
417
    * If the data needs to be swapped down the heap, recurse on
418
    * heapifying it's new placement.
419
    */
420
   if (extreme != i)
421
     {
422
        void *temp;
423

424
        temp = heap->data[extreme - 1];
425
        heap->data[extreme - 1] = heap->data[i - 1];
426
        heap->data[i - 1] = temp;
427

428
        _ecore_sheap_heapify(heap, extreme);
429
     }
430
}
431

432
static void
433
_ecore_sheap_update_data(Ecore_Sheap *heap)
434
{
435
   int i, old_size;
436
   void **data;
437

438
   /*
439
    * Track the old values from the heap
440
    */
441
   old_size = heap->size;
442
   data = heap->data;
443

444
   heap->size = 0;
445
   heap->data = malloc(heap->space * sizeof(void *));
446

447
   for (i = 0; i < old_size; i++)
448
      ecore_sheap_insert(heap, data[i]);
449

450
   FREE(data);
451
}
452

453
int
454
ecore_direct_compare(const void *key1, const void *key2)
455
{
456
   uintptr_t k1, k2;
457

458
   k1 = (uintptr_t)key1;
459
   k2 = (uintptr_t)key2;
460

461
   if (k1 > k2)
462
      return 1;
463

464
   if (k1 < k2)
465
      return -1;
466

467
   return 0;
468
}
469