LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

blocksort.c File Reference

#include "bzlib_private.h"

Include dependency graph for blocksort.c:

Go to the source code of this file.

Defines

#define fswap(zz1, zz2)   { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
#define fvswap(zzp1, zzp2, zzn)
#define fmin(a, b)   ((a) < (b)) ? (a) : (b)
#define fpush(lz, hz)
#define fpop(lz, hz)
#define FALLBACK_QSORT_SMALL_THRESH   10
#define FALLBACK_QSORT_STACK_SIZE   100
#define SET_BH(zz)   bhtab[(zz) >> 5] |= (1 << ((zz) & 31))
#define CLEAR_BH(zz)   bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))
#define ISSET_BH(zz)   (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))
#define WORD_BH(zz)   bhtab[(zz) >> 5]
#define UNALIGNED_BH(zz)   ((zz) & 0x01f)
#define mswap(zz1, zz2)   { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
#define mvswap(zzp1, zzp2, zzn)
#define mmin(a, b)   ((a) < (b)) ? (a) : (b)
#define mpush(lz, hz, dz)
#define mpop(lz, hz, dz)
#define mnextsize(az)   (nextHi[az]-nextLo[az])
#define mnextswap(az, bz)
#define MAIN_QSORT_SMALL_THRESH   20
#define MAIN_QSORT_DEPTH_THRESH   (BZ_N_RADIX + BZ_N_QSORT)
#define MAIN_QSORT_STACK_SIZE   100
#define BIGFREQ(b)   (ftab[((b)+1) << 8] - ftab[(b) << 8])
#define SETMASK   (1 << 21)
#define CLEARMASK   (~(SETMASK))

Functions

static __inline__ void fallbackSimpleSort (UInt32 *fmap, UInt32 *eclass, Int32 lo, Int32 hi)
static void fallbackQSort3 (UInt32 *fmap, UInt32 *eclass, Int32 loSt, Int32 hiSt)
static void fallbackSort (UInt32 *fmap, UInt32 *eclass, UInt32 *bhtab, Int32 nblock, Int32 verb)
static __inline__ Bool mainGtU (UInt32 i1, UInt32 i2, UChar *block, UInt16 *quadrant, UInt32 nblock, Int32 *budget)
static void mainSimpleSort (UInt32 *ptr, UChar *block, UInt16 *quadrant, Int32 nblock, Int32 lo, Int32 hi, Int32 d, Int32 *budget)
static __inline__ UChar mmed3 (UChar a, UChar b, UChar c)
static void mainQSort3 (UInt32 *ptr, UChar *block, UInt16 *quadrant, Int32 nblock, Int32 loSt, Int32 hiSt, Int32 dSt, Int32 *budget)
static void mainSort (UInt32 *ptr, UChar *block, UInt16 *quadrant, UInt32 *ftab, Int32 nblock, Int32 verb, Int32 *budget)
void BZ2_blockSort (EState *s)

Variables

static Int32 incs [14]


Define Documentation

#define BIGFREQ  )     (ftab[((b)+1) << 8] - ftab[(b) << 8])
 

Definition at line 793 of file blocksort.c.

Referenced by mainSort().

#define CLEAR_BH zz   )     bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))
 

Definition at line 253 of file blocksort.c.

Referenced by fallbackSort().

#define CLEARMASK   (~(SETMASK))
 

Definition at line 795 of file blocksort.c.

Referenced by mainSort().

#define FALLBACK_QSORT_SMALL_THRESH   10
 

Definition at line 135 of file blocksort.c.

Referenced by fallbackQSort3().

#define FALLBACK_QSORT_STACK_SIZE   100
 

Definition at line 136 of file blocksort.c.

Referenced by fallbackQSort3().

#define fmin a,
 )     ((a) < (b)) ? (a) : (b)
 

Definition at line 125 of file blocksort.c.

Referenced by fallbackQSort3().

