Reworked the "unpacked" archivers to use DirTree.
authorRyan C. Gordon <icculus@icculus.org>
Sun, 16 Jul 2017 04:39:14 -0400
changeset 1463 c23e55bad32d
parent 1462 e4995ae256a7
child 1464 5f40aef46865
Reworked the "unpacked" archivers to use DirTree. This cleaned up a lot of code and improved things, and also allowed a lot of the restrictions on unpacked archivers to be removed.
src/archiver_grp.c
src/archiver_hog.c
src/archiver_mvl.c
src/archiver_qpak.c
src/archiver_slb.c
src/archiver_unpacked.c
src/archiver_wad.c
src/physfs_internal.h
--- a/src/archiver_grp.c	Sat Jul 15 15:59:55 2017 -0400
+++ b/src/archiver_grp.c	Sun Jul 16 04:39:14 2017 -0400
@@ -29,36 +29,30 @@
 
 #if PHYSFS_SUPPORTS_GRP
 
-static UNPKentry *grpLoadEntries(PHYSFS_Io *io, PHYSFS_uint32 fileCount)
+static int grpLoadEntries(PHYSFS_Io *io, const PHYSFS_uint32 count, void *arc)
 {
-    PHYSFS_uint32 location = 16;  /* sizeof sig. */
-    UNPKentry *entries = NULL;
-    UNPKentry *entry = NULL;
-    char *ptr = NULL;
+    PHYSFS_uint32 location = 16 + (16 * count);  /* past sig+metadata. */
+    PHYSFS_uint32 i;
 
-    entries = (UNPKentry *) allocator.Malloc(sizeof (UNPKentry) * fileCount);
-    BAIL_IF(entries == NULL, PHYSFS_ERR_OUT_OF_MEMORY, NULL);
-
-    location += (16 * fileCount);
+    for (i = 0; i < count; i++)
+    {
+        char *ptr;
+        char name[13];
+        PHYSFS_uint32 size;
+        BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, name, 12), 0);
+        BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &size, 4), 0);
 
-    for (entry = entries; fileCount > 0; fileCount--, entry++)
-    {
-        GOTO_IF_ERRPASS(!__PHYSFS_readAll(io, &entry->name, 12), failed);
-        GOTO_IF_ERRPASS(!__PHYSFS_readAll(io, &entry->size, 4), failed);
-        entry->name[12] = '\0';  /* name isn't null-terminated in file. */
-        if ((ptr = strchr(entry->name, ' ')) != NULL)
+        name[12] = '\0';  /* name isn't null-terminated in file. */
+        if ((ptr = strchr(name, ' ')) != NULL)
             *ptr = '\0';  /* trim extra spaces. */
 
-        entry->size = PHYSFS_swapULE32(entry->size);
-        entry->startPos = location;
-        location += entry->size;
+        size = PHYSFS_swapULE32(size);
+        BAIL_IF_ERRPASS(!UNPK_addEntry(arc, name, 0, location, size), 0);
+
+        location += size;
     } /* for */
 
-    return entries;
-
-failed:
-    allocator.Free(entries);
-    return NULL;
+    return 1;
 } /* grpLoadEntries */
 
 
@@ -66,7 +60,7 @@
 {
     PHYSFS_uint8 buf[12];
     PHYSFS_uint32 count = 0;
-    UNPKentry *entries = NULL;
+    void *unpkarc = NULL;
 
     assert(io != NULL);  /* shouldn't ever happen. */
 
@@ -79,9 +73,16 @@
     BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &count, sizeof(count)), NULL);
     count = PHYSFS_swapULE32(count);
 
-    entries = grpLoadEntries(io, count);
-    BAIL_IF_ERRPASS(!entries, NULL);
-    return UNPK_openArchive(io, entries, count);
+    unpkarc = UNPK_openArchive(io, count);
+    BAIL_IF_ERRPASS(!unpkarc, NULL);
+
+    if (!grpLoadEntries(io, count, unpkarc))
+    {
+        UNPK_closeArchive(unpkarc);
+        return NULL;
+    } /* if */
+
+    return unpkarc;
 } /* GRP_openArchive */
 
 
--- a/src/archiver_hog.c	Sat Jul 15 15:59:55 2017 -0400
+++ b/src/archiver_hog.c	Sun Jul 16 04:39:14 2017 -0400
@@ -34,43 +34,30 @@
 
 #if PHYSFS_SUPPORTS_HOG
 
