Enlightenment CVS committal
Author : pfritz
Project : e17
Module : libs/ecore
Dir : e17/libs/ecore/src/lib/ecore
Modified Files:
Ecore_Data.h ecore_list.c ecore_sheap.c
Log Message:
- add ecore_list_sort() a wrapper for ecore_list_mergesort and
ecore_list_heapsort
- change the API for the sort functions to return an int on success
- change ECORE_SHEAP_MIN/MAX to ECORE_SORT_MIN/MAX (*API break*)
- use ecore_list_sort() in ecore_file_ls()
===================================================================
RCS file: /cvs/e/e17/libs/ecore/src/lib/ecore/Ecore_Data.h,v
retrieving revision 1.30
retrieving revision 1.31
diff -u -3 -r1.30 -r1.31
--- Ecore_Data.h 28 Jan 2007 02:46:13 -0000 1.30
+++ Ecore_Data.h 1 Feb 2007 19:22:35 -0000 1.31
@@ -40,6 +40,9 @@
EAPI extern const unsigned int ecore_prime_table[];
+# define ECORE_SORT_MIN 0
+# define ECORE_SORT_MAX 1
+
typedef void (*Ecore_For_Each) (void *value, void *user_data);
# define ECORE_FOR_EACH(function) ((Ecore_For_Each)function)
@@ -119,9 +122,11 @@
const void *user_data);
/* Sorting the list */
- EAPI void ecore_list_mergesort(Ecore_List *list, Ecore_Compare_Cb compare,
+ EAPI int ecore_list_sort(Ecore_List *list, Ecore_Compare_Cb compare,
+ char order);
+ EAPI int ecore_list_mergesort(Ecore_List *list, Ecore_Compare_Cb compare,
char order);
- EAPI void ecore_list_heapsort(Ecore_List *list, Ecore_Compare_Cb compare,
+ EAPI int ecore_list_heapsort(Ecore_List *list, Ecore_Compare_Cb compare,
char order);
/* Check to see if there is any data in the list */
@@ -326,9 +331,6 @@
EAPI Ecore_List *ecore_plugin_get_available(int group_id);
-
-# define ECORE_SHEAP_MIN 0
-# define ECORE_SHEAP_MAX 1
typedef struct _ecore_heap Ecore_Sheap;
# define ECORE_HEAP(heap) ((Ecore_Sheap *)heap)
===================================================================
RCS file: /cvs/e/e17/libs/ecore/src/lib/ecore/ecore_list.c,v
retrieving revision 1.35
retrieving revision 1.36
diff -u -3 -r1.35 -r1.36
--- ecore_list.c 28 Jan 2007 02:46:13 -0000 1.35
+++ ecore_list.c 1 Feb 2007 19:22:35 -0000 1.36
@@ -2,6 +2,11 @@
#include "Ecore.h"
#include "Ecore_Data.h"
+/* Some tests showed that beyond that value heap sort is faster than merge sort
+ * (in this implementation). This value has to be changed or at least review
+ * if someone is changing the implementation. */
+#define ECORE_MERGESORT_LIMIT 40000
+
/* Return information about the list */
static void *_ecore_list_current(Ecore_List * list);
@@ -1121,24 +1126,51 @@
}
/**
- * Sort data in @p list using the compare function @p func
+ * Sort data in @p list using the compare function @p compare
* @param list The list.
* @param compare The function to compare the data of @p list
* @param order The sort direction
*
+ * @return true on success
+ *
+ * This is a wrapper function for mergesort and heapsort. It
+ * tries to choose the fastest algorithm depending on the
+ * number of notes. Note: The sort may be unstable.
+ */
+EAPI int
+ecore_list_sort(Ecore_List *list, Ecore_Compare_Cb compare, char order)
+{
+ CHECK_PARAM_POINTER_RETURN("list", list, 0);
+
+ if (list->nodes < 2)
+ return 1;
+ if (list->nodes < ECORE_MERGESORT_LIMIT)
+ return ecore_list_mergesort(list, compare, order);
+ if (!ecore_list_heapsort(list, compare, order))
+ return ecore_list_mergesort(list, compare, order);
+
+ return 1;
+}
+/**
+ * Sort data in @p list using the compare function @p compare
+ * @param list The list.
+ * @param compare The function to compare the data of @p list
+ * @param order The sort direction
+ *
+ * @return true on success
+ *
* Mergesort is a stable, in-place sorting algorithm
*/
-EAPI void
+EAPI int
ecore_list_mergesort(Ecore_List *list, Ecore_Compare_Cb compare, char order)
{
Ecore_List_Node *node;
- CHECK_PARAM_POINTER("list", list);
- if (!list || list->nodes < 2)
- {
- return;
- }
- if (order == ECORE_SHEAP_MIN)
+ CHECK_PARAM_POINTER_RETURN("list", list, 0);
+ if (list->nodes < 2)
+ return 1;
+
+ if (order == ECORE_SORT_MIN)
order = 1;
else
order = -1;
@@ -1152,6 +1184,8 @@
list->last = node;
_ecore_list_goto_first(list);
+
+ return 1;
}
/* this is the internal recrusive function for the merge sort */
@@ -1170,7 +1204,7 @@
return first;
else if (n == 2)
{
- if (compare(first->data, first->next->data) == order)
+ if (compare(first->data, first->next->data) * order > 0)
{
/* swap the data */
void *data;
@@ -1206,7 +1240,7 @@
/* select the first node outside the loop, because we need to keep
* a pointer to it */
- if (compare(first->data, second->data) == order)
+ if (compare(first->data, second->data) * order > 0)
{
list = l = second;
second = second->next;
@@ -1220,7 +1254,7 @@
/* and now start the merging */
while (first && second)
{
- if (compare(first->data, second->data) == order)
+ if (compare(first->data, second->data) * order > 0)
{
l = l->next = second;
second = second->next;
@@ -1244,26 +1278,31 @@
}
/**
- * Sort data in @p list using the compare function @p func
+ * Sort data in @p list using the compare function @p compare
* @param list The list.
* @param compare The function to compare the data of @p list
* @param order The sort direction
*
+ * @return true on success
+ *
* Heapsort is a unstable sorting algorithm, it needs to allocate extra
memomry,
* but there for it is for a great number of nodes faster than mergesort
*/
-EAPI void
+EAPI int
ecore_list_heapsort(Ecore_List *list, Ecore_Compare_Cb compare, char order)
{
Ecore_Sheap *heap;
Ecore_List_Node *node;
void *data;
- CHECK_PARAM_POINTER("list", list);
+ CHECK_PARAM_POINTER_RETURN("list", list, 0);
/*
* Push the data into a heap.
*/
heap = ecore_sheap_new(compare, list->nodes);
+ if (!heap)
+ return 0;
+
ecore_sheap_set_order(heap, order);
_ecore_list_goto_first(list);
while ((data = _ecore_list_next(list)))
@@ -1284,6 +1323,7 @@
ecore_sheap_destroy(heap);
_ecore_list_goto_first(list);
+ return 1;
}
/* Initialize a node to starting values */
===================================================================
RCS file: /cvs/e/e17/libs/ecore/src/lib/ecore/ecore_sheap.c,v
retrieving revision 1.11
retrieving revision 1.12
diff -u -3 -r1.11 -r1.12
--- ecore_sheap.c 23 Jun 2006 06:41:44 -0000 1.11
+++ ecore_sheap.c 1 Feb 2007 19:22:35 -0000 1.12
@@ -54,7 +54,7 @@
heap->compare = ecore_direct_compare;
else
heap->compare = compare;
- heap->order = ECORE_SHEAP_MIN;
+ heap->order = ECORE_SORT_MIN;
heap->data = (void **)malloc(heap->space * sizeof(void *));
if (!heap->data)
@@ -149,7 +149,7 @@
* data. The loop is placed inside the if statement to reduce the
* number of branching decisions that must be predicted.
*/
- if (heap->order == ECORE_SHEAP_MIN)
+ if (heap->order == ECORE_SORT_MIN)
{
while ((position > 0) && heap->compare(heap->data[parent],
heap->data[position]) > 0)
@@ -383,7 +383,7 @@
int left = LEFT(i);
int right = RIGHT(i);
- if (heap->order == ECORE_SHEAP_MIN)
+ if (heap->order == ECORE_SORT_MIN)
{
if (left <= heap->size && heap->compare(heap->data[left - 1],
heap->data[i - 1]) < 0)
-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier.
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
enlightenment-cvs mailing list
enlightenment-cvs@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/enlightenment-cvs
