From unknown Sat Sep 13 17:05:26 2025 X-Loop: help-debbugs@gnu.org Subject: bug#18360: Modularize recent qsort_r additions Resent-From: Paul Eggert Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 29 Aug 2014 20:59:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 18360 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: 18360@debbugs.gnu.org X-Debbugs-Original-To: Emacs bug reports Received: via spool by submit@debbugs.gnu.org id=B.140934591629476 (code B ref -1); Fri, 29 Aug 2014 20:59:01 +0000 Received: (at submit) by debbugs.gnu.org; 29 Aug 2014 20:58:36 +0000 Received: from localhost ([127.0.0.1]:53820 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNTFh-0007fJ-Tg for submit@debbugs.gnu.org; Fri, 29 Aug 2014 16:58:35 -0400 Received: from eggs.gnu.org ([208.118.235.92]:51276) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNTFe-0007f5-3s for submit@debbugs.gnu.org; Fri, 29 Aug 2014 16:58:32 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XNTFU-0001Wv-Fo for submit@debbugs.gnu.org; Fri, 29 Aug 2014 16:58:24 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:34083) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XNTFU-0001Wb-Ce for submit@debbugs.gnu.org; Fri, 29 Aug 2014 16:58:20 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:52985) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XNTFQ-0002DG-07 for bug-gnu-emacs@gnu.org; Fri, 29 Aug 2014 16:58:20 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XNTFL-0001QG-Hw for bug-gnu-emacs@gnu.org; Fri, 29 Aug 2014 16:58:15 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:58422) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XNTFL-0001QC-0z for bug-gnu-emacs@gnu.org; Fri, 29 Aug 2014 16:58:11 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 56C52A6000B for ; Fri, 29 Aug 2014 13:58:10 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id VWRhHi1Iy5MT for ; Fri, 29 Aug 2014 13:58:06 -0700 (PDT) Received: from penguin.cs.ucla.edu (Penguin.CS.UCLA.EDU [131.179.64.200]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 37B30A60001 for ; Fri, 29 Aug 2014 13:58:06 -0700 (PDT) Message-ID: <5400E959.3000805@cs.ucla.edu> Date: Fri, 29 Aug 2014 13:58:01 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.7.0 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------010809080206030708060802" X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -4.0 (----) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -4.0 (----) This is a multi-part message in MIME format. --------------010809080206030708060802 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Tags: patch The recent changes to have Emacs use qsort_r look good except for the forest of #ifdefs in Emacs proper. Attached is a proposed patch to migrate that stuff into Gnulib. As usual most of this patch is automatically generated; fns.c contains the crucial hand-generated stuff. I have not tested this on Microsoft Windows and so am posting it here first to give Eli a heads-up. --------------010809080206030708060802 Content-Type: text/x-patch; name="qsort_r.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="qsort_r.patch" =3D=3D=3D modified file 'ChangeLog' --- ChangeLog 2014-08-29 07:29:47 +0000 +++ ChangeLog 2014-08-29 20:46:33 +0000 @@ -1,3 +1,13 @@ +2014-08-29 Paul Eggert + + Modularize qsort_r in Gnulib, to simplify Emacs proper. + * configure.ac (qsort_r): Remove check; gnulib does this now. + * lib/qsort.c, lib/qsort_r.c, m4/qsort_r.m4: New files. + Merge from gnulib, incorporating: + 2014-08-29 qsort_r: new module, for GNU-style qsort_r + * lib/gnulib.mk, m4/gnulib-comp.m4: Regenerate. + * lib/stdlib.in.h, m4/stdlib_h.m4: Update from gnulib. + 2014-08-29 Dmitry Antipov =20 * configure.ac (AC_CHECK_FUNCS): Check for qsort_r. =3D=3D=3D modified file 'admin/ChangeLog' --- admin/ChangeLog 2014-08-29 18:10:15 +0000 +++ admin/ChangeLog 2014-08-29 20:46:33 +0000 @@ -1,3 +1,8 @@ +2014-08-29 Paul Eggert + + Modularize qsort_r in Gnulib, to simplify Emacs proper. + * merge-gnulib (GNULIB_MODULES): Add qsort_r. + 2014-08-29 Michael Albinus =20 * authors.el (authors): Use LOCALE argument of `string-collate-lessp'. =3D=3D=3D modified file 'admin/merge-gnulib' --- admin/merge-gnulib 2014-07-14 19:23:18 +0000 +++ admin/merge-gnulib 2014-08-29 20:46:33 +0000 @@ -34,7 +34,7 @@ getloadavg getopt-gnu gettime gettimeofday intprops largefile lstat manywarnings memrchr mkostemp mktime - pipe2 pselect pthread_sigmask putenv qacl readlink readlinkat + pipe2 pselect pthread_sigmask putenv qacl qsort_r readlink readlinkat sig2str socklen stat-time stdalign stdio strftime strtoimax strtoumax symlink sys_stat sys_time time timer-time timespec-add timespec-sub =3D=3D=3D modified file 'configure.ac' --- configure.ac 2014-08-29 07:29:47 +0000 +++ configure.ac 2014-08-29 20:46:33 +0000 @@ -3573,7 +3573,7 @@ getrlimit setrlimit shutdown getaddrinfo \ pthread_sigmask strsignal setitimer \ sendto recvfrom getsockname getpeername getifaddrs freeifaddrs \ -gai_strerror sync qsort_r \ +gai_strerror sync \ getpwent endpwent getgrent endgrent \ cfmakeraw cfsetspeed copysign __executable_start log2) LIBS=3D$OLD_LIBS =3D=3D=3D modified file 'lib/gnulib.mk' --- lib/gnulib.mk 2014-08-04 18:44:49 +0000 +++ lib/gnulib.mk 2014-08-29 20:46:33 +0000 @@ -21,7 +21,7 @@ # the same distribution terms as the rest of that program. # # Generated by gnulib-tool. -# Reproduce by: gnulib-tool --import --dir=3D. --lib=3Dlibgnu --source-b= ase=3Dlib --m4-base=3Dm4 --doc-base=3Ddoc --tests-base=3Dtests --aux-dir=3D= build-aux --avoid=3Dclose --avoid=3Ddup --avoid=3Dfchdir --avoid=3Dfstat = --avoid=3Dmalloc-posix --avoid=3Dmsvc-inval --avoid=3Dmsvc-nothrow --avoi= d=3Dopen --avoid=3Dopenat-die --avoid=3Dopendir --avoid=3Draise --avoid=3D= save-cwd --avoid=3Dselect --avoid=3Dsigprocmask --avoid=3Dstdarg --avoid=3D= stdbool --avoid=3Dthreadlib --makefile-name=3Dgnulib.mk --conditional-dep= endencies --no-libtool --macro-prefix=3Dgl --no-vc-files alloca-opt binar= y-io byteswap c-ctype c-strcase careadlinkat close-stream count-one-bits = count-trailing-zeros crypto/md5 crypto/sha1 crypto/sha256 crypto/sha512 d= toastr dtotimespec dup2 environ execinfo faccessat fcntl fcntl-h fdatasyn= c fdopendir filemode fstatat fsync getloadavg getopt-gnu gettime gettimeo= fday intprops largefile lstat manywarnings memrchr mkostemp mktime pipe2 = pselect pthread_sigmask putenv qacl readlink readlinkat sig2str socklen s= tat-time stdalign stdio strftime strtoimax strtoumax symlink sys_stat sys= _time time timer-time timespec-add timespec-sub unsetenv update-copyright= utimens warnings +# Reproduce by: gnulib-tool --import --dir=3D. --lib=3Dlibgnu --source-b= ase=3Dlib --m4-base=3Dm4 --doc-base=3Ddoc --tests-base=3Dtests --aux-dir=3D= build-aux --avoid=3Dclose --avoid=3Ddup --avoid=3Dfchdir --avoid=3Dfstat = --avoid=3Dmalloc-posix --avoid=3Dmsvc-inval --avoid=3Dmsvc-nothrow --avoi= d=3Dopen --avoid=3Dopenat-die --avoid=3Dopendir --avoid=3Draise --avoid=3D= save-cwd --avoid=3Dselect --avoid=3Dsigprocmask --avoid=3Dstdarg --avoid=3D= stdbool --avoid=3Dthreadlib --makefile-name=3Dgnulib.mk --conditional-dep= endencies --no-libtool --macro-prefix=3Dgl --no-vc-files alloca-opt binar= y-io byteswap c-ctype c-strcase careadlinkat close-stream count-one-bits = count-trailing-zeros crypto/md5 crypto/sha1 crypto/sha256 crypto/sha512 d= toastr dtotimespec dup2 environ execinfo faccessat fcntl fcntl-h fdatasyn= c fdopendir filemode fstatat fsync getloadavg getopt-gnu gettime gettimeo= fday intprops largefile lstat manywarnings memrchr mkostemp mktime pipe2 = pselect pthread_sigmask putenv qacl qsort_r readlink readlinkat sig2str s= ocklen stat-time stdalign stdio strftime strtoimax strtoumax symlink sys_= stat sys_time time timer-time timespec-add timespec-sub unsetenv update-c= opyright utimens warnings =20 =20 MOSTLYCLEANFILES +=3D core *.stackdump @@ -688,6 +688,15 @@ =20 ## end gnulib module qacl =20 +## begin gnulib module qsort_r + + +EXTRA_DIST +=3D qsort.c qsort_r.c + +EXTRA_libgnu_a_SOURCES +=3D qsort.c qsort_r.c + +## end gnulib module qsort_r + ## begin gnulib module readlink =20 =20 @@ -1141,6 +1150,7 @@ -e 's/@''GNULIB_PTSNAME''@/$(GNULIB_PTSNAME)/g' \ -e 's/@''GNULIB_PTSNAME_R''@/$(GNULIB_PTSNAME_R)/g' \ -e 's/@''GNULIB_PUTENV''@/$(GNULIB_PUTENV)/g' \ + -e 's/@''GNULIB_QSORT_R''@/$(GNULIB_QSORT_R)/g' \ -e 's/@''GNULIB_RANDOM''@/$(GNULIB_RANDOM)/g' \ -e 's/@''GNULIB_RANDOM_R''@/$(GNULIB_RANDOM_R)/g' \ -e 's/@''GNULIB_REALLOC_POSIX''@/$(GNULIB_REALLOC_POSIX)/g' \ @@ -1192,6 +1202,7 @@ -e 's|@''REPLACE_PTSNAME''@|$(REPLACE_PTSNAME)|g' \ -e 's|@''REPLACE_PTSNAME_R''@|$(REPLACE_PTSNAME_R)|g' \ -e 's|@''REPLACE_PUTENV''@|$(REPLACE_PUTENV)|g' \ + -e 's|@''REPLACE_QSORT_R''@|$(REPLACE_QSORT_R)|g' \ -e 's|@''REPLACE_RANDOM_R''@|$(REPLACE_RANDOM_R)|g' \ -e 's|@''REPLACE_REALLOC''@|$(REPLACE_REALLOC)|g' \ -e 's|@''REPLACE_REALPATH''@|$(REPLACE_REALPATH)|g' \ =3D=3D=3D added file 'lib/qsort.c' --- lib/qsort.c 1970-01-01 00:00:00 +0000 +++ lib/qsort.c 2014-08-29 20:46:33 +0000 @@ -0,0 +1,254 @@ +/* Copyright (C) 1991-2014 Free Software Foundation, Inc. + This file is part of the GNU C Library. + Written by Douglas C. Schmidt (schmidt@ics.uci.edu). + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public + License as published by the Free Software Foundation; either + version 3 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 + General Public License for more details. + + You should have received a copy of the GNU General Public + License along with the GNU C Library; if not, see + . */ + +/* If you consider tuning this algorithm, you should consult first: + Engineering a sort function; Jon Bentley and M. Douglas McIlroy; + Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. *= / + +#include +#include +#include + +#ifndef _LIBC +# define _quicksort qsort_r +# define __compar_d_fn_t compar_d_fn_t +typedef int (*compar_d_fn_t) (const void *, const void *, void *); +#endif + +/* Byte-wise swap two items of size SIZE. */ +#define SWAP(a, b, size) \ + do \ + { \ + size_t __size =3D (size); \ + char *__a =3D (a), *__b =3D (b); \ + do \ + { \ + char __tmp =3D *__a; \ + *__a++ =3D *__b; \ + *__b++ =3D __tmp; \ + } while (--__size > 0); \ + } while (0) + +/* Discontinue quicksort algorithm when partition gets below this size. + This particular magic number was chosen to work best on a Sun 4/260. = */ +#define MAX_THRESH 4 + +/* Stack node declarations used to store unfulfilled partition obligatio= ns. */ +typedef struct + { + char *lo; + char *hi; + } stack_node; + +/* The next 4 #defines implement a very fast in-line stack abstraction. = */ +/* The stack needs log (total_elements) entries (we could even subtract + log(MAX_THRESH)). Since total_elements has type size_t, we get as + upper bound for log (total_elements): + bits per byte (CHAR_BIT) * sizeof(size_t). */ +#define STACK_SIZE (CHAR_BIT * sizeof(size_t)) +#define PUSH(low, high) ((void) ((top->lo =3D (low)), (top->hi =3D (high= )), ++top)) +#define POP(low, high) ((void) (--top, (low =3D top->lo), (high =3D top-= >hi))) +#define STACK_NOT_EMPTY (stack < top) + + +/* Order size using quicksort. This implementation incorporates + four optimizations discussed in Sedgewick: + + 1. Non-recursive, using an explicit stack of pointer that store the + next array partition to sort. To save time, this maximum amount + of space required to store an array of SIZE_MAX is allocated on th= e + stack. Assuming a 32-bit (64 bit) integer for size_t, this needs + only 32 * sizeof(stack_node) =3D=3D 256 bytes (for 64 bit: 1024 by= tes). + Pretty cheap, actually. + + 2. Chose the pivot element using a median-of-three decision tree. + This reduces the probability of selecting a bad pivot value and + eliminates certain extraneous comparisons. + + 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving + insertion sort to order the MAX_THRESH items within each partition= =2E + This is a big win, since insertion sort is faster for small, mostl= y + sorted array segments. + + 4. The larger of the two sub-partitions is always pushed onto the + stack first, with the algorithm then concentrating on the + smaller partition. This *guarantees* no more than log (total_elem= s) + 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) +{ + char *base_ptr =3D (char *) pbase; + + const size_t max_thresh =3D MAX_THRESH * size; + + if (total_elems =3D=3D 0) + /* Avoid lossage with unsigned arithmetic below. */ + return; + + if (total_elems > MAX_THRESH) + { + char *lo =3D base_ptr; + char *hi =3D &lo[size * (total_elems - 1)]; + stack_node stack[STACK_SIZE]; + stack_node *top =3D stack; + + PUSH (NULL, NULL); + + while (STACK_NOT_EMPTY) + { + char *left_ptr; + char *right_ptr; + + /* Select median value from among LO, MID, and HI. Rearrange + LO and HI so the three values are sorted. This lowers the + probability of picking a pathological pivot value and + skips a comparison for both the LEFT_PTR and RIGHT_PTR in + the while loops. */ + + char *mid =3D lo + size * ((hi - lo) / size >> 1); + + if ((*cmp) ((void *) mid, (void *) lo, arg) < 0) + SWAP (mid, lo, size); + if ((*cmp) ((void *) hi, (void *) mid, arg) < 0) + SWAP (mid, hi, size); + else + goto jump_over; + if ((*cmp) ((void *) mid, (void *) lo, arg) < 0) + SWAP (mid, lo, size); + jump_over:; + + left_ptr =3D lo + size; + right_ptr =3D hi - size; + + /* Here's the famous ``collapse the walls'' section of quicksort. + Gotta like those tight inner loops! They are the main reason + that this algorithm runs much faster than others. */ + do + { + while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0) + left_ptr +=3D size; + + while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0) + right_ptr -=3D size; + + if (left_ptr < right_ptr) + { + SWAP (left_ptr, right_ptr, size); + if (mid =3D=3D left_ptr) + mid =3D right_ptr; + else if (mid =3D=3D right_ptr) + mid =3D left_ptr; + left_ptr +=3D size; + right_ptr -=3D size; + } + else if (left_ptr =3D=3D right_ptr) + { + left_ptr +=3D size; + right_ptr -=3D size; + break; + } + } + while (left_ptr <=3D right_ptr); + + /* Set up pointers for next iteration. First determine whethe= r + left and right partitions are below the threshold size. If= so, + ignore one or both. Otherwise, push the larger partition's= + bounds on the stack and continue sorting the smaller one. *= / + + if ((size_t) (right_ptr - lo) <=3D max_thresh) + { + if ((size_t) (hi - left_ptr) <=3D max_thresh) + /* Ignore both small partitions. */ + POP (lo, hi); + else + /* Ignore small left partition. */ + lo =3D left_ptr; + } + else if ((size_t) (hi - left_ptr) <=3D max_thresh) + /* Ignore small right partition. */ + hi =3D right_ptr; + else if ((right_ptr - lo) > (hi - left_ptr)) + { + /* Push larger left partition indices. */ + PUSH (lo, right_ptr); + lo =3D left_ptr; + } + else + { + /* Push larger right partition indices. */ + PUSH (left_ptr, hi); + hi =3D right_ptr; + } + } + } + + /* Once the BASE_PTR array is partially sorted by quicksort the rest + is completely sorted using insertion sort, since this is efficient + for partitions below MAX_THRESH size. BASE_PTR points to the beginn= ing + of the array to sort, and END_PTR points at the very last element i= n + the array (*not* one beyond it!). */ + +#define min(x, y) ((x) < (y) ? (x) : (y)) + + { + char *const end_ptr =3D &base_ptr[size * (total_elems - 1)]; + char *tmp_ptr =3D base_ptr; + char *thresh =3D min(end_ptr, base_ptr + max_thresh); + char *run_ptr; + + /* Find smallest element in first threshold and place it at the + array's beginning. This is the smallest array element, + and the operation speeds up insertion sort's inner loop. */ + + for (run_ptr =3D tmp_ptr + size; run_ptr <=3D thresh; run_ptr +=3D s= ize) + if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0) + tmp_ptr =3D run_ptr; + + if (tmp_ptr !=3D base_ptr) + SWAP (tmp_ptr, base_ptr, size); + + /* Insertion sort, running from left-hand-side up to right-hand-side= =2E */ + + run_ptr =3D base_ptr + size; + while ((run_ptr +=3D size) <=3D end_ptr) + { + tmp_ptr =3D run_ptr - size; + while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0) + tmp_ptr -=3D size; + + tmp_ptr +=3D size; + if (tmp_ptr !=3D run_ptr) + { + char *trav; + + trav =3D run_ptr + size; + while (--trav >=3D run_ptr) + { + char c =3D *trav; + char *hi, *lo; + + for (hi =3D lo =3D trav; (lo -=3D size) >=3D tmp_ptr; hi= =3D lo) + *hi =3D *lo; + *hi =3D c; + } + } + } + } +} =3D=3D=3D added file 'lib/qsort_r.c' --- lib/qsort_r.c 1970-01-01 00:00:00 +0000 +++ lib/qsort_r.c 2014-08-29 20:46:33 +0000 @@ -0,0 +1,51 @@ +/* Reentrant sort function. + + Copyright 2014 Free Software Foundation, Inc. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3, or (at your option) + any later version. + + This program 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 General Public License for more details. + + You should have received a copy of the GNU General Public License alo= ng + with this program; if not, see . */ + +/* Written by Paul Eggert. */ + +#include + +#include + +/* This file is compiled only when the system has a qsort_r that needs + to be replaced because it has the BSD signature rather than the GNU + signature. */ + +struct thunk +{ + int (*cmp) (void const *, void const *, void *); + void *arg; +}; + +static int +thunk_cmp (void *thunk, void const *a, void const *b) +{ + struct thunk *th =3D thunk; + return th->cmp (a, b, th->arg); +} + +void +qsort_r (void *base, size_t nmemb, size_t size, + int (*cmp) (void const *, void const *, void *), + void *arg) +{ +# undef qsort_r + struct thunk thunk; + thunk.cmp =3D cmp; + thunk.arg =3D arg; + qsort_r (base, nmemb, size, &thunk, thunk_cmp); +} =3D=3D=3D modified file 'lib/stdlib.in.h' --- lib/stdlib.in.h 2014-01-01 07:43:34 +0000 +++ lib/stdlib.in.h 2014-08-29 20:46:33 +0000 @@ -520,6 +520,29 @@ _GL_CXXALIASWARN (putenv); #endif =20 +#if @GNULIB_QSORT_R@ +# if @REPLACE_QSORT_R@ +# if !(defined __cplusplus && defined GNULIB_NAMESPACE) +# undef qsort_r +# define qsort_r rpl_qsort_r +# endif +_GL_FUNCDECL_RPL (qsort_r, void, (void *base, size_t nmemb, size_t size,= + int (*compare) (void const *, void con= st *, + void *), + void *arg) _GL_ARG_NONNULL ((1, 4))); +_GL_CXXALIAS_RPL (qsort_r, void, (void *base, size_t nmemb, size_t size,= + int (*compare) (void const *, void con= st *, + void *), + void *arg)); +# else +_GL_CXXALIAS_SYS (qsort_r, void, (void *base, size_t nmemb, size_t size,= + int (*compare) (void const *, void con= st *, + void *), + void *arg)); +# endif +_GL_CXXALIASWARN (qsort_r); +#endif + =20 #if @GNULIB_RANDOM_R@ # if !@HAVE_RANDOM_R@ =3D=3D=3D modified file 'm4/gnulib-comp.m4' --- m4/gnulib-comp.m4 2014-05-17 08:11:31 +0000 +++ m4/gnulib-comp.m4 2014-08-29 20:46:33 +0000 @@ -104,6 +104,7 @@ # Code from module pthread_sigmask: # Code from module putenv: # Code from module qacl: + # Code from module qsort_r: # Code from module readlink: # Code from module readlinkat: # Code from module root-uid: @@ -313,6 +314,13 @@ fi gl_STDLIB_MODULE_INDICATOR([putenv]) gl_FUNC_ACL + gl_FUNC_QSORT_R + if test $HAVE_QSORT_R =3D 0; then + AC_LIBOBJ([qsort]) + elif test $REPLACE_QSORT_R =3D 1; then + AC_LIBOBJ([qsort_r]) + fi + gl_STDLIB_MODULE_INDICATOR([qsort_r]) gl_FUNC_READLINK if test $HAVE_READLINK =3D 0 || test $REPLACE_READLINK =3D 1; then AC_LIBOBJ([readlink]) @@ -865,6 +873,8 @@ lib/putenv.c lib/qcopy-acl.c lib/qset-acl.c + lib/qsort.c + lib/qsort_r.c lib/readlink.c lib/readlinkat.c lib/root-uid.h @@ -972,6 +982,7 @@ m4/pselect.m4 m4/pthread_sigmask.m4 m4/putenv.m4 + m4/qsort_r.m4 m4/readlink.m4 m4/readlinkat.m4 m4/secure_getenv.m4 =3D=3D=3D added file 'm4/qsort_r.m4' --- m4/qsort_r.m4 1970-01-01 00:00:00 +0000 +++ m4/qsort_r.m4 2014-08-29 20:46:33 +0000 @@ -0,0 +1,48 @@ +dnl Reentrant sort function. + +dnl Copyright 2014 Free Software Foundation, Inc. +dnl This file is free software; the Free Software Foundation +dnl gives unlimited permission to copy and/or distribute it, +dnl with or without modifications, as long as this notice is preserved. + +dnl Written by Paul Eggert. + +AC_DEFUN([gl_FUNC_QSORT_R], +[ + dnl Persuade glibc to declare qsort_r. + AC_REQUIRE([gl_USE_SYSTEM_EXTENSIONS]) + + AC_REQUIRE([gl_STDLIB_H_DEFAULTS]) + + AC_CACHE_CHECK([for qsort_r signature], [gl_cv_qsort_r_signature], + [AC_LINK_IFELSE( + [AC_LANG_PROGRAM([[#include + void qsort_r (void *, size_t, size_t, + int (*) (void const *, void cons= t *, + void *), + void *); + void (*p) (void *, size_t, size_t, + int (*) (void const *, void const *= , + void *), + void *) =3D qsort_r; + ]])], + [gl_cv_qsort_r_signature=3DGNU], + [AC_LINK_IFELSE( + [AC_LANG_PROGRAM([[#include + void qsort_r (void *, size_t, size_t, void = *, + int (*) (void *, + void const *, + void const *)); + void (*p) (void *, size_t, size_t, void *, + int (*) (void *, void const *, + void const *)) =3D qsor= t_r; + ]])], + [gl_cv_qsort_r_signature=3DBSD], + [gl_cv_qsort_r_signature=3Dno])])]) + + case $gl_cv_qsort_r_signature in + GNU) HAVE_QSORT_R=3D1;; + BSD) HAVE_QSORT_R=3D1 REPLACE_QSORT_R=3D1;; + *) HAVE_QSORT_R=3D0 REPLACE_QSORT_R=3D1;; + esac +]) =3D=3D=3D modified file 'm4/stdlib_h.m4' --- m4/stdlib_h.m4 2014-01-01 07:43:34 +0000 +++ m4/stdlib_h.m4 2014-08-29 20:46:33 +0000 @@ -55,6 +55,7 @@ GNULIB_PTSNAME=3D0; AC_SUBST([GNULIB_PTSNAME]) GNULIB_PTSNAME_R=3D0; AC_SUBST([GNULIB_PTSNAME_R]) GNULIB_PUTENV=3D0; AC_SUBST([GNULIB_PUTENV]) + GNULIB_QSORT_R=3D0; AC_SUBST([GNULIB_QSORT_R]) GNULIB_RANDOM=3D0; AC_SUBST([GNULIB_RANDOM]) GNULIB_RANDOM_R=3D0; AC_SUBST([GNULIB_RANDOM_R]) GNULIB_REALLOC_POSIX=3D0; AC_SUBST([GNULIB_REALLOC_POSIX]) @@ -107,6 +108,7 @@ REPLACE_PTSNAME=3D0; AC_SUBST([REPLACE_PTSNAME]) REPLACE_PTSNAME_R=3D0; AC_SUBST([REPLACE_PTSNAME_R]) REPLACE_PUTENV=3D0; AC_SUBST([REPLACE_PUTENV]) + REPLACE_QSORT_R=3D0; AC_SUBST([REPLACE_QSORT_R]) REPLACE_RANDOM_R=3D0; AC_SUBST([REPLACE_RANDOM_R]) REPLACE_REALLOC=3D0; AC_SUBST([REPLACE_REALLOC]) REPLACE_REALPATH=3D0; AC_SUBST([REPLACE_REALPATH]) =3D=3D=3D modified file 'src/ChangeLog' --- src/ChangeLog 2014-08-29 20:16:40 +0000 +++ src/ChangeLog 2014-08-29 20:46:33 +0000 @@ -1,5 +1,10 @@ 2014-08-29 Paul Eggert =20 + Modularize qsort_r in Gnulib, to simplify Emacs proper. + * fns.c (sort_vector_predicate) [!HAVE_QSORT_R]: Remove. + (sort_vector_compare, sort_vector): Simplify by assuming GNU qsort_r, + since Gnulib now supplies it. + * sysdep.c (str_collate): Do not look at errno after towlower_l. errno's value is not specified after towlower_l. Instead, assume that towlower_l returns its argument on failure, which is portable =3D=3D=3D modified file 'src/fns.c' --- src/fns.c 2014-08-29 19:18:06 +0000 +++ src/fns.c 2014-08-29 20:46:33 +0000 @@ -1897,42 +1897,24 @@ return merge (front, back, predicate); } =20 -/* Using GNU qsort_r, we can pass this as a parameter. This also - exists on FreeBSD and Darwin/OSX, but with a different signature. */ -#ifndef HAVE_QSORT_R -static Lisp_Object sort_vector_predicate; -#endif - -/* Comparison function called by qsort. */ +/* Comparison function called by qsort_r. */ =20 static int -#ifdef HAVE_QSORT_R -#if defined (DARWIN_OS) || defined (__FreeBSD__) -sort_vector_compare (void *arg, const void *p, const void *q) -#elif defined (GNU_LINUX) sort_vector_compare (const void *p, const void *q, void *arg) -#else /* neither darwin/bsd nor gnu/linux */ -#error "check how qsort_r comparison function works on your platform" -#endif /* DARWIN_OS || __FreeBSD__ */ -#else /* not HAVE_QSORT_R */ -sort_vector_compare (const void *p, const void *q) -#endif /* HAVE_QSORT_R */ { - bool more, less; - Lisp_Object op, oq, vp, vq; -#ifdef HAVE_QSORT_R - Lisp_Object sort_vector_predicate =3D *(Lisp_Object *) arg; -#endif - - op =3D *(Lisp_Object *) p; - oq =3D *(Lisp_Object *) q; - vp =3D XSAVE_OBJECT (op, 1); - vq =3D XSAVE_OBJECT (oq, 1); + Lisp_Object const *ap =3D p; + Lisp_Object const *aq =3D q; + Lisp_Object const *aarg =3D arg; + Lisp_Object op =3D *ap; + Lisp_Object oq =3D *aq; + Lisp_Object sort_vector_predicate =3D *aarg; + Lisp_Object vp =3D XSAVE_OBJECT (op, 1); + Lisp_Object vq =3D XSAVE_OBJECT (oq, 1); =20 /* Use recorded element index as a secondary key to preserve original order. Pretty ugly but works. */ - more =3D NILP (call2 (sort_vector_predicate, vp, vq)); - less =3D NILP (call2 (sort_vector_predicate, vq, vp)); + bool more =3D NILP (call2 (sort_vector_predicate, vp, vq)); + bool less =3D NILP (call2 (sort_vector_predicate, vq, vp)); return ((more && !less) ? 1 : ((!more && less) ? -1 : XSAVE_INTEGER (op, 0) - XSAVE_INTEGER (oq, 0))); @@ -1950,23 +1932,11 @@ =20 if (len < 2) return vector; - /* Record original index of each element to make qsort stable. */ + /* Record original index of each element to make qsort_r stable. */ for (i =3D 0; i < len; i++) v[i] =3D make_save_int_obj (i, v[i]); =20 - /* Setup predicate and sort. */ -#ifdef HAVE_QSORT_R -#if defined (DARWIN_OS) || defined (__FreeBSD__) - qsort_r (v, len, word_size, (void *) &predicate, sort_vector_compare);= -#elif defined (GNU_LINUX) - qsort_r (v, len, word_size, sort_vector_compare, (void *) &predicate);= -#else /* neither darwin/bsd nor gnu/linux */ -#error "check how qsort_r works on your platform" -#endif /* DARWIN_OS || __FreeBSD__ */ -#else /* not HAVE_QSORT_R */ - sort_vector_predicate =3D predicate; - qsort (v, len, word_size, sort_vector_compare); -#endif /* HAVE_QSORT_R */ + qsort_r (v, len, word_size, sort_vector_compare, &predicate); =20 /* Discard indexes and restore original elements. */ for (i =3D 0; i < len; i++) --------------010809080206030708060802-- From unknown Sat Sep 13 17:05:26 2025 X-Loop: help-debbugs@gnu.org Subject: bug#18360: Modularize recent qsort_r additions Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 30 Aug 2014 07:30:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 18360 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Paul Eggert Cc: 18360@debbugs.gnu.org Reply-To: Eli Zaretskii Received: via spool by 18360-submit@debbugs.gnu.org id=B18360.140938379229778 (code B ref 18360); Sat, 30 Aug 2014 07:30:02 +0000 Received: (at 18360) by debbugs.gnu.org; 30 Aug 2014 07:29:52 +0000 Received: from localhost ([127.0.0.1]:53961 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNd6d-0007kD-Tk for submit@debbugs.gnu.org; Sat, 30 Aug 2014 03:29:52 -0400 Received: from mtaout22.012.net.il ([80.179.55.172]:51629) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNd6a-0007ju-Iw for 18360@debbugs.gnu.org; Sat, 30 Aug 2014 03:29:49 -0400 Received: from conversion-daemon.a-mtaout22.012.net.il by a-mtaout22.012.net.il (HyperSendmail v2007.08) id <0NB300400Z1HXD00@a-mtaout22.012.net.il> for 18360@debbugs.gnu.org; Sat, 30 Aug 2014 10:29:42 +0300 (IDT) Received: from HOME-C4E4A596F7 ([87.69.4.28]) by a-mtaout22.012.net.il (HyperSendmail v2007.08) with ESMTPA id <0NB300401ZHHSY30@a-mtaout22.012.net.il>; Sat, 30 Aug 2014 10:29:42 +0300 (IDT) Date: Sat, 30 Aug 2014 10:29:44 +0300 From: Eli Zaretskii In-reply-to: <5400E959.3000805@cs.ucla.edu> X-012-Sender: halo1@inter.net.il Message-id: <831tryigev.fsf@gnu.org> References: <5400E959.3000805@cs.ucla.edu> X-Spam-Score: 1.0 (+) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 1.0 (+) > Date: Fri, 29 Aug 2014 13:58:01 -0700 > From: Paul Eggert > > The recent changes to have Emacs use qsort_r look good except for the > forest of #ifdefs in Emacs proper. Attached is a proposed patch to > migrate that stuff into Gnulib. As usual most of this patch is > automatically generated; fns.c contains the crucial hand-generated > stuff. I have not tested this on Microsoft Windows and so am posting it > here first to give Eli a heads-up. Why is it a good idea to use qsort_r? It's evidently not portable enough, and its benefits for Emacs at this time are nil, AFAICT. I say let's wait until we really need a reentrant sort function, and introduce it then. qsort is good enough for us for now. From unknown Sat Sep 13 17:05:26 2025 X-Loop: help-debbugs@gnu.org Subject: bug#18360: Modularize recent qsort_r additions Resent-From: Paul Eggert Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 30 Aug 2014 13:46:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 18360 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Eli Zaretskii Cc: 18360@debbugs.gnu.org Received: via spool by 18360-submit@debbugs.gnu.org id=B18360.140940630510688 (code B ref 18360); Sat, 30 Aug 2014 13:46:01 +0000 Received: (at 18360) by debbugs.gnu.org; 30 Aug 2014 13:45:05 +0000 Received: from localhost ([127.0.0.1]:54101 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNixk-0002mI-Gv for submit@debbugs.gnu.org; Sat, 30 Aug 2014 09:45:04 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:38691) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNixh-0002lO-Dk for 18360@debbugs.gnu.org; Sat, 30 Aug 2014 09:45:02 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 2E8B8A60016; Sat, 30 Aug 2014 06:44:55 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id fTEloKE3zltu; Sat, 30 Aug 2014 06:44:46 -0700 (PDT) Received: from [192.168.1.9] (pool-71-177-17-123.lsanca.dsl-w.verizon.net [71.177.17.123]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 8D248A60002; Sat, 30 Aug 2014 06:44:46 -0700 (PDT) Message-ID: <5401D54B.40601@cs.ucla.edu> Date: Sat, 30 Aug 2014 06:44:43 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.0 MIME-Version: 1.0 References: <5400E959.3000805@cs.ucla.edu> <831tryigev.fsf@gnu.org> In-Reply-To: <831tryigev.fsf@gnu.org> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -2.3 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) Eli Zaretskii wrote: > qsort is good enough for us for now. Unfortunately qsort doesn't work either, as discussed in Bug#18361. From unknown Sat Sep 13 17:05:26 2025 X-Loop: help-debbugs@gnu.org Subject: bug#18360: Modularize recent qsort_r additions Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 30 Aug 2014 14:16:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 18360 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Paul Eggert Cc: 18360@debbugs.gnu.org Reply-To: Eli Zaretskii Received: via spool by 18360-submit@debbugs.gnu.org id=B18360.140940813313872 (code B ref 18360); Sat, 30 Aug 2014 14:16:01 +0000 Received: (at 18360) by debbugs.gnu.org; 30 Aug 2014 14:15:33 +0000 Received: from localhost ([127.0.0.1]:54518 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNjRF-0003bg-2z for submit@debbugs.gnu.org; Sat, 30 Aug 2014 10:15:33 -0400 Received: from mtaout25.012.net.il ([80.179.55.181]:41390) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNjRB-0003bM-EE for 18360@debbugs.gnu.org; Sat, 30 Aug 2014 10:15:30 -0400 Received: from conversion-daemon.mtaout25.012.net.il by mtaout25.012.net.il (HyperSendmail v2007.08) id <0NB400C00H7XUK00@mtaout25.012.net.il> for 18360@debbugs.gnu.org; Sat, 30 Aug 2014 17:10:03 +0300 (IDT) Received: from HOME-C4E4A596F7 ([87.69.4.28]) by mtaout25.012.net.il (HyperSendmail v2007.08) with ESMTPA id <0NB4005WEI0RZM90@mtaout25.012.net.il>; Sat, 30 Aug 2014 17:10:03 +0300 (IDT) Date: Sat, 30 Aug 2014 17:15:25 +0300 From: Eli Zaretskii In-reply-to: <5401D54B.40601@cs.ucla.edu> X-012-Sender: halo1@inter.net.il Message-id: <83ppfigj2a.fsf@gnu.org> References: <5400E959.3000805@cs.ucla.edu> <831tryigev.fsf@gnu.org> <5401D54B.40601@cs.ucla.edu> X-Spam-Score: 1.0 (+) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 1.0 (+) > Date: Sat, 30 Aug 2014 06:44:43 -0700 > From: Paul Eggert > CC: 18360@debbugs.gnu.org > > Eli Zaretskii wrote: > > qsort is good enough for us for now. > > Unfortunately qsort doesn't work either, as discussed in Bug#18361. That is a different issue, and should not get in our way here. For the purposes of this bug, can we agree that qsort_r is not needed, and the changes that use it should be reverted to use qsort instead? We could then discuss separately what to do with qsort. From unknown Sat Sep 13 17:05:26 2025 X-Loop: help-debbugs@gnu.org Subject: bug#18360: Modularize recent qsort_r additions Resent-From: Paul Eggert Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 30 Aug 2014 16:40:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 18360 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Eli Zaretskii Cc: 18360@debbugs.gnu.org Received: via spool by 18360-submit@debbugs.gnu.org id=B18360.140941679227663 (code B ref 18360); Sat, 30 Aug 2014 16:40:02 +0000 Received: (at 18360) by debbugs.gnu.org; 30 Aug 2014 16:39:52 +0000 Received: from localhost ([127.0.0.1]:54550 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNlgt-0007C7-UO for submit@debbugs.gnu.org; Sat, 30 Aug 2014 12:39:52 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:44005) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNlgq-0007Bs-AZ for 18360@debbugs.gnu.org; Sat, 30 Aug 2014 12:39:49 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 36CD0A60013; Sat, 30 Aug 2014 09:39:42 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Vp6z4WpW3JcR; Sat, 30 Aug 2014 09:39:33 -0700 (PDT) Received: from [192.168.1.9] (pool-71-177-17-123.lsanca.dsl-w.verizon.net [71.177.17.123]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 5ED2FA60002; Sat, 30 Aug 2014 09:39:33 -0700 (PDT) Message-ID: <5401FE44.4050800@cs.ucla.edu> Date: Sat, 30 Aug 2014 09:39:32 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.0 MIME-Version: 1.0 References: <5400E959.3000805@cs.ucla.edu> <831tryigev.fsf@gnu.org> <5401D54B.40601@cs.ucla.edu> <83ppfigj2a.fsf@gnu.org> In-Reply-To: <83ppfigj2a.fsf@gnu.org> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -2.3 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) Eli Zaretskii wrote: > That is a different issue, and should not get in our way here. For > the purposes of this bug, can we agree that qsort_r is not needed, and > the changes that use it should be reverted to use qsort instead? Yes and no. The previous version did not use qsort, so reverting the changes that use qsort_r will the drop the use of qsort (and qsort_r) entirely. One could further *modify* the changes to stop using qsort_r, and to use qsort only. But what would be the point? qsort (and qsort_r) are mistakes here; we cannot use them. Dropping the use of qsort_r would be like wiping the lipstick off a pig. From unknown Sat Sep 13 17:05:26 2025 X-Loop: help-debbugs@gnu.org Subject: bug#18360: Modularize recent qsort_r additions Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 30 Aug 2014 16:44:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 18360 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Paul Eggert Cc: 18360@debbugs.gnu.org Reply-To: Eli Zaretskii Received: via spool by 18360-submit@debbugs.gnu.org id=B18360.140941702728072 (code B ref 18360); Sat, 30 Aug 2014 16:44:01 +0000 Received: (at 18360) by debbugs.gnu.org; 30 Aug 2014 16:43:47 +0000 Received: from localhost ([127.0.0.1]:54566 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNlkg-0007Ii-RO for submit@debbugs.gnu.org; Sat, 30 Aug 2014 12:43:47 -0400 Received: from mtaout25.012.net.il ([80.179.55.181]:58965) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNlkf-0007IV-6S for 18360@debbugs.gnu.org; Sat, 30 Aug 2014 12:43:46 -0400 Received: from conversion-daemon.mtaout25.012.net.il by mtaout25.012.net.il (HyperSendmail v2007.08) id <0NB400G00OBMT700@mtaout25.012.net.il> for 18360@debbugs.gnu.org; Sat, 30 Aug 2014 19:38:18 +0300 (IDT) Received: from HOME-C4E4A596F7 ([87.69.4.28]) by mtaout25.012.net.il (HyperSendmail v2007.08) with ESMTPA id <0NB400EIIOVUAZ40@mtaout25.012.net.il>; Sat, 30 Aug 2014 19:38:18 +0300 (IDT) Date: Sat, 30 Aug 2014 19:43:41 +0300 From: Eli Zaretskii In-reply-to: <5401FE44.4050800@cs.ucla.edu> X-012-Sender: halo1@inter.net.il Message-id: <83lhq6gc76.fsf@gnu.org> References: <5400E959.3000805@cs.ucla.edu> <831tryigev.fsf@gnu.org> <5401D54B.40601@cs.ucla.edu> <83ppfigj2a.fsf@gnu.org> <5401FE44.4050800@cs.ucla.edu> X-Spam-Score: 1.0 (+) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 1.0 (+) > Date: Sat, 30 Aug 2014 09:39:32 -0700 > From: Paul Eggert > CC: 18360@debbugs.gnu.org > > Eli Zaretskii wrote: > > That is a different issue, and should not get in our way here. For > > the purposes of this bug, can we agree that qsort_r is not needed, and > > the changes that use it should be reverted to use qsort instead? > > Yes and no. The previous version did not use qsort, so reverting the > changes that use qsort_r will the drop the use of qsort (and qsort_r) > entirely. > > One could further *modify* the changes to stop using qsort_r, and to use > qsort only. But what would be the point? qsort (and qsort_r) are > mistakes here; we cannot use them. Dropping the use of qsort_r would be > like wiping the lipstick off a pig. Then let's use a different sort routine, not qsort. From unknown Sat Sep 13 17:05:26 2025 X-Loop: help-debbugs@gnu.org Subject: bug#18360: Modularize recent qsort_r additions Resent-From: Paul Eggert Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 30 Aug 2014 16:46:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 18360 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Eli Zaretskii Cc: 18360@debbugs.gnu.org Received: via spool by 18360-submit@debbugs.gnu.org id=B18360.140941710528237 (code B ref 18360); Sat, 30 Aug 2014 16:46:01 +0000 Received: (at 18360) by debbugs.gnu.org; 30 Aug 2014 16:45:05 +0000 Received: from localhost ([127.0.0.1]:54570 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNllw-0007LM-8z for submit@debbugs.gnu.org; Sat, 30 Aug 2014 12:45:05 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:44148) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNllu-0007Kb-3c for 18360@debbugs.gnu.org; Sat, 30 Aug 2014 12:45:02 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 711E5A60013; Sat, 30 Aug 2014 09:44:56 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id vARWlBlmIV9M; Sat, 30 Aug 2014 09:44:47 -0700 (PDT) Received: from [192.168.1.9] (pool-71-177-17-123.lsanca.dsl-w.verizon.net [71.177.17.123]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id CC19EA60002; Sat, 30 Aug 2014 09:44:47 -0700 (PDT) Message-ID: <5401FF7F.4070104@cs.ucla.edu> Date: Sat, 30 Aug 2014 09:44:47 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.0 MIME-Version: 1.0 References: <5400E959.3000805@cs.ucla.edu> <831tryigev.fsf@gnu.org> <5401D54B.40601@cs.ucla.edu> <83ppfigj2a.fsf@gnu.org> <5401FE44.4050800@cs.ucla.edu> <83lhq6gc76.fsf@gnu.org> In-Reply-To: <83lhq6gc76.fsf@gnu.org> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -2.3 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) Eli Zaretskii wrote: > Then let's use a different sort routine, not qsort. Exactly my point! I'll get on it. From unknown Sat Sep 13 17:05:26 2025 MIME-Version: 1.0 X-Mailer: MIME-tools 5.503 (Entity 5.503) X-Loop: help-debbugs@gnu.org From: help-debbugs@gnu.org (GNU bug Tracking System) To: Paul Eggert Subject: bug#18360: closed (Re: bug#18360: Modularize recent qsort_r additions) Message-ID: References: <54020252.2090100@cs.ucla.edu> <5400E959.3000805@cs.ucla.edu> X-Gnu-PR-Message: they-closed 18360 X-Gnu-PR-Package: emacs X-Gnu-PR-Keywords: patch Reply-To: 18360@debbugs.gnu.org Date: Sat, 30 Aug 2014 16:58:02 +0000 Content-Type: multipart/mixed; boundary="----------=_1409417882-29403-1" This is a multi-part message in MIME format... ------------=_1409417882-29403-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Your bug report #18360: Modularize recent qsort_r additions which was filed against the emacs package, has been closed. The explanation is attached below, along with your original report. If you require more details, please reply to 18360@debbugs.gnu.org. --=20 18360: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D18360 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1409417882-29403-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at 18360-done) by debbugs.gnu.org; 30 Aug 2014 16:57:08 +0000 Received: from localhost ([127.0.0.1]:54578 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNlxb-0007d9-OI for submit@debbugs.gnu.org; Sat, 30 Aug 2014 12:57:08 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:44540) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNlxZ-0007ce-7j for 18360-done@debbugs.gnu.org; Sat, 30 Aug 2014 12:57:05 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 57B81A60013; Sat, 30 Aug 2014 09:56:59 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id KJl0j-ZSAaIQ; Sat, 30 Aug 2014 09:56:50 -0700 (PDT) Received: from [192.168.1.9] (pool-71-177-17-123.lsanca.dsl-w.verizon.net [71.177.17.123]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id AFE78A60002; Sat, 30 Aug 2014 09:56:50 -0700 (PDT) Message-ID: <54020252.2090100@cs.ucla.edu> Date: Sat, 30 Aug 2014 09:56:50 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.0 MIME-Version: 1.0 To: Eli Zaretskii Subject: Re: bug#18360: Modularize recent qsort_r additions References: <5400E959.3000805@cs.ucla.edu> <831tryigev.fsf@gnu.org> <5401D54B.40601@cs.ucla.edu> <83ppfigj2a.fsf@gnu.org> <5401FE44.4050800@cs.ucla.edu> <83lhq6gc76.fsf@gnu.org> <5401FF7F.4070104@cs.ucla.edu> In-Reply-To: <5401FF7F.4070104@cs.ucla.edu> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 18360-done Cc: 18360-done@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) Paul Eggert wrote: > Eli Zaretskii wrote: >> Then let's use a different sort routine, not qsort. > > Exactly my point! I'll get on it. Oh, and I'll close this bug report, since we shouldn't use either qsort or qsort_r here. ------------=_1409417882-29403-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at submit) by debbugs.gnu.org; 29 Aug 2014 20:58:36 +0000 Received: from localhost ([127.0.0.1]:53820 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNTFh-0007fJ-Tg for submit@debbugs.gnu.org; Fri, 29 Aug 2014 16:58:35 -0400 Received: from eggs.gnu.org ([208.118.235.92]:51276) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNTFe-0007f5-3s for submit@debbugs.gnu.org; Fri, 29 Aug 2014 16:58:32 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XNTFU-0001Wv-Fo for submit@debbugs.gnu.org; Fri, 29 Aug 2014 16:58:24 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:34083) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XNTFU-0001Wb-Ce for submit@debbugs.gnu.org; Fri, 29 Aug 2014 16:58:20 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:52985) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XNTFQ-0002DG-07 for bug-gnu-emacs@gnu.org; Fri, 29 Aug 2014 16:58:20 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XNTFL-0001QG-Hw for bug-gnu-emacs@gnu.org; Fri, 29 Aug 2014 16:58:15 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:58422) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XNTFL-0001QC-0z for bug-gnu-emacs@gnu.org; Fri, 29 Aug 2014 16:58:11 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 56C52A6000B for ; Fri, 29 Aug 2014 13:58:10 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id VWRhHi1Iy5MT for ; Fri, 29 Aug 2014 13:58:06 -0700 (PDT) Received: from penguin.cs.ucla.edu (Penguin.CS.UCLA.EDU [131.179.64.200]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 37B30A60001 for ; Fri, 29 Aug 2014 13:58:06 -0700 (PDT) Message-ID: <5400E959.3000805@cs.ucla.edu> Date: Fri, 29 Aug 2014 13:58:01 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.7.0 MIME-Version: 1.0 To: Emacs bug reports Subject: Modularize recent qsort_r additions Content-Type: multipart/mixed; boundary="------------010809080206030708060802" X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -4.0 (----) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -4.0 (----) This is a multi-part message in MIME format. --------------010809080206030708060802 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Tags: patch The recent changes to have Emacs use qsort_r look good except for the forest of #ifdefs in Emacs proper. Attached is a proposed patch to migrate that stuff into Gnulib. As usual most of this patch is automatically generated; fns.c contains the crucial hand-generated stuff. I have not tested this on Microsoft Windows and so am posting it here first to give Eli a heads-up. --------------010809080206030708060802 Content-Type: text/x-patch; name="qsort_r.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="qsort_r.patch" =3D=3D=3D modified file 'ChangeLog' --- ChangeLog 2014-08-29 07:29:47 +0000 +++ ChangeLog 2014-08-29 20:46:33 +0000 @@ -1,3 +1,13 @@ +2014-08-29 Paul Eggert + + Modularize qsort_r in Gnulib, to simplify Emacs proper. + * configure.ac (qsort_r): Remove check; gnulib does this now. + * lib/qsort.c, lib/qsort_r.c, m4/qsort_r.m4: New files. + Merge from gnulib, incorporating: + 2014-08-29 qsort_r: new module, for GNU-style qsort_r + * lib/gnulib.mk, m4/gnulib-comp.m4: Regenerate. + * lib/stdlib.in.h, m4/stdlib_h.m4: Update from gnulib. + 2014-08-29 Dmitry Antipov =20 * configure.ac (AC_CHECK_FUNCS): Check for qsort_r. =3D=3D=3D modified file 'admin/ChangeLog' --- admin/ChangeLog 2014-08-29 18:10:15 +0000 +++ admin/ChangeLog 2014-08-29 20:46:33 +0000 @@ -1,3 +1,8 @@ +2014-08-29 Paul Eggert + + Modularize qsort_r in Gnulib, to simplify Emacs proper. + * merge-gnulib (GNULIB_MODULES): Add qsort_r. + 2014-08-29 Michael Albinus =20 * authors.el (authors): Use LOCALE argument of `string-collate-lessp'. =3D=3D=3D modified file 'admin/merge-gnulib' --- admin/merge-gnulib 2014-07-14 19:23:18 +0000 +++ admin/merge-gnulib 2014-08-29 20:46:33 +0000 @@ -34,7 +34,7 @@ getloadavg getopt-gnu gettime gettimeofday intprops largefile lstat manywarnings memrchr mkostemp mktime - pipe2 pselect pthread_sigmask putenv qacl readlink readlinkat + pipe2 pselect pthread_sigmask putenv qacl qsort_r readlink readlinkat sig2str socklen stat-time stdalign stdio strftime strtoimax strtoumax symlink sys_stat sys_time time timer-time timespec-add timespec-sub =3D=3D=3D modified file 'configure.ac' --- configure.ac 2014-08-29 07:29:47 +0000 +++ configure.ac 2014-08-29 20:46:33 +0000 @@ -3573,7 +3573,7 @@ getrlimit setrlimit shutdown getaddrinfo \ pthread_sigmask strsignal setitimer \ sendto recvfrom getsockname getpeername getifaddrs freeifaddrs \ -gai_strerror sync qsort_r \ +gai_strerror sync \ getpwent endpwent getgrent endgrent \ cfmakeraw cfsetspeed copysign __executable_start log2) LIBS=3D$OLD_LIBS =3D=3D=3D modified file 'lib/gnulib.mk' --- lib/gnulib.mk 2014-08-04 18:44:49 +0000 +++ lib/gnulib.mk 2014-08-29 20:46:33 +0000 @@ -21,7 +21,7 @@ # the same distribution terms as the rest of that program. # # Generated by gnulib-tool. -# Reproduce by: gnulib-tool --import --dir=3D. --lib=3Dlibgnu --source-b= ase=3Dlib --m4-base=3Dm4 --doc-base=3Ddoc --tests-base=3Dtests --aux-dir=3D= build-aux --avoid=3Dclose --avoid=3Ddup --avoid=3Dfchdir --avoid=3Dfstat = --avoid=3Dmalloc-posix --avoid=3Dmsvc-inval --avoid=3Dmsvc-nothrow --avoi= d=3Dopen --avoid=3Dopenat-die --avoid=3Dopendir --avoid=3Draise --avoid=3D= save-cwd --avoid=3Dselect --avoid=3Dsigprocmask --avoid=3Dstdarg --avoid=3D= stdbool --avoid=3Dthreadlib --makefile-name=3Dgnulib.mk --conditional-dep= endencies --no-libtool --macro-prefix=3Dgl --no-vc-files alloca-opt binar= y-io byteswap c-ctype c-strcase careadlinkat close-stream count-one-bits = count-trailing-zeros crypto/md5 crypto/sha1 crypto/sha256 crypto/sha512 d= toastr dtotimespec dup2 environ execinfo faccessat fcntl fcntl-h fdatasyn= c fdopendir filemode fstatat fsync getloadavg getopt-gnu gettime gettimeo= fday intprops largefile lstat manywarnings memrchr mkostemp mktime pipe2 = pselect pthread_sigmask putenv qacl readlink readlinkat sig2str socklen s= tat-time stdalign stdio strftime strtoimax strtoumax symlink sys_stat sys= _time time timer-time timespec-add timespec-sub unsetenv update-copyright= utimens warnings +# Reproduce by: gnulib-tool --import --dir=3D. --lib=3Dlibgnu --source-b= ase=3Dlib --m4-base=3Dm4 --doc-base=3Ddoc --tests-base=3Dtests --aux-dir=3D= build-aux --avoid=3Dclose --avoid=3Ddup --avoid=3Dfchdir --avoid=3Dfstat = --avoid=3Dmalloc-posix --avoid=3Dmsvc-inval --avoid=3Dmsvc-nothrow --avoi= d=3Dopen --avoid=3Dopenat-die --avoid=3Dopendir --avoid=3Draise --avoid=3D= save-cwd --avoid=3Dselect --avoid=3Dsigprocmask --avoid=3Dstdarg --avoid=3D= stdbool --avoid=3Dthreadlib --makefile-name=3Dgnulib.mk --conditional-dep= endencies --no-libtool --macro-prefix=3Dgl --no-vc-files alloca-opt binar= y-io byteswap c-ctype c-strcase careadlinkat close-stream count-one-bits = count-trailing-zeros crypto/md5 crypto/sha1 crypto/sha256 crypto/sha512 d= toastr dtotimespec dup2 environ execinfo faccessat fcntl fcntl-h fdatasyn= c fdopendir filemode fstatat fsync getloadavg getopt-gnu gettime gettimeo= fday intprops largefile lstat manywarnings memrchr mkostemp mktime pipe2 = pselect pthread_sigmask putenv qacl qsort_r readlink readlinkat sig2str s= ocklen stat-time stdalign stdio strftime strtoimax strtoumax symlink sys_= stat sys_time time timer-time timespec-add timespec-sub unsetenv update-c= opyright utimens warnings =20 =20 MOSTLYCLEANFILES +=3D core *.stackdump @@ -688,6 +688,15 @@ =20 ## end gnulib module qacl =20 +## begin gnulib module qsort_r + + +EXTRA_DIST +=3D qsort.c qsort_r.c + +EXTRA_libgnu_a_SOURCES +=3D qsort.c qsort_r.c + +## end gnulib module qsort_r + ## begin gnulib module readlink =20 =20 @@ -1141,6 +1150,7 @@ -e 's/@''GNULIB_PTSNAME''@/$(GNULIB_PTSNAME)/g' \ -e 's/@''GNULIB_PTSNAME_R''@/$(GNULIB_PTSNAME_R)/g' \ -e 's/@''GNULIB_PUTENV''@/$(GNULIB_PUTENV)/g' \ + -e 's/@''GNULIB_QSORT_R''@/$(GNULIB_QSORT_R)/g' \ -e 's/@''GNULIB_RANDOM''@/$(GNULIB_RANDOM)/g' \ -e 's/@''GNULIB_RANDOM_R''@/$(GNULIB_RANDOM_R)/g' \ -e 's/@''GNULIB_REALLOC_POSIX''@/$(GNULIB_REALLOC_POSIX)/g' \ @@ -1192,6 +1202,7 @@ -e 's|@''REPLACE_PTSNAME''@|$(REPLACE_PTSNAME)|g' \ -e 's|@''REPLACE_PTSNAME_R''@|$(REPLACE_PTSNAME_R)|g' \ -e 's|@''REPLACE_PUTENV''@|$(REPLACE_PUTENV)|g' \ + -e 's|@''REPLACE_QSORT_R''@|$(REPLACE_QSORT_R)|g' \ -e 's|@''REPLACE_RANDOM_R''@|$(REPLACE_RANDOM_R)|g' \ -e 's|@''REPLACE_REALLOC''@|$(REPLACE_REALLOC)|g' \ -e 's|@''REPLACE_REALPATH''@|$(REPLACE_REALPATH)|g' \ =3D=3D=3D added file 'lib/qsort.c' --- lib/qsort.c 1970-01-01 00:00:00 +0000 +++ lib/qsort.c 2014-08-29 20:46:33 +0000 @@ -0,0 +1,254 @@ +/* Copyright (C) 1991-2014 Free Software Foundation, Inc. + This file is part of the GNU C Library. + Written by Douglas C. Schmidt (schmidt@ics.uci.edu). + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public + License as published by the Free Software Foundation; either + version 3 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 + General Public License for more details. + + You should have received a copy of the GNU General Public + License along with the GNU C Library; if not, see + . */ + +/* If you consider tuning this algorithm, you should consult first: + Engineering a sort function; Jon Bentley and M. Douglas McIlroy; + Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. *= / + +#include +#include +#include + +#ifndef _LIBC +# define _quicksort qsort_r +# define __compar_d_fn_t compar_d_fn_t +typedef int (*compar_d_fn_t) (const void *, const void *, void *); +#endif + +/* Byte-wise swap two items of size SIZE. */ +#define SWAP(a, b, size) \ + do \ + { \ + size_t __size =3D (size); \ + char *__a =3D (a), *__b =3D (b); \ + do \ + { \ + char __tmp =3D *__a; \ + *__a++ =3D *__b; \ + *__b++ =3D __tmp; \ + } while (--__size > 0); \ + } while (0) + +/* Discontinue quicksort algorithm when partition gets below this size. + This particular magic number was chosen to work best on a Sun 4/260. = */ +#define MAX_THRESH 4 + +/* Stack node declarations used to store unfulfilled partition obligatio= ns. */ +typedef struct + { + char *lo; + char *hi; + } stack_node; + +/* The next 4 #defines implement a very fast in-line stack abstraction. = */ +/* The stack needs log (total_elements) entries (we could even subtract + log(MAX_THRESH)). Since total_elements has type size_t, we get as + upper bound for log (total_elements): + bits per byte (CHAR_BIT) * sizeof(size_t). */ +#define STACK_SIZE (CHAR_BIT * sizeof(size_t)) +#define PUSH(low, high) ((void) ((top->lo =3D (low)), (top->hi =3D (high= )), ++top)) +#define POP(low, high) ((void) (--top, (low =3D top->lo), (high =3D top-= >hi))) +#define STACK_NOT_EMPTY (stack < top) + + +/* Order size using quicksort. This implementation incorporates + four optimizations discussed in Sedgewick: + + 1. Non-recursive, using an explicit stack of pointer that store the + next array partition to sort. To save time, this maximum amount + of space required to store an array of SIZE_MAX is allocated on th= e + stack. Assuming a 32-bit (64 bit) integer for size_t, this needs + only 32 * sizeof(stack_node) =3D=3D 256 bytes (for 64 bit: 1024 by= tes). + Pretty cheap, actually. + + 2. Chose the pivot element using a median-of-three decision tree. + This reduces the probability of selecting a bad pivot value and + eliminates certain extraneous comparisons. + + 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving + insertion sort to order the MAX_THRESH items within each partition= =2E + This is a big win, since insertion sort is faster for small, mostl= y + sorted array segments. + + 4. The larger of the two sub-partitions is always pushed onto the + stack first, with the algorithm then concentrating on the + smaller partition. This *guarantees* no more than log (total_elem= s) + 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) +{ + char *base_ptr =3D (char *) pbase; + + const size_t max_thresh =3D MAX_THRESH * size; + + if (total_elems =3D=3D 0) + /* Avoid lossage with unsigned arithmetic below. */ + return; + + if (total_elems > MAX_THRESH) + { + char *lo =3D base_ptr; + char *hi =3D &lo[size * (total_elems - 1)]; + stack_node stack[STACK_SIZE]; + stack_node *top =3D stack; + + PUSH (NULL, NULL); + + while (STACK_NOT_EMPTY) + { + char *left_ptr; + char *right_ptr; + + /* Select median value from among LO, MID, and HI. Rearrange + LO and HI so the three values are sorted. This lowers the + probability of picking a pathological pivot value and + skips a comparison for both the LEFT_PTR and RIGHT_PTR in + the while loops. */ + + char *mid =3D lo + size * ((hi - lo) / size >> 1); + + if ((*cmp) ((void *) mid, (void *) lo, arg) < 0) + SWAP (mid, lo, size); + if ((*cmp) ((void *) hi, (void *) mid, arg) < 0) + SWAP (mid, hi, size); + else + goto jump_over; + if ((*cmp) ((void *) mid, (void *) lo, arg) < 0) + SWAP (mid, lo, size); + jump_over:; + + left_ptr =3D lo + size; + right_ptr =3D hi - size; + + /* Here's the famous ``collapse the walls'' section of quicksort. + Gotta like those tight inner loops! They are the main reason + that this algorithm runs much faster than others. */ + do + { + while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0) + left_ptr +=3D size; + + while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0) + right_ptr -=3D size; + + if (left_ptr < right_ptr) + { + SWAP (left_ptr, right_ptr, size); + if (mid =3D=3D left_ptr) + mid =3D right_ptr; + else if (mid =3D=3D right_ptr) + mid =3D left_ptr; + left_ptr +=3D size; + right_ptr -=3D size; + } + else if (left_ptr =3D=3D right_ptr) + { + left_ptr +=3D size; + right_ptr -=3D size; + break; + } + } + while (left_ptr <=3D right_ptr); + + /* Set up pointers for next iteration. First determine whethe= r + left and right partitions are below the threshold size. If= so, + ignore one or both. Otherwise, push the larger partition's= + bounds on the stack and continue sorting the smaller one. *= / + + if ((size_t) (right_ptr - lo) <=3D max_thresh) + { + if ((size_t) (hi - left_ptr) <=3D max_thresh) + /* Ignore both small partitions. */ + POP (lo, hi); + else + /* Ignore small left partition. */ + lo =3D left_ptr; + } + else if ((size_t) (hi - left_ptr) <=3D max_thresh) + /* Ignore small right partition. */ + hi =3D right_ptr; + else if ((right_ptr - lo) > (hi - left_ptr)) + { + /* Push larger left partition indices. */ + PUSH (lo, right_ptr); + lo =3D left_ptr; + } + else + { + /* Push larger right partition indices. */ + PUSH (left_ptr, hi); + hi =3D right_ptr; + } + } + } + + /* Once the BASE_PTR array is partially sorted by quicksort the rest + is completely sorted using insertion sort, since this is efficient + for partitions below MAX_THRESH size. BASE_PTR points to the beginn= ing + of the array to sort, and END_PTR points at the very last element i= n + the array (*not* one beyond it!). */ + +#define min(x, y) ((x) < (y) ? (x) : (y)) + + { + char *const end_ptr =3D &base_ptr[size * (total_elems - 1)]; + char *tmp_ptr =3D base_ptr; + char *thresh =3D min(end_ptr, base_ptr + max_thresh); + char *run_ptr; + + /* Find smallest element in first threshold and place it at the + array's beginning. This is the smallest array element, + and the operation speeds up insertion sort's inner loop. */ + + for (run_ptr =3D tmp_ptr + size; run_ptr <=3D thresh; run_ptr +=3D s= ize) + if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0) + tmp_ptr =3D run_ptr; + + if (tmp_ptr !=3D base_ptr) + SWAP (tmp_ptr, base_ptr, size); + + /* Insertion sort, running from left-hand-side up to right-hand-side= =2E */ + + run_ptr =3D base_ptr + size; + while ((run_ptr +=3D size) <=3D end_ptr) + { + tmp_ptr =3D run_ptr - size; + while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0) + tmp_ptr -=3D size; + + tmp_ptr +=3D size; + if (tmp_ptr !=3D run_ptr) + { + char *trav; + + trav =3D run_ptr + size; + while (--trav >=3D run_ptr) + { + char c =3D *trav; + char *hi, *lo; + + for (hi =3D lo =3D trav; (lo -=3D size) >=3D tmp_ptr; hi= =3D lo) + *hi =3D *lo; + *hi =3D c; + } + } + } + } +} =3D=3D=3D added file 'lib/qsort_r.c' --- lib/qsort_r.c 1970-01-01 00:00:00 +0000 +++ lib/qsort_r.c 2014-08-29 20:46:33 +0000 @@ -0,0 +1,51 @@ +/* Reentrant sort function. + + Copyright 2014 Free Software Foundation, Inc. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3, or (at your option) + any later version. + + This program 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 General Public License for more details. + + You should have received a copy of the GNU General Public License alo= ng + with this program; if not, see . */ + +/* Written by Paul Eggert. */ + +#include + +#include + +/* This file is compiled only when the system has a qsort_r that needs + to be replaced because it has the BSD signature rather than the GNU + signature. */ + +struct thunk +{ + int (*cmp) (void const *, void const *, void *); + void *arg; +}; + +static int +thunk_cmp (void *thunk, void const *a, void const *b) +{ + struct thunk *th =3D thunk; + return th->cmp (a, b, th->arg); +} + +void +qsort_r (void *base, size_t nmemb, size_t size, + int (*cmp) (void const *, void const *, void *), + void *arg) +{ +# undef qsort_r + struct thunk thunk; + thunk.cmp =3D cmp; + thunk.arg =3D arg; + qsort_r (base, nmemb, size, &thunk, thunk_cmp); +} =3D=3D=3D modified file 'lib/stdlib.in.h' --- lib/stdlib.in.h 2014-01-01 07:43:34 +0000 +++ lib/stdlib.in.h 2014-08-29 20:46:33 +0000 @@ -520,6 +520,29 @@ _GL_CXXALIASWARN (putenv); #endif =20 +#if @GNULIB_QSORT_R@ +# if @REPLACE_QSORT_R@ +# if !(defined __cplusplus && defined GNULIB_NAMESPACE) +# undef qsort_r +# define qsort_r rpl_qsort_r +# endif +_GL_FUNCDECL_RPL (qsort_r, void, (void *base, size_t nmemb, size_t size,= + int (*compare) (void const *, void con= st *, + void *), + void *arg) _GL_ARG_NONNULL ((1, 4))); +_GL_CXXALIAS_RPL (qsort_r, void, (void *base, size_t nmemb, size_t size,= + int (*compare) (void const *, void con= st *, + void *), + void *arg)); +# else +_GL_CXXALIAS_SYS (qsort_r, void, (void *base, size_t nmemb, size_t size,= + int (*compare) (void const *, void con= st *, + void *), + void *arg)); +# endif +_GL_CXXALIASWARN (qsort_r); +#endif + =20 #if @GNULIB_RANDOM_R@ # if !@HAVE_RANDOM_R@ =3D=3D=3D modified file 'm4/gnulib-comp.m4' --- m4/gnulib-comp.m4 2014-05-17 08:11:31 +0000 +++ m4/gnulib-comp.m4 2014-08-29 20:46:33 +0000 @@ -104,6 +104,7 @@ # Code from module pthread_sigmask: # Code from module putenv: # Code from module qacl: + # Code from module qsort_r: # Code from module readlink: # Code from module readlinkat: # Code from module root-uid: @@ -313,6 +314,13 @@ fi gl_STDLIB_MODULE_INDICATOR([putenv]) gl_FUNC_ACL + gl_FUNC_QSORT_R + if test $HAVE_QSORT_R =3D 0; then + AC_LIBOBJ([qsort]) + elif test $REPLACE_QSORT_R =3D 1; then + AC_LIBOBJ([qsort_r]) + fi + gl_STDLIB_MODULE_INDICATOR([qsort_r]) gl_FUNC_READLINK if test $HAVE_READLINK =3D 0 || test $REPLACE_READLINK =3D 1; then AC_LIBOBJ([readlink]) @@ -865,6 +873,8 @@ lib/putenv.c lib/qcopy-acl.c lib/qset-acl.c + lib/qsort.c + lib/qsort_r.c lib/readlink.c lib/readlinkat.c lib/root-uid.h @@ -972,6 +982,7 @@ m4/pselect.m4 m4/pthread_sigmask.m4 m4/putenv.m4 + m4/qsort_r.m4 m4/readlink.m4 m4/readlinkat.m4 m4/secure_getenv.m4 =3D=3D=3D added file 'm4/qsort_r.m4' --- m4/qsort_r.m4 1970-01-01 00:00:00 +0000 +++ m4/qsort_r.m4 2014-08-29 20:46:33 +0000 @@ -0,0 +1,48 @@ +dnl Reentrant sort function. + +dnl Copyright 2014 Free Software Foundation, Inc. +dnl This file is free software; the Free Software Foundation +dnl gives unlimited permission to copy and/or distribute it, +dnl with or without modifications, as long as this notice is preserved. + +dnl Written by Paul Eggert. + +AC_DEFUN([gl_FUNC_QSORT_R], +[ + dnl Persuade glibc to declare qsort_r. + AC_REQUIRE([gl_USE_SYSTEM_EXTENSIONS]) + + AC_REQUIRE([gl_STDLIB_H_DEFAULTS]) + + AC_CACHE_CHECK([for qsort_r signature], [gl_cv_qsort_r_signature], + [AC_LINK_IFELSE( + [AC_LANG_PROGRAM([[#include + void qsort_r (void *, size_t, size_t, + int (*) (void const *, void cons= t *, + void *), + void *); + void (*p) (void *, size_t, size_t, + int (*) (void const *, void const *= , + void *), + void *) =3D qsort_r; + ]])], + [gl_cv_qsort_r_signature=3DGNU], + [AC_LINK_IFELSE( + [AC_LANG_PROGRAM([[#include + void qsort_r (void *, size_t, size_t, void = *, + int (*) (void *, + void const *, + void const *)); + void (*p) (void *, size_t, size_t, void *, + int (*) (void *, void const *, + void const *)) =3D qsor= t_r; + ]])], + [gl_cv_qsort_r_signature=3DBSD], + [gl_cv_qsort_r_signature=3Dno])])]) + + case $gl_cv_qsort_r_signature in + GNU) HAVE_QSORT_R=3D1;; + BSD) HAVE_QSORT_R=3D1 REPLACE_QSORT_R=3D1;; + *) HAVE_QSORT_R=3D0 REPLACE_QSORT_R=3D1;; + esac +]) =3D=3D=3D modified file 'm4/stdlib_h.m4' --- m4/stdlib_h.m4 2014-01-01 07:43:34 +0000 +++ m4/stdlib_h.m4 2014-08-29 20:46:33 +0000 @@ -55,6 +55,7 @@ GNULIB_PTSNAME=3D0; AC_SUBST([GNULIB_PTSNAME]) GNULIB_PTSNAME_R=3D0; AC_SUBST([GNULIB_PTSNAME_R]) GNULIB_PUTENV=3D0; AC_SUBST([GNULIB_PUTENV]) + GNULIB_QSORT_R=3D0; AC_SUBST([GNULIB_QSORT_R]) GNULIB_RANDOM=3D0; AC_SUBST([GNULIB_RANDOM]) GNULIB_RANDOM_R=3D0; AC_SUBST([GNULIB_RANDOM_R]) GNULIB_REALLOC_POSIX=3D0; AC_SUBST([GNULIB_REALLOC_POSIX]) @@ -107,6 +108,7 @@ REPLACE_PTSNAME=3D0; AC_SUBST([REPLACE_PTSNAME]) REPLACE_PTSNAME_R=3D0; AC_SUBST([REPLACE_PTSNAME_R]) REPLACE_PUTENV=3D0; AC_SUBST([REPLACE_PUTENV]) + REPLACE_QSORT_R=3D0; AC_SUBST([REPLACE_QSORT_R]) REPLACE_RANDOM_R=3D0; AC_SUBST([REPLACE_RANDOM_R]) REPLACE_REALLOC=3D0; AC_SUBST([REPLACE_REALLOC]) REPLACE_REALPATH=3D0; AC_SUBST([REPLACE_REALPATH]) =3D=3D=3D modified file 'src/ChangeLog' --- src/ChangeLog 2014-08-29 20:16:40 +0000 +++ src/ChangeLog 2014-08-29 20:46:33 +0000 @@ -1,5 +1,10 @@ 2014-08-29 Paul Eggert =20 + Modularize qsort_r in Gnulib, to simplify Emacs proper. + * fns.c (sort_vector_predicate) [!HAVE_QSORT_R]: Remove. + (sort_vector_compare, sort_vector): Simplify by assuming GNU qsort_r, + since Gnulib now supplies it. + * sysdep.c (str_collate): Do not look at errno after towlower_l. errno's value is not specified after towlower_l. Instead, assume that towlower_l returns its argument on failure, which is portable =3D=3D=3D modified file 'src/fns.c' --- src/fns.c 2014-08-29 19:18:06 +0000 +++ src/fns.c 2014-08-29 20:46:33 +0000 @@ -1897,42 +1897,24 @@ return merge (front, back, predicate); } =20 -/* Using GNU qsort_r, we can pass this as a parameter. This also - exists on FreeBSD and Darwin/OSX, but with a different signature. */ -#ifndef HAVE_QSORT_R -static Lisp_Object sort_vector_predicate; -#endif - -/* Comparison function called by qsort. */ +/* Comparison function called by qsort_r. */ =20 static int -#ifdef HAVE_QSORT_R -#if defined (DARWIN_OS) || defined (__FreeBSD__) -sort_vector_compare (void *arg, const void *p, const void *q) -#elif defined (GNU_LINUX) sort_vector_compare (const void *p, const void *q, void *arg) -#else /* neither darwin/bsd nor gnu/linux */ -#error "check how qsort_r comparison function works on your platform" -#endif /* DARWIN_OS || __FreeBSD__ */ -#else /* not HAVE_QSORT_R */ -sort_vector_compare (const void *p, const void *q) -#endif /* HAVE_QSORT_R */ { - bool more, less; - Lisp_Object op, oq, vp, vq; -#ifdef HAVE_QSORT_R - Lisp_Object sort_vector_predicate =3D *(Lisp_Object *) arg; -#endif - - op =3D *(Lisp_Object *) p; - oq =3D *(Lisp_Object *) q; - vp =3D XSAVE_OBJECT (op, 1); - vq =3D XSAVE_OBJECT (oq, 1); + Lisp_Object const *ap =3D p; + Lisp_Object const *aq =3D q; + Lisp_Object const *aarg =3D arg; + Lisp_Object op =3D *ap; + Lisp_Object oq =3D *aq; + Lisp_Object sort_vector_predicate =3D *aarg; + Lisp_Object vp =3D XSAVE_OBJECT (op, 1); + Lisp_Object vq =3D XSAVE_OBJECT (oq, 1); =20 /* Use recorded element index as a secondary key to preserve original order. Pretty ugly but works. */ - more =3D NILP (call2 (sort_vector_predicate, vp, vq)); - less =3D NILP (call2 (sort_vector_predicate, vq, vp)); + bool more =3D NILP (call2 (sort_vector_predicate, vp, vq)); + bool less =3D NILP (call2 (sort_vector_predicate, vq, vp)); return ((more && !less) ? 1 : ((!more && less) ? -1 : XSAVE_INTEGER (op, 0) - XSAVE_INTEGER (oq, 0))); @@ -1950,23 +1932,11 @@ =20 if (len < 2) return vector; - /* Record original index of each element to make qsort stable. */ + /* Record original index of each element to make qsort_r stable. */ for (i =3D 0; i < len; i++) v[i] =3D make_save_int_obj (i, v[i]); =20 - /* Setup predicate and sort. */ -#ifdef HAVE_QSORT_R -#if defined (DARWIN_OS) || defined (__FreeBSD__) - qsort_r (v, len, word_size, (void *) &predicate, sort_vector_compare);= -#elif defined (GNU_LINUX) - qsort_r (v, len, word_size, sort_vector_compare, (void *) &predicate);= -#else /* neither darwin/bsd nor gnu/linux */ -#error "check how qsort_r works on your platform" -#endif /* DARWIN_OS || __FreeBSD__ */ -#else /* not HAVE_QSORT_R */ - sort_vector_predicate =3D predicate; - qsort (v, len, word_size, sort_vector_compare); -#endif /* HAVE_QSORT_R */ + qsort_r (v, len, word_size, sort_vector_compare, &predicate); =20 /* Discard indexes and restore original elements. */ for (i =3D 0; i < len; i++) --------------010809080206030708060802-- ------------=_1409417882-29403-1--