diff options
Diffstat (limited to 'lib/libc/stdlib')
-rw-r--r-- | lib/libc/stdlib/getenv.3 | 6 | ||||
-rw-r--r-- | lib/libc/stdlib/qsort.3 | 15 | ||||
-rw-r--r-- | lib/libc/stdlib/radixsort.3 | 5 | ||||
-rw-r--r-- | lib/libc/stdlib/random.3 | 12 | ||||
-rw-r--r-- | lib/libc/stdlib/tsearch.3 | 6 |
5 files changed, 30 insertions, 14 deletions
diff --git a/lib/libc/stdlib/getenv.3 b/lib/libc/stdlib/getenv.3 index 269fecb..11922a7 100644 --- a/lib/libc/stdlib/getenv.3 +++ b/lib/libc/stdlib/getenv.3 @@ -144,13 +144,15 @@ assigning a differently sized .Fa value to the same .Fa name -will result in a memory leak. The +will result in a memory leak. +The .Fx semantics for these functions (namely, that the contents of .Fa value are copied and that old values remain accessible indefinitely) make this -bug unavoidable. Future versions may eliminate one or both of these +bug unavoidable. +Future versions may eliminate one or both of these semantic guarantees in order to fix the bug. .Sh HISTORY The functions diff --git a/lib/libc/stdlib/qsort.3 b/lib/libc/stdlib/qsort.3 index 6dfffd6..07777db 100644 --- a/lib/libc/stdlib/qsort.3 +++ b/lib/libc/stdlib/qsort.3 @@ -149,11 +149,13 @@ The .Fn qsort and .Fn qsort_r -functions are an implementation of C.A.R. Hoare's +functions are an implementation of C.A.R. +Hoare's .Dq quicksort algorithm, -a variant of partition-exchange sorting; in particular, see D.E. Knuth's -Algorithm Q. +a variant of partition-exchange sorting; in particular, see +.An D.E. Knuth Ns 's +.%T "Algorithm Q" . .Sy Quicksort takes O N lg N average time. This implementation uses median selection to avoid its @@ -161,10 +163,13 @@ O N**2 worst-case behavior. .Pp The .Fn heapsort -function is an implementation of J.W.J. William's +function is an implementation of +.An "J.W.J. William" Ns 's .Dq heapsort algorithm, -a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. +a variant of selection sorting; in particular, see +.An "D.E. Knuth" Ns 's +.%T "Algorithm H" . .Sy Heapsort takes O N lg N worst-case time. Its diff --git a/lib/libc/stdlib/radixsort.3 b/lib/libc/stdlib/radixsort.3 index 9558259..da4ed16 100644 --- a/lib/libc/stdlib/radixsort.3 +++ b/lib/libc/stdlib/radixsort.3 @@ -105,7 +105,10 @@ The function is not stable, but uses no additional memory. .Pp These functions are variants of most-significant-byte radix sorting; in -particular, see D.E. Knuth's Algorithm R and section 5.2.5, exercise 10. +particular, see +.An "D.E. Knuth" Ns 's +.%T "Algorithm R" +and section 5.2.5, exercise 10. They take linear time relative to the number of bytes in the strings. .Sh RETURN VALUES .Rv -std radixsort diff --git a/lib/libc/stdlib/random.3 b/lib/libc/stdlib/random.3 index 66ccd55..a1dbf8a 100644 --- a/lib/libc/stdlib/random.3 +++ b/lib/libc/stdlib/random.3 @@ -81,9 +81,11 @@ functions. The difference is that .Xr rand 3 produces a much less random sequence \(em in fact, the low dozen bits -generated by rand go through a cyclic pattern. All the bits generated by +generated by rand go through a cyclic pattern. +All the bits generated by .Fn random -are usable. For example, +are usable. +For example, .Sq Li random()&01 will produce a random binary value. @@ -115,13 +117,15 @@ a fixed seed. The .Fn initstate routine allows a state array, passed in as an argument, to be initialized -for future use. The size of the state array (in bytes) is used by +for future use. +The size of the state array (in bytes) is used by .Fn initstate to decide how sophisticated a random number generator it should use \(em the more state, the better the random numbers will be. (Current "optimal" values for the amount of state information are 8, 32, 64, 128, and 256 bytes; other amounts will be rounded down to -the nearest known amount. Using less than 8 bytes will cause an error.) +the nearest known amount. +Using less than 8 bytes will cause an error.) The seed for the initialization (which specifies a starting point for the random number sequence, and provides for restarting at the same point) is also an argument. diff --git a/lib/libc/stdlib/tsearch.3 b/lib/libc/stdlib/tsearch.3 index 0c7f1bd..ea0a9da 100644 --- a/lib/libc/stdlib/tsearch.3 +++ b/lib/libc/stdlib/tsearch.3 @@ -51,7 +51,8 @@ The and .Fn twalk functions manage binary search trees based on algorithms T and D -from Knuth (6.2.2). The comparison function passed in by +from Knuth (6.2.2). +The comparison function passed in by the user has the same style of return values as .Xr strcmp 3 . .Pp @@ -72,7 +73,8 @@ is identical to .Fn tfind except that if no match is found, .Fa key -is inserted into the tree and a pointer to it is returned. If +is inserted into the tree and a pointer to it is returned. +If .Fa rootp points to a NULL value a new binary search tree is created. .Pp |