From 2843a1979f55368c42dcf097e4f7745babb0faee Mon Sep 17 00:00:00 2001
From: "Ryan C. Gordon" <icculus@icculus.org>
Date: Fri, 6 Jul 2001 21:29:37 +0000
Subject: [PATCH] Redesign of enumerateFiles code. More efficient and clean,
 less memory hungry. Some tiny snafus, though, for future maintanence
 (*shrug*).

---
 physfs.c          | 132 +++++++++++++++++++++++++++++++++++-----------
 physfs_internal.h |  15 ++++--
 2 files changed, 112 insertions(+), 35 deletions(-)

diff --git a/physfs.c b/physfs.c
index 5c8976f3..49cf1404 100644
--- a/physfs.c
+++ b/physfs.c
@@ -708,41 +708,109 @@ const char *PHYSFS_getRealDir(const char *filename)
 } /* PHYSFS_getRealDir */
 
 
+static void countList(LinkedStringList *list)
+{
+    int retval = 0;
+    LinkedStringList *i;
+
+    assert(list != NULL);
+
+    for (i = list; i != NULL; i = i->next)
+        retval++;
+
+    return(retval);
+} /* countList */
+
+
+static char **convertStringListToPhysFSList(LinkedStringList *finalList)
+{
+    int i;
+    LinkedStringList *next = NULL;
+    int len = countList(finalList);
+    char **retval = (char **) malloc((len + 1) * sizeof (char *));
+
+    if (retval == NULL)
+        __PHYSFS_setError(ERR_OUT_OF_MEMORY);
+
+    for (i = 0; i < len; i++)
+    {
+        next = finalList->next;
+        if (retval == NULL)
+            free(finalList->str);
+        else
+            retval[i] = finalList->str;
+        free(finalList);
+        finalList = next;
+    } /* for */
+
+    if (retval != NULL);
+        retval[i] = NULL;
+
+    return(retval);
+} /* convertStringListToPhysFSList */
+
+
+static void insertStringListItem(LinkedStringList **final,
+                                 LinkedStringList *item)
+{
+    LinkedStringList *i;
+    LinkedStringList *prev = NULL;
+    int rc;
+
+    for (i = *final; i != NULL; i = i->next)
+    {
+        rc = strcmp(i->str, item->str);
+        if (rc == 0)      /* already in list. */
+        {
+            free(item->str);
+            free(item);
+            return;
+        } /* if */
+        else if (rc > 0)  /* insertion point. */
+        {
+            if (prev == NULL)
+                *final = item;
+            else
+                prev->next = item;
+            item->next = i;
+            return;
+        } /* else if */
+        prev = i;
+    } /* for */
+} /* insertStringListItem */
+
+
+/* if we run out of memory anywhere in here, we give back what we can. */
+static void interpolateStringLists(LinkedStringList **final,
+                                    LinkedStringList *newList)
+{
+    LinkedStringList *next = NULL;
+
+    while (newList != NULL)
+    {
+        next = newList->next;
+        insertStringListItem(final, newList);
+        newList = next;
+    } /* while */
+} /* interpolateStringLists */
+
 
-/**
- * Get a file listing of a search path's directory. Matching directories are
- *  interpolated. That is, if "C:\mypath" is in the search path and contains a
- *  directory "savegames" that contains "x.sav", "y.sav", and "z.sav", and
- *  there is also a "C:\userpath" in the search path that has a "savegames"
- *  subdirectory with "w.sav", then the following code:
- *
- * ------------------------------------------------
- * char **rc = PHYSFS_enumerateFiles("savegames");
- * char **i;
- *
- * for (i = rc; *i != NULL; i++)
- *     printf("We've got [%s].\n", *i);
- *
- * PHYSFS_freeList(rc);
- * ------------------------------------------------
- *
- *  ...will print:
- *
- * ------------------------------------------------
- * We've got [x.sav].
- * We've got [y.sav].
- * We've got [z.sav].
- * We've got [w.sav].
- * ------------------------------------------------
- *
- * Don't forget to call PHYSFS_freeList() with the return value from this
- *  function when you are done with it.
- *
- *    @param path directory in platform-independent notation to enumerate.
- *   @return Null-terminated array of null-terminated strings.
- */
 char **PHYSFS_enumerateFiles(const char *path)
 {
+    SearchDirInfo *i;
+    char **retval = NULL;
+    LinkedStringList *rc;
+    LinkedStringList *finalList = NULL;
+
+    for (i = searchPath; i != NULL; i = i->next)
+    {
+        assert(i->reader->funcs->enumerateFiles != NULL);
+        rc = i->reader->funcs->enumerateFiles(path);
+        interpolateStringLists(&finalList, rc);
+    } /* for */
+
+    retval = convertStringListToPhysFSList(finalList);
+    return(retval);
 } /* PHYSFS_enumerateFiles */
 
 
diff --git a/physfs_internal.h b/physfs_internal.h
index 2a44b609..1fa2ce33 100644
--- a/physfs_internal.h
+++ b/physfs_internal.h
@@ -88,6 +88,12 @@ typedef struct __PHYSFS_DIRREADER__
 } DirHandle;
 
 
+typedef struct __PHYSFS_LINKEDSTRINGLIST__
+{
+    char *str;
+    struct __PHYSFS_LINKEDSTRINGLIST__ *next;
+} LinkedStringList;
+
 /*
  * Symlinks should always be followed; PhysicsFS will use
  *  DirFunctions->isSymLink() and make a judgement on whether to
@@ -110,11 +116,14 @@ typedef struct __PHYSFS_DIRFUNCTIONS__
     DirHandle *(*openArchive)(const char *name);
 
         /*
-         * Returns a list (freeable via PHYSFS_freeList()) of
-         *  all files in dirname.
+         * Returns a list of all files in dirname. Each element of this list
+         *  (and its "str" field) will be deallocated with the system's free()
+         *  function by the caller, so be sure to explicitly malloc() each
+         *  chunk.
+         * If you have a memory failure, return as much as you can.
          *  This dirname is in platform-independent notation.
          */
-    char **(*enumerateFiles)(DirHandle *r, const char *dirname);
+    LinkedStringList **(*enumerateFiles)(DirHandle *r, const char *dirname);
 
         /*
          * Returns non-zero if filename is really a directory.