A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from http://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/blocksort_8c_source.html below:

NCBI C++ ToolKit: src/util/compress/bzip2/blocksort.c Source File

40  if

(lo == hi)

return

;

43  for

(

i

= hi-4;

i

>= lo;

i

-- ) {

45

ec_tmp = eclass[

tmp

];

46  for

( j =

i

+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 )

52  for

(

i

= hi-1;

i

>= lo;

i

-- ) {

54

ec_tmp = eclass[

tmp

];

55  for

( j =

i

+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ )

63 #define fswap(zz1, zz2) \ 64  { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; } 66 #define fvswap(zzp1, zzp2, zzn) \ 68  Int32 yyp1 = (zzp1); \ 69  Int32 yyp2 = (zzp2); \ 72  fswap(fmap[yyp1], fmap[yyp2]); \ 73  yyp1++; yyp2++; yyn--; \ 78 #define fmin(a,b) ((a) < (b)) ? (a) : (b) 80 #define fpush(lz,hz) { stackLo[sp] = lz; \ 84 #define fpop(lz,hz) { sp--; \ 88 #define FALLBACK_QSORT_SMALL_THRESH 10 89 #define FALLBACK_QSORT_STACK_SIZE 100 98  Int32

unLo, unHi, ltLo, gtHi,

n

, m;

107  fpush

( loSt, hiSt );

126  r

= ((

r

* 7621) + 1) % 32768;

128  if

(

r3

== 0) med = eclass[fmap[lo]];

else 129  if

(

r3

== 1) med = eclass[fmap[(lo+hi)>>1]];

else 130

med = eclass[fmap[hi]];

137  if

(unLo > unHi)

break

;

140  fswap

(fmap[unLo], fmap[ltLo]);

148  if

(unLo > unHi)

break

;

151  fswap

(fmap[unHi], fmap[gtHi]);

158  if

(unLo > unHi)

break

;

159  fswap

(fmap[unLo], fmap[unHi]); unLo++; unHi--;

162  AssertD

( unHi == unLo-1,

"fallbackQSort3(2)"

);

164  if

(gtHi < ltLo)

continue

;

167

m =

fmin

(hi-gtHi, gtHi-unHi);

fvswap

(unLo, hi-m+1, m);

169  n

= lo + unLo - ltLo - 1;

170

m = hi - (gtHi - unHi) + 1;

172  if

(

n

- lo > hi - m) {

187 #undef FALLBACK_QSORT_SMALL_THRESH 188 #undef FALLBACK_QSORT_STACK_SIZE 205 #define SET_BH(zz) bhtab[(zz) >> 5] |= ((UInt32)1 << ((zz) & 31)) 206 #define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~((UInt32)1 << ((zz) & 31)) 207 #define ISSET_BH(zz) (bhtab[(zz) >> 5] & ((UInt32)1 << ((zz) & 31))) 208 #define WORD_BH(zz) bhtab[(zz) >> 5] 209 #define UNALIGNED_BH(zz) ((zz) & 0x01f) 230  VPrintf0

(

" bucket sorting ...\n"

);

231  for

(

i

= 0;

i

< 257;

i

++) ftab[

i

] = 0;

232  for

(

i

= 0;

i

< nblock;

i

++) ftab[eclass8[

i

]]++;

233  for

(

i

= 0;

i

< 256;

i

++) ftabCopy[

i

] = ftab[

i

];

234  for

(

i

= 1;

i

< 257;

i

++) ftab[

i

] += ftab[

i

-1];

236  for

(

i

= 0;

i

< nblock;

i

++) {

243

nBhtab = 2 + (nblock / 32);

244  for

(

i

= 0;

i

< nBhtab;

i

++) bhtab[

i

] = 0;

245  for

(

i

= 0;

i

< 256;

i

++)

SET_BH

(ftab[

i

]);

254  for

(

i

= 0;

i

< 32;

i

++) {

267  for

(

i

= 0;

i

< nblock;

i

++) {

269

k = fmap[

i

] -

H

;

if

(k < 0) k += nblock;

281  while

(

WORD_BH

(k) == 0xffffffff) k += 32;

285  if

(

l

>= nblock)

break

;

288  while

(

WORD_BH

(k) == 0x00000000) k += 32;

292  if

(

r

>= nblock)

break

;

296

nNotDone += (

r

-

l

+ 1);

301  for

(

i

=

l

;

i

<=

r

;

i

++) {

302

cc1 = eclass[fmap[

i

]];

303  if

(cc != cc1) {

SET_BH

(

i

); cc = cc1; };

309  VPrintf1

(

"%6d unresolved strings\n"

, nNotDone );

312  if

(

H

> nblock || nNotDone == 0)

break

;

321  VPrintf0

(

" reconstructing block ...\n"

);

323  for

(

i

= 0;

i

< nblock;

i

++) {

324  while

(ftabCopy[j] == 0) j++;

326

eclass8[fmap[

i

]] = (

UChar

)j;

358  AssertD

( i1 != i2,

"mainGtU"

);

360

c1 = block[i1]; c2 = block[i2];

361  if

(c1 != c2)

return

(c1 > c2);

364

c1 = block[i1]; c2 = block[i2];

365  if

(c1 != c2)

return

(c1 > c2);

368

c1 = block[i1]; c2 = block[i2];

369  if

(c1 != c2)

return

(c1 > c2);

372

c1 = block[i1]; c2 = block[i2];

373  if

(c1 != c2)

return

(c1 > c2);

376

c1 = block[i1]; c2 = block[i2];

377  if

(c1 != c2)

return

(c1 > c2);

380

c1 = block[i1]; c2 = block[i2];

381  if

(c1 != c2)

return

(c1 > c2);

384

c1 = block[i1]; c2 = block[i2];

385  if

(c1 != c2)

return

(c1 > c2);

388

c1 = block[i1]; c2 = block[i2];

389  if

(c1 != c2)

return

(c1 > c2);

392

c1 = block[i1]; c2 = block[i2];

393  if

(c1 != c2)

return

(c1 > c2);

396

c1 = block[i1]; c2 = block[i2];

397  if

(c1 != c2)

return

(c1 > c2);

400

c1 = block[i1]; c2 = block[i2];

401  if

(c1 != c2)

return

(c1 > c2);

404

c1 = block[i1]; c2 = block[i2];

405  if

(c1 != c2)

return

(c1 > c2);

412

c1 = block[i1]; c2 = block[i2];

413  if

(c1 != c2)

return

(c1 > c2);

414

s1 = quadrant[i1]; s2 = quadrant[i2];

415  if

(s1 != s2)

return

(s1 > s2);

418

c1 = block[i1]; c2 = block[i2];

419  if

(c1 != c2)

return

(c1 > c2);

420

s1 = quadrant[i1]; s2 = quadrant[i2];

421  if

(s1 != s2)

return

(s1 > s2);

424

c1 = block[i1]; c2 = block[i2];

425  if

(c1 != c2)

return

(c1 > c2);

426

s1 = quadrant[i1]; s2 = quadrant[i2];

427  if

(s1 != s2)

return

(s1 > s2);

430

c1 = block[i1]; c2 = block[i2];

431  if

(c1 != c2)

return

(c1 > c2);

432

s1 = quadrant[i1]; s2 = quadrant[i2];

433  if

(s1 != s2)

return

(s1 > s2);

436

c1 = block[i1]; c2 = block[i2];

437  if

(c1 != c2)

return

(c1 > c2);

438

s1 = quadrant[i1]; s2 = quadrant[i2];

439  if

(s1 != s2)

return

(s1 > s2);

442

c1 = block[i1]; c2 = block[i2];

443  if

(c1 != c2)

return

(c1 > c2);

444

s1 = quadrant[i1]; s2 = quadrant[i2];

445  if

(s1 != s2)

return

(s1 > s2);

448

c1 = block[i1]; c2 = block[i2];

449  if

(c1 != c2)

return

(c1 > c2);

450

s1 = quadrant[i1]; s2 = quadrant[i2];

451  if

(s1 != s2)

return

(s1 > s2);

454

c1 = block[i1]; c2 = block[i2];

455  if

(c1 != c2)

return

(c1 > c2);

456

s1 = quadrant[i1]; s2 = quadrant[i2];

457  if

(s1 != s2)

return

(s1 > s2);

460  if

(i1 >= nblock) i1 -= nblock;

461  if

(i2 >= nblock) i2 -= nblock;

481

9841, 29524, 88573, 265720,

498  if

(bigN < 2)

return

;

501  while

(

incs

[hp] < bigN) hp++;

504  for

(; hp >= 0; hp--) {

515

ptr[j-h]+d, v+d, block, quadrant, nblock, budget

519  if

(j <= (lo + h - 1))

break

;

529

ptr[j-h]+d, v+d, block, quadrant, nblock, budget

533  if

(j <= (lo + h - 1))

break

;

543

ptr[j-h]+d, v+d, block, quadrant, nblock, budget

547  if

(j <= (lo + h - 1))

break

;

552  if

(*budget < 0)

return

;

567 #define mswap(zz1, zz2) \ 568  { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; } 570 #define mvswap(zzp1, zzp2, zzn) \ 572  Int32 yyp1 = (zzp1); \ 573  Int32 yyp2 = (zzp2); \ 576  mswap(ptr[yyp1], ptr[yyp2]); \ 577  yyp1++; yyp2++; yyn--; \ 586  if

(

a

>

b

) {

t

=

a

;

a

=

b

;

b

=

t

; };

594 #define mmin(a,b) ((a) < (b)) ? (a) : (b) 596 #define mpush(lz,hz,dz) { stackLo[sp] = lz; \ 601 #define mpop(lz,hz,dz) { sp--; \ 607 #define mnextsize(az) (nextHi[az]-nextLo[az]) 609 #define mnextswap(az,bz) \ 611  tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \ 612  tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \ 613  tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; } 616 #define MAIN_QSORT_SMALL_THRESH 20 617 #define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT) 618 #define MAIN_QSORT_STACK_SIZE 100 630  Int32

unLo, unHi, ltLo, gtHi,

n

, m, med;

642  mpush

( loSt, hiSt, dSt );

651  mainSimpleSort

( ptr, block, quadrant, nblock, lo, hi, d, budget );

652  if

(*budget < 0)

return

;

657  mmed3

( block[ptr[ lo ]+d],

659

block[ptr[ (lo+hi)>>1 ]+d] );

666  if

(unLo > unHi)

break

;

667  n

= ((

Int32

)block[ptr[unLo]+d]) - med;

669  mswap

(ptr[unLo], ptr[ltLo]);

670

ltLo++; unLo++;

continue

;

676  if

(unLo > unHi)

break

;

677  n

= ((

Int32

)block[ptr[unHi]+d]) - med;

679  mswap

(ptr[unHi], ptr[gtHi]);

680

gtHi--; unHi--;

continue

;

685  if

(unLo > unHi)

break

;

686  mswap

(ptr[unLo], ptr[unHi]); unLo++; unHi--;

689  AssertD

( unHi == unLo-1,

"mainQSort3(2)"

);

692  mpush

(lo, hi, d+1 );

697

m =

mmin

(hi-gtHi, gtHi-unHi);

mvswap

(unLo, hi-m+1, m);

699  n

= lo + unLo - ltLo - 1;

700

m = hi - (gtHi - unHi) + 1;

702

nextLo[0] = lo; nextHi[0] =

n

; nextD[0] = d;

703

nextLo[1] = m; nextHi[1] = hi; nextD[1] = d;

704

nextLo[2] =

n

+1; nextHi[2] = m-1; nextD[2] = d+1;

713  mpush

(nextLo[0], nextHi[0], nextD[0]);

714  mpush

(nextLo[1], nextHi[1], nextD[1]);

715  mpush

(nextLo[2], nextHi[2], nextD[2]);

726 #undef MAIN_QSORT_SMALL_THRESH 727 #undef MAIN_QSORT_DEPTH_THRESH 728 #undef MAIN_QSORT_STACK_SIZE 746 #define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8]) 747 #define SETMASK (1 << 21) 748 #define CLEARMASK (~(SETMASK)) 760  Int32

runningOrder[256];

762  Int32

copyStart[256];

767  if

(verb >= 4)

VPrintf0

(

" main sort initialise ...\n"

);

770  for

(

i

= 65536;

i

>= 0;

i

--) ftab[

i

] = 0;

774  for

(;

i

>= 3;

i

-= 4) {

776

j = (j >> 8) | ( ((

UInt16

)block[

i

]) << 8);

779

j = (j >> 8) | ( ((

UInt16

)block[

i

-1]) << 8);

782

j = (j >> 8) | ( ((

UInt16

)block[

i

-2]) << 8);

785

j = (j >> 8) | ( ((

UInt16

)block[

i

-3]) << 8);

788  for

(;

i

>= 0;

i

--) {

790

j = (j >> 8) | ( ((

UInt16

)block[

i

]) << 8);

796

block [nblock+

i

] = block[

i

];

797

quadrant[nblock+

i

] = 0;

800  if

(verb >= 4)

VPrintf0

(

" bucket sorting ...\n"

);

803  for

(

i

= 1;

i

<= 65536;

i

++) ftab[

i

] += ftab[

i

-1];

807  for

(;

i

>= 3;

i

-= 4) {

808

s = (s >> 8) | (block[

i

] << 8);

812

s = (s >> 8) | (block[

i

-1] << 8);

816

s = (s >> 8) | (block[

i

-2] << 8);

820

s = (s >> 8) | (block[

i

-3] << 8);

825  for

(;

i

>= 0;

i

--) {

826

s = (s >> 8) | (block[

i

] << 8);

837  for

(

i

= 0;

i

<= 255;

i

++) {

839

runningOrder[

i

] =

i

;

845  do

h = 3 * h + 1;

while

(h <= 256);

848  for

(

i

= h;

i

<= 255;

i

++) {

849

vv = runningOrder[

i

];

852

runningOrder[j] = runningOrder[j-h];

854  if

(j <= (h - 1))

goto

zero;

857

runningOrder[j] = vv;

868  for

(

i

= 0;

i

<= 255;

i

++) {

876

ss = runningOrder[

i

];

886  for

(j = 0; j <= 255; j++) {

889  if

( ! (ftab[sb] &

SETMASK

) ) {

895  "done %d this %d\n"

,

896

ss, j, numQSorted, hi - lo + 1 );

898

ptr, block, quadrant, nblock,

901

numQSorted += (hi - lo + 1);

902  if

(*budget < 0)

return

;

909  AssertH

( !bigDone[ss], 1006 );

919  for

(j = 0; j <= 255; j++) {

920

copyStart[j] = ftab[(j << 8) + ss] &

CLEARMASK

;

921

copyEnd [j] = (ftab[(j << 8) + ss + 1] &

CLEARMASK

) - 1;

923  for

(j = ftab[ss << 8] &

CLEARMASK

; j < copyStart[ss]; j++) {

924

k = ptr[j]-1;

if

(k < 0) k += nblock;

927

ptr[ copyStart[c1]++ ] = k;

929  for

(j = (ftab[(ss+1) << 8] &

CLEARMASK

) - 1; j > copyEnd[ss]; j--) {

930

k = ptr[j]-1;

if

(k < 0) k += nblock;

933

ptr[ copyEnd[c1]-- ] = k;

937  AssertH

( (copyStart[ss]-1 == copyEnd[ss])

943

(copyStart[ss] == 0 && copyEnd[ss] == nblock-1),

946  for

(j = 0; j <= 255; j++) ftab[(j << 8) + ss] |=

SETMASK

;

994  while

((bbSize >> shifts) > 65534) shifts++;

996  for

(j = bbSize-1; j >= 0; j--) {

997  Int32

a2update = ptr[bbStart + j];

999

quadrant[a2update] = qVal;

1001

quadrant[a2update + nblock] = qVal;

1003  AssertH

( ((bbSize-1) >> shifts) <= 65535, 1002 );

1009  VPrintf3

(

" %d pointers, %d sorted, %d scanned\n"

,

1010

nblock, numQSorted, nblock - numQSorted );

1044  if

(nblock < 10000) {

1054

quadrant = (

UInt16

*)(&(block[

i

]));

1063  if

(wfact < 1 ) wfact = 1;

1064  if

(wfact > 100) wfact = 100;

1065

budgetInit = nblock * ((wfact-1) / 3);

1066

budget = budgetInit;

1068  mainSort

( ptr, block, quadrant, ftab, nblock, verb, &budget );

1070  VPrintf3

(

" %d work, %d block, ratio %5.2f\n"

,

1071

budgetInit - budget,

1073

(

float

)(budgetInit - budget) /

1074

(

float

)(nblock==0 ? 1 : nblock) );

1077  VPrintf0

(

" too repetitive; using fallback" 1078  " sorting algorithm\n"

);

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)

#define MAIN_QSORT_STACK_SIZE

#define mvswap(zzp1, zzp2, zzn)

static void mainSimpleSort(UInt32 *ptr, UChar *block, UInt16 *quadrant, Int32 nblock, Int32 lo, Int32 hi, Int32 d, Int32 *budget)

#define MAIN_QSORT_SMALL_THRESH

static void fallbackSort(UInt32 *fmap, UInt32 *eclass, UInt32 *bhtab, Int32 nblock, Int32 verb)

static Bool mainGtU(UInt32 i1, UInt32 i2, UChar *block, UInt16 *quadrant, UInt32 nblock, Int32 *budget)

void BZ2_blockSort(EState *s)

static void fallbackQSort3(UInt32 *fmap, UInt32 *eclass, Int32 loSt, Int32 hiSt)

#define mpush(lz, hz, dz)

#define MAIN_QSORT_DEPTH_THRESH

static UChar mmed3(UChar a, UChar b, UChar c)

static void fallbackSimpleSort(UInt32 *fmap, UInt32 *eclass, Int32 lo, Int32 hi)

#define fvswap(zzp1, zzp2, zzn)

#define FALLBACK_QSORT_STACK_SIZE

#define mnextswap(az, bz)

#define FALLBACK_QSORT_SMALL_THRESH

#define VPrintf4(zf, za1, za2, za3, za4)

#define VPrintf3(zf, za1, za2, za3)

#define AssertH(cond, errcode)

#define AssertD(cond, msg)

#define VPrintf1(zf, za1)

double r(size_t dimension_, const Int4 *score_, const double *prob_, double theta_)

static SLJIT_INLINE sljit_ins l(sljit_gpr r, sljit_s32 d, sljit_gpr x, sljit_gpr b)

static const sljit_gpr r3

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4