about summary refs log tree commit diff
path: root/locale/programs
diff options
context:
space:
mode:
authorRoland McGrath <roland@gnu.org>1996-03-28 09:16:15 +0000
committerRoland McGrath <roland@gnu.org>1996-03-28 09:16:15 +0000
commit0393dfd6c22d4f3bb61c4650e4c22e87026b19bd (patch)
tree6191705921900f148158c834b1a9cb095ffc8475 /locale/programs
parent19bc17a90548ee427035994bbc4b14395723ff1f (diff)
downloadglibc-0393dfd6c22d4f3bb61c4650e4c22e87026b19bd.tar.gz
glibc-0393dfd6c22d4f3bb61c4650e4c22e87026b19bd.tar.xz
glibc-0393dfd6c22d4f3bb61c4650e4c22e87026b19bd.zip
* locale/programs/xmalloc.c: Test _LIBC as well as STDC_HEADERS.
	* locale/programs/ld-collate.c (collate_finish): Use error_at_line
	instead of error_with_loc.

	* locale/weight.h: Use u_int32_t instead of u32_t.
	* string/strxfrm.c: Likewise.

	* string/strxfrm.c: Find weight.h in ../locale; don't #include
	"localeinfo.h".
	* string/strcoll.c: Likewise.

	* locale/programs/simple-hash.c, locale/programs/simple-hash.h,
 	locale/programs/xmalloc.c, locale/programs/xstrdup.c: Helper functions
 	for locale related programs.
 	locale/programs/charmap.c, locale/programs/charset.c,
 	locale/programs/charset.h, locale/programs/config.h,
 	locale/programs/ctypedump.c, locale/programs/ld-collate.c,
 	locale/programs/ld-ctype.c, locale/programs/ld-messages.c,
 	locale/programs/ld-monetary.c, locale/programs/ld-numeric.c,
 	locale/programs/ld-time.c, locale/programs/linereader.c,
 	locale/programs/linereader.h, locale/programs/locale.c,
 	locale/programs/localedef.c, locale/programs/locales.h,
 	locale/programs/locfile-kw.gperf, locale/programs/locfile-kw.h,
 	locale/programs/locfile-token.h, locale/programs/locfile.c,
 	locale/programs/locfile.h, locale/programs/stringtrans.c,
 	locale/programs/stringtrans.h: Implementation of locale related
 	programs.
Diffstat (limited to 'locale/programs')
-rw-r--r--locale/programs/ld-collate.c2
-rw-r--r--locale/programs/simple-hash.c401
-rw-r--r--locale/programs/simple-hash.h48
-rw-r--r--locale/programs/xmalloc.c111
-rw-r--r--locale/programs/xstrdup.c36
5 files changed, 597 insertions, 1 deletions
diff --git a/locale/programs/ld-collate.c b/locale/programs/ld-collate.c
index 0f3bcbca33..598b963fc0 100644
--- a/locale/programs/ld-collate.c
+++ b/locale/programs/ld-collate.c
@@ -239,7 +239,7 @@ collate_finish (struct localedef_t *locale, struct charset_t *charset)
 	value = 0;
 
       if (value == 0)
