Date: Wed, 2 Apr 2014 16:07:48 +0000 (UTC) From: David Chisnall <theraven@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r264042 - in head: include lib/libc/gen lib/libc/include lib/libc/stdlib Message-ID: <201404021607.s32G7mhw051355@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: theraven Date: Wed Apr 2 16:07:48 2014 New Revision: 264042 URL: http://svnweb.freebsd.org/changeset/base/264042 Log: Add support for some block functions that come from OS X. These are intended to build with any C compiler. Reviewed by: pfg MFC after: 3 weeks Added: head/lib/libc/gen/scandir_b.c (contents, props changed) head/lib/libc/include/block_abi.h (contents, props changed) head/lib/libc/stdlib/bsearch_b.c (contents, props changed) head/lib/libc/stdlib/heapsort_b.c (contents, props changed) head/lib/libc/stdlib/mergesort_b.c (contents, props changed) Modified: head/include/dirent.h head/include/stdlib.h head/lib/libc/gen/Symbol.map head/lib/libc/gen/scandir.3 head/lib/libc/gen/scandir.c head/lib/libc/stdlib/Makefile.inc head/lib/libc/stdlib/Symbol.map head/lib/libc/stdlib/atexit.3 head/lib/libc/stdlib/atexit.c head/lib/libc/stdlib/bsearch.c head/lib/libc/stdlib/heapsort.c head/lib/libc/stdlib/merge.c head/lib/libc/stdlib/qsort.3 head/lib/libc/stdlib/qsort_r.c Modified: head/include/dirent.h ============================================================================== --- head/include/dirent.h Wed Apr 2 15:56:11 2014 (r264041) +++ head/include/dirent.h Wed Apr 2 16:07:48 2014 (r264042) @@ -95,6 +95,11 @@ void rewinddir(DIR *); int scandir(const char *, struct dirent ***, int (*)(const struct dirent *), int (*)(const struct dirent **, const struct dirent **)); +#ifdef __BLOCKS__ +int scandir_b(const char *, struct dirent ***, + int (^)(const struct dirent *), + int (^)(const struct dirent **, const struct dirent **)); +#endif #endif #if __XSI_VISIBLE void seekdir(DIR *, long); Modified: head/include/stdlib.h ============================================================================== --- head/include/stdlib.h Wed Apr 2 15:56:11 2014 (r264041) +++ head/include/stdlib.h Wed Apr 2 16:07:48 2014 (r264042) @@ -82,6 +82,9 @@ extern int ___mb_cur_max(void); _Noreturn void abort(void); int abs(int) __pure2; int atexit(void (*)(void)); +#ifdef __BLOCKS__ +int atexit_b(void (^)(void)); +#endif double atof(const char *); int atoi(const char *); long atol(const char *); @@ -100,6 +103,10 @@ size_t mbstowcs(wchar_t * __restrict , int mbtowc(wchar_t * __restrict, const char * __restrict, size_t); void qsort(void *, size_t, size_t, int (*)(const void *, const void *)); +#ifdef __BLOCKS__ +void qsort_b(void *, size_t, size_t, + int (^)(const void *, const void *)); +#endif int rand(void); void *realloc(void *, size_t); void srand(unsigned); @@ -280,8 +287,14 @@ const char * getprogname(void); int heapsort(void *, size_t, size_t, int (*)(const void *, const void *)); +#ifdef __BLOCKS__ +int heapsort_b(void *, size_t, size_t, int (^)(const void *, const void *)); +#endif int l64a_r(long, char *, int); int mergesort(void *, size_t, size_t, int (*)(const void *, const void *)); +#ifdef __BLOCKS__ +int mergesort_b(void *, size_t, size_t, int (^)(const void *, const void *)); +#endif int mkostemp(char *, int); int mkostemps(char *, int, int); void qsort_r(void *, size_t, size_t, void *, Modified: head/lib/libc/gen/Symbol.map ============================================================================== --- head/lib/libc/gen/Symbol.map Wed Apr 2 15:56:11 2014 (r264041) +++ head/lib/libc/gen/Symbol.map Wed Apr 2 16:07:48 2014 (r264042) @@ -349,6 +349,7 @@ FBSD_1.1 { posix_spawnattr_setsigdefault; posix_spawnattr_setsigmask; posix_spawnp; + scandir_b; semctl; tcgetsid; tcsetsid; Modified: head/lib/libc/gen/scandir.3 ============================================================================== --- head/lib/libc/gen/scandir.3 Wed Apr 2 15:56:11 2014 (r264041) +++ head/lib/libc/gen/scandir.3 Wed Apr 2 16:07:48 2014 (r264042) @@ -42,6 +42,8 @@ .Ft int .Fn scandir "const char *dirname" "struct dirent ***namelist" "int \*(lp*select\*(rp\*(lpconst struct dirent *\*(rp" "int \*(lp*compar\*(rp\*(lpconst struct dirent **, const struct dirent **\*(rp" .Ft int +.Fn scandir_b "const char *dirname" "struct dirent ***namelist" "int \*(lp*select\^(rp\*(lpconst struct dirent *\*(rp" "int \*(lp^compar\*(rp\*(lpconst struct dirent **, const struct dirent **\*(rp" +.Ft int .Fn alphasort "const struct dirent **d1" "const struct dirent **d2" .Sh DESCRIPTION The @@ -87,6 +89,15 @@ argument to sort the array alphabeticall The memory allocated for the array can be deallocated with .Xr free 3 , by freeing each pointer in the array and then the array itself. +.Pp +The +.Fn scandir_b +function behaves in the same way as +.Fn scandir , +but takes blocks as arguments instead of function pointers and calls +.Fn qsort_b +rather than +.Fn qsort . .Sh DIAGNOSTICS Returns \-1 if the directory cannot be opened for reading or if .Xr malloc 3 Modified: head/lib/libc/gen/scandir.c ============================================================================== --- head/lib/libc/gen/scandir.c Wed Apr 2 15:56:11 2014 (r264041) +++ head/lib/libc/gen/scandir.c Wed Apr 2 16:07:48 2014 (r264042) @@ -46,6 +46,17 @@ __FBSDID("$FreeBSD$"); #include <string.h> #include "un-namespace.h" +#ifdef I_AM_SCANDIR_B +#include "block_abi.h" +#define SELECT(x) CALL_BLOCK(select, x) +#ifndef __BLOCKS__ +void +qsort_b(void *, size_t, size_t, void*); +#endif +#else +#define SELECT(x) select(x) +#endif + static int alphasort_thunk(void *thunk, const void *p1, const void *p2); /* @@ -60,9 +71,15 @@ static int alphasort_thunk(void *thunk, (((dp)->d_namlen + 1 + 3) &~ 3)) int +#ifdef I_AM_SCANDIR_B +scandir_b(const char *dirname, struct dirent ***namelist, + DECLARE_BLOCK(int, select, const struct dirent *), + DECLARE_BLOCK(int, dcomp, const struct dirent **, const struct dirent **)) +#else scandir(const char *dirname, struct dirent ***namelist, int (*select)(const struct dirent *), int (*dcomp)(const struct dirent **, const struct dirent **)) +#endif { struct dirent *d, *p, **names = NULL; size_t nitems = 0; @@ -78,7 +95,7 @@ scandir(const char *dirname, struct dire goto fail; while ((d = readdir(dirp)) != NULL) { - if (select != NULL && !(*select)(d)) + if (select != NULL && !SELECT(d)) continue; /* just selected names */ /* * Make a minimum size copy of the data @@ -111,8 +128,12 @@ scandir(const char *dirname, struct dire } closedir(dirp); if (nitems && dcomp != NULL) +#ifdef I_AM_SCANDIR_B + qsort_b(names, nitems, sizeof(struct dirent *), (void*)dcomp); +#else qsort_r(names, nitems, sizeof(struct dirent *), &dcomp, alphasort_thunk); +#endif *namelist = names; return (nitems); Added: head/lib/libc/gen/scandir_b.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/lib/libc/gen/scandir_b.c Wed Apr 2 16:07:48 2014 (r264042) @@ -0,0 +1,29 @@ +/*- + * Copyright (c) 2014 David Chisnall + * All rights reserved. + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. + * + * $FreeBSD$ + */ +#define I_AM_SCANDIR_B +#include "scandir.c" Added: head/lib/libc/include/block_abi.h ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/lib/libc/include/block_abi.h Wed Apr 2 16:07:48 2014 (r264042) @@ -0,0 +1,63 @@ +/*- + * Copyright (c) 2014 David T Chisnall + * All rights reserved. + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. + * + * $FreeBSD$ + */ + +#ifdef __BLOCKS__ +/** + * Declares a block variable. This macro is defined in the trivial way for + * compilers that support blocks and exposing the ABI in the source for other + * compilers. + */ +#define DECLARE_BLOCK(retTy, name, argTys, ...)\ + retTy(^name)(argTys, ## __VA_ARGS__) +/** + * Calls a block variable. This macro is defined in the trivial way for + * compilers that support blocks and exposing the ABI in the source for other + * compilers. + */ +#define CALL_BLOCK(name, ...) name(__VA_ARGS__) +#else // !__BLOCKS__ +#define DECLARE_BLOCK(retTy, name, argTys, ...)\ + struct {\ + void *isa;\ + int flags;\ + int reserved;\ + retTy (*invoke)(void *, ...);\ + } *name +#define CALL_BLOCK(name, ...) (name)->invoke(name, __VA_ARGS__) +#endif // __BLOCKS__ +/** + * Returns the pointer to the block-invoke function. This is used for passing + * blocks to functions that want a function pointer and a data pointer. + */ +#define GET_BLOCK_FUNCTION(x) \ + (((struct {\ + void *isa;\ + int flags;\ + int reserved;\ + void (*invoke)(void *, ...);\ + }*)x)->invoke) Modified: head/lib/libc/stdlib/Makefile.inc ============================================================================== --- head/lib/libc/stdlib/Makefile.inc Wed Apr 2 15:56:11 2014 (r264041) +++ head/lib/libc/stdlib/Makefile.inc Wed Apr 2 16:07:48 2014 (r264042) @@ -6,9 +6,10 @@ MISRCS+=_Exit.c a64l.c abort.c abs.c atexit.c atof.c atoi.c atol.c atoll.c \ bsearch.c div.c exit.c getenv.c getopt.c getopt_long.c \ - getsubopt.c hcreate.c heapsort.c imaxabs.c imaxdiv.c \ + getsubopt.c hcreate.c heapsort.c heapsort_b.c imaxabs.c imaxdiv.c \ insque.c l64a.c labs.c ldiv.c llabs.c lldiv.c lsearch.c \ - merge.c ptsname.c qsort.c qsort_r.c quick_exit.c radixsort.c rand.c \ + merge.c mergesort_b.c ptsname.c qsort.c qsort_r.c quick_exit.c \ + radixsort.c rand.c \ random.c reallocf.c realpath.c remque.c strfmon.c strtoimax.c \ strtol.c strtoll.c strtoq.c strtoul.c strtonum.c strtoull.c \ strtoumax.c strtouq.c system.c tdelete.c tfind.c tsearch.c twalk.c Modified: head/lib/libc/stdlib/Symbol.map ============================================================================== --- head/lib/libc/stdlib/Symbol.map Wed Apr 2 15:56:11 2014 (r264041) +++ head/lib/libc/stdlib/Symbol.map Wed Apr 2 16:07:48 2014 (r264042) @@ -86,10 +86,14 @@ FBSD_1.0 { FBSD_1.3 { at_quick_exit; + atexit_b; atof_l; atoi_l; atol_l; atoll_l; + heapsort_b; + mergesort_b; + qsort_b; quick_exit; strtod_l; strtof_l; Modified: head/lib/libc/stdlib/atexit.3 ============================================================================== --- head/lib/libc/stdlib/atexit.3 Wed Apr 2 15:56:11 2014 (r264041) +++ head/lib/libc/stdlib/atexit.3 Wed Apr 2 16:07:48 2014 (r264042) @@ -44,6 +44,8 @@ .In stdlib.h .Ft int .Fn atexit "void (*function)(void)" +.Ft int +.Fn atexit_b "void (^function)(void)" .Sh DESCRIPTION The .Fn atexit @@ -69,6 +71,12 @@ process termination, for example by call .Pp At least 32 functions can always be registered, and more are allowed as long as sufficient memory can be allocated. +.Pp +The +.Fn atexit_b +function behaves identically to +.Fn atexit , +except that it takes a block, rather than a function pointer. .\" XXX {ATEXIT_MAX} is not implemented yet .Sh RETURN VALUES .Rv -std atexit @@ -77,6 +85,12 @@ and more are allowed as long as sufficie .It Bq Er ENOMEM No memory was available to add the function to the list. The existing list of functions is unmodified. +.It Bq Er ENOSYS +The +.Fn atexit_b +function was called by a program that did not supply a +.Fn _Block_copy +implementation. .El .Sh SEE ALSO .Xr at_quick_exit 3 Modified: head/lib/libc/stdlib/atexit.c ============================================================================== --- head/lib/libc/stdlib/atexit.c Wed Apr 2 15:56:11 2014 (r264041) +++ head/lib/libc/stdlib/atexit.c Wed Apr 2 16:07:48 2014 (r264042) @@ -37,6 +37,7 @@ static char sccsid[] = "@(#)atexit.c 8.2 __FBSDID("$FreeBSD$"); #include "namespace.h" +#include <errno.h> #include <link.h> #include <stddef.h> #include <stdlib.h> @@ -44,9 +45,16 @@ __FBSDID("$FreeBSD$"); #include <pthread.h> #include "atexit.h" #include "un-namespace.h" +#include "block_abi.h" #include "libc_private.h" +/** + * The _Block_copy() function is provided by the block runtime. + */ +__attribute__((weak)) void* +_Block_copy(void*); + #define ATEXIT_FN_EMPTY 0 #define ATEXIT_FN_STD 1 #define ATEXIT_FN_CXA 2 @@ -125,7 +133,32 @@ atexit(void (*func)(void)) fn.fn_arg = NULL; fn.fn_dso = NULL; - error = atexit_register(&fn); + error = atexit_register(&fn); + return (error); +} + +/** + * Register a block to be performed at exit. + */ +int +atexit_b(DECLARE_BLOCK(void, func, void)) +{ + struct atexit_fn fn; + int error; + if (_Block_copy == 0) { + errno = ENOSYS; + return -1; + } + func = _Block_copy(func); + + // Blocks are not C++ destructors, but they have the same signature (a + // single void* parameter), so we can pretend that they are. + fn.fn_type = ATEXIT_FN_CXA; + fn.fn_ptr.cxa_func = (void(*)(void*))GET_BLOCK_FUNCTION(func); + fn.fn_arg = func; + fn.fn_dso = NULL; + + error = atexit_register(&fn); return (error); } @@ -144,7 +177,7 @@ __cxa_atexit(void (*func)(void *), void fn.fn_arg = arg; fn.fn_dso = dso; - error = atexit_register(&fn); + error = atexit_register(&fn); return (error); } Modified: head/lib/libc/stdlib/bsearch.c ============================================================================== --- head/lib/libc/stdlib/bsearch.c Wed Apr 2 15:56:11 2014 (r264041) +++ head/lib/libc/stdlib/bsearch.c Wed Apr 2 16:07:48 2014 (r264042) @@ -36,6 +36,13 @@ __FBSDID("$FreeBSD$"); #include <stddef.h> #include <stdlib.h> +#ifdef I_AM_BSEARCH_B +#include "block_abi.h" +#define COMPAR(x,y) CALL_BLOCK(compar, x, y) +#else +#define COMPAR(x,y) compar(x, y) +#endif + /* * Perform a binary search. * @@ -52,6 +59,15 @@ __FBSDID("$FreeBSD$"); * have to make lim 3, then halve, obtaining 1, so that we will only * look at item 3. */ +#ifdef I_AM_BSEARCH_B +void * +bsearch_b(key, base0, nmemb, size, compar) + const void *key; + const void *base0; + size_t nmemb; + size_t size; + DECLARE_BLOCK(int, compar, const void *, const void *); +#else void * bsearch(key, base0, nmemb, size, compar) const void *key; @@ -59,6 +75,7 @@ bsearch(key, base0, nmemb, size, compar) size_t nmemb; size_t size; int (*compar)(const void *, const void *); +#endif { const char *base = base0; size_t lim; @@ -67,7 +84,7 @@ bsearch(key, base0, nmemb, size, compar) for (lim = nmemb; lim != 0; lim >>= 1) { p = base + (lim >> 1) * size; - cmp = (*compar)(key, p); + cmp = COMPAR(key, p); if (cmp == 0) return ((void *)p); if (cmp > 0) { /* key > p: move right */ Added: head/lib/libc/stdlib/bsearch_b.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/lib/libc/stdlib/bsearch_b.c Wed Apr 2 16:07:48 2014 (r264042) @@ -0,0 +1,29 @@ +/*- + * Copyright (c) 2014 David Chisnall + * All rights reserved. + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. + * + * $FreeBSD$ + */ +#define I_AM_BSEARCH_B +#include "bsearch.c" Modified: head/lib/libc/stdlib/heapsort.c ============================================================================== --- head/lib/libc/stdlib/heapsort.c Wed Apr 2 15:56:11 2014 (r264041) +++ head/lib/libc/stdlib/heapsort.c Wed Apr 2 16:07:48 2014 (r264042) @@ -1,6 +1,8 @@ /*- * Copyright (c) 1991, 1993 * The Regents of the University of California. All rights reserved. + * Copyright (c) 2014 David T. Chisnall + * All rights reserved. * * This code is derived from software contributed to Berkeley by * Ronnie Kon at Mindcraft Inc., Kevin Lew and Elmer Yglesias. @@ -40,6 +42,13 @@ __FBSDID("$FreeBSD$"); #include <stddef.h> #include <stdlib.h> +#ifdef I_AM_HEAPSORT_B +#include "block_abi.h" +#define COMPAR(x, y) CALL_BLOCK(compar, x, y) +#else +#define COMPAR(x, y) compar(x, y) +#endif + /* * Swap two areas of size number of bytes. Although qsort(3) permits random * blocks of memory to be sorted, sorting pointers is almost certainly the @@ -77,12 +86,12 @@ __FBSDID("$FreeBSD$"); for (par_i = initval; (child_i = par_i * 2) <= nmemb; \ par_i = child_i) { \ child = base + child_i * size; \ - if (child_i < nmemb && compar(child, child + size) < 0) { \ + if (child_i < nmemb && COMPAR(child, child + size) < 0) { \ child += size; \ ++child_i; \ } \ par = base + par_i * size; \ - if (compar(child, par) <= 0) \ + if (COMPAR(child, par) <= 0) \ break; \ SWAP(par, child, count, size, tmp); \ } \ @@ -108,7 +117,7 @@ __FBSDID("$FreeBSD$"); #define SELECT(par_i, child_i, nmemb, par, child, size, k, count, tmp1, tmp2) { \ for (par_i = 1; (child_i = par_i * 2) <= nmemb; par_i = child_i) { \ child = base + child_i * size; \ - if (child_i < nmemb && compar(child, child + size) < 0) { \ + if (child_i < nmemb && COMPAR(child, child + size) < 0) { \ child += size; \ ++child_i; \ } \ @@ -120,7 +129,7 @@ __FBSDID("$FreeBSD$"); par_i = child_i / 2; \ child = base + child_i * size; \ par = base + par_i * size; \ - if (child_i == 1 || compar(k, par) < 0) { \ + if (child_i == 1 || COMPAR(k, par) < 0) { \ COPY(child, k, count, size, tmp1, tmp2); \ break; \ } \ @@ -135,11 +144,19 @@ __FBSDID("$FreeBSD$"); * a data set that will trigger the worst case is nonexistent. Heapsort's * only advantage over quicksort is that it requires little additional memory. */ +#ifdef I_AM_HEAPSORT_B +int +heapsort_b(vbase, nmemb, size, compar) + void *vbase; + size_t nmemb, size; + DECLARE_BLOCK(int, compar, const void *, const void *); +#else int heapsort(vbase, nmemb, size, compar) void *vbase; size_t nmemb, size; int (*compar)(const void *, const void *); +#endif { size_t cnt, i, j, l; char tmp, *tmp1, *tmp2; Added: head/lib/libc/stdlib/heapsort_b.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/lib/libc/stdlib/heapsort_b.c Wed Apr 2 16:07:48 2014 (r264042) @@ -0,0 +1,29 @@ +/*- + * Copyright (c) 2014 David Chisnall + * All rights reserved. + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. + * + * $FreeBSD$ + */ +#define I_AM_HEAPSORT_B +#include "heapsort.c" Modified: head/lib/libc/stdlib/merge.c ============================================================================== --- head/lib/libc/stdlib/merge.c Wed Apr 2 15:56:11 2014 (r264041) +++ head/lib/libc/stdlib/merge.c Wed Apr 2 16:07:48 2014 (r264042) @@ -56,10 +56,18 @@ __FBSDID("$FreeBSD$"); #include <stdlib.h> #include <string.h> -static void setup(u_char *, u_char *, size_t, size_t, - int (*)(const void *, const void *)); -static void insertionsort(u_char *, size_t, size_t, - int (*)(const void *, const void *)); +#ifdef I_AM_MERGESORT_B +#include "block_abi.h" +#define DECLARE_CMP DECLARE_BLOCK(int, cmp, const void *, const void *) +typedef DECLARE_BLOCK(int, cmp_t, const void *, const void *); +#define CMP(x, y) CALL_BLOCK(cmp, x, y) +#else +typedef int (*cmp_t)(const void *, const void *); +#define CMP(x, y) cmp(x, y) +#endif + +static void setup(u_char *, u_char *, size_t, size_t, cmp_t); +static void insertionsort(u_char *, size_t, size_t, cmp_t); #define ISIZE sizeof(int) #define PSIZE sizeof(u_char *) @@ -95,11 +103,15 @@ static void insertionsort(u_char *, size * Arguments are as for qsort. */ int +#ifdef I_AM_MERGESORT_B +mergesort_b(base, nmemb, size, cmp) +#else mergesort(base, nmemb, size, cmp) +#endif void *base; size_t nmemb; size_t size; - int (*cmp)(const void *, const void *); + cmp_t cmp; { size_t i; int sense; @@ -141,7 +153,7 @@ mergesort(base, nmemb, size, cmp) p2 = *EVAL(p2); l2 = list1 + (p2 - list2); while (f1 < l1 && f2 < l2) { - if ((*cmp)(f1, f2) <= 0) { + if (CMP(f1, f2) <= 0) { q = f2; b = f1, t = l1; sense = -1; @@ -151,7 +163,7 @@ mergesort(base, nmemb, size, cmp) sense = 0; } if (!big) { /* here i = 0 */ - while ((b += size) < t && cmp(q, b) >sense) + while ((b += size) < t && CMP(q, b) >sense) if (++i == 6) { big = 1; goto EXPONENTIAL; @@ -160,12 +172,12 @@ mergesort(base, nmemb, size, cmp) EXPONENTIAL: for (i = size; ; i <<= 1) if ((p = (b + i)) >= t) { if ((p = t - size) > b && - (*cmp)(q, p) <= sense) + CMP(q, p) <= sense) t = p; else b = p; break; - } else if ((*cmp)(q, p) <= sense) { + } else if (CMP(q, p) <= sense) { t = p; if (i == size) big = 0; @@ -174,14 +186,14 @@ EXPONENTIAL: for (i = size; ; i << b = p; while (t > b+size) { i = (((t - b) / size) >> 1) * size; - if ((*cmp)(q, p = b + i) <= sense) + if (CMP(q, p = b + i) <= sense) t = p; else b = p; } goto COPY; FASTCASE: while (i > size) - if ((*cmp)(q, + if (CMP(q, p = b + (i >>= 1)) <= sense) t = p; else @@ -261,8 +273,8 @@ COPY: b = t; void setup(list1, list2, n, size, cmp) size_t n, size; - int (*cmp)(const void *, const void *); u_char *list1, *list2; + cmp_t cmp; { int i, length, size2, tmp, sense; u_char *f1, *f2, *s, *l2, *last, *p2; @@ -285,12 +297,12 @@ setup(list1, list2, n, size, cmp) #ifdef NATURAL p2 = list2; f1 = list1; - sense = (cmp(f1, f1 + size) > 0); + sense = (CMP(f1, f1 + size) > 0); for (; f1 < last; sense = !sense) { length = 2; /* Find pairs with same sense. */ for (f2 = f1 + size2; f2 < last; f2 += size2) { - if ((cmp(f2, f2+ size) > 0) != sense) + if ((CMP(f2, f2+ size) > 0) != sense) break; length += 2; } @@ -303,7 +315,7 @@ setup(list1, list2, n, size, cmp) } else { /* Natural merge */ l2 = f2; for (f2 = f1 + size2; f2 < l2; f2 += size2) { - if ((cmp(f2-size, f2) > 0) != sense) { + if ((CMP(f2-size, f2) > 0) != sense) { p2 = *EVAL(p2) = f2 - list1 + list2; if (sense > 0) reverse(f1, f2-size); @@ -313,7 +325,7 @@ setup(list1, list2, n, size, cmp) if (sense > 0) reverse (f1, f2-size); f1 = f2; - if (f2 < last || cmp(f2 - size, f2) > 0) + if (f2 < last || CMP(f2 - size, f2) > 0) p2 = *EVAL(p2) = f2 - list1 + list2; else p2 = *EVAL(p2) = list2 + n*size; @@ -322,7 +334,7 @@ setup(list1, list2, n, size, cmp) #else /* pairwise merge only. */ for (f1 = list1, p2 = list2; f1 < last; f1 += size2) { p2 = *EVAL(p2) = p2 + size2; - if (cmp (f1, f1 + size) > 0) + if (CMP (f1, f1 + size) > 0) swap(f1, f1 + size); } #endif /* NATURAL */ @@ -336,7 +348,7 @@ static void insertionsort(a, n, size, cmp) u_char *a; size_t n, size; - int (*cmp)(const void *, const void *); + cmp_t cmp; { u_char *ai, *s, *t, *u, tmp; int i; @@ -344,7 +356,7 @@ insertionsort(a, n, size, cmp) for (ai = a+size; --n >= 1; ai += size) for (t = ai; t > a; t -= size) { u = t - size; - if (cmp(u, t) <= 0) + if (CMP(u, t) <= 0) break; swap(u, t); } Added: head/lib/libc/stdlib/mergesort_b.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/lib/libc/stdlib/mergesort_b.c Wed Apr 2 16:07:48 2014 (r264042) @@ -0,0 +1,29 @@ +/*- + * Copyright (c) 2014 David Chisnall + * All rights reserved. + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. + * + * $FreeBSD$ + */ +#define I_AM_MERGESORT_B +#include "merge.c" Modified: head/lib/libc/stdlib/qsort.3 ============================================================================== --- head/lib/libc/stdlib/qsort.3 Wed Apr 2 15:56:11 2014 (r264041) +++ head/lib/libc/stdlib/qsort.3 Wed Apr 2 16:07:48 2014 (r264042) @@ -36,7 +36,7 @@ .Dt QSORT 3 .Os .Sh NAME -.Nm qsort , qsort_r , heapsort , mergesort +.Nm qsort , qsort_b , qsort_r , heapsort , heapsort_b , mergesort, mergesort_b .Nd sort functions .Sh LIBRARY .Lb libc @@ -50,6 +50,13 @@ .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]" .Fc .Ft void +.Fo qsort_b +.Fa "void *base" +.Fa "size_t nmemb" +.Fa "size_t size" +.Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]" +.Fc +.Ft void .Fo qsort_r .Fa "void *base" .Fa "size_t nmemb" @@ -65,12 +72,26 @@ .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]" .Fc .Ft int +.Fo heapsort_b +.Fa "void *base" +.Fa "size_t nmemb" +.Fa "size_t size" +.Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]" +.Fc +.Ft int .Fo mergesort .Fa "void *base" .Fa "size_t nmemb" .Fa "size_t size" .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]" .Fc +.Ft int +.Fo mergesort_b +.Fa "void *base" +.Fa "size_t nmemb" +.Fa "size_t size" +.Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]" +.Fc .Sh DESCRIPTION The .Fn qsort @@ -127,6 +148,11 @@ This allows the comparison function to a data without using global variables, and thus .Fn qsort_r is suitable for use in functions which must be reentrant. +The +.Fn qsort_b +function behaves identically to +.Fn qsort , +except that it takes a block, rather than a function pointer. .Pp The algorithms implemented by .Fn qsort , @@ -138,8 +164,18 @@ are stable, that is, if two members compare as equal, their order in the sorted array is undefined. The +.Fn heapsort_b +function behaves identically to +.Fn heapsort , +except that it takes a block, rather than a function pointer. +The .Fn mergesort algorithm is stable. +The +.Fn mergesort_b +function behaves identically to +.Fn mergesort , +except that it takes a block, rather than a function pointer. .Pp The .Fn qsort @@ -324,3 +360,7 @@ The function conforms to .St -isoC . +.Sh HISTORY +The variants of these functions that take blocks as arguments first appeared in +Mac OS X. +This implementation was created by David Chisnall. Modified: head/lib/libc/stdlib/qsort_r.c ============================================================================== --- head/lib/libc/stdlib/qsort_r.c Wed Apr 2 15:56:11 2014 (r264041) +++ head/lib/libc/stdlib/qsort_r.c Wed Apr 2 16:07:48 2014 (r264042) @@ -4,5 +4,15 @@ * * $FreeBSD$ */ +#include "block_abi.h" #define I_AM_QSORT_R #include "qsort.c" + +void +qsort_b(void *base, size_t nel, size_t width, + DECLARE_BLOCK(int, compar, const void *, const void *)) +{ + qsort_r(base, nel, width, compar, + (int (*)(void *, const void *, const void *)) + GET_BLOCK_FUNCTION(compar)); +}
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201404021607.s32G7mhw051355>