#define fpop lz,
hz   ) 
 

Value:

{ sp--;              \
                      lz = stackLo[sp];  \
                      hz = stackHi[sp]; }

Definition at line 131 of file blocksort.c.

Referenced by fallbackQSort3().

#define fpush lz,
hz   ) 
 

Value:

{ stackLo[sp] = lz; \
                       stackHi[sp] = hz; \
                       sp++; }

Definition at line 127 of file blocksort.c.

Referenced by fallbackQSort3().

#define fswap zz1,
zz2   )     { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
 

Definition at line 110 of file blocksort.c.

Referenced by fallbackQSort3().

#define fvswap zzp1,
zzp2,
zzn   ) 
 

Value:

{                                     \
   Int32 yyp1 = (zzp1);               \
   Int32 yyp2 = (zzp2);               \
   Int32 yyn  = (zzn);                \
   while (yyn > 0) {                  \
      fswap(fmap[yyp1], fmap[yyp2]);  \
      yyp1++; yyp2++; yyn--;          \
   }                                  \
}

Definition at line 113 of file blocksort.c.

Referenced by fallbackQSort3().

#define ISSET_BH zz   )     (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))
 

Definition at line 254 of file blocksort.c.

Referenced by fallbackSort().

#define MAIN_QSORT_DEPTH_THRESH   (BZ_N_RADIX + BZ_N_QSORT)
 

Definition at line 664 of file blocksort.c.

Referenced by mainQSort3().

#define MAIN_QSORT_SMALL_THRESH   20
 

Definition at line 663 of file blocksort.c.

Referenced by mainQSort3().

#define MAIN_QSORT_STACK_SIZE   100
 

Definition at line 665 of file blocksort.c.

Referenced by mainQSort3().

#define mmin a,
 )     ((a) < (b)) ? (a) : (b)
 

Definition at line 641 of file blocksort.c.

Referenced by mainQSort3().

#define mnextsize az   )     (nextHi[az]-nextLo[az])
 

Definition at line 654 of file blocksort.c.

Referenced by mainQSort3().

#define mnextswap az,
bz   ) 
 

Value:

{ 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; }

Definition at line 656 of file blocksort.c.

Referenced by mainQSort3().

#define mpop lz,
hz,
dz   ) 
 

Value:

{ sp--;             \
                         lz = stackLo[sp]; \
                         hz = stackHi[sp]; \
                         dz = stackD [sp]; }

Definition at line 648 of file blocksort.c.

Referenced by mainQSort3().

#define mpush lz,
hz,
dz   ) 
 

Value:

{ stackLo[sp] = lz; \
                          stackHi[sp] = hz; \
                          stackD [sp] = dz; \
                          sp++; }

Definition at line 643 of file blocksort.c.

Referenced by mainQSort3().

#define mswap zz1,
zz2   )     { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
 

Definition at line 614 of file blocksort.c.

Referenced by mainQSort3().

#define mvswap zzp1,
zzp2,
zzn   ) 
 

Value:

{                                     \
   Int32 yyp1 = (zzp1);               \
   Int32 yyp2 = (zzp2);               \
   Int32 yyn  = (zzn);                \
   while (yyn > 0) {                  \
      mswap(ptr[yyp1], ptr[yyp2]);    \
      yyp1++; yyp2++; yyn--;          \
   }                                  \
}

Definition at line 617 of file blocksort.c.

Referenced by mainQSort3().

#define SET_BH zz   )     bhtab[(zz) >> 5] |= (1 << ((zz) & 31))
 

Definition at line 252 of file blocksort.c.

Referenced by fallbackSort().

#define SETMASK   (1 << 21)
 

Definition at line 794 of file blocksort.c.

Referenced by mainSort().

#define UNALIGNED_BH zz   )     ((zz) & 0x01f)
 

Definition at line 256 of file blocksort.c.

Referenced by fallbackSort().

