17c478bdstevel@tonic-gate/*
27c478bdstevel@tonic-gate * CDDL HEADER START
37c478bdstevel@tonic-gate *
47c478bdstevel@tonic-gate * The contents of this file are subject to the terms of the
57257d1braf * Common Development and Distribution License (the "License").
67257d1braf * You may not use this file except in compliance with the License.
77c478bdstevel@tonic-gate *
87c478bdstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bdstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
107c478bdstevel@tonic-gate * See the License for the specific language governing permissions
117c478bdstevel@tonic-gate * and limitations under the License.
127c478bdstevel@tonic-gate *
137c478bdstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
147c478bdstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bdstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
167c478bdstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
177c478bdstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bdstevel@tonic-gate *
197c478bdstevel@tonic-gate * CDDL HEADER END
207c478bdstevel@tonic-gate */
21e8031f0raf
227c478bdstevel@tonic-gate/*
237257d1braf * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
247c478bdstevel@tonic-gate * Use is subject to license terms.
257c478bdstevel@tonic-gate */
267c478bdstevel@tonic-gate
277c478bdstevel@tonic-gate#pragma ident	"%Z%%M%	%I%	%E% SMI"
287c478bdstevel@tonic-gate
297c478bdstevel@tonic-gate#if !defined(_KERNEL) && !defined(_KMDB)
307257d1braf#include "lint.h"
317c478bdstevel@tonic-gate#endif /* !_KERNEL && !_KMDB */
327c478bdstevel@tonic-gate
337c478bdstevel@tonic-gate#include <sys/types.h>
347c478bdstevel@tonic-gate
357c478bdstevel@tonic-gate#if !defined(_KERNEL) && !defined(_KMDB)
367c478bdstevel@tonic-gate#include <stdlib.h>
377c478bdstevel@tonic-gate#include <synch.h>
387c478bdstevel@tonic-gate#endif /* !_KERNEL && !_KMDB */
397c478bdstevel@tonic-gate
407c478bdstevel@tonic-gate#include "qsort.h"
417c478bdstevel@tonic-gate
427c478bdstevel@tonic-gatestatic void swapp32(uint32_t *r1, uint32_t *r2, size_t cnt);
437c478bdstevel@tonic-gatestatic void swapp64(uint64_t *r1, uint64_t *r2, size_t cnt);
447c478bdstevel@tonic-gatestatic void swapi(uint32_t *r1, uint32_t *r2, size_t cnt);
457c478bdstevel@tonic-gatestatic void swapb(char *r1, char *r2, size_t cnt);
467c478bdstevel@tonic-gate
477c478bdstevel@tonic-gate/*
487c478bdstevel@tonic-gate * choose a median of 3 values
497c478bdstevel@tonic-gate *
507c478bdstevel@tonic-gate * note: cstyle specifically prohibits nested conditional operators
517c478bdstevel@tonic-gate * but this is the only way to do the median of 3 function in-line
527c478bdstevel@tonic-gate */
537c478bdstevel@tonic-gate#define	med3(a, b, c) (cmp((a), (b)) < 0) \
547c478bdstevel@tonic-gate	? ((cmp((b), (c)) < 0) ? (b) : (cmp((a), (c)) < 0) ? (c) : (a)) \
557c478bdstevel@tonic-gate	: ((cmp((b), (c)) > 0) ? (b) : (cmp((a), (c)) > 0) ? (c) : (a))
567c478bdstevel@tonic-gate
577c478bdstevel@tonic-gate#define	THRESH_L	5	/* threshold for insertion sort */
587c478bdstevel@tonic-gate#define	THRESH_M3	20	/* threshold for median of 3 */
597c478bdstevel@tonic-gate#define	THRESH_M9	50	/* threshold for median of 9 */
607c478bdstevel@tonic-gate
617c478bdstevel@tonic-gatetypedef struct {
627c478bdstevel@tonic-gate	char	*b_lim;
637c478bdstevel@tonic-gate	size_t	nrec;
647c478bdstevel@tonic-gate} stk_t;
657c478bdstevel@tonic-gate
667c478bdstevel@tonic-gate/*
677c478bdstevel@tonic-gate * qsort() is a general purpose, in-place sorting routine using a
687c478bdstevel@tonic-gate * user provided call back function for comparisons.  This implementation
697c478bdstevel@tonic-gate * utilizes a ternary quicksort algorithm, and cuts over to an
707c478bdstevel@tonic-gate * insertion sort for partitions involving fewer than THRESH_L records.
717c478bdstevel@tonic-gate *
727c478bdstevel@tonic-gate * Potential User Errors
737c478bdstevel@tonic-gate *   There is no return value from qsort, this function has no method
747c478bdstevel@tonic-gate *   of alerting the user that a sort did not work or could not work.
757c478bdstevel@tonic-gate *   We do not print an error message or exit the process or thread,
767c478bdstevel@tonic-gate *   Even if we can detect an error, We CANNOT silently return without
777c478bdstevel@tonic-gate *   sorting the data, if we did so the user could never be sure the
787c478bdstevel@tonic-gate *   sort completed successfully.
797c478bdstevel@tonic-gate *   It is possible we could change the return value of sort from void
807c478bdstevel@tonic-gate *   to int and return success or some error codes, but this gets into
817c478bdstevel@tonic-gate *   standards  and compatibility issues.
827c478bdstevel@tonic-gate *
837c478bdstevel@tonic-gate *   Examples of qsort parameter errors might be
847c478bdstevel@tonic-gate *   1) record size (rsiz) equal to 0
857c478bdstevel@tonic-gate *      qsort will loop and never return.
867c478bdstevel@tonic-gate *   2) record size (rsiz) less than 0
877c478bdstevel@tonic-gate *      rsiz is unsigned, so a negative value is insanely large
887c478bdstevel@tonic-gate *   3) number of records (nrec) is 0
897c478bdstevel@tonic-gate *      This is legal - qsort will return without examining any records
907c478bdstevel@tonic-gate *   4) number of records (nrec) is less than 0
917c478bdstevel@tonic-gate *      nrec is unsigned, so a negative value is insanely large.
927c478bdstevel@tonic-gate *   5) nrec * rsiz > memory allocation for sort array
937c478bdstevel@tonic-gate *      a segment violation may occur
947c478bdstevel@tonic-gate *      corruption of other memory may occur
957c478bdstevel@tonic-gate *   6) The base address of the sort array is invalid
967c478bdstevel@tonic-gate *      a segment violation may occur
977c478bdstevel@tonic-gate *      corruption of other memory may occur
987c478bdstevel@tonic-gate *   7) The user call back function is invalid
997c478bdstevel@tonic-gate *      we may get alignment errors or segment violations
1007c478bdstevel@tonic-gate *      we may jump into never-never land
1017c478bdstevel@tonic-gate *
1027c478bdstevel@tonic-gate *   Some less obvious errors might be
1037c478bdstevel@tonic-gate *   8) The user compare function is not comparing correctly
1047c478bdstevel@tonic-gate *   9) The user compare function modifies the data records
1057c478bdstevel@tonic-gate */
1067c478bdstevel@tonic-gate
1077c478bdstevel@tonic-gatevoid
1087c478bdstevel@tonic-gateqsort(
1097c478bdstevel@tonic-gate	void		*basep,
1107c478bdstevel@tonic-gate	size_t		nrec,
1117c478bdstevel@tonic-gate	size_t		rsiz,
1127c478bdstevel@tonic-gate	int		(*cmp)(const void *, const void *))
1137c478bdstevel@tonic-gate{
1147c478bdstevel@tonic-gate	size_t		i;		/* temporary variable */
1157c478bdstevel@tonic-gate
1167c478bdstevel@tonic-gate	/* variables used by swap */
1177c478bdstevel@tonic-gate	void		(*swapf)(char *, char *, size_t);
1187c478bdstevel@tonic-gate	size_t		loops;
1197c478bdstevel@tonic-gate
1207c478bdstevel@tonic-gate	/* variables used by sort */
1217c478bdstevel@tonic-gate	stk_t		stack[8 * sizeof (nrec) + 1];
1227c478bdstevel@tonic-gate	stk_t		*sp;
1237c478bdstevel@tonic-gate	char		*b_lim;		/* bottom limit */
1247c478bdstevel@tonic-gate	char		*b_dup;		/* bottom duplicate */
1257c478bdstevel@tonic-gate	char		*b_par;		/* bottom partition */
1267c478bdstevel@tonic-gate	char		*t_lim;		/* top limit */
1277c478bdstevel@tonic-gate	char		*t_dup;		/* top duplicate */
1287c478bdstevel@tonic-gate	char		*t_par;		/* top partition */
1297c478bdstevel@tonic-gate	char		*m1, *m2, *m3;	/* median pointers */
1307c478bdstevel@tonic-gate	uintptr_t	d_bytelength;	/* byte length of duplicate records */
1317c478bdstevel@tonic-gate	int		b_nrec;
1327c478bdstevel@tonic-gate	int		t_nrec;
1337c478bdstevel@tonic-gate	int		cv;		/* results of compare (bottom / top) */
1347c478bdstevel@tonic-gate
1357c478bdstevel@tonic-gate	/*
1367c478bdstevel@tonic-gate	 * choose a swap function based on alignment and size
1377c478bdstevel@tonic-gate	 *
1387c478bdstevel@tonic-gate	 * The qsort function sorts an array of fixed length records.
1397c478bdstevel@tonic-gate	 * We have very limited knowledge about the data record itself.
1407c478bdstevel@tonic-gate	 * It may be that the data record is in the array we are sorting
1417c478bdstevel@tonic-gate	 * or it may be that the array contains pointers or indexes to
1427c478bdstevel@tonic-gate	 * the actual data record and all that we are sorting is the indexes.
1437c478bdstevel@tonic-gate	 *
1447c478bdstevel@tonic-gate	 * The following decision will choose an optimal swap function
1457c478bdstevel@tonic-gate	 * based on the size and alignment of the data records
1467c478bdstevel@tonic-gate	 *   swapp64	will swap 64 bit pointers
1477c478bdstevel@tonic-gate	 *   swapp32	will swap 32 bit pointers
1487c478bdstevel@tonic-gate	 *   swapi	will swap an array of 32 bit integers
1497c478bdstevel@tonic-gate	 *   swapb	will swap an array of 8 bit characters
1507c478bdstevel@tonic-gate	 *
1517c478bdstevel@tonic-gate	 * swapi and swapb will also require the variable loops to be set
1527c478bdstevel@tonic-gate	 * to control the length of the array being swapped
1537c478bdstevel@tonic-gate	 */
1547c478bdstevel@tonic-gate	if ((((uintptr_t)basep & (sizeof (uint64_t) - 1)) == 0) &&
1557c478bdstevel@tonic-gate	    (rsiz == sizeof (uint64_t))) {
1567c478bdstevel@tonic-gate		loops = 1;
1577c478bdstevel@tonic-gate		swapf = (void (*)(char *, char *, size_t))swapp64;
1587c478bdstevel@tonic-gate	} else if ((((uintptr_t)basep & (sizeof (uint32_t) - 1)) == 0) &&
1597c478bdstevel@tonic-gate	    (rsiz == sizeof (uint32_t))) {
1607c478bdstevel@tonic-gate		loops = 1;
1617c478bdstevel@tonic-gate		swapf = (void (*)(char *, char *, size_t))swapp32;
1627c478bdstevel@tonic-gate	} else if ((((uintptr_t)basep & (sizeof (uint32_t) - 1)) == 0) &&
1637c478bdstevel@tonic-gate	    ((rsiz & (sizeof (uint32_t) - 1)) == 0)) {
1647c478bdstevel@tonic-gate		loops = rsiz / sizeof (int);
1657c478bdstevel@tonic-gate		swapf = (void (*)(char *, char *, size_t))swapi;
1667c478bdstevel@tonic-gate	} else {
1677c478bdstevel@tonic-gate		loops = rsiz;
1687c478bdstevel@tonic-gate		swapf = swapb;
1697c478bdstevel@tonic-gate	}
1707c478bdstevel@tonic-gate
1717c478bdstevel@tonic-gate	/*
1727c478bdstevel@tonic-gate	 * qsort is a partitioning sort
1737c478bdstevel@tonic-gate	 *
1747c478bdstevel@tonic-gate	 * the stack is the bookkeeping mechanism to keep track of all
1757c478bdstevel@tonic-gate	 * the partitions.
1767c478bdstevel@tonic-gate	 *
1777c478bdstevel@tonic-gate	 * each sort pass takes one partition and sorts it into two partitions.
1787c478bdstevel@tonic-gate	 * at the top of the loop we simply take the partition on the top
1797c478bdstevel@tonic-gate	 * of the stack and sort it. See the comments at the bottom
1807c478bdstevel@tonic-gate	 * of the loop regarding which partitions to add in what order.
1817c478bdstevel@tonic-gate	 *
1827c478bdstevel@tonic-gate	 * initially put the whole partition on the stack
1837c478bdstevel@tonic-gate	 */
1847c478bdstevel@tonic-gate	sp = stack;
1857c478bdstevel@tonic-gate	sp->b_lim = (char *)basep;
1867c478bdstevel@tonic-gate	sp->nrec = nrec;
1877c478bdstevel@tonic-gate	sp++;
1887c478bdstevel@tonic-gate	while (sp > stack) {
1897c478bdstevel@tonic-gate		sp--;
1907c478bdstevel@tonic-gate		b_lim = sp->b_lim;
1917c478bdstevel@tonic-gate		nrec = sp->nrec;
1927c478bdstevel@tonic-gate
1937c478bdstevel@tonic-gate		/*
1947c478bdstevel@tonic-gate		 * a linear insertion sort i faster than a qsort for
1957c478bdstevel@tonic-gate		 * very small number of records (THRESH_L)
1967c478bdstevel@tonic-gate		 *
1977c478bdstevel@tonic-gate		 * if number records < threshold use linear insertion sort
1987c478bdstevel@tonic-gate		 *
1997c478bdstevel@tonic-gate		 * this also handles the special case where the partition
2007c478bdstevel@tonic-gate		 * 0 or 1 records length.
2017c478bdstevel@tonic-gate		 */
2027c478bdstevel@tonic-gate		if (nrec < THRESH_L) {
2037c478bdstevel@tonic-gate			/*
2047c478bdstevel@tonic-gate			 * Linear insertion sort
2057c478bdstevel@tonic-gate			 */
2067c478bdstevel@tonic-gate			t_par = b_lim;
2077c478bdstevel@tonic-gate			for (i = 1; i < nrec; i++) {
2087c478bdstevel@tonic-gate				t_par += rsiz;
2097c478bdstevel@tonic-gate				b_par = t_par;
2107c478bdstevel@tonic-gate				while (b_par > b_lim) {
2117c478bdstevel@tonic-gate					b_par -= rsiz;
2127c478bdstevel@tonic-gate					if ((*cmp)(b_par, b_par + rsiz) <= 0) {
2137c478bdstevel@tonic-gate						break;
2147c478bdstevel@tonic-gate					}
2157c478bdstevel@tonic-gate					(*swapf)(b_par, b_par + rsiz, loops);
2167c478bdstevel@tonic-gate				}
2177c478bdstevel@tonic-gate			}
2187c478bdstevel@tonic-gate
2197c478bdstevel@tonic-gate			/*
2207c478bdstevel@tonic-gate			 * a linear insertion sort will put all records
2217c478bdstevel@tonic-gate			 * in their final position and will not create
2227c478bdstevel@tonic-gate			 * subpartitions.
2237c478bdstevel@tonic-gate			 *
2247c478bdstevel@tonic-gate			 * therefore when the insertion sort is complete
2257c478bdstevel@tonic-gate			 * just go to the top of the loop and get the
2267c478bdstevel@tonic-gate			 * next partition to sort.
2277c478bdstevel@tonic-gate			 */
2287c478bdstevel@tonic-gate			continue;
2297c478bdstevel@tonic-gate		}
2307c478bdstevel@tonic-gate
2317c478bdstevel@tonic-gate		/* quicksort */
2327c478bdstevel@tonic-gate
2337c478bdstevel@tonic-gate		/*
2347c478bdstevel@tonic-gate		 * choose a pivot record
2357c478bdstevel@tonic-gate		 *
2367c478bdstevel@tonic-gate		 * Ideally the pivot record will divide the partition
2377c478bdstevel@tonic-gate		 * into two equal parts. however we have to balance the
2387c478bdstevel@tonic-gate		 * work involved in selecting the pivot record with the
2397c478bdstevel@tonic-gate		 * expected benefit.
2407c478bdstevel@tonic-gate		 *
2417c478bdstevel@tonic-gate		 * The choice of pivot record depends on the number of
2427c478bdstevel@tonic-gate		 * records in the partition
2437c478bdstevel@tonic-gate		 *
2447c478bdstevel@tonic-gate		 * for small partitions (nrec < THRESH_M3)
2457c478bdstevel@tonic-gate		 *   we just select the record in the middle of the partition
2467c478bdstevel@tonic-gate		 *
2477c478bdstevel@tonic-gate		 * if (nrec >= THRESH_M3 && nrec < THRESH_M9)
2487c478bdstevel@tonic-gate		 *   we select three values and choose the median of 3
2497c478bdstevel@tonic-gate		 *
2507c478bdstevel@tonic-gate		 * if (nrec >= THRESH_M9)
2517c478bdstevel@tonic-gate		 *   then we use an approximate median of 9
2527c478bdstevel@tonic-gate		 *   9 records are selected and grouped in 3 groups of 3
2537c478bdstevel@tonic-gate		 *   the median of each of these 3 groups is fed into another
2547c478bdstevel@tonic-gate		 *   median of 3 decision.
2557c478bdstevel@tonic-gate		 *
2567c478bdstevel@tonic-gate		 * Each median of 3 decision is 2 or 3 compares,
2577c478bdstevel@tonic-gate		 * so median of 9 costs between 8 and 12 compares.
2587c478bdstevel@tonic-gate		 *
2597c478bdstevel@tonic-gate		 * i is byte distance between two consecutive samples
2607c478bdstevel@tonic-gate		 * m2 will point to the pivot record
2617c478bdstevel@tonic-gate		 */
2627c478bdstevel@tonic-gate		if (nrec < THRESH_M3) {
2637c478bdstevel@tonic-gate			m2 = b_lim + (nrec / 2) * rsiz;
2647c478bdstevel@tonic-gate		} else if (nrec < THRESH_M9) {
2657c478bdstevel@tonic-gate			/* use median of 3 */
2667c478bdstevel@tonic-gate			i = ((nrec - 1) / 2) * rsiz;
2677c478bdstevel@tonic-gate			m2 = med3(b_lim, b_lim + i, b_lim + 2 * i);
2687c478bdstevel@tonic-gate		} else {
2697c478bdstevel@tonic-gate			/* approx median of 9 */
2707c478bdstevel@tonic-gate			i = ((nrec - 1) / 8) * rsiz;
2717c478bdstevel@tonic-gate			m1 = med3(b_lim, b_lim +  i, b_lim + 2 * i);
2727c478bdstevel@tonic-gate			m2 = med3(b_lim + 3 * i, b_lim + 4 * i, b_lim + 5 * i);
2737c478bdstevel@tonic-gate			m3 = med3(b_lim + 6 * i, b_lim + 7 * i, b_lim + 8 * i);
2747c478bdstevel@tonic-gate			m2 = med3(m1, m2, m3);
2757c478bdstevel@tonic-gate		}
2767c478bdstevel@tonic-gate
2777c478bdstevel@tonic-gate		/*
2787c478bdstevel@tonic-gate		 * quick sort partitioning
2797c478bdstevel@tonic-gate		 *
2807c478bdstevel@tonic-gate		 * The partition limits are defined by bottom and top pointers
2817c478bdstevel@tonic-gate		 * b_lim and t_lim.
2827c478bdstevel@tonic-gate		 *
2837c478bdstevel@tonic-gate		 * qsort uses a fairly standard method of moving the
2847c478bdstevel@tonic-gate		 * partitioning pointers, b_par and t_par, to the middle of
2857c478bdstevel@tonic-gate		 * the partition and exchanging records that are in the
2867c478bdstevel@tonic-gate		 * wrong part of the partition.
2877c478bdstevel@tonic-gate		 *
2887c478bdstevel@tonic-gate		 * Two enhancements have been made to the basic algorithm.
2897c478bdstevel@tonic-gate		 * One for handling duplicate records and one to minimize
2907c478bdstevel@tonic-gate		 * the number of swaps.
2917c478bdstevel@tonic-gate		 *
2927c478bdstevel@tonic-gate		 * Two duplicate records pointers are (b_dup and t_dup) are
2937c478bdstevel@tonic-gate		 * initially set to b_lim and t_lim.  Each time a record
2947c478bdstevel@tonic-gate		 * whose sort key value is equal to the pivot record is found
2957c478bdstevel@tonic-gate		 * it will be swapped with the record pointed to by
2967c478bdstevel@tonic-gate		 * b_dup or t_dup and the duplicate pointer will be
2977c478bdstevel@tonic-gate		 * incremented toward the center.
2987c478bdstevel@tonic-gate		 * When partitioning is complete, all the duplicate records
2997c478bdstevel@tonic-gate		 * will have been collected at the upper and lower limits of
3007c478bdstevel@tonic-gate		 * the partition and can easily be moved adjacent to the
3017c478bdstevel@tonic-gate		 * pivot record.
3027c478bdstevel@tonic-gate		 *
3037c478bdstevel@tonic-gate		 * The second optimization is to minimize the number of swaps.
3047c478bdstevel@tonic-gate		 * The pointer m2 points to the pivot record.
3057c478bdstevel@tonic-gate		 * During partitioning, if m2 is ever equal to the partitioning
3067c478bdstevel@tonic-gate		 * pointers, b_par or t_par, then b_par or t_par just moves
3077c478bdstevel@tonic-gate		 * onto the next record without doing a compare.
3087c478bdstevel@tonic-gate		 * If as a result of duplicate record detection,
3097c478bdstevel@tonic-gate		 * b_dup or t_dup is ever equal to m2,
3107c478bdstevel@tonic-gate		 * then m2 is changed to point to the duplicate record and
3117c478bdstevel@tonic-gate		 * b_dup or t_dup is incremented with out swapping records.
3127c478bdstevel@tonic-gate		 *
3137c478bdstevel@tonic-gate		 * When partitioning is done, we may not have the same pivot
3147c478bdstevel@tonic-gate		 * record that we started with, but we will have one with
3157c478bdstevel@tonic-gate		 * an equal sort key.
3167c478bdstevel@tonic-gate		 */
3177c478bdstevel@tonic-gate		b_dup = b_par		= b_lim;
3187c478bdstevel@tonic-gate		t_dup = t_par = t_lim	= b_lim + rsiz * (nrec - 1);
3197c478bdstevel@tonic-gate		for (;;) {
3207c478bdstevel@tonic-gate
3217c478bdstevel@tonic-gate			/* move bottom pointer up */
3227c478bdstevel@tonic-gate			for (; b_par <= t_par; b_par += rsiz) {
3237c478bdstevel@tonic-gate				if (b_par == m2) {
3247c478bdstevel@tonic-gate					continue;
3257c478bdstevel@tonic-gate				}
3267c478bdstevel@tonic-gate				cv = cmp(b_par, m2);
3277c478bdstevel@tonic-gate				if (cv > 0) {
3287c478bdstevel@tonic-gate					break;
3297c478bdstevel@tonic-gate				}
3307c478bdstevel@tonic-gate				if (cv == 0) {
3317c478bdstevel@tonic-gate					if (b_dup == m2) {
3327c478bdstevel@tonic-gate						m2 = b_par;
3337c478bdstevel@tonic-gate					} else if (b_dup != b_par) {
3347c478bdstevel@tonic-gate						(*swapf)(b_dup, b_par, loops);
3357c478bdstevel@tonic-gate					}
3367c478bdstevel@tonic-gate					b_dup += rsiz;
3377c478bdstevel@tonic-gate				}
3387c478bdstevel@tonic-gate			}
3397c478bdstevel@tonic-gate
3407c478bdstevel@tonic-gate			/* move top pointer down */
3417c478bdstevel@tonic-gate			for (; b_par < t_par; t_par -= rsiz) {
3427c478bdstevel@tonic-gate				if (t_par == m2) {
3437c478bdstevel@tonic-gate					continue;
3447c478bdstevel@tonic-gate				}
3457c478bdstevel@tonic-gate				cv = cmp(t_par, m2);
3467c478bdstevel@tonic-gate				if (cv < 0) {
3477c478bdstevel@tonic-gate					break;
3487c478bdstevel@tonic-gate				}
3497c478bdstevel@tonic-gate				if (cv == 0) {
3507c478bdstevel@tonic-gate					if (t_dup == m2) {
3517c478bdstevel@tonic-gate						m2 = t_par;
3527c478bdstevel@tonic-gate					} else if (t_dup != t_par) {
3537c478bdstevel@tonic-gate						(*swapf)(t_dup, t_par, loops);
3547c478bdstevel@tonic-gate					}
3557c478bdstevel@tonic-gate					t_dup -= rsiz;
3567c478bdstevel@tonic-gate				}
3577c478bdstevel@tonic-gate			}
3587c478bdstevel@tonic-gate
3597c478bdstevel@tonic-gate			/* break if we are done partitioning */
3607c478bdstevel@tonic-gate			if (b_par >= t_par) {
3617c478bdstevel@tonic-gate				break;
3627c478bdstevel@tonic-gate			}
3637c478bdstevel@tonic-gate
3647c478bdstevel@tonic-gate			/* exchange records at upper and lower break points */
3657c478bdstevel@tonic-gate			(*swapf)(b_par, t_par, loops);
3667c478bdstevel@tonic-gate			b_par += rsiz;
3677c478bdstevel@tonic-gate			t_par -= rsiz;
3687c478bdstevel@tonic-gate		}
3697c478bdstevel@tonic-gate
3707c478bdstevel@tonic-gate		/*
3717c478bdstevel@tonic-gate		 * partitioning is now complete
3727c478bdstevel@tonic-gate		 *
3737c478bdstevel@tonic-gate		 * there are two termination conditions from the partitioning
3747c478bdstevel@tonic-gate		 * loop above.  Either b_par or t_par have crossed or
3757c478bdstevel@tonic-gate		 * they are equal.
3767c478bdstevel@tonic-gate		 *
3777c478bdstevel@tonic-gate		 * we need to swap the pivot record to its final position
3787c478bdstevel@tonic-gate		 * m2 could be in either the upper or lower partitions
3797c478bdstevel@tonic-gate		 * or it could already be in its final position
3807c478bdstevel@tonic-gate		 */
3817c478bdstevel@tonic-gate		/*
3827c478bdstevel@tonic-gate		 * R[b_par] > R[m2]
3837c478bdstevel@tonic-gate		 * R[t_par] < R[m2]
3847c478bdstevel@tonic-gate		 */
3857c478bdstevel@tonic-gate		if (t_par < b_par) {
3867c478bdstevel@tonic-gate			if (m2 < t_par) {
3877c478bdstevel@tonic-gate				(*swapf)(m2, t_par, loops);
3887c478bdstevel@tonic-gate				m2 = b_par = t_par;
3897c478bdstevel@tonic-gate			} else if (m2 > b_par) {
3907c478bdstevel@tonic-gate				(*swapf)(m2, b_par, loops);
3917c478bdstevel@tonic-gate				m2 = t_par = b_par;
3927c478bdstevel@tonic-gate			} else {
3937c478bdstevel@tonic-gate				b_par = t_par = m2;
3947c478bdstevel@tonic-gate			}
3957c478bdstevel@tonic-gate		} else {
3967c478bdstevel@tonic-gate			if (m2 < t_par) {
3977c478bdstevel@tonic-gate				t_par = b_par = t_par - rsiz;
3987c478bdstevel@tonic-gate			}
3997c478bdstevel@tonic-gate			if (m2 != b_par) {
4007c478bdstevel@tonic-gate				(*swapf)(m2, b_par, loops);
4017c478bdstevel@tonic-gate			}
4027c478bdstevel@tonic-gate			m2 = t_par;
4037c478bdstevel@tonic-gate		}
4047c478bdstevel@tonic-gate
4057c478bdstevel@tonic-gate		/*
4067c478bdstevel@tonic-gate		 * move bottom duplicates next to pivot
4077c478bdstevel@tonic-gate		 * optimized to eliminate overlap
4087c478bdstevel@tonic-gate		 */
4097c478bdstevel@tonic-gate		d_bytelength = b_dup - b_lim;
4107c478bdstevel@tonic-gate		if (b_par - b_dup < d_bytelength) {
4117c478bdstevel@tonic-gate			b_dup = b_lim + (b_par - b_dup);
4127c478bdstevel@tonic-gate		}
4137c478bdstevel@tonic-gate		while (b_dup > b_lim) {
4147c478bdstevel@tonic-gate			b_dup -= rsiz;
4157c478bdstevel@tonic-gate			b_par -= rsiz;
4167c478bdstevel@tonic-gate			(*swapf)(b_dup, b_par, loops);
4177c478bdstevel@tonic-gate		}
4187c478bdstevel@tonic-gate		b_par = m2 - d_bytelength;
4197c478bdstevel@tonic-gate
4207c478bdstevel@tonic-gate		/*
4217c478bdstevel@tonic-gate		 * move top duplicates next to pivot
4227c478bdstevel@tonic-gate		 */
4237c478bdstevel@tonic-gate		d_bytelength = t_lim - t_dup;
4247c478bdstevel@tonic-gate		if (t_dup - t_par < d_bytelength) {
4257c478bdstevel@tonic-gate			t_dup = t_lim - (t_dup - t_par);
4267c478bdstevel@tonic-gate		}
4277c478bdstevel@tonic-gate		while (t_dup < t_lim) {
4287c478bdstevel@tonic-gate			t_dup += rsiz;
4297c478bdstevel@tonic-gate			t_par += rsiz;
4307c478bdstevel@tonic-gate			(*swapf)(t_dup, t_par, loops);
4317c478bdstevel@tonic-gate		}
4327c478bdstevel@tonic-gate		t_par = m2 + d_bytelength;
4337c478bdstevel@tonic-gate
4347c478bdstevel@tonic-gate		/*
4357c478bdstevel@tonic-gate		 * when a qsort pass completes there are three partitions
4367c478bdstevel@tonic-gate		 * 1) the lower contains all records less than pivot
4377c478bdstevel@tonic-gate		 * 2) the upper contains all records greater than pivot
4387c478bdstevel@tonic-gate		 * 3) the pivot partition contains all record equal to pivot
4397c478bdstevel@tonic-gate		 *
4407c478bdstevel@tonic-gate		 * all records in the pivot partition are in their final
4417c478bdstevel@tonic-gate		 * position and do not need to be accounted for by the stack
4427c478bdstevel@tonic-gate		 *
4437c478bdstevel@tonic-gate		 * when adding partitions to the stack
4447c478bdstevel@tonic-gate		 * it is important to add the largest partition first
4457c478bdstevel@tonic-gate		 * to prevent stack overflow.
4467c478bdstevel@tonic-gate		 *
4477c478bdstevel@tonic-gate		 * calculate number of unsorted records in top and bottom
4487c478bdstevel@tonic-gate		 * push resulting partitions on stack
4497c478bdstevel@tonic-gate		 */
4507c478bdstevel@tonic-gate		b_nrec = (b_par - b_lim) / rsiz;
4517c478bdstevel@tonic-gate		t_nrec = (t_lim - t_par) / rsiz;
4527c478bdstevel@tonic-gate		if (b_nrec < t_nrec) {
4537c478bdstevel@tonic-gate			sp->b_lim = t_par + rsiz;
4547c478bdstevel@tonic-gate			sp->nrec = t_nrec;
4557c478bdstevel@tonic-gate			sp++;
4567c478bdstevel@tonic-gate			sp->b_lim = b_lim;
4577c478bdstevel@tonic-gate			sp->nrec = b_nrec;
4587c478bdstevel@tonic-gate			sp++;
4597c478bdstevel@tonic-gate		} else {
4607c478bdstevel@tonic-gate			sp->b_lim = b_lim;
4617c478bdstevel@tonic-gate			sp->nrec = b_nrec;
4627c478bdstevel@tonic-gate			sp++;
4637c478bdstevel@tonic-gate			sp->b_lim = t_par + rsiz;
4647c478bdstevel@tonic-gate			sp->nrec = t_nrec;
4657c478bdstevel@tonic-gate			sp++;
4667c478bdstevel@tonic-gate		}
4677c478bdstevel@tonic-gate	}
4687c478bdstevel@tonic-gate}
4697c478bdstevel@tonic-gate
4707c478bdstevel@tonic-gate/*
4717c478bdstevel@tonic-gate * The following swap functions should not create a stack frame
4727c478bdstevel@tonic-gate * the SPARC call / return instruction will be executed
4737c478bdstevel@tonic-gate * but the a save / restore will not be executed
4747c478bdstevel@tonic-gate * which means we won't do a window turn with the spill / fill overhead
4757c478bdstevel@tonic-gate * verify this by examining the assembly code
4767c478bdstevel@tonic-gate */
4777c478bdstevel@tonic-gate
4787c478bdstevel@tonic-gate/* ARGSUSED */
4797c478bdstevel@tonic-gatestatic void
4807c478bdstevel@tonic-gateswapp32(uint32_t *r1, uint32_t *r2, size_t cnt)
4817c478bdstevel@tonic-gate{
4827c478bdstevel@tonic-gate	uint32_t temp;
4837c478bdstevel@tonic-gate
4847c478bdstevel@tonic-gate	temp = *r1;
4857c478bdstevel@tonic-gate	*r1++ = *r2;
4867c478bdstevel@tonic-gate	*r2++ = temp;
4877c478bdstevel@tonic-gate}
4887c478bdstevel@tonic-gate
4897c478bdstevel@tonic-gate/* ARGSUSED */
4907c478bdstevel@tonic-gatestatic void
4917c478bdstevel@tonic-gateswapp64(uint64_t *r1, uint64_t *r2, size_t cnt)
4927c478bdstevel@tonic-gate{
4937c478bdstevel@tonic-gate	uint64_t temp;
4947c478bdstevel@tonic-gate
4957c478bdstevel@tonic-gate	temp = *r1;
4967c478bdstevel@tonic-gate	*r1++ = *r2;
4977c478bdstevel@tonic-gate	*r2++ = temp;
4987c478bdstevel@tonic-gate}
4997c478bdstevel@tonic-gate
5007c478bdstevel@tonic-gatestatic void
5017c478bdstevel@tonic-gateswapi(uint32_t *r1, uint32_t *r2, size_t cnt)
5027c478bdstevel@tonic-gate{
5037c478bdstevel@tonic-gate	uint32_t temp;
5047c478bdstevel@tonic-gate
5057c478bdstevel@tonic-gate	/* character by character */
5067c478bdstevel@tonic-gate	while (cnt--) {
5077c478bdstevel@tonic-gate		temp = *r1;
5087c478bdstevel@tonic-gate		*r1++ = *r2;
5097c478bdstevel@tonic-gate		*r2++ = temp;
5107c478bdstevel@tonic-gate	}
5117c478bdstevel@tonic-gate}
5127c478bdstevel@tonic-gate
5137c478bdstevel@tonic-gatestatic void
5147c478bdstevel@tonic-gateswapb(char *r1, char *r2, size_t cnt)
5157c478bdstevel@tonic-gate{
5167c478bdstevel@tonic-gate	char	temp;
5177c478bdstevel@tonic-gate
5187c478bdstevel@tonic-gate	/* character by character */
5197c478bdstevel@tonic-gate	while (cnt--) {
5207c478bdstevel@tonic-gate		temp = *r1;
5217c478bdstevel@tonic-gate		*r1++ = *r2;
5227c478bdstevel@tonic-gate		*r2++ = temp;
5237c478bdstevel@tonic-gate	}
5247c478bdstevel@tonic-gate}
525