Enlightenment CVS committal
Author : rbdpngn
Project : e17
Module : libs/ecore
Dir : e17/libs/ecore/src/lib/ecore_file
Modified Files:
ecore_file.c
Log Message:
Move ecore_file_ls from an O(n^2) insertion sort to an O(n log n) heap sort,
since we already have it available. Worked fine on OS X and had dj2 check on
Linux to ensure filesystem ordering wasn't skewing the results. He ran a
couple quick benchmarks on a 10k file directory.
Insertion sort results
23:38 <@dj2> real 0m2.134s
23:38 <@dj2> user 0m1.880s
23:38 <@dj2> sys 0m0.120s
Heap sort results
23:35 <@dj2> real 0m0.223s
23:35 <@dj2> user 0m0.072s
23:35 <@dj2> sys 0m0.052s
23:38 <@dj2> and thats on a 3ghz box, heh
===================================================================
RCS file:
/cvsroot/enlightenment/e17/libs/ecore/src/lib/ecore_file/ecore_file.c,v
retrieving revision 1.38
retrieving revision 1.39
diff -u -3 -r1.38 -r1.39
--- ecore_file.c 31 Oct 2005 09:14:41 -0000 1.38
+++ ecore_file.c 10 Nov 2005 05:44:41 -0000 1.39
@@ -261,9 +261,11 @@
Ecore_List *
ecore_file_ls(const char *dir)
{
+ char *f;
DIR *dirp;
struct dirent *dp;
- Ecore_List *list;
+ Ecore_List *list;
+ Ecore_Sheap *heap;
dirp = opendir(dir);
if (!dirp) return NULL;
@@ -275,30 +277,29 @@
{
if ((strcmp(dp->d_name, ".")) && (strcmp(dp->d_name, "..")))
{
- char *file, *f;
-
- /* insertion sort */
- ecore_list_goto_first(list);
- while ((file = ecore_list_current(list)))
- {
- if (strcasecmp(file, dp->d_name) > 0)
- {
- f = strdup(dp->d_name);
- ecore_list_insert(list, f);
- break;
- }
- ecore_list_next(list);
- }
- /* nowhwre to go? just append it */
- if (!file)
- {
- f = strdup(dp->d_name);
- ecore_list_insert(list, f);
- }
+ f = strdup(dp->d_name);
+ ecore_list_append(list, f);
}
}
closedir(dirp);
+ /*
+ * Push the data into a heap.
+ */
+ heap = ecore_sheap_new(ECORE_COMPARE_CB(strcasecmp),
ecore_list_nodes(list));
+ while ((f = ecore_list_remove_first(list)))
+ {
+ ecore_sheap_insert(heap, f);
+ }
+
+ /*
+ * Extract in sorted order.
+ */
+ while ((f = ecore_sheap_extract(heap)))
+ {
+ ecore_list_append(list, f);
+ }
+
ecore_list_goto_first(list);
return list;
}
-------------------------------------------------------
SF.Net email is sponsored by:
Tame your development challenges with Apache's Geronimo App Server. Download
it for free - -and be entered to win a 42" plasma tv or your very own
Sony(tm)PSP. Click here to play: http://sourceforge.net/geronimo.php
_______________________________________________
enlightenment-cvs mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/enlightenment-cvs