Update.

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.

	* manial/syslog.texi (openlog): Describe possible problems with
	first parameter.
	Patch by Christopher Allen Wing <wingc@engin.umich.edu>.

5 files changed, 431 insertions, 62 deletions

diff --git a/ChangeLog b/ChangeLog
index 697db4d..1072bf9 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 9b7f62f..bfde824 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 336f720..b826dc9 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 49f599d..df4179e 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 3668370..7d21c10 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
 	{