-static UNPKentry *hogLoadEntries(PHYSFS_Io *io, PHYSFS_uint32 *_entCount)
+static int hogLoadEntries(PHYSFS_Io *io, void *unpkarc)
 {
     const PHYSFS_uint64 iolen = io->length(io);
-    PHYSFS_uint32 entCount = 0;
-    void *ptr = NULL;
-    UNPKentry *entries = NULL;
-    UNPKentry *entry = NULL;
-    PHYSFS_uint32 size = 0;
     PHYSFS_uint32 pos = 3;
 
     while (pos < iolen)
     {
-        entCount++;
-        ptr = allocator.Realloc(ptr, sizeof (UNPKentry) * entCount);
-        GOTO_IF(ptr == NULL, PHYSFS_ERR_OUT_OF_MEMORY, failed);
-        entries = (UNPKentry *) ptr;
-        entry = &entries[entCount-1];
+        PHYSFS_uint32 size;
+        char name[13];
 
-        GOTO_IF_ERRPASS(!__PHYSFS_readAll(io, &entry->name, 13), failed);
-        pos += 13;
-        GOTO_IF_ERRPASS(!__PHYSFS_readAll(io, &size, 4), failed);
-        pos += 4;
+        BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, name, 13), 0);
+        BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &size, 4), 0);
+        name[12] = '\0';  /* just in case. */
+        pos += 13 + 4;
 
-        entry->size = PHYSFS_swapULE32(size);
-        entry->startPos = pos;
+        size = PHYSFS_swapULE32(size);
+        BAIL_IF_ERRPASS(!UNPK_addEntry(unpkarc, name, 0, pos, size), 0);
         pos += size;
 
         /* skip over entry */
-        GOTO_IF_ERRPASS(!io->seek(io, pos), failed);
+        BAIL_IF_ERRPASS(!io->seek(io, pos), 0);
     } /* while */
 
-    *_entCount = entCount;
-    return entries;
-
-failed:
-    allocator.Free(entries);
-    return NULL;
+    return 1;
 } /* hogLoadEntries */
 
 
@@ -78,16 +65,23 @@
 {
     PHYSFS_uint8 buf[3];
     PHYSFS_uint32 count = 0;
-    UNPKentry *entries = NULL;
+    void *unpkarc = NULL;
 
     assert(io != NULL);  /* shouldn't ever happen. */
     BAIL_IF(forWriting, PHYSFS_ERR_READ_ONLY, NULL);
     BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, buf, 3), NULL);
     BAIL_IF(memcmp(buf, "DHF", 3) != 0, PHYSFS_ERR_UNSUPPORTED, NULL);
 
-    entries = hogLoadEntries(io, &count);
-    BAIL_IF_ERRPASS(!entries, NULL);
-    return UNPK_openArchive(io, entries, count);
+    unpkarc = UNPK_openArchive(io, count);
+    BAIL_IF_ERRPASS(!unpkarc, NULL);
+
+    if (!hogLoadEntries(io, unpkarc))
+    {
+        UNPK_closeArchive(unpkarc);
+        return NULL;
+    } /* if */
+
+    return unpkarc;
 } /* HOG_openArchive */
 
 
--- a/src/archiver_mvl.c	Sat Jul 15 15:59:55 2017 -0400
+++ b/src/archiver_mvl.c	Sun Jul 16 04:39:14 2017 -0400
@@ -32,31 +32,24 @@
 
 #if PHYSFS_SUPPORTS_MVL
 
-static UNPKentry *mvlLoadEntries(PHYSFS_Io *io, PHYSFS_uint32 fileCount)
+static int mvlLoadEntries(PHYSFS_Io *io, const PHYSFS_uint32 count, void *arc)
 {
-    PHYSFS_uint32 location = 8;  /* sizeof sig. */
-    UNPKentry *entries = NULL;
-    UNPKentry *entry = NULL;
-
-    entries = (UNPKentry *) allocator.Malloc(sizeof (UNPKentry) * fileCount);
-    BAIL_IF(entries == NULL, PHYSFS_ERR_OUT_OF_MEMORY, NULL);
+    PHYSFS_uint32 location = 8 + (17 * count);   /* past sig+metadata. */
+    PHYSFS_uint32 i;
 
-    location += (17 * fileCount);
-
-    for (entry = entries; fileCount > 0; fileCount--, entry++)
+    for (i = 0; i < count; i++)
     {
-        if (!__PHYSFS_readAll(io, &entry->name, 13)) goto failed;
-        if (!__PHYSFS_readAll(io, &entry->size, 4)) goto failed;
-        entry->size = PHYSFS_swapULE32(entry->size);
-        entry->startPos = location;
-        location += entry->size;
+        PHYSFS_uint32 size;
+        char name[13];
+        BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, name, 13), 0);
+        BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &size, 4), 0);
+        name[12] = '\0';  /* just in case. */
+        size = PHYSFS_swapULE32(size);
+        BAIL_IF_ERRPASS(!UNPK_addEntry(arc, name, 0, location, size), 0);
+        location += size;
     } /* for */
 
