#undef     ISSET_BH#undef      WORD_BH#undef UNALIGNED_BH/*---------------------------------------------*//*--- The main, O(N^2 log(N)) sorting       ---*//*--- algorithm.  Faster for "normal"       ---*//*--- non-repetitive blocks.                ---*//*---------------------------------------------*//*---------------------------------------------*/static__inline__Bool mainGtU ( UInt32  i1,                UInt32  i2,               UChar*  block,                UInt16* quadrant,               UInt32  nblock,               Int32*  budget ){   Int32  k;   UChar  c1, c2;   UInt16 s1, s2;   AssertD ( i1 != i2, "mainGtU" );   /* 1 */   c1 = block[i1]; c2 = block[i2];   if (c1 != c2) return (c1 > c2);   i1++; i2++;   /* 2 */   c1 = block[i1]; c2 = block[i2];   if (c1 != c2) return (c1 > c2);   i1++; i2++;   /* 3 */   c1 = block[i1]; c2 = block[i2];   if (c1 != c2) return (c1 > c2);   i1++; i2++;   /* 4 */   c1 = block[i1]; c2 = block[i2];   if (c1 != c2) return (c1 > c2);   i1++; i2++;   /* 5 */   c1 = block[i1]; c2 = block[i2];   if (c1 != c2) return (c1 > c2);   i1++; i2++;   /* 6 */   c1 = block[i1]; c2 = block[i2];   if (c1 != c2) return (c1 > c2);   i1++; i2++;   /* 7 */   c1 = block[i1]; c2 = block[i2];   if (c1 != c2) return (c1 > c2);   i1++; i2++;   /* 8 */   c1 = block[i1]; c2 = block[i2];   if (c1 != c2) return (c1 > c2);   i1++; i2++;   /* 9 */   c1 = block[i1]; c2 = block[i2];   if (c1 != c2) return (c1 > c2);   i1++; i2++;   /* 10 */   c1 = block[i1]; c2 = block[i2];   if (c1 != c2) return (c1 > c2);   i1++; i2++;   /* 11 */   c1 = block[i1]; c2 = block[i2];   if (c1 != c2) return (c1 > c2);   i1++; i2++;   /* 12 */   c1 = block[i1]; c2 = block[i2];   if (c1 != c2) return (c1 > c2);   i1++; i2++;   k = nblock + 8;   do {      /* 1 */      c1 = block[i1]; c2 = block[i2];      if (c1 != c2) return (c1 > c2);      s1 = quadrant[i1]; s2 = quadrant[i2];      if (s1 != s2) return (s1 > s2);      i1++; i2++;      /* 2 */      c1 = block[i1]; c2 = block[i2];      if (c1 != c2) return (c1 > c2);      s1 = quadrant[i1]; s2 = quadrant[i2];      if (s1 != s2) return (s1 > s2);      i1++; i2++;      /* 3 */      c1 = block[i1]; c2 = block[i2];      if (c1 != c2) return (c1 > c2);      s1 = quadrant[i1]; s2 = quadrant[i2];      if (s1 != s2) return (s1 > s2);      i1++; i2++;      /* 4 */      c1 = block[i1]; c2 = block[i2];      if (c1 != c2) return (c1 > c2);      s1 = quadrant[i1]; s2 = quadrant[i2];      if (s1 != s2) return (s1 > s2);      i1++; i2++;      /* 5 */      c1 = block[i1]; c2 = block[i2];      if (c1 != c2) return (c1 > c2);      s1 = quadrant[i1]; s2 = quadrant[i2];      if (s1 != s2) return (s1 > s2);      i1++; i2++;      /* 6 */      c1 = block[i1]; c2 = block[i2];      if (c1 != c2) return (c1 > c2);      s1 = quadrant[i1]; s2 = quadrant[i2];      if (s1 != s2) return (s1 > s2);      i1++; i2++;      /* 7 */      c1 = block[i1]; c2 = block[i2];      if (c1 != c2) return (c1 > c2);      s1 = quadrant[i1]; s2 = quadrant[i2];      if (s1 != s2) return (s1 > s2);      i1++; i2++;      /* 8 */      c1 = block[i1]; c2 = block[i2];      if (c1 != c2) return (c1 > c2);      s1 = quadrant[i1]; s2 = quadrant[i2];      if (s1 != s2) return (s1 > s2);      i1++; i2++;      if (i1 >= nblock) i1 -= nblock;      if (i2 >= nblock) i2 -= nblock;      k -= 8;      (*budget)--;   }      while (k >= 0);   return False;}/*---------------------------------------------*//*--   Knuth's increments seem to work better   than Incerpi-Sedgewick here.  Possibly   because the number of elems to sort is   usually small, typically <= 20.--*/staticInt32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,                   9841, 29524, 88573, 265720,                   797161, 2391484 };staticvoid mainSimpleSort ( UInt32* ptr,                      UChar*  block,                      UInt16* quadrant,                      Int32   nblock,                      Int32   lo,                       Int32   hi,                       Int32   d,                      Int32*  budget ){   Int32 i, j, h, bigN, hp;   UInt32 v;   bigN = hi - lo + 1;   if (bigN < 2) return;   hp = 0;   while (incs[hp] < bigN) hp++;   hp--;   for (; hp >= 0; hp--) {      h = incs[hp];      i = lo + h;      while (True) {         /*-- copy 1 --*/         if (i > hi) break;         v = ptr[i];         j = i;         while ( mainGtU (                     ptr[j-h]+d, v+d, block, quadrant, nblock, budget                  ) ) {            ptr[j] = ptr[j-h];            j = j - h;            if (j <= (lo + h - 1)) break;         }         ptr[j] = v;         i++;         /*-- copy 2 --*/         if (i > hi) break;         v = ptr[i];         j = i;         while ( mainGtU (                     ptr[j-h]+d, v+d, block, quadrant, nblock, budget                  ) ) {            ptr[j] = ptr[j-h];            j = j - h;            if (j <= (lo + h - 1)) break;         }         ptr[j] = v;         i++;         /*-- copy 3 --*/         if (i > hi) break;         v = ptr[i];         j = i;         while ( mainGtU (                     ptr[j-h]+d, v+d, block, quadrant, nblock, budget                  ) ) {            ptr[j] = ptr[j-h];            j = j - h;            if (j <= (lo + h - 1)) break;         }         ptr[j] = v;         i++;         if (*budget < 0) return;      }   }}/*---------------------------------------------*//*--   The following is an implementation of   an elegant 3-way quicksort for strings,   described in a paper "Fast Algorithms for   Sorting and Searching Strings", by Robert   Sedgewick and Jon L. Bentley.--*/#define mswap(zz1, zz2) \   { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }#define mvswap(zzp1, zzp2, zzn)       \{                                     \   Int32 yyp1 = (zzp1);               \   Int32 yyp2 = (zzp2);               \   Int32 yyn  = (zzn);                \   while (yyn > 0) {                  \      mswap(ptr[yyp1], ptr[yyp2]);    \      yyp1++; yyp2++; yyn--;          \   }                                  \}static __inline__UChar mmed3 ( UChar a, UChar b, UChar c ){   UChar t;   if (a > b) { t = a; a = b; b = t; };   if (b > c) {       b = c;      if (a > b) b = a;   }   return b;}#define mmin(a,b) ((a) < (b)) ? (a) : (b)#define mpush(lz,hz,dz) { stackLo[sp] = lz; \                          stackHi[sp] = hz; \                          stackD [sp] = dz; \                          sp++; }#define mpop(lz,hz,dz) { sp--;             \                         lz = stackLo[sp]; \                         hz = stackHi[sp]; \                         dz = stackD [sp]; }#define mnextsize(az) (nextHi[az]-nextLo[az])#define mnextswap(az,bz)                                        \   { Int32 tz;                                                  \     tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \     tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \     tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; }#define MAIN_QSORT_SMALL_THRESH 20#define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT)#define MAIN_QSORT_STACK_SIZE 100staticvoid mainQSort3 ( UInt32* ptr,                  UChar*  block,                  UInt16* quadrant,                  Int32   nblock,                  Int32   loSt,                   Int32   hiSt,                   Int32   dSt,                  Int32*  budget ){   Int32 unLo, unHi, ltLo, gtHi, n, m, med;   Int32 sp, lo, hi, d;   Int32 stackLo[MAIN_QSORT_STACK_SIZE];   Int32 stackHi[MAIN_QSORT_STACK_SIZE];   Int32 stackD [MAIN_QSORT_STACK_SIZE];   Int32 nextLo[3];   Int32 nextHi[3];   Int32 nextD [3];   sp = 0;   mpush ( loSt, hiSt, dSt );   while (sp > 0) {      AssertH ( sp < MAIN_QSORT_STACK_SIZE, 1001 );      mpop ( lo, hi, d );      if (hi - lo < MAIN_QSORT_SMALL_THRESH ||           d > MAIN_QSORT_DEPTH_THRESH) {         mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget );         if (*budget < 0) return;         continue;      }      med = (Int32)             mmed3 ( block[ptr[ lo         ]+d],                    block[ptr[ hi         ]+d],                    block[ptr[ (lo+hi)>>1 ]+d] );      unLo = ltLo = lo;      unHi = gtHi = hi;      while (True) {         while (True) {            if (unLo > unHi) break;            n = ((Int32)block[ptr[unLo]+d]) - med;            if (n == 0) {                mswap(ptr[unLo], ptr[ltLo]);                ltLo++; unLo++; continue;             };            if (n >  0) break;            unLo++;         }         while (True) {            if (unLo > unHi) break;            n = ((Int32)block[ptr[unHi]+d]) - med;            if (n == 0) {                mswap(ptr[unHi], ptr[gtHi]);                gtHi--; unHi--; continue;             };            if (n <  0) break;            unHi--;         }         if (unLo > unHi) break;         mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--;      }      AssertD ( unHi == unLo-1, "mainQSort3(2)" );      if (gtHi < ltLo) {         mpush(lo, hi, d+1 );         continue;      }      n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n);      m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m);      n = lo + unLo - ltLo - 1;      m = hi - (gtHi - unHi) + 1;      nextLo[0] = lo;  nextHi[0] = n;   nextD[0] = d;      nextLo[1] = m;   nextHi[1] = hi;  nextD[1] = d;      nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;      if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);      if (mnextsize(1) < mnextsize(2)) mnextswap(1,2);      if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);      AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" );      AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" );