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