-	error_with_loc (0, 0, patch->fname, patch->lineno,
+	error_at_line (0, 0, patch->fname, patch->lineno,
 			_("no weight defined for symbol `%s'"), patch->token);
       else
 	*patch->where.pos = value;
diff --git a/locale/programs/simple-hash.c b/locale/programs/simple-hash.c
new file mode 100644
index 0000000000..234ba0c49e
--- /dev/null
+++ b/locale/programs/simple-hash.c
@@ -0,0 +1,401 @@
+/* hash - implement simple hashing table with string based keys.
+   Copyright (C) 1994, 1995, 1996 Free Software Foundation, Inc.
+   Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994.
+
+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
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/types.h>
+
+#if HAVE_OBSTACK
+# include <obstack.h>
+#else
+# include "obstack.h"
+#endif
+
+#ifdef HAVE_VALUES_H
+# include <values.h>
+#endif
+
+#include "simple-hash.h"
+
+#define obstack_chunk_alloc xmalloc
+#define obstack_chunk_free free
+
+#ifndef BITSPERBYTE
+# define BITSPERBYTE 8
+#endif
+
+#ifndef	LONGBITS
+# define LONGBITS (sizeof (long) * BITSPERBYTE)
+#endif
+
+#ifndef bcopy
+# define bcopy(s, d, n)	memcpy ((d), (s), (n))
+#endif
+
+void *xmalloc __P ((size_t __n));
+
+typedef struct hash_entry
+{
+  unsigned long used;
+  const void *key;
+  size_t keylen;
+  void *data;
+  struct hash_entry *next;
+}
+hash_entry;
+
+/* Prototypes for local functions.  */
+static void insert_entry_2 __P ((hash_table *htab, const void *key,
+				 size_t keylen, unsigned long hval,
+				 size_t idx, void *data));
+static size_t lookup __P ((hash_table *htab, const void *key, size_t keylen,
+			   unsigned long int hval));
+static size_t lookup_2 __P ((hash_table *htab, const void *key,
+			     size_t keylen, unsigned long int hval));
+static unsigned long compute_hashval __P ((const void *key, size_t keylen));
+static int is_prime __P ((unsigned long int candidate));
+
+
+int
+init_hash (htab, init_size)
+     hash_table *htab;
+     unsigned long int init_size;
+{
+  /* We need the size to be a prime.  */
+  init_size = next_prime (init_size);
+
+  /* Initialize the data structure.  */
+  htab->size = init_size;
+  htab->filled = 0;
+  htab->first = NULL;
+  htab->table = (void *) xmalloc ((init_size + 1) * sizeof (hash_entry));
+  if (htab->table == NULL)
+    return -1;
+
+  memset (htab->table, '\0', (init_size + 1) * sizeof (hash_entry));
+  obstack_init (&htab->mem_pool);
+
+  return 0;
+}
+
+
+int
+delete_hash (htab)
+     hash_table *htab;
+{
+  free (htab->table);
+  obstack_free (&htab->mem_pool, NULL);
+  return 0;
+}
+
+
+int
+insert_entry (htab, key, keylen, data)
+     hash_table *htab;
+     const void *key;
+     size_t keylen;
+     void *data;
+{
+  unsigned long int hval = compute_hashval (key, keylen);
+  hash_entry *table = (hash_entry *) htab->table;
+  size_t idx = lookup (htab, key, keylen, hval);
+
+  if (table[idx].used)
+    /* We don't want to overwrite the old value.  */
+    return -1;
+  else
+    {
+      /* An empty bucket has been found.  */
+      insert_entry_2 (htab, obstack_copy (&htab->mem_pool, key, keylen),
+		      keylen, hval, idx, data);
+      return 0;
+    }
+}
+
+static void
+insert_entry_2 (htab, key, keylen, hval, idx, data)
+     hash_table *htab;
+     const void *key;
+     size_t keylen;
+     unsigned long int hval;
+     size_t idx;
+     void *data;
+{
+  hash_entry *table = (hash_entry *) htab->table;
+
+  table[idx].used = hval;
+  table[idx].key = key;
+  table[idx].keylen = keylen;
+  table[idx].data = data;
+
+      /* List the new value in the list.  */
+  if ((hash_entry *) htab->first == NULL)
+    {
+      table[idx].next = &table[idx];
+      *(hash_entry **) &htab->first = &table[idx];
+    }
+  else
+    {
+      table[idx].next = ((hash_entry *) htab->first)->next;
+      ((hash_entry *) htab->first)->next = &table[idx];
+      *(hash_entry **) &htab->first = &table[idx];
+    }
+
+  ++htab->filled;
+  if (100 * htab->filled > 90 * htab->size)
+    {
+      /* Table is filled more than 90%.  Resize the table.  */
+      unsigned long int old_size = htab->size;
+
+      htab->size = next_prime (htab->size * 2);
+      htab->filled = 0;
+      htab->first = NULL;
+      htab->table = (void *) xmalloc ((1 + htab->size)
+				      * sizeof (hash_entry));
+      memset (htab->table, '\0', (1 + htab->size) * sizeof (hash_entry));
+
+      for (idx = 1; idx <= old_size; ++idx)
+	if (table[idx].used)
+	  insert_entry_2 (htab, table[idx].key, table[idx].keylen,
+			  table[idx].used,
+			  lookup_2 (htab, table[idx].key, table[idx].keylen,
+				    table[idx].used),
+			  table[idx].data);
+
+      free (table);
+    }
+}
+
+
+int
+find_entry (htab, key, keylen, result)
+     hash_table *htab;
+     const void *key;
+     size_t keylen;
+     void **result;
+{
+  hash_entry *table = (hash_entry *) htab->table;
+  size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
+
+  if (table[idx].used == 0)
+    return -1;
+
+  *result = table[idx].data;
+  return 0;
+}
+
+
+int
+set_entry (htab, key, keylen, newval)
+     hash_table *htab;
+     const void *key;
+     size_t keylen;
+     void *newval;
+{
+  hash_entry *table = (hash_entry *) htab->table;
+  size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
+
+  if (table[idx].used == 0)
+    return -1;
+
+  table[idx].data = newval;
+  return 0;
+}
+
+
+int
+iterate_table (htab, ptr, key, keylen, data)
+     hash_table *htab;
+     void **ptr;
+     const void **key;
+     size_t *keylen;
+     void **data;
+{
+  if (*ptr == NULL)
+    {
+      if (htab->first == NULL)
+	return -1;
+      *ptr = (void *) ((hash_entry *) htab->first)->next;
+    }
+  else
+    {
+      if (*ptr == htab->first)
+	return -1;
+      *ptr = (void *) (((hash_entry *) *ptr)->next);
+    }
+
+  *key = ((hash_entry *) *ptr)->key;
+  *keylen = ((hash_entry *) *ptr)->keylen;
+  *data = ((hash_entry *) *ptr)->data;
+  return 0;
+}
+
+
+static size_t
+lookup (htab, key, keylen, hval)
+     hash_table *htab;
+     const void *key;
+     size_t keylen;
+     unsigned long hval;
+{
+  unsigned long hash;
+  size_t idx;
+  hash_entry *table = (hash_entry *) htab->table;
+
+  /* First hash function: simply take the modul but prevent zero.  */
+  hash = 1 + hval % htab->size;
+
+  idx = hash;
+
+  if (table[idx].used)
+    {
+      if (table[idx].used == hval && table[idx].keylen == keylen
+	  && memcmp (key, table[idx].key, keylen) == 0)
+	return idx;
+
+      /* Second hash function as suggested in [Knuth].  */
+      hash = 1 + hval % (htab->size - 2);
+
+      do
+	{
+	  if (idx <= hash)
+	    idx = htab->size + idx - hash;
+	  else
+	    idx -= hash;
+
+	  /* If entry is found use it.  */
+	  if (table[idx].used == hval && table[idx].keylen == keylen
+	      && memcmp (key, table[idx].key, keylen) == 0)
+	    return idx;
+	}
+      while (table[idx].used);
+    }
+  return idx;
+}
+
+
+/* References:
+   [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
+   [Knuth]	      The Art of Computer Programming, part3 (6.4) */
+
+static size_t
+lookup_2 (htab, key, keylen, hval)
+     hash_table *htab;
+     const void *key;
+     size_t keylen;
+     unsigned long int hval;
+{
+  unsigned long int hash;
+  size_t idx;
+  hash_entry *table = (hash_entry *) htab->table;
+
+  /* First hash function: simply take the modul but prevent zero.  */
+  hash = 1 + hval % htab->size;
+
+  idx = hash;
+
+  if (table[idx].used)
+    {
+      if (table[idx].used == hval && table[idx].keylen == keylen
+	  && memcmp (table[idx].key, key, keylen) == 0)
+	return idx;
+
+      /* Second hash function as suggested in [Knuth].  */
+      hash = 1 + hval % (htab->size - 2);
+
+      do
+	{
+	  if (idx <= hash)
+	    idx = htab->size + idx - hash;
+	  else
+	    idx -= hash;
+
+	  /* If entry is found use it.  */
+	  if (table[idx].used == hval && table[idx].keylen == keylen
+	      && memcmp (table[idx].key, key, keylen) == 0)
+	    return idx;
+	}
+      while (table[idx].used);
+    }
+  return idx;
+}
+
+
+static unsigned long
+compute_hashval (key, keylen)
+     const void *key;
+     size_t keylen;
+{
+  size_t cnt;
+  unsigned long int hval, g;
+
+  /* Compute the hash value for the given string.  The algorithm
+     is taken from [Aho,Sethi,Ullman].  */
+  cnt = 0;
+  hval = keylen;
+  while (cnt < keylen)
+    {
+      hval <<= 4;
+      hval += (unsigned long int) *(((char *) key) + cnt++);
+      g = hval & ((unsigned long) 0xf << (LONGBITS - 4));
+      if (g != 0)
+	{
+	  hval ^= g >> (LONGBITS - 8);
+	  hval ^= g;
+	}
+    }
+  return hval != 0 ? hval : ~((unsigned long) 0);
+}
+
+
+unsigned long
+next_prime (seed)
+     unsigned long int seed;
+{
+  /* Make it definitely odd.  */
+  seed |= 1;
+
+  while (!is_prime (seed))
+    seed += 2;
+
+  return seed;
+}
+
+
+static int
+is_prime (candidate)
+     unsigned long int candidate;
+{
+  /* No even number and none less than 10 will be passed here.  */
+  unsigned long int divn = 3;
+  unsigned long int sq = divn * divn;
+
+  while (sq < candidate && candidate % divn != 0)
+    {
+      ++divn;
+      sq += 4 * divn;
+      ++divn;
+    }
+
+  return candidate % divn != 0;
+}
diff --git a/locale/programs/simple-hash.h b/locale/programs/simple-hash.h
new file mode 100644
index 0000000000..3409c57cec
--- /dev/null
+++ b/locale/programs/simple-hash.h
@@ -0,0 +1,48 @@
+/* Copyright (C) 1995, 1996 Free Software Foundation, Inc.
+
+The GNU C Library is free software; you can redistribute it and/or
+modify it under the terms of the GNU Library General Public License as
+published by the Free Software Foundation; either version 2 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
+Library General Public License for more details.
+
+You should have received a copy of the GNU Library General Public
+License along with the GNU C Library; see the file COPYING.LIB.  If
+not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA.  */
+
+#ifndef _SIMPLE_HASH_H
+#define _SIMPLE_HASH_H
+
+#include <obstack.h>
+
+typedef struct hash_table
+{
+  unsigned long size;
+  unsigned long filled;
+  void *first;
+  void *table;
+  struct obstack mem_pool;
+}
+hash_table;
+
+
+int init_hash __P ((hash_table *htab, unsigned long int init_size));
+int delete_hash __P ((hash_table *htab));
+int insert_entry __P ((hash_table *htab, const void *key, size_t keylen,
+		       void *data));
+int find_entry __P ((hash_table *htab, const void *key, size_t keylen,
+		     void **result));
+int set_entry __P ((hash_table *htab, const void *key, size_t keylen,
+		    void *newval));
+
+int iterate_table __P ((hash_table *htab, void **ptr,
+			const void **key, size_t *keylen, void **data));
+
+unsigned long next_prime __P ((unsigned long int seed));
+
+#endif /* simple-hash.h */
diff --git a/locale/programs/xmalloc.c b/locale/programs/xmalloc.c
new file mode 100644
index 0000000000..2680b8a160
--- /dev/null
+++ b/locale/programs/xmalloc.c
@@ -0,0 +1,111 @@
+/* xmalloc.c -- malloc with out of memory checking
+   Copyright (C) 1990, 91, 92, 93, 94, 95 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.  */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#if __STDC__
+#define VOID void
+#else
+#define VOID char
+#endif
+
+#include <sys/types.h>
+
+#if STDC_HEADERS || _LIBC
+#include <stdlib.h>
+#else
+VOID *calloc ();
+VOID *malloc ();
+VOID *realloc ();
+void free ();
+#endif
+
+#include <libintl.h>
+#include "error.h"
+
+#ifndef _
+# define _(str) gettext (str)
+#endif
+
+#ifndef EXIT_FAILURE
+#define EXIT_FAILURE 4
+#endif
+
+/* Exit value when the requested amount of memory is not available.
+   The caller may set it to some other value.  */
+int xmalloc_exit_failure = EXIT_FAILURE;
+
+static VOID *
+fixup_null_alloc (n)
+     size_t n;
+{
+  VOID *p;
+
+  p = 0;
+  if (n == 0)
+    p = malloc ((size_t) 1);
+  if (p == 0)
+    error (xmalloc_exit_failure, 0, _("memory exhausted"));
+  return p;
+}
+
+/* Allocate N bytes of memory dynamically, with error checking.  */
+
+VOID *
+xmalloc (n)
+     size_t n;
+{
+  VOID *p;
+
+  p = malloc (n);
+  if (p == 0)
+    p = fixup_null_alloc (n);
+  return p;
+}
+
+/* Allocate memory for N elements of S bytes, with error checking.  */
+
+VOID *
+xcalloc (n, s)
+     size_t n, s;
+{
+  VOID *p;
+
+  p = calloc (n, s);
+  if (p == 0)
+    p = fixup_null_alloc (n);
+  return p;
+}
+
+/* Change the size of an allocated block of memory P to N bytes,
+   with error checking.
+   If P is NULL, run xmalloc.  */
+
+VOID *
+xrealloc (p, n)
+     VOID *p;
+     size_t n;
+{
+  if (p == 0)
+    return xmalloc (n);
+  p = realloc (p, n);
+  if (p == 0)
+    p = fixup_null_alloc (n);
+  return p;
+}
diff --git a/locale/programs/xstrdup.c b/locale/programs/xstrdup.c
new file mode 100644
index 0000000000..1b5b415b2b
--- /dev/null
+++ b/locale/programs/xstrdup.c
@@ -0,0 +1,36 @@
+/* xstrdup.c -- copy a string with out of memory checking
+   Copyright (C) 1990 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.  */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#if defined(STDC_HEADERS) || defined(HAVE_STRING_H)
+#include <string.h>
+#else
+#include <strings.h>
+#endif
+char *xmalloc ();
+
+/* Return a newly allocated copy of STRING.  */
+
+char *
+xstrdup (string)
+     char *string;
+{
+  return strcpy (xmalloc (strlen (string) + 1), string);
+}