physfs.c
changeset 462 83c60189bc21
parent 453 108de3bb1b6b
child 467 99664d9842cb
equal deleted inserted replaced
461:3340aee8ba50 462:83c60189bc21
     8  *  This file written by Ryan C. Gordon.
     8  *  This file written by Ryan C. Gordon.
     9  */
     9  */
    10 
    10 
    11 #if HAVE_CONFIG_H
    11 #if HAVE_CONFIG_H
    12 #  include <config.h>
    12 #  include <config.h>
       
    13 #endif
       
    14 
       
    15 #if (defined PHYSFS_PROFILING)
       
    16 #include <sys/time.h>
       
    17 #include <unistd.h>
    13 #endif
    18 #endif
    14 
    19 
    15 #include <stdio.h>
    20 #include <stdio.h>
    16 #include <stdlib.h>
    21 #include <stdlib.h>
    17 #include <string.h>
    22 #include <string.h>
   119 static void *stateLock = NULL;     /* protects other PhysFS static state. */
   124 static void *stateLock = NULL;     /* protects other PhysFS static state. */
   120 
   125 
   121 
   126 
   122 /* functions ... */
   127 /* functions ... */
   123 
   128 
       
   129 void __PHYSFS_bubble_sort(void *a, PHYSFS_uint32 lo, PHYSFS_uint32 hi,
       
   130                          int (*cmpfn)(void *, PHYSFS_uint32, PHYSFS_uint32),
       
   131                          void (*swapfn)(void *, PHYSFS_uint32, PHYSFS_uint32))
       
   132 {
       
   133     PHYSFS_uint32 i;
       
   134     int sorted;
       
   135 
       
   136     do
       
   137     {
       
   138         sorted = 1;
       
   139         for (i = lo; i < hi; i++)
       
   140         {
       
   141             if (cmpfn(a, i, i + 1) > 0)
       
   142             {
       
   143                 swapfn(a, i, i + 1);
       
   144                 sorted = 0;
       
   145             } /* if */
       
   146         } /* for */
       
   147     } while (!sorted);
       
   148 } /* __PHYSFS_bubble_sort */
       
   149 
       
   150 
       
   151 void __PHYSFS_quick_sort(void *a, PHYSFS_uint32 lo, PHYSFS_uint32 hi,
       
   152                          int (*cmpfn)(void *, PHYSFS_uint32, PHYSFS_uint32),
       
   153                          void (*swapfn)(void *, PHYSFS_uint32, PHYSFS_uint32))
       
   154 {
       
   155     PHYSFS_uint32 i;
       
   156     PHYSFS_uint32 j;
       
   157     PHYSFS_uint32 v;
       
   158 
       
   159 	if ((hi - lo) <= PHYSFS_QUICKSORT_THRESHOLD)
       
   160         __PHYSFS_bubble_sort(a, lo, hi, cmpfn, swapfn);
       
   161     else
       
   162 	{
       
   163 		i = (hi + lo) / 2;
       
   164 
       
   165         if (cmpfn(a, lo, i) > 0) swapfn(a, lo, i);
       
   166 		if (cmpfn(a, lo, hi) > 0) swapfn(a, lo, hi);
       
   167 		if (cmpfn(a, i, hi) > 0) swapfn(a, i, hi);
       
   168 
       
   169 		j = hi - 1;
       
   170 		swapfn(a, i, j);
       
   171 		i = lo;
       
   172 		v = j;
       
   173 		while (1)
       
   174 		{
       
   175 			while(cmpfn(a, ++i, v) < 0) { /* do nothing */ }
       
   176 			while(cmpfn(a, --j, v) > 0) { /* do nothing */ }
       
   177 			if (j < i)
       
   178                 break;
       
   179 			swapfn(a, i, j);
       
   180 		} /* while */
       
   181 		swapfn(a, i, hi-1);
       
   182 		__PHYSFS_quick_sort(a, lo, j, cmpfn, swapfn);
       
   183 		__PHYSFS_quick_sort(a, i+1, hi, cmpfn, swapfn);
       
   184 	} /* else */
       
   185 } /* __PHYSFS_quick_sort */
       
   186 
       
   187 
       
   188 void __PHYSFS_sort(void *entries, PHYSFS_uint32 max,
       
   189                    int (*cmpfn)(void *, PHYSFS_uint32, PHYSFS_uint32),
       
   190                    void (*swapfn)(void *, PHYSFS_uint32, PHYSFS_uint32))
       
   191 {
       
   192     /*
       
   193      * Quicksort w/ Bubblesort fallback algorithm inspired by code from here:
       
   194      *   http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
       
   195      */
       
   196     __PHYSFS_quick_sort(entries, 0, max - 1, cmpfn, swapfn);
       
   197 } /* __PHYSFS_sort */
       
   198 
       
   199 
       
   200 
       
   201 #if (defined PHYSFS_PROFILING)
       
   202 
       
   203 #define PHYSFS_TEST_SORT_ITERATIONS 150
       
   204 #define PHYSFS_TEST_SORT_ELEMENTS   (64 * 1024)
       
   205 
       
   206 static int __PHYSFS_test_sort_cmp(void *_a, PHYSFS_uint32 x, PHYSFS_uint32 y)
       
   207 {
       
   208     PHYSFS_sint32 *a = (PHYSFS_sint32 *) _a;
       
   209     PHYSFS_sint32 one = a[x];
       
   210     PHYSFS_sint32 two = a[y];
       
   211 
       
   212     if (one < two)
       
   213         return(-1);
       
   214     else if (one > two)
       
   215         return(1);
       
   216 
       
   217     return(0);
       
   218 } /* __PHYSFS_test_sort_cmp */
       
   219 
       
   220 
       
   221 static void __PHYSFS_test_sort_swap(void *_a, PHYSFS_uint32 x, PHYSFS_uint32 y)
       
   222 {
       
   223     PHYSFS_sint32 *a = (PHYSFS_sint32 *) _a;
       
   224     PHYSFS_sint32 tmp;
       
   225     tmp = a[x];
       
   226     a[x] = a[y];
       
   227     a[y] = tmp;
       
   228 } /* __PHYSFS_test_sort_swap */
       
   229 
       
   230 
       
   231 static int __PHYSFS_test_sort_do(PHYSFS_uint32 *timer,
       
   232                          PHYSFS_sint32 *a, PHYSFS_uint32 max,
       
   233                          int (*cmpfn)(void *, PHYSFS_uint32, PHYSFS_uint32),
       
   234                          void (*swapfn)(void *, PHYSFS_uint32, PHYSFS_uint32))
       
   235 {
       
   236     PHYSFS_uint32 i;
       
   237     struct timeval starttime, endtime;
       
   238 
       
   239     gettimeofday(&starttime, NULL);
       
   240     __PHYSFS_sort(a, max, cmpfn, swapfn);
       
   241     gettimeofday(&endtime, NULL);
       
   242 
       
   243     for (i = 1; i < max; i++)
       
   244     {
       
   245         if (a[i] < a[i - 1])
       
   246             return(0);
       
   247     } /* for */
       
   248 
       
   249     if (timer != NULL)
       
   250     {
       
   251         *timer = ( ((endtime.tv_sec  - starttime.tv_sec) * 1000) +
       
   252                    ((endtime.tv_usec - starttime.tv_usec) / 1000) );
       
   253     } /* if */
       
   254 
       
   255     return(1);
       
   256 } /* __PHYSFS_test_sort_time */
       
   257 
       
   258 
       
   259 static void __PHYSFS_test_sort(void)
       
   260 {
       
   261     PHYSFS_uint32 elasped[PHYSFS_TEST_SORT_ITERATIONS];
       
   262     PHYSFS_sint32 iter;
       
   263     PHYSFS_sint32 a[PHYSFS_TEST_SORT_ELEMENTS];
       
   264     PHYSFS_sint32 i, x;
       
   265     int success;
       
   266 
       
   267     printf("Testing __PHYSFS_sort (linear presorted) ... ");
       
   268     for (iter = 0; iter < PHYSFS_TEST_SORT_ITERATIONS; iter++)
       
   269     {
       
   270         /* set up array to sort. */
       
   271         for (i = 0; i < PHYSFS_TEST_SORT_ELEMENTS; i++)
       
   272             a[i] = i;
       
   273 
       
   274         /* sort it. */
       
   275         success = __PHYSFS_test_sort_do(&elasped[iter],
       
   276                                         a, PHYSFS_TEST_SORT_ELEMENTS,
       
   277                                         __PHYSFS_test_sort_cmp,
       
   278                                         __PHYSFS_test_sort_swap);
       
   279         if (!success)
       
   280             break;
       
   281     } /* for */
       
   282 
       
   283     if (!success)
       
   284         printf("Failed!\n");
       
   285     else
       
   286     {
       
   287         for (x = 0, iter = 0; iter < PHYSFS_TEST_SORT_ITERATIONS; iter++)
       
   288             x += elasped[iter];
       
   289 
       
   290         x /= PHYSFS_TEST_SORT_ITERATIONS;
       
   291         printf("Average run (%lu) ms.\n", (unsigned long) x);
       
   292     } /* else */
       
   293 
       
   294     printf("Testing __PHYSFS_sort (linear presorted reverse) ... ");
       
   295     for (iter = 0; iter < PHYSFS_TEST_SORT_ITERATIONS; iter++)
       
   296     {
       
   297         /* set up array to sort. */
       
   298         for (i = 0, x = PHYSFS_TEST_SORT_ELEMENTS;
       
   299              i < PHYSFS_TEST_SORT_ELEMENTS;
       
   300              i++, x--)
       
   301         {
       
   302             a[i] = x;
       
   303         } /* for */
       
   304 
       
   305         /* sort it. */
       
   306         success = __PHYSFS_test_sort_do(&elasped[iter],
       
   307                                         a, PHYSFS_TEST_SORT_ELEMENTS,
       
   308                                         __PHYSFS_test_sort_cmp,
       
   309                                         __PHYSFS_test_sort_swap);
       
   310         if (!success)
       
   311             break;
       
   312     } /* for */
       
   313 
       
   314     if (!success)
       
   315         printf("Failed!\n");
       
   316     else
       
   317     {
       
   318         for (x = 0, iter = 0; iter < PHYSFS_TEST_SORT_ITERATIONS; iter++)
       
   319             x += elasped[iter];
       
   320 
       
   321         x /= PHYSFS_TEST_SORT_ITERATIONS;
       
   322         printf("Average run (%lu) ms.\n", (unsigned long) x);
       
   323     } /* else */
       
   324 
       
   325 
       
   326     printf("Testing __PHYSFS_sort (randomized) ... ");
       
   327     for (iter = 0; iter < PHYSFS_TEST_SORT_ITERATIONS; iter++)
       
   328     {
       
   329         /* set up array to sort. */
       
   330         for (i = 0; i < PHYSFS_TEST_SORT_ELEMENTS; i++)
       
   331             a[i] = (PHYSFS_uint32) rand();
       
   332 
       
   333         /* sort it. */
       
   334         success = __PHYSFS_test_sort_do(&elasped[iter],
       
   335                                         a, PHYSFS_TEST_SORT_ELEMENTS,
       
   336                                         __PHYSFS_test_sort_cmp,
       
   337                                         __PHYSFS_test_sort_swap);
       
   338         if (!success)
       
   339             break;
       
   340     } /* for */
       
   341 
       
   342     if (!success)
       
   343         printf("Failed!\n");
       
   344     else
       
   345     {
       
   346         for (x = 0, iter = 0; iter < PHYSFS_TEST_SORT_ITERATIONS; iter++)
       
   347             x += elasped[iter];
       
   348 
       
   349         x /= PHYSFS_TEST_SORT_ITERATIONS;
       
   350         printf("Average run (%lu) ms.\n", (unsigned long) x);
       
   351     } /* else */
       
   352 
       
   353     printf("__PHYSFS_test_sort() complete.\n\n");
       
   354 } /* __PHYSFS_test_sort */
       
   355 #endif
       
   356 
       
   357 
   124 static ErrMsg *findErrorForCurrentThread(void)
   358 static ErrMsg *findErrorForCurrentThread(void)
   125 {
   359 {
   126     ErrMsg *i;
   360     ErrMsg *i;
   127     PHYSFS_uint64 tid;
   361     PHYSFS_uint64 tid;
   128 
   362 
   506 
   740 
   507     initialized = 1;
   741     initialized = 1;
   508 
   742 
   509     /* This makes sure that the error subsystem is initialized. */
   743     /* This makes sure that the error subsystem is initialized. */
   510     __PHYSFS_setError(PHYSFS_getLastError());
   744     __PHYSFS_setError(PHYSFS_getLastError());
       
   745 
       
   746 #if (defined PHYSFS_PROFILING)
       
   747     srand(time(NULL));
       
   748     setbuf(stdout, NULL);
       
   749     printf("\n");
       
   750     printf("********************************************************\n");
       
   751     printf("Warning! Profiling is built into this copy of PhysicsFS!\n");
       
   752     printf("********************************************************\n");
       
   753     printf("\n");
       
   754     printf("\n");
       
   755     __PHYSFS_test_sort();
       
   756 #endif
       
   757 
   511     return(1);
   758     return(1);
   512 } /* PHYSFS_init */
   759 } /* PHYSFS_init */
   513 
   760 
   514 
   761 
   515 /* MAKE SURE you hold stateLock before calling this! */
   762 /* MAKE SURE you hold stateLock before calling this! */
  1555     *prev = l;
  1802     *prev = l;
  1556     l->next = NULL;
  1803     l->next = NULL;
  1557     return(retval);
  1804     return(retval);
  1558 } /* __PHYSFS_addToLinkedStringList */
  1805 } /* __PHYSFS_addToLinkedStringList */
  1559 
  1806 
  1560 
       
  1561 
       
  1562 /* end of physfs.c ... */
  1807 /* end of physfs.c ... */
  1563 
  1808