Stop force-inlining everything marked 'inline'

[wimlib] / src / divsufsort.c

diff --git a/src/divsufsort.c b/src/divsufsort.c
index 6353a9583518b62a7bc32238bacfcf40b5d49b0f..c80412f5cad1f9f18478b3e4327b8fd431642d2c 100644 (file)
--- a/src/divsufsort.c
+++ b/src/divsufsort.c
@@ -24,39 +24,24 @@
  * OTHER DEALINGS IN THE SOFTWARE.
  */
 
-#define assert(x)
+#ifdef HAVE_CONFIG_H
+#  include "config.h"
+#endif
 
 #include "wimlib/divsufsort.h"
-#include <stddef.h>
+#include "wimlib/util.h"
+
+#define DIVSUFSORT_ASSERT(expr)
 
 /*- Constants -*/
-#if defined(ALPHABET_SIZE) && (ALPHABET_SIZE < 1)
-# undef ALPHABET_SIZE
-#endif
-#if !defined(ALPHABET_SIZE)
-# define ALPHABET_SIZE (256)
-#endif
+#define ALPHABET_SIZE 256
 #define BUCKET_A_SIZE (ALPHABET_SIZE)
 #define BUCKET_B_SIZE (ALPHABET_SIZE * ALPHABET_SIZE)
-#if defined(SS_INSERTIONSORT_THRESHOLD)
-# if SS_INSERTIONSORT_THRESHOLD < 1
-#  undef SS_INSERTIONSORT_THRESHOLD
-#  define SS_INSERTIONSORT_THRESHOLD (1)
-# endif
-#else
-# define SS_INSERTIONSORT_THRESHOLD (8)
-#endif
-#if defined(SS_BLOCKSIZE)
-# if SS_BLOCKSIZE < 0
-#  undef SS_BLOCKSIZE
-#  define SS_BLOCKSIZE (0)
-# elif 32768 <= SS_BLOCKSIZE
-#  undef SS_BLOCKSIZE
-#  define SS_BLOCKSIZE (32767)
-# endif
-#else
-# define SS_BLOCKSIZE (1024)
-#endif
+
+#define SS_INSERTIONSORT_THRESHOLD 8
+
+#define SS_BLOCKSIZE 1024
+
 /* minstacksize = log(SS_BLOCKSIZE) / log(3) * 2 */
 #if SS_BLOCKSIZE == 0
 # define SS_MISORT_STACKSIZE (96)
@@ -71,37 +56,32 @@
 
 
 /*- Macros -*/
