Adding upstream version 1:10.5.12.upstream/1%10.5.12upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 966 insertions, 0 deletions

diff --git a/storage/connect/csort.cpp b/storage/connect/csort.cpp
new file mode 100644
index 00000000..1e4ba674
--- /dev/null
+++ b/storage/connect/csort.cpp
@@ -0,0 +1,966 @@
+/*************** 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 --------------------------- */