hash-map: New module.

* lib/gl_hash_map.h: New file.
* lib/gl_hash_map.c: New file.
* modules/hash-map: New file.

4 files changed, 404 insertions, 0 deletions

diff --git a/ChangeLog b/ChangeLog
index baf552c011..adb83614ab 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,10 @@
 2018-12-14  Bruno Haible  <bruno@clisp.org>
 
+	hash-map: New module.
+	* lib/gl_hash_map.h: New file.
+	* lib/gl_hash_map.c: New file.
+	* modules/hash-map: New file.
+
 	linkedhash-map: New module.
 	* lib/gl_linkedhash_map.h: New file.
 	* lib/gl_linkedhash_map.c: New file.
diff --git a/lib/gl_hash_map.c b/lib/gl_hash_map.c
new file mode 100644
index 0000000000..7d68e7bd31
--- /dev/null
+++ b/lib/gl_hash_map.c
@@ -0,0 +1,337 @@
+/* Map data type implemented by a hash table.
+   Copyright (C) 2006, 2008-2018 Free Software Foundation, Inc.
+   Written by Bruno Haible <bruno@clisp.org>, 2018.
+
+   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 3 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 <https://www.gnu.org/licenses/>.  */
+
+#include <config.h>
+
+/* Specification.  */
+#include "gl_hash_map.h"
+
+#include <stdint.h> /* for SIZE_MAX */
+#include <stdlib.h>
+
+#include "xsize.h"
+
+#ifndef uintptr_t
+# define uintptr_t unsigned long
+#endif
+
+/* --------------------------- gl_map_t Data Type --------------------------- */
+
+#include "gl_anyhash1.h"
+
+/* Concrete list node implementation, valid for this file only.  */
+struct gl_list_node_impl
+{
+  struct gl_hash_entry h;           /* hash table entry fields; must be first */
+  const void *key;
+  const void *value;
+};
+typedef struct gl_list_node_impl * gl_list_node_t;
+
+/* Concrete gl_map_impl type, valid for this file only.  */
+struct gl_map_impl
+{
+  struct gl_map_impl_base base;
+  gl_mapkey_hashcode_fn hashcode_fn;
+  /* A hash table: managed as an array of collision lists.  */
+  struct gl_hash_entry **table;
+  size_t table_size;
+  /* Number of hash table entries.  */
+  size_t count;
+};
+
+#define CONTAINER_T gl_map_t
+#define CONTAINER_COUNT(map) (map)->count
+#include "gl_anyhash2.h"
+
+/* --------------------------- gl_map_t Data Type --------------------------- */
+
+static gl_map_t
+gl_hash_nx_create_empty (gl_map_implementation_t implementation,
+                         gl_mapkey_equals_fn equals_fn,
+                         gl_mapkey_hashcode_fn hashcode_fn,
+                         gl_mapkey_dispose_fn kdispose_fn,
+                         gl_mapvalue_dispose_fn vdispose_fn)
+{
+  struct gl_map_impl *map =
+    (struct gl_map_impl *) malloc (sizeof (struct gl_map_impl));
+
+  if (map == NULL)
+    return NULL;
+
+  map->base.vtable = implementation;
+  map->base.equals_fn = equals_fn;
+  map->base.kdispose_fn = kdispose_fn;
+  map->base.vdispose_fn = vdispose_fn;
+  map->hashcode_fn = hashcode_fn;
+  map->table_size = 11;
+  map->table =
+    (gl_hash_entry_t *) calloc (map->table_size, sizeof (gl_hash_entry_t));
+  if (map->table == NULL)
+    goto fail;
+  map->count = 0;
+
+  return map;
+
+ fail:
+  free (map);
+  return NULL;
+}
+
+static size_t _GL_ATTRIBUTE_PURE
+gl_hash_size (gl_map_t map)
+{
+  return map->count;
+}
+
+static bool _GL_ATTRIBUTE_PURE
+gl_hash_search (gl_map_t map, const void *key, const void **valuep)
+{
+  size_t hashcode =
+    (map->hashcode_fn != NULL
+     ? map->hashcode_fn (key)
+     : (size_t)(uintptr_t) key);
+  size_t bucket = hashcode % map->table_size;
+  gl_mapkey_equals_fn equals = map->base.equals_fn;
+
+  /* Look for a match in the hash bucket.  */
+  gl_list_node_t node;
+
+  for (node = (gl_list_node_t) map->table[bucket];
+       node != NULL;
+       node = (gl_list_node_t) node->h.hash_next)
+    if (node->h.hashcode == hashcode
+        && (equals != NULL
+            ? equals (key, node->key)
+            : key == node->key))
+      {
+        *valuep = node->value;
+        return true;
+      }
+  return false;
+}
+
+static int
+gl_hash_nx_getput (gl_map_t map, const void *key, const void *value,
+                   const void **oldvaluep)
+{
+  size_t hashcode =
+    (map->hashcode_fn != NULL
+     ? map->hashcode_fn (key)
+     : (size_t)(uintptr_t) key);
+  size_t bucket = hashcode % map->table_size;
+  gl_mapkey_equals_fn equals = map->base.equals_fn;
+
+  /* Look for a match in the hash bucket.  */
+  {
+    gl_list_node_t node;
+
+    for (node = (gl_list_node_t) map->table[bucket];
+         node != NULL;
+         node = (gl_list_node_t) node->h.hash_next)
+      if (node->h.hashcode == hashcode
+          && (equals != NULL
+              ? equals (key, node->key)
+              : key == node->key))
+        {
+          *oldvaluep = node->value;
+          node->value = value;
+          return 0;
+        }
+  }
+
+  /* Allocate a new node.  */
+  gl_list_node_t node =
+    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+
+  if (node == NULL)
+    return -1;
+
+  node->key = key;
+  node->value = value;
+  node->h.hashcode = hashcode;
+
+  /* Add node to the hash table.  */
+  node->h.hash_next = map->table[bucket];
+  map->table[bucket] = &node->h;
+
+  /* Add node to the map.  */
+  map->count++;
+
+  hash_resize_after_add (map);
+
+  return 1;
+}
+
+static bool
+gl_hash_getremove (gl_map_t map, const void *key, const void **oldvaluep)
+{
+  size_t hashcode =
+    (map->hashcode_fn != NULL
+     ? map->hashcode_fn (key)
+     : (size_t)(uintptr_t) key);
+  size_t bucket = hashcode % map->table_size;
+  gl_mapkey_equals_fn equals = map->base.equals_fn;
+
+  /* Look for the first match in the hash bucket.  */
+  gl_list_node_t *nodep;
+
+  for (nodep = (gl_list_node_t *) &map->table[bucket];
+       *nodep != NULL;
+       nodep = (gl_list_node_t *) &(*nodep)->h.hash_next)
+    {
+      gl_list_node_t node = *nodep;
+      if (node->h.hashcode == hashcode
+          && (equals != NULL
+              ? equals (key, node->key)
+              : key == node->key))
+        {
+          *oldvaluep = node->value;
+
+          /* Remove node from the hash table.  */
+          *nodep = (gl_list_node_t) node->h.hash_next;
+
+          /* Remove node from the map.  */
+          map->count--;
+
+          if (map->base.kdispose_fn != NULL)
+            map->base.kdispose_fn (node->key);
+          free (node);
+          return true;
+        }
+    }
+
+  return false;
+}
+
+static void
+gl_hash_free (gl_map_t map)
+{
+  if (map->count > 0)
+    {
+      gl_mapkey_dispose_fn kdispose = map->base.kdispose_fn;
+      gl_mapvalue_dispose_fn vdispose = map->base.vdispose_fn;
+      struct gl_hash_entry **table = map->table;
+      size_t i;
+
+      for (i = map->table_size; i > 0; )
+        {
+          gl_hash_entry_t node = table[--i];
+
+          while (node != NULL)
+            {
+              gl_hash_entry_t next = node->hash_next;
+
+              /* Free the entry.  */
+              if (vdispose != NULL)
+                vdispose (((gl_list_node_t) node)->value);
+              if (kdispose != NULL)
+                kdispose (((gl_list_node_t) node)->key);
+              free (node);
+
+              node = next;
+            }
+        }
+    }
+
+  free (map->table);
+  free (map);
+}
+
+/* ---------------------- gl_map_iterator_t Data Type ---------------------- */
+
+/* Here we iterate through the hash buckets.  Therefore the order in which the
+   pairs are returned is unpredictable.  */
+
+static gl_map_iterator_t
+gl_hash_iterator (gl_map_t map)
+{
+  gl_map_iterator_t result;
+
+  result.vtable = map->base.vtable;
+  result.map = map;
+  result.p = NULL;         /* runs through the nodes of a bucket */
+  result.i = 0;            /* index of the bucket that p points into + 1 */
+  result.j = map->table_size;
+#if defined GCC_LINT || defined lint
+  result.q = NULL;
+  result.count = 0;
+#endif
+
+  return result;
+}
+
+static bool
+gl_hash_iterator_next (gl_map_iterator_t *iterator,
+                       const void **keyp, const void **valuep)
+{
+  if (iterator->p != NULL)
+    {
+      /* We're traversing a bucket.  */
+      gl_list_node_t node = (gl_list_node_t) iterator->p;
+      *keyp = node->key;
+      *valuep = node->value;
+      iterator->p = (gl_list_node_t) node->h.hash_next;
+      return true;
+    }
+  else
+    {
+      /* Find the next bucket that is not empty.  */
+      size_t j = iterator->j;
+      size_t i = iterator->i;
+
+      if (i < j)
+        {
+          gl_hash_entry_t *table = iterator->map->table;
+          do
+            {
+              gl_list_node_t node = (gl_list_node_t) table[i++];
+              if (node != NULL)
+                {
+                  *keyp = node->key;
+                  *valuep = node->value;
+                  iterator->p = (gl_list_node_t) node->h.hash_next;
+                  iterator->i = i;
+                  return true;
+                }
+            }
+          while (i < j);
+        }
+      /* Here iterator->p is still NULL, and i == j.  */
+      iterator->i = j;
+      return false;
+    }
+}
+
+static void
+gl_hash_iterator_free (gl_map_iterator_t *iterator)
+{
+}
+
+
+const struct gl_map_implementation gl_hash_map_implementation =
+  {
+    gl_hash_nx_create_empty,
+    gl_hash_size,
+    gl_hash_search,
+    gl_hash_nx_getput,
+    gl_hash_getremove,
+    gl_hash_free,
+    gl_hash_iterator,
+    gl_hash_iterator_next,
+    gl_hash_iterator_free
+  };
diff --git a/lib/gl_hash_map.h b/lib/gl_hash_map.h
new file mode 100644
index 0000000000..1ae80856f3
--- /dev/null
+++ b/lib/gl_hash_map.h
@@ -0,0 +1,34 @@
+/* Map data type implemented by a hash table.
+   Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc.
+   Written by Bruno Haible <bruno@clisp.org>, 2018.
+
+   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 3 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 <https://www.gnu.org/licenses/>.  */
+
+#ifndef _GL_HASH_MAP_H
+#define _GL_HASH_MAP_H
+
+#include "gl_map.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+extern const struct gl_map_implementation gl_hash_map_implementation;
+#define GL_HASH_MAP &gl_hash_map_implementation
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _GL_HASH_MAP_H */
diff --git a/modules/hash-map b/modules/hash-map
new file mode 100644
index 0000000000..5cc5c68acc
--- /dev/null
+++ b/modules/hash-map
@@ -0,0 +1,28 @@
+Description:
+Set data type implemented by a hash table.
+
+Files:
+lib/gl_hash_map.h
+lib/gl_hash_map.c
+lib/gl_anyhash1.h
+lib/gl_anyhash2.h
+lib/gl_anyhash_primes.h
+
+Depends-on:
+map
+stdint
+xsize
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += gl_hash_map.h gl_hash_map.c gl_anyhash1.h gl_anyhash2.h gl_anyhash_primes.h
+
+Include:
+"gl_hash_map.h"
+
+License:
+GPL
+
+Maintainer:
+all