mirror/mariadb
1
0
Fork 0
mirror of https://github.com/MariaDB/server.git synced 2025-11-04 04:46:15 +01:00
Code Issues Projects Releases Packages Wiki Activity
mariadb/storage/connect/csort.cpp
Olivier Bertrand 0b624debdf Update to version 1.07 (as for MariaDB 10.2)
2020-01-09 16:10:25 +01:00

966 lines
35 KiB
C++
Raw Permalink Blame History

/*************** CSort C Program Source Code File (.CPP) ***************/
/* PROGRAM NAME: CSORT */
/* ------------- */
/* Version 2.2 */
/* */
/* COPYRIGHT: */
/* ---------- */
/* (C) Copyright to the author Olivier Bertrand 1995-2016 */
/* */
/* WHAT THIS PROGRAM DOES: */
/* ----------------------- */
/* This program is the C++ sorting routines that use qsort/insert */
/* algorithm and produces an offset/break table while sorting. */
/* */
/* WHAT YOU NEED TO COMPILE THIS PROGRAM: */
/* -------------------------------------- */
/* */
/* REQUIRED FILES: */
/* --------------- */
/* csort.cpp - Source code */
/* */
/* REQUIRED LIBRARIES: */
/* ------------------- */
/* OS2DEF.LIB - OS2 libray definition subset. */
/* */
/* REQUIRED PROGRAMS: */
/* ------------------ */
/* Microsoft C++ Compiler */
/* or GNU Compiler/Linker */
/* or BORLAND 4.5 C++ compiler */
/* */
/* NOTE */
/* ---- */
/* These functions are not 64-bits ready. */
/* */
/***********************************************************************/
/***********************************************************************/
/* Include relevant MariaDB header file. */
/***********************************************************************/
#include "my_global.h"
/***********************************************************************/
/* Include application header files */
/***********************************************************************/
#include <stdlib.h> /* C standard library */
#include <string.h> /* String manipulation declares */
#include <stdio.h> /* Required for sprintf declare */
#if defined(_DEBUG)
#include <assert.h> /* Assertion routine declares */
#endif
/***********************************************************************/
/* Include CSort class header file */
/***********************************************************************/
#include "global.h"
#include "plgdbsem.h" /* For MBLOCK type definition */
#include "csort.h" /* CSort class definition */
#include "osutil.h"
#if !defined(BIGSORT)
#define BIGSORT 200000
#endif // !BIGSORT
/***********************************************************************/
/* DB static external variables. */
/***********************************************************************/
extern MBLOCK Nmblk; /* Used to initialize MBLOCK's */
/***********************************************************************/
/* Initialize the CSORT static members. */
/***********************************************************************/
int CSORT::Limit = 0;
double CSORT::Lg2 = log(2.0);
size_t CSORT::Cpn[1000] = {0}; /* Precalculated cmpnum values */
/***********************************************************************/
/* CSORT constructor. */
/***********************************************************************/
CSORT::CSORT(bool cns, int th, int mth)
: Pex((int*&)Index.Memp), Pof((int*&)Offset.Memp)
{
G = NULL;
Dup =NULL;
Cons = cns;
Thresh = th;
Mthresh = mth;
Nitem = 0;
Index = Nmblk;
Offset = Nmblk;
Swix = NULL;
Savmax = 0;
Savcur = 0;
Savstep = NULL;
} // end of CSORT constructor
/***********************************************************************/
/* CSORT intialization. */
/***********************************************************************/
int CSORT::Qsort(PGLOBAL g, int nb)
{
int rc;
#if defined(_DEBUG)
assert(Index.Size >= nb * sizeof(int));
#endif
if (nb > BIGSORT) {
G = g;
Dup = (PDBUSER)g->Activityp->Aptr;
if (Dup->Proginfo) {
Savstep = Dup->Step;
Savmax = Dup->ProgMax;
Savcur = Dup->ProgCur;
// Evaluate the number of comparisons that we will do
Dup->ProgMax = Cmpnum(nb);
Dup->ProgCur = 0;
Dup->Step = (char*)PlugSubAlloc(g, NULL, 32);
sprintf((char*)Dup->Step, MSG(SORTING_VAL), nb);
} else
Dup = NULL;
} else
Dup = NULL;
Nitem = nb;
for (int n = 0; n < Nitem; n++)
Pex[n] = n;
rc = (Cons) ? Qsortc() : Qsortx();
if (Dup) {
// Restore any change in progress info settings
// printf("Progcur=%u\n", Dup->ProgCur);
Dup->Step = Savstep;
Dup->ProgMax = Savmax;
Dup->ProgCur = Savcur;
} // endif Subcor
return rc;
} // end of QSort
#if defined(DEBTRACE)
/***********************************************************************/
/* Debug routine to be used by sort for specific data (dummy as now) */
/***********************************************************************/
void CSORT::DebugSort(int ph, int n, int *base, int *mid, int *tmp)
{
htrc("phase=%d n=%d base=%p mid=%p tmp=%p\n",
ph, n, base, mid, tmp);
} // end of DebugSort
#endif
/***********************************************************************/
/* Qsortx: Version adapted from qsortx.c by O.Bertrand */
/* This version is specialy adapted for Index sorting, meaning that */
/* the data is not moved, but the Index only is sorted. */
/* Index array elements are any 4-byte word (a pointer or a int int */
/* array index), they are not interpreted except by the user provided */
/* comparison routine which must works accordingly. */
/* In addition, this program takes care of data in which there is a */
/* high rate of repetitions. */
/* CAUTION: the sort algorithm used here is not conservative. Equal */
/* values will be internally stored in unpredictable order. */
/* The THRESHold below is the insertion sort threshold, and also the */
/* threshold for continuing que quicksort partitioning. */
/* The MTHREShold is where we stop finding a better median. */
/* These two quantities should be adjusted dynamically depending upon */
/* the repetition rate of the data. */
/* Algorithm used: */
/* First, set up some global parameters for Qstx to share. Then, */
/* quicksort with Qstx(), and then a cleanup insertion sort ourselves. */
/* Sound simple? It's not... */
/***********************************************************************/
int CSORT::Qsortx(void)
{
int c;
int lo, hi, min;
int i, j, rc = 0;
// To do: rc should be checked for being used uninitialized
int *top;
#ifdef DEBTRACE
int ncp;
num_comp = 0;
#endif
/*********************************************************************/
/* Prepare the Offset array that will be updated during sorts. */
/*********************************************************************/
if (Pof)
for (Pof[Nitem] = Nitem, j = 0; j < Nitem; j++)
Pof[j] = 0;
else
j = Nitem + 1;
/*********************************************************************/
/* Sort on one or zero element is obvious. */
/*********************************************************************/
if (Nitem <= 1)
return Nitem;
/*********************************************************************/
/* Thresh seems to be good as (10 * n / rep). But for testing we */
/* set it directly as one parameter of the Xset function call. */
/* Note: this should be final as the rep parameter is no more used. */
/*********************************************************************/
top = Pex + Nitem;
#ifdef DEBTRACE
htrc("Qsortx: nitem=%d thresh=%d mthresh=%d\n",
Nitem, Thresh, Mthresh);
#endif
/*********************************************************************/
/* If applicable, do a rough preliminary quick sort. */
/*********************************************************************/
if (Nitem >= Thresh)
Qstx(Pex, top);
#ifdef DEBTRACE
htrc(" after quick sort num_comp=%d\n", num_comp);
ncp = num_comp;
num_comp = 0;
#ifdef DEBUG2
DebugSort((Pof) ? 1 : 4, Nitem, Pex, NULL, NULL);
#endif
#endif
if (Thresh > 2) {
if (Pof)
/*****************************************************************/
/* The preliminary search for the smallest element has been */
/* removed so with no sentinel in place, we must check for x */
/* going below the Pof pointer. For each remaining element */
/* group from [1] to [n-1], set hi to the index of the element */
/* AFTER which this one goes. Then, do the standard insertion */
/* sort shift on an integer at a time basis for each equal */
/* element group in the frob. */
/*****************************************************************/
for (min = hi = 0; min < Nitem; min = hi) {
if (Pof[hi]) {
hi += Pof[hi];
continue;
} // endif Pof
Pof[min] = 1;
#ifdef DEBUG2
htrc("insert from min=%d\n", min);
#endif
for (lo = hi; !Pof[++hi]; lo = hi) {
while (lo >= min && (rc = Qcompare(Pex + lo, Pex + hi)) > 0)
if (Pof[lo] > 0)
lo -= Pof[lo];
else
return -2;
if (++lo != hi) {
c = Pex[hi];
for (i = j = hi; i > 0; i = j)
if (Pof[i - 1] <= 0)
return -3;
else if ((j -= Pof[i - 1]) >= lo) {
Pex[i] = Pex[j];
Pof[j + 1] = Pof[i] = Pof[j];
} else
break;
Pex[i] = c;
} // endif lo
if (rc)
Pof[lo] = 1;
else {
i = lo - Pof[lo - 1];
Pof[lo] = ++Pof[i];
} // endelse
#ifdef DEBUG2
htrc("rc=%d lo=%d hi=%d trx=%d\n", rc, lo, hi, Pof[lo]);
#endif
} // endfor hi
} // endfor min
else
/*****************************************************************/
/* Call conservative insertion sort not using/setting offset. */
/*****************************************************************/
Istc(Pex, Pex + MY_MIN(Nitem, Thresh), top);
} // endif Thresh
#ifdef DEBTRACE
htrc(" after insert sort num_comp=%d\n", num_comp);
num_comp += ncp;
#endif
if (Pof)
/*******************************************************************/
/* Reduce the Offset array. */
/*******************************************************************/
for (i = j = 0; i <= Nitem; j++, i += c) {
#ifdef DEBUG2
htrc(" trxp(%d)=%d trxp(%d)=%d c=%d\n",
i, Pof[i], j, Pof[j], c);
#endif
if ((c = Pof[i]))
Pof[j] = i;
else
return -4;
} // endfor i
return (j - 1);
} // end of Qsortx
/***********************************************************************/
/* Qstx: Do a quicksort on index elements (just one int int). */
/* First, find the median element, and put that one in the first place */
/* as the discriminator. (This "median" is just the median of the */
/* first, last and middle elements). (Using this median instead of */
/* the first element is a big win). Then, the usual partitioning/ */
/* swapping, followed by moving the discriminator into the right place.*/
/* Element equal to the discriminator are placed against it, so the */
/* mid (discriminator) block grows when equal elements exist. This is */
/* a huge win in case of repartitions with few different elements. */
/* The mid block being at its final position, its first and last */
/* elements are marked in the offset list (used to make break list). */
/* Then, figure out the sizes of the two partitions, do the smaller */
/* one recursively and the larger one via a repeat of this code. */
/* Stopping when there are less than THRESH elements in a partition */
/* and cleaning up with an insertion sort (in our caller) is a huge */
/* win(?). All data swaps are done in-line, which is space-losing but */
/* time-saving. (And there are only three places where this is done). */
/***********************************************************************/
void CSORT::Qstx(int *base, int *max)
{
int *i, *j, *jj, *mid, *him, c;
int *tmp;
int lo, hi, rc;
size_t zlo, zhi, cnm;
zlo = zhi = cnm = 0; // Avoid warning message
lo = (int)(max - base); // Number of elements as longs
if (Dup)
cnm = Cmpnum(lo);
do {
/*******************************************************************/
/* At the top here, lo is the number of integers of elements in */
/* the current partition. (Which should be max - base). */
/* Find the median of the first, last, and middle element and make */
/* that the middle element. Set j to largest of first and middle. */
/* If max is larger than that guy, then it's that guy, else */
/* compare max with loser of first and take larger. Things are */
/* set up to prefer the middle, then the first in case of ties. */
/* In addition, hi and rc are set to comparison results. So if hi */
/* is null, the two high values are equal and if rc is null, the */
/* two low values are equal. This was used to set which test will */
/* be made by LE and which one by LT (does not apply anymore). */
/*******************************************************************/
him = mid = i = base + (lo >> 1);
hi = rc = 0;
#ifdef DEBTRACE
tmp = max - 1;
htrc("--> block base=%d size=%d\n", base - Pex, lo);
DebugSort(2, 0, base, mid, tmp);
#endif
if (lo >= Mthresh) {
rc = Qcompare((jj = base), i);
j = (rc > 0) ? jj : i;
hi = Qcompare(j, (tmp = max - 1));
if (hi > 0 && rc) {
j = (j == jj) ? i : jj; // switch to first loser
if ((rc = Qcompare(j, tmp)) < 0)
j = tmp;
} // endif
if (j != i) {
c = *i;
*i = *j;
*j = c;
} // endif j
} else if (lo == 2) {
/*****************************************************************/
/* Small group. Do special quicker processing. */
/*****************************************************************/
if ((rc = Qcompare(base, (him = base + 1))) > 0)
c = *base, *base = *him, *him = c;
if (Pof)
Pof[base - Pex] = Pof[him - Pex] = (rc) ? 1 : 2;
break;
} // endif lo
#ifdef DEBTRACE
DebugSort(3, hi, NULL, mid, &rc);
#endif
/*******************************************************************/
/* Semi-standard quicksort partitioning/swapping. Added here is */
/* a test on equality. All values equal to the mid element are */
/* placed under or over it. Mid block can be also moved when it */
/* is necessary because the other partition is full. At the end */
/* of the for loop the mid block is definitely positionned. */
/*******************************************************************/
for (i = base, j = max - 1; ;) {
CONT:
while (i < mid)
if ((rc = Qcompare(i, mid)) < 0)
i++;
else if (!rc) {
c = *i;
*i = *(--mid);
*mid = c;
} else
break;
while (j > him)
if ((rc = Qcompare(him, j)) < 0)
j--;
else if (!rc) {
c = *j;
*j = *(++him);
*him = c;
} else if (i == mid) { // Triple move:
c = *j; // j goes under mid block
*j = *(++him); // val over mid block -> j
*him = *mid++; // and mid block goes one
*i++ = c; // position higher.
} else { // i <-> j
c = *i;
*i++ = *j;
*j-- = c;
goto CONT;
} // endif's
if (i == mid)
break;
else { // Triple move:
c = *i; // i goes over mid block
*i = *(--mid); // val under mid block -> i
*mid = *him--; // and mid block goes one
*j-- = c; // position lower.
} // endelse
} // endfor i
/*******************************************************************/
/* The mid block being placed at its final position we can now set */
/* the offset array values indicating break point and block size. */
/*******************************************************************/
j = mid;
i = him + 1;
if (Pof)
Pof[him - Pex] = Pof[mid - Pex] = (int)(i - j);
/*******************************************************************/
/* Look at sizes of the two partitions, do the smaller one first */
/* by recursion, then do the larger one by making sure lo is its */
/* size, base and max are update correctly, and branching back. */
/* But only repeat (recursively or by branching) if the partition */
/* is of at least size THRESH. */
/*******************************************************************/
lo = (int)(j - base);
hi = (int)(max - i);
if (Dup) { // Update progress information
zlo = Cmpnum(lo);
zhi = Cmpnum(hi);
Dup->ProgCur += cnm - (zlo + zhi);
} // endif Dup
#ifdef DEBTRACE
htrc(" done lo=%d sep=%d hi=%d\n", lo, i - j, hi);
#endif
if (lo <= hi) {
if (lo >= Thresh)
Qstx(base, j);
else if (lo == 1 && Pof)
Pof[base - Pex] = 1;
base = i;
lo = hi;
cnm = zhi;
} else {
if (hi >= Thresh)
Qstx(i, max);
else if (hi == 1 && Pof)
Pof[i - Pex] = 1;
max = j;
cnm = zlo;
} // endif
if (lo == 1 && Pof)
Pof[base - Pex] = 1;
} while (lo >= Thresh); // enddo
} // end of Qstx
/***********************************************************************/
/* Qsortc.c: Version adapted from qsort.c by O.Bertrand */
/* This version is specialy adapted for Index sorting, meaning that */
/* the data is not moved, but the Index only is sorted. */
/* Index array elements are any 4-byte word (a pointer or a int int */
/* array index), they are not interpreted except by the user provided */
/* comparison routine which must works accordingly. */
/* In addition, this program takes care of data in which there is a */
/* high rate of repetitions. */
/* NOTE: the sort algorithm used here is conservative. Equal and */
/* greater than values are internally stored in additional work area. */
/* The THRESHold below is the insertion sort threshold, and also the */
/* threshold for continuing que quicksort partitioning. */
/* The MTHREShold is where we stop finding a better median. */
/* These two quantities should be adjusted dynamically depending upon */
/* the repetition rate of the data. */
/* Algorithm used: */
/* First, set up some global parameters for Qstc to share. Then, */
/* quicksort with Qstc(), and then a cleanup insertion sort ourselves.*/
/* Sound simple? It's not... */
/***********************************************************************/
int CSORT::Qsortc(void)
{
int c;
int lo, hi, min;
int i, j, k, m, rc = 0;
// To do: rc should be checked for being used uninitialized
int *max;
#ifdef DEBTRACE
int ncp;
num_comp = 0;
#endif
/*********************************************************************/
/* Prepare the Offset array that will be updated during sorts. */
/*********************************************************************/
if (Pof)
for (Pof[Nitem] = Nitem, j = 0; j < Nitem; j++)
Pof[j] = 0;
else
j = Nitem + 1;
/*********************************************************************/
/* Sort on one or zero element is obvious. */
/*********************************************************************/
if (Nitem <= 1)
return Nitem;
/*********************************************************************/
/* Thresh seems to be good as (10 * n / rep). But for testing we */
/* set it directly as one parameter of the Xset function call. */
/* Note: this should be final as the rep parameter is no more used. */
/*********************************************************************/
max = Pex + Nitem;
#ifdef DEBTRACE
htrc("Qsortc: nitem=%d thresh=%d mthresh=%d\n",
Nitem, Thresh, Mthresh);
#endif
/*********************************************************************/
/* If applicable, do a rough preliminary conservative quick sort. */
/*********************************************************************/
if (Nitem >= Thresh) {
if (!(Swix = (int *)malloc(Nitem * sizeof(int))))
return -1;
Qstc(Pex, max);
free(Swix);
Swix = NULL;
} // endif n
#ifdef DEBTRACE
htrc(" after quick sort num_comp=%d\n", num_comp);
ncp = num_comp;
num_comp = 0;
#ifdef DEBUG2
DebugSort((Pof) ? 1 : 4, Nitem, Pex, NULL, NULL);
#endif
#endif
if (Thresh > 2) {
if (Pof)
/*****************************************************************/
/* The preliminary search for the smallest element has been */
/* removed so with no sentinel in place, we must check for x */
/* going below the Pof pointer. For each remaining element */
/* group from [1] to [n-1], set hi to the index of the element */
/* AFTER which this one goes. Then, do the standard insertion */
/* sort shift on an integer at a time basis for each equal */
/* element group in the frob. */
/*****************************************************************/
for (min = hi = 0; min < Nitem; min = hi) {
if (Pof[hi]) {
hi += Pof[hi];
continue;
} // endif
Pof[min] = 1;
#ifdef DEBUG2
htrc("insert from min=%d\n", min);
#endif
for (lo = hi; !Pof[++hi]; lo = hi) {
while (lo >= min && (rc = Qcompare(Pex + lo, Pex + hi)) > 0)
if (Pof[lo] > 0)
lo -= Pof[lo];
else
return -2;
if (++lo != hi) {
c = Pex[hi];
for (i = j = hi; i > 0; i = j)
if (Pof[i - 1] <= 0)
return -3;
else if ((j -= Pof[i - 1]) >= lo) {
for (k = m = i; --m >= j; k--) // Move intermediate
Pex[k] = Pex[m]; // for conservation.
Pof[j + 1] = Pof[i] = Pof[j];
} else
break;
Pex[i] = c;
} // endif
if (rc)
Pof[lo] = 1;
else {
i = lo - Pof[lo - 1];
Pof[lo] = ++Pof[i];
} // endelse
#ifdef DEBUG2
htrc("rc=%d lo=%d hi=%d ofx=%d\n", rc, lo, hi, Pof[lo]);
#endif
} // endfor hi
} // endfor min
else
/*****************************************************************/
/* Call conservative insertion sort not using/setting offset. */
/*****************************************************************/
Istc(Pex, Pex + MY_MIN(Nitem, Thresh), max);
} // endif Thresh
#ifdef DEBTRACE
htrc(" after insert sort num_comp=%d\n", num_comp);
num_comp += ncp;
#endif
if (Pof)
/*******************************************************************/
/* Reduce the Offset array. */
/*******************************************************************/
for (i = j = 0; i <= Nitem; j++, i += c) {
#ifdef DEBUG2
htrc(" Pof(%d)=%d Pof(%d)=%d c=%d\n",
i, Pof[i], j, Pof[j], c);
#endif
if ((c = Pof[i]))
Pof[j] = i;
else
return -4;
} // endfor i
return (j - 1);
} // end of Qsortc
/***********************************************************************/
/* Qstc: Do a quicksort on index elements (just one int int). */
/* First, find the median element, and set it as the discriminator. */
/* (This "median" is just the median of the first, last and middle */
/* elements). (Using this median instead of the first element is a */
/* big win). Then, the special partitioning/swapping, where elements */
/* smaller than the discriminator are placed in the sorted block, */
/* elements equal to the discriminator are placed backward from the */
/* top of the work area and elements greater than *j (discriminator) */
/* are placed in the work area from its bottom. Then the elements in */
/* the work area are placed back in the sort area in natural order, */
/* making the sort conservative. Non equal blocks shrink faster when */
/* equal elements exist. This is a huge win in case of repartitions */
/* with few different elements. The mid block being at its final */
/* position, its first and last elements are marked in the offset */
/* list (used to make break list). Then, figure out the sizes of the */
/* two partitions, do the smaller one recursively and the larger one */
/* via a repeat of this code. Stopping when there are less than */
/* THRESH elements in a partition and cleaning up with an insertion */
/* sort (in our caller) is a huge win (yet to be proved?). */
/***********************************************************************/
void CSORT::Qstc(int *base, int *max)
{
int *i, *j, *jj, *lt, *eq, *gt, *mid;
int c = 0, lo, hi, rc;
size_t zlo, zhi, cnm;
zlo = zhi = cnm = 0; // Avoid warning message
lo = (int)(max - base); // Number of elements as longs
if (Dup)
cnm = Cmpnum(lo);
do {
/*******************************************************************/
/* At the top here, lo is the number of integers of elements in */
/* the current partition. (Which should be max - base). Find the */
/* median of the first, last, and middle element and make that */
/* the compare element. Set jj to smallest of middle and last. */
/* If base is smaller or equal than that guy, then it's that guy, */
/* else compare base with loser of first and take smaller. Things */
/* are set up to prefer the top, then the middle in case of ties. */
/*******************************************************************/
i = base + (lo >> 1);
jj = mid = max - 1;
#ifdef DEBTRACE
htrc("--> block base=%d size=%d\n", base - Pex, lo);
DebugSort(2, 0, base, i, mid);
#endif
if (lo >= Mthresh) {
jj = ((rc = Qcompare(i, mid)) < 0) ? i : mid;
if (rc && Qcompare(base, jj) > 0) {
jj = (jj == mid) ? i : mid; // switch to first loser
if (Qcompare(base, jj) < 0)
jj = base;
} // endif
if (jj != mid) {
/***************************************************************/
/* The compare element must be at the top of the block so it */
/* cannot be overwritten while making the partitioning. So */
/* save the last block value which will be compared later. */
/***************************************************************/
c = *mid;
*mid = *jj;
} // endif
} else if (lo == 2) {
/*****************************************************************/
/* Small group. Do special quicker processing. */
/*****************************************************************/
if ((rc = Qcompare(base, (i = base + 1))) > 0) {
c = *base;
*base = *i;
*i = c;
} // endif rc
if (Pof)
Pof[base - Pex] = Pof[i - Pex] = (rc) ? 1 : 2;
break;
} // endif lo
#ifdef DEBTRACE
DebugSort(3, lo, NULL, jj, &rc);
#endif
/*******************************************************************/
/* Non-standard quicksort partitioning using additional storage */
/* to store values less than, equal or greater than the middle */
/* element. This uses more memory but provides conservation of */
/* the equal elements order. */
/*******************************************************************/
lt = base;
eq = Swix + lo;
gt = Swix;
if (jj == mid) {
/*****************************************************************/
/* Compare element was last. No problem. */
/*****************************************************************/
for (i = base; i < max; i++)
if ((rc = Qcompare(i, mid)) < 0)
*lt++ = *i;
else if (rc > 0)
*gt++ = *i;
else
*--eq = *i;
} else {
/*****************************************************************/
/* Compare element was not last and was copied to top of block. */
/*****************************************************************/
for (i = base; i < mid; i++)
if ((rc = Qcompare(i, mid)) < 0)
*lt++ = *i;
else if (rc > 0)
*gt++ = *i;
else
*--eq = *i;
/*****************************************************************/
/* Restore saved last value and do the comparison from there. */
/*****************************************************************/
*--i = c;
if ((rc = Qcompare(i, mid)) < 0)
*lt++ = *i;
else if (rc > 0)
*gt++ = *i;
else
*--eq = *i;
} // endif
/*******************************************************************/
/* Now copy the equal and greater values back in the main array in */
/* the same order they have been placed in the work area. */
/*******************************************************************/
for (j = Swix + lo, i = lt; j > eq; )
*i++ = *--j;
for (j = Swix, jj = i; j < gt; )
*i++ = *j++;
/*******************************************************************/
/* The mid block being placed at its final position we can now set */
/* the offset array values indicating break point and block size. */
/*******************************************************************/
if (Pof)
Pof[lt - Pex] = Pof[(jj - 1) - Pex] = (int)(jj - lt);
/*******************************************************************/
/* Look at sizes of the two partitions, do the smaller one first */
/* by recursion, then do the larger one by making sure lo is its */
/* size, base and max are update correctly, and branching back. */
/* But only repeat (recursively or by branching) if the partition */
/* is of at least size THRESH. */
/*******************************************************************/
lo = (int)(lt - base);
hi = (int)(gt - Swix);
if (Dup) { // Update progress information
zlo = Cmpnum(lo);
zhi = Cmpnum(hi);
Dup->ProgCur += cnm - (zlo + zhi);
} // endif Dup
#ifdef DEBTRACE
htrc(" done lo=%d hi=%d\n",
lo, /*Swix + lt - base - eq,*/ hi);
#endif
if (lo <= hi) {
if (lo >= Thresh)
Qstc(base, lt);
else if (lo == 1 && Pof)
Pof[base - Pex] = 1;
base = jj;
lo = hi;
cnm = zhi;
} else {
if (hi >= Thresh)
Qstc(jj, max);
else if (hi == 1 && Pof)
Pof[jj - Pex] = 1;
max = lt;
cnm = zlo;
} // endif
if (lo == 1 && Pof)
Pof[base - Pex] = 1;
} while (lo >= Thresh); // enddo
} // end of Qstc
/***********************************************************************/
/* Conservative insertion sort not using/setting offset array. */
/***********************************************************************/
void CSORT::Istc(int *base, int *hi, int *max)
{
int c = 0;
int *lo;
int *i, *j;
/*********************************************************************/
/* First put smallest element, which must be in the first THRESH, */
/* in the first position as a sentinel. This is done just by */
/* searching the 1st THRESH elements (or the 1st n if n < THRESH) */
/* finding the min, and shifting it into the first position. */
/*********************************************************************/
for (j = lo = base; ++lo < hi; )
if (Qcompare(j, lo) > 0)
j = lo;
if (j != base) { // shift j into place
c = *j;
for (i = j; --j >= base; i = j)
*i = *j;
*base = c;
} // endif j
#ifdef DEBTRACE
htrc("sentinel %d in place, base=%p hi=%p max=%p\n",
c, base, hi, max);
#endif
/*********************************************************************/
/* With our sentinel in place, we now run the following hyper- */
/* fast insertion sort. For each remaining element, lo, from [1] */
/* to [n-1], set hi to the index of the element AFTER which this */
/* one goes. Then, do the standard insertion sort shift for each */
/* element in the frob. */
/*********************************************************************/
for (lo = base; (hi = ++lo) < max;) {
while (Qcompare(--hi, lo) > 0) ;
#ifdef DEBUG2
htrc("after while: hi(%p)=%d lo(%p)=%d\n",
hi, *hi, lo, *lo);
#endif
if (++hi != lo) {
c = *lo;
for (i = j = lo; --j >= hi; i = j)
*i = *j;
*i = c;
} // endif hi
} // endfor lo
} // end of Istc
/* -------------------------- End of CSort --------------------------- */
Reference in a new issue View git blame Copy permalink