LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages
llvm » lib » Support » bzip2

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 (  b   )     (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,
b   )     ((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,
b   )     ((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().

Generated on Thu Jun 16 18:23:03 2005 for LLVM by doxygen 1.4.3-20050530
Copyright © 2003,2004 University of Illinois at Urbana-Champaign. All Rights Reserved.