-#ifndef SWAP
-# define SWAP(_a, _b) do { t = (_a); (_a) = (_b); (_b) = t; } while(0)
-#endif /* SWAP */
-#ifndef MIN
-# define MIN(_a, _b) (((_a) < (_b)) ? (_a) : (_b))
-#endif /* MIN */
-#ifndef MAX
-# define MAX(_a, _b) (((_a) > (_b)) ? (_a) : (_b))
-#endif /* MAX */
+#define SWAP swap
+#define MIN min
+#define MAX max
+
 #define STACK_PUSH(_a, _b, _c, _d)\
   do {\
-    assert(ssize < STACK_SIZE);\
+    DIVSUFSORT_ASSERT(ssize < STACK_SIZE);\
     stack[ssize].a = (_a), stack[ssize].b = (_b),\
     stack[ssize].c = (_c), stack[ssize++].d = (_d);\
   } while(0)
 #define STACK_PUSH5(_a, _b, _c, _d, _e)\
   do {\
-    assert(ssize < STACK_SIZE);\
+    DIVSUFSORT_ASSERT(ssize < STACK_SIZE);\
     stack[ssize].a = (_a), stack[ssize].b = (_b),\
     stack[ssize].c = (_c), stack[ssize].d = (_d), stack[ssize++].e = (_e);\
   } while(0)
 #define STACK_POP(_a, _b, _c, _d)\
   do {\
-    assert(0 <= ssize);\
+    DIVSUFSORT_ASSERT(0 <= ssize);\
     if(ssize == 0) { return; }\
     (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\
     (_c) = stack[ssize].c, (_d) = stack[ssize].d;\
   } while(0)
 #define STACK_POP5(_a, _b, _c, _d, _e)\
   do {\
-    assert(0 <= ssize);\
+    DIVSUFSORT_ASSERT(0 <= ssize);\
     if(ssize == 0) { return; }\
     (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\
     (_c) = stack[ssize].c, (_d) = stack[ssize].d, (_e) = stack[ssize].e;\
@@ -131,7 +111,7 @@ static const int lg_table[256]= {
 
 #if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)
 
-static inline
+static forceinline
 int
 ss_ilg(int n) {
 #if SS_BLOCKSIZE == 0
@@ -174,7 +154,7 @@ static const int sqq_table[256] = {
 247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253, 253, 254, 254, 255
 };
 
-static inline
+static forceinline
 int
 ss_isqrt(int x) {
   int y, e;
@@ -207,7 +187,7 @@ ss_isqrt(int x) {
 /*---------------------------------------------------------------------------*/
 
 /* Compares two suffixes. */
-static inline
+static forceinline
 int
 ss_compare(const unsigned char *T,
            const int *p1, const int *p2,
@@ -258,7 +238,7 @@ ss_insertionsort(const unsigned char *T, const int *PA,
 
 #if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)
 
-static inline
+static forceinline
 void
 ss_fixdown(const unsigned char *Td, const int *PA,
            int *SA, int i, int size) {
@@ -300,11 +280,10 @@ ss_heapsort(const unsigned char *Td, const int *PA, int *SA, int size) {
 /*---------------------------------------------------------------------------*/
 
 /* Returns the median of three elements. */
-static inline
+static forceinline
 int *
 ss_median3(const unsigned char *Td, const int *PA,
            int *v1, int *v2, int *v3) {
-  int *t;
   if(Td[PA[*v1]] > Td[PA[*v2]]) { SWAP(v1, v2); }
   if(Td[PA[*v2]] > Td[PA[*v3]]) {
     if(Td[PA[*v1]] > Td[PA[*v3]]) { return v1; }
@@ -314,11 +293,10 @@ ss_median3(const unsigned char *Td, const int *PA,
 }
 
 /* Returns the median of five elements. */
-static inline
+static forceinline
 int *
 ss_median5(const unsigned char *Td, const int *PA,
            int *v1, int *v2, int *v3, int *v4, int *v5) {
-  int *t;
   if(Td[PA[*v2]] > Td[PA[*v3]]) { SWAP(v2, v3); }
   if(Td[PA[*v4]] > Td[PA[*v5]]) { SWAP(v4, v5); }
   if(Td[PA[*v2]] > Td[PA[*v4]]) { SWAP(v2, v4); SWAP(v3, v5); }
@@ -329,7 +307,7 @@ ss_median5(const unsigned char *Td, const int *PA,
 }
 
 /* Returns the pivot element. */
-static inline
+static forceinline
 int *
 ss_pivot(const unsigned char *Td, const int *PA, int *first, int *last) {
   int *middle;
@@ -357,7 +335,7 @@ ss_pivot(const unsigned char *Td, const int *PA, int *first, int *last) {
 /*---------------------------------------------------------------------------*/
 
 /* Binary partition for substrings. */
-static inline
+static forceinline
 int *
 ss_partition(const int *PA,
                     int *first, int *last, int depth) {
@@ -518,7 +496,7 @@ ss_mintrosort(const unsigned char *T, const int *PA,
 
 #if SS_BLOCKSIZE != 0
 
-static inline
+static forceinline
 void
 ss_blockswap(int *a, int *b, int n) {
   int t;
@@ -527,7 +505,7 @@ ss_blockswap(int *a, int *b, int n) {
   }
 }
 
-static inline
+static forceinline
 void
 ss_rotate(int *first, int *middle, int *last) {
   int *a, *b, t;
@@ -887,7 +865,7 @@ sssort(const unsigned char *T, const int *PA,
 
 /*---------------------------------------------------------------------------*/
 
-static inline
+static forceinline
 int
 tr_ilg(int n) {
   return (n & 0xffff0000) ?
@@ -922,7 +900,7 @@ tr_insertionsort(const int *ISAd, int *first, int *last) {
 
 /*---------------------------------------------------------------------------*/
 
-static inline
+static forceinline
 void
 tr_fixdown(const int *ISAd, int *SA, int i, int size) {
   int j, k;
@@ -963,10 +941,9 @@ tr_heapsort(const int *ISAd, int *SA, int size) {
 /*---------------------------------------------------------------------------*/
 
 /* Returns the median of three elements. */
-static inline
+static forceinline
 int *
 tr_median3(const int *ISAd, int *v1, int *v2, int *v3) {
-  int *t;
   if(ISAd[*v1] > ISAd[*v2]) { SWAP(v1, v2); }
   if(ISAd[*v2] > ISAd[*v3]) {
     if(ISAd[*v1] > ISAd[*v3]) { return v1; }
@@ -976,11 +953,10 @@ tr_median3(const int *ISAd, int *v1, int *v2, int *v3) {
 }
 
 /* Returns the median of five elements. */
-static inline
+static forceinline
 int *
 tr_median5(const int *ISAd,
            int *v1, int *v2, int *v3, int *v4, int *v5) {
-  int *t;
   if(ISAd[*v2] > ISAd[*v3]) { SWAP(v2, v3); }
   if(ISAd[*v4] > ISAd[*v5]) { SWAP(v4, v5); }
   if(ISAd[*v2] > ISAd[*v4]) { SWAP(v2, v4); SWAP(v3, v5); }
@@ -991,7 +967,7 @@ tr_median5(const int *ISAd,
 }
 
 /* Returns the pivot element. */
-static inline
+static forceinline
 int *
 tr_pivot(const int *ISAd, int *first, int *last) {
   int *middle;
@@ -1026,14 +1002,14 @@ struct _trbudget_t {
   int count;
 };
 
-static inline
+static forceinline
 void
 trbudget_init(trbudget_t *budget, int chance, int incval) {
   budget->chance = chance;
   budget->remain = budget->incval = incval;
 }
 
-static inline
+static forceinline
 int
 trbudget_check(trbudget_t *budget, int size) {
   if(size <= budget->remain) { budget->remain -= size; return 1; }
@@ -1046,7 +1022,7 @@ trbudget_check(trbudget_t *budget, int size) {
 
 /*---------------------------------------------------------------------------*/
 
-static inline
+static forceinline
 void
 tr_partition(const int *ISAd,
              int *first, int *middle, int *last,
@@ -1159,7 +1135,6 @@ tr_introsort(int *ISA, const int *ISAd,
 #define STACK_SIZE TR_STACKSIZE
   struct { const int *a; int *b, *c; int d, e; }stack[STACK_SIZE];
   int *a, *b, *c;
-  int t;
   int v, x = 0;
   int incr = ISAd - ISA;
   int limit, next;
@@ -1554,9 +1529,9 @@ construct_SA(const unsigned char *T, int *SA,
           i <= j;
           --j) {
         if(0 < (s = *j)) {
-          assert(T[s] == c1);
-          assert(((s + 1) < n) && (T[s] <= T[s + 1]));
-          assert(T[s - 1] <= T[s]);
+          DIVSUFSORT_ASSERT(T[s] == c1);
+          DIVSUFSORT_ASSERT(((s + 1) < n) && (T[s] <= T[s + 1]));
+          DIVSUFSORT_ASSERT(T[s - 1] <= T[s]);
           *j = ~s;
           c0 = T[--s];
           if((0 < s) && (T[s - 1] > c0)) { s = ~s; }
@@ -1564,10 +1539,10 @@ construct_SA(const unsigned char *T, int *SA,
             if(0 <= c2) { BUCKET_B(c2, c1) = k - SA; }
             k = SA + BUCKET_B(c2 = c0, c1);
           }
-          assert(k < j);
+          DIVSUFSORT_ASSERT(k < j);
           *k-- = s;
         } else {
-          assert(((s == 0) && (T[s] == c1)) || (s < 0));
+          DIVSUFSORT_ASSERT(((s == 0) && (T[s] == c1)) || (s < 0));
           *j = ~s;
         }
       }
@@ -1581,17 +1556,17 @@ construct_SA(const unsigned char *T, int *SA,
   /* Scan the suffix array from left to right. */
   for(i = SA, j = SA + n; i < j; ++i) {
     if(0 < (s = *i)) {
-      assert(T[s - 1] >= T[s]);
+      DIVSUFSORT_ASSERT(T[s - 1] >= T[s]);
       c0 = T[--s];
       if((s == 0) || (T[s - 1] < c0)) { s = ~s; }
       if(c0 != c2) {
         BUCKET_A(c2) = k - SA;
         k = SA + BUCKET_A(c2 = c0);
       }
-      assert(i < k);
+      DIVSUFSORT_ASSERT(i < k);
       *k++ = s;
     } else {
-      assert(s < 0);
+      DIVSUFSORT_ASSERT(s < 0);
       *i = ~s;
     }
   }
@@ -1604,10 +1579,11 @@ construct_SA(const unsigned char *T, int *SA,
 /* XXX Modified from original: use provided temporary space instead of
  * allocating it.  */
 void
-divsufsort(const unsigned char *T, int *SA, int n,
-          int *bucket_A, int *bucket_B)
+divsufsort(const u8 *T, u32 *SA, u32 n, u32 *tmp)
 {
-  int m;
+  u32 *bucket_A = tmp;
+  u32 *bucket_B = tmp + BUCKET_A_SIZE;
+  u32 m;
 
   switch (n) {
     case 0: