diff options
author | sjg <sjg@FreeBSD.org> | 2014-04-27 08:13:43 +0000 |
---|---|---|
committer | sjg <sjg@FreeBSD.org> | 2014-04-27 08:13:43 +0000 |
commit | 0c7e03a54c8e7ddc9c3fe710f83d9ca53173692e (patch) | |
tree | b92e741b68057a24e381faa9809f32030d65574c /lib/libc/stdlib | |
parent | c244fcbcaa61dc2a15995e7dbdf3ae8107bc2111 (diff) | |
parent | 69c3e6933b6946c49fe99b19986f018d71621980 (diff) | |
download | FreeBSD-src-0c7e03a54c8e7ddc9c3fe710f83d9ca53173692e.zip FreeBSD-src-0c7e03a54c8e7ddc9c3fe710f83d9ca53173692e.tar.gz |
Merge head
Diffstat (limited to 'lib/libc/stdlib')
-rw-r--r-- | lib/libc/stdlib/Makefile.inc | 11 | ||||
-rw-r--r-- | lib/libc/stdlib/Symbol.map | 7 | ||||
-rw-r--r-- | lib/libc/stdlib/atexit.3 | 14 | ||||
-rw-r--r-- | lib/libc/stdlib/atexit.c | 53 | ||||
-rw-r--r-- | lib/libc/stdlib/bsearch.c | 19 | ||||
-rw-r--r-- | lib/libc/stdlib/bsearch_b.c | 29 | ||||
-rw-r--r-- | lib/libc/stdlib/getopt_long.3 | 4 | ||||
-rw-r--r-- | lib/libc/stdlib/getsubopt.c | 4 | ||||
-rw-r--r-- | lib/libc/stdlib/heapsort.c | 26 | ||||
-rw-r--r-- | lib/libc/stdlib/heapsort_b.c | 29 | ||||
-rw-r--r-- | lib/libc/stdlib/jemalloc/Makefile.inc | 18 | ||||
-rw-r--r-- | lib/libc/stdlib/jemalloc/Symbol.map | 12 | ||||
-rw-r--r-- | lib/libc/stdlib/merge.c | 50 | ||||
-rw-r--r-- | lib/libc/stdlib/mergesort_b.c | 29 | ||||
-rw-r--r-- | lib/libc/stdlib/qsort.3 | 42 | ||||
-rw-r--r-- | lib/libc/stdlib/qsort_r.c | 11 | ||||
-rw-r--r-- | lib/libc/stdlib/realpath.c | 26 |
17 files changed, 316 insertions, 68 deletions
diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc index 75204f5..68dda94 100644 --- a/lib/libc/stdlib/Makefile.inc +++ b/lib/libc/stdlib/Makefile.inc @@ -2,21 +2,22 @@ # $FreeBSD$ # machine-independent stdlib sources -.PATH: ${.CURDIR}/${LIBC_ARCH}/stdlib ${.CURDIR}/stdlib +.PATH: ${LIBC_SRCTOP}/${LIBC_ARCH}/stdlib ${LIBC_SRCTOP}/stdlib 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 -SYM_MAPS+= ${.CURDIR}/stdlib/Symbol.map +SYM_MAPS+= ${LIBC_SRCTOP}/stdlib/Symbol.map # machine-dependent stdlib sources -.sinclude "${.CURDIR}/${LIBC_ARCH}/stdlib/Makefile.inc" +.sinclude "${LIBC_SRCTOP}/${LIBC_ARCH}/stdlib/Makefile.inc" MAN+= a64l.3 abort.3 abs.3 alloca.3 atexit.3 atof.3 \ atoi.3 atol.3 at_quick_exit.3 bsearch.3 \ diff --git a/lib/libc/stdlib/Symbol.map b/lib/libc/stdlib/Symbol.map index 6a1798f..d28a8e9 100644 --- a/lib/libc/stdlib/Symbol.map +++ b/lib/libc/stdlib/Symbol.map @@ -104,6 +104,13 @@ FBSD_1.3 { strtouq_l; }; +FBSD_1.4 { + atexit_b; + heapsort_b; + mergesort_b; + qsort_b; +}; + FBSDprivate_1.0 { __system; _system; diff --git a/lib/libc/stdlib/atexit.3 b/lib/libc/stdlib/atexit.3 index d6dab56..68f4e8f 100644 --- a/lib/libc/stdlib/atexit.3 +++ b/lib/libc/stdlib/atexit.3 @@ -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 calling .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 sufficient memory can be allocated. .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 diff --git a/lib/libc/stdlib/atexit.c b/lib/libc/stdlib/atexit.c index 18c31c3..0a5048a 100644 --- a/lib/libc/stdlib/atexit.c +++ b/lib/libc/stdlib/atexit.c @@ -37,6 +37,7 @@ static char sccsid[] = "@(#)atexit.c 8.2 (Berkeley) 7/3/94"; __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 @@ -72,6 +80,7 @@ struct atexit { }; static struct atexit *__atexit; /* points to head of LIFO stack */ +typedef DECLARE_BLOCK(void, atexit_block, void); /* * Register the function described by 'fptr' to be called at application @@ -125,7 +134,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(atexit_block func) +{ + 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,13 +178,15 @@ __cxa_atexit(void (*func)(void *), void *arg, void *dso) fn.fn_arg = arg; fn.fn_dso = dso; - error = atexit_register(&fn); + error = atexit_register(&fn); return (error); } #pragma weak __pthread_cxa_finalize void __pthread_cxa_finalize(const struct dl_phdr_info *); +static int global_exit; + /* * Call all handlers registered with __cxa_atexit for the shared * object owning 'dso'. Note: if 'dso' is NULL, then all remaining @@ -164,10 +200,12 @@ __cxa_finalize(void *dso) struct atexit_fn fn; int n, has_phdr; - if (dso != NULL) + if (dso != NULL) { has_phdr = _rtld_addr_phdr(dso, &phdr_info); - else + } else { has_phdr = 0; + global_exit = 1; + } _MUTEX_LOCK(&atexit_mutex); for (p = __atexit; p; p = p->next) { @@ -177,8 +215,9 @@ __cxa_finalize(void *dso) fn = p->fns[n]; if (dso != NULL && dso != fn.fn_dso) { /* wrong DSO ? */ - if (!has_phdr || !__elf_phdr_match_addr( - &phdr_info, fn.fn_ptr.cxa_func)) + if (!has_phdr || global_exit || + !__elf_phdr_match_addr(&phdr_info, + fn.fn_ptr.cxa_func)) continue; } /* @@ -200,6 +239,6 @@ __cxa_finalize(void *dso) if (dso == NULL) _MUTEX_DESTROY(&atexit_mutex); - if (has_phdr && &__pthread_cxa_finalize != NULL) + if (has_phdr && !global_exit && &__pthread_cxa_finalize != NULL) __pthread_cxa_finalize(&phdr_info); } diff --git a/lib/libc/stdlib/bsearch.c b/lib/libc/stdlib/bsearch.c index 4bcaaf3..4a1dd52 100644 --- a/lib/libc/stdlib/bsearch.c +++ b/lib/libc/stdlib/bsearch.c @@ -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 */ diff --git a/lib/libc/stdlib/bsearch_b.c b/lib/libc/stdlib/bsearch_b.c new file mode 100644 index 0000000..393feba --- /dev/null +++ b/lib/libc/stdlib/bsearch_b.c @@ -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" diff --git a/lib/libc/stdlib/getopt_long.3 b/lib/libc/stdlib/getopt_long.3 index 06eadca..6904716 100644 --- a/lib/libc/stdlib/getopt_long.3 +++ b/lib/libc/stdlib/getopt_long.3 @@ -130,11 +130,11 @@ field should be one of: .Pp .Bl -tag -width ".Dv optional_argument" -offset indent -compact .It Dv no_argument -no argument to the option is expect +no argument to the option is expected .It Dv required_argument an argument to the option is required .It Dv optional_argument -an argument to the option may be presented. +an argument to the option may be presented .El .Pp If diff --git a/lib/libc/stdlib/getsubopt.c b/lib/libc/stdlib/getsubopt.c index efff9da..d2db991 100644 --- a/lib/libc/stdlib/getsubopt.c +++ b/lib/libc/stdlib/getsubopt.c @@ -45,9 +45,7 @@ __FBSDID("$FreeBSD$"); char *suboptarg; int -getsubopt(optionp, tokens, valuep) - char **optionp, **valuep; - char * const *tokens; +getsubopt(char **optionp, char * const *tokens, char **valuep) { int cnt; char *p; diff --git a/lib/libc/stdlib/heapsort.c b/lib/libc/stdlib/heapsort.c index 4bad8a7..673a6a1 100644 --- a/lib/libc/stdlib/heapsort.c +++ b/lib/libc/stdlib/heapsort.c @@ -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,14 @@ __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) +typedef DECLARE_BLOCK(int, heapsort_block, const void *, const void *); +#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 +87,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 +118,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 +130,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 +145,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; + heapsort_block compar; +#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; diff --git a/lib/libc/stdlib/heapsort_b.c b/lib/libc/stdlib/heapsort_b.c new file mode 100644 index 0000000..b1814bc --- /dev/null +++ b/lib/libc/stdlib/heapsort_b.c @@ -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" diff --git a/lib/libc/stdlib/jemalloc/Makefile.inc b/lib/libc/stdlib/jemalloc/Makefile.inc index 9718676..4f5fa58 100644 --- a/lib/libc/stdlib/jemalloc/Makefile.inc +++ b/lib/libc/stdlib/jemalloc/Makefile.inc @@ -1,26 +1,26 @@ # $FreeBSD$ -.PATH: ${.CURDIR}/stdlib/jemalloc +.PATH: ${LIBC_SRCTOP}/stdlib/jemalloc JEMALLOCSRCS:= jemalloc.c arena.c atomic.c base.c bitmap.c chunk.c \ chunk_dss.c chunk_mmap.c ckh.c ctl.c extent.c hash.c huge.c mb.c \ - mutex.c prof.c quarantine.c rtree.c stats.c tcache.c util.c tsd.c + mutex.c prof.c quarantine.c rtree.c stats.c tcache.c tsd.c util.c -SYM_MAPS+=${.CURDIR}/stdlib/jemalloc/Symbol.map +SYM_MAPS+=${LIBC_SRCTOP}/stdlib/jemalloc/Symbol.map -CFLAGS+=-I${.CURDIR}/../../contrib/jemalloc/include +CFLAGS+=-I${LIBC_SRCTOP}/../../contrib/jemalloc/include .for src in ${JEMALLOCSRCS} MISRCS+=jemalloc_${src} CLEANFILES+=jemalloc_${src} jemalloc_${src}: - ln -sf ${.CURDIR}/../../contrib/jemalloc/src/${src} ${.TARGET} + ln -sf ${LIBC_SRCTOP}/../../contrib/jemalloc/src/${src} ${.TARGET} .endfor MAN+=jemalloc.3 CLEANFILES+=jemalloc.3 jemalloc.3: - ln -sf ${.CURDIR}/../../contrib/jemalloc/doc/jemalloc.3 ${.TARGET} + ln -sf ${LIBC_SRCTOP}/../../contrib/jemalloc/doc/jemalloc.3 ${.TARGET} MLINKS+= \ jemalloc.3 malloc.3 \ @@ -34,6 +34,12 @@ MLINKS+= \ jemalloc.3 mallctl.3 \ jemalloc.3 mallctlnametomib.3 \ jemalloc.3 mallctlbymib.3 \ + jemalloc.3 mallocx.3 \ + jemalloc.3 rallocx.3 \ + jemalloc.3 xallocx.3 \ + jemalloc.3 sallocx.3 \ + jemalloc.3 dallocx.3 \ + jemalloc.3 nallocx.3 \ jemalloc.3 allocm.3 \ jemalloc.3 rallocm.3 \ jemalloc.3 sallocm.3 \ diff --git a/lib/libc/stdlib/jemalloc/Symbol.map b/lib/libc/stdlib/jemalloc/Symbol.map index 617194f..35a5dad 100644 --- a/lib/libc/stdlib/jemalloc/Symbol.map +++ b/lib/libc/stdlib/jemalloc/Symbol.map @@ -21,6 +21,12 @@ FBSD_1.3 { mallctl; mallctlnametomib; mallctlbymib; + mallocx; + rallocx; + xallocx; + sallocx; + dallocx; + nallocx; allocm; rallocm; sallocm; @@ -32,6 +38,12 @@ FBSD_1.3 { __free; __posix_memalign; __malloc_usable_size; + __mallocx; + __rallocx; + __xallocx; + __sallocx; + __dallocx; + __nallocx; __allocm; __rallocm; __sallocm; diff --git a/lib/libc/stdlib/merge.c b/lib/libc/stdlib/merge.c index 01a9028..6b368c3 100644 --- a/lib/libc/stdlib/merge.c +++ b/lib/libc/stdlib/merge.c @@ -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_t, size_t, * 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 <<= 1) 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); } diff --git a/lib/libc/stdlib/mergesort_b.c b/lib/libc/stdlib/mergesort_b.c new file mode 100644 index 0000000..acf5987 --- /dev/null +++ b/lib/libc/stdlib/mergesort_b.c @@ -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" diff --git a/lib/libc/stdlib/qsort.3 b/lib/libc/stdlib/qsort.3 index ac01912..a0610d9 100644 --- a/lib/libc/stdlib/qsort.3 +++ b/lib/libc/stdlib/qsort.3 @@ -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 access additional 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. diff --git a/lib/libc/stdlib/qsort_r.c b/lib/libc/stdlib/qsort_r.c index d868736..f489d31 100644 --- a/lib/libc/stdlib/qsort_r.c +++ b/lib/libc/stdlib/qsort_r.c @@ -4,5 +4,16 @@ * * $FreeBSD$ */ +#include "block_abi.h" #define I_AM_QSORT_R #include "qsort.c" + +typedef DECLARE_BLOCK(int, qsort_block, const void *, const void *); + +void +qsort_b(void *base, size_t nel, size_t width, qsort_block compar) +{ + qsort_r(base, nel, width, compar, + (int (*)(void *, const void *, const void *)) + GET_BLOCK_FUNCTION(compar)); +} diff --git a/lib/libc/stdlib/realpath.c b/lib/libc/stdlib/realpath.c index a2a9329..c4bd953 100644 --- a/lib/libc/stdlib/realpath.c +++ b/lib/libc/stdlib/realpath.c @@ -132,26 +132,7 @@ realpath(const char * __restrict path, char * __restrict resolved) resolved[resolved_len] = '\0'; } if (next_token[0] == '\0') { - /* - * Handle consequential slashes. The path - * before slash shall point to a directory. - * - * Only the trailing slashes are not covered - * by other checks in the loop, but we verify - * the prefix for any (rare) "//" or "/\0" - * occurrence to not implement lookahead. - */ - if (lstat(resolved, &sb) != 0) { - if (m) - free(resolved); - return (NULL); - } - if (!S_ISDIR(sb.st_mode)) { - if (m) - free(resolved); - errno = ENOTDIR; - return (NULL); - } + /* Handle consequential slashes. */ continue; } else if (strcmp(next_token, ".") == 0) @@ -236,6 +217,11 @@ realpath(const char * __restrict path, char * __restrict resolved) } } left_len = strlcpy(left, symlink, sizeof(left)); + } else if (!S_ISDIR(sb.st_mode) && p != NULL) { + if (m) + free(resolved); + errno = ENOTDIR; + return (NULL); } } |