New files, from gnulib

3 files changed, 277 insertions, 0 deletions

diff --git a/lib/allocsa.c b/lib/allocsa.c
new file mode 100644
index 000000000..55f6b80da
--- /dev/null
+++ b/lib/allocsa.c
@@ -0,0 +1,139 @@
+/* Safe automatic memory allocation.
+   Copyright (C) 2003 Free Software Foundation, Inc.
+   Written by Bruno Haible <bruno@clisp.org>, 2003.
+
+   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 2, 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
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+/* Specification.  */
+#include "allocsa.h"
+
+/* The speed critical point in this file is freesa() applied to an alloca()
+   result: it must be fast, to match the speed of alloca().  The speed of
+   mallocsa() and freesa() in the other case are not critical, because they
+   are only invoked for big memory sizes.  */
+
+#if HAVE_ALLOCA
+
+/* Store the mallocsa() results in a hash table.  This is needed to reliably
+   distinguish a mallocsa() result and an alloca() result.
+
+   Although it is possible that the same pointer is returned by alloca() and
+   by mallocsa() at different times in the same application, it does not lead
+   to a bug in freesa(), because:
+     - Before a pointer returned by alloca() can point into malloc()ed memory,
+       the function must return, and once this has happened the programmer must
+       not call freesa() on it anyway.
+     - Before a pointer returned by mallocsa() can point into the stack, it
+       must be freed.  The only function that can free it is freesa(), and
+       when freesa() frees it, it also removes it from the hash table.  */
+
+# define MAGIC_NUMBER 0x1415fb4a
+# define MAGIC_SIZE sizeof (int)
+/* This is how the header info would look like without any alignment
+   considerations.  */
+struct preliminary_header { void *next; char room[MAGIC_SIZE]; };
+/* But the header's size must be a multiple of sa_alignment_max.  */
+# define HEADER_SIZE \
+  (((sizeof (struct preliminary_header) + sa_alignment_max - 1) / sa_alignment_max) * sa_alignment_max)
+struct header { void *next; char room[HEADER_SIZE - sizeof (struct preliminary_header) + MAGIC_SIZE]; };
+/* Verify that HEADER_SIZE == sizeof (struct header).  */
+typedef int verify1[2 * (HEADER_SIZE == sizeof (struct header)) - 1];
+/* We make the hash table quite big, so that during lookups the probability
+   of empty hash buckets is quite high.  There is no need to make the hash
+   table resizable, because when the hash table gets filled so much that the
+   lookup becomes slow, it means that the application has memory leaks.  */
+# define HASH_TABLE_SIZE 257
+static void * mallocsa_results[HASH_TABLE_SIZE];
+
+#endif
+
+void *
+mallocsa (size_t n)
+{
+#if HAVE_ALLOCA
+  /* Allocate one more word, that serves as an indicator for malloc()ed
+     memory, so that freesa() of an alloca() result is fast.  */
+  size_t nplus = n + HEADER_SIZE;
+
+  if (nplus >= n)
+    {
+      char *p = (char *) malloc (nplus);
+
+      if (p != NULL)
+	{
+	  size_t slot;
+
+	  p += HEADER_SIZE;
+
+	  /* Put a magic number into the indicator word.  */
+	  ((int *) p)[-1] = MAGIC_NUMBER;
+
+	  /* Enter p into the hash table.  */
+	  slot = (unsigned long) p % HASH_TABLE_SIZE;
+	  ((struct header *) (p - HEADER_SIZE))->next = mallocsa_results[slot];
+	  mallocsa_results[slot] = p;
+
+	  return p;
+	}
+    }
+  /* Out of memory.  */
+  return NULL;
+#else
+# if !MALLOC_0_IS_NONNULL
+  if (n == 0)
+    n = 1;
+# endif
+  return malloc (n);
+#endif
+}
+
+#if HAVE_ALLOCA
+void
+freesa (void *p)
+{
+  /* mallocsa() may have returned NULL.  */
+  if (p != NULL)
+    {
+      /* Attempt to quickly distinguish the mallocsa() result - which has
+	 a magic indicator word - and the alloca() result - which has an
+	 uninitialized indicator word.  It is for this test that sa_increment
+	 additional bytes are allocated in the alloca() case.  */
+      if (((int *) p)[-1] == MAGIC_NUMBER)
+	{
+	  /* Looks like a mallocsa() result.  To see whether it really is one,
+	     perform a lookup in the hash table.  */
+	  size_t slot = (unsigned long) p % HASH_TABLE_SIZE;
+	  void **chain = &mallocsa_results[slot];
+	  for (; *chain != NULL;)
+	    {
+	      if (*chain == p)
+		{
+		  /* Found it.  Remove it from the hash table and free it.  */
+		  char *p_begin = (char *) p - HEADER_SIZE;
+		  *chain = ((struct header *) p_begin)->next;
+		  free (p_begin);
+		  return;
+		}
+	      chain = &((struct header *) ((char *) *chain - HEADER_SIZE))->next;
+	    }
+	}
+      /* At this point, we know it was not a mallocsa() result.  */
+    }
+}
+#endif
diff --git a/lib/allocsa.h b/lib/allocsa.h
new file mode 100644
index 000000000..9d33bdc62
--- /dev/null
+++ b/lib/allocsa.h
@@ -0,0 +1,109 @@
+/* Safe automatic memory allocation.
+   Copyright (C) 2003 Free Software Foundation, Inc.
+   Written by Bruno Haible <bruno@clisp.org>, 2003.
+
+   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 2, 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
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#ifndef _ALLOCSA_H
+#define _ALLOCSA_H
+
+#include <alloca.h>
+#include <stddef.h>
+#include <stdlib.h>
+
+/* safe_alloca(N) is equivalent to alloca(N) when it is safe to call
+   alloca(N); otherwise it returns NULL.  It either returns N bytes of
+   memory allocated on the stack, that lasts until the function returns,
+   or NULL.
+   Use of safe_alloca should be avoided:
+     - inside arguments of function calls - undefined behaviour,
+     - in inline functions - the allocation may actually last until the
+       calling function returns.
+*/
+#if HAVE_ALLOCA
+/* The OS usually guarantees only one guard page at the bottom of the stack,
+   and a page size can be as small as 4096 bytes.  So we cannot safely
+   allocate anything larger than 4096 bytes.  Also care for the possibility
+   of a few compiler-allocated temporary stack slots.
+   This must be a macro, not an inline function.  */
+# define safe_alloca(N) ((N) < 4032 ? alloca (N) : NULL)
+#else
+# define safe_alloca(N) ((N), NULL)
+#endif
+
+/* allocsa(N) is a safe variant of alloca(N).  It allocates N bytes of
+   memory allocated on the stack, that must be freed using freesa() before
+   the function returns.  Upon failure, it returns NULL.  */
+#if HAVE_ALLOCA
+# define allocsa(N) \
+  ((N) < 4032 - sa_increment					    \
+   ? (void *) ((char *) alloca ((N) + sa_increment) + sa_increment) \
+   : mallocsa (N))
+#else
+# define allocsa(N) \
+  mallocsa (N)
+#endif
+extern void * mallocsa (size_t n);
+
+/* Free a block of memory allocated through allocsa().  */
+#if HAVE_ALLOCA
+extern void freesa (void *p);
+#else
+# define freesa free
+#endif
+
+/* Maybe we should also define a variant
+    nallocsa (size_t n, size_t s) - behaves like allocsa (n * s)
+   If this would be useful in your application. please speak up.  */
+
+
+/* ------------------- Auxiliary, non-public definitions ------------------- */
+
+/* Determine the alignment of a type at compile time.  */
+#if defined __GNUC__
+# define sa_alignof __alignof__
+#elif defined __cplusplus
+  template <class type> struct sa_alignof_helper { char __slot1; type __slot2; };
+# define sa_alignof(type) offsetof (sa_alignof_helper<type>, __slot2)
+#else
+# define sa_alignof(type) offsetof (struct { char __slot1; type __slot2; }, __slot2)
+#endif
+
+enum
+{
+/* The desired alignment of memory allocations is the maximum alignment
+   among all elementary types.  */
+  sa_alignment_long = sa_alignof (long),
+  sa_alignment_double = sa_alignof (double),
+#ifdef HAVE_LONG_LONG
+  sa_alignment_longlong = sa_alignof (long long),
+#endif
+#ifdef HAVE_LONG_DOUBLE 
+  sa_alignment_longdouble = sa_alignof (long double),
+#endif
+  sa_alignment_max = ((sa_alignment_long - 1) | (sa_alignment_double - 1)
+#ifdef HAVE_LONG_LONG
+		      | (sa_alignment_longlong - 1)
+#endif
+#ifdef HAVE_LONG_DOUBLE 
+		      | (sa_alignment_longdouble - 1)
+#endif
+		     ) + 1,
+/* The increment that guarantees room for a magic word must be >= sizeof (int)
+   and a multiple of sa_alignment_max.  */
+  sa_increment = ((sizeof (int) + sa_alignment_max - 1) / sa_alignment_max) * sa_alignment_max
+};
+
+#endif /* _ALLOCSA_H */
diff --git a/lib/strdup.h b/lib/strdup.h
new file mode 100644
index 000000000..4dc6a391c
--- /dev/null
+++ b/lib/strdup.h
@@ -0,0 +1,29 @@
+/* strdup.h -- duplicate a string
+   Copyright (C) 2004 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 2, 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
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#ifndef STRDUP_H_
+#define STRDUP_H_
+
+/* Get strdup declaration, if available.  */
+#include <string.h>
+
+#if !HAVE_DECL_STRDUP && !defined strdup
+/* Duplicate S, returning an identical malloc'd string.  */
+extern char *strdup (const char *s);
+#endif
+
+#endif /* STRDUP_H_ */