-    return entries;
-
-failed:
-    allocator.Free(entries);
-    return NULL;
+    return 1;
 } /* mvlLoadEntries */
 
 
@@ -64,7 +57,7 @@
 {
     PHYSFS_uint8 buf[4];
     PHYSFS_uint32 count = 0;
-    UNPKentry *entries = NULL;
+    void *unpkarc;
 
     assert(io != NULL);  /* shouldn't ever happen. */
     BAIL_IF(forWriting, PHYSFS_ERR_READ_ONLY, NULL);
@@ -73,8 +66,17 @@
     BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &count, sizeof(count)), NULL);
 
     count = PHYSFS_swapULE32(count);
-    entries = mvlLoadEntries(io, count);
-    return (!entries) ? NULL : UNPK_openArchive(io, entries, count);
+
+    unpkarc = UNPK_openArchive(io, count);
+    BAIL_IF_ERRPASS(!unpkarc, NULL);
+
+    if (!mvlLoadEntries(io, count, unpkarc))
+    {
+        UNPK_closeArchive(unpkarc);
+        return NULL;
+    } /* if */
+
+    return unpkarc;
 } /* MVL_openArchive */
 
 
--- a/src/archiver_qpak.c	Sat Jul 15 15:59:55 2017 -0400
+++ b/src/archiver_qpak.c	Sun Jul 16 04:39:14 2017 -0400
@@ -36,37 +36,32 @@
 
 #define QPAK_SIG 0x4B434150   /* "PACK" in ASCII. */
 
-static UNPKentry *qpakLoadEntries(PHYSFS_Io *io, PHYSFS_uint32 fileCount)
+static int qpakLoadEntries(PHYSFS_Io *io, const PHYSFS_uint32 count, void *arc)
 {
-    UNPKentry *entries = NULL;
-    UNPKentry *entry = NULL;
-
-    entries = (UNPKentry *) allocator.Malloc(sizeof (UNPKentry) * fileCount);
-    BAIL_IF(entries == NULL, PHYSFS_ERR_OUT_OF_MEMORY, NULL);
-
-    for (entry = entries; fileCount > 0; fileCount--, entry++)
+    PHYSFS_uint32 i;
+    for (i = 0; i < count; i++)
     {
-        if (!__PHYSFS_readAll(io, &entry->name, 56)) goto failed;
-        if (!__PHYSFS_readAll(io, &entry->startPos, 4)) goto failed;
-        if (!__PHYSFS_readAll(io, &entry->size, 4)) goto failed;
-        entry->size = PHYSFS_swapULE32(entry->size);
-        entry->startPos = PHYSFS_swapULE32(entry->startPos);
+        PHYSFS_uint32 size;
+        PHYSFS_uint32 location;
+        char name[56];
+        BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, name, 56), 0);
+        BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &location, 4), 0);
+        BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &size, 4), 0);
+        size = PHYSFS_swapULE32(size);
+        location = PHYSFS_swapULE32(location);
+        BAIL_IF_ERRPASS(!UNPK_addEntry(arc, name, 0, location, size), 0);
     } /* for */
 
-    return entries;
-
-failed:
-    allocator.Free(entries);
-    return NULL;
+    return 1;
 } /* qpakLoadEntries */
 
 
 static void *QPAK_openArchive(PHYSFS_Io *io, const char *name, int forWriting)
 {
-    UNPKentry *entries = NULL;
     PHYSFS_uint32 val = 0;
     PHYSFS_uint32 pos = 0;
     PHYSFS_uint32 count = 0;
+    void *unpkarc;
 
     assert(io != NULL);  /* shouldn't ever happen. */
 
@@ -88,9 +83,16 @@
 
     BAIL_IF_ERRPASS(!io->seek(io, pos), NULL);
 
-    entries = qpakLoadEntries(io, count);
-    BAIL_IF_ERRPASS(!entries, NULL);
-    return UNPK_openArchive(io, entries, count);
+    unpkarc = UNPK_openArchive(io, count);
+    BAIL_IF_ERRPASS(!unpkarc, NULL);
+
+    if (!qpakLoadEntries(io, count, unpkarc))
+    {
+        UNPK_closeArchive(unpkarc);
+        return NULL;
+    } /* if */
+
+    return unpkarc;
 } /* QPAK_openArchive */
 
 
