From 5dce0c1384f698b3a27a82e72e3cbcf49b325404 Mon Sep 17 00:00:00 2001 From: keramida Date: Tue, 19 Feb 2013 23:57:39 +0000 Subject: Add a sample program that shows how a custom comparison function and qsort(3) can work together to sort an array of integers. PR: docs/176197 Submitted by: Fernando, fapesteguia at opensistemas.com Approved by: gjb (mentor) MFC after: 1 week --- lib/libc/stdlib/qsort.3 | 48 +++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 47 insertions(+), 1 deletion(-) (limited to 'lib/libc/stdlib') diff --git a/lib/libc/stdlib/qsort.3 b/lib/libc/stdlib/qsort.3 index 0f7ef73..83d9140 100644 --- a/lib/libc/stdlib/qsort.3 +++ b/lib/libc/stdlib/qsort.3 @@ -32,7 +32,7 @@ .\" @(#)qsort.3 8.1 (Berkeley) 6/4/93 .\" $FreeBSD$ .\" -.Dd September 30, 2003 +.Dd February 20, 2013 .Dt QSORT 3 .Os .Sh NAME @@ -211,6 +211,52 @@ Previous versions of did not permit the comparison routine itself to call .Fn qsort 3 . This is no longer true. +.Sh EXAMPLES +A sample program that sorts an array of +.Vt int +values in place using +.Fn qsort , +and then prints the sorted array to standard output is: +.Bd -literal +#include +#include +#include + +/* + * Custom comparison function that can compare 'int' values through pointers + * passed by qsort(3). + */ +static int +int_compare(const void *p1, const void *p2) +{ + int *left = (int *)p1; + int *right = (int *)p2; + + if (*left < *right) + return (-1); + else if (*left > *right) + return (1); + else + return (0); +} + +/* + * Sort an array of 'int' values and print it to standard output. + */ +int +main(void) +{ + int int_array[] = { 4, 5, 9, 3, 0, 1, 7, 2, 8, 6 }; + const int array_size = sizeof(int_array) / sizeof(int_array[0]); + int k; + + qsort(&int_array, array_size, sizeof(int), int_compare); + for (k = 0; k < array_size; k++) + printf(" %d", int_array[k]); + printf("\\n"); + exit(EXIT_SUCCESS); +} +.Ed .Sh ERRORS The .Fn heapsort -- cgit v1.1 From 1183d7a09c590e018fd2b8740e7c6525a014a246 Mon Sep 17 00:00:00 2001 From: keramida Date: Wed, 20 Feb 2013 18:31:55 +0000 Subject: Various improvements to the qsort(3) usage example: - Remove unused #include. - Do not cast away const. - Use the canonical idiom to compare two numbers. - Use proper type for sizes, i.e. size_t instead of int. - Correct indentation. - Simplify printf("\n") to puts(""). - Use return instead of exit() in main(). Submitted by: Christoph Mallon, christoph.mallon at gmx.de Approved by: gjb (mentor) Reviewed by: stefanf MFC after: 1 week --- lib/libc/stdlib/qsort.3 | 22 ++++++++-------------- 1 file changed, 8 insertions(+), 14 deletions(-) (limited to 'lib/libc/stdlib') diff --git a/lib/libc/stdlib/qsort.3 b/lib/libc/stdlib/qsort.3 index 83d9140..a39517f 100644 --- a/lib/libc/stdlib/qsort.3 +++ b/lib/libc/stdlib/qsort.3 @@ -220,7 +220,6 @@ and then prints the sorted array to standard output is: .Bd -literal #include #include -#include /* * Custom comparison function that can compare 'int' values through pointers @@ -229,15 +228,10 @@ and then prints the sorted array to standard output is: static int int_compare(const void *p1, const void *p2) { - int *left = (int *)p1; - int *right = (int *)p2; + int left = *(const int *)p1; + int right = *(const int *)p2; - if (*left < *right) - return (-1); - else if (*left > *right) - return (1); - else - return (0); + return ((left > right) - (left < right)); } /* @@ -247,14 +241,14 @@ int main(void) { int int_array[] = { 4, 5, 9, 3, 0, 1, 7, 2, 8, 6 }; - const int array_size = sizeof(int_array) / sizeof(int_array[0]); - int k; + const size_t array_size = sizeof(int_array) / sizeof(int_array[0]); + size_t k; - qsort(&int_array, array_size, sizeof(int), int_compare); + qsort(&int_array, array_size, sizeof(int_array[0]), int_compare); for (k = 0; k < array_size; k++) printf(" %d", int_array[k]); - printf("\\n"); - exit(EXIT_SUCCESS); + puts(""); + return (EXIT_SUCCESS); } .Ed .Sh ERRORS -- cgit v1.1 From 4778623d426b579d28de62ccf6bd1e9aeba0c58f Mon Sep 17 00:00:00 2001 From: joel Date: Wed, 20 Feb 2013 19:05:13 +0000 Subject: Sort sections. --- lib/libc/stdlib/qsort.3 | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'lib/libc/stdlib') diff --git a/lib/libc/stdlib/qsort.3 b/lib/libc/stdlib/qsort.3 index a39517f..f34d260 100644 --- a/lib/libc/stdlib/qsort.3 +++ b/lib/libc/stdlib/qsort.3 @@ -205,12 +205,6 @@ functions return no value. .Pp .Rv -std heapsort mergesort -.Sh COMPATIBILITY -Previous versions of -.Fn qsort -did not permit the comparison routine itself to call -.Fn qsort 3 . -This is no longer true. .Sh EXAMPLES A sample program that sorts an array of .Vt int @@ -251,6 +245,12 @@ main(void) return (EXIT_SUCCESS); } .Ed +.Sh COMPATIBILITY +Previous versions of +.Fn qsort +did not permit the comparison routine itself to call +.Fn qsort 3 . +This is no longer true. .Sh ERRORS The .Fn heapsort -- cgit v1.1 From 8ca73cd0cf0b0f0dce53840b864ee25cf2f2ebbb Mon Sep 17 00:00:00 2001 From: keramida Date: Sat, 23 Feb 2013 12:31:52 +0000 Subject: Now that qsort(3) has a sample comparison function, point to that example from bsearch(3) too, so that we don't have to duplicate the example code in both places. PR: docs/176197 Reviewed by: stefanf Approved by: remko (mentor), gjb (mentor) MFC after: 1 week --- lib/libc/stdlib/bsearch.3 | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) (limited to 'lib/libc/stdlib') diff --git a/lib/libc/stdlib/bsearch.3 b/lib/libc/stdlib/bsearch.3 index b3591f8e..25be842 100644 --- a/lib/libc/stdlib/bsearch.3 +++ b/lib/libc/stdlib/bsearch.3 @@ -32,7 +32,7 @@ .\" @(#)bsearch.3 8.3 (Berkeley) 4/19/94 .\" $FreeBSD$ .\" -.Dd April 19, 1994 +.Dd February 22, 2013 .Dt BSEARCH 3 .Os .Sh NAME @@ -71,6 +71,12 @@ less than, equal to, or greater than zero if the .Fa key object is found, respectively, to be less than, to match, or be greater than the array member. +See the +.Fa int_compare +sample function in +.Xr qsort 3 +for a comparison function that is also compatible with +.Fn bsearch . .Sh RETURN VALUES The .Fn bsearch -- cgit v1.1 From 296df9cb791e840eba6397812105beac6b27dfa8 Mon Sep 17 00:00:00 2001 From: kevlo Date: Mon, 18 Mar 2013 01:22:28 +0000 Subject: Add restrict keyword to realpath manpage. --- lib/libc/stdlib/realpath.3 | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/libc/stdlib') diff --git a/lib/libc/stdlib/realpath.3 b/lib/libc/stdlib/realpath.3 index c7384d6..33970fd 100644 --- a/lib/libc/stdlib/realpath.3 +++ b/lib/libc/stdlib/realpath.3 @@ -42,7 +42,7 @@ .Sh SYNOPSIS .In stdlib.h .Ft "char *" -.Fn realpath "const char *pathname" "char *resolved_path" +.Fn realpath "const char * restrict pathname" "char * restrict resolved_path" .Sh DESCRIPTION The .Fn realpath -- cgit v1.1 From 08ef412169e7d1b670ae8d57bfd6adfdace32ca4 Mon Sep 17 00:00:00 2001 From: delphij Date: Tue, 2 Apr 2013 23:41:20 +0000 Subject: Replace access to /dev/random with the kernel pseudo-random number source sysctl(KERN_ARND) and remove the fallback code. Obtained from: OpenBSD Reviewed by: secteam MFC after: 1 month --- lib/libc/stdlib/rand.3 | 6 ++---- lib/libc/stdlib/rand.c | 33 ++++++++++++--------------------- lib/libc/stdlib/random.3 | 6 +++--- lib/libc/stdlib/random.c | 42 +++++++++++++++--------------------------- 4 files changed, 32 insertions(+), 55 deletions(-) (limited to 'lib/libc/stdlib') diff --git a/lib/libc/stdlib/rand.3 b/lib/libc/stdlib/rand.3 index 390a40b..bf50e3d 100644 --- a/lib/libc/stdlib/rand.3 +++ b/lib/libc/stdlib/rand.3 @@ -32,7 +32,7 @@ .\" @(#)rand.3 8.1 (Berkeley) 6/4/93 .\" $FreeBSD$ .\" -.Dd September 4, 2012 +.Dd April 2, 2013 .Dt RAND 3 .Os .Sh NAME @@ -91,9 +91,7 @@ seeded with a value of 1. .Pp The .Fn sranddev -function initializes a seed using the -.Xr random 4 -random number device which returns good random numbers. +function initializes a seed using pseudo-random numbers obtained from the kernel. .Pp The .Fn rand_r diff --git a/lib/libc/stdlib/rand.c b/lib/libc/stdlib/rand.c index 7041818..0cbd948 100644 --- a/lib/libc/stdlib/rand.c +++ b/lib/libc/stdlib/rand.c @@ -36,11 +36,10 @@ static char sccsid[] = "@(#)rand.c 8.1 (Berkeley) 6/14/93"; __FBSDID("$FreeBSD$"); #include "namespace.h" -#include /* for sranddev() */ +#include +#include #include -#include /* for sranddev() */ #include -#include /* for sranddev() */ #include "un-namespace.h" #ifdef TEST @@ -112,28 +111,20 @@ u_int seed; * sranddev: * * Many programs choose the seed value in a totally predictable manner. - * This often causes problems. We seed the generator using the much more - * secure random(4) interface. + * This often causes problems. We seed the generator using pseudo-random + * data from the kernel. */ void sranddev() { - int fd, done; - - done = 0; - fd = _open("/dev/random", O_RDONLY | O_CLOEXEC, 0); - if (fd >= 0) { - if (_read(fd, (void *) &next, sizeof(next)) == sizeof(next)) - done = 1; - _close(fd); - } - - if (!done) { - struct timeval tv; - - gettimeofday(&tv, NULL); - srand((getpid() << 16) ^ tv.tv_sec ^ tv.tv_usec); - } + int mib[2]; + size_t len; + + len = sizeof(next); + + mib[0] = CTL_KERN; + mib[1] = KERN_ARND; + sysctl(mib, 2, (void *)&next, &len, NULL, 0); } diff --git a/lib/libc/stdlib/random.3 b/lib/libc/stdlib/random.3 index 4817440..a1e585b 100644 --- a/lib/libc/stdlib/random.3 +++ b/lib/libc/stdlib/random.3 @@ -28,7 +28,7 @@ .\" @(#)random.3 8.1 (Berkeley) 6/4/93 .\" $FreeBSD$ .\" -.Dd September 4, 2012 +.Dd April 2, 2013 .Dt RANDOM 3 .Os .Sh NAME @@ -106,8 +106,8 @@ as the seed. .Pp The .Fn srandomdev -routine initializes a state array using data from -.Xr random 4 . +routine initializes a state array using +pseudo-random numbers obtained from the kernel. Note that this particular seeding procedure can generate states which are impossible to reproduce by calling diff --git a/lib/libc/stdlib/random.c b/lib/libc/stdlib/random.c index a3c054e..4c88ecb 100644 --- a/lib/libc/stdlib/random.c +++ b/lib/libc/stdlib/random.c @@ -34,12 +34,11 @@ static char sccsid[] = "@(#)random.c 8.2 (Berkeley) 5/19/95"; __FBSDID("$FreeBSD$"); #include "namespace.h" -#include /* for srandomdev() */ -#include /* for srandomdev() */ +#include +#include #include #include #include -#include /* for srandomdev() */ #include "un-namespace.h" /* @@ -284,39 +283,28 @@ srandom(unsigned long x) * srandomdev: * * Many programs choose the seed value in a totally predictable manner. - * This often causes problems. We seed the generator using the much more - * secure random(4) interface. Note that this particular seeding - * procedure can generate states which are impossible to reproduce by - * calling srandom() with any value, since the succeeding terms in the - * state buffer are no longer derived from the LC algorithm applied to - * a fixed seed. + * This often causes problems. We seed the generator using pseudo-random + * data from the kernel. + * + * Note that this particular seeding procedure can generate states + * which are impossible to reproduce by calling srandom() with any + * value, since the succeeding terms in the state buffer are no longer + * derived from the LC algorithm applied to a fixed seed. */ void srandomdev(void) { - int fd, done; + int mib[2]; size_t len; if (rand_type == TYPE_0) - len = sizeof state[0]; + len = sizeof(state[0]); else - len = rand_deg * sizeof state[0]; - - done = 0; - fd = _open("/dev/random", O_RDONLY | O_CLOEXEC, 0); - if (fd >= 0) { - if (_read(fd, (void *) state, len) == (ssize_t) len) - done = 1; - _close(fd); - } + len = rand_deg * sizeof(state[0]); - if (!done) { - struct timeval tv; - - gettimeofday(&tv, NULL); - srandom((getpid() << 16) ^ tv.tv_sec ^ tv.tv_usec); - return; - } + mib[0] = CTL_KERN; + mib[1] = KERN_ARND; + sysctl(mib, 2, state, &len, NULL, 0); if (rand_type != TYPE_0) { fptr = &state[rand_sep]; -- cgit v1.1