summaryrefslogtreecommitdiff
path: root/src/lib/libc/stdlib/radixsort.3
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libc/stdlib/radixsort.3')
-rw-r--r--src/lib/libc/stdlib/radixsort.333
1 files changed, 14 insertions, 19 deletions
diff --git a/src/lib/libc/stdlib/radixsort.3 b/src/lib/libc/stdlib/radixsort.3
index a2af9f17a4..f70990fa8e 100644
--- a/src/lib/libc/stdlib/radixsort.3
+++ b/src/lib/libc/stdlib/radixsort.3
@@ -29,8 +29,7 @@
29.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30.\" SUCH DAMAGE. 30.\" SUCH DAMAGE.
31.\" 31.\"
32.\" from: @(#)radixsort.3 8.2 (Berkeley) 1/27/94 32.\" $OpenBSD: radixsort.3,v 1.7 2001/08/06 10:42:26 mpech Exp $
33.\" $Id: radixsort.3,v 1.1.1.1 1995/10/18 08:42:18 deraadt Exp $
34.\" 33.\"
35.Dd January 27, 1994 34.Dd January 27, 1994
36.Dt RADIXSORT 3 35.Dt RADIXSORT 3
@@ -42,16 +41,15 @@
42.Fd #include <limits.h> 41.Fd #include <limits.h>
43.Fd #include <stdlib.h> 42.Fd #include <stdlib.h>
44.Ft int 43.Ft int
45.Fn radixsort "u_char **base" "int nmemb" "u_char *table" "u_int endbyte" 44.Fn radixsort "const u_char **base" "int nmemb" "const u_char *table" "u_int endbyte"
46.Ft int 45.Ft int
47.Fn sradixsort "u_char **base" "int nmemb" "u_char *table" "u_int endbyte" 46.Fn sradixsort "const u_char **base" "int nmemb" "const u_char *table" "u_int endbyte"
48.Sh DESCRIPTION 47.Sh DESCRIPTION
49The 48The
50.Fn radixsort 49.Fn radixsort
51and 50and
52.Fn sradixsort 51.Fn sradixsort
53functions 52functions are implementations of radix sort.
54are implementations of radix sort.
55.Pp 53.Pp
56These functions sort an array of pointers to byte strings, the initial 54These functions sort an array of pointers to byte strings, the initial
57member of which is referenced by 55member of which is referenced by
@@ -63,26 +61,24 @@ is denoted by the user-specified value
63Applications may specify a sort order by providing the 61Applications may specify a sort order by providing the
64.Fa table 62.Fa table
65argument. 63argument.
66If 64If non-null,
67.Pf non- Dv NULL ,
68.Fa table 65.Fa table
69must reference an array of 66must reference an array of
70.Dv UCHAR_MAX 67.Dv UCHAR_MAX
71+ 1 bytes which contains the sort 68+ 1 bytes which contains the sort weight of each possible byte value.
72weight of each possible byte value.
73The end-of-string byte must have a sort weight of 0 or 255 69The end-of-string byte must have a sort weight of 0 or 255
74(for sorting in reverse order). 70(for sorting in reverse order).
75More than one byte may have the same sort weight. 71More than one byte may have the same sort weight.
76The 72The
77.Fa table 73.Fa table
78argument 74argument is useful for applications which wish to sort different characters
79is useful for applications which wish to sort different characters
80equally, for example, providing a table with the same weights 75equally, for example, providing a table with the same weights
81for A-Z as for a-z will result in a case-insensitive sort. 76for A-Z as for a-z will result in a case-insensitive sort.
82If 77If
83.Fa table 78.Fa table
84is NULL, the contents of the array are sorted in ascending order 79is
85according to the 80.Dv NULL ,
81the contents of the array are sorted in ascending order according to the
86.Tn ASCII 82.Tn ASCII
87order of the byte strings they reference and 83order of the byte strings they reference and
88.Fa endbyte 84.Fa endbyte
@@ -107,7 +103,7 @@ particular, see D.E. Knuth's Algorithm R and section 5.2.5, exercise 10.
107They take linear time relative to the number of bytes in the strings. 103They take linear time relative to the number of bytes in the strings.
108.Sh RETURN VALUES 104.Sh RETURN VALUES
109Upon successful completion 0 is returned. 105Upon successful completion 0 is returned.
110Otherwise, \-1 is returned and the global variable 106Otherwise, \-1 is returned and the global variable
111.Va errno 107.Va errno
112is set to indicate the error. 108is set to indicate the error.
113.Sh ERRORS 109.Sh ERRORS
@@ -122,15 +118,13 @@ is not 0 or 255.
122.Pp 118.Pp
123Additionally, the 119Additionally, the
124.Fn sradixsort 120.Fn sradixsort
125function 121function may fail and set
126may fail and set
127.Va errno 122.Va errno
128for any of the errors specified for the library routine 123for any of the errors specified for the library routine
129.Xr malloc 3 . 124.Xr malloc 3 .
130.Sh SEE ALSO 125.Sh SEE ALSO
131.Xr sort 1 , 126.Xr sort 1 ,
132.Xr qsort 3 127.Xr qsort 3
133.Pp
134.Rs 128.Rs
135.%A Knuth, D.E. 129.%A Knuth, D.E.
136.%D 1968 130.%D 1968
@@ -158,4 +152,5 @@ for any of the errors specified for the library routine
158.Sh HISTORY 152.Sh HISTORY
159The 153The
160.Fn radixsort 154.Fn radixsort
161function first appeared in 4.4BSD. 155function first appeared in
156.Bx 4.4 .