Skip site navigation (1)Skip section navigation (2)
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>