#define WORD_BH zz   )     bhtab[(zz) >> 5]
 

Definition at line 255 of file blocksort.c.

Referenced by fallbackSort().


Function Documentation

void BZ2_blockSort EState s  ) 
 

Definition at line 1078 of file blocksort.c.

References EState::arr1, EState::arr2, AssertH, EState::block, BZ_N_OVERSHOOT, fallbackSort(), EState::ftab, mainSort(), EState::nblock, EState::origPtr, EState::ptr, EState::verbosity, VPrintf0, VPrintf3, and EState::workFactor.

Referenced by BZ2_compressBlock().

static void fallbackQSort3 UInt32 fmap,
UInt32 eclass,
Int32  loSt,
Int32  hiSt
[static]
 

Definition at line 140 of file blocksort.c.

References AssertD, AssertH, FALLBACK_QSORT_SMALL_THRESH, FALLBACK_QSORT_STACK_SIZE, fallbackSimpleSort(), fmin, fpop, fpush, fswap, fvswap, and r.

Referenced by fallbackSort().

static __inline__ void fallbackSimpleSort UInt32 fmap,
UInt32 eclass,
Int32  lo,
Int32  hi
[static]
 

Definition at line 79 of file blocksort.c.

Referenced by fallbackQSort3().

static void fallbackSort UInt32 fmap,
UInt32 eclass,
UInt32 bhtab,
Int32  nblock,
Int32  verb
[static]
 

Definition at line 259 of file blocksort.c.

References AssertH, CLEAR_BH, fallbackQSort3(), H, ISSET_BH, l, r, SET_BH, UNALIGNED_BH, VPrintf0, VPrintf1, and WORD_BH.

Referenced by BZ2_blockSort().

static __inline__ Bool mainGtU UInt32  i1,
UInt32  i2,
UChar block,
UInt16 quadrant,
UInt32  nblock,
Int32 budget
[static]
 

Definition at line 394 of file blocksort.c.

References AssertD, and False.

Referenced by mainSimpleSort().

static void mainQSort3 UInt32 ptr,
UChar block,
UInt16 quadrant,
Int32  nblock,
Int32  loSt,
Int32  hiSt,
Int32  dSt,
Int32 budget
[static]
 

Definition at line 668 of file blocksort.c.

References AssertD, AssertH, MAIN_QSORT_DEPTH_THRESH, MAIN_QSORT_SMALL_THRESH, MAIN_QSORT_STACK_SIZE, mainSimpleSort(), mmed3(), mmin, mnextsize, mnextswap, mpop, mpush, mswap, mvswap, and True.

Referenced by mainSort().

static void mainSimpleSort UInt32 ptr,
UChar block,
UInt16 quadrant,
Int32  nblock,
Int32  lo,
Int32  hi,
Int32  d,
Int32 budget
[static]
 

Definition at line 532 of file blocksort.c.

References incs, mainGtU(), and True.

Referenced by mainQSort3().

static void mainSort UInt32 ptr,
UChar block,
UInt16 quadrant,
UInt32 ftab,
Int32  nblock,
Int32  verb,
Int32 budget
[static]
 

Definition at line 798 of file blocksort.c.

References AssertH, BIGFREQ, BZ_N_OVERSHOOT, BZ_N_RADIX, CLEARMASK, False, mainQSort3(), SETMASK, True, VPrintf0, VPrintf3, and VPrintf4.

Referenced by BZ2_blockSort().

static __inline__ UChar mmed3 UChar  a,
UChar  b,
UChar  c
[static]
 

Definition at line 630 of file blocksort.c.

Referenced by mainQSort3().


Variable Documentation

Int32 incs[14] [static]
 

Initial value:

 { 1, 4, 13, 40, 121, 364, 1093, 3280,
                   9841, 29524, 88573, 265720,
                   797161, 2391484 }

Definition at line 527 of file blocksort.c.

Referenced by mainSimpleSort().