archivers/grp.c
changeset 464 21c8e0d1578c
parent 427 c38ace41039f
child 467 99664d9842cb
equal deleted inserted replaced
463:98455f2c89c6 464:21c8e0d1578c
    38 #include <assert.h>
    38 #include <assert.h>
    39 #include "physfs.h"
    39 #include "physfs.h"
    40 
    40 
    41 #define __PHYSICSFS_INTERNAL__
    41 #define __PHYSICSFS_INTERNAL__
    42 #include "physfs_internal.h"
    42 #include "physfs_internal.h"
    43 
       
    44 /*
       
    45  * When sorting the grp entries in an archive, we use a modified QuickSort.
       
    46  *  When there are less then GRP_QUICKSORT_THRESHOLD entries left to sort,
       
    47  *  we switch over to an InsertionSort for the remainder. Tweak to taste.
       
    48  */
       
    49 #define GRP_QUICKSORT_THRESHOLD 4
       
    50 
    43 
    51 typedef struct
    44 typedef struct
    52 {
    45 {
    53     char name[13];
    46     char name[13];
    54     PHYSFS_uint64 startPos;
    47     PHYSFS_uint64 startPos;
   256 
   249 
   257     return(retval);
   250     return(retval);
   258 } /* GRP_isArchive */
   251 } /* GRP_isArchive */
   259 
   252 
   260 
   253 
   261 static void grp_entry_swap(GRPentry *a, PHYSFS_uint32 one, PHYSFS_uint32 two)
   254 static int grp_entry_cmp(void *_a, PHYSFS_uint32 one, PHYSFS_uint32 two)
       
   255 {
       
   256     GRPentry *a = (GRPentry *) _a;
       
   257     return(strcmp(a[one].name, a[two].name));
       
   258 } /* grp_entry_cmp */
       
   259 
       
   260 
       
   261 static void grp_entry_swap(void *_a, PHYSFS_uint32 one, PHYSFS_uint32 two)
   262 {
   262 {
   263     GRPentry tmp;
   263     GRPentry tmp;
   264     memcpy(&tmp, &a[one], sizeof (GRPentry));
   264     GRPentry *first = &(((GRPentry *) _a)[one]);
   265     memcpy(&a[one], &a[two], sizeof (GRPentry));
   265     GRPentry *second = &(((GRPentry *) _a)[two]);
   266     memcpy(&a[two], &tmp, sizeof (GRPentry));
   266     memcpy(&tmp, first, sizeof (GRPentry));
       
   267     memcpy(first, second, sizeof (GRPentry));
       
   268     memcpy(second, &tmp, sizeof (GRPentry));
   267 } /* grp_entry_swap */
   269 } /* grp_entry_swap */
   268 
       
   269 
       
   270 static void grp_quick_sort(GRPentry *a, PHYSFS_uint32 lo, PHYSFS_uint32 hi)
       
   271 {
       
   272     PHYSFS_uint32 i;
       
   273     PHYSFS_uint32 j;
       
   274     GRPentry *v;
       
   275 
       
   276 	if ((hi - lo) > GRP_QUICKSORT_THRESHOLD)
       
   277 	{
       
   278 		i = (hi + lo) / 2;
       
   279 
       
   280 		if (strcmp(a[lo].name, a[i].name) > 0) grp_entry_swap(a, lo, i);
       
   281 		if (strcmp(a[lo].name, a[hi].name) > 0) grp_entry_swap(a, lo, hi);
       
   282 		if (strcmp(a[i].name, a[hi].name) > 0) grp_entry_swap(a, i, hi);
       
   283 
       
   284 		j = hi - 1;
       
   285 		grp_entry_swap(a, i, j);
       
   286 		i = lo;
       
   287 		v = &a[j];
       
   288 		while (1)
       
   289 		{
       
   290 			while(strcmp(a[++i].name, v->name) < 0) {}
       
   291 			while(strcmp(a[--j].name, v->name) > 0) {}
       
   292 			if (j < i)
       
   293                 break;
       
   294 			grp_entry_swap(a, i, j);
       
   295 		} /* while */
       
   296 		grp_entry_swap(a, i, hi-1);
       
   297 		grp_quick_sort(a, lo, j);
       
   298 		grp_quick_sort(a, i+1, hi);
       
   299 	} /* if */
       
   300 } /* grp_quick_sort */
       
   301 
       
   302 
       
   303 static void grp_insertion_sort(GRPentry *a, PHYSFS_uint32 lo, PHYSFS_uint32 hi)
       
   304 {
       
   305     PHYSFS_uint32 i;
       
   306     PHYSFS_uint32 j;
       
   307     GRPentry tmp;
       
   308 
       
   309     for (i = lo + 1; i <= hi; i++)
       
   310     {
       
   311         memcpy(&tmp, &a[i], sizeof (GRPentry));
       
   312         j = i;
       
   313         while ((j > lo) && (strcmp(a[j - 1].name, tmp.name) > 0))
       
   314         {
       
   315             memcpy(&a[j], &a[j - 1], sizeof (GRPentry));
       
   316             j--;
       
   317         } /* while */
       
   318         memcpy(&a[j], &tmp, sizeof (GRPentry));
       
   319     } /* for */
       
   320 } /* grp_insertion_sort */
       
   321 
       
   322 
       
   323 static void grp_sort_entries(GRPentry *entries, PHYSFS_uint32 max)
       
   324 {
       
   325     /*
       
   326      * Fast Quicksort algorithm inspired by code from here:
       
   327      *   http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
       
   328      */
       
   329     if (max <= GRP_QUICKSORT_THRESHOLD)
       
   330         grp_quick_sort(entries, 0, max - 1);
       
   331 	grp_insertion_sort(entries, 0, max - 1);
       
   332 } /* grp_sort_entries */
       
   333 
   270 
   334 
   271 
   335 static int grp_load_entries(const char *name, int forWriting, GRPinfo *info)
   272 static int grp_load_entries(const char *name, int forWriting, GRPinfo *info)
   336 {
   273 {
   337     void *fh = NULL;
   274     void *fh = NULL;
   374         location += entry->size;
   311         location += entry->size;
   375     } /* for */
   312     } /* for */
   376 
   313 
   377     __PHYSFS_platformClose(fh);
   314     __PHYSFS_platformClose(fh);
   378 
   315 
   379     grp_sort_entries(info->entries, info->entryCount);
   316     __PHYSFS_sort(info->entries, info->entryCount,
       
   317                   grp_entry_cmp, grp_entry_swap);
   380     return(1);
   318     return(1);
   381 } /* grp_load_entries */
   319 } /* grp_load_entries */
   382 
   320 
   383 
   321 
   384 static DirHandle *GRP_openArchive(const char *name, int forWriting)
   322 static DirHandle *GRP_openArchive(const char *name, int forWriting)