Fri Sep 29 03:43:51 1995 Paul Eggert <eggert@twinsun.com>

	Rewrite mktime from scratch for performance, and for correctness
	in the presence of leap seconds.

	* time/mktime.c	(ydhms_tm_diff, not_equal_tm, print_tm, check_result):
	New functions.
	(LEAP_SECONDS_POSSIBLE, CHAR_BIT, INT_MIN, INT_MAX,
	TIME_T_MIN, TIME_T_MAX, TM_YEAR_BASE, EPOCH_YEAR): New macros.
	<limits.h>, <stdlib.h>: New #includes.
	(main): Support tests with given broken-down value; support benchmarks.
	(__mon_lengths, debugging_enabled, printtm, dist_tm, doit,
	do_normalization, normalize, BAD_STRUCT_TM, SKIP_VALUE,
	<ctype.h>): Remove.

	* time/time.h, time/mktime.c (__mktime_internal): New offset arg.
	* time/mktime.c (mktime), time/timegm.c (timegm): Use it.

	* time/mktime.c (__mon_yday): New variable; replaces `__mon_lengths'.
	time/offtime.c (__offtime), time/tzset.c (compute_change): Use it.
	
	* time/offtime.c (__offtime): Remove useless assignment
	`tp->tm_isdst = -1'.

	* manual/maint.texi: Update credits.

Fri Oct  6 00:28:53 1995  Roland McGrath  <roland@churchy.gnu.ai.mit.edu>

	* sysdeps/unix/common/readv.S: Moved to sysdeps/unix/bsd.
	* sysdeps/unix/common/writev.S: Moved to sysdeps/unix/bsd.
	* sysdeps/unix/sysv/linux/readv.c: File removed.
	* sysdeps/unix/sysv/linux/writev.c: File removed.
	* sysdeps/unix/configure.in: Check for readv and writev syscalls.

	* sysdeps/unix/configure.in: If eval doesn't set $unix_srcname,
	set it to $unix_syscall instead of $unix_function.

12 files changed, 373 insertions, 452 deletions

diff --git a/ChangeLog b/ChangeLog
index 3909695617..d600df2beb 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,40 @@
+Fri Sep 29 03:43:51 1995  Paul Eggert  <eggert@twinsun.com>
+
+	Rewrite mktime from scratch for performance, and for correctness
+	in the presence of leap seconds.
+
+	* time/mktime.c	(ydhms_tm_diff, not_equal_tm, print_tm, check_result):
+	New functions.
+	(LEAP_SECONDS_POSSIBLE, CHAR_BIT, INT_MIN, INT_MAX,
+	TIME_T_MIN, TIME_T_MAX, TM_YEAR_BASE, EPOCH_YEAR): New macros.
+	<limits.h>, <stdlib.h>: New #includes.
+	(main): Support tests with given broken-down value; support benchmarks.
+	(__mon_lengths, debugging_enabled, printtm, dist_tm, doit,
+	do_normalization, normalize, BAD_STRUCT_TM, SKIP_VALUE,
+	<ctype.h>): Remove.
+
+	* time/time.h, time/mktime.c (__mktime_internal): New offset arg.
+	* time/mktime.c (mktime), time/timegm.c (timegm): Use it.
+
+	* time/mktime.c (__mon_yday): New variable; replaces `__mon_lengths'.
+	time/offtime.c (__offtime), time/tzset.c (compute_change): Use it.
+	
+	* time/offtime.c (__offtime): Remove useless assignment
+	`tp->tm_isdst = -1'.
+
+	* manual/maint.texi: Update credits.
+
+Fri Oct  6 00:28:53 1995  Roland McGrath  <roland@churchy.gnu.ai.mit.edu>
+
+	* sysdeps/unix/common/readv.S: Moved to sysdeps/unix/bsd.
+	* sysdeps/unix/common/writev.S: Moved to sysdeps/unix/bsd.
+	* sysdeps/unix/sysv/linux/readv.c: File removed.
+	* sysdeps/unix/sysv/linux/writev.c: File removed.
+	* sysdeps/unix/configure.in: Check for readv and writev syscalls.
+
+	* sysdeps/unix/configure.in: If eval doesn't set $unix_srcname,
+	set it to $unix_syscall instead of $unix_function.
+
 Thu Oct  5 00:59:58 1995  Roland McGrath  <roland@churchy.gnu.ai.mit.edu>
 
 	* elf/rtld.c (dl_main): Grok --list flag.
