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 @@
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "Ecore_Data.h"
+
+#define HEAP_INCREMENT 4096
+
+#define PARENT(i) (i / 2)
+#define LEFT(i) (2 * i)
+#define RIGHT(i) (2 * i + 1)
+
+static void _ecore_sheap_heapify(Ecore_Sheap *heap, int i);
+static void _ecore_sheap_update_data(Ecore_Sheap *heap);
+
+/**
+ * Allocate and initialize a new binary heap
+ * @param compare The function for comparing keys, NULL for direct comparison
+ * @param size    The number of elements to allow in the heap
+ * @return A pointer to the newly allocated binary heap on success, NULL on
+ * failure.
+ */
+EAPI Ecore_Sheap *
+ecore_sheap_new(Ecore_Compare_Cb compare, int size)
+{
+   Ecore_Sheap *heap = NULL;
+
+   heap = (Ecore_Sheap *)malloc(sizeof(Ecore_Sheap));
+   if (!heap)
+      return NULL;
+
+   memset(heap, 0, sizeof(Ecore_Sheap));
+
+   if (!ecore_sheap_init(heap, compare, size))
+     {
+        FREE(heap);
+        return NULL;
+     }
+
+   return heap;
+}
+
+/**
+ * Initialize a binary heap to default values
+ * @param heap    The heap to initialize
+ * @param compare The function for comparing keys, NULL for direct comparison
+ * @param size    The number of elements to allow in the heap
+ * @return        TRUE on success, FALSE on failure
+ */
+EAPI int
+ecore_sheap_init(Ecore_Sheap *heap, Ecore_Compare_Cb compare, int size)
+{
+   CHECK_PARAM_POINTER_RETURN("heap", heap, FALSE);
+
+   heap->space = size;
+   if (!compare)
+      heap->compare = ecore_direct_compare;
+   else
+      heap->compare = compare;
+
+   heap->order = ECORE_SORT_MIN;
+
+   heap->data = (void **)malloc(heap->space * sizeof(void *));
+   if (!heap->data)
+      return FALSE;
+
+   memset(heap->data, 0, heap->space * sizeof(void *));
+
+   return TRUE;
+}
+
+/**
+ * Free up the memory used by the heap
+ *
+ * Frees the memory used by @a heap, calls the destroy function on each data
+ * item if necessary.
+ *
+ * @param  heap The heap to be freed
+ */
+EAPI void
+ecore_sheap_destroy(Ecore_Sheap *heap)
+{
+   int i;
+
+   CHECK_PARAM_POINTER("heap", heap);
+
+   /*
+    * Free data in heap
+    */
+   if (heap->free_func)
+      for (i = 0; i < heap->size; i++)
+         heap->free_func(heap->data[i]);
+
+   FREE(heap->data);
+
+   FREE(heap);
+}
+
+/**
+ * Set the function for freeing data.
+ * @param  heap      The heap that will use this function when nodes are
+ *                   destroyed.
+ * @param  free_func The function that will free the key data.
+ * @return @c TRUE on successful set, @c FALSE otherwise.
+ */
+EAPI int
+ecore_sheap_free_cb_set(Ecore_Sheap *heap, Ecore_Free_Cb free_func)
+{
+   CHECK_PARAM_POINTER_RETURN("heap", heap, FALSE);
+
+   heap->free_func = free_func;
+
+   return TRUE;
+}
+
+/**
+ * Insert new data into the heap.
+ * @param  heap The heap to insert @a data.
+ * @param  data The data to add to @a heap.
+ * @return TRUE on success, NULL on failure. Increases the size of the heap if
+ *         it becomes larger than available space.
+ */
+EAPI int
+ecore_sheap_insert(Ecore_Sheap *heap, void *data)
+{
+   int i;
+   void *temp;
+   int parent;
+   int position;
+
+   CHECK_PARAM_POINTER_RETURN("heap", heap, FALSE);
+
+   /*
+    * Increase the size of the allocated data area if there isn't enough
+    * space available to add this data
+    */
+   if (heap->size >= heap->space)
+      return FALSE;
+
+   heap->sorted = FALSE;
+
+   /*
+    * Place the data at the end of the heap initially. Then determine the
+    * parent and position in the array of it's parent.
+    */
+   heap->data[heap->size] = data;
+   position = heap->size;
+   heap->size++;
+   i = heap->size;
+   parent = PARENT(i) - 1;
+
+   /*
+    * Check the order of the heap to decide where to place the inserted
+    * data. The loop is placed inside the if statement to reduce the
+    * number of branching decisions that must be predicted.
+    */
+   if (heap->order == ECORE_SORT_MIN)
+      while ((position > 0) && heap->compare(heap->data[parent],
+                                             heap->data[position]) > 0)
+        {
+
+           /*
+            * Swap the data with it's parents to move it up in
+            * the heap.
+            */
+           temp = heap->data[position];
+           heap->data[position] = heap->data[parent];
+           heap->data[parent] = temp;
+
+           /*
+            * Now determine the new position for the next
+            * iteration of the loop, as well as it's parents
+            * position.
+            */
+           i = PARENT(i);
+           position = i - 1;
+           parent = PARENT(i) - 1;
+        }
+   else
+      while ((position > 0) && heap->compare(heap->data[parent],
+                                             heap->data[position]) < 0)
+        {
+
+           /*
+            * Swap the data with it's parents to move it up in
+            * the heap.
+            */
+           temp = heap->data[position];
+           heap->data[position] = heap->data[PARENT(i) - 1];
+           heap->data[PARENT(i) - 1] = temp;
+
+           /*
+            * Now determine the new position for the next
+            * iteration of the loop, as well as it's parents
+            * position.
+            */
+           i = PARENT(i);
+           position = i - 1;
+           parent = PARENT(i) - 1;
+        }
+
+   return TRUE;
+}
+
+/**
+ * Extract the item at the top of the heap
+ * @param  heap The heap to remove the top item
+ * @return The top item of the heap on success, NULL on failure.
+ * @note   The extract function maintains the heap properties after the
+ *         extract.
+ */
+EAPI void *
+ecore_sheap_extract(Ecore_Sheap *heap)
+{
+   void *extreme;
+
+   if (heap->size < 1)
+      return NULL;
+
+   heap->sorted = FALSE;
+
+   extreme = heap->data[0];
+   heap->size--;
+   heap->data[0] = heap->data[heap->size];
+
+   _ecore_sheap_heapify(heap, 1);
+
+   return extreme;
+}
+
+/**
+ * Examine the item at the top of the heap
+ * @param  heap The heap to examine the top item
+ * @return The top item of the heap on success, NULL on failure.
+ * @note   The function does not alter the heap.
+ */
+EAPI void *
+ecore_sheap_extreme(Ecore_Sheap *heap)
+{
+   if (heap->size < 1)
+      return NULL;
+
+   return heap->data[0];
+}
+
+/**
+ * Change the value of the specified item in the heap
+ * @param heap   The heap to search for the item to change
+ * @param item   The item in the heap to change
+ * @param newval The new value assigned to the item in the heap
+ * @return       TRUE on success, FALSE on failure.
+ * @note         The heap does not free the old data since it must be passed
+ *               in, so the caller can perform the free if desired.
+ */
+EAPI int
+ecore_sheap_change(Ecore_Sheap *heap, void *item, void *newval)
+{
+   int i;
+
+   CHECK_PARAM_POINTER_RETURN("heap", heap, FALSE);
+
+   for (i = 0; i < heap->size && heap->compare(heap->data[i], item); i++) ;
+
+   if (i < heap->size)
+      heap->data[i] = newval;
+   else
+      return FALSE;
+
+   /*
+    * FIXME: This is not the correct procedure when a change occurs.
+    */
+   _ecore_sheap_heapify(heap, 1);
+
+   return TRUE;
+}
+
+/**
+ * Change the comparison function for the heap
+ * @param  heap    The heap to change comparison function
+ * @param  compare The new function for comparing nodes
+ * @return TRUE on success, FALSE on failure.
+ *
+ * The comparison function is changed to @compare and the heap is heapified
+ * by the new comparison.
+ */
+EAPI int
+ecore_sheap_compare_set(Ecore_Sheap *heap, Ecore_Compare_Cb compare)
+{
+   CHECK_PARAM_POINTER_RETURN("heap", heap, FALSE);
+
+   if (!compare)
+      heap->compare = ecore_direct_compare;
+   else
+      heap->compare = compare;
+
+   _ecore_sheap_update_data(heap);
+
+   return TRUE;
+}
+
+/**
+ * Change the order of the heap
+ * @param  heap  The heap to change the order
+ * @param  order The new order of the heap
+ *
+ * Changes the heap order of @heap and re-heapifies the data to this new
+ * order. The default order is a min heap.
+ */
+EAPI void
+ecore_sheap_order_set(Ecore_Sheap *heap, char order)
+{
+   CHECK_PARAM_POINTER("heap", heap);
+
+   heap->order = order;
+
+   _ecore_sheap_update_data(heap);
+}
+
+/**
+ * Sort the data in the heap
+ * @param  heap The heap to be sorted
+ *
+ * Sorts the data in the heap into the order that is used for the heap's
+ * data.
+ */
+EAPI void
+ecore_sheap_sort(Ecore_Sheap *heap)
+{
+   int i = 0;
+   void **new_data;
+
+   CHECK_PARAM_POINTER("heap", heap);
+
+   new_data = (void **)malloc(heap->size * sizeof(void *));
+
+   /*
+    * Extract the heap and insert into the new data array in order.
+    */
+   while (heap->size > 0)
+      new_data[i++] = ecore_sheap_extract(heap);
+
+   /*
+    * Free the old data array and update the heap with the new data, also
+    * mark as sorted.
+    */
+   FREE(heap->data);
+   heap->data = new_data;
+   heap->size = i;
+   heap->sorted = TRUE;
+}
+
+/*
+ * Access the item at the ith position in the heap
+ * @param  heap The heap to access the internal data
+ * @param  i    The index of the data within the heap
+ * @return The data located at the ith position within @heap on success,
+ *         NULL on failure.
+ * @note   The data is guaranteed to be in sorted order.
+ */
+EAPI inline void *
+ecore_sheap_item(Ecore_Sheap *heap, int i)
+{
+   if (i >= heap->size)
+      return NULL;
+
+   /*
+    * Make sure the data is sorted so we return the correct value.
+    */
+   if (!heap->sorted)
+      ecore_sheap_sort(heap);
+
+   return heap->data[i];
+}
+
+/*
+ * Regain the heap properties starting at position i
+ * @param  heap The heap to regain heap properties
+ * @param  i    The position to start heapifying
+ */
+static void
+_ecore_sheap_heapify(Ecore_Sheap *heap, int i)
+{
+   int extreme;
+   int left = LEFT(i);
+   int right = RIGHT(i);
+
+   if (heap->order == ECORE_SORT_MIN)
+     {
+        if (left <= heap->size && heap->compare(heap->data[left - 1],
+                                                heap->data[i - 1]) < 0)
+           extreme = left;
+        else
+           extreme = i;
+
+        if (right <= heap->size && heap->compare(heap->data[right - 1],
+                                                 heap->data[extreme - 1]) < 0)
+           extreme = right;
+     }
+   else
+     {
+        if (left <= heap->size && heap->compare(heap->data[left - 1],
+                                                heap->data[i - 1]) > 0)
+           extreme = left;
+        else
+           extreme = i;
+
+        if (right <= heap->size && heap->compare(heap->data[right - 1],
+                                                 heap->data[extreme - 1]) > 0)
+           extreme = right;
+     }
+
+   /*
+    * If the data needs to be swapped down the heap, recurse on
+    * heapifying it's new placement.
+    */
+   if (extreme != i)
+     {
+        void *temp;
+
+        temp = heap->data[extreme - 1];
+        heap->data[extreme - 1] = heap->data[i - 1];
+        heap->data[i - 1] = temp;
+
+        _ecore_sheap_heapify(heap, extreme);
+     }
+}
+
+static void
+_ecore_sheap_update_data(Ecore_Sheap *heap)
+{
+   int i, old_size;
+   void **data;
+
+   /*
+    * Track the old values from the heap
+    */
+   old_size = heap->size;
+   data = heap->data;
+
+   heap->size = 0;
+   heap->data = malloc(heap->space * sizeof(void *));
+
+   for (i = 0; i < old_size; i++)
+      ecore_sheap_insert(heap, data[i]);
+
+   FREE(data);
+}
+
+int
+ecore_direct_compare(const void *key1, const void *key2)
+{
+   unsigned long k1, k2;
+
+   k1 = (unsigned long)key1;
+   k2 = (unsigned long)key2;
+
+   if (k1 > k2)
+      return 1;
+
+   if (k1 < k2)
+      return -1;
+
+   return 0;
+}