1 /*************** CSort C Program Source Code File (.CPP) ***************/
2 /* PROGRAM NAME: CSORT */
3 /* ------------- */
4 /* Version 2.2 */
5 /* */
6 /* COPYRIGHT: */
7 /* ---------- */
8 /* (C) Copyright to the author Olivier Bertrand 1995-2016 */
9 /* */
10 /* WHAT THIS PROGRAM DOES: */
11 /* ----------------------- */
12 /* This program is the C++ sorting routines that use qsort/insert */
13 /* algorithm and produces an offset/break table while sorting. */
14 /* */
15 /* WHAT YOU NEED TO COMPILE THIS PROGRAM: */
16 /* -------------------------------------- */
17 /* */
18 /* REQUIRED FILES: */
19 /* --------------- */
20 /* csort.cpp - Source code */
21 /* */
22 /* REQUIRED LIBRARIES: */
23 /* ------------------- */
24 /* OS2DEF.LIB - OS2 libray definition subset. */
25 /* */
26 /* REQUIRED PROGRAMS: */
27 /* ------------------ */
28 /* Microsoft C++ Compiler */
29 /* or GNU Compiler/Linker */
30 /* or BORLAND 4.5 C++ compiler */
31 /* */
32 /* NOTE */
33 /* ---- */
34 /* These functions are not 64-bits ready. */
35 /* */
36 /***********************************************************************/
37
38 /***********************************************************************/
39 /* Include relevant MariaDB header file. */
40 /***********************************************************************/
41 #include "my_global.h"
42
43 /***********************************************************************/
44 /* Include application header files */
45 /***********************************************************************/
46 #include <stdlib.h> /* C standard library */
47 #include <string.h> /* String manipulation declares */
48 #include <stdio.h> /* Required for sprintf declare */
49 #if defined(_DEBUG)
50 #include <assert.h> /* Assertion routine declares */
51 #endif
52
53 /***********************************************************************/
54 /* Include CSort class header file */
55 /***********************************************************************/
56 #include "global.h"
57 #include "plgdbsem.h" /* For MBLOCK type definition */
58 #include "csort.h" /* CSort class definition */
59 #include "osutil.h"
60
61 #if !defined(BIGSORT)
62 #define BIGSORT 200000
63 #endif // !BIGSORT
64
65 /***********************************************************************/
66 /* DB static external variables. */
67 /***********************************************************************/
68 extern MBLOCK Nmblk; /* Used to initialize MBLOCK's */
69
70 /***********************************************************************/
71 /* Initialize the CSORT static members. */
72 /***********************************************************************/
73 int CSORT::Limit = 0;
74 double CSORT::Lg2 = log(2.0);
75 size_t CSORT::Cpn[1000] = {0}; /* Precalculated cmpnum values */
76
77 /***********************************************************************/
78 /* CSORT constructor. */
79 /***********************************************************************/
CSORT(bool cns,int th,int mth)80 CSORT::CSORT(bool cns, int th, int mth)
81 : Pex((int*&)Index.Memp), Pof((int*&)Offset.Memp)
82 {
83 G = NULL;
84 Dup =NULL;
85 Cons = cns;
86 Thresh = th;
87 Mthresh = mth;
88 Nitem = 0;
89 Index = Nmblk;
90 Offset = Nmblk;
91 Swix = NULL;
92 Savmax = 0;
93 Savcur = 0;
94 Savstep = NULL;
95 } // end of CSORT constructor
96
97 /***********************************************************************/
98 /* CSORT intialization. */
99 /***********************************************************************/
Qsort(PGLOBAL g,int nb)100 int CSORT::Qsort(PGLOBAL g, int nb)
101 {
102 int rc;
103
104 #if defined(_DEBUG)
105 assert(Index.Size >= nb * sizeof(int));
106 #endif
107
108 if (nb > BIGSORT) {
109 G = g;
110 Dup = (PDBUSER)g->Activityp->Aptr;
111
112 if (Dup->Proginfo) {
113 Savstep = Dup->Step;
114 Savmax = Dup->ProgMax;
115 Savcur = Dup->ProgCur;
116
117 // Evaluate the number of comparisons that we will do
118 Dup->ProgMax = Cmpnum(nb);
119 Dup->ProgCur = 0;
120 Dup->Step = (char*)PlugSubAlloc(g, NULL, 32);
121 sprintf((char*)Dup->Step, MSG(SORTING_VAL), nb);
122 } else
123 Dup = NULL;
124
125 } else
126 Dup = NULL;
127
128 Nitem = nb;
129
130 for (int n = 0; n < Nitem; n++)
131 Pex[n] = n;
132
133 rc = (Cons) ? Qsortc() : Qsortx();
134
135 if (Dup) {
136 // Restore any change in progress info settings
137 // printf("Progcur=%u\n", Dup->ProgCur);
138
139 Dup->Step = Savstep;
140 Dup->ProgMax = Savmax;
141 Dup->ProgCur = Savcur;
142 } // endif Subcor
143
144 return rc;
145 } // end of QSort
146
147 #if defined(DEBTRACE)
148 /***********************************************************************/
149 /* Debug routine to be used by sort for specific data (dummy as now) */
150 /***********************************************************************/
DebugSort(int ph,int n,int * base,int * mid,int * tmp)151 void CSORT::DebugSort(int ph, int n, int *base, int *mid, int *tmp)
152 {
153 htrc("phase=%d n=%d base=%p mid=%p tmp=%p\n",
154 ph, n, base, mid, tmp);
155 } // end of DebugSort
156 #endif
157
158 /***********************************************************************/
159 /* Qsortx: Version adapted from qsortx.c by O.Bertrand */
160 /* This version is specialy adapted for Index sorting, meaning that */
161 /* the data is not moved, but the Index only is sorted. */
162 /* Index array elements are any 4-byte word (a pointer or a int int */
163 /* array index), they are not interpreted except by the user provided */
164 /* comparison routine which must works accordingly. */
165 /* In addition, this program takes care of data in which there is a */
166 /* high rate of repetitions. */
167 /* CAUTION: the sort algorithm used here is not conservative. Equal */
168 /* values will be internally stored in unpredictable order. */
169 /* The THRESHold below is the insertion sort threshold, and also the */
170 /* threshold for continuing que quicksort partitioning. */
171 /* The MTHREShold is where we stop finding a better median. */
172 /* These two quantities should be adjusted dynamically depending upon */
173 /* the repetition rate of the data. */
174 /* Algorithm used: */
175 /* First, set up some global parameters for Qstx to share. Then, */
176 /* quicksort with Qstx(), and then a cleanup insertion sort ourselves. */
177 /* Sound simple? It's not... */
178 /***********************************************************************/
Qsortx(void)179 int CSORT::Qsortx(void)
180 {
181 int c;
182 int lo, hi, min;
183 int i, j, rc = 0;
184 // To do: rc should be checked for being used uninitialized
185 int *top;
186 #ifdef DEBTRACE
187 int ncp;
188
189 num_comp = 0;
190 #endif
191
192 /*********************************************************************/
193 /* Prepare the Offset array that will be updated during sorts. */
194 /*********************************************************************/
195 if (Pof)
196 for (Pof[Nitem] = Nitem, j = 0; j < Nitem; j++)
197 Pof[j] = 0;
198 else
199 j = Nitem + 1;
200
201 /*********************************************************************/
202 /* Sort on one or zero element is obvious. */
203 /*********************************************************************/
204 if (Nitem <= 1)
205 return Nitem;
206
207 /*********************************************************************/
208 /* Thresh seems to be good as (10 * n / rep). But for testing we */
209 /* set it directly as one parameter of the Xset function call. */
210 /* Note: this should be final as the rep parameter is no more used. */
211 /*********************************************************************/
212 top = Pex + Nitem;
213
214 #ifdef DEBTRACE
215 htrc("Qsortx: nitem=%d thresh=%d mthresh=%d\n",
216 Nitem, Thresh, Mthresh);
217 #endif
218
219 /*********************************************************************/
220 /* If applicable, do a rough preliminary quick sort. */
221 /*********************************************************************/
222 if (Nitem >= Thresh)
223 Qstx(Pex, top);
224
225 #ifdef DEBTRACE
226 htrc(" after quick sort num_comp=%d\n", num_comp);
227 ncp = num_comp;
228 num_comp = 0;
229 #ifdef DEBUG2
230 DebugSort((Pof) ? 1 : 4, Nitem, Pex, NULL, NULL);
231 #endif
232 #endif
233
234 if (Thresh > 2) {
235 if (Pof)
236 /*****************************************************************/
237 /* The preliminary search for the smallest element has been */
238 /* removed so with no sentinel in place, we must check for x */
239 /* going below the Pof pointer. For each remaining element */
240 /* group from [1] to [n-1], set hi to the index of the element */
241 /* AFTER which this one goes. Then, do the standard insertion */
242 /* sort shift on an integer at a time basis for each equal */
243 /* element group in the frob. */
244 /*****************************************************************/
245 for (min = hi = 0; min < Nitem; min = hi) {
246 if (Pof[hi]) {
247 hi += Pof[hi];
248 continue;
249 } // endif Pof
250
251 Pof[min] = 1;
252
253 #ifdef DEBUG2
254 htrc("insert from min=%d\n", min);
255 #endif
256
257 for (lo = hi; !Pof[++hi]; lo = hi) {
258 while (lo >= min && (rc = Qcompare(Pex + lo, Pex + hi)) > 0)
259 if (Pof[lo] > 0)
260 lo -= Pof[lo];
261 else
262 return -2;
263
264 if (++lo != hi) {
265 c = Pex[hi];
266
267 for (i = j = hi; i > 0; i = j)
268 if (Pof[i - 1] <= 0)
269 return -3;
270 else if ((j -= Pof[i - 1]) >= lo) {
271 Pex[i] = Pex[j];
272 Pof[j + 1] = Pof[i] = Pof[j];
273 } else
274 break;
275
276 Pex[i] = c;
277 } // endif lo
278
279 if (rc)
280 Pof[lo] = 1;
281 else {
282 i = lo - Pof[lo - 1];
283 Pof[lo] = ++Pof[i];
284 } // endelse
285
286 #ifdef DEBUG2
287 htrc("rc=%d lo=%d hi=%d trx=%d\n", rc, lo, hi, Pof[lo]);
288 #endif
289
290 } // endfor hi
291
292 } // endfor min
293
294 else
295 /*****************************************************************/
296 /* Call conservative insertion sort not using/setting offset. */
297 /*****************************************************************/
298 Istc(Pex, Pex + MY_MIN(Nitem, Thresh), top);
299
300 } // endif Thresh
301
302 #ifdef DEBTRACE
303 htrc(" after insert sort num_comp=%d\n", num_comp);
304 num_comp += ncp;
305 #endif
306
307 if (Pof)
308 /*******************************************************************/
309 /* Reduce the Offset array. */
310 /*******************************************************************/
311 for (i = j = 0; i <= Nitem; j++, i += c) {
312 #ifdef DEBUG2
313 htrc(" trxp(%d)=%d trxp(%d)=%d c=%d\n",
314 i, Pof[i], j, Pof[j], c);
315 #endif
316 if ((c = Pof[i]))
317 Pof[j] = i;
318 else
319 return -4;
320
321 } // endfor i
322
323 return (j - 1);
324 } // end of Qsortx
325
326 /***********************************************************************/
327 /* Qstx: Do a quicksort on index elements (just one int int). */
328 /* First, find the median element, and put that one in the first place */
329 /* as the discriminator. (This "median" is just the median of the */
330 /* first, last and middle elements). (Using this median instead of */
331 /* the first element is a big win). Then, the usual partitioning/ */
332 /* swapping, followed by moving the discriminator into the right place.*/
333 /* Element equal to the discriminator are placed against it, so the */
334 /* mid (discriminator) block grows when equal elements exist. This is */
335 /* a huge win in case of repartitions with few different elements. */
336 /* The mid block being at its final position, its first and last */
337 /* elements are marked in the offset list (used to make break list). */
338 /* Then, figure out the sizes of the two partitions, do the smaller */
339 /* one recursively and the larger one via a repeat of this code. */
340 /* Stopping when there are less than THRESH elements in a partition */
341 /* and cleaning up with an insertion sort (in our caller) is a huge */
342 /* win(?). All data swaps are done in-line, which is space-losing but */
343 /* time-saving. (And there are only three places where this is done). */
344 /***********************************************************************/
Qstx(int * base,int * max)345 void CSORT::Qstx(int *base, int *max)
346 {
347 int *i, *j, *jj, *mid, *him, c;
348 int *tmp;
349 int lo, hi, rc;
350 size_t zlo, zhi, cnm;
351
352 zlo = zhi = cnm = 0; // Avoid warning message
353
354 lo = (int)(max - base); // Number of elements as longs
355
356 if (Dup)
357 cnm = Cmpnum(lo);
358
359 do {
360 /*******************************************************************/
361 /* At the top here, lo is the number of integers of elements in */
362 /* the current partition. (Which should be max - base). */
363 /* Find the median of the first, last, and middle element and make */
364 /* that the middle element. Set j to largest of first and middle. */
365 /* If max is larger than that guy, then it's that guy, else */
366 /* compare max with loser of first and take larger. Things are */
367 /* set up to prefer the middle, then the first in case of ties. */
368 /* In addition, hi and rc are set to comparison results. So if hi */
369 /* is null, the two high values are equal and if rc is null, the */
370 /* two low values are equal. This was used to set which test will */
371 /* be made by LE and which one by LT (does not apply anymore). */
372 /*******************************************************************/
373 him = mid = i = base + (lo >> 1);
374 hi = rc = 0;
375
376 #ifdef DEBTRACE
377 tmp = max - 1;
378 htrc("--> block base=%d size=%d\n", base - Pex, lo);
379 DebugSort(2, 0, base, mid, tmp);
380 #endif
381
382 if (lo >= Mthresh) {
383 rc = Qcompare((jj = base), i);
384 j = (rc > 0) ? jj : i;
385 hi = Qcompare(j, (tmp = max - 1));
386
387 if (hi > 0 && rc) {
388 j = (j == jj) ? i : jj; // switch to first loser
389
390 if ((rc = Qcompare(j, tmp)) < 0)
391 j = tmp;
392
393 } // endif
394
395 if (j != i) {
396 c = *i;
397 *i = *j;
398 *j = c;
399 } // endif j
400
401 } else if (lo == 2) {
402 /*****************************************************************/
403 /* Small group. Do special quicker processing. */
404 /*****************************************************************/
405 if ((rc = Qcompare(base, (him = base + 1))) > 0)
406 c = *base, *base = *him, *him = c;
407
408 if (Pof)
409 Pof[base - Pex] = Pof[him - Pex] = (rc) ? 1 : 2;
410
411 break;
412 } // endif lo
413
414 #ifdef DEBTRACE
415 DebugSort(3, hi, NULL, mid, &rc);
416 #endif
417
418 /*******************************************************************/
419 /* Semi-standard quicksort partitioning/swapping. Added here is */
420 /* a test on equality. All values equal to the mid element are */
421 /* placed under or over it. Mid block can be also moved when it */
422 /* is necessary because the other partition is full. At the end */
423 /* of the for loop the mid block is definitely positionned. */
424 /*******************************************************************/
425 for (i = base, j = max - 1; ;) {
426 CONT:
427 while (i < mid)
428 if ((rc = Qcompare(i, mid)) < 0)
429 i++;
430 else if (!rc) {
431 c = *i;
432 *i = *(--mid);
433 *mid = c;
434 } else
435 break;
436
437 while (j > him)
438 if ((rc = Qcompare(him, j)) < 0)
439 j--;
440 else if (!rc) {
441 c = *j;
442 *j = *(++him);
443 *him = c;
444 } else if (i == mid) { // Triple move:
445 c = *j; // j goes under mid block
446 *j = *(++him); // val over mid block -> j
447 *him = *mid++; // and mid block goes one
448 *i++ = c; // position higher.
449 } else { // i <-> j
450 c = *i;
451 *i++ = *j;
452 *j-- = c;
453 goto CONT;
454 } // endif's
455
456 if (i == mid)
457 break;
458 else { // Triple move:
459 c = *i; // i goes over mid block
460 *i = *(--mid); // val under mid block -> i
461 *mid = *him--; // and mid block goes one
462 *j-- = c; // position lower.
463 } // endelse
464
465 } // endfor i
466
467 /*******************************************************************/
468 /* The mid block being placed at its final position we can now set */
469 /* the offset array values indicating break point and block size. */
470 /*******************************************************************/
471 j = mid;
472 i = him + 1;
473
474 if (Pof)
475 Pof[him - Pex] = Pof[mid - Pex] = (int)(i - j);
476
477 /*******************************************************************/
478 /* Look at sizes of the two partitions, do the smaller one first */
479 /* by recursion, then do the larger one by making sure lo is its */
480 /* size, base and max are update correctly, and branching back. */
481 /* But only repeat (recursively or by branching) if the partition */
482 /* is of at least size THRESH. */
483 /*******************************************************************/
484 lo = (int)(j - base);
485 hi = (int)(max - i);
486
487 if (Dup) { // Update progress information
488 zlo = Cmpnum(lo);
489 zhi = Cmpnum(hi);
490 Dup->ProgCur += cnm - (zlo + zhi);
491 } // endif Dup
492
493 #ifdef DEBTRACE
494 htrc(" done lo=%d sep=%d hi=%d\n", lo, i - j, hi);
495 #endif
496
497 if (lo <= hi) {
498 if (lo >= Thresh)
499 Qstx(base, j);
500 else if (lo == 1 && Pof)
501 Pof[base - Pex] = 1;
502
503 base = i;
504 lo = hi;
505 cnm = zhi;
506 } else {
507 if (hi >= Thresh)
508 Qstx(i, max);
509 else if (hi == 1 && Pof)
510 Pof[i - Pex] = 1;
511
512 max = j;
513 cnm = zlo;
514 } // endif
515
516 if (lo == 1 && Pof)
517 Pof[base - Pex] = 1;
518
519 } while (lo >= Thresh); // enddo
520
521 } // end of Qstx
522
523 /***********************************************************************/
524 /* Qsortc.c: Version adapted from qsort.c by O.Bertrand */
525 /* This version is specialy adapted for Index sorting, meaning that */
526 /* the data is not moved, but the Index only is sorted. */
527 /* Index array elements are any 4-byte word (a pointer or a int int */
528 /* array index), they are not interpreted except by the user provided */
529 /* comparison routine which must works accordingly. */
530 /* In addition, this program takes care of data in which there is a */
531 /* high rate of repetitions. */
532 /* NOTE: the sort algorithm used here is conservative. Equal and */
533 /* greater than values are internally stored in additional work area. */
534 /* The THRESHold below is the insertion sort threshold, and also the */
535 /* threshold for continuing que quicksort partitioning. */
536 /* The MTHREShold is where we stop finding a better median. */
537 /* These two quantities should be adjusted dynamically depending upon */
538 /* the repetition rate of the data. */
539 /* Algorithm used: */
540 /* First, set up some global parameters for Qstc to share. Then, */
541 /* quicksort with Qstc(), and then a cleanup insertion sort ourselves.*/
542 /* Sound simple? It's not... */
543 /***********************************************************************/
Qsortc(void)544 int CSORT::Qsortc(void)
545 {
546 int c;
547 int lo, hi, min;
548 int i, j, k, m, rc = 0;
549 // To do: rc should be checked for being used uninitialized
550 int *max;
551 #ifdef DEBTRACE
552 int ncp;
553
554 num_comp = 0;
555 #endif
556
557 /*********************************************************************/
558 /* Prepare the Offset array that will be updated during sorts. */
559 /*********************************************************************/
560 if (Pof)
561 for (Pof[Nitem] = Nitem, j = 0; j < Nitem; j++)
562 Pof[j] = 0;
563 else
564 j = Nitem + 1;
565
566 /*********************************************************************/
567 /* Sort on one or zero element is obvious. */
568 /*********************************************************************/
569 if (Nitem <= 1)
570 return Nitem;
571
572 /*********************************************************************/
573 /* Thresh seems to be good as (10 * n / rep). But for testing we */
574 /* set it directly as one parameter of the Xset function call. */
575 /* Note: this should be final as the rep parameter is no more used. */
576 /*********************************************************************/
577 max = Pex + Nitem;
578
579 #ifdef DEBTRACE
580 htrc("Qsortc: nitem=%d thresh=%d mthresh=%d\n",
581 Nitem, Thresh, Mthresh);
582 #endif
583
584 /*********************************************************************/
585 /* If applicable, do a rough preliminary conservative quick sort. */
586 /*********************************************************************/
587 if (Nitem >= Thresh) {
588 if (!(Swix = (int *)malloc(Nitem * sizeof(int))))
589 return -1;
590
591 Qstc(Pex, max);
592
593 free(Swix);
594 Swix = NULL;
595 } // endif n
596
597 #ifdef DEBTRACE
598 htrc(" after quick sort num_comp=%d\n", num_comp);
599 ncp = num_comp;
600 num_comp = 0;
601 #ifdef DEBUG2
602 DebugSort((Pof) ? 1 : 4, Nitem, Pex, NULL, NULL);
603 #endif
604 #endif
605
606 if (Thresh > 2) {
607 if (Pof)
608 /*****************************************************************/
609 /* The preliminary search for the smallest element has been */
610 /* removed so with no sentinel in place, we must check for x */
611 /* going below the Pof pointer. For each remaining element */
612 /* group from [1] to [n-1], set hi to the index of the element */
613 /* AFTER which this one goes. Then, do the standard insertion */
614 /* sort shift on an integer at a time basis for each equal */
615 /* element group in the frob. */
616 /*****************************************************************/
617 for (min = hi = 0; min < Nitem; min = hi) {
618 if (Pof[hi]) {
619 hi += Pof[hi];
620 continue;
621 } // endif
622
623 Pof[min] = 1;
624
625 #ifdef DEBUG2
626 htrc("insert from min=%d\n", min);
627 #endif
628
629 for (lo = hi; !Pof[++hi]; lo = hi) {
630 while (lo >= min && (rc = Qcompare(Pex + lo, Pex + hi)) > 0)
631 if (Pof[lo] > 0)
632 lo -= Pof[lo];
633 else
634 return -2;
635
636 if (++lo != hi) {
637 c = Pex[hi];
638
639 for (i = j = hi; i > 0; i = j)
640 if (Pof[i - 1] <= 0)
641 return -3;
642 else if ((j -= Pof[i - 1]) >= lo) {
643 for (k = m = i; --m >= j; k--) // Move intermediate
644 Pex[k] = Pex[m]; // for conservation.
645
646 Pof[j + 1] = Pof[i] = Pof[j];
647 } else
648 break;
649
650 Pex[i] = c;
651 } // endif
652
653 if (rc)
654 Pof[lo] = 1;
655 else {
656 i = lo - Pof[lo - 1];
657 Pof[lo] = ++Pof[i];
658 } // endelse
659
660 #ifdef DEBUG2
661 htrc("rc=%d lo=%d hi=%d ofx=%d\n", rc, lo, hi, Pof[lo]);
662 #endif
663
664 } // endfor hi
665
666 } // endfor min
667
668 else
669 /*****************************************************************/
670 /* Call conservative insertion sort not using/setting offset. */
671 /*****************************************************************/
672 Istc(Pex, Pex + MY_MIN(Nitem, Thresh), max);
673
674 } // endif Thresh
675
676 #ifdef DEBTRACE
677 htrc(" after insert sort num_comp=%d\n", num_comp);
678 num_comp += ncp;
679 #endif
680
681 if (Pof)
682 /*******************************************************************/
683 /* Reduce the Offset array. */
684 /*******************************************************************/
685 for (i = j = 0; i <= Nitem; j++, i += c) {
686 #ifdef DEBUG2
687 htrc(" Pof(%d)=%d Pof(%d)=%d c=%d\n",
688 i, Pof[i], j, Pof[j], c);
689 #endif
690 if ((c = Pof[i]))
691 Pof[j] = i;
692 else
693 return -4;
694
695 } // endfor i
696
697 return (j - 1);
698 } // end of Qsortc
699
700 /***********************************************************************/
701 /* Qstc: Do a quicksort on index elements (just one int int). */
702 /* First, find the median element, and set it as the discriminator. */
703 /* (This "median" is just the median of the first, last and middle */
704 /* elements). (Using this median instead of the first element is a */
705 /* big win). Then, the special partitioning/swapping, where elements */
706 /* smaller than the discriminator are placed in the sorted block, */
707 /* elements equal to the discriminator are placed backward from the */
708 /* top of the work area and elements greater than *j (discriminator) */
709 /* are placed in the work area from its bottom. Then the elements in */
710 /* the work area are placed back in the sort area in natural order, */
711 /* making the sort conservative. Non equal blocks shrink faster when */
712 /* equal elements exist. This is a huge win in case of repartitions */
713 /* with few different elements. The mid block being at its final */
714 /* position, its first and last elements are marked in the offset */
715 /* list (used to make break list). Then, figure out the sizes of the */
716 /* two partitions, do the smaller one recursively and the larger one */
717 /* via a repeat of this code. Stopping when there are less than */
718 /* THRESH elements in a partition and cleaning up with an insertion */
719 /* sort (in our caller) is a huge win (yet to be proved?). */
720 /***********************************************************************/
Qstc(int * base,int * max)721 void CSORT::Qstc(int *base, int *max)
722 {
723 int *i, *j, *jj, *lt, *eq, *gt, *mid;
724 int c = 0, lo, hi, rc;
725 size_t zlo, zhi, cnm;
726
727 zlo = zhi = cnm = 0; // Avoid warning message
728
729 lo = (int)(max - base); // Number of elements as longs
730
731 if (Dup)
732 cnm = Cmpnum(lo);
733
734 do {
735 /*******************************************************************/
736 /* At the top here, lo is the number of integers of elements in */
737 /* the current partition. (Which should be max - base). Find the */
738 /* median of the first, last, and middle element and make that */
739 /* the compare element. Set jj to smallest of middle and last. */
740 /* If base is smaller or equal than that guy, then it's that guy, */
741 /* else compare base with loser of first and take smaller. Things */
742 /* are set up to prefer the top, then the middle in case of ties. */
743 /*******************************************************************/
744 i = base + (lo >> 1);
745 jj = mid = max - 1;
746
747 #ifdef DEBTRACE
748 htrc("--> block base=%d size=%d\n", base - Pex, lo);
749 DebugSort(2, 0, base, i, mid);
750 #endif
751
752 if (lo >= Mthresh) {
753 jj = ((rc = Qcompare(i, mid)) < 0) ? i : mid;
754
755 if (rc && Qcompare(base, jj) > 0) {
756 jj = (jj == mid) ? i : mid; // switch to first loser
757
758 if (Qcompare(base, jj) < 0)
759 jj = base;
760
761 } // endif
762
763 if (jj != mid) {
764 /***************************************************************/
765 /* The compare element must be at the top of the block so it */
766 /* cannot be overwritten while making the partitioning. So */
767 /* save the last block value which will be compared later. */
768 /***************************************************************/
769 c = *mid;
770 *mid = *jj;
771 } // endif
772
773 } else if (lo == 2) {
774 /*****************************************************************/
775 /* Small group. Do special quicker processing. */
776 /*****************************************************************/
777 if ((rc = Qcompare(base, (i = base + 1))) > 0) {
778 c = *base;
779 *base = *i;
780 *i = c;
781 } // endif rc
782
783 if (Pof)
784 Pof[base - Pex] = Pof[i - Pex] = (rc) ? 1 : 2;
785
786 break;
787 } // endif lo
788
789 #ifdef DEBTRACE
790 DebugSort(3, lo, NULL, jj, &rc);
791 #endif
792
793 /*******************************************************************/
794 /* Non-standard quicksort partitioning using additional storage */
795 /* to store values less than, equal or greater than the middle */
796 /* element. This uses more memory but provides conservation of */
797 /* the equal elements order. */
798 /*******************************************************************/
799 lt = base;
800 eq = Swix + lo;
801 gt = Swix;
802
803 if (jj == mid) {
804 /*****************************************************************/
805 /* Compare element was last. No problem. */
806 /*****************************************************************/
807 for (i = base; i < max; i++)
808 if ((rc = Qcompare(i, mid)) < 0)
809 *lt++ = *i;
810 else if (rc > 0)
811 *gt++ = *i;
812 else
813 *--eq = *i;
814
815 } else {
816 /*****************************************************************/
817 /* Compare element was not last and was copied to top of block. */
818 /*****************************************************************/
819 for (i = base; i < mid; i++)
820 if ((rc = Qcompare(i, mid)) < 0)
821 *lt++ = *i;
822 else if (rc > 0)
823 *gt++ = *i;
824 else
825 *--eq = *i;
826
827 /*****************************************************************/
828 /* Restore saved last value and do the comparison from there. */
829 /*****************************************************************/
830 *--i = c;
831
832 if ((rc = Qcompare(i, mid)) < 0)
833 *lt++ = *i;
834 else if (rc > 0)
835 *gt++ = *i;
836 else
837 *--eq = *i;
838
839 } // endif
840
841 /*******************************************************************/
842 /* Now copy the equal and greater values back in the main array in */
843 /* the same order they have been placed in the work area. */
844 /*******************************************************************/
845 for (j = Swix + lo, i = lt; j > eq; )
846 *i++ = *--j;
847
848 for (j = Swix, jj = i; j < gt; )
849 *i++ = *j++;
850
851 /*******************************************************************/
852 /* The mid block being placed at its final position we can now set */
853 /* the offset array values indicating break point and block size. */
854 /*******************************************************************/
855 if (Pof)
856 Pof[lt - Pex] = Pof[(jj - 1) - Pex] = (int)(jj - lt);
857
858 /*******************************************************************/
859 /* Look at sizes of the two partitions, do the smaller one first */
860 /* by recursion, then do the larger one by making sure lo is its */
861 /* size, base and max are update correctly, and branching back. */
862 /* But only repeat (recursively or by branching) if the partition */
863 /* is of at least size THRESH. */
864 /*******************************************************************/
865 lo = (int)(lt - base);
866 hi = (int)(gt - Swix);
867
868 if (Dup) { // Update progress information
869 zlo = Cmpnum(lo);
870 zhi = Cmpnum(hi);
871 Dup->ProgCur += cnm - (zlo + zhi);
872 } // endif Dup
873
874 #ifdef DEBTRACE
875 htrc(" done lo=%d hi=%d\n",
876 lo, /*Swix + lt - base - eq,*/ hi);
877 #endif
878
879 if (lo <= hi) {
880 if (lo >= Thresh)
881 Qstc(base, lt);
882 else if (lo == 1 && Pof)
883 Pof[base - Pex] = 1;
884
885 base = jj;
886 lo = hi;
887 cnm = zhi;
888 } else {
889 if (hi >= Thresh)
890 Qstc(jj, max);
891 else if (hi == 1 && Pof)
892 Pof[jj - Pex] = 1;
893
894 max = lt;
895 cnm = zlo;
896 } // endif
897
898 if (lo == 1 && Pof)
899 Pof[base - Pex] = 1;
900
901 } while (lo >= Thresh); // enddo
902
903 } // end of Qstc
904
905 /***********************************************************************/
906 /* Conservative insertion sort not using/setting offset array. */
907 /***********************************************************************/
Istc(int * base,int * hi,int * max)908 void CSORT::Istc(int *base, int *hi, int *max)
909 {
910 int c = 0;
911 int *lo;
912 int *i, *j;
913
914 /*********************************************************************/
915 /* First put smallest element, which must be in the first THRESH, */
916 /* in the first position as a sentinel. This is done just by */
917 /* searching the 1st THRESH elements (or the 1st n if n < THRESH) */
918 /* finding the min, and shifting it into the first position. */
919 /*********************************************************************/
920 for (j = lo = base; ++lo < hi; )
921 if (Qcompare(j, lo) > 0)
922 j = lo;
923
924 if (j != base) { // shift j into place
925 c = *j;
926
927 for (i = j; --j >= base; i = j)
928 *i = *j;
929
930 *base = c;
931 } // endif j
932
933 #ifdef DEBTRACE
934 htrc("sentinel %d in place, base=%p hi=%p max=%p\n",
935 c, base, hi, max);
936 #endif
937
938 /*********************************************************************/
939 /* With our sentinel in place, we now run the following hyper- */
940 /* fast insertion sort. For each remaining element, lo, from [1] */
941 /* to [n-1], set hi to the index of the element AFTER which this */
942 /* one goes. Then, do the standard insertion sort shift for each */
943 /* element in the frob. */
944 /*********************************************************************/
945 for (lo = base; (hi = ++lo) < max;) {
946 while (Qcompare(--hi, lo) > 0) ;
947
948 #ifdef DEBUG2
949 htrc("after while: hi(%p)=%d lo(%p)=%d\n",
950 hi, *hi, lo, *lo);
951 #endif
952
953 if (++hi != lo) {
954 c = *lo;
955
956 for (i = j = lo; --j >= hi; i = j)
957 *i = *j;
958
959 *i = c;
960 } // endif hi
961
962 } // endfor lo
963
964 } // end of Istc
965
966 /* -------------------------- End of CSort --------------------------- */
967