diff --git a/manual/maint.texi b/manual/maint.texi
index 49fb6b4a04..c3e3ee24d7 100644
--- a/manual/maint.texi
+++ b/manual/maint.texi
@@ -774,7 +774,7 @@ The startup code to support SunOS shared libraries was contributed by
 Tom Quinn.
 
 @item
-The @code{mktime} function was contributed by Noel Cragg.
+The @code{mktime} function was contributed by Paul Eggert.
 
 @item
 The port to the Sequent Symmetry running Dynix version 3
diff --git a/sysdeps/unix/common/readv.S b/sysdeps/unix/bsd/readv.S
index 1d643ac6d3..1d643ac6d3 100644
--- a/sysdeps/unix/common/readv.S
+++ b/sysdeps/unix/bsd/readv.S
diff --git a/sysdeps/unix/common/writev.S b/sysdeps/unix/bsd/writev.S
index 3d1692c8fe..3d1692c8fe 100644
--- a/sysdeps/unix/common/writev.S
+++ b/sysdeps/unix/bsd/writev.S
diff --git a/sysdeps/unix/configure.in b/sysdeps/unix/configure.in
index 6d8a1fd006..74456fe18c 100644
--- a/sysdeps/unix/configure.in
+++ b/sysdeps/unix/configure.in
@@ -72,7 +72,7 @@ for unix_function in \
   getitimer setitimer \
   getdomainname/getdomain=bsd/bsd4.4 \
   setdomainname/setdomain=bsd/bsd4.4 \
-  profil=bsd \
+  profil=bsd readv=bsd writev=bsd \
   getpriority setpriority \
   getrlimit setrlimit
 do
@@ -85,7 +85,7 @@ do
   eval "unix_syscall=`echo $unix_function | \
 		       sed -e 's@=\(.*\)$@ unix_srcdir=\1@' \
 			   -e 's@/\(.*\)$@ unix_srcname=\1@'`"
-  test -z "$unix_srcname" && unix_srcname=$unix_function
+  test -z "$unix_srcname" && unix_srcname=$unix_syscall
 
   unix_implementor=none
   for unix_dir in $sysnames; do
@@ -97,11 +97,13 @@ do
     fi
   done
 
-  # mkdir and rmdir have implementations in unix/sysv, but
-  # the simple syscall versions are preferable if available.
-  test $unix_syscall = mkdir -o $unix_syscall = rmdir && \
-  test $unix_implementor = unix/sysv && \
-    unix_implementor=generic
+  case $unix_syscall in
+  mkdir|rmdir) 
+    # mkdir and rmdir have implementations in unix/sysv, but
+    # the simple syscall versions are preferable if available.
+    test $unix_implementor = unix/sysv && unix_implementor=generic
+    ;;
+  esac
 
   case $unix_implementor in
   none|stub|generic|posix)
diff --git a/sysdeps/unix/sysv/linux/readv.c b/sysdeps/unix/sysv/linux/readv.c
deleted file mode 100644
index baa976da6d..0000000000
--- a/sysdeps/unix/sysv/linux/readv.c
+++ /dev/null
@@ -1 +0,0 @@
-#include <sysdeps/posix/readv.c>
diff --git a/sysdeps/unix/sysv/linux/writev.c b/sysdeps/unix/sysv/linux/writev.c
deleted file mode 100644
index 0dc6a76014..0000000000
--- a/sysdeps/unix/sysv/linux/writev.c
+++ /dev/null
@@ -1 +0,0 @@
-#include <sysdeps/posix/writev.c>
diff --git a/time/mktime.c b/time/mktime.c
index 1adb138e0a..852d4058b9 100644
--- a/time/mktime.c
+++ b/time/mktime.c
@@ -1,7 +1,5 @@
 /* Copyright (C) 1993, 1994, 1995 Free Software Foundation, Inc.
-   Contributed by Noel Cragg (noel@cs.oberlin.edu), with fixes by
-   Michael E. Calwas (calwas@ttd.teradyne.com) and
-   Wade Hampton (tasi029@tmn.com).
+   Contributed by Paul Eggert (eggert@twinsun.com).
 
 This file is part of the GNU C Library.
 
@@ -22,22 +20,34 @@ Cambridge, MA 02139, USA.  */
 
 /* Define this to have a standalone program to test this implementation of
    mktime.  */