--- a/src/archiver_slb.c	Sat Jul 15 15:59:55 2017 -0400
+++ b/src/archiver_slb.c	Sun Jul 16 04:39:14 2017 -0400
@@ -20,79 +20,80 @@
 
 #if PHYSFS_SUPPORTS_SLB
 
-static UNPKentry *slbLoadEntries(PHYSFS_Io *io, PHYSFS_uint32 fileCount)
+static int slbLoadEntries(PHYSFS_Io *io, const PHYSFS_uint32 count, void *arc)
 {
-    UNPKentry *entries = NULL;
-    UNPKentry *entry = NULL;
-
-    entries = (UNPKentry *) allocator.Malloc(sizeof (UNPKentry) * fileCount);
-    BAIL_IF(entries == NULL, PHYSFS_ERR_OUT_OF_MEMORY, NULL);
-
-    for (entry = entries; fileCount > 0; fileCount--, entry++)
+    PHYSFS_uint32 i;
+    for (i = 0; i < count; i++)
     {
+        PHYSFS_uint32 location;
+        PHYSFS_uint32 size;
+        char name[64];
+        char backslash;
         char *ptr;
 
         /* don't include the '\' in the beginning */
-        char backslash;
-        GOTO_IF_ERRPASS(!__PHYSFS_readAll(io, &backslash, 1), failed);
-        GOTO_IF_ERRPASS(backslash != '\\', failed);
+        BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &backslash, 1), 0);
+        BAIL_IF(backslash != '\\', PHYSFS_ERR_CORRUPT, 0);
 
         /* read the rest of the buffer, 63 bytes */
-        GOTO_IF_ERRPASS(!__PHYSFS_readAll(io, &entry->name, 63), failed);
-        entry->name[63] = '\0'; /* in case the name lacks the null terminator */
+        BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &name, 63), 0);
+        name[63] = '\0'; /* in case the name lacks the null terminator */
 
         /* convert backslashes */
-        for (ptr = entry->name; *ptr; ptr++)
+        for (ptr = name; *ptr; ptr++)
         {
             if (*ptr == '\\')
                 *ptr = '/';
         } /* for */
 
-        GOTO_IF_ERRPASS(!__PHYSFS_readAll(io, &entry->startPos, 4), failed);
-        entry->startPos = PHYSFS_swapULE32(entry->startPos);
+        BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &location, 4), 0);
+        location = PHYSFS_swapULE32(location);
 
-        GOTO_IF_ERRPASS(!__PHYSFS_readAll(io, &entry->size, 4), failed);
-        entry->size = PHYSFS_swapULE32(entry->size);
+        BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &size, 4), 0);
+        size = PHYSFS_swapULE32(size);
+
+        BAIL_IF_ERRPASS(!UNPK_addEntry(arc, name, 0, location, size), 0);
     } /* for */
-    
-    return entries;
 
-failed:
-    allocator.Free(entries);
-    return NULL;
-
+    return 1;
 } /* slbLoadEntries */
 
 
 static void *SLB_openArchive(PHYSFS_Io *io, const char *name, int forWriting)
 {
     PHYSFS_uint32 version;
-    PHYSFS_uint32 count = 0;
-    PHYSFS_uint32 tocPos = 0;
-    UNPKentry *entries = NULL;
+    PHYSFS_uint32 count;
+    PHYSFS_uint32 tocPos;
+    void *unpkarc;
 
     assert(io != NULL);  /* shouldn't ever happen. */
 
     BAIL_IF(forWriting, PHYSFS_ERR_READ_ONLY, NULL);
 
-    BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &version, sizeof(version)), NULL);
+    BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &version, sizeof (version)), NULL);
     version = PHYSFS_swapULE32(version);
     BAIL_IF(version != 0, PHYSFS_ERR_UNSUPPORTED, NULL);
 
-    BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &count, sizeof(count)), NULL);
+    BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &count, sizeof (count)), NULL);
     count = PHYSFS_swapULE32(count);
 
     /* offset of the table of contents */
-    BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &tocPos, sizeof(tocPos)), NULL);
+    BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &tocPos, sizeof (tocPos)), NULL);
     tocPos = PHYSFS_swapULE32(tocPos);
     
     /* seek to the table of contents */
     BAIL_IF_ERRPASS(!io->seek(io, tocPos), NULL);
 
-    entries = slbLoadEntries(io, count);
-    BAIL_IF_ERRPASS(!entries, NULL);
+    unpkarc = UNPK_openArchive(io, count);
+    BAIL_IF_ERRPASS(!unpkarc, NULL);
 
-    return UNPK_openArchive(io, entries, count);
+    if (!slbLoadEntries(io, count, unpkarc))
+    {
+        UNPK_closeArchive(unpkarc);
+        return NULL;
+    } /* if */
+
+    return unpkarc;
 } /* SLB_openArchive */
 
 
