From bff3b37695781143ae115f609ae69603ddd73a7e Mon Sep 17 00:00:00 2001 From: havoc Date: Thu, 15 Mar 2007 13:54:37 +0000 Subject: [PATCH] rewrote stringlist stuff, now uses a (dynamically resizing) array of pointers rather than a linked list, and uses a selection sort rather than a bubble sort, this has changed the "maps" command from taking about 7 seconds on my system to about 70ms git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@6983 d7cf8633-e32d-0410-b094-e92efae38249 --- common.h | 16 ++++--- filematch.c | 125 ++++++++++++++++++++++------------------------------ fs.c | 103 +++++++++++++++++++++---------------------- 3 files changed, 111 insertions(+), 133 deletions(-) diff --git a/common.h b/common.h index 816a8fa9..b1a7b90b 100644 --- a/common.h +++ b/common.h @@ -289,16 +289,18 @@ int COM_ReadAndTokenizeLine(const char **text, char **argv, int maxargc, char *t typedef struct stringlist_s { - struct stringlist_s *next; - char *text; + // maxstrings changes as needed, causing reallocation of strings[] array + int maxstrings; + int numstrings; + char **strings; } stringlist_t; int matchpattern(const char *in, const char *pattern, int caseinsensitive); -stringlist_t *stringlistappend(stringlist_t *current, char *text); -void stringlistfree(stringlist_t *current); -stringlist_t *stringlistsort(stringlist_t *start); -stringlist_t *listdirectory(const char *path); -void freedirectory(stringlist_t *list); +void stringlistinit(stringlist_t *list); +void stringlistfreecontents(stringlist_t *list); +void stringlistappend(stringlist_t *list, char *text); +void stringlistsort(stringlist_t *list); +void listdirectory(stringlist_t *list, const char *path); char *SearchInfostring(const char *infostring, const char *key); diff --git a/filematch.c b/filematch.c index 0837136f..99737875 100644 --- a/filematch.c +++ b/filematch.c @@ -57,79 +57,76 @@ int matchpattern(const char *in, const char *pattern, int caseinsensitive) return 1; // success } -// a little chained strings system -stringlist_t *stringlistappend(stringlist_t *current, char *text) +// a little strings system +void stringlistinit(stringlist_t *list) { - stringlist_t *newitem; - size_t textlen; + memset(list, 0, sizeof(*list)); +} - textlen = strlen(text) + 1; - newitem = (stringlist_t *)Z_Malloc(textlen + sizeof(stringlist_t)); - newitem->next = NULL; - newitem->text = (char *)(newitem + 1); - memcpy(newitem->text, text, textlen); - if (current) - current->next = newitem; - return newitem; +void stringlistfreecontents(stringlist_t *list) +{ + int i; + for (i = 0;i < list->numstrings;i++) + { + if (list->strings[i]) + Z_Free(list->strings[i]); + list->strings[i] = NULL; + } + list->numstrings = 0; + list->maxstrings = 0; + if (list->strings) + Z_Free(list->strings); } -void stringlistfree(stringlist_t *current) +void stringlistappend(stringlist_t *list, char *text) { - stringlist_t *next; - while (current) + size_t textlen; + char **oldstrings; + + if (list->numstrings >= list->maxstrings) { - next = current->next; - Z_Free(current); - current = next; + oldstrings = list->strings; + list->maxstrings += 4096; + list->strings = Z_Malloc(list->maxstrings * sizeof(*list->strings)); + if (list->numstrings) + memcpy(list->strings, oldstrings, list->numstrings * sizeof(*list->strings)); + if (oldstrings) + Z_Free(oldstrings); } + textlen = strlen(text) + 1; + list->strings[list->numstrings] = Z_Malloc(textlen); + memcpy(list->strings[list->numstrings], text, textlen); + list->numstrings++; } -stringlist_t *stringlistsort(stringlist_t *start) +void stringlistsort(stringlist_t *list) { - int notdone; - stringlist_t *current, *previous, *temp2, *temp3, *temp4; - // exit early if there's nothing to sort - if (start == NULL || start->next == NULL) - return start; - notdone = 1; - while (notdone) + int i, j; + char *temp; + // this is a selection sort (finds the best entry for each slot) + for (i = 0;i < list->numstrings - 1;i++) { - current = start; - notdone = 0; - previous = NULL; - while (current && current->next) + for (j = i + 1;j < list->numstrings;j++) { - if (strcmp(current->text, current->next->text) > 0) + if (strcmp(list->strings[i], list->strings[j]) > 0) { - // current is greater than next - notdone = 1; - temp2 = current->next; - temp3 = current; - temp4 = current->next->next; - if (previous) - previous->next = temp2; - else - start = temp2; - temp2->next = temp3; - temp3->next = temp4; - break; + temp = list->strings[i]; + list->strings[i] = list->strings[j]; + list->strings[j] = temp; } - previous = current; - current = current->next; } } - return start; } // operating system specific code #ifdef WIN32 #include -stringlist_t *listdirectory(const char *path) +void listdirectory(stringlist_t *list, const char *path) { + int i; char pattern[4096], *c; struct _finddata_t n_file; long hFile; - stringlist_t *start, *current; strlcpy (pattern, path, sizeof (pattern)); strlcat (pattern, "*", sizeof (pattern)); // ask for the directory listing handle @@ -137,49 +134,31 @@ stringlist_t *listdirectory(const char *path) if(hFile == -1) return NULL; // start a new chain with the the first name - start = current = stringlistappend(NULL, n_file.name); + stringlistappend(list, n_file.name); // iterate through the directory while (_findnext(hFile, &n_file) == 0) - current = stringlistappend(current, n_file.name); + stringlistappend(list, n_file.name); _findclose(hFile); // convert names to lowercase because windows does not care, but pattern matching code often does - for (current = start;current;current = current->next) - for (c = current->text;*c;c++) + for (i = 0;i < list->numstrings;i++) + for (c = list->strings[i];*c;c++) if (*c >= 'A' && *c <= 'Z') *c += 'a' - 'A'; - - // sort the list alphanumerically - return stringlistsort(start); } #else #include -stringlist_t *listdirectory(const char *path) +void listdirectory(stringlist_t *list, const char *path) { DIR *dir; struct dirent *ent; - stringlist_t *start, *current; dir = opendir(path); if (!dir) - return NULL; - start = current = NULL; + return; while ((ent = readdir(dir))) - { if (strcmp(ent->d_name, ".") && strcmp(ent->d_name, "..")) - { - current = stringlistappend(current, ent->d_name); - if (!start) - start = current; - } - } + stringlistappend(list, ent->d_name); closedir(dir); - // sort the list alphanumerically - return stringlistsort(start); } #endif -void freedirectory(stringlist_t *list) -{ - stringlistfree(list); -} - diff --git a/fs.c b/fs.c index 556384c0..0c6901b3 100644 --- a/fs.c +++ b/fs.c @@ -961,35 +961,38 @@ then loads and adds pak1.pak pak2.pak ... */ void FS_AddGameDirectory (const char *dir) { - stringlist_t *list, *current; + int i; + stringlist_t list; searchpath_t *search; char pakfile[MAX_OSPATH]; strlcpy (fs_gamedir, dir, sizeof (fs_gamedir)); - list = listdirectory(dir); + stringlistinit(&list); + listdirectory(&list, dir); + stringlistsort(&list); // add any PAK package in the directory - for (current = list;current;current = current->next) + for (i = 0;i < list.numstrings;i++) { - if (!strcasecmp(FS_FileExtension(current->text), "pak")) + if (!strcasecmp(FS_FileExtension(list.strings[i]), "pak")) { - dpsnprintf (pakfile, sizeof (pakfile), "%s%s", dir, current->text); + dpsnprintf (pakfile, sizeof (pakfile), "%s%s", dir, list.strings[i]); FS_AddPack_Fullpath(pakfile, NULL, false); } } // add any PK3 package in the directory - for (current = list;current;current = current->next) + for (i = 0;i < list.numstrings;i++) { - if (!strcasecmp(FS_FileExtension(current->text), "pk3")) + if (!strcasecmp(FS_FileExtension(list.strings[i]), "pk3")) { - dpsnprintf (pakfile, sizeof (pakfile), "%s%s", dir, current->text); + dpsnprintf (pakfile, sizeof (pakfile), "%s%s", dir, list.strings[i]); FS_AddPack_Fullpath(pakfile, NULL, false); } } - freedirectory(list); + stringlistfreecontents(&list); // Add the directory to the search path // (unpacked files have the priority over packed files) @@ -1281,10 +1284,13 @@ FS_CheckGameDir */ qboolean FS_CheckGameDir(const char *gamedir) { - stringlist_t *list = listdirectory(va("%s%s/", fs_basedir, gamedir)); - if (list) - freedirectory(list); - return list != NULL; + qboolean success; + stringlist_t list; + stringlistinit(&list); + listdirectory(&list, va("%s%s/", fs_basedir, gamedir)); + success = list.numstrings > 0; + stringlistfreecontents(&list); + return success; } @@ -2423,8 +2429,9 @@ fssearch_t *FS_Search(const char *pattern, int caseinsensitive, int quiet) fssearch_t *search; searchpath_t *searchpath; pack_t *pak; - int i, basepathlength, numfiles, numchars; - stringlist_t *dir, *dirfile, *liststart, *listcurrent, *listtemp; + int i, basepathlength, numfiles, numchars, resultlistindex, dirlistindex; + stringlist_t resultlist; + stringlist_t dirlist; const char *slash, *backslash, *colon, *separator; char *basepath; char netpath[MAX_OSPATH]; @@ -2439,10 +2446,9 @@ fssearch_t *FS_Search(const char *pattern, int caseinsensitive, int quiet) return NULL; } + stringlistinit(&resultlist); + stringlistinit(&dirlist); search = NULL; - liststart = NULL; - listcurrent = NULL; - listtemp = NULL; slash = strrchr(pattern, '/'); backslash = strrchr(pattern, '\\'); colon = strrchr(pattern, ':'); @@ -2469,14 +2475,12 @@ fssearch_t *FS_Search(const char *pattern, int caseinsensitive, int quiet) { if (matchpattern(temp, (char *)pattern, true)) { - for (listtemp = liststart;listtemp;listtemp = listtemp->next) - if (!strcmp(listtemp->text, temp)) + for (resultlistindex = 0;resultlistindex < resultlist.numstrings;resultlistindex++) + if (!strcmp(resultlist.strings[resultlistindex], temp)) break; - if (listtemp == NULL) + if (resultlistindex == resultlist.numstrings) { - listcurrent = stringlistappend(listcurrent, temp); - if (liststart == NULL) - liststart = listcurrent; + stringlistappend(&resultlist, temp); if (!quiet) Con_DPrintf("SearchPackFile: %s : %s\n", pak->filename, temp); } @@ -2501,59 +2505,52 @@ fssearch_t *FS_Search(const char *pattern, int caseinsensitive, int quiet) { // get a directory listing and look at each name dpsnprintf(netpath, sizeof (netpath), "%s%s", searchpath->filename, basepath); - if ((dir = listdirectory(netpath))) + stringlistinit(&dirlist); + listdirectory(&dirlist, netpath); + for (dirlistindex = 0;dirlistindex < dirlist.numstrings;dirlistindex++) { - for (dirfile = dir;dirfile;dirfile = dirfile->next) + dpsnprintf(temp, sizeof(temp), "%s%s", basepath, dirlist.strings[dirlistindex]); + if (matchpattern(temp, (char *)pattern, true)) { - dpsnprintf(temp, sizeof(temp), "%s%s", basepath, dirfile->text); - if (matchpattern(temp, (char *)pattern, true)) + for (resultlistindex = 0;resultlistindex < resultlist.numstrings;resultlistindex++) + if (!strcmp(resultlist.strings[resultlistindex], temp)) + break; + if (resultlistindex == resultlist.numstrings) { - for (listtemp = liststart;listtemp;listtemp = listtemp->next) - if (!strcmp(listtemp->text, temp)) - break; - if (listtemp == NULL) - { - listcurrent = stringlistappend(listcurrent, temp); - if (liststart == NULL) - liststart = listcurrent; - if (!quiet) - Con_DPrintf("SearchDirFile: %s\n", temp); - } + stringlistappend(&resultlist, temp); + if (!quiet) + Con_DPrintf("SearchDirFile: %s\n", temp); } } - freedirectory(dir); } + stringlistfreecontents(&dirlist); } } - if (liststart) + if (resultlist.numstrings) { - liststart = stringlistsort(liststart); - numfiles = 0; + stringlistsort(&resultlist); + numfiles = resultlist.numstrings; numchars = 0; - for (listtemp = liststart;listtemp;listtemp = listtemp->next) - { - numfiles++; - numchars += (int)strlen(listtemp->text) + 1; - } + for (resultlistindex = 0;resultlistindex < resultlist.numstrings;resultlistindex++) + numchars += (int)strlen(resultlist.strings[resultlistindex]) + 1; search = (fssearch_t *)Z_Malloc(sizeof(fssearch_t) + numchars + numfiles * sizeof(char *)); search->filenames = (char **)((char *)search + sizeof(fssearch_t)); search->filenamesbuffer = (char *)((char *)search + sizeof(fssearch_t) + numfiles * sizeof(char *)); search->numfilenames = (int)numfiles; numfiles = 0; numchars = 0; - for (listtemp = liststart;listtemp;listtemp = listtemp->next) + for (resultlistindex = 0;resultlistindex < resultlist.numstrings;resultlistindex++) { size_t textlen; search->filenames[numfiles] = search->filenamesbuffer + numchars; - textlen = strlen(listtemp->text) + 1; - memcpy(search->filenames[numfiles], listtemp->text, textlen); + textlen = strlen(resultlist.strings[resultlistindex]) + 1; + memcpy(search->filenames[numfiles], resultlist.strings[resultlistindex], textlen); numfiles++; numchars += (int)textlen; } - if (liststart) - stringlistfree(liststart); } + stringlistfreecontents(&resultlist); Mem_Free(basepath); return search; -- 2.39.2