-/* #define DEBUG */
+/* #define DEBUG 1 */
 
 #ifdef HAVE_CONFIG_H
 #include <config.h>
 #endif
 
+/* Assume that leap seconds are possible, unless told otherwise.
+   If the host has a `zic' command with a `-L leapsecondfilename' option,
+   then it supports leap seconds; otherwise it probably doesn't.  */
+#ifndef LEAP_SECONDS_POSSIBLE
+#define LEAP_SECONDS_POSSIBLE 1
+#endif
+
 #include <sys/types.h>		/* Some systems define `time_t' here.  */
 #include <time.h>
 
+#if __STDC__ || __GNU_LIBRARY__ || STDC_HEADERS
+#include <limits.h>
+#endif
 
-#ifndef __isleap
-/* Nonzero if YEAR is a leap year (every 4 years,
-   except every 100th isn't, and every 400th is).  */
-#define	__isleap(year)	\
-  ((year) % 4 == 0 && ((year) % 100 != 0 || (year) % 400 == 0))
+#if DEBUG
+#include <stdio.h>
+#if __STDC__ || __GNU_LIBRARY__ || STDC_HEADERS
+#include <stdlib.h>
 #endif
+/* Make it work even if the system's libc has its own mktime routine.  */
+#define mktime my_mktime
+#endif /* DEBUG */
 
 #ifndef __P
 #if defined (__GNUC__) || (defined (__STDC__) && __STDC__)
@@ -47,370 +57,62 @@ Cambridge, MA 02139, USA.  */
 #endif  /* GCC.  */
 #endif  /* Not __P.  */
 
-/* How many days are in each month.  */
-const unsigned short int __mon_lengths[2][12] =
-  {
-    /* Normal years.  */
-    { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 },
-    /* Leap years.  */
-    { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }
-  };
-
-
-static int times_through_search; /* This library routine should never
-				    hang -- make sure we always return
-				    when we're searching for a value */
-
-
-#ifdef DEBUG
-
-#include <stdio.h>
-#include <ctype.h>
-
-int debugging_enabled = 0;
-
-/* Print the values in a `struct tm'. */
-static void
-printtm (it)
-     struct tm *it;
-{
-  printf ("%02d/%02d/%04d %02d:%02d:%02d (%s) yday:%03d dst:%d gmtoffset:%ld",
-	  it->tm_mon + 1,
-	  it->tm_mday,
-	  it->tm_year + 1900,
-	  it->tm_hour,
-	  it->tm_min,
-	  it->tm_sec,
-	  it->tm_zone,
-	  it->tm_yday,
-	  it->tm_isdst,
-	  it->tm_gmtoff);
-}
+#ifndef CHAR_BIT
+#define CHAR_BIT 8
 #endif
 
