Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
Generalized sorting routines, and removed individual implementations.
  • Loading branch information
icculus committed Aug 20, 2002
1 parent 69d56e9 commit 1e2372b
Show file tree
Hide file tree
Showing 4 changed files with 70 additions and 179 deletions.
88 changes: 13 additions & 75 deletions archivers/grp.c
Expand Up @@ -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];
Expand Down Expand Up @@ -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)
Expand Down Expand Up @@ -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 */

Expand Down
49 changes: 21 additions & 28 deletions archivers/qpak.c
Expand Up @@ -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)
{
Expand Down Expand Up @@ -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);
Expand All @@ -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;
Expand Down Expand Up @@ -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)
Expand Down
87 changes: 12 additions & 75 deletions archivers/zip.c
Expand Up @@ -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
Expand Down Expand Up @@ -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,
Expand All @@ -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 */

Expand Down
25 changes: 24 additions & 1 deletion physfs_internal.h
Expand Up @@ -700,7 +700,6 @@ extern "C" {

/* end LANG section. */


struct __PHYSFS_DIRHANDLE__;
struct __PHYSFS_FILEFUNCTIONS__;

Expand Down Expand Up @@ -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; }
Expand Down

0 comments on commit 1e2372b

Please sign in to comment.