@@ -120,4 +121,3 @@
 #endif  /* defined PHYSFS_SUPPORTS_SLB */
 
 /* end of archiver_slb.c ... */
-
--- a/src/archiver_unpacked.c	Sat Jul 15 15:59:55 2017 -0400
+++ b/src/archiver_unpacked.c	Sun Jul 16 04:39:14 2017 -0400
@@ -5,10 +5,8 @@
  *  formats that can just hand back a list of files and the offsets of their
  *  uncompressed data. There are an alarming number of formats like this.
  *
- * RULES: Archive entries must be uncompressed, must not have separate subdir
- *  entries (but can have subdirs), must be case insensitive LOW ASCII
- *  filenames <= 64 bytes. No symlinks, etc. We can relax some of these rules
- *  as necessary.
+ * RULES: Archive entries must be uncompressed. Dirs and files allowed, but no
+ *  symlinks, etc. We can relax some of these rules as necessary.
  *
  * Please see the file LICENSE.txt in the source's root directory.
  *
@@ -20,11 +18,16 @@
 
 typedef struct
 {
+    __PHYSFS_DirTree tree;
     PHYSFS_Io *io;
-    PHYSFS_uint32 entryCount;
-    UNPKentry *entries;
 } UNPKinfo;
 
+typedef struct
+{
+    __PHYSFS_DirTreeEntry tree;
+    PHYSFS_uint64 startPos;
+    PHYSFS_uint64 size;
+} UNPKentry;
 
 typedef struct
 {
@@ -37,9 +40,15 @@
 void UNPK_closeArchive(void *opaque)
 {
     UNPKinfo *info = ((UNPKinfo *) opaque);
-    info->io->destroy(info->io);
-    allocator.Free(info->entries);
-    allocator.Free(info);
+    if (info)
+    {
+        __PHYSFS_DirTreeDeinit(&info->tree);
+
+        if (info->io)
+            info->io->destroy(info->io);
+
+        allocator.Free(info);
+    } /* if */
 } /* UNPK_closeArchive */
 
 
@@ -145,202 +154,9 @@
 };
 
 
