From patchwork Thu Jan 18 17:53:20 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella Netto X-Patchwork-Id: 125001 Delivered-To: patch@linaro.org Received: by 10.46.64.27 with SMTP id n27csp228606lja; Thu, 18 Jan 2018 09:54:43 -0800 (PST) X-Google-Smtp-Source: ACJfBosW3xHiO8SYkkBVRC2h3tpyFEvCA2f4xAno3PxFLAGI7338gUDUi3VfjD1Q+2KBeMD7f6hB X-Received: by 2002:a17:902:43:: with SMTP id 61-v6mr174877pla.73.1516298083439; Thu, 18 Jan 2018 09:54:43 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1516298083; cv=none; d=google.com; s=arc-20160816; b=RFoaHGhJiGzlcMMy6+kUJ4s3SDvXhtyI4IGSOM+QcJ18Si0iEWiXK/dtOPE8kBSUVn 6Gy/t8cUP9gYpzq7clqYlqb8ItAGtFwxtdZK7dKzK/ykwr7gablNPlcjghDloFAgobh2 cffYI+885hpQQPtZ3e5WwS5Y+bkPHh3bIZPdqCaG6fMHk6Zedhj5xzVxwgOoNuY+qxsN JyaqxLS6mETaV/CUAkMFlK16WTuuYjTvY2XepmYcjQ5GnCLft2tGUUKW6ESTShJ8a7vq TXuj8eCTRwoMC18VCnAR1pg7rsX8dSS2sOMssJzIvcXACB6S7Sm4qhOgHwDwIcC4Cf0e 1dPQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=references:in-reply-to:message-id:date:subject:to:from:delivered-to :sender:list-help:list-post:list-archive:list-subscribe :list-unsubscribe:list-id:precedence:mailing-list:dkim-signature :domainkey-signature:arc-authentication-results; bh=KEHpGdchErgE0wKtK4Md1ZzXe8xzo5yjs9zGFERBbWQ=; b=dLdvFelqu7XB0SomUubxD1Jt5EY/1rB47gVXDmHWegNrDi3lqnoij2Mcll6j3knKYF 3j3651UYgBlAryFUkK1RYSO1J48f1TwMl0HE96nOVPi/EqOdpp3uYcvZQA3pEb8Wrrq4 nUwAZztbzDfvphS+Usvi/M+wD9TZb+0VPB4qiVTeQlbXkGz8vJlu+SYNeH5e1TuqaHoQ gQYTVnKZ/TRRv2sGOdSReVz+5KqBD6DeEdCw1YLTpWH68A4K7ubRk3ZtKi0t0+1RVJpn 9OQXmLe7lPjFu1iTUK+S291eU/7e8zyNbkLYgjY3oMjQHCGZLj5ZpkRO5Kvcb8HqQR0i iMlA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=IrNTT2q4; spf=pass (google.com: domain of libc-alpha-return-89328-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89328-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id y68si7351746pfd.104.2018.01.18.09.54.43 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 18 Jan 2018 09:54:43 -0800 (PST) Received-SPF: pass (google.com: domain of libc-alpha-return-89328-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=IrNTT2q4; spf=pass (google.com: domain of libc-alpha-return-89328-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89328-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; q=dns; s=default; b=IKR5zxC6oJnocDyUuzMEKfyA/DK17lm 9krs5JLRNzaNkZw4+ltU+2HxkSYmDPIpuVXoCmfAS5t7FvP4mHWXVkt07xwLndlw FjxpZJJOXtPt+a5Z1PSWqVWu8zM2BQOzds8tyEgM6cv08mE1XNolujJA/prrQBo8 xQJWfRD/0n6Y= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; s=default; bh=AyueZ5TKg3HkvOdtr0QqBL4IBZY=; b=IrNTT 2q42boxWUcVx6LFUa75Kt5uYTC+aB7kME/XZJoMxngn5YV2CoJQp6pe3lBKNWq3/ WaRo6V88vkrAZZNmVT32Rbfei/Kpyj6k6mkQYUnuWgvFOsI9CeYOJlKehqW0g1i9 +7n1MM3NVPjW1O9c5f5QdMoNAdHRg//pqwHx/Y= Received: (qmail 80037 invoked by alias); 18 Jan 2018 17:53:43 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 79916 invoked by uid 89); 18 Jan 2018 17:53:43 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.3 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=Engineering, thereby X-HELO: mail-qt0-f171.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=KEHpGdchErgE0wKtK4Md1ZzXe8xzo5yjs9zGFERBbWQ=; b=TUILyYrIJEMvhAyUcmr+HlFldcdFXbkMgkoOaOR6S7undGVrtH38t24ElD5jgBvVmW qiO445Om5tRoil/knayRgOSrNPkoWY5MeYdTEWH1lP8mCBNOXJCfv+Rcex3tNvJcbi/g 5Eo5LpqZhl3uyXA4oulhcvFuyg0bP4OvL8MnqqQ7K2UfN41uyBksT/ZAFfhb38jG2q1E chpP1qVl4sZqEDi1X2qOLWx1no0Xb1nucWZcR7NYUNlJ66p4xdALTWhvH3qRFYun1mEA TKPtfwBZPNKvEeEN5ClU/EruCsZ3SKjqOXnqbnLewuzsJOiXM8bkfUPoiiatgIdCuk7a TVYw== X-Gm-Message-State: AKwxyteZThyfM+w/Z4KDIgdcO3m09ZRo1FeFG6cJRGP82Z+hIt+ffOGS igN0IqIuafVUMknBPXsYCnJmvIaMp8s= X-Received: by 10.200.24.202 with SMTP id o10mr28653355qtk.27.1516298016696; Thu, 18 Jan 2018 09:53:36 -0800 (PST) From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH 5/7] stdlib: Remove use of mergesort on qsort Date: Thu, 18 Jan 2018 15:53:20 -0200 Message-Id: <1516298002-4618-6-git-send-email-adhemerval.zanella@linaro.org> In-Reply-To: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> References: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> This patch removes the mergesort optimization on qsort{_r} implementation and use the quicksort instead. The mergesort implementation has some issues: - It is as-safe only for certain types sizes (if total size is less than 1 KB with large element sizes also forcing memory allocation) which contradicts the function documentation. Although not required by the C standard, it is preferable and doable to have a O(1) space qsort implementation. - The malloc for certain element size and element number adds arbitrary latency (might even be worse if malloc is interposed). - To avoid trigger swap from memory allocation the implementation relies on system information that might be virtualized (for instance VMs with overcommit memory) which might leads to potentially use of swap even if system advertise more memory than actually has. The check also have the downside of issuing syscalls where none is expected (although only once per execution). - The mergesort is suboptimal on already sorted array (BZ#21719). The quicksort implementation is already optimized to use constant extra space (due the limit of total number of elements from maximum VM size) and thus can be used to avoid the malloc usage issues. Using bench-qsort (i7-4790K, gcc 7.2.1) shows the performance difference between mergesort (base) and quicksort (patched): Results for member size 4 Sorted nmemb | base | patched | diff 32| 1447 | 1401 | -3.18 4096| 315978 | 351333 | 11.19 32768| 2559093 | 3369386 | 31.66 524288| 46228488 | 63192972 | 36.70 MostlySorted nmemb | base | patched | diff 32| 1974 | 2391 | 21.12 4096| 922332 | 1124074 | 21.87 32768| 9268671 | 11196607 | 20.80 524288| 186856297 | 215908169 | 15.55 Unsorted nmemb | base | patched | diff 32| 1978 | 4993 | 152.43 4096| 916413 | 1113860 | 21.55 32768| 9270003 | 11251293 | 21.37 524288| 187606088 | 217252237 | 15.80 Results for member size 8 Sorted nmemb | base | patched | diff 32| 1424 | 1296 | -8.99 4096| 299105 | 359418 | 20.16 32768| 2737859 | 3535229 | 29.12 524288| 53082807 | 69847251 | 31.58 MostlySorted nmemb | base | patched | diff 32| 2129 | 2745 | 28.93 4096| 969465 | 1222082 | 26.06 32768| 9605227 | 12244800 | 27.48 524288| 193353927 | 241557971 | 24.93 Unsorted nmemb | base | patched | diff 32| 2194 | 2972 | 35.46 4096| 958610 | 1314861 | 37.16 32768| 9664246 | 12397909 | 28.29 524288| 193758429 | 241789262 | 24.79 Results for member size 32 Sorted nmemb | base | patched | diff 32| 4477 | 1305 | -70.85 4096| 1109492 | 346332 | -68.78 32768| 11075976 | 3458244 | -68.78 524288| 230773658 | 72793445 | -68.46 MostlySorted nmemb | base | patched | diff 32| 5905 | 5435 | -7.96 4096| 2568895 | 2032260 | -20.89 32768| 24936755 | 19909035 | -20.16 524288| 526442900 | 390339319 | -25.85 Unsorted nmemb | base | patched | diff 32| 6004 | 5833 | -2.85 4096| 2437943 | 2022531 | -17.04 32768| 24789971 | 19842888 | -19.96 524288| 525898556 | 388838382 | -26.06 An increase in latency, however some performance difference is due the fact mergesort uses a slight improved swap operation than quicksort (which following patch addresses). This change also renders the BZ #21719 fix unrequired (since it is to fix the sorted input performance degradation for mergesort). The manual is also updated to indicate the function is not async-cancel safe. Checked on x86_64-linux-gnu. [BZ #21719] * stdlib/Makefile (routines): Remove msort. (CFLAGS-msort.c): Remove rule. * stdlib/msort.c: Remove file. * stdlib/qsort.c (_quicksort): Rename to __qsort_r and add weak_alias to qsort_r. (qsort): New symbol. * manual/argp.texi: Remove qsort @acu* annotation. * manual/locale.texi: Likewise. * manual/search.texi: Likewise. --- manual/argp.texi | 2 +- manual/locale.texi | 3 +- manual/search.texi | 7 +- stdlib/Makefile | 9 +- stdlib/msort.c | 310 ----------------------------------------------------- stdlib/qsort.c | 15 ++- 6 files changed, 21 insertions(+), 325 deletions(-) delete mode 100644 stdlib/msort.c -- 2.7.4 diff --git a/manual/argp.texi b/manual/argp.texi index 0023441..b77ad68 100644 --- a/manual/argp.texi +++ b/manual/argp.texi @@ -735,7 +735,7 @@ for options, bad phase of the moon, etc. @c hol_set_group ok @c hol_find_entry ok @c hol_sort @mtslocale @acucorrupt -@c qsort dup @acucorrupt +@c qsort dup @c hol_entry_qcmp @mtslocale @c hol_entry_cmp @mtslocale @c group_cmp ok diff --git a/manual/locale.texi b/manual/locale.texi index 60ad2a1..9e742e4 100644 --- a/manual/locale.texi +++ b/manual/locale.texi @@ -253,7 +253,7 @@ The symbols in this section are defined in the header file @file{locale.h}. @c calculate_head_size ok @c __munmap ok @c compute_hashval ok -@c qsort dup @acucorrupt +@c qsort dup @c rangecmp ok @c malloc @ascuheap @acsmem @c strdup @ascuheap @acsmem @@ -275,7 +275,6 @@ The symbols in this section are defined in the header file @file{locale.h}. @c realloc @ascuheap @acsmem @c realloc @ascuheap @acsmem @c fclose @ascuheap @asulock @acsmem @acsfd @aculock -@c qsort @ascuheap @acsmem @c alias_compare dup @c libc_lock_unlock @aculock @c _nl_explode_name @ascuheap @acsmem diff --git a/manual/search.texi b/manual/search.texi index 57dad7a..148d451 100644 --- a/manual/search.texi +++ b/manual/search.texi @@ -159,7 +159,7 @@ To sort an array using an arbitrary comparison function, use the @deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare}) @standards{ISO, stdlib.h} -@safety{@prelim{}@mtsafe{}@assafe{}@acunsafe{@acucorrupt{}}} +@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}} The @code{qsort} function sorts the array @var{array}. The array contains @var{count} elements, each of which is of size @var{size}. @@ -199,9 +199,8 @@ Functions}): The @code{qsort} function derives its name from the fact that it was originally implemented using the ``quick sort'' algorithm. -The implementation of @code{qsort} in this library might not be an -in-place sort and might thereby use an extra amount of memory to store -the array. +The implementation of @code{qsort} in this library is an in-place sort +and uses a constant extra space (allocated on the stack). @end deftypefun @node Search/Sort Example diff --git a/stdlib/Makefile b/stdlib/Makefile index 6ef20a7..a39a176 100644 --- a/stdlib/Makefile +++ b/stdlib/Makefile @@ -34,7 +34,7 @@ headers := stdlib.h bits/stdlib.h bits/stdlib-ldbl.h bits/stdlib-float.h \ routines := \ atof atoi atol atoll \ abort \ - bsearch qsort msort \ + bsearch qsort \ getenv putenv setenv secure-getenv \ exit on_exit atexit cxa_atexit cxa_finalize old_atexit \ quick_exit at_quick_exit cxa_at_quick_exit cxa_thread_atexit_impl \ @@ -135,10 +135,9 @@ extra-test-objs += tst-putenvmod.os generated += isomac isomac.out tst-putenvmod.so -CFLAGS-bsearch.c += $(uses-callbacks) -CFLAGS-msort.c += $(uses-callbacks) -CFLAGS-qsort.c += $(uses-callbacks) -CFLAGS-system.c += -fexceptions +CFLAGS-bsearch.c = $(uses-callbacks) +CFLAGS-qsort.c = $(uses-callbacks) +CFLAGS-system.c = -fexceptions CFLAGS-system.os = -fomit-frame-pointer CFLAGS-fmtmsg.c += -fexceptions diff --git a/stdlib/msort.c b/stdlib/msort.c deleted file mode 100644 index 266c253..0000000 --- a/stdlib/msort.c +++ /dev/null @@ -1,310 +0,0 @@ -/* An alternative to qsort, with an identical interface. - This file is part of the GNU C Library. - Copyright (C) 1992-2018 Free Software Foundation, Inc. - Written by Mike Haertel, September 1988. - - The GNU C Library is free software; you can redistribute it and/or - modify it under the terms of the GNU Lesser General Public - License as published by the Free Software Foundation; either - version 2.1 of the License, or (at your option) any later version. - - The GNU C Library is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - Lesser General Public License for more details. - - You should have received a copy of the GNU Lesser General Public - License along with the GNU C Library; if not, see - . */ - -#include -#include -#include -#include -#include -#include -#include -#include - -struct msort_param -{ - size_t s; - size_t var; - __compar_d_fn_t cmp; - void *arg; - char *t; -}; -static void msort_with_tmp (const struct msort_param *p, void *b, size_t n); - -static void -msort_with_tmp (const struct msort_param *p, void *b, size_t n) -{ - char *b1, *b2; - size_t n1, n2; - - if (n <= 1) - return; - - n1 = n / 2; - n2 = n - n1; - b1 = b; - b2 = (char *) b + (n1 * p->s); - - msort_with_tmp (p, b1, n1); - msort_with_tmp (p, b2, n2); - - char *tmp = p->t; - const size_t s = p->s; - __compar_d_fn_t cmp = p->cmp; - void *arg = p->arg; - switch (p->var) - { - case 0: - while (n1 > 0 && n2 > 0) - { - if ((*cmp) (b1, b2, arg) <= 0) - { - *(uint32_t *) tmp = *(uint32_t *) b1; - b1 += sizeof (uint32_t); - --n1; - } - else - { - *(uint32_t *) tmp = *(uint32_t *) b2; - b2 += sizeof (uint32_t); - --n2; - } - tmp += sizeof (uint32_t); - } - break; - case 1: - while (n1 > 0 && n2 > 0) - { - if ((*cmp) (b1, b2, arg) <= 0) - { - *(uint64_t *) tmp = *(uint64_t *) b1; - b1 += sizeof (uint64_t); - --n1; - } - else - { - *(uint64_t *) tmp = *(uint64_t *) b2; - b2 += sizeof (uint64_t); - --n2; - } - tmp += sizeof (uint64_t); - } - break; - case 2: - while (n1 > 0 && n2 > 0) - { - unsigned long *tmpl = (unsigned long *) tmp; - unsigned long *bl; - - tmp += s; - if ((*cmp) (b1, b2, arg) <= 0) - { - bl = (unsigned long *) b1; - b1 += s; - --n1; - } - else - { - bl = (unsigned long *) b2; - b2 += s; - --n2; - } - while (tmpl < (unsigned long *) tmp) - *tmpl++ = *bl++; - } - break; - case 3: - while (n1 > 0 && n2 > 0) - { - if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0) - { - *(void **) tmp = *(void **) b1; - b1 += sizeof (void *); - --n1; - } - else - { - *(void **) tmp = *(void **) b2; - b2 += sizeof (void *); - --n2; - } - tmp += sizeof (void *); - } - break; - default: - while (n1 > 0 && n2 > 0) - { - if ((*cmp) (b1, b2, arg) <= 0) - { - tmp = (char *) __mempcpy (tmp, b1, s); - b1 += s; - --n1; - } - else - { - tmp = (char *) __mempcpy (tmp, b2, s); - b2 += s; - --n2; - } - } - break; - } - - if (n1 > 0) - memcpy (tmp, b1, n1 * s); - memcpy (b, p->t, (n - n2) * s); -} - - -void -__qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg) -{ - size_t size = n * s; - char *tmp = NULL; - struct msort_param p; - - /* For large object sizes use indirect sorting. */ - if (s > 32) - size = 2 * n * sizeof (void *) + s; - - if (size < 1024) - /* The temporary array is small, so put it on the stack. */ - p.t = __alloca (size); - else - { - /* We should avoid allocating too much memory since this might - have to be backed up by swap space. */ - static long int phys_pages; - static int pagesize; - - if (pagesize == 0) - { - phys_pages = __sysconf (_SC_PHYS_PAGES); - - if (phys_pages == -1) - /* Error while determining the memory size. So let's - assume there is enough memory. Otherwise the - implementer should provide a complete implementation of - the `sysconf' function. */ - phys_pages = (long int) (~0ul >> 1); - - /* The following determines that we will never use more than - a quarter of the physical memory. */ - phys_pages /= 4; - - /* Make sure phys_pages is written to memory. */ - atomic_write_barrier (); - - pagesize = __sysconf (_SC_PAGESIZE); - } - - /* Just a comment here. We cannot compute - phys_pages * pagesize - and compare the needed amount of memory against this value. - The problem is that some systems might have more physical - memory then can be represented with a `size_t' value (when - measured in bytes. */ - - /* If the memory requirements are too high don't allocate memory. */ - if (size / pagesize > (size_t) phys_pages) - { - _quicksort (b, n, s, cmp, arg); - return; - } - - /* It's somewhat large, so malloc it. */ - int save = errno; - tmp = malloc (size); - __set_errno (save); - if (tmp == NULL) - { - /* Couldn't get space, so use the slower algorithm - that doesn't need a temporary array. */ - _quicksort (b, n, s, cmp, arg); - return; - } - p.t = tmp; - } - - p.s = s; - p.var = 4; - p.cmp = cmp; - p.arg = arg; - - if (s > 32) - { - /* Indirect sorting. */ - char *ip = (char *) b; - void **tp = (void **) (p.t + n * sizeof (void *)); - void **t = tp; - void *tmp_storage = (void *) (tp + n); - - while ((void *) t < tmp_storage) - { - *t++ = ip; - ip += s; - } - p.s = sizeof (void *); - p.var = 3; - msort_with_tmp (&p, p.t + n * sizeof (void *), n); - - /* tp[0] .. tp[n - 1] is now sorted, copy around entries of - the original array. Knuth vol. 3 (2nd ed.) exercise 5.2-10. */ - char *kp; - size_t i; - for (i = 0, ip = (char *) b; i < n; i++, ip += s) - if ((kp = tp[i]) != ip) - { - size_t j = i; - char *jp = ip; - memcpy (tmp_storage, ip, s); - - do - { - size_t k = (kp - (char *) b) / s; - tp[j] = jp; - memcpy (jp, kp, s); - j = k; - jp = kp; - kp = tp[k]; - } - while (kp != ip); - - tp[j] = jp; - memcpy (jp, tmp_storage, s); - } - } - else - { - if ((s & (sizeof (uint32_t) - 1)) == 0 - && ((char *) b - (char *) 0) % __alignof__ (uint32_t) == 0) - { - if (s == sizeof (uint32_t)) - p.var = 0; - else if (s == sizeof (uint64_t) - && ((char *) b - (char *) 0) % __alignof__ (uint64_t) == 0) - p.var = 1; - else if ((s & (sizeof (unsigned long) - 1)) == 0 - && ((char *) b - (char *) 0) - % __alignof__ (unsigned long) == 0) - p.var = 2; - } - msort_with_tmp (&p, b, n); - } - free (tmp); -} -libc_hidden_def (__qsort_r) -weak_alias (__qsort_r, qsort_r) - - -void -qsort (void *b, size_t n, size_t s, __compar_fn_t cmp) -{ - return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL); -} -libc_hidden_def (qsort) diff --git a/stdlib/qsort.c b/stdlib/qsort.c index 264a06b..b3a5102 100644 --- a/stdlib/qsort.c +++ b/stdlib/qsort.c @@ -20,7 +20,6 @@ Engineering a sort function; Jon Bentley and M. Douglas McIlroy; Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */ -#include #include #include #include @@ -86,8 +85,8 @@ typedef struct stack size is needed (actually O(1) in this case)! */ void -_quicksort (void *const pbase, size_t total_elems, size_t size, - __compar_d_fn_t cmp, void *arg) +__qsort_r (void *const pbase, size_t total_elems, size_t size, + __compar_d_fn_t cmp, void *arg) { char *base_ptr = (char *) pbase; @@ -247,3 +246,13 @@ _quicksort (void *const pbase, size_t total_elems, size_t size, } } } + +libc_hidden_def (__qsort_r) +weak_alias (__qsort_r, qsort_r) + +void +qsort (void *b, size_t n, size_t s, __compar_fn_t cmp) +{ + return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL); +} +libc_hidden_def (qsort)