Here comes the last of the five generic container types:
- list
- ordered set
- set
- ordered map
- map
The operations are:
Operation ARRAY LINKEDHASH
HASH
gl_map_size O(1) O(1)
gl_map_get O(n) O(1)
gl_map_put O(n) O(1)
gl_map_remove O(n) O(1)
gl_map_search O(n) O(1)
gl_map_iterator O(1) O(1)
gl_map_iterator_next O(1) O(1)
Review and comments welcome!
Bruno
>From 4d1dabf15bf9a3b5652872340ef85711b877c074 Mon Sep 17 00:00:00 2001
From: Bruno Haible <[email protected]>
Date: Wed, 12 Dec 2018 01:23:21 +0100
Subject: [PATCH 1/8] map: New module.
* lib/gl_map.h: New file.
* lib/gl_map.c: New file.
* lib/gl_omap.h (gl_mapkey_dispose_fn, gl_mapvalue_dispose_fn): Avoid
conflict with gl_map.h.
* modules/map: New file.
---
ChangeLog | 9 ++
lib/gl_map.c | 3 +
lib/gl_map.h | 382 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
lib/gl_omap.h | 5 +
modules/map | 24 ++++
5 files changed, 423 insertions(+)
create mode 100644 lib/gl_map.c
create mode 100644 lib/gl_map.h
create mode 100644 modules/map
diff --git a/ChangeLog b/ChangeLog
index 69a62b5..a49412b 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,14 @@
2018-12-11 Bruno Haible <[email protected]>
+ map: New module.
+ * lib/gl_map.h: New file.
+ * lib/gl_map.c: New file.
+ * lib/gl_omap.h (gl_mapkey_dispose_fn, gl_mapvalue_dispose_fn): Avoid
+ conflict with gl_map.h.
+ * modules/map: New file.
+
+2018-12-11 Bruno Haible <[email protected]>
+
omap: Don't dispose the old value when the function returns it.
* lib/gl_array_omap.c (gl_array_remove_at): Don't invoke the vdispose_fn
here.
diff --git a/lib/gl_map.c b/lib/gl_map.c
new file mode 100644
index 0000000..758a65f
--- /dev/null
+++ b/lib/gl_map.c
@@ -0,0 +1,3 @@
+#include <config.h>
+#define GL_MAP_INLINE _GL_EXTERN_INLINE
+#include "gl_map.h"
diff --git a/lib/gl_map.h b/lib/gl_map.h
new file mode 100644
index 0000000..e14dd65
--- /dev/null
+++ b/lib/gl_map.h
@@ -0,0 +1,382 @@
+/* Abstract map data type.
+ Copyright (C) 2006-2007, 2009-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <[email protected]>, 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_MAP_H
+#define _GL_MAP_H
+
+#include <stdbool.h>
+#include <stddef.h>
+
+#ifndef _GL_INLINE_HEADER_BEGIN
+ #error "Please include config.h first."
+#endif
+_GL_INLINE_HEADER_BEGIN
+#ifndef GL_MAP_INLINE
+# define GL_MAP_INLINE _GL_INLINE
+#endif
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+
+/* gl_map is an abstract map data type. It can contain any number of
+ (key, value) pairs, where
+ - keys and values are objects ('void *' or 'const void *' pointers),
+ - There are no (key, value1) and (key, value2) pairs with the same key
+ (in the sense of a given comparator function).
+
+ There are several implementations of this map datatype, optimized for
+ different operations or for memory. You can start using the simplest map
+ implementation, GL_ARRAY_MAP, and switch to a different implementation
+ later, when you realize which operations are performed the most frequently.
+ The API of the different implementations is exactly the same; when switching
+ to a different implementation, you only have to change the gl_map_create
+ call.
+
+ The implementations are:
+ GL_ARRAY_MAP a growable array
+ GL_LINKEDHASH_MAP a hash table with a linked list
+ GL_HASH_MAP a hash table
+
+ The memory consumption is asymptotically the same: O(1) for every pair
+ in the map. When looking more closely at the average memory consumed
+ for an object, GL_ARRAY_MAP is the most compact representation, then comes
+ GL_HASH_MAP, and GL_LINKEDHASH_MAP needs the most memory.
+
+ The guaranteed average performance of the operations is, for a map of
+ n pairs:
+
+ Operation ARRAY LINKEDHASH
+ HASH
+
+ gl_map_size O(1) O(1)
+ gl_map_get O(n) O(1)
+ gl_map_put O(n) O(1)
+ gl_map_remove O(n) O(1)
+ gl_map_search O(n) O(1)
+ gl_map_iterator O(1) O(1)
+ gl_map_iterator_next O(1) O(1)
+ */
+
+/* --------------------------- gl_map_t Data Type --------------------------- */
+
+/* Type of function used to compare two keys.
+ NULL denotes pointer comparison. */
+typedef bool (*gl_mapkey_equals_fn) (const void *key1, const void *key2);
+
+/* Type of function used to compute a hash code.
+ NULL denotes a function that depends only on the pointer itself. */
+typedef size_t (*gl_mapkey_hashcode_fn) (const void *key);
+
+#ifndef _GL_MAP_DISPOSE_FNS_DEFINED
+
+/* Type of function used to dispose a key once a (key, value) pair is removed
+ from a map. NULL denotes a no-op. */
+typedef void (*gl_mapkey_dispose_fn) (const void *key);
+
+/* Type of function used to dispose a value once a (key, value) pair is removed
+ from a map. NULL denotes a no-op. */
+typedef void (*gl_mapvalue_dispose_fn) (const void *value);
+
+# define _GL_MAP_DISPOSE_FNS_DEFINED 1
+#endif
+
+struct gl_map_impl;
+/* Type representing an entire map. */
+typedef struct gl_map_impl * gl_map_t;
+
+struct gl_map_implementation;
+/* Type representing a map datatype implementation. */
+typedef const struct gl_map_implementation * gl_map_implementation_t;
+
+#if 0 /* Unless otherwise specified, these are defined inline below. */
+
+/* Create an empty map.
+ IMPLEMENTATION is one of GL_ARRAY_MAP, GL_LINKEDHASH_MAP, GL_HASH_MAP.
+ EQUALS_FN is a key comparison function or NULL.
+ HASHCODE_FN is a key hash code function or NULL.
+ KDISPOSE_FN is a key disposal function or NULL.
+ VDISPOSE_FN is a value disposal function or NULL. */
+/* declared in gl_xmap.h */
+extern gl_map_t gl_map_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);
+/* Likewise. Return NULL upon out-of-memory. */
+extern gl_map_t gl_map_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);
+
+/* Return the current number of pairs in a map. */
+extern size_t gl_map_size (gl_map_t map);
+
+/* Search whether a pair with the given key is already in the map.
+ Return the value if found, or NULL if not present in the map. */
+extern const void * gl_map_get (gl_map_t map, const void *key);
+
+/* Search whether a pair with the given key is already in the map.
+ Return true and set *VALUEP to the value if found.
+ Return false if not present in the map. */
+extern bool gl_map_search (gl_map_t map, const void *key, const void **valuep);
+
+/* Add a pair to a map.
+ Return true if a pair with the given key was not already in the map and so
+ this pair was added.
+ Return false if a pair with the given key was already in the map and only
+ its value was replaced. */
+/* declared in gl_xmap.h */
+extern bool gl_map_put (gl_map_t map, const void *key, const void *value);
+/* Likewise. Return -1 upon out-of-memory. */
+extern int gl_map_nx_put (gl_map_t map, const void *key, const void *value)
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+ ;
+
+/* Add a pair to a map and retrieve the previous value.
+ Return true if a pair with the given key was not already in the map and so
+ this pair was added.
+ Return false and set *OLDVALUEP to the previous value, if a pair with the
+ given key was already in the map and only its value was replaced. */
+/* declared in gl_xmap.h */
+extern bool gl_map_getput (gl_map_t map, const void *key, const void *value,
+ const void **oldvaluep);
+/* Likewise. Return -1 upon out-of-memory. */
+extern int gl_map_nx_getput (gl_map_t map, const void *key, const void *value,
+ const void **oldvaluep)
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+ ;
+
+/* Remove a pair from a map.
+ Return true if the key was found and its pair removed.
+ Return false otherwise. */
+extern bool gl_map_remove (gl_map_t map, const void *key);
+
+/* Remove a pair from a map and retrieve the previous value.
+ Return true and set *OLDVALUEP to the previous value, if the key was found
+ and its pair removed.
+ Return false otherwise. */
+extern bool gl_map_getremove (gl_map_t map, const void *key,
+ const void **oldvaluep);
+
+/* Free an entire map.
+ (But this call does not free the keys and values of the pairs in the map.
+ It only invokes the KDISPOSE_FN on each key and the VDISPOSE_FN on each value
+ of the pairs in the map.) */
+extern void gl_map_free (gl_map_t map);
+
+#endif /* End of inline and gl_xmap.h-defined functions. */
+
+/* ---------------------- gl_map_iterator_t Data Type ---------------------- */
+
+/* Functions for iterating through a map.
+ Note: Iterating through a map of type GL_HASH_MAP returns the pairs in an
+ unpredictable order. If you need a predictable order, use GL_LINKEDHASH_MAP
+ instead of GL_HASH_MAP. */
+
+/* Type of an iterator that traverses a map.
+ This is a fixed-size struct, so that creation of an iterator doesn't need
+ memory allocation on the heap. */
+typedef struct
+{
+ /* For fast dispatch of gl_map_iterator_next. */
+ const struct gl_map_implementation *vtable;
+ /* For detecting whether the last returned pair was removed. */
+ gl_map_t map;
+ size_t count;
+ /* Other, implementation-private fields. */
+ void *p; void *q;
+ size_t i; size_t j;
+} gl_map_iterator_t;
+
+#if 0 /* These are defined inline below. */
+
+/* Create an iterator traversing a map.
+ The map's contents must not be modified while the iterator is in use,
+ except for modifying the value of the last returned key or removing the
+ last returned pair. */
+extern gl_map_iterator_t gl_map_iterator (gl_map_t map);
+
+/* If there is a next pair, store the next pair in *KEYP and *VALUEP, advance
+ the iterator, and return true. Otherwise, return false. */
+extern bool gl_map_iterator_next (gl_map_iterator_t *iterator,
+ const void **keyp, const void **valuep);
+
+/* Free an iterator. */
+extern void gl_map_iterator_free (gl_map_iterator_t *iterator);
+
+#endif /* End of inline functions. */
+
+/* ------------------------- Implementation Details ------------------------- */
+
+struct gl_map_implementation
+{
+ /* gl_map_t functions. */
+ gl_map_t (*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);
+ size_t (*size) (gl_map_t map);
+ bool (*search) (gl_map_t map, const void *key, const void **valuep);
+ int (*nx_getput) (gl_map_t map, const void *key, const void *value,
+ const void **oldvaluep);
+ bool (*getremove) (gl_map_t map, const void *key, const void **oldvaluep);
+ void (*map_free) (gl_map_t map);
+ /* gl_map_iterator_t functions. */
+ gl_map_iterator_t (*iterator) (gl_map_t map);
+ bool (*iterator_next) (gl_map_iterator_t *iterator,
+ const void **keyp, const void **valuep);
+ void (*iterator_free) (gl_map_iterator_t *iterator);
+};
+
+struct gl_map_impl_base
+{
+ const struct gl_map_implementation *vtable;
+ gl_mapkey_equals_fn equals_fn;
+ gl_mapkey_dispose_fn kdispose_fn;
+ gl_mapvalue_dispose_fn vdispose_fn;
+};
+
+/* Define most functions of this file as accesses to the
+ struct gl_map_implementation. */
+
+GL_MAP_INLINE gl_map_t
+gl_map_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)
+{
+ return implementation->nx_create_empty (implementation,
+ equals_fn, hashcode_fn,
+ kdispose_fn, vdispose_fn);
+}
+
+GL_MAP_INLINE size_t
+gl_map_size (gl_map_t map)
+{
+ return ((const struct gl_map_impl_base *) map)->vtable->size (map);
+}
+
+GL_MAP_INLINE bool
+gl_map_search (gl_map_t map, const void *key, const void **valuep)
+{
+ return ((const struct gl_map_impl_base *) map)->vtable
+ ->search (map, key, valuep);
+}
+
+GL_MAP_INLINE int
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+gl_map_nx_getput (gl_map_t map, const void *key, const void *value,
+ const void **oldvaluep)
+{
+ return ((const struct gl_map_impl_base *) map)->vtable
+ ->nx_getput (map, key, value, oldvaluep);
+}
+
+GL_MAP_INLINE bool
+gl_map_getremove (gl_map_t map, const void *key, const void **oldvaluep)
+{
+ return ((const struct gl_map_impl_base *) map)->vtable
+ ->getremove (map, key, oldvaluep);
+}
+
+GL_MAP_INLINE void
+gl_map_free (gl_map_t map)
+{
+ ((const struct gl_map_impl_base *) map)->vtable->map_free (map);
+}
+
+GL_MAP_INLINE gl_map_iterator_t
+gl_map_iterator (gl_map_t map)
+{
+ return ((const struct gl_map_impl_base *) map)->vtable->iterator (map);
+}
+
+GL_MAP_INLINE bool
+gl_map_iterator_next (gl_map_iterator_t *iterator,
+ const void **keyp, const void **valuep)
+{
+ return iterator->vtable->iterator_next (iterator, keyp, valuep);
+}
+
+GL_MAP_INLINE void
+gl_map_iterator_free (gl_map_iterator_t *iterator)
+{
+ iterator->vtable->iterator_free (iterator);
+}
+
+/* Define the convenience functions, that is, the functions that are independent
+ of the implementation. */
+
+GL_MAP_INLINE const void *
+gl_map_get (gl_map_t map, const void *key)
+{
+ const void *value = NULL;
+ gl_map_search (map, key, &value);
+ return value;
+}
+
+GL_MAP_INLINE int
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+gl_map_nx_put (gl_map_t map, const void *key, const void *value)
+{
+ const void *oldvalue;
+ int result = gl_map_nx_getput (map, key, value, &oldvalue);
+ if (result == 0)
+ {
+ gl_mapvalue_dispose_fn vdispose_fn =
+ ((const struct gl_map_impl_base *) map)->vdispose_fn;
+ if (vdispose_fn != NULL)
+ vdispose_fn (oldvalue);
+ }
+ return result;
+}
+
+GL_MAP_INLINE bool
+gl_map_remove (gl_map_t map, const void *key)
+{
+ const void *oldvalue;
+ bool result = gl_map_getremove (map, key, &oldvalue);
+ if (result)
+ {
+ gl_mapvalue_dispose_fn vdispose_fn =
+ ((const struct gl_map_impl_base *) map)->vdispose_fn;
+ if (vdispose_fn != NULL)
+ vdispose_fn (oldvalue);
+ }
+ return result;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+_GL_INLINE_HEADER_END
+
+#endif /* _GL_MAP_H */
diff --git a/lib/gl_omap.h b/lib/gl_omap.h
index aa82e33..da41bc4 100644
--- a/lib/gl_omap.h
+++ b/lib/gl_omap.h
@@ -81,6 +81,8 @@ extern "C" {
NULL denotes pointer comparison. */
typedef int (*gl_mapkey_compar_fn) (const void *key1, const void *key2);
+#ifndef _GL_MAP_DISPOSE_FNS_DEFINED
+
/* Type of function used to dispose a key once a (key, value) pair is removed
from a map. NULL denotes a no-op. */
typedef void (*gl_mapkey_dispose_fn) (const void *key);
@@ -89,6 +91,9 @@ typedef void (*gl_mapkey_dispose_fn) (const void *key);
from a map. NULL denotes a no-op. */
typedef void (*gl_mapvalue_dispose_fn) (const void *value);
+# define _GL_MAP_DISPOSE_FNS_DEFINED 1
+#endif
+
/* Type of function used to compare a key with a threshold.
Return true if the key is greater or equal than the threshold. */
typedef bool (*gl_mapkey_threshold_fn) (const void *key, const void *threshold);
diff --git a/modules/map b/modules/map
new file mode 100644
index 0000000..0b611ed
--- /dev/null
+++ b/modules/map
@@ -0,0 +1,24 @@
+Description:
+Abstract map data type.
+
+Files:
+lib/gl_map.h
+lib/gl_map.c
+
+Depends-on:
+extern-inline
+stdbool
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += gl_map.h gl_map.c
+
+Include:
+"gl_map.h"
+
+License:
+GPL
+
+Maintainer:
+all
--
2.7.4
>From e0e9153a933c9c8d135515f5f612ed228d875d01 Mon Sep 17 00:00:00 2001
From: Bruno Haible <[email protected]>
Date: Wed, 12 Dec 2018 01:25:04 +0100
Subject: [PATCH 2/8] array-map: New module.
* lib/gl_array_map.h: New file.
* lib/gl_array_map.c: New file.
* modules/array-map: New file.
---
ChangeLog | 5 +
lib/gl_array_map.c | 299 +++++++++++++++++++++++++++++++++++++++++++++++++++++
lib/gl_array_map.h | 34 ++++++
modules/array-map | 24 +++++
4 files changed, 362 insertions(+)
create mode 100644 lib/gl_array_map.c
create mode 100644 lib/gl_array_map.h
create mode 100644 modules/array-map
diff --git a/ChangeLog b/ChangeLog
index a49412b..a24e5c1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,10 @@
2018-12-11 Bruno Haible <[email protected]>
+ array-map: New module.
+ * lib/gl_array_map.h: New file.
+ * lib/gl_array_map.c: New file.
+ * modules/array-map: New file.
+
map: New module.
* lib/gl_map.h: New file.
* lib/gl_map.c: New file.
diff --git a/lib/gl_array_map.c b/lib/gl_array_map.c
new file mode 100644
index 0000000..e855c66
--- /dev/null
+++ b/lib/gl_array_map.c
@@ -0,0 +1,299 @@
+/* Map data type implemented by an array.
+ Copyright (C) 2006-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <[email protected]>, 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_array_map.h"
+
+#include <stdlib.h>
+
+/* Checked size_t computations. */
+#include "xsize.h"
+
+#ifndef uintptr_t
+# define uintptr_t unsigned long
+#endif
+
+/* --------------------------- gl_map_t Data Type --------------------------- */
+
+struct pair
+{
+ const void *key;
+ const void *value;
+};
+
+/* Concrete gl_map_impl type, valid for this file only. */
+struct gl_map_impl
+{
+ struct gl_map_impl_base base;
+ /* An array of ALLOCATED pairs, of which the first COUNT are used.
+ 0 <= COUNT <= ALLOCATED. */
+ struct pair *pairs;
+ size_t count;
+ size_t allocated;
+};
+
+static gl_map_t
+gl_array_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->pairs = NULL;
+ map->count = 0;
+ map->allocated = 0;
+
+ return map;
+}
+
+static size_t
+gl_array_size (gl_map_t map)
+{
+ return map->count;
+}
+
+static size_t
+gl_array_indexof (gl_map_t map, const void *key)
+{
+ size_t count = map->count;
+
+ if (count > 0)
+ {
+ gl_mapkey_equals_fn equals = map->base.equals_fn;
+ if (equals != NULL)
+ {
+ size_t i;
+
+ for (i = 0; i < count; i++)
+ if (equals (map->pairs[i].key, key))
+ return i;
+ }
+ else
+ {
+ size_t i;
+
+ for (i = 0; i < count; i++)
+ if (map->pairs[i].key == key)
+ return i;
+ }
+ }
+ return (size_t)(-1);
+}
+
+static bool
+gl_array_search (gl_map_t map, const void *key, const void **valuep)
+{
+ size_t index = gl_array_indexof (map, key);
+ if (index != (size_t)(-1))
+ {
+ *valuep = map->pairs[index].value;
+ return true;
+ }
+ else
+ return false;
+}
+
+/* Ensure that map->allocated > map->count.
+ Return 0 upon success, -1 upon out-of-memory. */
+static int
+grow (gl_map_t map)
+{
+ size_t new_allocated;
+ size_t memory_size;
+ struct pair *memory;
+
+ new_allocated = xtimes (map->allocated, 2);
+ new_allocated = xsum (new_allocated, 1);
+ memory_size = xtimes (new_allocated, sizeof (struct pair));
+ if (size_overflow_p (memory_size))
+ /* Overflow, would lead to out of memory. */
+ return -1;
+ memory = (struct pair *) realloc (map->pairs, memory_size);
+ if (memory == NULL)
+ /* Out of memory. */
+ return -1;
+ map->pairs = memory;
+ map->allocated = new_allocated;
+ return 0;
+}
+
+static int
+gl_array_nx_getput (gl_map_t map, const void *key, const void *value,
+ const void **oldvaluep)
+{
+ size_t index = gl_array_indexof (map, key);
+ if (index != (size_t)(-1))
+ {
+ *oldvaluep = map->pairs[index].value;
+ map->pairs[index].value = value;
+ return 0;
+ }
+ else
+ {
+ size_t count = map->count;
+ struct pair *pairs;
+
+ if (count == map->allocated)
+ if (grow (map) < 0)
+ return -1;
+ pairs = map->pairs;
+ pairs[count].key = key;
+ pairs[count].value = value;
+ map->count = count + 1;
+ return 1;
+ }
+}
+
+/* Remove the pair at the given position,
+ 0 <= position < gl_map_size (map). */
+static void
+gl_array_remove_at (gl_map_t map, size_t position)
+{
+ size_t count = map->count;
+ struct pair *pairs;
+ size_t i;
+
+ pairs = map->pairs;
+ if (map->base.kdispose_fn != NULL)
+ map->base.kdispose_fn (pairs[position].key);
+ for (i = position + 1; i < count; i++)
+ pairs[i - 1] = pairs[i];
+ map->count = count - 1;
+}
+
+static bool
+gl_array_getremove (gl_map_t map, const void *key, const void **oldvaluep)
+{
+ size_t index = gl_array_indexof (map, key);
+ if (index != (size_t)(-1))
+ {
+ *oldvaluep = map->pairs[index].value;
+ gl_array_remove_at (map, index);
+ return true;
+ }
+ else
+ return false;
+}
+
+static void
+gl_array_free (gl_map_t map)
+{
+ if (map->pairs != NULL)
+ {
+ if (map->base.kdispose_fn != NULL || map->base.vdispose_fn != NULL)
+ {
+ size_t count = map->count;
+
+ if (count > 0)
+ {
+ gl_mapkey_dispose_fn kdispose = map->base.kdispose_fn;
+ gl_mapvalue_dispose_fn vdispose = map->base.vdispose_fn;
+ struct pair *pairs = map->pairs;
+
+ do
+ {
+ if (vdispose)
+ vdispose (pairs->value);
+ if (kdispose)
+ kdispose (pairs->key);
+ pairs++;
+ }
+ while (--count > 0);
+ }
+ }
+ free (map->pairs);
+ }
+ free (map);
+}
+
+/* ---------------------- gl_map_iterator_t Data Type ---------------------- */
+
+static gl_map_iterator_t
+gl_array_iterator (gl_map_t map)
+{
+ gl_map_iterator_t result;
+
+ result.vtable = map->base.vtable;
+ result.map = map;
+ result.count = map->count;
+ result.p = map->pairs + 0;
+ result.q = map->pairs + map->count;
+#if defined GCC_LINT || defined lint
+ result.i = 0;
+ result.j = 0;
+#endif
+
+ return result;
+}
+
+static bool
+gl_array_iterator_next (gl_map_iterator_t *iterator,
+ const void **keyp, const void **valuep)
+{
+ gl_map_t map = iterator->map;
+ if (iterator->count != map->count)
+ {
+ if (iterator->count != map->count + 1)
+ /* Concurrent modifications were done on the map. */
+ abort ();
+ /* The last returned pair was removed. */
+ iterator->count--;
+ iterator->p = (struct pair *) iterator->p - 1;
+ iterator->q = (struct pair *) iterator->q - 1;
+ }
+ if (iterator->p < iterator->q)
+ {
+ struct pair *p = (struct pair *) iterator->p;
+ *keyp = p->key;
+ *valuep = p->value;
+ iterator->p = p + 1;
+ return true;
+ }
+ else
+ return false;
+}
+
+static void
+gl_array_iterator_free (gl_map_iterator_t *iterator)
+{
+}
+
+
+const struct gl_map_implementation gl_array_map_implementation =
+ {
+ gl_array_nx_create_empty,
+ gl_array_size,
+ gl_array_search,
+ gl_array_nx_getput,
+ gl_array_getremove,
+ gl_array_free,
+ gl_array_iterator,
+ gl_array_iterator_next,
+ gl_array_iterator_free
+ };
diff --git a/lib/gl_array_map.h b/lib/gl_array_map.h
new file mode 100644
index 0000000..e9ff412
--- /dev/null
+++ b/lib/gl_array_map.h
@@ -0,0 +1,34 @@
+/* Map data type implemented by an array.
+ Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <[email protected]>, 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_ARRAY_MAP_H
+#define _GL_ARRAY_MAP_H
+
+#include "gl_map.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+extern const struct gl_map_implementation gl_array_map_implementation;
+#define GL_ARRAY_MAP &gl_array_map_implementation
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _GL_ARRAY_MAP_H */
diff --git a/modules/array-map b/modules/array-map
new file mode 100644
index 0000000..abdef16
--- /dev/null
+++ b/modules/array-map
@@ -0,0 +1,24 @@
+Description:
+Set data type implemented by an array.
+
+Files:
+lib/gl_array_map.h
+lib/gl_array_map.c
+
+Depends-on:
+map
+xsize
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += gl_array_map.h gl_array_map.c
+
+Include:
+"gl_array_map.h"
+
+License:
+GPL
+
+Maintainer:
+all
--
2.7.4
>From 4d2c4598b2c8d1a726dd2480f6ee06c1f32ddd92 Mon Sep 17 00:00:00 2001
From: Bruno Haible <[email protected]>
Date: Wed, 12 Dec 2018 01:27:08 +0100
Subject: [PATCH 3/8] linkedhash-map: New module.
* lib/gl_linkedhash_map.h: New file.
* lib/gl_linkedhash_map.c: New file.
* lib/gl_anyhash1.h: Update comments.
* lib/gl_anyhash2.h: Likewise.
* modules/linkedhash-map: New file.
---
ChangeLog | 7 +
lib/gl_anyhash1.h | 3 +-
lib/gl_anyhash2.h | 3 +-
lib/gl_linkedhash_map.c | 334 ++++++++++++++++++++++++++++++++++++++++++++++++
lib/gl_linkedhash_map.h | 34 +++++
modules/linkedhash-map | 28 ++++
6 files changed, 407 insertions(+), 2 deletions(-)
create mode 100644 lib/gl_linkedhash_map.c
create mode 100644 lib/gl_linkedhash_map.h
create mode 100644 modules/linkedhash-map
diff --git a/ChangeLog b/ChangeLog
index a24e5c1..4b7407e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,12 @@
2018-12-11 Bruno Haible <[email protected]>
+ linkedhash-map: New module.
+ * lib/gl_linkedhash_map.h: New file.
+ * lib/gl_linkedhash_map.c: New file.
+ * lib/gl_anyhash1.h: Update comments.
+ * lib/gl_anyhash2.h: Likewise.
+ * modules/linkedhash-map: New file.
+
array-map: New module.
* lib/gl_array_map.h: New file.
* lib/gl_array_map.c: New file.
diff --git a/lib/gl_anyhash1.h b/lib/gl_anyhash1.h
index 86bdee3..dda29fe 100644
--- a/lib/gl_anyhash1.h
+++ b/lib/gl_anyhash1.h
@@ -17,7 +17,8 @@
/* Common code of
gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c,
- gl_linkedhash_set.c, gl_hash_set.c. */
+ gl_linkedhash_set.c, gl_hash_set.c,
+ gl_linkedhash_map.c, gl_hash_map.c. */
/* Hash table entry. */
struct gl_hash_entry
diff --git a/lib/gl_anyhash2.h b/lib/gl_anyhash2.h
index d4c5430..c7ece04 100644
--- a/lib/gl_anyhash2.h
+++ b/lib/gl_anyhash2.h
@@ -17,7 +17,8 @@
/* Common code of
gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c,
- gl_linkedhash_set.c, gl_hash_set.c. */
+ gl_linkedhash_set.c, gl_hash_set.c,
+ gl_linkedhash_map.c, gl_hash_map.c. */
#include "gl_anyhash_primes.h"
diff --git a/lib/gl_linkedhash_map.c b/lib/gl_linkedhash_map.c
new file mode 100644
index 0000000..2cf3199
--- /dev/null
+++ b/lib/gl_linkedhash_map.c
@@ -0,0 +1,334 @@
+/* Map data type implemented by a hash table with a linked list.
+ Copyright (C) 2006, 2008-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <[email protected]>, 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_linkedhash_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 */
+ struct gl_list_node_impl *next;
+ struct gl_list_node_impl *prev;
+ 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;
+ /* A circular list anchored at root.
+ The first node is = root.next, the last node is = root.prev.
+ The root's value is unused. */
+ struct gl_list_node_impl root;
+ /* Number of list nodes, excluding the root. */
+ size_t count;
+};
+
+#define CONTAINER_T gl_map_t
+#define CONTAINER_COUNT(map) (map)->count
+#include "gl_anyhash2.h"
+
+/* If the symbol SIGNAL_SAFE_MAP is defined, the code is compiled in such
+ a way that a gl_map_t data structure may be used from within a signal
+ handler. The operations allowed in the signal handler are:
+ gl_map_iterator, gl_map_iterator_next, gl_map_iterator_free.
+ The map and node fields that are therefore accessed from the signal handler
+ are:
+ map->root, node->next, node->value.
+ We are careful to make modifications to these fields only in an order
+ that maintains the consistency of the list data structure at any moment,
+ and we use 'volatile' assignments to prevent the compiler from reordering
+ such assignments. */
+#ifdef SIGNAL_SAFE_MAP
+# define ASYNCSAFE(type) *(type volatile *)&
+#else
+# define ASYNCSAFE(type)
+#endif
+
+/* --------------------------- gl_map_t Data Type --------------------------- */
+
+static gl_map_t
+gl_linkedhash_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->root.next = &map->root;
+ map->root.prev = &map->root;
+ map->count = 0;
+
+ return map;
+
+ fail:
+ free (map);
+ return NULL;
+}
+
+static size_t _GL_ATTRIBUTE_PURE
+gl_linkedhash_size (gl_map_t map)
+{
+ return map->count;
+}
+
+static bool _GL_ATTRIBUTE_PURE
+gl_linkedhash_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_linkedhash_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;
+
+ ASYNCSAFE(const void *) node->key = key;
+ ASYNCSAFE(const void *) 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. */
+ ASYNCSAFE(gl_list_node_t) node->next = &map->root;
+ node->prev = map->root.prev;
+ ASYNCSAFE(gl_list_node_t) node->prev->next = node;
+ map->root.prev = node;
+ map->count++;
+
+ hash_resize_after_add (map);
+
+ return 1;
+}
+
+static bool
+gl_linkedhash_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 list. */
+ {
+ gl_list_node_t prev = node->prev;
+ gl_list_node_t next = node->next;
+
+ ASYNCSAFE(gl_list_node_t) prev->next = next;
+ next->prev = prev;
+ }
+ map->count--;
+
+ if (map->base.kdispose_fn != NULL)
+ map->base.kdispose_fn (node->key);
+ free (node);
+ return true;
+ }
+ }
+
+ return false;
+}
+
+static void
+gl_linkedhash_free (gl_map_t map)
+{
+ gl_mapkey_dispose_fn kdispose = map->base.kdispose_fn;
+ gl_mapvalue_dispose_fn vdispose = map->base.vdispose_fn;
+ gl_list_node_t node;
+
+ for (node = map->root.next; node != &map->root; )
+ {
+ gl_list_node_t next = node->next;
+ if (vdispose != NULL)
+ vdispose (node->value);
+ if (kdispose != NULL)
+ kdispose (node->key);
+ free (node);
+ node = next;
+ }
+ free (map->table);
+ free (map);
+}
+
+/* ---------------------- gl_map_iterator_t Data Type ---------------------- */
+
+/* Iterate through the list, not through the hash buckets, so that the order
+ in which the pairs are returned is predictable. */
+
+static gl_map_iterator_t
+gl_linkedhash_iterator (gl_map_t map)
+{
+ gl_map_iterator_t result;
+
+ result.vtable = map->base.vtable;
+ result.map = map;
+ result.p = map->root.next;
+ result.q = &map->root;
+#if defined GCC_LINT || defined lint
+ result.i = 0;
+ result.j = 0;
+ result.count = 0;
+#endif
+
+ return result;
+}
+
+static bool
+gl_linkedhash_iterator_next (gl_map_iterator_t *iterator,
+ const void **keyp, const void **valuep)
+{
+ if (iterator->p != iterator->q)
+ {
+ gl_list_node_t node = (gl_list_node_t) iterator->p;
+ *keyp = node->key;
+ *valuep = node->value;
+ iterator->p = node->next;
+ return true;
+ }
+ else
+ return false;
+}
+
+static void
+gl_linkedhash_iterator_free (gl_map_iterator_t *iterator)
+{
+}
+
+
+const struct gl_map_implementation gl_linkedhash_map_implementation =
+ {
+ gl_linkedhash_nx_create_empty,
+ gl_linkedhash_size,
+ gl_linkedhash_search,
+ gl_linkedhash_nx_getput,
+ gl_linkedhash_getremove,
+ gl_linkedhash_free,
+ gl_linkedhash_iterator,
+ gl_linkedhash_iterator_next,
+ gl_linkedhash_iterator_free
+ };
diff --git a/lib/gl_linkedhash_map.h b/lib/gl_linkedhash_map.h
new file mode 100644
index 0000000..4ea98ba
--- /dev/null
+++ b/lib/gl_linkedhash_map.h
@@ -0,0 +1,34 @@
+/* Map data type implemented by a hash table with a linked list.
+ Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <[email protected]>, 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_LINKEDHASH_MAP_H
+#define _GL_LINKEDHASH_MAP_H
+
+#include "gl_map.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+extern const struct gl_map_implementation gl_linkedhash_map_implementation;
+#define GL_LINKEDHASH_MAP &gl_linkedhash_map_implementation
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _GL_LINKEDHASH_MAP_H */
diff --git a/modules/linkedhash-map b/modules/linkedhash-map
new file mode 100644
index 0000000..3424660
--- /dev/null
+++ b/modules/linkedhash-map
@@ -0,0 +1,28 @@
+Description:
+Set data type implemented by a hash table with a linked list.
+
+Files:
+lib/gl_linkedhash_map.h
+lib/gl_linkedhash_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_linkedhash_map.h gl_linkedhash_map.c gl_anyhash1.h gl_anyhash2.h gl_anyhash_primes.h
+
+Include:
+"gl_linkedhash_map.h"
+
+License:
+GPL
+
+Maintainer:
+all
--
2.7.4
>From b23673c63782f8468fb8261fbab9f7bab3758609 Mon Sep 17 00:00:00 2001
From: Bruno Haible <[email protected]>
Date: Wed, 12 Dec 2018 01:27:47 +0100
Subject: [PATCH 4/8] hash-map: New module.
* lib/gl_hash_map.h: New file.
* lib/gl_hash_map.c: New file.
* modules/hash-map: New file.
---
ChangeLog | 5 +
lib/gl_hash_map.c | 337 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
lib/gl_hash_map.h | 34 ++++++
modules/hash-map | 28 +++++
4 files changed, 404 insertions(+)
create mode 100644 lib/gl_hash_map.c
create mode 100644 lib/gl_hash_map.h
create mode 100644 modules/hash-map
diff --git a/ChangeLog b/ChangeLog
index 4b7407e..817998e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,10 @@
2018-12-11 Bruno Haible <[email protected]>
+ 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 0000000..7d68e7b
--- /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 <[email protected]>, 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 0000000..1ae8085
--- /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 <[email protected]>, 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 0000000..5cc5c68
--- /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
--
2.7.4
>From 3b4e211ff049fb5d1a5a92a04b96952c28c7e06b Mon Sep 17 00:00:00 2001
From: Bruno Haible <[email protected]>
Date: Wed, 12 Dec 2018 01:29:10 +0100
Subject: [PATCH 5/8] xmap: New module.
* lib/gl_xmap.h: New file.
* lib/gl_xmap.c: New file.
* modules/xmap: New file.
---
ChangeLog | 5 ++++
lib/gl_xmap.c | 3 ++
lib/gl_xmap.h | 91 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
modules/xmap | 26 +++++++++++++++++
4 files changed, 125 insertions(+)
create mode 100644 lib/gl_xmap.c
create mode 100644 lib/gl_xmap.h
create mode 100644 modules/xmap
diff --git a/ChangeLog b/ChangeLog
index 817998e..8e3189e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,10 @@
2018-12-11 Bruno Haible <[email protected]>
+ xmap: New module.
+ * lib/gl_xmap.h: New file.
+ * lib/gl_xmap.c: New file.
+ * modules/xmap: New file.
+
hash-map: New module.
* lib/gl_hash_map.h: New file.
* lib/gl_hash_map.c: New file.
diff --git a/lib/gl_xmap.c b/lib/gl_xmap.c
new file mode 100644
index 0000000..3d39fdb
--- /dev/null
+++ b/lib/gl_xmap.c
@@ -0,0 +1,3 @@
+#include <config.h>
+#define GL_XMAP_INLINE _GL_EXTERN_INLINE
+#include "gl_xmap.h"
diff --git a/lib/gl_xmap.h b/lib/gl_xmap.h
new file mode 100644
index 0000000..6eb7fff
--- /dev/null
+++ b/lib/gl_xmap.h
@@ -0,0 +1,91 @@
+/* Abstract map data type, with out-of-memory checking.
+ Copyright (C) 2009-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <[email protected]>, 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_XMAP_H
+#define _GL_XMAP_H
+
+#include "gl_map.h"
+#include "xalloc.h"
+
+#ifndef _GL_INLINE_HEADER_BEGIN
+ #error "Please include config.h first."
+#endif
+_GL_INLINE_HEADER_BEGIN
+#ifndef GL_XMAP_INLINE
+# define GL_XMAP_INLINE _GL_INLINE
+#endif
+
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* These functions are thin wrappers around the corresponding functions with
+ _nx_ infix from gl_map.h. Upon out-of-memory, they invoke xalloc_die (),
+ instead of returning an error indicator. */
+#if 0 /* These are defined inline below. */
+extern gl_map_t gl_map_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);
+extern bool gl_map_put (gl_map_t map, const void *key, const void *value);
+extern bool gl_map_getput (gl_map_t map, const void *key, const void *value,
+ const void **oldvaluep);
+#endif
+
+GL_XMAP_INLINE gl_map_t
+gl_map_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)
+{
+ gl_map_t result =
+ gl_map_nx_create_empty (implementation, equals_fn, hashcode_fn,
+ kdispose_fn, vdispose_fn);
+ if (result == NULL)
+ xalloc_die ();
+ return result;
+}
+
+GL_XMAP_INLINE bool
+gl_map_put (gl_map_t map, const void *key, const void *value)
+{
+ int result = gl_map_nx_put (map, key, value);
+ if (result < 0)
+ xalloc_die ();
+ return result;
+}
+
+GL_XMAP_INLINE bool
+gl_map_getput (gl_map_t map, const void *key, const void *value,
+ const void **oldvaluep)
+{
+ int result = gl_map_nx_getput (map, key, value, oldvaluep);
+ if (result < 0)
+ xalloc_die ();
+ return result;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+_GL_INLINE_HEADER_END
+
+#endif /* _GL_XMAP_H */
diff --git a/modules/xmap b/modules/xmap
new file mode 100644
index 0000000..2a7cead
--- /dev/null
+++ b/modules/xmap
@@ -0,0 +1,26 @@
+Description:
+Abstract map data type, with out-of-memory checking.
+
+Files:
+lib/gl_xmap.h
+lib/gl_xmap.c
+
+Depends-on:
+map
+extern-inline
+stdbool
+xalloc-die
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += gl_xmap.h gl_xmap.c
+
+Include:
+"gl_xmap.h"
+
+License:
+GPL
+
+Maintainer:
+all
--
2.7.4
>From 4e8100e0fd4594a43f841403de8006d08e7f930b Mon Sep 17 00:00:00 2001
From: Bruno Haible <[email protected]>
Date: Wed, 12 Dec 2018 01:29:52 +0100
Subject: [PATCH 6/8] array-map: Add tests.
* tests/test-array_map.c: New file.
* modules/array-map-tests: New file.
---
ChangeLog | 4 +
modules/array-map-tests | 14 ++++
tests/test-array_map.c | 219 ++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 237 insertions(+)
create mode 100644 modules/array-map-tests
create mode 100644 tests/test-array_map.c
diff --git a/ChangeLog b/ChangeLog
index 8e3189e..c9ddd7c 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,9 @@
2018-12-11 Bruno Haible <[email protected]>
+ array-map: Add tests.
+ * tests/test-array_map.c: New file.
+ * modules/array-map-tests: New file.
+
xmap: New module.
* lib/gl_xmap.h: New file.
* lib/gl_xmap.c: New file.
diff --git a/modules/array-map-tests b/modules/array-map-tests
new file mode 100644
index 0000000..7dbcd73
--- /dev/null
+++ b/modules/array-map-tests
@@ -0,0 +1,14 @@
+Files:
+tests/test-array_map.c
+tests/macros.h
+
+Depends-on:
+xlist
+array-list
+xalloc
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-array_map
+check_PROGRAMS += test-array_map
diff --git a/tests/test-array_map.c b/tests/test-array_map.c
new file mode 100644
index 0000000..5a35d2a
--- /dev/null
+++ b/tests/test-array_map.c
@@ -0,0 +1,219 @@
+/* Test of map data type implementation.
+ Copyright (C) 2006-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <[email protected]>, 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>
+
+#include "gl_array_map.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "gl_xlist.h"
+#include "gl_array_list.h"
+#include "macros.h"
+
+static const char *objects[30] =
+ {
+ "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o",
+ "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "<", ">", "[", "]"
+ };
+
+#define SIZE_BITS (sizeof (size_t) * CHAR_BIT)
+
+static bool
+string_equals (const void *x1, const void *x2)
+{
+ const char *s1 = x1;
+ const char *s2 = x2;
+ return strcmp (s1, s2) == 0;
+}
+
+/* A hash function for NUL-terminated char* strings using
+ the method described by Bruno Haible.
+ See https://www.haible.de/bruno/hashfunc.html. */
+static size_t
+string_hash (const void *x)
+{
+ const char *s = x;
+ size_t h = 0;
+
+ for (; *s; s++)
+ h = *s + ((h << 9) | (h >> (SIZE_BITS - 9)));
+
+ return h;
+}
+
+#define RANDOM(n) (rand () % (n))
+#define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
+
+struct pair
+{
+ const void *key;
+ const void *value;
+};
+
+static int
+cmp_pairs_in_array (const void *pairptr1, const void *pairptr2)
+{
+ const void *key1 = ((struct pair const *)pairptr1)->key;
+ const void *key2 = ((struct pair const *)pairptr2)->key;
+ return strcmp ((const char *) key1, (const char *) key2);
+}
+
+static void
+check_equals (gl_map_t map1, gl_list_t keys, gl_list_t values)
+{
+ size_t n = gl_map_size (map1);
+ struct pair *pairs_of_map1 = XNMALLOC (n, struct pair);
+
+ gl_map_iterator_t iter1;
+ const void *key1;
+ const void *value1;
+ size_t i;
+
+ ASSERT (gl_list_size (keys) == n);
+ ASSERT (gl_list_size (values) == n);
+ iter1 = gl_map_iterator (map1);
+ for (i = 0; i < n; i++)
+ {
+ ASSERT (gl_map_iterator_next (&iter1, &key1, &value1));
+ pairs_of_map1[i].key = key1;
+ pairs_of_map1[i].value = value1;
+ }
+ ASSERT (!gl_map_iterator_next (&iter1, &key1, &value1));
+ gl_map_iterator_free (&iter1);
+
+ if (n > 0)
+ qsort (pairs_of_map1, n, sizeof (struct pair), cmp_pairs_in_array);
+ for (i = 0; i < n; i++)
+ {
+ ASSERT (pairs_of_map1[i].key == gl_list_get_at (keys, i));
+ ASSERT (pairs_of_map1[i].value == gl_list_get_at (values, i));
+ }
+ free (pairs_of_map1);
+}
+
+static void
+check_all (gl_map_t map1, gl_list_t keys, gl_list_t values)
+{
+ check_equals (map1, keys, values);
+}
+
+int
+main (int argc, char *argv[])
+{
+ gl_map_t map1;
+ gl_list_t keys;
+ gl_list_t values;
+
+ /* Allow the user to provide a non-default random seed on the command line. */
+ if (argc > 1)
+ srand (atoi (argv[1]));
+
+ {
+ size_t initial_size = RANDOM (20);
+ size_t i;
+ unsigned int repeat;
+
+ /* Create map1. */
+ map1 = gl_map_nx_create_empty (GL_ARRAY_MAP,
+ string_equals, string_hash, NULL, NULL);
+ ASSERT (map1 != NULL);
+
+ /* Create keys and values. */
+ keys = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, false);
+ values = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, false);
+
+ check_all (map1, keys, values);
+
+ /* Initialize them. */
+ for (i = 0; i < initial_size; i++)
+ {
+ const char *key = RANDOM_OBJECT ();
+ const char *value = RANDOM_OBJECT ();
+ bool added = gl_map_nx_put (map1, key, value);
+ size_t index = gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
+ ASSERT (added == (index == (size_t)(-1)));
+ if (added)
+ {
+ gl_sortedlist_add (keys, (gl_listelement_compar_fn)strcmp, key);
+ index = gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
+ gl_list_add_at (values, index, value);
+ }
+ else
+ gl_list_set_at (values, index, value);
+ check_all (map1, keys, values);
+ }
+
+ for (repeat = 0; repeat < 100000; repeat++)
+ {
+ unsigned int operation = RANDOM (3);
+ switch (operation)
+ {
+ case 0:
+ {
+ const char *key = RANDOM_OBJECT ();
+ const void *ret = gl_map_get (map1, key);
+ size_t index =
+ gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
+ ASSERT (ret
+ == (index != (size_t)(-1) ? gl_list_get_at (values, index) : NULL));
+ }
+ break;
+ case 1:
+ {
+ const char *key = RANDOM_OBJECT ();
+ const char *value = RANDOM_OBJECT ();
+ bool added = gl_map_nx_put (map1, key, value);
+ size_t index =
+ gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
+ ASSERT (added == (index == (size_t)(-1)));
+ if (added)
+ {
+ gl_sortedlist_add (keys, (gl_listelement_compar_fn)strcmp, key);
+ index = gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
+ gl_list_add_at (values, index, value);
+ }
+ else
+ gl_list_set_at (values, index, value);
+ }
+ break;
+ case 2:
+ {
+ const char *key = RANDOM_OBJECT ();
+ bool removed = gl_map_remove (map1, key);
+ size_t index =
+ gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
+ ASSERT (removed == (index != (size_t)(-1)));
+ if (removed)
+ {
+ gl_list_remove_at (keys, index);
+ gl_list_remove_at (values, index);
+ }
+ }
+ break;
+ }
+ check_all (map1, keys, values);
+ }
+
+ gl_map_free (map1);
+ gl_list_free (keys);
+ gl_list_free (values);
+ }
+
+ return 0;
+}
--
2.7.4
>From 83824758898696aa9d3825b8d885205233d73812 Mon Sep 17 00:00:00 2001
From: Bruno Haible <[email protected]>
Date: Wed, 12 Dec 2018 01:30:25 +0100
Subject: [PATCH 7/8] linkedhash-map: Add tests.
* tests/test-linkedhash_map.c: New file.
* modules/linkedhash-map-tests: New file.
---
ChangeLog | 4 +
modules/linkedhash-map-tests | 13 +++
tests/test-linkedhash_map.c | 195 +++++++++++++++++++++++++++++++++++++++++++
3 files changed, 212 insertions(+)
create mode 100644 modules/linkedhash-map-tests
create mode 100644 tests/test-linkedhash_map.c
diff --git a/ChangeLog b/ChangeLog
index c9ddd7c..9a706f6 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,9 @@
2018-12-11 Bruno Haible <[email protected]>
+ linkedhash-map: Add tests.
+ * tests/test-linkedhash_map.c: New file.
+ * modules/linkedhash-map-tests: New file.
+
array-map: Add tests.
* tests/test-array_map.c: New file.
* modules/array-map-tests: New file.
diff --git a/modules/linkedhash-map-tests b/modules/linkedhash-map-tests
new file mode 100644
index 0000000..a21dad3
--- /dev/null
+++ b/modules/linkedhash-map-tests
@@ -0,0 +1,13 @@
+Files:
+tests/test-linkedhash_map.c
+tests/macros.h
+
+Depends-on:
+array-map
+xalloc
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-linkedhash_map
+check_PROGRAMS += test-linkedhash_map
diff --git a/tests/test-linkedhash_map.c b/tests/test-linkedhash_map.c
new file mode 100644
index 0000000..780105e
--- /dev/null
+++ b/tests/test-linkedhash_map.c
@@ -0,0 +1,195 @@
+/* Test of map data type implementation.
+ Copyright (C) 2006-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <[email protected]>, 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>
+
+#include "gl_linkedhash_map.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "gl_array_map.h"
+#include "xalloc.h"
+#include "macros.h"
+
+static const char *objects[30] =
+ {
+ "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o",
+ "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "<", ">", "[", "]"
+ };
+
+#define SIZE_BITS (sizeof (size_t) * CHAR_BIT)
+
+static bool
+string_equals (const void *x1, const void *x2)
+{
+ const char *s1 = x1;
+ const char *s2 = x2;
+ return strcmp (s1, s2) == 0;
+}
+
+/* A hash function for NUL-terminated char* strings using
+ the method described by Bruno Haible.
+ See https://www.haible.de/bruno/hashfunc.html. */
+static size_t
+string_hash (const void *x)
+{
+ const char *s = x;
+ size_t h = 0;
+
+ for (; *s; s++)
+ h = *s + ((h << 9) | (h >> (SIZE_BITS - 9)));
+
+ return h;
+}
+
+#define RANDOM(n) (rand () % (n))
+#define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
+
+struct pair
+{
+ const void *key;
+ const void *value;
+};
+
+static int
+cmp_pairs_in_array (const void *pairptr1, const void *pairptr2)
+{
+ const void *key1 = ((struct pair const *)pairptr1)->key;
+ const void *key2 = ((struct pair const *)pairptr2)->key;
+ return strcmp ((const char *) key1, (const char *) key2);
+}
+
+static void
+check_equals (gl_map_t map1, gl_map_t map2)
+{
+ size_t n = gl_map_size (map1);
+ struct pair *pairs_of_map1 = XNMALLOC (n, struct pair);
+ struct pair *pairs_of_map2 = XNMALLOC (n, struct pair);
+
+ gl_map_iterator_t iter1, iter2;
+ const void *key1;
+ const void *value1;
+ const void *key2;
+ const void *value2;
+ size_t i;
+
+ iter1 = gl_map_iterator (map1);
+ iter2 = gl_map_iterator (map2);
+ for (i = 0; i < n; i++)
+ {
+ ASSERT (gl_map_iterator_next (&iter1, &key1, &value1));
+ ASSERT (gl_map_iterator_next (&iter2, &key2, &value2));
+ pairs_of_map1[i].key = key1;
+ pairs_of_map1[i].value = value1;
+ pairs_of_map2[i].key = key2;
+ pairs_of_map2[i].value = value2;
+ }
+ ASSERT (!gl_map_iterator_next (&iter1, &key1, &value1));
+ ASSERT (!gl_map_iterator_next (&iter2, &key2, &value2));
+ gl_map_iterator_free (&iter1);
+ gl_map_iterator_free (&iter2);
+
+ if (n > 0)
+ {
+ qsort (pairs_of_map1, n, sizeof (struct pair), cmp_pairs_in_array);
+ qsort (pairs_of_map2, n, sizeof (struct pair), cmp_pairs_in_array);
+ }
+ for (i = 0; i < n; i++)
+ {
+ ASSERT (pairs_of_map1[i].key == pairs_of_map2[i].key);
+ ASSERT (pairs_of_map1[i].value == pairs_of_map2[i].value);
+ }
+ free (pairs_of_map2);
+ free (pairs_of_map1);
+}
+
+static void
+check_all (gl_map_t map1, gl_map_t map2)
+{
+ check_equals (map1, map2);
+}
+
+int
+main (int argc, char *argv[])
+{
+ gl_map_t map1, map2;
+
+ /* Allow the user to provide a non-default random seed on the command line. */
+ if (argc > 1)
+ srand (atoi (argv[1]));
+
+ {
+ size_t initial_size = RANDOM (20);
+ size_t i;
+ unsigned int repeat;
+
+ /* Create map1. */
+ map1 = gl_map_nx_create_empty (GL_ARRAY_MAP,
+ string_equals, string_hash, NULL, NULL);
+ ASSERT (map1 != NULL);
+
+ /* Create map2. */
+ map2 = gl_map_nx_create_empty (GL_LINKEDHASH_MAP,
+ string_equals, string_hash, NULL, NULL);
+ ASSERT (map2 != NULL);
+
+ check_all (map1, map2);
+
+ /* Initialize them. */
+ for (i = 0; i < initial_size; i++)
+ {
+ const char *key = RANDOM_OBJECT ();
+ const char *value = RANDOM_OBJECT ();
+ ASSERT (gl_map_nx_put (map1, key, value) == gl_map_nx_put (map2, key, value));
+ check_all (map1, map2);
+ }
+
+ for (repeat = 0; repeat < 100000; repeat++)
+ {
+ unsigned int operation = RANDOM (3);
+ switch (operation)
+ {
+ case 0:
+ {
+ const char *key = RANDOM_OBJECT ();
+ ASSERT (gl_map_get (map1, key) == gl_map_get (map2, key));
+ }
+ break;
+ case 1:
+ {
+ const char *key = RANDOM_OBJECT ();
+ const char *value = RANDOM_OBJECT ();
+ ASSERT (gl_map_nx_put (map1, key, value) == gl_map_nx_put (map2, key, value));
+ }
+ break;
+ case 2:
+ {
+ const char *key = RANDOM_OBJECT ();
+ ASSERT (gl_map_remove (map1, key) == gl_map_remove (map2, key));
+ }
+ break;
+ }
+ check_all (map1, map2);
+ }
+
+ gl_map_free (map1);
+ gl_map_free (map2);
+ }
+
+ return 0;
+}
--
2.7.4
>From 62932421ced5c8e90865ab46ebd9740d14ef68b8 Mon Sep 17 00:00:00 2001
From: Bruno Haible <[email protected]>
Date: Wed, 12 Dec 2018 01:30:56 +0100
Subject: [PATCH 8/8] hash-map: Add tests.
* tests/test-hash_map.c: New file.
* modules/hash-map-tests: New file.
---
ChangeLog | 4 +
modules/hash-map-tests | 13 ++++
tests/test-hash_map.c | 195 +++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 212 insertions(+)
create mode 100644 modules/hash-map-tests
create mode 100644 tests/test-hash_map.c
diff --git a/ChangeLog b/ChangeLog
index 9a706f6..795f47c 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,9 @@
2018-12-11 Bruno Haible <[email protected]>
+ hash-map: Add tests.
+ * tests/test-hash_map.c: New file.
+ * modules/hash-map-tests: New file.
+
linkedhash-map: Add tests.
* tests/test-linkedhash_map.c: New file.
* modules/linkedhash-map-tests: New file.
diff --git a/modules/hash-map-tests b/modules/hash-map-tests
new file mode 100644
index 0000000..693a026
--- /dev/null
+++ b/modules/hash-map-tests
@@ -0,0 +1,13 @@
+Files:
+tests/test-hash_map.c
+tests/macros.h
+
+Depends-on:
+array-map
+xalloc
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-hash_map
+check_PROGRAMS += test-hash_map
diff --git a/tests/test-hash_map.c b/tests/test-hash_map.c
new file mode 100644
index 0000000..9982173
--- /dev/null
+++ b/tests/test-hash_map.c
@@ -0,0 +1,195 @@
+/* Test of map data type implementation.
+ Copyright (C) 2006-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <[email protected]>, 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>
+
+#include "gl_hash_map.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "gl_array_map.h"
+#include "xalloc.h"
+#include "macros.h"
+
+static const char *objects[30] =
+ {
+ "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o",
+ "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "<", ">", "[", "]"
+ };
+
+#define SIZE_BITS (sizeof (size_t) * CHAR_BIT)
+
+static bool
+string_equals (const void *x1, const void *x2)
+{
+ const char *s1 = x1;
+ const char *s2 = x2;
+ return strcmp (s1, s2) == 0;
+}
+
+/* A hash function for NUL-terminated char* strings using
+ the method described by Bruno Haible.
+ See https://www.haible.de/bruno/hashfunc.html. */
+static size_t
+string_hash (const void *x)
+{
+ const char *s = x;
+ size_t h = 0;
+
+ for (; *s; s++)
+ h = *s + ((h << 9) | (h >> (SIZE_BITS - 9)));
+
+ return h;
+}
+
+#define RANDOM(n) (rand () % (n))
+#define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
+
+struct pair
+{
+ const void *key;
+ const void *value;
+};
+
+static int
+cmp_pairs_in_array (const void *pairptr1, const void *pairptr2)
+{
+ const void *key1 = ((struct pair const *)pairptr1)->key;
+ const void *key2 = ((struct pair const *)pairptr2)->key;
+ return strcmp ((const char *) key1, (const char *) key2);
+}
+
+static void
+check_equals (gl_map_t map1, gl_map_t map2)
+{
+ size_t n = gl_map_size (map1);
+ struct pair *pairs_of_map1 = XNMALLOC (n, struct pair);
+ struct pair *pairs_of_map2 = XNMALLOC (n, struct pair);
+
+ gl_map_iterator_t iter1, iter2;
+ const void *key1;
+ const void *value1;
+ const void *key2;
+ const void *value2;
+ size_t i;
+
+ iter1 = gl_map_iterator (map1);
+ iter2 = gl_map_iterator (map2);
+ for (i = 0; i < n; i++)
+ {
+ ASSERT (gl_map_iterator_next (&iter1, &key1, &value1));
+ ASSERT (gl_map_iterator_next (&iter2, &key2, &value2));
+ pairs_of_map1[i].key = key1;
+ pairs_of_map1[i].value = value1;
+ pairs_of_map2[i].key = key2;
+ pairs_of_map2[i].value = value2;
+ }
+ ASSERT (!gl_map_iterator_next (&iter1, &key1, &value1));
+ ASSERT (!gl_map_iterator_next (&iter2, &key2, &value2));
+ gl_map_iterator_free (&iter1);
+ gl_map_iterator_free (&iter2);
+
+ if (n > 0)
+ {
+ qsort (pairs_of_map1, n, sizeof (struct pair), cmp_pairs_in_array);
+ qsort (pairs_of_map2, n, sizeof (struct pair), cmp_pairs_in_array);
+ }
+ for (i = 0; i < n; i++)
+ {
+ ASSERT (pairs_of_map1[i].key == pairs_of_map2[i].key);
+ ASSERT (pairs_of_map1[i].value == pairs_of_map2[i].value);
+ }
+ free (pairs_of_map2);
+ free (pairs_of_map1);
+}
+
+static void
+check_all (gl_map_t map1, gl_map_t map2)
+{
+ check_equals (map1, map2);
+}
+
+int
+main (int argc, char *argv[])
+{
+ gl_map_t map1, map2;
+
+ /* Allow the user to provide a non-default random seed on the command line. */
+ if (argc > 1)
+ srand (atoi (argv[1]));
+
+ {
+ size_t initial_size = RANDOM (20);
+ size_t i;
+ unsigned int repeat;
+
+ /* Create map1. */
+ map1 = gl_map_nx_create_empty (GL_ARRAY_MAP,
+ string_equals, string_hash, NULL, NULL);
+ ASSERT (map1 != NULL);
+
+ /* Create map2. */
+ map2 = gl_map_nx_create_empty (GL_HASH_MAP,
+ string_equals, string_hash, NULL, NULL);
+ ASSERT (map2 != NULL);
+
+ check_all (map1, map2);
+
+ /* Initialize them. */
+ for (i = 0; i < initial_size; i++)
+ {
+ const char *key = RANDOM_OBJECT ();
+ const char *value = RANDOM_OBJECT ();
+ ASSERT (gl_map_nx_put (map1, key, value) == gl_map_nx_put (map2, key, value));
+ check_all (map1, map2);
+ }
+
+ for (repeat = 0; repeat < 100000; repeat++)
+ {
+ unsigned int operation = RANDOM (3);
+ switch (operation)
+ {
+ case 0:
+ {
+ const char *key = RANDOM_OBJECT ();
+ ASSERT (gl_map_get (map1, key) == gl_map_get (map2, key));
+ }
+ break;
+ case 1:
+ {
+ const char *key = RANDOM_OBJECT ();
+ const char *value = RANDOM_OBJECT ();
+ ASSERT (gl_map_nx_put (map1, key, value) == gl_map_nx_put (map2, key, value));
+ }
+ break;
+ case 2:
+ {
+ const char *key = RANDOM_OBJECT ();
+ ASSERT (gl_map_remove (map1, key) == gl_map_remove (map2, key));
+ }
+ break;
+ }
+ check_all (map1, map2);
+ }
+
+ gl_map_free (map1);
+ gl_map_free (map2);
+ }
+
+ return 0;
+}
--
2.7.4