-static int entryCmp(void *_a, size_t one, size_t two)
-{
-    if (one != two)
-    {
-        const UNPKentry *a = (const UNPKentry *) _a;
-        return __PHYSFS_stricmpASCII(a[one].name, a[two].name);
-    } /* if */
-
-    return 0;
-} /* entryCmp */
-
-
-static void entrySwap(void *_a, size_t one, size_t two)
-{
-    if (one != two)
-    {
-        UNPKentry tmp;
-        UNPKentry *first = &(((UNPKentry *) _a)[one]);
-        UNPKentry *second = &(((UNPKentry *) _a)[two]);
-        memcpy(&tmp, first, sizeof (UNPKentry));
-        memcpy(first, second, sizeof (UNPKentry));
-        memcpy(second, &tmp, sizeof (UNPKentry));
-    } /* if */
-} /* entrySwap */
-
-
-static PHYSFS_sint32 findStartOfDir(UNPKinfo *info, const char *path,
-                                    int stop_on_first_find)
-{
-    PHYSFS_sint32 lo = 0;
-    PHYSFS_sint32 hi = (PHYSFS_sint32) (info->entryCount - 1);
-    PHYSFS_sint32 middle;
-    PHYSFS_uint32 dlen = (PHYSFS_uint32) strlen(path);
-    PHYSFS_sint32 retval = -1;
-    const char *name;
-    int rc;
-
-    if (*path == '\0')  /* root dir? */
-        return 0;
-
-    if ((dlen > 0) && (path[dlen - 1] == '/')) /* ignore trailing slash. */
-        dlen--;
-
-    while (lo <= hi)
-    {
-        middle = lo + ((hi - lo) / 2);
-        name = info->entries[middle].name;
-        rc = __PHYSFS_strnicmpASCII(path, name, dlen);
-        if (rc == 0)
-        {
-            char ch = name[dlen];
-            if (ch < '/') /* make sure this isn't just a substr match. */
-                rc = -1;
-            else if (ch > '/')
-                rc = 1;
-            else 
-            {
-                if (stop_on_first_find) /* Just checking dir's existance? */
-                    return middle;
-
-                if (name[dlen + 1] == '\0') /* Skip initial dir entry. */
-                    return (middle + 1);
-
-                /* there might be more entries earlier in the list. */
-                retval = middle;
-                hi = middle - 1;
-            } /* else */
-        } /* if */
-
-        if (rc > 0)
-            lo = middle + 1;
-        else
-            hi = middle - 1;
-    } /* while */
-
-    return retval;
-} /* findStartOfDir */
-
-
-/*
- * Moved to seperate function so we can use alloca then immediately throw
- *  away the allocated stack space...
- */
-static void doEnumCallback(PHYSFS_EnumFilesCallback cb, void *callbackdata,
-                           const char *odir, const char *str, PHYSFS_sint32 ln)
+static inline UNPKentry *findEntry(UNPKinfo *info, const char *path)
 {
-    char *newstr = __PHYSFS_smallAlloc(ln + 1);
-    if (newstr == NULL)
-        return;
-
-    memcpy(newstr, str, ln);
-    newstr[ln] = '\0';
-    cb(callbackdata, odir, newstr);
-    __PHYSFS_smallFree(newstr);
-} /* doEnumCallback */
-
-
-void UNPK_enumerateFiles(void *opaque, const char *dname,
-                         PHYSFS_EnumFilesCallback cb,
-                         const char *origdir, void *callbackdata)
-{
-    UNPKinfo *info = ((UNPKinfo *) opaque);
-    PHYSFS_sint32 dlen, dlen_inc, max, i;
-
-    i = findStartOfDir(info, dname, 0);
-    if (i == -1)  /* no such directory. */
-        return;
-
-    dlen = (PHYSFS_sint32) strlen(dname);
-    if ((dlen > 0) && (dname[dlen - 1] == '/')) /* ignore trailing slash. */
-        dlen--;
-
-    dlen_inc = ((dlen > 0) ? 1 : 0) + dlen;
-    max = (PHYSFS_sint32) info->entryCount;
-    while (i < max)
-    {
-        char *add;
-        char *ptr;
-        PHYSFS_sint32 ln;
-        char *e = info->entries[i].name;
-        if ((dlen) &&
-            ((__PHYSFS_strnicmpASCII(e, dname, dlen)) || (e[dlen] != '/')))
-        {
-            break;  /* past end of this dir; we're done. */
-        } /* if */
-
-        add = e + dlen_inc;
-        ptr = strchr(add, '/');
-        ln = (PHYSFS_sint32) ((ptr) ? ptr-add : strlen(add));
-        doEnumCallback(cb, callbackdata, origdir, add, ln);
-        ln += dlen_inc;  /* point past entry to children... */
-
-        /* increment counter and skip children of subdirs... */
-        while ((++i < max) && (ptr != NULL))
-        {
-            char *e_new = info->entries[i].name;
-            if ((__PHYSFS_strnicmpASCII(e, e_new, ln) != 0) ||
-                (e_new[ln] != '/'))
-            {
-                break;
-            } /* if */
-        } /* while */
-    } /* while */
-} /* UNPK_enumerateFiles */
-
-
-/*
- * This will find the UNPKentry associated with a path in platform-independent
- *  notation. Directories don't have UNPKentries associated with them, but 
- *  (*isDir) will be set to non-zero if a dir was hit.
- */
-static UNPKentry *findEntry(const UNPKinfo *info, const char *path, int *isDir)
-{
-    UNPKentry *a = info->entries;
-    PHYSFS_sint32 pathlen = (PHYSFS_sint32) strlen(path);
-    PHYSFS_sint32 lo = 0;
-    PHYSFS_sint32 hi = (PHYSFS_sint32) (info->entryCount - 1);
-    PHYSFS_sint32 middle;
-    const char *thispath = NULL;
-    int rc;
-
-    while (lo <= hi)
-    {
-        middle = lo + ((hi - lo) / 2);
-        thispath = a[middle].name;
-        rc = __PHYSFS_strnicmpASCII(path, thispath, pathlen);
-
-        if (rc > 0)
-            lo = middle + 1;
-
-        else if (rc < 0)
-            hi = middle - 1;
-
-        else /* substring match...might be dir or entry or nothing. */
-        {
-            if (isDir != NULL)
-            {
-                *isDir = (thispath[pathlen] == '/');
-                if (*isDir)
-                    return NULL;
-            } /* if */
-
-            if (thispath[pathlen] == '\0') /* found entry? */
-                return &a[middle];
-            /* adjust search params, try again. */
-            else if (thispath[pathlen] > '/')
-                hi = middle - 1;
-            else
-                lo = middle + 1;
-        } /* if */
-    } /* while */
-
-    if (isDir != NULL)
-        *isDir = 0;
-
-    BAIL(PHYSFS_ERR_NOT_FOUND, NULL);
+    return (UNPKentry *) __PHYSFS_DirTreeFind(&info->tree, path);
 } /* findEntry */
 
 
