Prepare for radical source tree reorganization. zack/build-layout-experiment

All top-level files and directories are moved into a temporary storage
directory, REORG.TODO, except for files that will certainly still
exist in their current form at top level when we're done (COPYING,
COPYING.LIB, LICENSES, NEWS, README), all old ChangeLog files (which
are moved to the new directory OldChangeLogs, instead), and the
generated file INSTALL (which is just deleted; in the new order, there
will be no generated files checked into version control).

1 files changed, 291 insertions, 0 deletions

diff --git a/REORG.TODO/locale/programs/simple-hash.c b/REORG.TODO/locale/programs/simple-hash.c
new file mode 100644
index 0000000000..5e62e249a6
--- /dev/null
+++ b/REORG.TODO/locale/programs/simple-hash.c
@@ -0,0 +1,291 @@
+/* Implement simple hashing table with string based keys.
+   Copyright (C) 1994-2017 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+   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; version 2 of the License, 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, see <http://www.gnu.org/licenses/>.  */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h>
+#include <sys/types.h>
+
+#include <obstack.h>
+
+#ifdef HAVE_VALUES_H
+# include <values.h>
+#endif
+
+#include "simple-hash.h"
+
+#define obstack_chunk_alloc malloc
+#define obstack_chunk_free free
+
+#ifndef BITSPERBYTE
+# define BITSPERBYTE 8
+#endif
+
+#define hashval_t uint32_t
+#include "hashval.h"
+
+#include <programs/xmalloc.h>
+
+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 (hash_table *htab, const void *key, size_t keylen,
+			    unsigned long hval, size_t idx, void *data);
+static size_t lookup (const hash_table *htab, const void *key, size_t keylen,
+		      unsigned long int hval);
+static int is_prime (unsigned long int candidate);
+
+
+int
+init_hash (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 *) xcalloc (init_size + 1, sizeof (hash_entry));
+  if (htab->table == NULL)
+    return -1;
+
+  obstack_init (&htab->mem_pool);
+
+  return 0;
+}
+
+
+int
+delete_hash (hash_table *htab)
+{
+  free (htab->table);
+  obstack_free (&htab->mem_pool, NULL);
+  return 0;
+}
+
+
+int
+insert_entry (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 (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];
+      htab->first = &table[idx];
+    }
+  else
+    {
+      table[idx].next = ((hash_entry *) htab->first)->next;
+      ((hash_entry *) htab->first)->next = &table[idx];
+      htab->first = &table[idx];
+    }
+
+  ++htab->filled;
+  if (100 * htab->filled > 75 * htab->size)
+    {
+      /* Table is filled more than 75%.  Resize the table.
+	 Experiments have shown that for best performance, this threshold
+	 must lie between 40% and 85%.  */
+      unsigned long int old_size = htab->size;
+
+      htab->size = next_prime (htab->size * 2);
+      htab->filled = 0;
+      htab->first = NULL;
+      htab->table = (void *) xcalloc (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 (htab, table[idx].key, table[idx].keylen,
+				  table[idx].used),
+			  table[idx].data);
+
+      free (table);
+    }
+}
+
+
+int
+find_entry (const 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 (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 (const 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;
+}
+
+
+/* References:
+   [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
+   [Knuth]	      The Art of Computer Programming, part3 (6.4) */
+
+static size_t
+lookup (const 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;
+}
+
+
+unsigned long int
+next_prime (unsigned long int seed)
+{
+  /* Make it definitely odd.  */
+  seed |= 1;
+
+  while (!is_prime (seed))
+    seed += 2;
+
+  return seed;
+}
+
+
+static int
+is_prime (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;
+}