From 1e2372b44cddf8691d248dd6b0dc9de558a35afc Mon Sep 17 00:00:00 2001 From: "Ryan C. Gordon" Date: Tue, 20 Aug 2002 01:34:27 +0000 Subject: [PATCH] Generalized sorting routines, and removed individual implementations. --- archivers/grp.c | 88 +++++++---------------------------------------- archivers/qpak.c | 49 +++++++++++--------------- archivers/zip.c | 87 +++++++--------------------------------------- physfs_internal.h | 25 +++++++++++++- 4 files changed, 70 insertions(+), 179 deletions(-) diff --git a/archivers/grp.c b/archivers/grp.c index 4746c085..5d235af7 100644 --- a/archivers/grp.c +++ b/archivers/grp.c @@ -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 @@ static int GRP_isArchive(const char *filename, int forWriting) } /* 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 @@ static int grp_load_entries(const char *name, int forWriting, GRPinfo *info) __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 */ diff --git a/archivers/qpak.c b/archivers/qpak.c index a9950478..f7b72c36 100644 --- a/archivers/qpak.c +++ b/archivers/qpak.c @@ -183,32 +183,6 @@ static int QPAK_isArchive(const char *filename, int forWriting) } /* 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 @@ static int qpak_populateDirectories(QPAKentry *entries, int numEntries, } /* 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 @@ static void qpak_deletePakInfo (QPAKinfo *pakInfo) } /* 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 @@ static DirHandle *QPAK_openArchive(const char *name, int forWriting) 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) diff --git a/archivers/zip.c b/archivers/zip.c index dd9abd32..42f796a4 100644 --- a/archivers/zip.c +++ b/archivers/zip.c @@ -26,13 +26,6 @@ #define __PHYSICSFS_INTERNAL__ #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 @@ -937,78 +930,22 @@ static int zip_load_entry(void *in, ZIPentry *entry, PHYSFS_uint32 ofs_fixup) } /* 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 @@ static int zip_load_entries(void *in, DirHandle *dirh, } /* if */ } /* for */ - zip_sort_entries(info->entries, max); + __PHYSFS_sort(info->entries, max, zip_entry_cmp, zip_entry_swap); return(1); } /* zip_load_entries */ diff --git a/physfs_internal.h b/physfs_internal.h index de5f965e..84f531bc 100644 --- a/physfs_internal.h +++ b/physfs_internal.h @@ -700,7 +700,6 @@ extern "C" { /* end LANG section. */ - struct __PHYSFS_DIRHANDLE__; struct __PHYSFS_FILEFUNCTIONS__; @@ -982,6 +981,30 @@ LinkedStringList *__PHYSFS_addToLinkedStringList(LinkedStringList *retval, 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; }