-
-static time_t
-dist_tm (t1, t2)
-     struct tm *t1;
-     struct tm *t2;
-{
-  time_t distance = 0;
-  unsigned long int v1, v2;
-  int diff_flag = 0;
-
-  v1 = v2 = 0;
-
-#define doit(x, secs)                                                         \
-  v1 += t1->x * secs;                                                         \
-  v2 += t2->x * secs;                                                         \
-  if (!diff_flag)                                                             \
-    {                                                                         \
-      if (t1->x < t2->x)                                                      \
-	diff_flag = -1;                                                       \
-      else if (t1->x > t2->x)                                                 \
-	diff_flag = 1;                                                        \
-    }
-  
-  doit (tm_year, 31536000);	/* Okay, not all years have 365 days. */
-  doit (tm_mon, 2592000);	/* Okay, not all months have 30 days. */
-  doit (tm_mday, 86400);
-  doit (tm_hour, 3600);
-  doit (tm_min, 60);
-  doit (tm_sec, 1);
-  
-#undef doit
-  
-  /* We should also make sure that the sign of DISTANCE is correct -- if
-     DIFF_FLAG is positive, the distance should be positive and vice versa. */
-  
-  distance = (v1 > v2) ? (v1 - v2) : (v2 - v1);
-  if (diff_flag < 0)
-    distance = -distance;
-
-  if (times_through_search > 20) /* Arbitrary # of calls, but makes sure we
-				    never hang if there's a problem with
-				    this algorithm.  */
-    {
-      distance = diff_flag;
-    }
-
-  /* We need this DIFF_FLAG business because it is forseeable that the
-     distance may be zero when, in actuality, the two structures are
-     different.  This is usually the case when the dates are 366 days apart
-     and one of the years is a leap year.  */
-
-  if (distance == 0 && diff_flag)
-    distance = 86400 * diff_flag;
-
-  return distance;
-}
-      
-
-/* MKTIME converts the values in a struct tm to a time_t.  The values
-   in tm_wday and tm_yday are ignored; other values can be put outside
-   of legal ranges since they will be normalized.  This routine takes
-   care of that normalization. */
-
-void
-do_normalization (tmptr)
-     struct tm *tmptr;
-{
-
-#define normalize(foo,x,y,bar); \
-  while (tmptr->foo < x) \
-    { \
-      tmptr->bar--; \
-      tmptr->foo = (y - (x - tmptr->foo) + 1); \
-    } \
-  while (tmptr->foo > y) \
-    { \
-      tmptr->foo = (x + (tmptr->foo - y) - 1); \
-      tmptr->bar++; \
-    }
-  
-  normalize (tm_sec, 0, 59, tm_min);
-  normalize (tm_min, 0, 59, tm_hour);
-  normalize (tm_hour, 0, 23, tm_mday);
-  
-  /* Do the month first, so day range can be found. */
-  normalize (tm_mon, 0, 11, tm_year);
-
-  /* Since the day range modifies the month, we should be careful how
-     we reference the array of month lengths -- it is possible that
-     the month will go negative, hence the modulo...
-
-     Also, tm_year is the year - 1900, so we have to 1900 to have it
-     work correctly. */
-
-  normalize (tm_mday, 1,
-	     __mon_lengths[__isleap (tmptr->tm_year + 1900)]
-                          [((tmptr->tm_mon < 0)
-			    ? (12 + (tmptr->tm_mon % 12))
-			    : (tmptr->tm_mon % 12)) ],
-	     tm_mon);
-
-  /* Do the month again, because the day may have pushed it out of range. */
-  normalize (tm_mon, 0, 11, tm_year);
-
-  /* Do the day again, because the month may have changed the range. */
-  normalize (tm_mday, 1,
-	     __mon_lengths[__isleap (tmptr->tm_year + 1900)]
-	                  [((tmptr->tm_mon < 0)
-			    ? (12 + (tmptr->tm_mon % 12))
-			    : (tmptr->tm_mon % 12)) ],
-	     tm_mon);
-  
-#ifdef DEBUG
-  if (debugging_enabled)
-    {
-      printf ("   After normalizing:\n     ");
-      printtm (tmptr);
-      putchar ('\n');
-    }
+#ifndef INT_MIN
+#define INT_MIN (~0 << (sizeof (int) * CHAR_BIT - 1))
 #endif
-
-}
-
-
-/* Here's where the work gets done. */
-
-#define BAD_STRUCT_TM ((time_t) -1)
-
-time_t
-__mktime_internal (timeptr, producer)
-     struct tm *timeptr;
-     struct tm *(*producer) __P ((const time_t *, struct tm *));
-{
-  struct tm our_tm;		/* our working space */
-  struct tm *me = &our_tm;	/* a pointer to the above */
-  time_t result;		/* the value we return */
-
-  *me = *timeptr;		/* copy the struct tm that was passed
-				   in by the caller */
-
-
-  /***************************/
-  /* Normalize the structure */
-  /***************************/
-
-  /* This routine assumes that the value of TM_ISDST is -1, 0, or 1.
-     If the user didn't pass it in that way, fix it. */
-
-  if (me->tm_isdst > 0)
-    me->tm_isdst = 1;
-  else if (me->tm_isdst < 0)
-    me->tm_isdst = -1;
-
-  do_normalization (me);
-
-  /* Get out of here if it's not possible to represent this struct.
-     If any of the values in the normalized struct tm are negative,
-     our algorithms won't work.  Luckily, we only need to check the
-     year at this point; normalization guarantees that all values will
-     be in correct ranges EXCEPT the year. */
-
-  if (me->tm_year < 0)
-    return BAD_STRUCT_TM;
-
-  /*************************************************/
-  /* Find the appropriate time_t for the structure */
-  /*************************************************/
-
-  /* Modified b-search -- make intelligent guesses as to where the
-     time might lie along the timeline, assuming that our target time
-     lies a linear distance (w/o considering time jumps of a
-     particular region).
-
-     Assume that time does not fluctuate at all along the timeline --
-     e.g., assume that a day will always take 86400 seconds, etc. --
-     and come up with a hypothetical value for the time_t
-     representation of the struct tm TARGET, in relation to the guess
-     variable -- it should be pretty close!
-
-     After testing this, the maximum number of iterations that I had
-     on any number that I tried was 3!  Not bad.
-
-     The reason this is not a subroutine is that we will modify some
-     fields in the struct tm (yday and mday).  I've never felt good
-     about side-effects when writing structured code... */
-
-  {
-    struct tm *guess_tm;
-    struct tm guess_struct;
-    time_t guess = 0;
-    time_t distance = 0;
-    time_t last_distance = 0;
-
-    times_through_search = 0;
-
-    do
-      {
-	guess += distance;
-
-	times_through_search++;     
-      
-	guess_tm = (*producer) (&guess, &guess_struct);
-      
-#ifdef DEBUG
-	if (debugging_enabled)
-	  {
-	    printf ("   Guessing time_t == %d\n     ", (int) guess);
-	    printtm (guess_tm);
-	    putchar ('\n');
-	  }
-#endif
-      
-	/* How far is our guess from the desired struct tm? */
-	distance = dist_tm (me, guess_tm);
-      
-	/* Handle periods of time where a period of time is skipped.
-	   For example, 2:15 3 April 1994 does not exist, because DST
-	   is in effect.  The distance function will alternately
-	   return values of 3600 and -3600, because it doesn't know
-	   that the requested time doesn't exist.  In these situations
-	   (even if the skip is not exactly an hour) the distances
-	   returned will be the same, but alternating in sign.  We
-	   want the later time, so check to see that the distance is
-	   oscillating and we've chosen the correct of the two
-	   possibilities.
-
-	   Useful: 3 Apr 94 765356300, 30 Oct 94 783496000 */
-
-	if ((distance == -last_distance) && (distance < last_distance))
-	  {
-	    /* If the caller specified that the DST flag was off, it's
-               not possible to represent this time. */
-	    if (me->tm_isdst == 0)
-	      {
-#ifdef DEBUG
-	    printf ("   Distance is oscillating -- dst flag nixes struct!\n");
+#ifndef INT_MAX
+#define INT_MAX (~0 - INT_MIN)
 #endif
-		return BAD_STRUCT_TM;
-	      }
 
-#ifdef DEBUG
-	    printf ("   Distance is oscillating -- chose the later time.\n");
+#ifndef TIME_T_MIN
+#define TIME_T_MIN (0 < (time_t) -1 ? (time_t) 0 \
+		    : ~ (time_t) 0 << (sizeof (time_t) * CHAR_BIT - 1))
 #endif
-	    distance = 0;
-	  }
-
-	if ((distance == 0) && (me->tm_isdst != -1)
-	    && (me->tm_isdst != guess_tm->tm_isdst))
-	  {
-	    /* If we're in this code, we've got the right time but the
-               wrong daylight savings flag.  We need to move away from
-               the time that we have and approach the other time from
-               the other direction.  That is, if I've requested the
-               non-DST version of a time and I get the DST version
-               instead, I want to put us forward in time and search
-               backwards to get the other time.  I checked all of the
-               configuration files for the tz package -- no entry
-               saves more than two hours, so I think we'll be safe by
-               moving 24 hours in one direction.  IF THE AMOUNT OF
-               TIME SAVED IN THE CONFIGURATION FILES CHANGES, THIS
-               VALUE MAY NEED TO BE ADJUSTED.  Luckily, we can never
-               have more than one level of overlaps, or this would
-               never work. */
-
-#define SKIP_VALUE 86400
-
-	    if (guess_tm->tm_isdst == 0)
-	      /* we got the later one, but want the earlier one */
-	      distance = -SKIP_VALUE;
-	    else
-	      distance = SKIP_VALUE;
-	    
-#ifdef DEBUG
-	    printf ("   Got the right time, wrong DST value -- adjusting\n");
+#ifndef TIME_T_MAX
+#define TIME_T_MAX (~ (time_t) 0 - TIME_T_MIN)
 #endif
-	  }
-
-	last_distance = distance;
-
-      } while (distance != 0);
 
-    /* Check to see that the dst flag matches */
+#define TM_YEAR_BASE 1900
+#define EPOCH_YEAR 1970
 
-    if (me->tm_isdst != -1)
-      {
-	if (me->tm_isdst != guess_tm->tm_isdst)
-	  {
-#ifdef DEBUG
-	    printf ("   DST flag doesn't match!  FIXME?\n");
+#ifndef __isleap
+/* Nonzero if YEAR is a leap year (every 4 years,
+   except every 100th isn't, and every 400th is).  */
+#define	__isleap(year)	\
+  ((year) % 4 == 0 && ((year) % 100 != 0 || (year) % 400 == 0))
 #endif
-	    return BAD_STRUCT_TM;
-	  }
-      }
-
-    result = guess;		/* Success! */
-
-    /* On successful completion, the values of tm_wday and tm_yday
-       have to be set appropriately. */
-    
-    /* me->tm_yday = guess_tm->tm_yday; 
-       me->tm_mday = guess_tm->tm_mday; */
-
-    *me = *guess_tm;
-  }
 
