diff options
| -rw-r--r-- | ChangeLog | 11 | ||||
| -rw-r--r-- | localedata/ChangeLog | 4 | ||||
| -rw-r--r-- | localedata/charmaps/MACINTOSH | 6 | ||||
| -rw-r--r-- | manual/syslog.texi | 64 | ||||
| -rw-r--r-- | stdlib/msort.c | 408 |
5 files changed, 431 insertions, 62 deletions
diff --git a/ChangeLog b/ChangeLog index 697db4d62b..1072bf9dce 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,16 @@ +2002-01-16 Roger Sayle <roger@eyesopen.com> + + * stdlib/msort.c (msort_with_tmp): Replace implementation with + more efficient "Towers of Hanoi" mergesort. + (hanoi_sort, hanoi_sort_int, hanoi_sort_long): New functions, + for generic, sizeof(int) and sizeof(long) variants respectively. + 2002-01-17 Ulrich Drepper <drepper@redhat.com> + * manial/syslog.texi (openlog): Describe possible problems with + first parameter. + Patch by Christopher Allen Wing <wingc@engin.umich.edu>. + * nscd/nscd.c (drop_privileges): Removed. Adjust caller. * nscd/connections.c (begin_drop_privileges): New function. (finish_drop_privileges): New function. diff --git a/localedata/ChangeLog b/localedata/ChangeLog index 9b7f62fe95..bfde824eda 100644 --- a/localedata/ChangeLog +++ b/localedata/ChangeLog @@ -1,3 +1,7 @@ +2002-01-17 Ulrich Drepper <drepper@redhat.com> + + * charmaps/MACINTOSH: Update to Apple's latest definition. + 2002-01-16 Ulrich Drepper <drepper@redhat.com> * charmaps/GB18030: Update. diff --git a/localedata/charmaps/MACINTOSH b/localedata/charmaps/MACINTOSH index 336f720913..b826dc944f 100644 --- a/localedata/charmaps/MACINTOSH +++ b/localedata/charmaps/MACINTOSH @@ -211,7 +211,7 @@ CHARMAP <U00A0> /xca NO-BREAK SPACE <U00C0> /xcb LATIN CAPITAL LETTER A WITH GRAVE <U00C3> /xcc LATIN CAPITAL LETTER A WITH TILDE -<U2126> /xcd OHM SIGN +<U00D5> /xcd LATIN CAPITAL LETTER O WITH TILDE <U0152> /xce LATIN CAPITAL LIGATURE OE <U0153> /xcf LATIN SMALL LIGATURE OE <U2013> /xd0 EN DASH @@ -225,7 +225,7 @@ CHARMAP <U00FF> /xd8 LATIN SMALL LETTER Y WITH DIAERESIS <U0178> /xd9 LATIN CAPITAL LETTER Y WITH DIAERESIS <U2044> /xda FRACTION SLASH -<U00A4> /xdb CURRENCY SIGN +<U20AC> /xdb EURO SIGN <U2039> /xdc SINGLE LEFT-POINTING ANGLE QUOTATION MARK <U203A> /xdd SINGLE RIGHT-POINTING ANGLE QUOTATION MARK <UFB01> /xde LATIN SMALL LIGATURE FI @@ -252,6 +252,8 @@ CHARMAP <U00DB> /xf3 LATIN CAPITAL LETTER U WITH CIRCUMFLEX <U00D9> /xf4 LATIN CAPITAL LETTER U WITH GRAVE <U0131> /xf5 LATIN SMALL LETTER DOTLESS I +<U02C6> /xf6 MODIFIER LETTER CIRCUMFLEX ACCENT +<U02DC> /xf7 SMALL TILDE <U00AF> /xf8 MACRON <U02D8> /xf9 BREVE <U02D9> /xfa DOT ABOVE (Mandarin Chinese light tone) diff --git a/manual/syslog.texi b/manual/syslog.texi index 49f599d93f..df4179e27a 100644 --- a/manual/syslog.texi +++ b/manual/syslog.texi @@ -146,8 +146,7 @@ The symbols referred to in this section are declared in the file @comment syslog.h @comment BSD -@deftypefun void openlog (char *@var{ident}, int @var{option}, - int @var{facility}) +@deftypefun void openlog (const char *@var{ident}, int @var{option}, int @var{facility}) @code{openlog} opens or reopens a connection to Syslog in preparation for submitting messages. @@ -157,6 +156,46 @@ for submitting messages. to identify the source of the message, and people conventionally set it to the name of the program that will submit the messages. +If @var{ident} is NULL, or if @code{openlog} is not called, the default +identification string used in Syslog messages will be the program name, +taken from argv[0]. + +Please note that the string pointer @var{ident} will be retained +internally by the Syslog routines. You must not free the memory that +@var{ident} points to. It is also dangerous to pass a reference to an +automatic variable since leaving the scope would mean ending the +lifetime of the variable. If you want to change the @var{ident} string, +you must call @code{openlog} again; overwriting the string pointed to by +@var{ident} is not thread-safe. + +You can cause the Syslog routines to drop the reference to @var{ident} and +go back to the default string (the program name taken from argv[0]), by +calling @code{closelog}: @xref{closelog}. + +In particular, if you are writing code for a shared library that might get +loaded and then unloaded (e.g. a PAM module), and you use @code{openlog}, +you must call @code{closelog} before any point where your library might +get unloaded, as in this example: + +@smallexample +#include <syslog.h> + +void +shared_library_function (void) +@{ + openlog ("mylibrary", option, priority); + + syslog (LOG_INFO, "shared library has been invoked"); + + closelog (); +@} +@end smallexample + +Without the call to @code{closelog}, future invocations of @code{syslog} +by the program using the shared library may crash, if the library gets +unloaded and the memory containing the string @code{"mylibrary"} becomes +unmapped. This is a limitation of the BSD syslog interface. + @code{openlog} may or may not open the @file{/dev/log} socket, depending on @var{option}. If it does, it tries to open it and connect it as a stream socket. If that doesn't work, it tries to open it and connect it @@ -383,12 +422,21 @@ The symbols referred to in this section are declared in the file @deftypefun void closelog (void) @code{closelog} closes the current Syslog connection, if there is one. -This include closing the @file{dev/log} socket, if it is open. - -There is very little reason to use this function. It does not flush any -buffers; you can reopen a Syslog connection without closing it first; -The connection gets closed automatically on exec or exit. -@code{closelog} has primarily aesthetic value. +This includes closing the @file{dev/log} socket, if it is open. +@code{closelog} also sets the identification string for Syslog messages +back to the default, if @code{openlog} was called with a non-NULL argument +to @var{ident}. The default identification string is the program name +taken from argv[0]. + +If you are writing shared library code that uses @code{openlog} to +generate custom syslog output, you should use @code{closelog} to drop the +GNU C library's internal reference to the @var{ident} pointer when you are +done. Please read the section on @code{openlog} for more information: +@xref{openlog}. + +@code{closelog} does not flush any buffers. You do not have to call +@code{closelog} before re-opening a Syslog connection with @code{initlog}. +Syslog connections are automatically closed on exec or exit. @end deftypefun diff --git a/stdlib/msort.c b/stdlib/msort.c index 3668370cd5..7d21c10fc9 100644 --- a/stdlib/msort.c +++ b/stdlib/msort.c @@ -1,7 +1,9 @@ /* An alternative to qsort, with an identical interface. This file is part of the GNU C Library. - Copyright (C) 1992, 1995-1997, 1999, 2000, 2001 Free Software Foundation, Inc. - Written by Mike Haertel, September 1988. + Copyright (C) 1992, 1995-1997, 1999, 2000, 2001, 2002 + Free Software Foundation, Inc. + Original Implementation by Mike Haertel, September 1988. + Towers of Hanoi Mergesort by Roger Sayle, January 2002. The GNU C Library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public @@ -19,70 +21,372 @@ 02111-1307 USA. */ #include <alloca.h> +#include <limits.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #include <memcopy.h> #include <errno.h> + +/* Check whether pointer P is aligned for access by type T. */ +#define TYPE_ALIGNED(P,T) (((char *) (P) - (char *) 0) % __alignof__ (T) == 0) + + +static int hanoi_sort (char *b, size_t n, size_t s, + __compar_fn_t cmp, char *t); +static int hanoi_sort_int (int *b, size_t n, + __compar_fn_t cmp, int *t); +#if INT_MAX != LONG_MAX +static int hanoi_sort_long (long int *b, size_t n, + __compar_fn_t cmp, long int *t); +#endif static void msort_with_tmp (void *b, size_t n, size_t s, - __compar_fn_t cmp, char *t); + __compar_fn_t cmp, void *t); -static void -msort_with_tmp (void *b, size_t n, size_t s, __compar_fn_t cmp, - char *t) + +/* This routine implements "Towers of Hanoi Mergesort". The algorithm + sorts the n elements of size s pointed to by array b using comparison + function cmp. The argument t points to a suitable temporary buffer. + If the return value is zero, the sorted array is returned in b, and + for non-zero return values the sorted array is returned in t. */ +static int +hanoi_sort (char *b, size_t n, size_t s, __compar_fn_t cmp, char *t) { - char *tmp; - char *b1, *b2; size_t n1, n2; + char *b1,*b2; + char *t1,*t2; + char *s1,*s2; + size_t size; + int result; + char *ptr; if (n <= 1) - return; + return 0; - n1 = n / 2; + if (n == 2) + { + b2 = b + s; + if ((*cmp) (b, b2) <= 0) + return 0; + memcpy (__mempcpy (t, b2, s), b, s); + return 1; + } + + n1 = n/2; n2 = n - n1; + /* n1 < n2! */ + + size = n1 * s; 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)++; - } - else - { - --n2; - *((op_t *) tmp)++ = *((op_t *) b2)++; - } - } + b2 = b + size; + + t1 = t; + t2 = t + size; + + /* Recursively call hanoi_sort to sort the two halves of the array. + Depending upon the return values, determine the values s1 and s2 + the locations of the two sorted subarrays, ptr, the location to + contain the sorted array and result, the return value for this + function. Note that "ptr = result? t : b". */ + if (hanoi_sort (b1, n1, s, cmp, t1)) + { + if (hanoi_sort (b2, n2, s, cmp, t2)) + { + result = 0; + ptr = b; + s1 = t1; + s2 = t2; + } + else + { + result = 0; + ptr = b; + s1 = t1; + s2 = b2; + } + } 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; - } - } - if (n1 > 0) - memcpy (tmp, b1, n1 * s); - memcpy (b, t, (n - n2) * s); + { + if (hanoi_sort (b2, n2, s, cmp, t2)) + { + result = 1; + ptr = t; + s1 = b1; + s2 = t2; + } + else + { + result = 1; + ptr = t; + s1 = b1; + s2 = b2; + } + } + + /* Merge the two sorted arrays s1 and s2 of n1 and n2 elements + respectively, placing the result in ptr. On entry, n1 > 0 + && n2 > 0, and with each iteration either n1 or n2 is decreased + until either reaches zero, and the loop terminates via return. */ + for (;;) + { + if ((*cmp) (s1, s2) <= 0) + { + ptr = (char *) __mempcpy (ptr, s1, s); + s1 += s; + --n1; + if (n1 == 0) + { + if (ptr != s2) + memcpy (ptr, s2, n2 * s); + return result; + } + } + else + { + ptr = (char *) __mempcpy (ptr, s2, s); + s2 += s; + --n2; + if (n2 == 0) + { + memcpy (ptr, s1, n1 * s); + return result; + } + } + } +} + + +/* This routine is a variant of hanoi_sort that is optimized for the + case where items to be sorted are the size of ints, and both b and + t are suitably aligned. The parameter s in not needed as it is + known to be sizeof(int). */ +static int +hanoi_sort_int (int *b, size_t n, __compar_fn_t cmp, int *t) +{ + size_t n1, n2; + int *b1,*b2; + int *t1,*t2; + int *s1,*s2; + int result; + int *ptr; + + if (n <= 1) + return 0; + + if (n == 2) + { + if ((*cmp) (b, b + 1) <= 0) + return 0; + t[0] = b[1]; + t[1] = b[0]; + return 1; + } + + n1 = n/2; + n2 = n - n1; + /* n1 < n2! */ + + b1 = b; + b2 = b + n1; + + t1 = t; + t2 = t + n1; + + /* Recursively call hanoi_sort_int to sort the two halves. */ + if (hanoi_sort_int (b1, n1, cmp, t1)) + { + if (hanoi_sort_int (b2, n2, cmp, t2)) + { + result = 0; + ptr = b; + s1 = t1; + s2 = t2; + } + else + { + result = 0; + ptr = b; + s1 = t1; + s2 = b2; + } + } + else + { + if (hanoi_sort_int (b2, n2, cmp, t2)) + { + result = 1; + ptr = t; + s1 = b1; + s2 = t2; + } + else + { + result = 1; + ptr = t; + s1 = b1; + s2 = b2; + } + } + + /* Merge n1 elements from s1 and n2 elements from s2 into ptr. */ + for (;;) + { + if ((*cmp) (s1, s2) <= 0) + { + *ptr++ = *s1++; + --n1; + if (n1 == 0) + { + if (ptr != s2) + memcpy (ptr, s2, n2 * sizeof (int)); + return result; + } + } + else + { + *ptr++ = *s2++; + --n2; + if (n2 == 0) + { + memcpy (ptr, s1, n1 * sizeof (int)); + return result; + } + } + } +} + + +#if INT_MAX != LONG_MAX +/* This routine is a variant of hanoi_sort that is optimized for the + case where items to be sorted are the size of longs, and both b and + t are suitably aligned. The parameter s in not needed as it is + known to be sizeof(long). In case sizeof(int)== sizeof(long) we + do not need this code since it would be the same as hanoi_sort_int. */ +static int +hanoi_sort_long (long int *b, size_t n, __compar_fn_t cmp, long int *t) +{ + size_t n1, n2; + long int *b1,*b2; + long int *t1,*t2; + long int *s1,*s2; + int result; + long int *ptr; + + if (n <= 1) + return 0; + + if (n == 2) + { + if ((*cmp) (b, b + 1) <= 0) + return 0; + t[0] = b[1]; + t[1] = b[0]; + return 1; + } + + n1 = n/2; + n2 = n - n1; + /* n1 < n2! */ + + b1 = b; + b2 = b + n1; + + t1 = t; + t2 = t + n1; + + /* Recursively call hanoi_sort_long to sort the two halves. */ + if (hanoi_sort_long (b1, n1, cmp, t1)) + { + if (hanoi_sort_long (b2, n2, cmp, t2)) + { + result = 0; + ptr = b; + s1 = t1; + s2 = t2; + } + else + { + result = 0; + ptr = b; + s1 = t1; + s2 = b2; + } + } + else + { + if (hanoi_sort_long (b2, n2, cmp, t2)) + { + result = 1; + ptr = t; + s1 = b1; + s2 = t2; + } + else + { + result = 1; + ptr = t; + s1 = b1; + s2 = b2; + } + } + + /* Merge n1 elements from s1 and n2 elements from s2 into ptr. */ + for (;;) + { + if ((*cmp) (s1, s2) <= 0) + { + *ptr++ = *s1++; + --n1; + if (n1 == 0) + { + if (ptr != s2) + memcpy (ptr, s2, n2 * sizeof (long)); + return result; + } + } + else + { + *ptr++ = *s2++; + --n2; + if (n2 == 0) + { + memcpy (ptr, s1, n1 * sizeof (long)); + return result; + } + } + } +} +#endif + + +/* This routine preserves the original interface to msort_with_tmp and + determines which variant of hanoi_sort to call, based upon item size + and alignment. */ + +static void +msort_with_tmp (void *b, size_t n, size_t s, __compar_fn_t cmp, void *t) +{ + const size_t size = n * s; + + if (s == sizeof (int) && TYPE_ALIGNED (b, int)) + { + if (hanoi_sort_int (b, n, cmp, t)) + memcpy (b, t, size); + } +#if INT_MAX != LONG_MAX + else if (s == sizeof (long int) && TYPE_ALIGNED (b, long int)) + { + if (hanoi_sort_long (b, n, cmp, t)) + memcpy (b, t, size); + } +#endif + else + { + /* Call the generic implementation. */ + if (hanoi_sort (b, n, s, cmp, t)) + memcpy (b, t, size); + } } void @@ -93,7 +397,7 @@ qsort (void *b, size_t n, size_t s, __compar_fn_t cmp) 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); } @@ -130,7 +434,7 @@ qsort (void *b, size_t n, size_t s, __compar_fn_t cmp) measured in bytes. */ /* If the memory requirements are too high don't allocate memory. */ - if (size / pagesize > phys_pages) + if ((long int) (size / pagesize) > phys_pages) _quicksort (b, n, s, cmp); else { |