1*7c478bd9Sstevel@tonic-gate /* 2*7c478bd9Sstevel@tonic-gate * CDDL HEADER START 3*7c478bd9Sstevel@tonic-gate * 4*7c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the 5*7c478bd9Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only 6*7c478bd9Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance 7*7c478bd9Sstevel@tonic-gate * with the License. 8*7c478bd9Sstevel@tonic-gate * 9*7c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10*7c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 11*7c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions 12*7c478bd9Sstevel@tonic-gate * and limitations under the License. 13*7c478bd9Sstevel@tonic-gate * 14*7c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 15*7c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16*7c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 17*7c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 18*7c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 19*7c478bd9Sstevel@tonic-gate * 20*7c478bd9Sstevel@tonic-gate * CDDL HEADER END 21*7c478bd9Sstevel@tonic-gate */ 22*7c478bd9Sstevel@tonic-gate /* 23*7c478bd9Sstevel@tonic-gate * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 24*7c478bd9Sstevel@tonic-gate * Use is subject to license terms. 25*7c478bd9Sstevel@tonic-gate */ 26*7c478bd9Sstevel@tonic-gate 27*7c478bd9Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 28*7c478bd9Sstevel@tonic-gate 29*7c478bd9Sstevel@tonic-gate 30*7c478bd9Sstevel@tonic-gate #if !defined(_KERNEL) && !defined(_KMDB) 31*7c478bd9Sstevel@tonic-gate #include "synonyms.h" 32*7c478bd9Sstevel@tonic-gate #endif /* !_KERNEL && !_KMDB */ 33*7c478bd9Sstevel@tonic-gate 34*7c478bd9Sstevel@tonic-gate #include <sys/types.h> 35*7c478bd9Sstevel@tonic-gate 36*7c478bd9Sstevel@tonic-gate #if !defined(_KERNEL) && !defined(_KMDB) 37*7c478bd9Sstevel@tonic-gate #include <stdlib.h> 38*7c478bd9Sstevel@tonic-gate #include <mtlib.h> 39*7c478bd9Sstevel@tonic-gate #include <synch.h> 40*7c478bd9Sstevel@tonic-gate #endif /* !_KERNEL && !_KMDB */ 41*7c478bd9Sstevel@tonic-gate 42*7c478bd9Sstevel@tonic-gate #include "qsort.h" 43*7c478bd9Sstevel@tonic-gate 44*7c478bd9Sstevel@tonic-gate static void swapp32(uint32_t *r1, uint32_t *r2, size_t cnt); 45*7c478bd9Sstevel@tonic-gate static void swapp64(uint64_t *r1, uint64_t *r2, size_t cnt); 46*7c478bd9Sstevel@tonic-gate static void swapi(uint32_t *r1, uint32_t *r2, size_t cnt); 47*7c478bd9Sstevel@tonic-gate static void swapb(char *r1, char *r2, size_t cnt); 48*7c478bd9Sstevel@tonic-gate 49*7c478bd9Sstevel@tonic-gate /* 50*7c478bd9Sstevel@tonic-gate * choose a median of 3 values 51*7c478bd9Sstevel@tonic-gate * 52*7c478bd9Sstevel@tonic-gate * note: cstyle specifically prohibits nested conditional operators 53*7c478bd9Sstevel@tonic-gate * but this is the only way to do the median of 3 function in-line 54*7c478bd9Sstevel@tonic-gate */ 55*7c478bd9Sstevel@tonic-gate #define med3(a, b, c) (cmp((a), (b)) < 0) \ 56*7c478bd9Sstevel@tonic-gate ? ((cmp((b), (c)) < 0) ? (b) : (cmp((a), (c)) < 0) ? (c) : (a)) \ 57*7c478bd9Sstevel@tonic-gate : ((cmp((b), (c)) > 0) ? (b) : (cmp((a), (c)) > 0) ? (c) : (a)) 58*7c478bd9Sstevel@tonic-gate 59*7c478bd9Sstevel@tonic-gate #define THRESH_L 5 /* threshold for insertion sort */ 60*7c478bd9Sstevel@tonic-gate #define THRESH_M3 20 /* threshold for median of 3 */ 61*7c478bd9Sstevel@tonic-gate #define THRESH_M9 50 /* threshold for median of 9 */ 62*7c478bd9Sstevel@tonic-gate 63*7c478bd9Sstevel@tonic-gate typedef struct { 64*7c478bd9Sstevel@tonic-gate char *b_lim; 65*7c478bd9Sstevel@tonic-gate size_t nrec; 66*7c478bd9Sstevel@tonic-gate } stk_t; 67*7c478bd9Sstevel@tonic-gate 68*7c478bd9Sstevel@tonic-gate /* 69*7c478bd9Sstevel@tonic-gate * qsort() is a general purpose, in-place sorting routine using a 70*7c478bd9Sstevel@tonic-gate * user provided call back function for comparisons. This implementation 71*7c478bd9Sstevel@tonic-gate * utilizes a ternary quicksort algorithm, and cuts over to an 72*7c478bd9Sstevel@tonic-gate * insertion sort for partitions involving fewer than THRESH_L records. 73*7c478bd9Sstevel@tonic-gate * 74*7c478bd9Sstevel@tonic-gate * Potential User Errors 75*7c478bd9Sstevel@tonic-gate * There is no return value from qsort, this function has no method 76*7c478bd9Sstevel@tonic-gate * of alerting the user that a sort did not work or could not work. 77*7c478bd9Sstevel@tonic-gate * We do not print an error message or exit the process or thread, 78*7c478bd9Sstevel@tonic-gate * Even if we can detect an error, We CANNOT silently return without 79*7c478bd9Sstevel@tonic-gate * sorting the data, if we did so the user could never be sure the 80*7c478bd9Sstevel@tonic-gate * sort completed successfully. 81*7c478bd9Sstevel@tonic-gate * It is possible we could change the return value of sort from void 82*7c478bd9Sstevel@tonic-gate * to int and return success or some error codes, but this gets into 83*7c478bd9Sstevel@tonic-gate * standards and compatibility issues. 84*7c478bd9Sstevel@tonic-gate * 85*7c478bd9Sstevel@tonic-gate * Examples of qsort parameter errors might be 86*7c478bd9Sstevel@tonic-gate * 1) record size (rsiz) equal to 0 87*7c478bd9Sstevel@tonic-gate * qsort will loop and never return. 88*7c478bd9Sstevel@tonic-gate * 2) record size (rsiz) less than 0 89*7c478bd9Sstevel@tonic-gate * rsiz is unsigned, so a negative value is insanely large 90*7c478bd9Sstevel@tonic-gate * 3) number of records (nrec) is 0 91*7c478bd9Sstevel@tonic-gate * This is legal - qsort will return without examining any records 92*7c478bd9Sstevel@tonic-gate * 4) number of records (nrec) is less than 0 93*7c478bd9Sstevel@tonic-gate * nrec is unsigned, so a negative value is insanely large. 94*7c478bd9Sstevel@tonic-gate * 5) nrec * rsiz > memory allocation for sort array 95*7c478bd9Sstevel@tonic-gate * a segment violation may occur 96*7c478bd9Sstevel@tonic-gate * corruption of other memory may occur 97*7c478bd9Sstevel@tonic-gate * 6) The base address of the sort array is invalid 98*7c478bd9Sstevel@tonic-gate * a segment violation may occur 99*7c478bd9Sstevel@tonic-gate * corruption of other memory may occur 100*7c478bd9Sstevel@tonic-gate * 7) The user call back function is invalid 101*7c478bd9Sstevel@tonic-gate * we may get alignment errors or segment violations 102*7c478bd9Sstevel@tonic-gate * we may jump into never-never land 103*7c478bd9Sstevel@tonic-gate * 104*7c478bd9Sstevel@tonic-gate * Some less obvious errors might be 105*7c478bd9Sstevel@tonic-gate * 8) The user compare function is not comparing correctly 106*7c478bd9Sstevel@tonic-gate * 9) The user compare function modifies the data records 107*7c478bd9Sstevel@tonic-gate */ 108*7c478bd9Sstevel@tonic-gate 109*7c478bd9Sstevel@tonic-gate void 110*7c478bd9Sstevel@tonic-gate qsort( 111*7c478bd9Sstevel@tonic-gate void *basep, 112*7c478bd9Sstevel@tonic-gate size_t nrec, 113*7c478bd9Sstevel@tonic-gate size_t rsiz, 114*7c478bd9Sstevel@tonic-gate int (*cmp)(const void *, const void *)) 115*7c478bd9Sstevel@tonic-gate { 116*7c478bd9Sstevel@tonic-gate size_t i; /* temporary variable */ 117*7c478bd9Sstevel@tonic-gate 118*7c478bd9Sstevel@tonic-gate /* variables used by swap */ 119*7c478bd9Sstevel@tonic-gate void (*swapf)(char *, char *, size_t); 120*7c478bd9Sstevel@tonic-gate size_t loops; 121*7c478bd9Sstevel@tonic-gate 122*7c478bd9Sstevel@tonic-gate /* variables used by sort */ 123*7c478bd9Sstevel@tonic-gate stk_t stack[8 * sizeof (nrec) + 1]; 124*7c478bd9Sstevel@tonic-gate stk_t *sp; 125*7c478bd9Sstevel@tonic-gate char *b_lim; /* bottom limit */ 126*7c478bd9Sstevel@tonic-gate char *b_dup; /* bottom duplicate */ 127*7c478bd9Sstevel@tonic-gate char *b_par; /* bottom partition */ 128*7c478bd9Sstevel@tonic-gate char *t_lim; /* top limit */ 129*7c478bd9Sstevel@tonic-gate char *t_dup; /* top duplicate */ 130*7c478bd9Sstevel@tonic-gate char *t_par; /* top partition */ 131*7c478bd9Sstevel@tonic-gate char *m1, *m2, *m3; /* median pointers */ 132*7c478bd9Sstevel@tonic-gate uintptr_t d_bytelength; /* byte length of duplicate records */ 133*7c478bd9Sstevel@tonic-gate int b_nrec; 134*7c478bd9Sstevel@tonic-gate int t_nrec; 135*7c478bd9Sstevel@tonic-gate int cv; /* results of compare (bottom / top) */ 136*7c478bd9Sstevel@tonic-gate 137*7c478bd9Sstevel@tonic-gate /* 138*7c478bd9Sstevel@tonic-gate * choose a swap function based on alignment and size 139*7c478bd9Sstevel@tonic-gate * 140*7c478bd9Sstevel@tonic-gate * The qsort function sorts an array of fixed length records. 141*7c478bd9Sstevel@tonic-gate * We have very limited knowledge about the data record itself. 142*7c478bd9Sstevel@tonic-gate * It may be that the data record is in the array we are sorting 143*7c478bd9Sstevel@tonic-gate * or it may be that the array contains pointers or indexes to 144*7c478bd9Sstevel@tonic-gate * the actual data record and all that we are sorting is the indexes. 145*7c478bd9Sstevel@tonic-gate * 146*7c478bd9Sstevel@tonic-gate * The following decision will choose an optimal swap function 147*7c478bd9Sstevel@tonic-gate * based on the size and alignment of the data records 148*7c478bd9Sstevel@tonic-gate * swapp64 will swap 64 bit pointers 149*7c478bd9Sstevel@tonic-gate * swapp32 will swap 32 bit pointers 150*7c478bd9Sstevel@tonic-gate * swapi will swap an array of 32 bit integers 151*7c478bd9Sstevel@tonic-gate * swapb will swap an array of 8 bit characters 152*7c478bd9Sstevel@tonic-gate * 153*7c478bd9Sstevel@tonic-gate * swapi and swapb will also require the variable loops to be set 154*7c478bd9Sstevel@tonic-gate * to control the length of the array being swapped 155*7c478bd9Sstevel@tonic-gate */ 156*7c478bd9Sstevel@tonic-gate if ((((uintptr_t)basep & (sizeof (uint64_t) - 1)) == 0) && 157*7c478bd9Sstevel@tonic-gate (rsiz == sizeof (uint64_t))) { 158*7c478bd9Sstevel@tonic-gate loops = 1; 159*7c478bd9Sstevel@tonic-gate swapf = (void (*)(char *, char *, size_t))swapp64; 160*7c478bd9Sstevel@tonic-gate } else if ((((uintptr_t)basep & (sizeof (uint32_t) - 1)) == 0) && 161*7c478bd9Sstevel@tonic-gate (rsiz == sizeof (uint32_t))) { 162*7c478bd9Sstevel@tonic-gate loops = 1; 163*7c478bd9Sstevel@tonic-gate swapf = (void (*)(char *, char *, size_t))swapp32; 164*7c478bd9Sstevel@tonic-gate } else if ((((uintptr_t)basep & (sizeof (uint32_t) - 1)) == 0) && 165*7c478bd9Sstevel@tonic-gate ((rsiz & (sizeof (uint32_t) - 1)) == 0)) { 166*7c478bd9Sstevel@tonic-gate loops = rsiz / sizeof (int); 167*7c478bd9Sstevel@tonic-gate swapf = (void (*)(char *, char *, size_t))swapi; 168*7c478bd9Sstevel@tonic-gate } else { 169*7c478bd9Sstevel@tonic-gate loops = rsiz; 170*7c478bd9Sstevel@tonic-gate swapf = swapb; 171*7c478bd9Sstevel@tonic-gate } 172*7c478bd9Sstevel@tonic-gate 173*7c478bd9Sstevel@tonic-gate /* 174*7c478bd9Sstevel@tonic-gate * qsort is a partitioning sort 175*7c478bd9Sstevel@tonic-gate * 176*7c478bd9Sstevel@tonic-gate * the stack is the bookkeeping mechanism to keep track of all 177*7c478bd9Sstevel@tonic-gate * the partitions. 178*7c478bd9Sstevel@tonic-gate * 179*7c478bd9Sstevel@tonic-gate * each sort pass takes one partition and sorts it into two partitions. 180*7c478bd9Sstevel@tonic-gate * at the top of the loop we simply take the partition on the top 181*7c478bd9Sstevel@tonic-gate * of the stack and sort it. See the comments at the bottom 182*7c478bd9Sstevel@tonic-gate * of the loop regarding which partitions to add in what order. 183*7c478bd9Sstevel@tonic-gate * 184*7c478bd9Sstevel@tonic-gate * initially put the whole partition on the stack 185*7c478bd9Sstevel@tonic-gate */ 186*7c478bd9Sstevel@tonic-gate sp = stack; 187*7c478bd9Sstevel@tonic-gate sp->b_lim = (char *)basep; 188*7c478bd9Sstevel@tonic-gate sp->nrec = nrec; 189*7c478bd9Sstevel@tonic-gate sp++; 190*7c478bd9Sstevel@tonic-gate while (sp > stack) { 191*7c478bd9Sstevel@tonic-gate sp--; 192*7c478bd9Sstevel@tonic-gate b_lim = sp->b_lim; 193*7c478bd9Sstevel@tonic-gate nrec = sp->nrec; 194*7c478bd9Sstevel@tonic-gate 195*7c478bd9Sstevel@tonic-gate /* 196*7c478bd9Sstevel@tonic-gate * a linear insertion sort i faster than a qsort for 197*7c478bd9Sstevel@tonic-gate * very small number of records (THRESH_L) 198*7c478bd9Sstevel@tonic-gate * 199*7c478bd9Sstevel@tonic-gate * if number records < threshold use linear insertion sort 200*7c478bd9Sstevel@tonic-gate * 201*7c478bd9Sstevel@tonic-gate * this also handles the special case where the partition 202*7c478bd9Sstevel@tonic-gate * 0 or 1 records length. 203*7c478bd9Sstevel@tonic-gate */ 204*7c478bd9Sstevel@tonic-gate if (nrec < THRESH_L) { 205*7c478bd9Sstevel@tonic-gate /* 206*7c478bd9Sstevel@tonic-gate * Linear insertion sort 207*7c478bd9Sstevel@tonic-gate */ 208*7c478bd9Sstevel@tonic-gate t_par = b_lim; 209*7c478bd9Sstevel@tonic-gate for (i = 1; i < nrec; i++) { 210*7c478bd9Sstevel@tonic-gate t_par += rsiz; 211*7c478bd9Sstevel@tonic-gate b_par = t_par; 212*7c478bd9Sstevel@tonic-gate while (b_par > b_lim) { 213*7c478bd9Sstevel@tonic-gate b_par -= rsiz; 214*7c478bd9Sstevel@tonic-gate if ((*cmp)(b_par, b_par + rsiz) <= 0) { 215*7c478bd9Sstevel@tonic-gate break; 216*7c478bd9Sstevel@tonic-gate } 217*7c478bd9Sstevel@tonic-gate (*swapf)(b_par, b_par + rsiz, loops); 218*7c478bd9Sstevel@tonic-gate } 219*7c478bd9Sstevel@tonic-gate } 220*7c478bd9Sstevel@tonic-gate 221*7c478bd9Sstevel@tonic-gate /* 222*7c478bd9Sstevel@tonic-gate * a linear insertion sort will put all records 223*7c478bd9Sstevel@tonic-gate * in their final position and will not create 224*7c478bd9Sstevel@tonic-gate * subpartitions. 225*7c478bd9Sstevel@tonic-gate * 226*7c478bd9Sstevel@tonic-gate * therefore when the insertion sort is complete 227*7c478bd9Sstevel@tonic-gate * just go to the top of the loop and get the 228*7c478bd9Sstevel@tonic-gate * next partition to sort. 229*7c478bd9Sstevel@tonic-gate */ 230*7c478bd9Sstevel@tonic-gate continue; 231*7c478bd9Sstevel@tonic-gate } 232*7c478bd9Sstevel@tonic-gate 233*7c478bd9Sstevel@tonic-gate /* quicksort */ 234*7c478bd9Sstevel@tonic-gate 235*7c478bd9Sstevel@tonic-gate /* 236*7c478bd9Sstevel@tonic-gate * choose a pivot record 237*7c478bd9Sstevel@tonic-gate * 238*7c478bd9Sstevel@tonic-gate * Ideally the pivot record will divide the partition 239*7c478bd9Sstevel@tonic-gate * into two equal parts. however we have to balance the 240*7c478bd9Sstevel@tonic-gate * work involved in selecting the pivot record with the 241*7c478bd9Sstevel@tonic-gate * expected benefit. 242*7c478bd9Sstevel@tonic-gate * 243*7c478bd9Sstevel@tonic-gate * The choice of pivot record depends on the number of 244*7c478bd9Sstevel@tonic-gate * records in the partition 245*7c478bd9Sstevel@tonic-gate * 246*7c478bd9Sstevel@tonic-gate * for small partitions (nrec < THRESH_M3) 247*7c478bd9Sstevel@tonic-gate * we just select the record in the middle of the partition 248*7c478bd9Sstevel@tonic-gate * 249*7c478bd9Sstevel@tonic-gate * if (nrec >= THRESH_M3 && nrec < THRESH_M9) 250*7c478bd9Sstevel@tonic-gate * we select three values and choose the median of 3 251*7c478bd9Sstevel@tonic-gate * 252*7c478bd9Sstevel@tonic-gate * if (nrec >= THRESH_M9) 253*7c478bd9Sstevel@tonic-gate * then we use an approximate median of 9 254*7c478bd9Sstevel@tonic-gate * 9 records are selected and grouped in 3 groups of 3 255*7c478bd9Sstevel@tonic-gate * the median of each of these 3 groups is fed into another 256*7c478bd9Sstevel@tonic-gate * median of 3 decision. 257*7c478bd9Sstevel@tonic-gate * 258*7c478bd9Sstevel@tonic-gate * Each median of 3 decision is 2 or 3 compares, 259*7c478bd9Sstevel@tonic-gate * so median of 9 costs between 8 and 12 compares. 260*7c478bd9Sstevel@tonic-gate * 261*7c478bd9Sstevel@tonic-gate * i is byte distance between two consecutive samples 262*7c478bd9Sstevel@tonic-gate * m2 will point to the pivot record 263*7c478bd9Sstevel@tonic-gate */ 264*7c478bd9Sstevel@tonic-gate if (nrec < THRESH_M3) { 265*7c478bd9Sstevel@tonic-gate m2 = b_lim + (nrec / 2) * rsiz; 266*7c478bd9Sstevel@tonic-gate } else if (nrec < THRESH_M9) { 267*7c478bd9Sstevel@tonic-gate /* use median of 3 */ 268*7c478bd9Sstevel@tonic-gate i = ((nrec - 1) / 2) * rsiz; 269*7c478bd9Sstevel@tonic-gate m2 = med3(b_lim, b_lim + i, b_lim + 2 * i); 270*7c478bd9Sstevel@tonic-gate } else { 271*7c478bd9Sstevel@tonic-gate /* approx median of 9 */ 272*7c478bd9Sstevel@tonic-gate i = ((nrec - 1) / 8) * rsiz; 273*7c478bd9Sstevel@tonic-gate m1 = med3(b_lim, b_lim + i, b_lim + 2 * i); 274*7c478bd9Sstevel@tonic-gate m2 = med3(b_lim + 3 * i, b_lim + 4 * i, b_lim + 5 * i); 275*7c478bd9Sstevel@tonic-gate m3 = med3(b_lim + 6 * i, b_lim + 7 * i, b_lim + 8 * i); 276*7c478bd9Sstevel@tonic-gate m2 = med3(m1, m2, m3); 277*7c478bd9Sstevel@tonic-gate } 278*7c478bd9Sstevel@tonic-gate 279*7c478bd9Sstevel@tonic-gate /* 280*7c478bd9Sstevel@tonic-gate * quick sort partitioning 281*7c478bd9Sstevel@tonic-gate * 282*7c478bd9Sstevel@tonic-gate * The partition limits are defined by bottom and top pointers 283*7c478bd9Sstevel@tonic-gate * b_lim and t_lim. 284*7c478bd9Sstevel@tonic-gate * 285*7c478bd9Sstevel@tonic-gate * qsort uses a fairly standard method of moving the 286*7c478bd9Sstevel@tonic-gate * partitioning pointers, b_par and t_par, to the middle of 287*7c478bd9Sstevel@tonic-gate * the partition and exchanging records that are in the 288*7c478bd9Sstevel@tonic-gate * wrong part of the partition. 289*7c478bd9Sstevel@tonic-gate * 290*7c478bd9Sstevel@tonic-gate * Two enhancements have been made to the basic algorithm. 291*7c478bd9Sstevel@tonic-gate * One for handling duplicate records and one to minimize 292*7c478bd9Sstevel@tonic-gate * the number of swaps. 293*7c478bd9Sstevel@tonic-gate * 294*7c478bd9Sstevel@tonic-gate * Two duplicate records pointers are (b_dup and t_dup) are 295*7c478bd9Sstevel@tonic-gate * initially set to b_lim and t_lim. Each time a record 296*7c478bd9Sstevel@tonic-gate * whose sort key value is equal to the pivot record is found 297*7c478bd9Sstevel@tonic-gate * it will be swapped with the record pointed to by 298*7c478bd9Sstevel@tonic-gate * b_dup or t_dup and the duplicate pointer will be 299*7c478bd9Sstevel@tonic-gate * incremented toward the center. 300*7c478bd9Sstevel@tonic-gate * When partitioning is complete, all the duplicate records 301*7c478bd9Sstevel@tonic-gate * will have been collected at the upper and lower limits of 302*7c478bd9Sstevel@tonic-gate * the partition and can easily be moved adjacent to the 303*7c478bd9Sstevel@tonic-gate * pivot record. 304*7c478bd9Sstevel@tonic-gate * 305*7c478bd9Sstevel@tonic-gate * The second optimization is to minimize the number of swaps. 306*7c478bd9Sstevel@tonic-gate * The pointer m2 points to the pivot record. 307*7c478bd9Sstevel@tonic-gate * During partitioning, if m2 is ever equal to the partitioning 308*7c478bd9Sstevel@tonic-gate * pointers, b_par or t_par, then b_par or t_par just moves 309*7c478bd9Sstevel@tonic-gate * onto the next record without doing a compare. 310*7c478bd9Sstevel@tonic-gate * If as a result of duplicate record detection, 311*7c478bd9Sstevel@tonic-gate * b_dup or t_dup is ever equal to m2, 312*7c478bd9Sstevel@tonic-gate * then m2 is changed to point to the duplicate record and 313*7c478bd9Sstevel@tonic-gate * b_dup or t_dup is incremented with out swapping records. 314*7c478bd9Sstevel@tonic-gate * 315*7c478bd9Sstevel@tonic-gate * When partitioning is done, we may not have the same pivot 316*7c478bd9Sstevel@tonic-gate * record that we started with, but we will have one with 317*7c478bd9Sstevel@tonic-gate * an equal sort key. 318*7c478bd9Sstevel@tonic-gate */ 319*7c478bd9Sstevel@tonic-gate b_dup = b_par = b_lim; 320*7c478bd9Sstevel@tonic-gate t_dup = t_par = t_lim = b_lim + rsiz * (nrec - 1); 321*7c478bd9Sstevel@tonic-gate for (;;) { 322*7c478bd9Sstevel@tonic-gate 323*7c478bd9Sstevel@tonic-gate /* move bottom pointer up */ 324*7c478bd9Sstevel@tonic-gate for (; b_par <= t_par; b_par += rsiz) { 325*7c478bd9Sstevel@tonic-gate if (b_par == m2) { 326*7c478bd9Sstevel@tonic-gate continue; 327*7c478bd9Sstevel@tonic-gate } 328*7c478bd9Sstevel@tonic-gate cv = cmp(b_par, m2); 329*7c478bd9Sstevel@tonic-gate if (cv > 0) { 330*7c478bd9Sstevel@tonic-gate break; 331*7c478bd9Sstevel@tonic-gate } 332*7c478bd9Sstevel@tonic-gate if (cv == 0) { 333*7c478bd9Sstevel@tonic-gate if (b_dup == m2) { 334*7c478bd9Sstevel@tonic-gate m2 = b_par; 335*7c478bd9Sstevel@tonic-gate } else if (b_dup != b_par) { 336*7c478bd9Sstevel@tonic-gate (*swapf)(b_dup, b_par, loops); 337*7c478bd9Sstevel@tonic-gate } 338*7c478bd9Sstevel@tonic-gate b_dup += rsiz; 339*7c478bd9Sstevel@tonic-gate } 340*7c478bd9Sstevel@tonic-gate } 341*7c478bd9Sstevel@tonic-gate 342*7c478bd9Sstevel@tonic-gate /* move top pointer down */ 343*7c478bd9Sstevel@tonic-gate for (; b_par < t_par; t_par -= rsiz) { 344*7c478bd9Sstevel@tonic-gate if (t_par == m2) { 345*7c478bd9Sstevel@tonic-gate continue; 346*7c478bd9Sstevel@tonic-gate } 347*7c478bd9Sstevel@tonic-gate cv = cmp(t_par, m2); 348*7c478bd9Sstevel@tonic-gate if (cv < 0) { 349*7c478bd9Sstevel@tonic-gate break; 350*7c478bd9Sstevel@tonic-gate } 351*7c478bd9Sstevel@tonic-gate if (cv == 0) { 352*7c478bd9Sstevel@tonic-gate if (t_dup == m2) { 353*7c478bd9Sstevel@tonic-gate m2 = t_par; 354*7c478bd9Sstevel@tonic-gate } else if (t_dup != t_par) { 355*7c478bd9Sstevel@tonic-gate (*swapf)(t_dup, t_par, loops); 356*7c478bd9Sstevel@tonic-gate } 357*7c478bd9Sstevel@tonic-gate t_dup -= rsiz; 358*7c478bd9Sstevel@tonic-gate } 359*7c478bd9Sstevel@tonic-gate } 360*7c478bd9Sstevel@tonic-gate 361*7c478bd9Sstevel@tonic-gate /* break if we are done partitioning */ 362*7c478bd9Sstevel@tonic-gate if (b_par >= t_par) { 363*7c478bd9Sstevel@tonic-gate break; 364*7c478bd9Sstevel@tonic-gate } 365*7c478bd9Sstevel@tonic-gate 366*7c478bd9Sstevel@tonic-gate /* exchange records at upper and lower break points */ 367*7c478bd9Sstevel@tonic-gate (*swapf)(b_par, t_par, loops); 368*7c478bd9Sstevel@tonic-gate b_par += rsiz; 369*7c478bd9Sstevel@tonic-gate t_par -= rsiz; 370*7c478bd9Sstevel@tonic-gate } 371*7c478bd9Sstevel@tonic-gate 372*7c478bd9Sstevel@tonic-gate /* 373*7c478bd9Sstevel@tonic-gate * partitioning is now complete 374*7c478bd9Sstevel@tonic-gate * 375*7c478bd9Sstevel@tonic-gate * there are two termination conditions from the partitioning 376*7c478bd9Sstevel@tonic-gate * loop above. Either b_par or t_par have crossed or 377*7c478bd9Sstevel@tonic-gate * they are equal. 378*7c478bd9Sstevel@tonic-gate * 379*7c478bd9Sstevel@tonic-gate * we need to swap the pivot record to its final position 380*7c478bd9Sstevel@tonic-gate * m2 could be in either the upper or lower partitions 381*7c478bd9Sstevel@tonic-gate * or it could already be in its final position 382*7c478bd9Sstevel@tonic-gate */ 383*7c478bd9Sstevel@tonic-gate /* 384*7c478bd9Sstevel@tonic-gate * R[b_par] > R[m2] 385*7c478bd9Sstevel@tonic-gate * R[t_par] < R[m2] 386*7c478bd9Sstevel@tonic-gate */ 387*7c478bd9Sstevel@tonic-gate if (t_par < b_par) { 388*7c478bd9Sstevel@tonic-gate if (m2 < t_par) { 389*7c478bd9Sstevel@tonic-gate (*swapf)(m2, t_par, loops); 390*7c478bd9Sstevel@tonic-gate m2 = b_par = t_par; 391*7c478bd9Sstevel@tonic-gate } else if (m2 > b_par) { 392*7c478bd9Sstevel@tonic-gate (*swapf)(m2, b_par, loops); 393*7c478bd9Sstevel@tonic-gate m2 = t_par = b_par; 394*7c478bd9Sstevel@tonic-gate } else { 395*7c478bd9Sstevel@tonic-gate b_par = t_par = m2; 396*7c478bd9Sstevel@tonic-gate } 397*7c478bd9Sstevel@tonic-gate } else { 398*7c478bd9Sstevel@tonic-gate if (m2 < t_par) { 399*7c478bd9Sstevel@tonic-gate t_par = b_par = t_par - rsiz; 400*7c478bd9Sstevel@tonic-gate } 401*7c478bd9Sstevel@tonic-gate if (m2 != b_par) { 402*7c478bd9Sstevel@tonic-gate (*swapf)(m2, b_par, loops); 403*7c478bd9Sstevel@tonic-gate } 404*7c478bd9Sstevel@tonic-gate m2 = t_par; 405*7c478bd9Sstevel@tonic-gate } 406*7c478bd9Sstevel@tonic-gate 407*7c478bd9Sstevel@tonic-gate /* 408*7c478bd9Sstevel@tonic-gate * move bottom duplicates next to pivot 409*7c478bd9Sstevel@tonic-gate * optimized to eliminate overlap 410*7c478bd9Sstevel@tonic-gate */ 411*7c478bd9Sstevel@tonic-gate d_bytelength = b_dup - b_lim; 412*7c478bd9Sstevel@tonic-gate if (b_par - b_dup < d_bytelength) { 413*7c478bd9Sstevel@tonic-gate b_dup = b_lim + (b_par - b_dup); 414*7c478bd9Sstevel@tonic-gate } 415*7c478bd9Sstevel@tonic-gate while (b_dup > b_lim) { 416*7c478bd9Sstevel@tonic-gate b_dup -= rsiz; 417*7c478bd9Sstevel@tonic-gate b_par -= rsiz; 418*7c478bd9Sstevel@tonic-gate (*swapf)(b_dup, b_par, loops); 419*7c478bd9Sstevel@tonic-gate } 420*7c478bd9Sstevel@tonic-gate b_par = m2 - d_bytelength; 421*7c478bd9Sstevel@tonic-gate 422*7c478bd9Sstevel@tonic-gate /* 423*7c478bd9Sstevel@tonic-gate * move top duplicates next to pivot 424*7c478bd9Sstevel@tonic-gate */ 425*7c478bd9Sstevel@tonic-gate d_bytelength = t_lim - t_dup; 426*7c478bd9Sstevel@tonic-gate if (t_dup - t_par < d_bytelength) { 427*7c478bd9Sstevel@tonic-gate t_dup = t_lim - (t_dup - t_par); 428*7c478bd9Sstevel@tonic-gate } 429*7c478bd9Sstevel@tonic-gate while (t_dup < t_lim) { 430*7c478bd9Sstevel@tonic-gate t_dup += rsiz; 431*7c478bd9Sstevel@tonic-gate t_par += rsiz; 432*7c478bd9Sstevel@tonic-gate (*swapf)(t_dup, t_par, loops); 433*7c478bd9Sstevel@tonic-gate } 434*7c478bd9Sstevel@tonic-gate t_par = m2 + d_bytelength; 435*7c478bd9Sstevel@tonic-gate 436*7c478bd9Sstevel@tonic-gate /* 437*7c478bd9Sstevel@tonic-gate * when a qsort pass completes there are three partitions 438*7c478bd9Sstevel@tonic-gate * 1) the lower contains all records less than pivot 439*7c478bd9Sstevel@tonic-gate * 2) the upper contains all records greater than pivot 440*7c478bd9Sstevel@tonic-gate * 3) the pivot partition contains all record equal to pivot 441*7c478bd9Sstevel@tonic-gate * 442*7c478bd9Sstevel@tonic-gate * all records in the pivot partition are in their final 443*7c478bd9Sstevel@tonic-gate * position and do not need to be accounted for by the stack 444*7c478bd9Sstevel@tonic-gate * 445*7c478bd9Sstevel@tonic-gate * when adding partitions to the stack 446*7c478bd9Sstevel@tonic-gate * it is important to add the largest partition first 447*7c478bd9Sstevel@tonic-gate * to prevent stack overflow. 448*7c478bd9Sstevel@tonic-gate * 449*7c478bd9Sstevel@tonic-gate * calculate number of unsorted records in top and bottom 450*7c478bd9Sstevel@tonic-gate * push resulting partitions on stack 451*7c478bd9Sstevel@tonic-gate */ 452*7c478bd9Sstevel@tonic-gate b_nrec = (b_par - b_lim) / rsiz; 453*7c478bd9Sstevel@tonic-gate t_nrec = (t_lim - t_par) / rsiz; 454*7c478bd9Sstevel@tonic-gate if (b_nrec < t_nrec) { 455*7c478bd9Sstevel@tonic-gate sp->b_lim = t_par + rsiz; 456*7c478bd9Sstevel@tonic-gate sp->nrec = t_nrec; 457*7c478bd9Sstevel@tonic-gate sp++; 458*7c478bd9Sstevel@tonic-gate sp->b_lim = b_lim; 459*7c478bd9Sstevel@tonic-gate sp->nrec = b_nrec; 460*7c478bd9Sstevel@tonic-gate sp++; 461*7c478bd9Sstevel@tonic-gate } else { 462*7c478bd9Sstevel@tonic-gate sp->b_lim = b_lim; 463*7c478bd9Sstevel@tonic-gate sp->nrec = b_nrec; 464*7c478bd9Sstevel@tonic-gate sp++; 465*7c478bd9Sstevel@tonic-gate sp->b_lim = t_par + rsiz; 466*7c478bd9Sstevel@tonic-gate sp->nrec = t_nrec; 467*7c478bd9Sstevel@tonic-gate sp++; 468*7c478bd9Sstevel@tonic-gate } 469*7c478bd9Sstevel@tonic-gate } 470*7c478bd9Sstevel@tonic-gate } 471*7c478bd9Sstevel@tonic-gate 472*7c478bd9Sstevel@tonic-gate /* 473*7c478bd9Sstevel@tonic-gate * The following swap functions should not create a stack frame 474*7c478bd9Sstevel@tonic-gate * the SPARC call / return instruction will be executed 475*7c478bd9Sstevel@tonic-gate * but the a save / restore will not be executed 476*7c478bd9Sstevel@tonic-gate * which means we won't do a window turn with the spill / fill overhead 477*7c478bd9Sstevel@tonic-gate * verify this by examining the assembly code 478*7c478bd9Sstevel@tonic-gate */ 479*7c478bd9Sstevel@tonic-gate 480*7c478bd9Sstevel@tonic-gate /* ARGSUSED */ 481*7c478bd9Sstevel@tonic-gate static void 482*7c478bd9Sstevel@tonic-gate swapp32(uint32_t *r1, uint32_t *r2, size_t cnt) 483*7c478bd9Sstevel@tonic-gate { 484*7c478bd9Sstevel@tonic-gate uint32_t temp; 485*7c478bd9Sstevel@tonic-gate 486*7c478bd9Sstevel@tonic-gate temp = *r1; 487*7c478bd9Sstevel@tonic-gate *r1++ = *r2; 488*7c478bd9Sstevel@tonic-gate *r2++ = temp; 489*7c478bd9Sstevel@tonic-gate } 490*7c478bd9Sstevel@tonic-gate 491*7c478bd9Sstevel@tonic-gate /* ARGSUSED */ 492*7c478bd9Sstevel@tonic-gate static void 493*7c478bd9Sstevel@tonic-gate swapp64(uint64_t *r1, uint64_t *r2, size_t cnt) 494*7c478bd9Sstevel@tonic-gate { 495*7c478bd9Sstevel@tonic-gate uint64_t temp; 496*7c478bd9Sstevel@tonic-gate 497*7c478bd9Sstevel@tonic-gate temp = *r1; 498*7c478bd9Sstevel@tonic-gate *r1++ = *r2; 499*7c478bd9Sstevel@tonic-gate *r2++ = temp; 500*7c478bd9Sstevel@tonic-gate } 501*7c478bd9Sstevel@tonic-gate 502*7c478bd9Sstevel@tonic-gate static void 503*7c478bd9Sstevel@tonic-gate swapi(uint32_t *r1, uint32_t *r2, size_t cnt) 504*7c478bd9Sstevel@tonic-gate { 505*7c478bd9Sstevel@tonic-gate uint32_t temp; 506*7c478bd9Sstevel@tonic-gate 507*7c478bd9Sstevel@tonic-gate /* character by character */ 508*7c478bd9Sstevel@tonic-gate while (cnt--) { 509*7c478bd9Sstevel@tonic-gate temp = *r1; 510*7c478bd9Sstevel@tonic-gate *r1++ = *r2; 511*7c478bd9Sstevel@tonic-gate *r2++ = temp; 512*7c478bd9Sstevel@tonic-gate } 513*7c478bd9Sstevel@tonic-gate } 514*7c478bd9Sstevel@tonic-gate 515*7c478bd9Sstevel@tonic-gate static void 516*7c478bd9Sstevel@tonic-gate swapb(char *r1, char *r2, size_t cnt) 517*7c478bd9Sstevel@tonic-gate { 518*7c478bd9Sstevel@tonic-gate char temp; 519*7c478bd9Sstevel@tonic-gate 520*7c478bd9Sstevel@tonic-gate /* character by character */ 521*7c478bd9Sstevel@tonic-gate while (cnt--) { 522*7c478bd9Sstevel@tonic-gate temp = *r1; 523*7c478bd9Sstevel@tonic-gate *r1++ = *r2; 524*7c478bd9Sstevel@tonic-gate *r2++ = temp; 525*7c478bd9Sstevel@tonic-gate } 526*7c478bd9Sstevel@tonic-gate } 527