X-Git-Url: https://git.subgeniuskitty.com/unix-history/.git/blobdiff_plain/8c8a5b54e79564c14fc7a2823a21a8f048449bcf..af359dea2e5ab3e937b62107ecd6a51d78189ed7:/usr/src/lib/libc/stdlib/radixsort.3 diff --git a/usr/src/lib/libc/stdlib/radixsort.3 b/usr/src/lib/libc/stdlib/radixsort.3 index 3746084105..0575ec798c 100644 --- a/usr/src/lib/libc/stdlib/radixsort.3 +++ b/usr/src/lib/libc/stdlib/radixsort.3 @@ -1,81 +1,143 @@ -.\" Copyright (c) 1990 The Regents of the University of California. +.\" Copyright (c) 1990, 1991 The Regents of the University of California. .\" All rights reserved. .\" -.\" %sccs.include.redist.man% +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. .\" -.\" @(#)radixsort.3 5.4 (Berkeley) %G% +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. .\" -.TH radixsort 3 "" -.SH NAME -radixsort \- radix sort -.SH SYNOPSIS -.nf -.ft B -#include -#include - -radixsort(u_char **base, int nmemb, u_char *table, u_char endbyte); -.ft R -.fi -.SH DESCRIPTION -.I Radixsort +.\" @(#)radixsort.3 5.5 (Berkeley) 4/19/91 +.\" +.Dd April 19, 1991 +.Dt RADIXSORT 3 +.Os +.Sh NAME +.Nm radixsort +.Nd radix sort +.Sh SYNOPSIS +.Fd #include +.Fd #include +.Ft int +.Fn radixsort "u_char **base" "int nmemb" "u_char *table" "u_char endbyte" +.Sh DESCRIPTION +The +.Fn radixsort +function is a modified radix sort. -.PP +.Pp The -.I radixsort +.Fn radixsort function sorts an array of -.I nmemb +.Fa nmemb pointers to byte strings, the initial member of which is referenced by -.IR base . +.Fa base . The byte strings may contain any values; the end of each string is denoted by the user-specified value -.IR endbyte . +.Fa endbyte . The contents of the array are sorted in ascending order according -to the ASCII order of the byte strings they reference. -.PP +to the +.Tn ASCII +order of the byte strings they reference. +.Pp Applications may specify a sort order by providing the -.IR table +.Fa table argument. -If non-NULL, -.I table -must reference an array of UCHAR_MAX + 1 bytes which contains the sort +If +.Pf non- Dv NULL , +.Fa table +must reference an array of +.Dv UCHAR_MAX ++ 1 bytes which contains the sort weight of each possible byte value. The end-of-string byte must have a sort weight of 0. More than one byte may have the same sort weight. -.I Table +The +.Fa table +argument is useful for applications which wish to sort different characters equally; for example, providing a table with the same weights for A-Z as for a-z will result in a case-insensitive sort. -.PP -.I Radixsort +.Pp +The +.Fn radixsort +function is stable, that is, if two elements compare as equal, their order in the sorted array is unchanged. -.PP -.I Radixsort +.Pp +The +.Fn radixsort +function is a variant of most-significant-byte radix sorting; in particular, see D.E. Knuth's Algorithm R and section 5.2.5, exercise 10. -.I Radixsort +The +.Fn radixsort +function takes linear time relative to the number of bytes in the strings. -.SH SEE ALSO -sort(1), qsort(3) -.sp -Knuth, D.E. [1968]. "The Art of Computer Programming Vol. 3: -Sorting and Searching", pp. 170-178. -.br -Paige, R. [1987]. "Three Partition Refinement Algorithms", -SIAM J. Comput. Vol. 16, No. 6. -.SH "RETURN VALUES" +.Sh RETURN VALUES Upon successful completion 0 is returned. Otherwise, \-1 is returned and the global variable -.I errno +.Va errno is set to indicate the error. -.SH ERRORS -.I Radixsort +.Sh ERRORS +The +.Fn radixsort +function may fail and set -.I errno +.Va errno for any of the errors specified for the library routine -.IR malloc (3). -.SH BUGS -.I Nmemb -must be less than the maximum integer, INT_MAX. +.Xr malloc 3 . +.Sh SEE ALSO +.Xr sort 1 , +.Xr qsort 3 +.Pp +.Rs +.%A Knuth, D.E. +.%D 1968 +.%B "The Art of Computer Programming" +.%T "Sorting and Searching" +.%V Vol. 3 +.%P pp. 170-178 +.Re +.Rs +.%A Paige, R. +.%D 1987 +.%T "Three Partition Refinement Algorithms" +.%J "SIAM J. Comput." +.%V Vol. 16 +.%N No. 6 +.Re +.Sh HISTORY +The +.Fn radixsort +function is +.Ud . +.Sh BUGS +The +.Fa nmemb +argument +must be less than the maximum integer, +.Dv INT_MAX .