@@ -349,11 +165,10 @@
     PHYSFS_Io *retval = NULL;
     UNPKinfo *info = (UNPKinfo *) opaque;
     UNPKfileinfo *finfo = NULL;
-    int isdir = 0;
-    UNPKentry *entry = findEntry(info, name, &isdir);
+    UNPKentry *entry = findEntry(info, name);
 
-    GOTO_IF(isdir, PHYSFS_ERR_NOT_A_FILE, UNPK_openRead_failed);
-    GOTO_IF_ERRPASS(!entry, UNPK_openRead_failed);
+    BAIL_IF_ERRPASS(!entry, NULL);
+    BAIL_IF(entry->tree.isdir, PHYSFS_ERR_NOT_A_FILE, NULL);
 
     retval = (PHYSFS_Io *) allocator.Malloc(sizeof (PHYSFS_Io));
     GOTO_IF(!retval, PHYSFS_ERR_OUT_OF_MEMORY, UNPK_openRead_failed);
@@ -413,25 +228,22 @@
 } /* UNPK_mkdir */
 
 
-int UNPK_stat(void *opaque, const char *filename, PHYSFS_Stat *stat)
+int UNPK_stat(void *opaque, const char *path, PHYSFS_Stat *stat)
 {
-    int isDir = 0;
-    const UNPKinfo *info = (const UNPKinfo *) opaque;
-    const UNPKentry *entry = findEntry(info, filename, &isDir);
+    UNPKinfo *info = (UNPKinfo *) opaque;
+    const UNPKentry *entry = findEntry(info, path);
 
-    if (isDir)
+    BAIL_IF_ERRPASS(!entry, 0);
+
+    if (entry->tree.isdir)
     {
         stat->filetype = PHYSFS_FILETYPE_DIRECTORY;
         stat->filesize = 0;
     } /* if */
-    else if (entry != NULL)
+    else
     {
         stat->filetype = PHYSFS_FILETYPE_REGULAR;
         stat->filesize = entry->size;
-    } /* else if */
-    else
-    {
-        return 0;
     } /* else */
 
     stat->modtime = -1;
@@ -443,19 +255,34 @@
 } /* UNPK_stat */
 
 
-void *UNPK_openArchive(PHYSFS_Io *io, UNPKentry *e, const PHYSFS_uint32 num)
+void *UNPK_addEntry(void *opaque, char *name, const int isdir,
+                    const PHYSFS_uint64 pos, const PHYSFS_uint64 len)
+{
+    UNPKinfo *info = (UNPKinfo *) opaque;
+    UNPKentry *entry;
+
+    entry = (UNPKentry *) __PHYSFS_DirTreeAdd(&info->tree, name, isdir);
+    BAIL_IF_ERRPASS(!entry, NULL);
+
+    entry->startPos = pos;
+    entry->size = len;
+
+    return entry;
+} /* UNPK_addEntry */
+
+
+void *UNPK_openArchive(PHYSFS_Io *io, const PHYSFS_uint64 entry_count)
 {
     UNPKinfo *info = (UNPKinfo *) allocator.Malloc(sizeof (UNPKinfo));
-    if (info == NULL)
+    BAIL_IF(!info, PHYSFS_ERR_OUT_OF_MEMORY, NULL);
+
+    if (!__PHYSFS_DirTreeInit(&info->tree, entry_count, sizeof (UNPKentry)))
     {
-        allocator.Free(e);
-        BAIL(PHYSFS_ERR_OUT_OF_MEMORY, NULL);
+        allocator.Free(info);
+        return NULL;
     } /* if */
 
-    __PHYSFS_sort(e, (size_t) num, entryCmp, entrySwap);
     info->io = io;
-    info->entryCount = num;
-    info->entries = e;
 
     return info;
 } /* UNPK_openArchive */
--- a/src/archiver_wad.c	Sat Jul 15 15:59:55 2017 -0400
+++ b/src/archiver_wad.c	Sun Jul 16 04:39:14 2017 -0400
@@ -47,44 +47,35 @@
 
 #if PHYSFS_SUPPORTS_WAD
 
