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
enlightenment-cvs@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/enlightenment-cvs

Reply via email to