qsort.c revision e8031f0a8ed0e45c6d8847c5e09424e66fd34a4b
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (the "License"). You may not use this file except in compliance
* with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
#include "synonyms.h"
#endif /* !_KERNEL && !_KMDB */
#include <stdlib.h>
#include <synch.h>
#endif /* !_KERNEL && !_KMDB */
#include "qsort.h"
/*
* choose a median of 3 values
*
* note: cstyle specifically prohibits nested conditional operators
* but this is the only way to do the median of 3 function in-line
*/
typedef struct {
char *b_lim;
} stk_t;
/*
* qsort() is a general purpose, in-place sorting routine using a
* user provided call back function for comparisons. This implementation
* utilizes a ternary quicksort algorithm, and cuts over to an
* insertion sort for partitions involving fewer than THRESH_L records.
*
* Potential User Errors
* There is no return value from qsort, this function has no method
* of alerting the user that a sort did not work or could not work.
* We do not print an error message or exit the process or thread,
* Even if we can detect an error, We CANNOT silently return without
* sorting the data, if we did so the user could never be sure the
* sort completed successfully.
* It is possible we could change the return value of sort from void
* to int and return success or some error codes, but this gets into
* standards and compatibility issues.
*
* Examples of qsort parameter errors might be
* 1) record size (rsiz) equal to 0
* qsort will loop and never return.
* 2) record size (rsiz) less than 0
* rsiz is unsigned, so a negative value is insanely large
* 3) number of records (nrec) is 0
* This is legal - qsort will return without examining any records
* 4) number of records (nrec) is less than 0
* nrec is unsigned, so a negative value is insanely large.
* 5) nrec * rsiz > memory allocation for sort array
* a segment violation may occur
* corruption of other memory may occur
* 6) The base address of the sort array is invalid
* a segment violation may occur
* corruption of other memory may occur
* 7) The user call back function is invalid
* we may get alignment errors or segment violations
* we may jump into never-never land
*
* Some less obvious errors might be
* 8) The user compare function is not comparing correctly
* 9) The user compare function modifies the data records
*/
void
void *basep,
int (*cmp)(const void *, const void *))
{
size_t i; /* temporary variable */
/* variables used by swap */
/* variables used by sort */
char *b_lim; /* bottom limit */
char *b_dup; /* bottom duplicate */
char *b_par; /* bottom partition */
char *t_lim; /* top limit */
char *t_dup; /* top duplicate */
char *t_par; /* top partition */
int b_nrec;
int t_nrec;
int cv; /* results of compare (bottom / top) */
/*
* choose a swap function based on alignment and size
*
* The qsort function sorts an array of fixed length records.
* We have very limited knowledge about the data record itself.
* It may be that the data record is in the array we are sorting
* or it may be that the array contains pointers or indexes to
* the actual data record and all that we are sorting is the indexes.
*
* The following decision will choose an optimal swap function
* based on the size and alignment of the data records
* swapp64 will swap 64 bit pointers
* swapp32 will swap 32 bit pointers
* swapi will swap an array of 32 bit integers
* swapb will swap an array of 8 bit characters
*
* swapi and swapb will also require the variable loops to be set
* to control the length of the array being swapped
*/
loops = 1;
loops = 1;
} else {
}
/*
* qsort is a partitioning sort
*
* the stack is the bookkeeping mechanism to keep track of all
* the partitions.
*
* each sort pass takes one partition and sorts it into two partitions.
* at the top of the loop we simply take the partition on the top
* of the stack and sort it. See the comments at the bottom
* of the loop regarding which partitions to add in what order.
*
* initially put the whole partition on the stack
*/
sp++;
sp--;
/*
* a linear insertion sort i faster than a qsort for
* very small number of records (THRESH_L)
*
* if number records < threshold use linear insertion sort
*
* this also handles the special case where the partition
* 0 or 1 records length.
*/
/*
* Linear insertion sort
*/
for (i = 1; i < nrec; i++) {
break;
}
}
}
/*
* a linear insertion sort will put all records
* in their final position and will not create
* subpartitions.
*
* therefore when the insertion sort is complete
* just go to the top of the loop and get the
* next partition to sort.
*/
continue;
}
/* quicksort */
/*
* choose a pivot record
*
* Ideally the pivot record will divide the partition
* into two equal parts. however we have to balance the
* work involved in selecting the pivot record with the
* expected benefit.
*
* The choice of pivot record depends on the number of
* records in the partition
*
* for small partitions (nrec < THRESH_M3)
* we just select the record in the middle of the partition
*
* if (nrec >= THRESH_M3 && nrec < THRESH_M9)
* we select three values and choose the median of 3
*
* if (nrec >= THRESH_M9)
* then we use an approximate median of 9
* 9 records are selected and grouped in 3 groups of 3
* the median of each of these 3 groups is fed into another
* median of 3 decision.
*
* Each median of 3 decision is 2 or 3 compares,
* so median of 9 costs between 8 and 12 compares.
*
* i is byte distance between two consecutive samples
* m2 will point to the pivot record
*/
/* use median of 3 */
} else {
/* approx median of 9 */
}
/*
* quick sort partitioning
*
* The partition limits are defined by bottom and top pointers
* b_lim and t_lim.
*
* qsort uses a fairly standard method of moving the
* partitioning pointers, b_par and t_par, to the middle of
* the partition and exchanging records that are in the
* wrong part of the partition.
*
* Two enhancements have been made to the basic algorithm.
* One for handling duplicate records and one to minimize
* the number of swaps.
*
* Two duplicate records pointers are (b_dup and t_dup) are
* initially set to b_lim and t_lim. Each time a record
* whose sort key value is equal to the pivot record is found
* it will be swapped with the record pointed to by
* b_dup or t_dup and the duplicate pointer will be
* incremented toward the center.
* When partitioning is complete, all the duplicate records
* will have been collected at the upper and lower limits of
* the partition and can easily be moved adjacent to the
* pivot record.
*
* The second optimization is to minimize the number of swaps.
* The pointer m2 points to the pivot record.
* During partitioning, if m2 is ever equal to the partitioning
* pointers, b_par or t_par, then b_par or t_par just moves
* onto the next record without doing a compare.
* If as a result of duplicate record detection,
* b_dup or t_dup is ever equal to m2,
* then m2 is changed to point to the duplicate record and
* b_dup or t_dup is incremented with out swapping records.
*
* When partitioning is done, we may not have the same pivot
* record that we started with, but we will have one with
* an equal sort key.
*/
for (;;) {
/* move bottom pointer up */
continue;
}
if (cv > 0) {
break;
}
if (cv == 0) {
}
}
}
/* move top pointer down */
continue;
}
if (cv < 0) {
break;
}
if (cv == 0) {
}
}
}
/* break if we are done partitioning */
break;
}
/* exchange records at upper and lower break points */
}
/*
* partitioning is now complete
*
* there are two termination conditions from the partitioning
* loop above. Either b_par or t_par have crossed or
* they are equal.
*
* we need to swap the pivot record to its final position
* m2 could be in either the upper or lower partitions
* or it could already be in its final position
*/
/*
* R[b_par] > R[m2]
* R[t_par] < R[m2]
*/
} else {
}
} else {
}
}
}
/*
* move bottom duplicates next to pivot
* optimized to eliminate overlap
*/
}
}
/*
* move top duplicates next to pivot
*/
}
}
/*
* when a qsort pass completes there are three partitions
* 1) the lower contains all records less than pivot
* 2) the upper contains all records greater than pivot
* 3) the pivot partition contains all record equal to pivot
*
* all records in the pivot partition are in their final
* position and do not need to be accounted for by the stack
*
* when adding partitions to the stack
* it is important to add the largest partition first
* to prevent stack overflow.
*
* calculate number of unsorted records in top and bottom
* push resulting partitions on stack
*/
sp++;
sp++;
} else {
sp++;
sp++;
}
}
}
/*
* The following swap functions should not create a stack frame
* the SPARC call / return instruction will be executed
* but the a save / restore will not be executed
* which means we won't do a window turn with the spill / fill overhead
* verify this by examining the assembly code
*/
/* ARGSUSED */
static void
{
}
/* ARGSUSED */
static void
{
}
static void
{
/* character by character */
while (cnt--) {
}
}
static void
{
char temp;
/* character by character */
while (cnt--) {
}
}