svn commit: r264042 - in head: include lib/libc/gen lib/libc/include lib/libc/stdlib
David Chisnall
theraven at FreeBSD.org
Wed Apr 2 16:07:53 UTC 2014
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));
+}
More information about the svn-src-all
mailing list