Generalized sorting routines, and removed individual implementations.
--- a/archivers/grp.c Tue Aug 20 01:00:23 2002 +0000
+++ b/archivers/grp.c Tue Aug 20 01:34:27 2002 +0000
@@ -41,13 +41,6 @@
#define __PHYSICSFS_INTERNAL__
#include "physfs_internal.h"
-/*
- * When sorting the grp entries in an archive, we use a modified QuickSort.
- * When there are less then GRP_QUICKSORT_THRESHOLD entries left to sort,
- * we switch over to an InsertionSort for the remainder. Tweak to taste.
- */
-#define GRP_QUICKSORT_THRESHOLD 4
-
typedef struct
{
char name[13];
@@ -258,78 +251,22 @@
} /* GRP_isArchive */
-static void grp_entry_swap(GRPentry *a, PHYSFS_uint32 one, PHYSFS_uint32 two)
+static int grp_entry_cmp(void *_a, PHYSFS_uint32 one, PHYSFS_uint32 two)
{
- GRPentry tmp;
- memcpy(&tmp, &a[one], sizeof (GRPentry));
- memcpy(&a[one], &a[two], sizeof (GRPentry));
- memcpy(&a[two], &tmp, sizeof (GRPentry));
-} /* grp_entry_swap */
+ GRPentry *a = (GRPentry *) _a;
+ return(strcmp(a[one].name, a[two].name));
+} /* grp_entry_cmp */
-static void grp_quick_sort(GRPentry *a, PHYSFS_uint32 lo, PHYSFS_uint32 hi)
+static void grp_entry_swap(void *_a, PHYSFS_uint32 one, PHYSFS_uint32 two)
{
- PHYSFS_uint32 i;
- PHYSFS_uint32 j;
- GRPentry *v;
-
- if ((hi - lo) > GRP_QUICKSORT_THRESHOLD)
- {
- i = (hi + lo) / 2;
-
- if (strcmp(a[lo].name, a[i].name) > 0) grp_entry_swap(a, lo, i);
- if (strcmp(a[lo].name, a[hi].name) > 0) grp_entry_swap(a, lo, hi);
- if (strcmp(a[i].name, a[hi].name) > 0) grp_entry_swap(a, i, hi);
-
- j = hi - 1;
- grp_entry_swap(a, i, j);
- i = lo;
- v = &a[j];
- while (1)
- {
- while(strcmp(a[++i].name, v->name) < 0) {}
- while(strcmp(a[--j].name, v->name) > 0) {}
- if (j < i)
- break;
- grp_entry_swap(a, i, j);
- } /* while */
- grp_entry_swap(a, i, hi-1);
- grp_quick_sort(a, lo, j);
- grp_quick_sort(a, i+1, hi);
- } /* if */
-} /* grp_quick_sort */
-
-
-static void grp_insertion_sort(GRPentry *a, PHYSFS_uint32 lo, PHYSFS_uint32 hi)
-{
- PHYSFS_uint32 i;
- PHYSFS_uint32 j;
GRPentry tmp;
-
- for (i = lo + 1; i <= hi; i++)
- {
- memcpy(&tmp, &a[i], sizeof (GRPentry));
- j = i;
- while ((j > lo) && (strcmp(a[j - 1].name, tmp.name) > 0))
- {
- memcpy(&a[j], &a[j - 1], sizeof (GRPentry));
- j--;
- } /* while */
- memcpy(&a[j], &tmp, sizeof (GRPentry));
- } /* for */
-} /* grp_insertion_sort */
-
-
-static void grp_sort_entries(GRPentry *entries, PHYSFS_uint32 max)
-{
- /*
- * Fast Quicksort algorithm inspired by code from here:
- * http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
- */
- if (max <= GRP_QUICKSORT_THRESHOLD)
- grp_quick_sort(entries, 0, max - 1);
- grp_insertion_sort(entries, 0, max - 1);
-} /* grp_sort_entries */
+ GRPentry *first = &(((GRPentry *) _a)[one]);
+ GRPentry *second = &(((GRPentry *) _a)[two]);
+ memcpy(&tmp, first, sizeof (GRPentry));
+ memcpy(first, second, sizeof (GRPentry));
+ memcpy(second, &tmp, sizeof (GRPentry));
+} /* grp_entry_swap */
static int grp_load_entries(const char *name, int forWriting, GRPinfo *info)
@@ -376,7 +313,8 @@
__PHYSFS_platformClose(fh);
- grp_sort_entries(info->entries, info->entryCount);
+ __PHYSFS_sort(info->entries, info->entryCount,
+ grp_entry_cmp, grp_entry_swap);
return(1);
} /* grp_load_entries */
--- a/archivers/qpak.c Tue Aug 20 01:00:23 2002 +0000
+++ b/archivers/qpak.c Tue Aug 20 01:34:27 2002 +0000
@@ -183,32 +183,6 @@
} /* QPAK_isArchive */
-static void qpak_insertion_sort(QPAKentry *a, PHYSFS_uint32 lo, PHYSFS_uint32 hi)
-{
- PHYSFS_uint32 i;
- PHYSFS_uint32 j;
- QPAKentry tmp;
-
- for (i = lo + 1; i <= hi; i++)
- {
- memcpy(&tmp, &a[i], sizeof (QPAKentry));
- j = i;
- while ((j > lo) && (strcmp(a[j - 1].name, tmp.name) > 0))
- {
- memcpy(&a[j], &a[j - 1], sizeof (QPAKentry));
- j--;
- } /* while */
- memcpy(&a[j], &tmp, sizeof (QPAKentry));
- } /* for */
-} /* qpak_insertion_sort */
-
-
-static void qpak_sort_entries(QPAKentry *entries, PHYSFS_uint32 max)
-{
- qpak_insertion_sort(entries, 0, max - 1);
-} /* qpak_sort_entries */
-
-
static int qpak_loadEntries(void *fh, int dirOffset, int numEntries,
QPAKentry *entries)
{
@@ -436,7 +410,7 @@
} /* qpak_populateDirectories */
-static void qpak_deletePakInfo (QPAKinfo *pakInfo)
+static void qpak_deletePakInfo(QPAKinfo *pakInfo)
{
if (pakInfo->handle != NULL)
__PHYSFS_platformClose(pakInfo->handle);
@@ -453,6 +427,24 @@
} /* qpak_deletePakInfo */
+static int qpak_entry_cmp(void *_a, PHYSFS_uint32 one, PHYSFS_uint32 two)
+{
+ QPAKentry *a = (QPAKentry *) _a;
+ return(strcmp(a[one].name, a[two].name));
+} /* qpak_entry_cmp */
+
+
+static void qpak_entry_swap(void *_a, PHYSFS_uint32 one, PHYSFS_uint32 two)
+{
+ QPAKentry tmp;
+ QPAKentry *first = &(((QPAKentry *) _a)[one]);
+ QPAKentry *second = &(((QPAKentry *) _a)[two]);
+ memcpy(&tmp, first, sizeof (QPAKentry));
+ memcpy(first, second, sizeof (QPAKentry));
+ memcpy(second, &tmp, sizeof (QPAKentry));
+} /* qpak_entry_swap */
+
+
static DirHandle *QPAK_openArchive(const char *name, int forWriting)
{
void *fh = NULL;
@@ -506,7 +498,8 @@
if (qpak_loadEntries(fh, dirOffset, pi->totalEntries, pi->entries) == 0)
goto QPAK_openArchive_failed;
- qpak_sort_entries(pi->entries, pi->totalEntries);
+ __PHYSFS_sort(pi->entries, pi->totalEntries,
+ qpak_entry_cmp, qpak_entry_swap);
pi->root = qpak_newDirectory("");
if (pi->root == NULL)
--- a/archivers/zip.c Tue Aug 20 01:00:23 2002 +0000
+++ b/archivers/zip.c Tue Aug 20 01:34:27 2002 +0000
@@ -27,13 +27,6 @@
#include "physfs_internal.h"
/*
- * When sorting the zip entries in an archive, we use a modified QuickSort.
- * When there are less then ZIP_QUICKSORT_THRESHOLD entries left to sort,
- * we switch over to an InsertionSort for the remainder. Tweak to taste.
- */
-#define ZIP_QUICKSORT_THRESHOLD 4
-
-/*
* A buffer of ZIP_READBUFSIZE is malloc() for each compressed file opened,
* and is free()'d when you close the file; compressed data is read into
* this buffer, and then is decompressed into the buffer passed to
@@ -937,78 +930,22 @@
} /* zip_load_entry */
-static void zip_entry_swap(ZIPentry *a, PHYSFS_uint32 one, PHYSFS_uint32 two)
+static int zip_entry_cmp(void *_a, PHYSFS_uint32 one, PHYSFS_uint32 two)
{
- ZIPentry tmp;
- memcpy(&tmp, &a[one], sizeof (ZIPentry));
- memcpy(&a[one], &a[two], sizeof (ZIPentry));
- memcpy(&a[two], &tmp, sizeof (ZIPentry));
-} /* zip_entry_swap */
+ ZIPentry *a = (ZIPentry *) _a;
+ return(strcmp(a[one].name, a[two].name));
+} /* zip_entry_cmp */
-static void zip_quick_sort(ZIPentry *a, PHYSFS_uint32 lo, PHYSFS_uint32 hi)
+static void zip_entry_swap(void *_a, PHYSFS_uint32 one, PHYSFS_uint32 two)
{
- PHYSFS_uint32 i;
- PHYSFS_uint32 j;
- ZIPentry *v;
-
- if ((hi - lo) > ZIP_QUICKSORT_THRESHOLD)
- {
- i = (hi + lo) / 2;
-
- if (strcmp(a[lo].name, a[i].name) > 0) zip_entry_swap(a, lo, i);
- if (strcmp(a[lo].name, a[hi].name) > 0) zip_entry_swap(a, lo, hi);
- if (strcmp(a[i].name, a[hi].name) > 0) zip_entry_swap(a, i, hi);
-
- j = hi - 1;
- zip_entry_swap(a, i, j);
- i = lo;
- v = &a[j];
- while (1)
- {
- while(strcmp(a[++i].name, v->name) < 0) {}
- while(strcmp(a[--j].name, v->name) > 0) {}
- if (j < i)
- break;
- zip_entry_swap(a, i, j);
- } /* while */
- zip_entry_swap(a, i, hi-1);
- zip_quick_sort(a, lo, j);
- zip_quick_sort(a, i+1, hi);
- } /* if */
-} /* zip_quick_sort */
-
-
-static void zip_insertion_sort(ZIPentry *a, PHYSFS_uint32 lo, PHYSFS_uint32 hi)
-{
- PHYSFS_uint32 i;
- PHYSFS_uint32 j;
ZIPentry tmp;
-
- for (i = lo + 1; i <= hi; i++)
- {
- memcpy(&tmp, &a[i], sizeof (ZIPentry));
- j = i;
- while ((j > lo) && (strcmp(a[j - 1].name, tmp.name) > 0))
- {
- memcpy(&a[j], &a[j - 1], sizeof (ZIPentry));
- j--;
- } /* while */
- memcpy(&a[j], &tmp, sizeof (ZIPentry));
- } /* for */
-} /* zip_insertion_sort */
-
-
-static void zip_sort_entries(ZIPentry *entries, PHYSFS_uint32 max)
-{
- /*
- * Fast Quicksort algorithm inspired by code from here:
- * http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
- */
- if (max <= ZIP_QUICKSORT_THRESHOLD)
- zip_quick_sort(entries, 0, max - 1);
- zip_insertion_sort(entries, 0, max - 1);
-} /* zip_sort_entries */
+ ZIPentry *first = &(((ZIPentry *) _a)[one]);
+ ZIPentry *second = &(((ZIPentry *) _a)[two]);
+ memcpy(&tmp, first, sizeof (ZIPentry));
+ memcpy(first, second, sizeof (ZIPentry));
+ memcpy(second, &tmp, sizeof (ZIPentry));
+} /* zip_entry_swap */
static int zip_load_entries(void *in, DirHandle *dirh,
@@ -1032,7 +969,7 @@
} /* if */
} /* for */
- zip_sort_entries(info->entries, max);
+ __PHYSFS_sort(info->entries, max, zip_entry_cmp, zip_entry_swap);
return(1);
} /* zip_load_entries */
--- a/physfs_internal.h Tue Aug 20 01:00:23 2002 +0000
+++ b/physfs_internal.h Tue Aug 20 01:34:27 2002 +0000
@@ -700,7 +700,6 @@
/* end LANG section. */
-
struct __PHYSFS_DIRHANDLE__;
struct __PHYSFS_FILEFUNCTIONS__;
@@ -982,6 +981,30 @@
PHYSFS_sint32 len);
+/*
+ * When sorting the entries in an archive, we use a modified QuickSort.
+ * When there are less then PHYSFS_QUICKSORT_THRESHOLD entries left to sort,
+ * we switch over to a BubbleSort for the remainder. Tweak to taste.
+ *
+ * You can override this setting by defining PHYSFS_QUICKSORT_THRESHOLD
+ * before #including "physfs_internal.h".
+ */
+#ifndef PHYSFS_QUICKSORT_THRESHOLD
+#define PHYSFS_QUICKSORT_THRESHOLD 4
+#endif
+
+/*
+ * Sort an array (or whatever) of (max) elements. This uses a mixture of
+ * a QuickSort and BubbleSort internally.
+ * (cmpfn) is used to determine ordering, and (swapfn) does the actual
+ * swapping of elements in the list.
+ *
+ * See zip.c for an example.
+ */
+void __PHYSFS_sort(void *entries, PHYSFS_uint32 max,
+ int (*cmpfn)(void *, PHYSFS_uint32, PHYSFS_uint32),
+ void (*swapfn)(void *, PHYSFS_uint32, PHYSFS_uint32));
+
/* These get used all over for lessening code clutter. */
#define BAIL_MACRO(e, r) { __PHYSFS_setError(e); return r; }