-static UNPKentry *wadLoadEntries(PHYSFS_Io *io, PHYSFS_uint32 fileCount)
+static int wadLoadEntries(PHYSFS_Io *io, const PHYSFS_uint32 count, void *arc)
 {
-    PHYSFS_uint32 directoryOffset;
-    UNPKentry *entries = NULL;
-    UNPKentry *entry = NULL;
-
-    BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &directoryOffset, 4), 0);
-    directoryOffset = PHYSFS_swapULE32(directoryOffset);
-
-    BAIL_IF_ERRPASS(!io->seek(io, directoryOffset), 0);
+    PHYSFS_uint32 i;
+    for (i = 0; i < count; i++)
+    {
+        PHYSFS_uint32 location;
+        PHYSFS_uint32 size;
+        char name[9];
 
-    entries = (UNPKentry *) allocator.Malloc(sizeof (UNPKentry) * fileCount);
-    BAIL_IF(!entries, PHYSFS_ERR_OUT_OF_MEMORY, NULL);
+        BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &location, 4), 0);
+        BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &size, 4), 0);
+        BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, name, 8), 0);
 
-    for (entry = entries; fileCount > 0; fileCount--, entry++)
-    {
-        if (!__PHYSFS_readAll(io, &entry->startPos, 4)) goto failed;
-        if (!__PHYSFS_readAll(io, &entry->size, 4)) goto failed;
-        if (!__PHYSFS_readAll(io, &entry->name, 8)) goto failed;
-
-        entry->name[8] = '\0'; /* name might not be null-terminated in file. */
-        entry->size = PHYSFS_swapULE32(entry->size);
-        entry->startPos = PHYSFS_swapULE32(entry->startPos);
+        name[8] = '\0'; /* name might not be null-terminated in file. */
+        size = PHYSFS_swapULE32(size);
+        location = PHYSFS_swapULE32(location);
+        BAIL_IF_ERRPASS(!UNPK_addEntry(arc, name, 0, location, size), 0);
     } /* for */
 
-    return entries;
-
-failed:
-    allocator.Free(entries);
-    return NULL;
+    return 1;
 } /* wadLoadEntries */
 
 
 static void *WAD_openArchive(PHYSFS_Io *io, const char *name, int forWriting)
 {
     PHYSFS_uint8 buf[4];
-    UNPKentry *entries = NULL;
-    PHYSFS_uint32 count = 0;
+    PHYSFS_uint32 count;
+    PHYSFS_uint32 directoryOffset;
+    void *unpkarc;
 
     assert(io != NULL);  /* shouldn't ever happen. */
 
@@ -96,9 +87,21 @@
     BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &count, sizeof (count)), NULL);
     count = PHYSFS_swapULE32(count);
 
-    entries = wadLoadEntries(io, count);
-    BAIL_IF_ERRPASS(!entries, NULL);
-    return UNPK_openArchive(io, entries, count);
+    BAIL_IF_ERRPASS(!__PHYSFS_readAll(io, &directoryOffset, 4), 0);
+    directoryOffset = PHYSFS_swapULE32(directoryOffset);
+
+    BAIL_IF_ERRPASS(!io->seek(io, directoryOffset), 0);
+
+    unpkarc = UNPK_openArchive(io, count);
+    BAIL_IF_ERRPASS(!unpkarc, NULL);
+
+    if (!wadLoadEntries(io, count, unpkarc))
+    {
+        UNPK_closeArchive(unpkarc);
+        return NULL;
+    } /* if */
+
+    return unpkarc;
 } /* WAD_openArchive */
 
 
--- a/src/physfs_internal.h	Sat Jul 15 15:59:55 2017 -0400
+++ b/src/physfs_internal.h	Sun Jul 16 04:39:14 2017 -0400
@@ -342,24 +342,17 @@
 
 /* These are shared between some archivers. */
 
-typedef struct
-{
-    char name[64];
-    PHYSFS_uint32 startPos;
-    PHYSFS_uint32 size;
-} UNPKentry;
-
 void UNPK_closeArchive(void *opaque);
-void *UNPK_openArchive(PHYSFS_Io *io,UNPKentry *e,const PHYSFS_uint32 n);
-void UNPK_enumerateFiles(void *opaque, const char *dname,
-                         PHYSFS_EnumFilesCallback cb,
-                         const char *origdir, void *callbackdata);
+void *UNPK_openArchive(PHYSFS_Io *io, const PHYSFS_uint64 entry_count);
+void *UNPK_addEntry(void *opaque, char *name, const int isdir,
+                    const PHYSFS_uint64 pos, const PHYSFS_uint64 len);
 PHYSFS_Io *UNPK_openRead(void *opaque, const char *name);
 PHYSFS_Io *UNPK_openWrite(void *opaque, const char *name);
 PHYSFS_Io *UNPK_openAppend(void *opaque, const char *name);
 int UNPK_remove(void *opaque, const char *name);
 int UNPK_mkdir(void *opaque, const char *name);
 int UNPK_stat(void *opaque, const char *fn, PHYSFS_Stat *st);
+#define UNPK_enumerateFiles __PHYSFS_DirTreeEnumerateFiles