[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[commits] r3707 - in /fsf/trunk/libc: ./ localedata/ localedata/locales/ login/ misc/ misc/bits/ stdlib/
- To: commits@xxxxxxxxxx
- Subject: [commits] r3707 - in /fsf/trunk/libc: ./ localedata/ localedata/locales/ login/ misc/ misc/bits/ stdlib/
- From: eglibc@xxxxxxxxxx
- Date: Fri, 05 Oct 2007 07:04:13 -0000
Author: eglibc
Date: Fri Oct 5 00:04:09 2007
New Revision: 3707
Log:
Import glibc-mainline for 2007-10-05
Added:
fsf/trunk/libc/localedata/locales/en_NG
fsf/trunk/libc/misc/bits/error.h
fsf/trunk/libc/stdlib/tst-qsort2.c
Modified:
fsf/trunk/libc/ChangeLog
fsf/trunk/libc/localedata/ChangeLog
fsf/trunk/libc/login/login_tty.c
fsf/trunk/libc/misc/error.h
fsf/trunk/libc/stdlib/Makefile
fsf/trunk/libc/stdlib/msort.c
Modified: fsf/trunk/libc/ChangeLog
==============================================================================
--- fsf/trunk/libc/ChangeLog (original)
+++ fsf/trunk/libc/ChangeLog Fri Oct 5 00:04:09 2007
@@ -1,3 +1,27 @@
+2007-10-04 Jakub Jelinek
+
+ * stdlib/msort.c: Include stdint.h.
+ (struct msort_param): New type.
+ (msort_with_tmp): Use struct msort_param pointer for unchanging
+ parameters. Add optimized handling for several common sizes
+ and indirect sorting mode.
+ (qsort): Adjust msort_with_tmp callers. For big S use indirect
+ sorting.
+ Suggested by Belazougui Djamel .
+
+ * stdlib/Makefile (tests): Add tst-qsort2.
+ * stdlib/tst-qsort2.c: New test.
+
+2007-10-04 Ulrich Drepper <drepper@xxxxxxxxxx>
+
+ * login/login_tty.c (login_tty): The Linux kernel can return EBUSY
+ for dup2 in case another thread races with the current one. Retry
+ in this case.
+
+ * misc/error.h: Remove support for use outside of libc. We have to
+ include <features.h> now. Include <bits/error.h> if possible.
+ * misc/bits/error.h: New file.
+
2007-10-03 Jakub Jelinek
* string/bits/string3.h (memcpy, memmove, mempcpy, memset, bcopy,
Modified: fsf/trunk/libc/localedata/ChangeLog
==============================================================================
--- fsf/trunk/libc/localedata/ChangeLog (original)
+++ fsf/trunk/libc/localedata/ChangeLog Fri Oct 5 00:04:09 2007
@@ -1,3 +1,7 @@
+2007-10-04 Ulrich Drepper <drepper@xxxxxxxxxx>
+
+ * locales/en_NG: New file.
+
2007-10-04 Jakub Jelinek <jakub@xxxxxxxxxx>
* tst-langinfo.sh: Update expected THOUSEP for fr_FR.
Added: fsf/trunk/libc/localedata/locales/en_NG
==============================================================================
--- fsf/trunk/libc/localedata/locales/en_NG (added)
+++ fsf/trunk/libc/localedata/locales/en_NG Fri Oct 5 00:04:09 2007
@@ -1,0 +1,289 @@
+escape_char /
+comment_char %
+
+% English language locale for Nigeria
+% Language: en
+% Territory: NG
+% Revision: 0.2
+% Date: 2006-02-01
+% Users: general
+% Charset: UTF-8
+% Distribution and use is free, also
+% for commercial purposes.
+%
+% adapted from en_ZA; should be checked and verified
+
+LC_IDENTIFICATION
+title "English locale for Nigeria"
+source ""
+address ""
+contact ""
+email ""
+tel ""
+fax ""
+language "English"
+territory "Nigeria"
+revision "0.2"
+date "2006-02-01"
+%
+category "en_NG:2003";LC_IDENTIFICATION
+category "en_NG:2000";LC_CTYPE
+category "en_NG:2000";LC_COLLATE
+category "en_NG:2003";LC_TIME
+category "en_NG:2000";LC_NUMERIC
+category "en_NG:2000";LC_MONETARY
+category "en_NG:2003";LC_MESSAGES
+category "en_NG:2000";LC_PAPER
+category "en_NG:2000";LC_MEASUREMENT
+category "en_NG:2003";LC_NAME
+category "en_NG:2003";LC_ADDRESS
+category "en_NG:2003";LC_TELEPHONE
+
+END LC_IDENTIFICATION
+
+LC_CTYPE
+copy "i18n"
+
+translit_start
+include "translit_combining";""
+translit_end
+END LC_CTYPE
+
+LC_COLLATE
+copy "iso14651_t1"
+END LC_COLLATE
+
+% FIXME
+LC_MONETARY
+% "NGN "
+int_curr_symbol "<U004E><U0047><U004E><U0020>"
+% "₦"
+currency_symbol "<U20A6>"
+% "."
+mon_decimal_point "<U002E>"
+% ","
+mon_thousands_sep "<U002C>"
+mon_grouping 3;3
+positive_sign ""
+% "-"
+negative_sign "<U002D>"
+int_frac_digits 2
+frac_digits 2
+p_cs_precedes 1
+p_sep_by_space 0
+n_cs_precedes 1
+n_sep_by_space 0
+p_sign_posn 1
+n_sign_posn 1
+END LC_MONETARY
+
+% FIXME
+LC_NUMERIC
+% "."
+decimal_point "<U002E>"
+% ","
+thousands_sep "<U002C>"
+grouping 3;3
+END LC_NUMERIC
+
+LC_TIME
+% abday - The abbreviations for the week days:
+% - Sun, Mon, Tue, Wed, Thu, Fri, Sat
+abday "<U0053><U0075><U006E>";"<U004D><U006F><U006E>";/
+ "<U0054><U0075><U0065>";"<U0057><U0065><U0064>";/
+ "<U0054><U0068><U0075>";"<U0046><U0072><U0069>";/
+ "<U0053><U0061><U0074>"
+
+% day - The full names of the week days:
+% - Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday
+day "<U0053><U0075><U006E><U0064><U0061><U0079>";/
+ "<U004D><U006F><U006E><U0064><U0061><U0079>";/
+ "<U0054><U0075><U0065><U0073><U0064><U0061><U0079>";/
+ "<U0057><U0065><U0064><U006E><U0065><U0073><U0064><U0061><U0079>";/
+ "<U0054><U0068><U0075><U0072><U0073><U0064><U0061><U0079>";/
+ "<U0046><U0072><U0069><U0064><U0061><U0079>";/
+ "<U0053><U0061><U0074><U0075><U0072><U0064><U0061><U0079>"
+
+% abmon - The abbreviations for the months
+% - Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec
+abmon "<U004A><U0061><U006E>";"<U0046><U0065><U0062>";/
+ "<U004D><U0061><U0072>";"<U0041><U0070><U0072>";/
+ "<U004D><U0061><U0079>";"<U004A><U0075><U006E>";/
+ "<U004A><U0075><U006C>";"<U0041><U0075><U0067>";/
+ "<U0053><U0065><U0070>";"<U004F><U0063><U0074>";/
+ "<U004E><U006F><U0076>";"<U0044><U0065><U0063>"
+
+% mon - The full names of the months -
+% - January, February, March, April, May, June
+% July, August, September, October, November, December
+mon "<U004A><U0061><U006E><U0075><U0061><U0072><U0079>";/
+ "<U0046><U0065><U0062><U0072><U0075><U0061><U0072><U0079>";/
+ "<U004D><U0061><U0072><U0063><U0068>";/
+ "<U0041><U0070><U0072><U0069><U006C>";/
+ "<U004D><U0061><U0079>";/
+ "<U004A><U0075><U006E><U0065>";/
+ "<U004A><U0075><U006C><U0079>";/
+ "<U0041><U0075><U0067><U0075><U0073><U0074>";/
+ "<U0053><U0065><U0070><U0074><U0065><U006D><U0062><U0065><U0072>";/
+ "<U004F><U0063><U0074><U006F><U0062><U0065><U0072>";/
+ "<U004E><U006F><U0076><U0065><U006D><U0062><U0065><U0072>";/
+ "<U0044><U0065><U0063><U0065><U006D><U0062><U0065><U0072>"
+
+% Abreviated date and time representation to be referenced by the "%c" field descriptor -
+%
+% "%a" (short weekday name),
+% "%d" (day of month as a decimal number),
+% "%b" (short month name),
+% "%Y" (year with century as a decimal number),
+% "%T" (24-hour clock time in format HH:MM:SS),
+% "%Z" (Time zone name)
+d_t_fmt "<U0025><U0061><U0020><U0025><U0064><U0020><U0025><U0062><U0020><U0025><U0059><U0020><U0025><U0054><U0020><U0025><U005A>"
+
+% Date representation to be referenced by the "%x" field descriptor -
+% "%d/%m/%Y", day/month/year as decimal numbers (01/01/2000).
+d_fmt "<U0025><U0064><U002F><U0025><U006D><U002F><U0025><U0059>"
+
+% Time representation to be referenced by the "%X" field descriptor -
+% "%T" (24-hour clock time in format HH:MM:SS)
+t_fmt "<U0025><U0054>"
+
+% Define representation of ante meridiem and post meridiem strings -
+% The "" mean default to "AM" and "PM".
+am_pm "";""
+
+% Define time representation in 12-hour format with "am_pm", to be referenced by the "%r"
+% The "" means that this format is not supported.
+t_fmt_ampm ""
+
+% Date representation not described in ISO/IEC 14652. Comes out as -
+% "%a %b %e %H:%M:%S %Z %Y" which is default "date" command output
+%
+% %a - abbreviated weekday name,
+% %b - abreviated month name,
+% %e - day of month as a decimal number with leading space (1 to 31),
+% %H - hour (24-hour clock) as a decimal number (00 to 23),
+% %M - minute as a decimal number (00 to 59),
+% %S - seconds as a decimal number (00 to 59),
+% %Z - time-zone name,
+% %Y - year with century as a decimal number,e.g. 2001.
+date_fmt "<U0025><U0061><U0020><U0025><U0062><U0020><U0025><U0065>/
+<U0020><U0025><U0048><U003A><U0025><U004D><U003A><U0025><U0053><U0020>/
+<U0025><U005A><U0020><U0025><U0059>"
+END LC_TIME
+
+LC_MESSAGES
+% The affirmative response -
+% "^[yY]"
+yesexpr "<U005E><U005B><U0079><U0059><U005D>"
+
+% The negative response -
+% "^[nN]"
+noexpr "<U005E><U005B><U006E><U004E><U005D>"
+END LC_MESSAGES
+
+LC_PAPER
+copy "en_DK"
+END LC_PAPER
+
+% FIXME
+LC_TELEPHONE
+% Representation of telephone number for international use -
+% "+%c %a %l", which is
+% "+%c - country code",
+% "%a - area code without the prefix (often 0)",
+% "%l local number".
+tel_int_fmt "<U002B><U0025><U0063><U0020><U0025><U0061><U0020><U0025>/
+<U006C>"
+
+% Represntation of telephone number for domestic use -
+% "(%A) %l", which is
+% %A - area code with national prefix
+% %l - local number".
+tel_dom_fmt "<U0028><U0025><U0041><U0029><U0020><U0025><U006C>"
+
+% Prefix for making international calls
+% "009"
+int_select "<U0030><U0030><U0039>"
+
+% International dialing code
+% "234"
+int_prefix "<U0032><U0033><U0034>"
+END LC_TELEPHONE
+
+LC_MEASUREMENT
+copy "en_DK"
+END LC_MEASUREMENT
+
+LC_NAME
+copy "en_DK"
+END LC_NAME
+
+% FIXME
+LC_ADDRESS
+% Representation of postal addresses (minus the addressee's name) in South
+% Africa. (Ignored for now)
+% "%f%N%a%N%d%N%b%N%s %h %e %r%N%%z %T%N%c%N", which gives -
+%
+% "firm name",
+% "end of line",
+% "C/O address",
+% "end of line",
+% "department name",
+% "Building name",
+% "end of line",
+% "street or block name",
+% "space",
+% "house number or designation",
+% "space",
+% "floor number",
+% "space",
+% "room number, door designation",
+% "end of line",
+% "postal code",
+% "space",
+% "town, city",
+% "end of line",
+% "country designation for the <country_post> keyword",
+% "end of line
+postal_fmt "<U0025><U0066><U0025><U004E><U0025><U0061><U0025><U004E>/
+<U0025><U0064><U0025><U004E><U0025><U0062><U0025><U004E><U0025><U0073>/
+<U0020><U0025><U0068><U0020><U0025><U0065><U0020><U0025><U0072><U0025>/
+<U004E><U0025><U0025><U007A><U0020><U0025><U0054><U0025>/
+<U004E><U0025><U0063><U0025><U004E>"
+
+% Country name in English - "Nigeria"
+country_name "<U004E><U0069><U0067><U0065><U0072><U0069><U0061>"
+
+% Language name in English - "English"
+lang_name "<U0045><U006E><U0067><U006C><U0069><U0073><U0068>"
+
+% CEPT MAILCODES are suggested
+% Alternatively use the code found on your countries postal item tracking number
+% "NG"?
+%country_post "<U004E><U0047>"
+
+% UN Geneve 1949:68 Distinguishing signs of vehicles in international traffic
+% http://www.unece.org/trans/conventn/Distsigns_Sept2003.pdf
+% "WAN"
+country_car "<U0057><U0041><U004E>"
+
+% ISO 2108
+% http://www.isbn-international.org/
+country_isbn 978
+
+% ISO 639 language abbreviations:
+% 639-1 2 letter, 639-2 3 letter terminology
+% http://www.loc.gov/standards/iso639-2/englagn.html
+% "en", "eng"
+lang_ab "<U0065><U006E>"
+lang_term "<U0065><U006E><U0067>"
+lang_lib "<U0065><U006E><U0067>"
+
+% ISO 3166 country number and 2 and 3 letter abreviations
+% http://www.unicode.org/onlinedat/countries.html
+% "NG", "NGA"
+country_ab2 "<U004E><U0047>"
+country_ab3 "<U004E><U0047><U0041>"
+country_num 566
+
+END LC_ADDRESS
Modified: fsf/trunk/libc/login/login_tty.c
==============================================================================
--- fsf/trunk/libc/login/login_tty.c (original)
+++ fsf/trunk/libc/login/login_tty.c Fri Oct 5 00:04:09 2007
@@ -31,6 +31,7 @@
static char sccsid[] = "@(#)login_tty.c 8.1 (Berkeley) 6/4/93";
#endif /* LIBC_SCCS and not lint */
+#include <errno.h>
#include <sys/param.h>
#include <sys/ioctl.h>
#include <unistd.h>
@@ -63,9 +64,12 @@
}
}
#endif
- (void) dup2(fd, 0);
- (void) dup2(fd, 1);
- (void) dup2(fd, 2);
+ while (dup2(fd, 0) == -1 && errno == EBUSY)
+ ;
+ while (dup2(fd, 1) == -1 && errno == EBUSY)
+ ;
+ while (dup2(fd, 2) == -1 && errno == EBUSY)
+ ;
if (fd > 2)
(void) close(fd);
return (0);
Added: fsf/trunk/libc/misc/bits/error.h
==============================================================================
--- fsf/trunk/libc/misc/bits/error.h (added)
+++ fsf/trunk/libc/misc/bits/error.h Fri Oct 5 00:04:09 2007
@@ -1,0 +1,72 @@
+/* Specializations for error functions.
+ Copyright (C) 2007 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ 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, write to the Free
+ Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+ 02111-1307 USA. */
+
+#ifndef _ERROR_H
+# error "Never include <bits/error.h> directly; use <error.h> instead."
+#endif
+
+
+extern void __REDIRECT (__error_alias, (int __status, int __errnum,
+ const char *__format, ...),
+ error)
+ __attribute__ ((__format__ (__printf__, 3, 4)));
+extern void __REDIRECT (__error_noreturn, (int __status, int __errnum,
+ const char *__format, ...),
+ error)
+ __attribute__ ((__noreturn__, __format__ (__printf__, 3, 4)));
+
+
+/* If we know the function will never return make sure the compiler
+ realizes that, too. */
+__extern_always_inline void
+error (int __status, int __errnum, const char *__format, ...)
+{
+ if (__builtin_constant_p (__status) && __status != 0)
+ __error_noreturn (__status, __errnum, __format, __va_arg_pack ());
+ else
+ __error_alias (__status, __errnum, __format, __va_arg_pack ());
+}
+
+
+extern void __REDIRECT (__error_at_line_alias, (int __status, int __errnum,
+ const char *__fname,
+ unsigned int __line,
+ const char *__format, ...),
+ error_at_line)
+ __attribute__ ((__format__ (__printf__, 5, 6)));
+extern void __REDIRECT (__error_at_line_noreturn, (int __status, int __errnum,
+ const char *__fname,
+ unsigned int __line,
+ const char *__format, ...),
+ error_at_line)
+ __attribute__ ((__noreturn__, __format__ (__printf__, 5, 6)));
+
+
+/* If we know the function will never return make sure the compiler
+ realizes that, too. */
+__extern_always_inline void
+error_at_line (int __status, int __errnum, const char *__format, ...)
+{
+ if (__builtin_constant_p (__status) && __status != 0)
+ __error_at_line_noreturn (__status, __errnum, __fname, __line, __format,
+ __va_arg_pack ());
+ else
+ __error_at_line_alias (__status, __errnum, __fname, __line,
+ __format, __va_arg_pack ());
+}
Modified: fsf/trunk/libc/misc/error.h
==============================================================================
--- fsf/trunk/libc/misc/error.h (original)
+++ fsf/trunk/libc/misc/error.h Fri Oct 5 00:04:09 2007
@@ -1,5 +1,5 @@
/* Declaration for error-reporting function
- Copyright (C) 1995, 1996, 1997, 2003, 2006 Free Software Foundation, Inc.
+ Copyright (C) 1995,1996,1997,2003,2006,2007 Free Software Foundation, Inc.
This file is part of the GNU C Library.
The GNU C Library is free software; you can redistribute it and/or
@@ -20,22 +20,10 @@
#ifndef _ERROR_H
#define _ERROR_H 1
-#ifndef __attribute__
-/* This feature is available in gcc versions 2.5 and later. */
-# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 5) || __STRICT_ANSI__
-# define __attribute__(Spec) /* empty */
-# endif
-/* The __-protected variants of `format' and `printf' attributes
- are accepted by gcc versions 2.6.4 (effectively 2.7) and later. */
-# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 7)
-# define __format__ format
-# define __printf__ printf
-# endif
-#endif
+#include <features.h>
-#ifdef __cplusplus
-extern "C" {
-#endif
+
+__BEGIN_DECLS
/* Print a message with `fprintf (stderr, FORMAT, ...)';
if ERRNUM is nonzero, follow it with ": " and strerror (ERRNUM).
@@ -60,8 +48,11 @@
variable controls whether this mode is selected or not. */
extern int error_one_per_line;
-#ifdef __cplusplus
-}
+
+#if defined __extern_always_inline && defined __va_arg_pack
+# include <bits/error.h>
#endif
+__END_DECLS
+
#endif /* error.h */
Modified: fsf/trunk/libc/stdlib/Makefile
==============================================================================
--- fsf/trunk/libc/stdlib/Makefile (original)
+++ fsf/trunk/libc/stdlib/Makefile Fri Oct 5 00:04:09 2007
@@ -68,7 +68,7 @@
tst-limits tst-rand48 bug-strtod tst-setcontext \
test-a64l tst-qsort tst-system testmb2 bug-strtod2 \
tst-atof1 tst-atof2 tst-strtod2 tst-strtod3 tst-rand48-2 \
- tst-makecontext tst-strtod4 tst-strtod5
+ tst-makecontext tst-strtod4 tst-strtod5 tst-qsort2
include ../Makeconfig
Modified: fsf/trunk/libc/stdlib/msort.c
==============================================================================
--- fsf/trunk/libc/stdlib/msort.c (original)
+++ fsf/trunk/libc/stdlib/msort.c Fri Oct 5 00:04:09 2007
@@ -1,6 +1,6 @@
/* An alternative to qsort, with an identical interface.
This file is part of the GNU C Library.
- Copyright (C) 1992,95-97,99,2000,01,02,04 Free Software Foundation, Inc.
+ Copyright (C) 1992,95-97,99,2000,01,02,04,07 Free Software Foundation, Inc.
Written by Mike Haertel, September 1988.
The GNU C Library is free software; you can redistribute it and/or
@@ -19,20 +19,25 @@
02111-1307 USA. */
#include <alloca.h>
+#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <memcopy.h>
#include <errno.h>
-static void msort_with_tmp (void *b, size_t n, size_t s,
- __compar_fn_t cmp, char *t);
+struct msort_param
+{
+ size_t s;
+ size_t var;
+ __compar_fn_t cmp;
+ char *t;
+};
+static void msort_with_tmp (const struct msort_param *p, void *b, size_t n);
static void
-msort_with_tmp (void *b, size_t n, size_t s, __compar_fn_t cmp,
- char *t)
+msort_with_tmp (const struct msort_param *p, void *b, size_t n)
{
- char *tmp;
char *b1, *b2;
size_t n1, n2;
@@ -42,65 +47,131 @@
n1 = n / 2;
n2 = n - n1;
b1 = b;
- b2 = (char *) b + (n1 * s);
-
- msort_with_tmp (b1, n1, s, cmp, t);
- msort_with_tmp (b2, n2, s, cmp, t);
-
- tmp = t;
-
- if (s == OPSIZ && (b1 - (char *) 0) % OPSIZ == 0)
- /* We are operating on aligned words. Use direct word stores. */
- while (n1 > 0 && n2 > 0)
- {
- if ((*cmp) (b1, b2) <= 0)
- {
- --n1;
- *((op_t *) tmp) = *((op_t *) b1);
- tmp += sizeof (op_t);
- b1 += sizeof (op_t);
- }
- else
- {
- --n2;
- *((op_t *) tmp) = *((op_t *) b2);
- tmp += sizeof (op_t);
- b2 += sizeof (op_t);
- }
- }
- else
- while (n1 > 0 && n2 > 0)
- {
- if ((*cmp) (b1, b2) <= 0)
- {
- tmp = (char *) __mempcpy (tmp, b1, s);
- b1 += s;
- --n1;
- }
- else
- {
- tmp = (char *) __mempcpy (tmp, b2, s);
- b2 += s;
- --n2;
- }
- }
+ 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_fn_t cmp = p->cmp;
+ switch (p->var)
+ {
+ case 0:
+ while (n1 > 0 && n2 > 0)
+ {
+ if ((*cmp) (b1, b2) <= 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) <= 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) <= 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) <= 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) <= 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, t, (n - n2) * s);
+ memcpy (b, p->t, (n - n2) * s);
}
void
qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
{
- const size_t size = n * s;
+ 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)
- {
- void *buf = __alloca (size);
-
- /* The temporary array is small, so put it on the stack. */
- msort_with_tmp (b, n, s, cmp, buf);
- }
+ /* 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
@@ -135,26 +206,89 @@
/* If the memory requirements are too high don't allocate memory. */
if (size / pagesize > (size_t) phys_pages)
- _quicksort (b, n, s, cmp);
- else
- {
- /* It's somewhat large, so malloc it. */
- int save = errno;
- char *tmp = malloc (size);
- if (tmp == NULL)
- {
- /* Couldn't get space, so use the slower algorithm
- that doesn't need a temporary array. */
- __set_errno (save);
- _quicksort (b, n, s, cmp);
- }
- else
- {
- __set_errno (save);
- msort_with_tmp (b, n, s, cmp, tmp);
- free (tmp);
- }
- }
- }
+ {
+ _quicksort (b, n, s, cmp);
+ 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);
+ return;
+ }
+ p.t = tmp;
+ }
+
+ p.s = s;
+ p.cmp = cmp;
+ p.var = 4;
+
+ 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)
Added: fsf/trunk/libc/stdlib/tst-qsort2.c
==============================================================================
--- fsf/trunk/libc/stdlib/tst-qsort2.c (added)
+++ fsf/trunk/libc/stdlib/tst-qsort2.c Fri Oct 5 00:04:09 2007
@@ -1,0 +1,89 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+char *array;
+char *array_end;
+size_t member_size;
+
+int
+compare (const void *a1, const void *b1)
+{
+ const char *a = a1;
+ const char *b = b1;
+
+ if (! (array <= a && a < array_end
+ && array <= b && b < array_end))
+ {
+ puts ("compare arguments not inside of the array");
+ exit (EXIT_FAILURE);
+ }
+ int ret = b[0] - a[0];
+ if (ret)
+ return ret;
+ if (member_size > 1)
+ return b[1] - a[1];
+ return 0;
+}
+
+int
+test (size_t nmemb, size_t size)
+{
+ array = malloc (nmemb * size);
+ if (array == NULL)
+ {
+ printf ("%zd x %zd: no memory", nmemb, size);
+ return 1;
+ }
+
+ array_end = array + nmemb * size;
+ member_size = size;
+
+ char *p;
+ size_t i;
+ size_t bias = random ();
+ for (i = 0, p = array; i < nmemb; i++, p += size)
+ {
+ p[0] = (char) (i + bias);
+ if (size > 1)
+ p[1] = (char) ((i + bias) >> 8);
+ }
+
+ qsort (array, nmemb, size, compare);
+
+ for (i = 0, p = array; i < nmemb - 1; i++, p += size)
+ {
+ if (p[0] < p[size]
+ || (size > 1 && p[0] == p[size] && p[1] < p[size + 1]))
+ {
+ printf ("%zd x %zd: failure at offset %zd\n", nmemb,
+ size, i);
+ free (array);
+ return 1;
+ }
+ }
+
+ free (array);
+ return 0;
+}
+
+int
+main (int argc, char **argv)
+{
+ int ret = 0;
+ if (argc >= 2)
+ ret |= test (atoi (argv[1]), atoi (argv[2]));
+ else
+ {
+ ret |= test (10000, 1);
+ ret |= test (200000, 2);
+ ret |= test (2000000, 3);
+ ret |= test (2132310, 4);
+ ret |= test (1202730, 7);
+ ret |= test (1184710, 8);
+ ret |= test (272710, 12);
+ ret |= test (14170, 32);
+ ret |= test (4170, 320);
+ }
+
+ return ret;
+}