-  /* Update the caller's version of the structure */
+/* How many days come before each month (0-12).  */
+const unsigned short int __mon_yday[2][13] =
+  {
+    /* Normal years.  */
+    { 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365 },
+    /* Leap years.  */
+    { 0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366 }
+  };
 
-  *timeptr = *me;
+static time_t ydhms_tm_diff __P ((int, int, int, int, int, const struct tm *));
+time_t __mktime_internal __P ((struct tm *,
+			       struct tm *(*) (const time_t *, struct tm *),
+			       time_t *));
 
-  return result;
-}
 
 #if ! HAVE_LOCALTIME_R && ! defined (localtime_r)
 #ifdef _LIBC
 #define localtime_r __localtime_r
 #else
 /* Approximate localtime_r as best we can in its absence.  */
-#define localtime_r my_localtime_r /* Avoid clash with system localtime_r.  */
+#define localtime_r my_localtime_r
+static struct tm *localtime_r __P ((const time_t *, struct tm *));
 static struct tm *
 localtime_r (t, tp)
      const time_t *t;
      struct tm *tp;
-{ 
+{
   struct tm *l = localtime (t);
   if (! l)
     return 0;
@@ -420,108 +122,287 @@ localtime_r (t, tp)
 #endif /* ! _LIBC */
 #endif /* ! HAVE_LOCALTIME_R && ! defined (localtime_r) */
 
+
+/* Yield the difference between (YEAR-YDAY HOUR:MIN:SEC) and (*TP),
+   measured in seconds, ignoring leap seconds.
+   YEAR uses the same numbering as TM->tm_year.
+   All values are in range, except possibly YEAR.
+   If overflow occurs, yield the low order bits of the correct answer.  */
+static time_t
+ydhms_tm_diff (year, yday, hour, min, sec, tp)
+     int year, yday, hour, min, sec;
+     const struct tm *tp;
+{
+  time_t ay = year + (time_t) (TM_YEAR_BASE - 1);
+  time_t by = tp->tm_year + (time_t) (TM_YEAR_BASE - 1);