Hi,
In gnulib, so far, we have generic containers for the abstract concepts of
- list,
- ordered set.
This proposed series of patches adds a container for
- set.
The difference between "ordered set" and "set" is that for ordered set,
there is a comparison function that introduces a total order [1], whereas
for set, we only have a comparison for equality.
While the operations for ordered set are:
Operation ARRAY TREE
gl_oset_size O(1) O(1)
gl_oset_add O(n) O(log n)
gl_oset_remove O(n) O(log n)
gl_oset_search O(log n) O(log n)
gl_oset_search_atleast O(log n) O(log n)
gl_oset_iterator O(1) O(log n)
gl_oset_iterator_next O(1) O(log n)
the ones for a set are:
Operation ARRAY LINKEDHASH
LINKED HASH
gl_set_size O(1) O(1)
gl_set_add O(n) O(1)
gl_set_remove O(n) O(1)
gl_set_search O(n) O(1)
gl_set_iterator O(1) O(1)
gl_set_iterator_next O(1) O(1)
Given that the ARRAY and LINKED (= linked-list) implementations of "set"
have the same asymptotic average performance, and LINKED eats more memory
and does more memory allocations than ARRAY, I left out the LINKED
implementation.
This patch series is a preparation for the "map" concept, which I claimed
to be desirable [2].
Review and comments welcome!
Bruno
[1] https://en.wikipedia.org/wiki/Total_order
[2] https://lists.gnu.org/archive/html/bug-gnulib/2018-12/msg00012.html
>From b34b0da5f82eb6b0c163820ad9aa0e4e5bfe7590 Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@clisp.org>
Date: Tue, 4 Dec 2018 00:41:24 +0100
Subject: [PATCH 1/8] set: New module.
* lib/gl_set.h: New file.
* lib/gl_set.c: New file.
* lib/gl_oset.h (gl_setelement_dispose_fn): Avoid conflict with
gl_set.h.
* modules/set: New file.
---
ChangeLog | 9 ++
lib/gl_oset.h | 5 +-
lib/gl_set.c | 3 +
lib/gl_set.h | 280 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
modules/set | 24 +++++
5 files changed, 320 insertions(+), 1 deletion(-)
create mode 100644 lib/gl_set.c
create mode 100644 lib/gl_set.h
create mode 100644 modules/set
diff --git a/ChangeLog b/ChangeLog
index 76d6966..1761c1d 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+2018-12-03 Bruno Haible <br...@clisp.org>
+
+ set: New module.
+ * lib/gl_set.h: New file.
+ * lib/gl_set.c: New file.
+ * lib/gl_oset.h (gl_setelement_dispose_fn): Avoid conflict with
+ gl_set.h.
+ * modules/set: New file.
+
2018-12-01 Bruno Haible <br...@clisp.org>
gnupload: Document short options.
diff --git a/lib/gl_oset.h b/lib/gl_oset.h
index 5cad161..abe3eb4 100644
--- a/lib/gl_oset.h
+++ b/lib/gl_oset.h
@@ -77,9 +77,12 @@ extern "C" {
NULL denotes pointer comparison. */
typedef int (*gl_setelement_compar_fn) (const void *elt1, const void *elt2);
+#ifndef _GL_SETELEMENT_DISPOSE_FN_DEFINED
/* Type of function used to dispose an element once it's removed from a set.
NULL denotes a no-op. */
typedef void (*gl_setelement_dispose_fn) (const void *elt);
+# define _GL_SETELEMENT_DISPOSE_FN_DEFINED 1
+#endif
/* Type of function used to compare an element with a threshold.
Return true if the element is greater or equal than the threshold. */
@@ -144,7 +147,7 @@ extern bool gl_oset_remove (gl_oset_t set, const void *elt);
(But this call does not free the elements of the set.) */
extern void gl_oset_free (gl_oset_t set);
-#endif /* End of inline and gl_xlist.h-defined functions. */
+#endif /* End of inline and gl_xoset.h-defined functions. */
/* --------------------- gl_oset_iterator_t Data Type --------------------- */
diff --git a/lib/gl_set.c b/lib/gl_set.c
new file mode 100644
index 0000000..e00d202
--- /dev/null
+++ b/lib/gl_set.c
@@ -0,0 +1,3 @@
+#include <config.h>
+#define GL_SET_INLINE _GL_EXTERN_INLINE
+#include "gl_set.h"
diff --git a/lib/gl_set.h b/lib/gl_set.h
new file mode 100644
index 0000000..bc615c3
--- /dev/null
+++ b/lib/gl_set.h
@@ -0,0 +1,280 @@
+/* Abstract set data type.
+ Copyright (C) 2006-2007, 2009-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <br...@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_SET_H
+#define _GL_SET_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_SET_INLINE
+# define GL_SET_INLINE _GL_INLINE
+#endif
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+
+/* gl_set is an abstract set data type. It can contain any number of objects
+ ('void *' or 'const void *' pointers); the order does not matter.
+ Duplicates (in the sense of the comparator) are forbidden.
+
+ There are several implementations of this set datatype, optimized for
+ different operations or for memory. You can start using the simplest set
+ implementation, GL_ARRAY_SET, 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_set_create
+ call.
+
+ The implementations are:
+ GL_ARRAY_SET a growable array
+ GL_LINKEDHASH_SET a hash table with a linked list
+ GL_HASH_SET a hash table
+
+ The memory consumption is asymptotically the same: O(1) for every object
+ in the set. When looking more closely at the average memory consumed
+ for an object, GL_ARRAY_SET is the most compact representation, then comes
+ GL_HASH_SET, and GL_LINKEDHASH_SET needs the most memory.
+
+ The guaranteed average performance of the operations is, for a set of
+ n elements:
+
+ Operation ARRAY LINKEDHASH
+ HASH
+
+ gl_set_size O(1) O(1)
+ gl_set_add O(n) O(1)
+ gl_set_remove O(n) O(1)
+ gl_set_search O(n) O(1)
+ gl_set_iterator O(1) O(1)
+ gl_set_iterator_next O(1) O(1)
+ */
+
+/* --------------------------- gl_set_t Data Type --------------------------- */
+
+/* Type of function used to compare two elements.
+ NULL denotes pointer comparison. */
+typedef bool (*gl_setelement_equals_fn) (const void *elt1, const void *elt2);
+
+/* Type of function used to compute a hash code.
+ NULL denotes a function that depends only on the pointer itself. */
+typedef size_t (*gl_setelement_hashcode_fn) (const void *elt);
+
+#ifndef _GL_SETELEMENT_DISPOSE_FN_DEFINED
+/* Type of function used to dispose an element once it's removed from a set.
+ NULL denotes a no-op. */
+typedef void (*gl_setelement_dispose_fn) (const void *elt);
+# define _GL_SETELEMENT_DISPOSE_FN_DEFINED 1
+#endif
+
+struct gl_set_impl;
+/* Type representing an entire set. */
+typedef struct gl_set_impl * gl_set_t;
+
+struct gl_set_implementation;
+/* Type representing a set datatype implementation. */
+typedef const struct gl_set_implementation * gl_set_implementation_t;
+
+#if 0 /* Unless otherwise specified, these are defined inline below. */
+
+/* Create an empty set.
+ IMPLEMENTATION is one of GL_ARRAY_SET, GL_LINKEDHASH_SET, GL_HASH_SET.
+ EQUALS_FN is an element comparison function or NULL.
+ HASHCODE_FN is an element hash code function or NULL.
+ DISPOSE_FN is an element disposal function or NULL. */
+/* declared in gl_xset.h */
+extern gl_set_t gl_set_create_empty (gl_set_implementation_t implementation,
+ gl_setelement_equals_fn equals_fn,
+ gl_setelement_hashcode_fn hashcode_fn,
+ gl_setelement_dispose_fn dispose_fn);
+/* Likewise. Return NULL upon out-of-memory. */
+extern gl_set_t gl_set_nx_create_empty (gl_set_implementation_t implementation,
+ gl_setelement_equals_fn equals_fn,
+ gl_setelement_hashcode_fn hashcode_fn,
+ gl_setelement_dispose_fn dispose_fn);
+
+/* Return the current number of elements in a set. */
+extern size_t gl_set_size (gl_set_t set);
+
+/* Search whether an element is already in the set.
+ Return true if found, or false if not present in the set. */
+extern bool gl_set_search (gl_set_t set, const void *elt);
+
+/* Add an element to a set.
+ Return true if it was not already in the set and added, false otherwise. */
+/* declared in gl_xset.h */
+extern bool gl_set_add (gl_set_t set, const void *elt);
+/* Likewise. Return -1 upon out-of-memory. */
+extern int gl_set_nx_add (gl_set_t set, const void *elt)
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+ ;
+
+/* Remove an element from a set.
+ Return true if it was found and removed. */
+extern bool gl_set_remove (gl_set_t set, const void *elt);
+
+/* Free an entire set.
+ (But this call does not free the elements of the set.) */
+extern void gl_set_free (gl_set_t set);
+
+#endif /* End of inline and gl_xset.h-defined functions. */
+
+/* ---------------------- gl_set_iterator_t Data Type ---------------------- */
+
+/* Functions for iterating through a set.
+ Note: Iterating through a set of type GL_HASH_SET returns the elements in an
+ unpredictable order. If you need a predictable order, use GL_LINKEDHASH_SET
+ instead of GL_HASH_SET. */
+
+/* Type of an iterator that traverses a set.
+ 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_set_iterator_next. */
+ const struct gl_set_implementation *vtable;
+ /* For detecting whether the last returned element was removed. */
+ gl_set_t set;
+ size_t count;
+ /* Other, implementation-private fields. */
+ void *p; void *q;
+ size_t i; size_t j;
+} gl_set_iterator_t;
+
+#if 0 /* These are defined inline below. */
+
+/* Create an iterator traversing a set.
+ The set's contents must not be modified while the iterator is in use,
+ except for removing the last returned element. */
+extern gl_set_iterator_t gl_set_iterator (gl_set_t set);
+
+/* If there is a next element, store the next element in *ELTP, advance the
+ iterator and return true. Otherwise, return false. */
+extern bool gl_set_iterator_next (gl_set_iterator_t *iterator,
+ const void **eltp);
+
+/* Free an iterator. */
+extern void gl_set_iterator_free (gl_set_iterator_t *iterator);
+
+#endif /* End of inline functions. */
+
+/* ------------------------ Implementation Details ------------------------ */
+
+struct gl_set_implementation
+{
+ /* gl_set_t functions. */
+ gl_set_t (*nx_create_empty) (gl_set_implementation_t implementation,
+ gl_setelement_equals_fn equals_fn,
+ gl_setelement_hashcode_fn hashcode_fn,
+ gl_setelement_dispose_fn dispose_fn);
+ size_t (*size) (gl_set_t set);
+ bool (*search) (gl_set_t set, const void *elt);
+ int (*nx_add) (gl_set_t set, const void *elt);
+ bool (*remove_elt) (gl_set_t set, const void *elt);
+ void (*set_free) (gl_set_t set);
+ /* gl_set_iterator_t functions. */
+ gl_set_iterator_t (*iterator) (gl_set_t set);
+ bool (*iterator_next) (gl_set_iterator_t *iterator, const void **eltp);
+ void (*iterator_free) (gl_set_iterator_t *iterator);
+};
+
+struct gl_set_impl_base
+{
+ const struct gl_set_implementation *vtable;
+ gl_setelement_equals_fn equals_fn;
+ gl_setelement_dispose_fn dispose_fn;
+};
+
+/* Define all functions of this file as accesses to the
+ struct gl_set_implementation. */
+
+GL_SET_INLINE gl_set_t
+gl_set_nx_create_empty (gl_set_implementation_t implementation,
+ gl_setelement_equals_fn equals_fn,
+ gl_setelement_hashcode_fn hashcode_fn,
+ gl_setelement_dispose_fn dispose_fn)
+{
+ return implementation->nx_create_empty (implementation, equals_fn,
+ hashcode_fn, dispose_fn);
+}
+
+GL_SET_INLINE size_t
+gl_set_size (gl_set_t set)
+{
+ return ((const struct gl_set_impl_base *) set)->vtable->size (set);
+}
+
+GL_SET_INLINE bool
+gl_set_search (gl_set_t set, const void *elt)
+{
+ return ((const struct gl_set_impl_base *) set)->vtable->search (set, elt);
+}
+
+GL_SET_INLINE int
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+gl_set_nx_add (gl_set_t set, const void *elt)
+{
+ return ((const struct gl_set_impl_base *) set)->vtable->nx_add (set, elt);
+}
+
+GL_SET_INLINE bool
+gl_set_remove (gl_set_t set, const void *elt)
+{
+ return ((const struct gl_set_impl_base *) set)->vtable->remove_elt (set, elt);
+}
+
+GL_SET_INLINE void
+gl_set_free (gl_set_t set)
+{
+ ((const struct gl_set_impl_base *) set)->vtable->set_free (set);
+}
+
+GL_SET_INLINE gl_set_iterator_t
+gl_set_iterator (gl_set_t set)
+{
+ return ((const struct gl_set_impl_base *) set)->vtable->iterator (set);
+}
+
+GL_SET_INLINE bool
+gl_set_iterator_next (gl_set_iterator_t *iterator, const void **eltp)
+{
+ return iterator->vtable->iterator_next (iterator, eltp);
+}
+
+GL_SET_INLINE void
+gl_set_iterator_free (gl_set_iterator_t *iterator)
+{
+ iterator->vtable->iterator_free (iterator);
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+_GL_INLINE_HEADER_END
+
+#endif /* _GL_SET_H */
diff --git a/modules/set b/modules/set
new file mode 100644
index 0000000..29cec74
--- /dev/null
+++ b/modules/set
@@ -0,0 +1,24 @@
+Description:
+Abstract set data type.
+
+Files:
+lib/gl_set.h
+lib/gl_set.c
+
+Depends-on:
+extern-inline
+stdbool
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += gl_set.h gl_set.c
+
+Include:
+"gl_set.h"
+
+License:
+GPL
+
+Maintainer:
+all
--
2.7.4
>From 21350bc5a1291e0a2ce9442b60463c0f9797c4b9 Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@clisp.org>
Date: Tue, 4 Dec 2018 00:43:22 +0100
Subject: [PATCH 2/8] array-set: New module.
* lib/gl_array_set.h: New file.
* lib/gl_array_set.c: New file.
* modules/array-set: New file.
---
ChangeLog | 7 ++
lib/gl_array_set.c | 256 +++++++++++++++++++++++++++++++++++++++++++++++++++++
lib/gl_array_set.h | 34 +++++++
modules/array-set | 24 +++++
4 files changed, 321 insertions(+)
create mode 100644 lib/gl_array_set.c
create mode 100644 lib/gl_array_set.h
create mode 100644 modules/array-set
diff --git a/ChangeLog b/ChangeLog
index 1761c1d..a74e9a2 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,12 @@
2018-12-03 Bruno Haible <br...@clisp.org>
+ array-set: New module.
+ * lib/gl_array_set.h: New file.
+ * lib/gl_array_set.c: New file.
+ * modules/array-set: New file.
+
+2018-12-03 Bruno Haible <br...@clisp.org>
+
set: New module.
* lib/gl_set.h: New file.
* lib/gl_set.c: New file.
diff --git a/lib/gl_array_set.c b/lib/gl_array_set.c
new file mode 100644
index 0000000..dd77ef1
--- /dev/null
+++ b/lib/gl_array_set.c
@@ -0,0 +1,256 @@
+/* Set data type implemented by an array.
+ Copyright (C) 2006-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <br...@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_array_set.h"
+
+#include <stdlib.h>
+
+/* Checked size_t computations. */
+#include "xsize.h"
+
+#ifndef uintptr_t
+# define uintptr_t unsigned long
+#endif
+
+/* --------------------------- gl_set_t Data Type --------------------------- */
+
+/* Concrete gl_set_impl type, valid for this file only. */
+struct gl_set_impl
+{
+ struct gl_set_impl_base base;
+ /* An array of ALLOCATED elements, of which the first COUNT are used.
+ 0 <= COUNT <= ALLOCATED. */
+ const void **elements;
+ size_t count;
+ size_t allocated;
+};
+
+static gl_set_t
+gl_array_nx_create_empty (gl_set_implementation_t implementation,
+ gl_setelement_equals_fn equals_fn,
+ gl_setelement_hashcode_fn hashcode_fn,
+ gl_setelement_dispose_fn dispose_fn)
+{
+ struct gl_set_impl *set =
+ (struct gl_set_impl *) malloc (sizeof (struct gl_set_impl));
+
+ if (set == NULL)
+ return NULL;
+
+ set->base.vtable = implementation;
+ set->base.equals_fn = equals_fn;
+ set->base.dispose_fn = dispose_fn;
+ set->elements = NULL;
+ set->count = 0;
+ set->allocated = 0;
+
+ return set;
+}
+
+static size_t
+gl_array_size (gl_set_t set)
+{
+ return set->count;
+}
+
+static bool
+gl_array_search (gl_set_t set, const void *elt)
+{
+ size_t count = set->count;
+
+ if (count > 0)
+ {
+ gl_setelement_equals_fn equals = set->base.equals_fn;
+ const void **elements = set->elements;
+ size_t i;
+
+ for (i = 0; i < count; i++)
+ if (equals != NULL ? equals (elements[i], elt) : elements[i] == elt)
+ return true;
+ }
+ return false;
+}
+
+/* Ensure that set->allocated > set->count.
+ Return 0 upon success, -1 upon out-of-memory. */
+static int
+grow (gl_set_t set)
+{
+ size_t new_allocated;
+ size_t memory_size;
+ const void **memory;
+
+ new_allocated = xtimes (set->allocated, 2);
+ new_allocated = xsum (new_allocated, 1);
+ memory_size = xtimes (new_allocated, sizeof (const void *));
+ if (size_overflow_p (memory_size))
+ /* Overflow, would lead to out of memory. */
+ return -1;
+ memory = (const void **) realloc (set->elements, memory_size);
+ if (memory == NULL)
+ /* Out of memory. */
+ return -1;
+ set->elements = memory;
+ set->allocated = new_allocated;
+ return 0;
+}
+
+static int
+gl_array_nx_add (gl_set_t set, const void *elt)
+{
+ if (gl_array_search (set, elt))
+ return 0;
+ else
+ {
+ size_t count = set->count;
+
+ if (count == set->allocated)
+ if (grow (set) < 0)
+ return -1;
+ set->elements[count] = elt;
+ set->count = count + 1;
+ return 1;
+ }
+}
+
+/* Remove the element at the given position,
+ 0 <= position < gl_set_size (set). */
+static void
+gl_array_remove_at (gl_set_t set, size_t position)
+{
+ size_t count = set->count;
+ const void **elements = set->elements;
+ size_t i;
+
+ if (set->base.dispose_fn != NULL)
+ set->base.dispose_fn (elements[position]);
+ for (i = position + 1; i < count; i++)
+ elements[i - 1] = elements[i];
+ set->count = count - 1;
+}
+
+static bool
+gl_array_remove (gl_set_t set, const void *elt)
+{
+ size_t count = set->count;
+
+ if (count > 0)
+ {
+ gl_setelement_equals_fn equals = set->base.equals_fn;
+ const void **elements = set->elements;
+ size_t i;
+
+ for (i = 0; i < count; i++)
+ if (equals != NULL ? equals (elements[i], elt) : elements[i] == elt)
+ {
+ gl_array_remove_at (set, i);
+ return true;
+ }
+ }
+ return false;
+}
+
+static void
+gl_array_free (gl_set_t set)
+{
+ if (set->elements != NULL)
+ {
+ if (set->base.dispose_fn != NULL)
+ {
+ size_t count = set->count;
+
+ if (count > 0)
+ {
+ gl_setelement_dispose_fn dispose = set->base.dispose_fn;
+ const void **elements = set->elements;
+
+ do
+ dispose (*elements++);
+ while (--count > 0);
+ }
+ }
+ free (set->elements);
+ }
+ free (set);
+}
+
+/* ---------------------- gl_set_iterator_t Data Type ---------------------- */
+
+static gl_set_iterator_t
+gl_array_iterator (gl_set_t set)
+{
+ gl_set_iterator_t result;
+
+ result.vtable = set->base.vtable;
+ result.set = set;
+ result.count = set->count;
+ result.p = set->elements + 0;
+ result.q = set->elements + set->count;
+#if defined GCC_LINT || defined lint
+ result.i = 0;
+ result.j = 0;
+#endif
+
+ return result;
+}
+
+static bool
+gl_array_iterator_next (gl_set_iterator_t *iterator, const void **eltp)
+{
+ gl_set_t set = iterator->set;
+ if (iterator->count != set->count)
+ {
+ if (iterator->count != set->count + 1)
+ /* Concurrent modifications were done on the set. */
+ abort ();
+ /* The last returned element was removed. */
+ iterator->count--;
+ iterator->p = (const void **) iterator->p - 1;
+ iterator->q = (const void **) iterator->q - 1;
+ }
+ if (iterator->p < iterator->q)
+ {
+ const void **p = (const void **) iterator->p;
+ *eltp = *p;
+ iterator->p = p + 1;
+ return true;
+ }
+ else
+ return false;
+}
+
+static void
+gl_array_iterator_free (gl_set_iterator_t *iterator)
+{
+}
+
+
+const struct gl_set_implementation gl_array_set_implementation =
+ {
+ gl_array_nx_create_empty,
+ gl_array_size,
+ gl_array_search,
+ gl_array_nx_add,
+ gl_array_remove,
+ gl_array_free,
+ gl_array_iterator,
+ gl_array_iterator_next,
+ gl_array_iterator_free
+ };
diff --git a/lib/gl_array_set.h b/lib/gl_array_set.h
new file mode 100644
index 0000000..ea9fea3
--- /dev/null
+++ b/lib/gl_array_set.h
@@ -0,0 +1,34 @@
+/* Set data type implemented by an array.
+ Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <br...@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_ARRAY_SET_H
+#define _GL_ARRAY_SET_H
+
+#include "gl_set.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+extern const struct gl_set_implementation gl_array_set_implementation;
+#define GL_ARRAY_SET &gl_array_set_implementation
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _GL_ARRAY_SET_H */
diff --git a/modules/array-set b/modules/array-set
new file mode 100644
index 0000000..bb03425
--- /dev/null
+++ b/modules/array-set
@@ -0,0 +1,24 @@
+Description:
+Set data type implemented by an array.
+
+Files:
+lib/gl_array_set.h
+lib/gl_array_set.c
+
+Depends-on:
+set
+xsize
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += gl_array_set.h gl_array_set.c
+
+Include:
+"gl_array_set.h"
+
+License:
+GPL
+
+Maintainer:
+all
--
2.7.4
>From a3a32aa9cee0a7224b9cd21bf251ac46dd4e4f83 Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@clisp.org>
Date: Tue, 4 Dec 2018 00:53:12 +0100
Subject: [PATCH 3/8] linkedhash-set: New module.
* lib/gl_linkedhash_set.h: New file.
* lib/gl_linkedhash_set.c: New file.
* lib/gl_anyhash_set1.h: New file, based on lib/gl_anyhash_list1.h.
* lib/gl_anyhash_set2.h: New file, based on lib/gl_anyhash_list2.h.
* lib/gl_anyhash_primes.h: New file, extracted from
lib/gl_anyhash_list2.h.
* lib/gl_anyhash_list2.h: Include it.
(primes, next_prime): Remove definitions.
* modules/linkedhash-set: New file.
* modules/avltreehash-list (Files): Add lib/gl_anyhash_primes.h.
(Makefile.am): Add gl_anyhash_primes.h to lib_SOURCES.
* modules/linkedhash-list (Files): Add lib/gl_anyhash_primes.h.
(Makefile.am): Add gl_anyhash_primes.h to lib_SOURCES.
* modules/rbtreehash-list (Files): Add lib/gl_anyhash_primes.h.
(Makefile.am): Add gl_anyhash_primes.h to lib_SOURCES.
---
ChangeLog | 19 +++
lib/gl_anyhash_list2.h | 71 +----------
lib/gl_anyhash_primes.h | 87 +++++++++++++
lib/gl_anyhash_set1.h | 27 ++++
lib/gl_anyhash_set2.h | 79 ++++++++++++
lib/gl_linkedhash_set.c | 313 +++++++++++++++++++++++++++++++++++++++++++++++
lib/gl_linkedhash_set.h | 34 +++++
modules/avltreehash-list | 3 +-
modules/linkedhash-list | 3 +-
modules/linkedhash-set | 28 +++++
modules/rbtreehash-list | 3 +-
11 files changed, 594 insertions(+), 73 deletions(-)
create mode 100644 lib/gl_anyhash_primes.h
create mode 100644 lib/gl_anyhash_set1.h
create mode 100644 lib/gl_anyhash_set2.h
create mode 100644 lib/gl_linkedhash_set.c
create mode 100644 lib/gl_linkedhash_set.h
create mode 100644 modules/linkedhash-set
diff --git a/ChangeLog b/ChangeLog
index a74e9a2..5f0ae48 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,24 @@
2018-12-03 Bruno Haible <br...@clisp.org>
+ linkedhash-set: New module.
+ * lib/gl_linkedhash_set.h: New file.
+ * lib/gl_linkedhash_set.c: New file.
+ * lib/gl_anyhash_set1.h: New file, based on lib/gl_anyhash_list1.h.
+ * lib/gl_anyhash_set2.h: New file, based on lib/gl_anyhash_list2.h.
+ * lib/gl_anyhash_primes.h: New file, extracted from
+ lib/gl_anyhash_list2.h.
+ * lib/gl_anyhash_list2.h: Include it.
+ (primes, next_prime): Remove definitions.
+ * modules/linkedhash-set: New file.
+ * modules/avltreehash-list (Files): Add lib/gl_anyhash_primes.h.
+ (Makefile.am): Add gl_anyhash_primes.h to lib_SOURCES.
+ * modules/linkedhash-list (Files): Add lib/gl_anyhash_primes.h.
+ (Makefile.am): Add gl_anyhash_primes.h to lib_SOURCES.
+ * modules/rbtreehash-list (Files): Add lib/gl_anyhash_primes.h.
+ (Makefile.am): Add gl_anyhash_primes.h to lib_SOURCES.
+
+2018-12-03 Bruno Haible <br...@clisp.org>
+
array-set: New module.
* lib/gl_array_set.h: New file.
* lib/gl_array_set.c: New file.
diff --git a/lib/gl_anyhash_list2.h b/lib/gl_anyhash_list2.h
index dac8bb5..d1a5dfb 100644
--- a/lib/gl_anyhash_list2.h
+++ b/lib/gl_anyhash_list2.h
@@ -18,76 +18,7 @@
/* Common code of
gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c. */
-/* Array of primes, approximately in steps of factor 1.2.
- This table was computed by executing the Common Lisp expression
- (dotimes (i 244) (format t "nextprime(~D)~%" (ceiling (expt 1.2d0 i))))
- and feeding the result to PARI/gp. */
-static const size_t primes[] =
- {
- 11, 13, 17, 19, 23, 29, 37, 41, 47, 59, 67, 83, 97, 127, 139, 167, 199,
- 239, 293, 347, 419, 499, 593, 709, 853, 1021, 1229, 1471, 1777, 2129, 2543,
- 3049, 3659, 4391, 5273, 6323, 7589, 9103, 10937, 13109, 15727, 18899,
- 22651, 27179, 32609, 39133, 46957, 56359, 67619, 81157, 97369, 116849,
- 140221, 168253, 201907, 242309, 290761, 348889, 418667, 502409, 602887,
- 723467, 868151, 1041779, 1250141, 1500181, 1800191, 2160233, 2592277,
- 3110741, 3732887, 4479463, 5375371, 6450413, 7740517, 9288589, 11146307,
- 13375573, 16050689, 19260817, 23112977, 27735583, 33282701, 39939233,
- 47927081, 57512503, 69014987, 82818011, 99381577, 119257891, 143109469,
- 171731387, 206077643, 247293161, 296751781, 356102141, 427322587,
- 512787097, 615344489, 738413383, 886096061, 1063315271, 1275978331,
- 1531174013, 1837408799, 2204890543UL, 2645868653UL, 3175042391UL,
- 3810050851UL,
-#if SIZE_MAX > 4294967295UL
- 4572061027UL, 5486473229UL, 6583767889UL, 7900521449UL, 9480625733UL,
- 11376750877UL, 13652101063UL, 16382521261UL, 19659025513UL, 23590830631UL,
- 28308996763UL, 33970796089UL, 40764955463UL, 48917946377UL, 58701535657UL,
- 70441842749UL, 84530211301UL, 101436253561UL, 121723504277UL,
- 146068205131UL, 175281846149UL, 210338215379UL, 252405858521UL,
- 302887030151UL, 363464436191UL, 436157323417UL, 523388788231UL,
- 628066545713UL, 753679854847UL, 904415825857UL, 1085298991109UL,
- 1302358789181UL, 1562830547009UL, 1875396656429UL, 2250475987709UL,
- 2700571185239UL, 3240685422287UL, 3888822506759UL, 4666587008147UL,
- 5599904409713UL, 6719885291641UL, 8063862349969UL, 9676634819959UL,
- 11611961783951UL, 13934354140769UL, 16721224968907UL, 20065469962669UL,
- 24078563955191UL, 28894276746229UL, 34673132095507UL, 41607758514593UL,
- 49929310217531UL, 59915172260971UL, 71898206713183UL, 86277848055823UL,
- 103533417666967UL, 124240101200359UL, 149088121440451UL, 178905745728529UL,
- 214686894874223UL, 257624273849081UL, 309149128618903UL, 370978954342639UL,
- 445174745211143UL, 534209694253381UL, 641051633104063UL, 769261959724877UL,
- 923114351670013UL, 1107737222003791UL, 1329284666404567UL,
- 1595141599685509UL, 1914169919622551UL, 2297003903547091UL,
- 2756404684256459UL, 3307685621107757UL, 3969222745329323UL,
- 4763067294395177UL, 5715680753274209UL, 6858816903929113UL,
- 8230580284714831UL, 9876696341657791UL, 11852035609989371UL,
- 14222442731987227UL, 17066931278384657UL, 20480317534061597UL,
- 24576381040873903UL, 29491657249048679UL, 35389988698858471UL,
- 42467986438630267UL, 50961583726356109UL, 61153900471627387UL,
- 73384680565952851UL, 88061616679143347UL, 105673940014972061UL,
- 126808728017966413UL, 152170473621559703UL, 182604568345871671UL,
- 219125482015045997UL, 262950578418055169UL, 315540694101666193UL,
- 378648832921999397UL, 454378599506399233UL, 545254319407679131UL,
- 654305183289214771UL, 785166219947057701UL, 942199463936469157UL,
- 1130639356723763129UL, 1356767228068515623UL, 1628120673682218619UL,
- 1953744808418662409UL, 2344493770102394881UL, 2813392524122873857UL,
- 3376071028947448339UL, 4051285234736937517UL, 4861542281684325481UL,
- 5833850738021191727UL, 7000620885625427969UL, 8400745062750513217UL,
- 10080894075300616261UL, 12097072890360739951UL, 14516487468432885797UL,
- 17419784962119465179UL,
-#endif
- SIZE_MAX /* sentinel, to ensure the search terminates */
- };
-
-/* Return a suitable prime >= ESTIMATE. */
-static size_t
-next_prime (size_t estimate)
-{
- size_t i;
-
- for (i = 0; i < sizeof (primes) / sizeof (primes[0]); i++)
- if (primes[i] >= estimate)
- return primes[i];
- return SIZE_MAX; /* not a prime, but better than nothing */
-}
+#include "gl_anyhash_primes.h"
/* Resize the hash table with a new estimated size. */
static void
diff --git a/lib/gl_anyhash_primes.h b/lib/gl_anyhash_primes.h
new file mode 100644
index 0000000..79d2695
--- /dev/null
+++ b/lib/gl_anyhash_primes.h
@@ -0,0 +1,87 @@
+/* Table of primes, for use by hash tables.
+ Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <br...@clisp.org>, 2006.
+
+ 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/>. */
+
+/* Array of primes, approximately in steps of factor 1.2.
+ This table was computed by executing the Common Lisp expression
+ (dotimes (i 244) (format t "nextprime(~D)~%" (ceiling (expt 1.2d0 i))))
+ and feeding the result to PARI/gp. */
+static const size_t primes[] =
+ {
+ 11, 13, 17, 19, 23, 29, 37, 41, 47, 59, 67, 83, 97, 127, 139, 167, 199,
+ 239, 293, 347, 419, 499, 593, 709, 853, 1021, 1229, 1471, 1777, 2129, 2543,
+ 3049, 3659, 4391, 5273, 6323, 7589, 9103, 10937, 13109, 15727, 18899,
+ 22651, 27179, 32609, 39133, 46957, 56359, 67619, 81157, 97369, 116849,
+ 140221, 168253, 201907, 242309, 290761, 348889, 418667, 502409, 602887,
+ 723467, 868151, 1041779, 1250141, 1500181, 1800191, 2160233, 2592277,
+ 3110741, 3732887, 4479463, 5375371, 6450413, 7740517, 9288589, 11146307,
+ 13375573, 16050689, 19260817, 23112977, 27735583, 33282701, 39939233,
+ 47927081, 57512503, 69014987, 82818011, 99381577, 119257891, 143109469,
+ 171731387, 206077643, 247293161, 296751781, 356102141, 427322587,
+ 512787097, 615344489, 738413383, 886096061, 1063315271, 1275978331,
+ 1531174013, 1837408799, 2204890543UL, 2645868653UL, 3175042391UL,
+ 3810050851UL,
+#if SIZE_MAX > 4294967295UL
+ 4572061027UL, 5486473229UL, 6583767889UL, 7900521449UL, 9480625733UL,
+ 11376750877UL, 13652101063UL, 16382521261UL, 19659025513UL, 23590830631UL,
+ 28308996763UL, 33970796089UL, 40764955463UL, 48917946377UL, 58701535657UL,
+ 70441842749UL, 84530211301UL, 101436253561UL, 121723504277UL,
+ 146068205131UL, 175281846149UL, 210338215379UL, 252405858521UL,
+ 302887030151UL, 363464436191UL, 436157323417UL, 523388788231UL,
+ 628066545713UL, 753679854847UL, 904415825857UL, 1085298991109UL,
+ 1302358789181UL, 1562830547009UL, 1875396656429UL, 2250475987709UL,
+ 2700571185239UL, 3240685422287UL, 3888822506759UL, 4666587008147UL,
+ 5599904409713UL, 6719885291641UL, 8063862349969UL, 9676634819959UL,
+ 11611961783951UL, 13934354140769UL, 16721224968907UL, 20065469962669UL,
+ 24078563955191UL, 28894276746229UL, 34673132095507UL, 41607758514593UL,
+ 49929310217531UL, 59915172260971UL, 71898206713183UL, 86277848055823UL,
+ 103533417666967UL, 124240101200359UL, 149088121440451UL, 178905745728529UL,
+ 214686894874223UL, 257624273849081UL, 309149128618903UL, 370978954342639UL,
+ 445174745211143UL, 534209694253381UL, 641051633104063UL, 769261959724877UL,
+ 923114351670013UL, 1107737222003791UL, 1329284666404567UL,
+ 1595141599685509UL, 1914169919622551UL, 2297003903547091UL,
+ 2756404684256459UL, 3307685621107757UL, 3969222745329323UL,
+ 4763067294395177UL, 5715680753274209UL, 6858816903929113UL,
+ 8230580284714831UL, 9876696341657791UL, 11852035609989371UL,
+ 14222442731987227UL, 17066931278384657UL, 20480317534061597UL,
+ 24576381040873903UL, 29491657249048679UL, 35389988698858471UL,
+ 42467986438630267UL, 50961583726356109UL, 61153900471627387UL,
+ 73384680565952851UL, 88061616679143347UL, 105673940014972061UL,
+ 126808728017966413UL, 152170473621559703UL, 182604568345871671UL,
+ 219125482015045997UL, 262950578418055169UL, 315540694101666193UL,
+ 378648832921999397UL, 454378599506399233UL, 545254319407679131UL,
+ 654305183289214771UL, 785166219947057701UL, 942199463936469157UL,
+ 1130639356723763129UL, 1356767228068515623UL, 1628120673682218619UL,
+ 1953744808418662409UL, 2344493770102394881UL, 2813392524122873857UL,
+ 3376071028947448339UL, 4051285234736937517UL, 4861542281684325481UL,
+ 5833850738021191727UL, 7000620885625427969UL, 8400745062750513217UL,
+ 10080894075300616261UL, 12097072890360739951UL, 14516487468432885797UL,
+ 17419784962119465179UL,
+#endif
+ SIZE_MAX /* sentinel, to ensure the search terminates */
+ };
+
+/* Return a suitable prime >= ESTIMATE. */
+static size_t
+next_prime (size_t estimate)
+{
+ size_t i;
+
+ for (i = 0; i < sizeof (primes) / sizeof (primes[0]); i++)
+ if (primes[i] >= estimate)
+ return primes[i];
+ return SIZE_MAX; /* not a prime, but better than nothing */
+}
diff --git a/lib/gl_anyhash_set1.h b/lib/gl_anyhash_set1.h
new file mode 100644
index 0000000..0816a45
--- /dev/null
+++ b/lib/gl_anyhash_set1.h
@@ -0,0 +1,27 @@
+/* Set data type implemented by a hash table with another list.
+ Copyright (C) 2006-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <br...@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/>. */
+
+/* Common code of
+ gl_linkedhash_set.c, gl_hash_set.c. */
+
+/* Hash table entry. */
+struct gl_hash_entry
+{
+ struct gl_hash_entry *hash_next; /* chain of entries in same bucket */
+ size_t hashcode; /* cache of the hash code of the value */
+};
+typedef struct gl_hash_entry * gl_hash_entry_t;
diff --git a/lib/gl_anyhash_set2.h b/lib/gl_anyhash_set2.h
new file mode 100644
index 0000000..98dc0cb
--- /dev/null
+++ b/lib/gl_anyhash_set2.h
@@ -0,0 +1,79 @@
+/* Set data type implemented by a hash table with another list.
+ Copyright (C) 2006-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <br...@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/>. */
+
+/* Common code of
+ gl_linkedhash_set.c, gl_hash_set.c. */
+
+#include "gl_anyhash_primes.h"
+
+/* Resize the hash table with a new estimated size. */
+static void
+hash_resize (gl_set_t set, size_t estimate)
+{
+ size_t new_size = next_prime (estimate);
+
+ if (new_size > set->table_size)
+ {
+ gl_hash_entry_t *old_table = set->table;
+ /* Allocate the new table. */
+ gl_hash_entry_t *new_table;
+ size_t i;
+
+ if (size_overflow_p (xtimes (new_size, sizeof (gl_hash_entry_t))))
+ goto fail;
+ new_table =
+ (gl_hash_entry_t *) calloc (new_size, sizeof (gl_hash_entry_t));
+ if (new_table == NULL)
+ goto fail;
+
+ /* Iterate through the entries of the old table. */
+ for (i = set->table_size; i > 0; )
+ {
+ gl_hash_entry_t node = old_table[--i];
+
+ while (node != NULL)
+ {
+ gl_hash_entry_t next = node->hash_next;
+ /* Add the entry to the new table. */
+ size_t bucket = node->hashcode % new_size;
+ node->hash_next = new_table[bucket];
+ new_table[bucket] = node;
+
+ node = next;
+ }
+ }
+
+ set->table = new_table;
+ set->table_size = new_size;
+ free (old_table);
+ }
+ return;
+
+ fail:
+ /* Just continue without resizing the table. */
+ return;
+}
+
+/* Resize the hash table if needed, after set->count was incremented. */
+static void
+hash_resize_after_add (gl_set_t set)
+{
+ size_t count = set->count;
+ size_t estimate = xsum (count, count / 2); /* 1.5 * count */
+ if (estimate > set->table_size)
+ hash_resize (set, estimate);
+}
diff --git a/lib/gl_linkedhash_set.c b/lib/gl_linkedhash_set.c
new file mode 100644
index 0000000..9f2d730
--- /dev/null
+++ b/lib/gl_linkedhash_set.c
@@ -0,0 +1,313 @@
+/* Set data type implemented by a hash table with a linked list.
+ Copyright (C) 2006, 2008-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <br...@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_linkedhash_set.h"
+
+#include <stdint.h> /* for SIZE_MAX */
+#include <stdlib.h>
+
+#include "xsize.h"
+
+#ifndef uintptr_t
+# define uintptr_t unsigned long
+#endif
+
+/* --------------------------- gl_set_t Data Type --------------------------- */
+
+#include "gl_anyhash_set1.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 *value;
+};
+typedef struct gl_list_node_impl * gl_list_node_t;
+
+/* Concrete gl_set_impl type, valid for this file only. */
+struct gl_set_impl
+{
+ struct gl_set_impl_base base;
+ gl_setelement_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;
+};
+
+#include "gl_anyhash_set2.h"
+
+/* If the symbol SIGNAL_SAFE_SET is defined, the code is compiled in such
+ a way that a gl_set_t data structure may be used from within a signal
+ handler. The operations allowed in the signal handler are:
+ gl_set_iterator, gl_set_iterator_next, gl_set_iterator_free.
+ The set and node fields that are therefore accessed from the signal handler
+ are:
+ set->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_SET
+# define ASYNCSAFE(type) *(type volatile *)&
+#else
+# define ASYNCSAFE(type)
+#endif
+
+/* --------------------------- gl_set_t Data Type --------------------------- */
+
+static gl_set_t
+gl_linkedhash_nx_create_empty (gl_set_implementation_t implementation,
+ gl_setelement_equals_fn equals_fn,
+ gl_setelement_hashcode_fn hashcode_fn,
+ gl_setelement_dispose_fn dispose_fn)
+{
+ struct gl_set_impl *set =
+ (struct gl_set_impl *) malloc (sizeof (struct gl_set_impl));
+
+ if (set == NULL)
+ return NULL;
+
+ set->base.vtable = implementation;
+ set->base.equals_fn = equals_fn;
+ set->base.dispose_fn = dispose_fn;
+ set->hashcode_fn = hashcode_fn;
+ set->table_size = 11;
+ set->table =
+ (gl_hash_entry_t *) calloc (set->table_size, sizeof (gl_hash_entry_t));
+ if (set->table == NULL)
+ goto fail;
+ set->root.next = &set->root;
+ set->root.prev = &set->root;
+ set->count = 0;
+
+ return set;
+
+ fail:
+ free (set);
+ return NULL;
+}
+
+static size_t _GL_ATTRIBUTE_PURE
+gl_linkedhash_size (gl_set_t set)
+{
+ return set->count;
+}
+
+static bool _GL_ATTRIBUTE_PURE
+gl_linkedhash_search (gl_set_t set, const void *elt)
+{
+ size_t hashcode =
+ (set->hashcode_fn != NULL
+ ? set->hashcode_fn (elt)
+ : (size_t)(uintptr_t) elt);
+ size_t bucket = hashcode % set->table_size;
+ gl_setelement_equals_fn equals = set->base.equals_fn;
+
+ /* Look for a match in the hash bucket. */
+ gl_list_node_t node;
+
+ for (node = (gl_list_node_t) set->table[bucket];
+ node != NULL;
+ node = (gl_list_node_t) node->h.hash_next)
+ if (node->h.hashcode == hashcode
+ && (equals != NULL
+ ? equals (elt, node->value)
+ : elt == node->value))
+ return true;
+ return false;
+}
+
+static int
+gl_linkedhash_nx_add (gl_set_t set, const void *elt)
+{
+ size_t hashcode =
+ (set->hashcode_fn != NULL
+ ? set->hashcode_fn (elt)
+ : (size_t)(uintptr_t) elt);
+ size_t bucket = hashcode % set->table_size;
+ gl_setelement_equals_fn equals = set->base.equals_fn;
+
+ /* Look for a match in the hash bucket. */
+ {
+ gl_list_node_t node;
+
+ for (node = (gl_list_node_t) set->table[bucket];
+ node != NULL;
+ node = (gl_list_node_t) node->h.hash_next)
+ if (node->h.hashcode == hashcode
+ && (equals != NULL
+ ? equals (elt, node->value)
+ : elt == node->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->value = elt;
+ node->h.hashcode = hashcode;
+
+ /* Add node to the hash table. */
+ node->h.hash_next = set->table[bucket];
+ set->table[bucket] = &node->h;
+
+ /* Add node to the set. */
+ ASYNCSAFE(gl_list_node_t) node->next = &set->root;
+ node->prev = set->root.prev;
+ ASYNCSAFE(gl_list_node_t) node->prev->next = node;
+ set->root.prev = node;
+ set->count++;
+
+ hash_resize_after_add (set);
+
+ return 1;
+}
+
+static bool
+gl_linkedhash_remove (gl_set_t set, const void *elt)
+{
+ size_t hashcode =
+ (set->hashcode_fn != NULL
+ ? set->hashcode_fn (elt)
+ : (size_t)(uintptr_t) elt);
+ size_t bucket = hashcode % set->table_size;
+ gl_setelement_equals_fn equals = set->base.equals_fn;
+
+ /* Look for the first match in the hash bucket. */
+ gl_list_node_t *nodep;
+
+ for (nodep = (gl_list_node_t *) &set->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 (elt, node->value)
+ : elt == 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;
+ }
+ set->count--;
+
+ if (set->base.dispose_fn != NULL)
+ set->base.dispose_fn (node->value);
+ free (node);
+ return true;
+ }
+ }
+
+ return false;
+}
+
+static void
+gl_linkedhash_free (gl_set_t set)
+{
+ gl_setelement_dispose_fn dispose = set->base.dispose_fn;
+ gl_list_node_t node;
+
+ for (node = set->root.next; node != &set->root; )
+ {
+ gl_list_node_t next = node->next;
+ if (dispose != NULL)
+ dispose (node->value);
+ free (node);
+ node = next;
+ }
+ free (set->table);
+ free (set);
+}
+
+/* ---------------------- gl_set_iterator_t Data Type ---------------------- */
+
+/* Iterate through the list, not through the hash buckets, so that the order
+ in which the elements are returned is predictable. */
+
+static gl_set_iterator_t
+gl_linkedhash_iterator (gl_set_t set)
+{
+ gl_set_iterator_t result;
+
+ result.vtable = set->base.vtable;
+ result.set = set;
+ result.p = set->root.next;
+ result.q = &set->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_set_iterator_t *iterator, const void **eltp)
+{
+ if (iterator->p != iterator->q)
+ {
+ gl_list_node_t node = (gl_list_node_t) iterator->p;
+ *eltp = node->value;
+ iterator->p = node->next;
+ return true;
+ }
+ else
+ return false;
+}
+
+static void
+gl_linkedhash_iterator_free (gl_set_iterator_t *iterator)
+{
+}
+
+
+const struct gl_set_implementation gl_linkedhash_set_implementation =
+ {
+ gl_linkedhash_nx_create_empty,
+ gl_linkedhash_size,
+ gl_linkedhash_search,
+ gl_linkedhash_nx_add,
+ gl_linkedhash_remove,
+ gl_linkedhash_free,
+ gl_linkedhash_iterator,
+ gl_linkedhash_iterator_next,
+ gl_linkedhash_iterator_free
+ };
diff --git a/lib/gl_linkedhash_set.h b/lib/gl_linkedhash_set.h
new file mode 100644
index 0000000..5aacd4f
--- /dev/null
+++ b/lib/gl_linkedhash_set.h
@@ -0,0 +1,34 @@
+/* Set data type implemented by a hash table with a linked list.
+ Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <br...@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_LINKEDHASH_SET_H
+#define _GL_LINKEDHASH_SET_H
+
+#include "gl_set.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+extern const struct gl_set_implementation gl_linkedhash_set_implementation;
+#define GL_LINKEDHASH_SET &gl_linkedhash_set_implementation
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _GL_LINKEDHASH_SET_H */
diff --git a/modules/avltreehash-list b/modules/avltreehash-list
index a7aa75e..afd4b25 100644
--- a/modules/avltreehash-list
+++ b/modules/avltreehash-list
@@ -6,6 +6,7 @@ lib/gl_avltreehash_list.h
lib/gl_avltreehash_list.c
lib/gl_anyhash_list1.h
lib/gl_anyhash_list2.h
+lib/gl_anyhash_primes.h
lib/gl_anyavltree_list1.h
lib/gl_anyavltree_list2.h
lib/gl_anytree_list1.h
@@ -23,7 +24,7 @@ xsize
configure.ac:
Makefile.am:
-lib_SOURCES += gl_avltreehash_list.h gl_avltreehash_list.c gl_anyhash_list1.h gl_anyhash_list2.h gl_anyavltree_list1.h gl_anyavltree_list2.h gl_anytree_list1.h gl_anytree_list2.h gl_anytreehash_list1.h gl_anytreehash_list2.h
+lib_SOURCES += gl_avltreehash_list.h gl_avltreehash_list.c gl_anyhash_list1.h gl_anyhash_list2.h gl_anyhash_primes.h gl_anyavltree_list1.h gl_anyavltree_list2.h gl_anytree_list1.h gl_anytree_list2.h gl_anytreehash_list1.h gl_anytreehash_list2.h
Include:
"gl_avltreehash_list.h"
diff --git a/modules/linkedhash-list b/modules/linkedhash-list
index f601a00..35de8c4 100644
--- a/modules/linkedhash-list
+++ b/modules/linkedhash-list
@@ -6,6 +6,7 @@ lib/gl_linkedhash_list.h
lib/gl_linkedhash_list.c
lib/gl_anyhash_list1.h
lib/gl_anyhash_list2.h
+lib/gl_anyhash_primes.h
lib/gl_anylinked_list1.h
lib/gl_anylinked_list2.h
@@ -17,7 +18,7 @@ xsize
configure.ac:
Makefile.am:
-lib_SOURCES += gl_linkedhash_list.h gl_linkedhash_list.c gl_anyhash_list1.h gl_anyhash_list2.h gl_anylinked_list1.h gl_anylinked_list2.h
+lib_SOURCES += gl_linkedhash_list.h gl_linkedhash_list.c gl_anyhash_list1.h gl_anyhash_list2.h gl_anyhash_primes.h gl_anylinked_list1.h gl_anylinked_list2.h
Include:
"gl_linkedhash_list.h"
diff --git a/modules/linkedhash-set b/modules/linkedhash-set
new file mode 100644
index 0000000..5ca2544
--- /dev/null
+++ b/modules/linkedhash-set
@@ -0,0 +1,28 @@
+Description:
+Set data type implemented by a hash table with a linked list.
+
+Files:
+lib/gl_linkedhash_set.h
+lib/gl_linkedhash_set.c
+lib/gl_anyhash_set1.h
+lib/gl_anyhash_set2.h
+lib/gl_anyhash_primes.h
+
+Depends-on:
+set
+stdint
+xsize
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += gl_linkedhash_set.h gl_linkedhash_set.c gl_anyhash_set1.h gl_anyhash_set2.h gl_anyhash_primes.h
+
+Include:
+"gl_linkedhash_set.h"
+
+License:
+GPL
+
+Maintainer:
+all
diff --git a/modules/rbtreehash-list b/modules/rbtreehash-list
index 2b4add5..7957d51 100644
--- a/modules/rbtreehash-list
+++ b/modules/rbtreehash-list
@@ -6,6 +6,7 @@ lib/gl_rbtreehash_list.h
lib/gl_rbtreehash_list.c
lib/gl_anyhash_list1.h
lib/gl_anyhash_list2.h
+lib/gl_anyhash_primes.h
lib/gl_anyrbtree_list1.h
lib/gl_anyrbtree_list2.h
lib/gl_anytree_list1.h
@@ -23,7 +24,7 @@ xsize
configure.ac:
Makefile.am:
-lib_SOURCES += gl_rbtreehash_list.h gl_rbtreehash_list.c gl_anyhash_list1.h gl_anyhash_list2.h gl_anyrbtree_list1.h gl_anyrbtree_list2.h gl_anytree_list1.h gl_anytree_list2.h gl_anytreehash_list1.h gl_anytreehash_list2.h
+lib_SOURCES += gl_rbtreehash_list.h gl_rbtreehash_list.c gl_anyhash_list1.h gl_anyhash_list2.h gl_anyhash_primes.h gl_anyrbtree_list1.h gl_anyrbtree_list2.h gl_anytree_list1.h gl_anytree_list2.h gl_anytreehash_list1.h gl_anytreehash_list2.h
Include:
"gl_rbtreehash_list.h"
--
2.7.4
>From 96499e27955e55b86d0dd13d36c33decf149aacd Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@clisp.org>
Date: Tue, 4 Dec 2018 00:54:30 +0100
Subject: [PATCH 4/8] hash-set: New module.
* lib/gl_hash_set.h: New file.
* lib/gl_hash_set.c: New file.
* modules/hash-set: New file.
---
ChangeLog | 7 ++
lib/gl_hash_set.c | 315 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
lib/gl_hash_set.h | 34 ++++++
modules/hash-set | 28 +++++
4 files changed, 384 insertions(+)
create mode 100644 lib/gl_hash_set.c
create mode 100644 lib/gl_hash_set.h
create mode 100644 modules/hash-set
diff --git a/ChangeLog b/ChangeLog
index 5f0ae48..a8f2314 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,12 @@
2018-12-03 Bruno Haible <br...@clisp.org>
+ hash-set: New module.
+ * lib/gl_hash_set.h: New file.
+ * lib/gl_hash_set.c: New file.
+ * modules/hash-set: New file.
+
+2018-12-03 Bruno Haible <br...@clisp.org>
+
linkedhash-set: New module.
* lib/gl_linkedhash_set.h: New file.
* lib/gl_linkedhash_set.c: New file.
diff --git a/lib/gl_hash_set.c b/lib/gl_hash_set.c
new file mode 100644
index 0000000..1f2f141
--- /dev/null
+++ b/lib/gl_hash_set.c
@@ -0,0 +1,315 @@
+/* Set data type implemented by a hash table.
+ Copyright (C) 2006, 2008-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <br...@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_set.h"
+
+#include <stdint.h> /* for SIZE_MAX */
+#include <stdlib.h>
+
+#include "xsize.h"
+
+#ifndef uintptr_t
+# define uintptr_t unsigned long
+#endif
+
+/* --------------------------- gl_set_t Data Type --------------------------- */
+
+#include "gl_anyhash_set1.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 *value;
+};
+typedef struct gl_list_node_impl * gl_list_node_t;
+
+/* Concrete gl_set_impl type, valid for this file only. */
+struct gl_set_impl
+{
+ struct gl_set_impl_base base;
+ gl_setelement_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;
+};
+
+#include "gl_anyhash_set2.h"
+
+/* --------------------------- gl_set_t Data Type --------------------------- */
+
+static gl_set_t
+gl_hash_nx_create_empty (gl_set_implementation_t implementation,
+ gl_setelement_equals_fn equals_fn,
+ gl_setelement_hashcode_fn hashcode_fn,
+ gl_setelement_dispose_fn dispose_fn)
+{
+ struct gl_set_impl *set =
+ (struct gl_set_impl *) malloc (sizeof (struct gl_set_impl));
+
+ if (set == NULL)
+ return NULL;
+
+ set->base.vtable = implementation;
+ set->base.equals_fn = equals_fn;
+ set->base.dispose_fn = dispose_fn;
+ set->hashcode_fn = hashcode_fn;
+ set->table_size = 11;
+ set->table =
+ (gl_hash_entry_t *) calloc (set->table_size, sizeof (gl_hash_entry_t));
+ if (set->table == NULL)
+ goto fail;
+ set->count = 0;
+
+ return set;
+
+ fail:
+ free (set);
+ return NULL;
+}
+
+static size_t _GL_ATTRIBUTE_PURE
+gl_hash_size (gl_set_t set)
+{
+ return set->count;
+}
+
+static bool _GL_ATTRIBUTE_PURE
+gl_hash_search (gl_set_t set, const void *elt)
+{
+ size_t hashcode =
+ (set->hashcode_fn != NULL
+ ? set->hashcode_fn (elt)
+ : (size_t)(uintptr_t) elt);
+ size_t bucket = hashcode % set->table_size;
+ gl_setelement_equals_fn equals = set->base.equals_fn;
+
+ /* Look for a match in the hash bucket. */
+ gl_list_node_t node;
+
+ for (node = (gl_list_node_t) set->table[bucket];
+ node != NULL;
+ node = (gl_list_node_t) node->h.hash_next)
+ if (node->h.hashcode == hashcode
+ && (equals != NULL
+ ? equals (elt, node->value)
+ : elt == node->value))
+ return true;
+ return false;
+}
+
+static int
+gl_hash_nx_add (gl_set_t set, const void *elt)
+{
+ size_t hashcode =
+ (set->hashcode_fn != NULL
+ ? set->hashcode_fn (elt)
+ : (size_t)(uintptr_t) elt);
+ size_t bucket = hashcode % set->table_size;
+ gl_setelement_equals_fn equals = set->base.equals_fn;
+
+ /* Look for a match in the hash bucket. */
+ {
+ gl_list_node_t node;
+
+ for (node = (gl_list_node_t) set->table[bucket];
+ node != NULL;
+ node = (gl_list_node_t) node->h.hash_next)
+ if (node->h.hashcode == hashcode
+ && (equals != NULL
+ ? equals (elt, node->value)
+ : elt == node->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->value = elt;
+ node->h.hashcode = hashcode;
+
+ /* Add node to the hash table. */
+ node->h.hash_next = set->table[bucket];
+ set->table[bucket] = &node->h;
+
+ /* Add node to the set. */
+ set->count++;
+
+ hash_resize_after_add (set);
+
+ return 1;
+}
+
+static bool
+gl_hash_remove (gl_set_t set, const void *elt)
+{
+ size_t hashcode =
+ (set->hashcode_fn != NULL
+ ? set->hashcode_fn (elt)
+ : (size_t)(uintptr_t) elt);
+ size_t bucket = hashcode % set->table_size;
+ gl_setelement_equals_fn equals = set->base.equals_fn;
+
+ /* Look for the first match in the hash bucket. */
+ gl_list_node_t *nodep;
+
+ for (nodep = (gl_list_node_t *) &set->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 (elt, node->value)
+ : elt == node->value))
+ {
+ /* Remove node from the hash table. */
+ *nodep = (gl_list_node_t) node->h.hash_next;
+
+ /* Remove node from the set. */
+ set->count--;
+
+ if (set->base.dispose_fn != NULL)
+ set->base.dispose_fn (node->value);
+ free (node);
+ return true;
+ }
+ }
+
+ return false;
+}
+
+static void
+gl_hash_free (gl_set_t set)
+{
+ if (set->count > 0)
+ {
+ gl_setelement_dispose_fn dispose = set->base.dispose_fn;
+ struct gl_hash_entry **table = set->table;
+ size_t i;
+
+ for (i = set->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 (dispose != NULL)
+ dispose (((gl_list_node_t) node)->value);
+ free (node);
+
+ node = next;
+ }
+ }
+ }
+
+ free (set->table);
+ free (set);
+}
+
+/* ---------------------- gl_set_iterator_t Data Type ---------------------- */
+
+/* Here we iterate through the hash buckets. Therefore the order in which the
+ elements are returned is unpredictable. */
+
+static gl_set_iterator_t
+gl_hash_iterator (gl_set_t set)
+{
+ gl_set_iterator_t result;
+
+ result.vtable = set->base.vtable;
+ result.set = set;
+ result.p = NULL; /* runs through the nodes of a bucket */
+ result.i = 0; /* index of the bucket that p points into + 1 */
+ result.j = set->table_size;
+#if defined GCC_LINT || defined lint
+ result.q = NULL;
+ result.count = 0;
+#endif
+
+ return result;
+}
+
+static bool
+gl_hash_iterator_next (gl_set_iterator_t *iterator, const void **eltp)
+{
+ if (iterator->p != NULL)
+ {
+ /* We're traversing a bucket. */
+ gl_list_node_t node = (gl_list_node_t) iterator->p;
+ *eltp = 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->set->table;
+ do
+ {
+ gl_list_node_t node = (gl_list_node_t) table[i++];
+ if (node != NULL)
+ {
+ *eltp = 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_set_iterator_t *iterator)
+{
+}
+
+
+const struct gl_set_implementation gl_hash_set_implementation =
+ {
+ gl_hash_nx_create_empty,
+ gl_hash_size,
+ gl_hash_search,
+ gl_hash_nx_add,
+ gl_hash_remove,
+ gl_hash_free,
+ gl_hash_iterator,
+ gl_hash_iterator_next,
+ gl_hash_iterator_free
+ };
diff --git a/lib/gl_hash_set.h b/lib/gl_hash_set.h
new file mode 100644
index 0000000..7d3d500
--- /dev/null
+++ b/lib/gl_hash_set.h
@@ -0,0 +1,34 @@
+/* Set data type implemented by a hash table.
+ Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <br...@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_SET_H
+#define _GL_HASH_SET_H
+
+#include "gl_set.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+extern const struct gl_set_implementation gl_hash_set_implementation;
+#define GL_HASH_SET &gl_hash_set_implementation
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _GL_HASH_SET_H */
diff --git a/modules/hash-set b/modules/hash-set
new file mode 100644
index 0000000..cd8ac8b
--- /dev/null
+++ b/modules/hash-set
@@ -0,0 +1,28 @@
+Description:
+Set data type implemented by a hash table.
+
+Files:
+lib/gl_hash_set.h
+lib/gl_hash_set.c
+lib/gl_anyhash_set1.h
+lib/gl_anyhash_set2.h
+lib/gl_anyhash_primes.h
+
+Depends-on:
+set
+stdint
+xsize
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += gl_hash_set.h gl_hash_set.c gl_anyhash_set1.h gl_anyhash_set2.h gl_anyhash_primes.h
+
+Include:
+"gl_hash_set.h"
+
+License:
+GPL
+
+Maintainer:
+all
--
2.7.4
>From 9d0b41b846c392c787f4e05407da57ee1c6acde2 Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@clisp.org>
Date: Tue, 4 Dec 2018 00:55:34 +0100
Subject: [PATCH 5/8] xset: New module.
* lib/gl_xset.h: New file.
* lib/gl_xset.c: New file.
* modules/xset: New file.
---
ChangeLog | 7 ++++++
lib/gl_xset.c | 3 +++
lib/gl_xset.h | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
modules/xset | 26 ++++++++++++++++++++
4 files changed, 112 insertions(+)
create mode 100644 lib/gl_xset.c
create mode 100644 lib/gl_xset.h
create mode 100644 modules/xset
diff --git a/ChangeLog b/ChangeLog
index a8f2314..5d26ed2 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,12 @@
2018-12-03 Bruno Haible <br...@clisp.org>
+ xset: New module.
+ * lib/gl_xset.h: New file.
+ * lib/gl_xset.c: New file.
+ * modules/xset: New file.
+
+2018-12-03 Bruno Haible <br...@clisp.org>
+
hash-set: New module.
* lib/gl_hash_set.h: New file.
* lib/gl_hash_set.c: New file.
diff --git a/lib/gl_xset.c b/lib/gl_xset.c
new file mode 100644
index 0000000..83557c0
--- /dev/null
+++ b/lib/gl_xset.c
@@ -0,0 +1,3 @@
+#include <config.h>
+#define GL_XSET_INLINE _GL_EXTERN_INLINE
+#include "gl_xset.h"
diff --git a/lib/gl_xset.h b/lib/gl_xset.h
new file mode 100644
index 0000000..f907b06
--- /dev/null
+++ b/lib/gl_xset.h
@@ -0,0 +1,76 @@
+/* Abstract set data type, with out-of-memory checking.
+ Copyright (C) 2009-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <br...@clisp.org>, 2009.
+
+ 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_XSET_H
+#define _GL_XSET_H
+
+#include "gl_set.h"
+#include "xalloc.h"
+
+#ifndef _GL_INLINE_HEADER_BEGIN
+ #error "Please include config.h first."
+#endif
+_GL_INLINE_HEADER_BEGIN
+#ifndef GL_XSET_INLINE
+# define GL_XSET_INLINE _GL_INLINE
+#endif
+
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* These functions are thin wrappers around the corresponding functions with
+ _nx_ infix from gl_set.h. Upon out-of-memory, they invoke xalloc_die (),
+ instead of returning an error indicator. */
+#if 0 /* These are defined inline below. */
+extern gl_set_t gl_set_create_empty (gl_set_implementation_t implementation,
+ gl_setelement_equals_fn equals_fn,
+ gl_setelement_hashcode_fn hashcode_fn,
+ gl_setelement_dispose_fn dispose_fn);
+extern bool gl_set_add (gl_set_t set, const void *elt);
+#endif
+
+GL_XSET_INLINE gl_set_t
+gl_set_create_empty (gl_set_implementation_t implementation,
+ gl_setelement_equals_fn equals_fn,
+ gl_setelement_hashcode_fn hashcode_fn,
+ gl_setelement_dispose_fn dispose_fn)
+{
+ gl_set_t result =
+ gl_set_nx_create_empty (implementation, equals_fn, hashcode_fn, dispose_fn);
+ if (result == NULL)
+ xalloc_die ();
+ return result;
+}
+
+GL_XSET_INLINE bool
+gl_set_add (gl_set_t set, const void *elt)
+{
+ int result = gl_set_nx_add (set, elt);
+ if (result < 0)
+ xalloc_die ();
+ return result;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+_GL_INLINE_HEADER_END
+
+#endif /* _GL_XSET_H */
diff --git a/modules/xset b/modules/xset
new file mode 100644
index 0000000..d78d5fc
--- /dev/null
+++ b/modules/xset
@@ -0,0 +1,26 @@
+Description:
+Abstract set data type, with out-of-memory checking.
+
+Files:
+lib/gl_xset.h
+lib/gl_xset.c
+
+Depends-on:
+set
+extern-inline
+stdbool
+xalloc-die
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += gl_xset.h gl_xset.c
+
+Include:
+"gl_xset.h"
+
+License:
+GPL
+
+Maintainer:
+all
--
2.7.4
>From 21184e0eab43ca2e5fa9b308e97621b26020ab94 Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@clisp.org>
Date: Tue, 4 Dec 2018 00:56:31 +0100
Subject: [PATCH 6/8] array-set: Add tests.
* tests/test-array_set.c: New file.
* modules/array-set-tests: New file.
---
ChangeLog | 6 ++
modules/array-set-tests | 15 +++++
tests/test-array_set.c | 149 ++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 170 insertions(+)
create mode 100644 modules/array-set-tests
create mode 100644 tests/test-array_set.c
diff --git a/ChangeLog b/ChangeLog
index 5d26ed2..651aa85 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
2018-12-03 Bruno Haible <br...@clisp.org>
+ array-set: Add tests.
+ * tests/test-array_set.c: New file.
+ * modules/array-set-tests: New file.
+
+2018-12-03 Bruno Haible <br...@clisp.org>
+
xset: New module.
* lib/gl_xset.h: New file.
* lib/gl_xset.c: New file.
diff --git a/modules/array-set-tests b/modules/array-set-tests
new file mode 100644
index 0000000..36b077e
--- /dev/null
+++ b/modules/array-set-tests
@@ -0,0 +1,15 @@
+Files:
+tests/test-array_set.c
+tests/macros.h
+
+Depends-on:
+xoset
+array-oset
+xalloc
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-array_set
+check_PROGRAMS += test-array_set
+
diff --git a/tests/test-array_set.c b/tests/test-array_set.c
new file mode 100644
index 0000000..35465ac
--- /dev/null
+++ b/tests/test-array_set.c
@@ -0,0 +1,149 @@
+/* Test of set data type implementation.
+ Copyright (C) 2006-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <br...@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>
+
+#include "gl_array_set.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "gl_xoset.h"
+#include "gl_array_oset.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 RANDOM(n) (rand () % (n))
+#define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
+
+static void
+check_equals (gl_set_t set1, gl_oset_t set2)
+{
+ size_t n = gl_set_size (set1);
+ const void **elements_of_set1 = XNMALLOC (n, const void *);
+ const void **elements_of_set2 = XNMALLOC (n, const void *);
+
+ gl_set_iterator_t iter1;
+ gl_oset_iterator_t iter2;
+ const void *elt1;
+ const void *elt2;
+ size_t i;
+
+ iter1 = gl_set_iterator (set1);
+ iter2 = gl_oset_iterator (set2);
+ for (i = 0; i < n; i++)
+ {
+ ASSERT (gl_set_iterator_next (&iter1, &elt1));
+ ASSERT (gl_oset_iterator_next (&iter2, &elt2));
+ elements_of_set1[i] = elt1;
+ elements_of_set2[i] = elt2;
+ }
+ ASSERT (!gl_set_iterator_next (&iter1, &elt1));
+ ASSERT (!gl_oset_iterator_next (&iter2, &elt2));
+ gl_set_iterator_free (&iter1);
+ gl_oset_iterator_free (&iter2);
+
+ if (n > 0)
+ {
+ qsort (elements_of_set1, n, sizeof (const void *),
+ (int (*) (const void *, const void *)) strcmp);
+ qsort (elements_of_set2, n, sizeof (const void *),
+ (int (*) (const void *, const void *)) strcmp);
+ }
+ for (i = 0; i < n; i++)
+ ASSERT (elements_of_set1[i] == elements_of_set2[i]);
+ free (elements_of_set2);
+ free (elements_of_set1);
+}
+
+static void
+check_all (gl_set_t set1, gl_oset_t set2)
+{
+ check_equals (set1, set2);
+}
+
+int
+main (int argc, char *argv[])
+{
+ gl_set_t set1;
+ gl_oset_t set2;
+
+ /* 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 set1. */
+ set1 = gl_set_nx_create_empty (GL_ARRAY_SET, NULL, NULL, NULL);
+ ASSERT (set1 != NULL);
+
+ /* Create set2. */
+ set2 = gl_oset_create_empty (GL_ARRAY_OSET, (gl_setelement_compar_fn) strcmp, NULL);
+
+ check_all (set1, set2);
+
+ /* Initialize them. */
+ for (i = 0; i < initial_size; i++)
+ {
+ const char *obj = RANDOM_OBJECT ();
+ ASSERT (gl_set_nx_add (set1, obj) == gl_oset_add (set2, obj));
+ check_all (set1, set2);
+ }
+
+ for (repeat = 0; repeat < 100000; repeat++)
+ {
+ unsigned int operation = RANDOM (3);
+ switch (operation)
+ {
+ case 0:
+ {
+ const char *obj = RANDOM_OBJECT ();
+ ASSERT (gl_set_search (set1, obj) == gl_oset_search (set2, obj));
+ }
+ break;
+ case 1:
+ {
+ const char *obj = RANDOM_OBJECT ();
+ ASSERT (gl_set_nx_add (set1, obj) == gl_oset_add (set2, obj));
+ }
+ break;
+ case 2:
+ {
+ const char *obj = RANDOM_OBJECT ();
+ ASSERT (gl_set_remove (set1, obj) == gl_oset_remove (set2, obj));
+ }
+ break;
+ }
+ check_all (set1, set2);
+ }
+
+ gl_set_free (set1);
+ gl_oset_free (set2);
+ }
+
+ return 0;
+}
--
2.7.4
>From 378334d804a1f7f96a87b10eba8715a1cdeaca26 Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@clisp.org>
Date: Tue, 4 Dec 2018 00:57:19 +0100
Subject: [PATCH 7/8] linkedhash-set: Add tests.
* tests/test-linkedhash_set.c: New file.
* modules/linkedhash-set-tests: New file.
---
ChangeLog | 6 ++
modules/linkedhash-set-tests | 13 ++++
tests/test-linkedhash_set.c | 164 +++++++++++++++++++++++++++++++++++++++++++
3 files changed, 183 insertions(+)
create mode 100644 modules/linkedhash-set-tests
create mode 100644 tests/test-linkedhash_set.c
diff --git a/ChangeLog b/ChangeLog
index 651aa85..cf678cc 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
2018-12-03 Bruno Haible <br...@clisp.org>
+ linkedhash-set: Add tests.
+ * tests/test-linkedhash_set.c: New file.
+ * modules/linkedhash-set-tests: New file.
+
+2018-12-03 Bruno Haible <br...@clisp.org>
+
array-set: Add tests.
* tests/test-array_set.c: New file.
* modules/array-set-tests: New file.
diff --git a/modules/linkedhash-set-tests b/modules/linkedhash-set-tests
new file mode 100644
index 0000000..a22c9e0
--- /dev/null
+++ b/modules/linkedhash-set-tests
@@ -0,0 +1,13 @@
+Files:
+tests/test-linkedhash_set.c
+tests/macros.h
+
+Depends-on:
+array-set
+xalloc
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-linkedhash_set
+check_PROGRAMS += test-linkedhash_set
diff --git a/tests/test-linkedhash_set.c b/tests/test-linkedhash_set.c
new file mode 100644
index 0000000..7ff92e8
--- /dev/null
+++ b/tests/test-linkedhash_set.c
@@ -0,0 +1,164 @@
+/* Test of set data type implementation.
+ Copyright (C) 2006-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <br...@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>
+
+#include "gl_linkedhash_set.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "gl_array_set.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 RANDOM(n) (rand () % (n))
+#define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
+
+static void
+check_equals (gl_set_t set1, gl_set_t set2)
+{
+ size_t n = gl_set_size (set1);
+ const void **elements_of_set1 = XNMALLOC (n, const void *);
+ const void **elements_of_set2 = XNMALLOC (n, const void *);
+
+ gl_set_iterator_t iter1;
+ gl_set_iterator_t iter2;
+ const void *elt1;
+ const void *elt2;
+ size_t i;
+
+ iter1 = gl_set_iterator (set1);
+ iter2 = gl_set_iterator (set2);
+ for (i = 0; i < n; i++)
+ {
+ ASSERT (gl_set_iterator_next (&iter1, &elt1));
+ ASSERT (gl_set_iterator_next (&iter2, &elt2));
+ elements_of_set1[i] = elt1;
+ elements_of_set2[i] = elt2;
+ }
+ ASSERT (!gl_set_iterator_next (&iter1, &elt1));
+ ASSERT (!gl_set_iterator_next (&iter2, &elt2));
+ gl_set_iterator_free (&iter1);
+ gl_set_iterator_free (&iter2);
+
+ if (n > 0)
+ {
+ qsort (elements_of_set1, n, sizeof (const void *),
+ (int (*) (const void *, const void *)) strcmp);
+ qsort (elements_of_set2, n, sizeof (const void *),
+ (int (*) (const void *, const void *)) strcmp);
+ }
+ for (i = 0; i < n; i++)
+ ASSERT (elements_of_set1[i] == elements_of_set2[i]);
+ free (elements_of_set2);
+ free (elements_of_set1);
+}
+
+static void
+check_all (gl_set_t set1, gl_set_t set2)
+{
+ check_equals (set1, set2);
+}
+
+static bool
+string_equals (const void *elt1, const void *elt2)
+{
+ return strcmp ((const char *) elt1, (const char *) elt2) == 0;
+}
+
+static size_t
+string_hashcode (const void *elt)
+{
+ size_t hashcode = 0;
+ const char *s;
+ for (s = (const char *) elt; *s != '\0'; s++)
+ hashcode += (unsigned char) *s;
+ return hashcode;
+}
+
+int
+main (int argc, char *argv[])
+{
+ gl_set_t set1, set2;
+
+ /* 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 set1. */
+ set1 = gl_set_nx_create_empty (GL_ARRAY_SET, string_equals, string_hashcode, NULL);
+ ASSERT (set1 != NULL);
+
+ /* Create set2. */
+ set2 = gl_set_nx_create_empty (GL_LINKEDHASH_SET, string_equals, string_hashcode, NULL);
+ ASSERT (set2 != NULL);
+
+ check_all (set1, set2);
+
+ /* Initialize them. */
+ for (i = 0; i < initial_size; i++)
+ {
+ const char *obj = RANDOM_OBJECT ();
+ ASSERT (gl_set_nx_add (set1, obj) == gl_set_nx_add (set2, obj));
+ check_all (set1, set2);
+ }
+
+ for (repeat = 0; repeat < 100000; repeat++)
+ {
+ unsigned int operation = RANDOM (3);
+ switch (operation)
+ {
+ case 0:
+ {
+ const char *obj = RANDOM_OBJECT ();
+ ASSERT (gl_set_search (set1, obj) == gl_set_search (set2, obj));
+ }
+ break;
+ case 1:
+ {
+ const char *obj = RANDOM_OBJECT ();
+ ASSERT (gl_set_nx_add (set1, obj) == gl_set_nx_add (set2, obj));
+ }
+ break;
+ case 2:
+ {
+ const char *obj = RANDOM_OBJECT ();
+ ASSERT (gl_set_remove (set1, obj) == gl_set_remove (set2, obj));
+ }
+ break;
+ }
+ check_all (set1, set2);
+ }
+
+ gl_set_free (set1);
+ gl_set_free (set2);
+ }
+
+ return 0;
+}
--
2.7.4
>From f7f4d0684141dc9bb703f7a29add16c04350fc3c Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@clisp.org>
Date: Tue, 4 Dec 2018 00:57:58 +0100
Subject: [PATCH 8/8] hash-set: Add tests.
* tests/test-hash_set.c: New file.
* modules/hash-set-tests: New file.
---
ChangeLog | 6 ++
modules/hash-set-tests | 13 ++++
tests/test-hash_set.c | 164 +++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 183 insertions(+)
create mode 100644 modules/hash-set-tests
create mode 100644 tests/test-hash_set.c
diff --git a/ChangeLog b/ChangeLog
index cf678cc..b96d8e6 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
2018-12-03 Bruno Haible <br...@clisp.org>
+ hash-set: Add tests.
+ * tests/test-hash_set.c: New file.
+ * modules/hash-set-tests: New file.
+
+2018-12-03 Bruno Haible <br...@clisp.org>
+
linkedhash-set: Add tests.
* tests/test-linkedhash_set.c: New file.
* modules/linkedhash-set-tests: New file.
diff --git a/modules/hash-set-tests b/modules/hash-set-tests
new file mode 100644
index 0000000..c98898c
--- /dev/null
+++ b/modules/hash-set-tests
@@ -0,0 +1,13 @@
+Files:
+tests/test-hash_set.c
+tests/macros.h
+
+Depends-on:
+array-set
+xalloc
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-hash_set
+check_PROGRAMS += test-hash_set
diff --git a/tests/test-hash_set.c b/tests/test-hash_set.c
new file mode 100644
index 0000000..d791074
--- /dev/null
+++ b/tests/test-hash_set.c
@@ -0,0 +1,164 @@
+/* Test of set data type implementation.
+ Copyright (C) 2006-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible <br...@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>
+
+#include "gl_hash_set.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "gl_array_set.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 RANDOM(n) (rand () % (n))
+#define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
+
+static void
+check_equals (gl_set_t set1, gl_set_t set2)
+{
+ size_t n = gl_set_size (set1);
+ const void **elements_of_set1 = XNMALLOC (n, const void *);
+ const void **elements_of_set2 = XNMALLOC (n, const void *);
+
+ gl_set_iterator_t iter1;
+ gl_set_iterator_t iter2;
+ const void *elt1;
+ const void *elt2;
+ size_t i;
+
+ iter1 = gl_set_iterator (set1);
+ iter2 = gl_set_iterator (set2);
+ for (i = 0; i < n; i++)
+ {
+ ASSERT (gl_set_iterator_next (&iter1, &elt1));
+ ASSERT (gl_set_iterator_next (&iter2, &elt2));
+ elements_of_set1[i] = elt1;
+ elements_of_set2[i] = elt2;
+ }
+ ASSERT (!gl_set_iterator_next (&iter1, &elt1));
+ ASSERT (!gl_set_iterator_next (&iter2, &elt2));
+ gl_set_iterator_free (&iter1);
+ gl_set_iterator_free (&iter2);
+
+ if (n > 0)
+ {
+ qsort (elements_of_set1, n, sizeof (const void *),
+ (int (*) (const void *, const void *)) strcmp);
+ qsort (elements_of_set2, n, sizeof (const void *),
+ (int (*) (const void *, const void *)) strcmp);
+ }
+ for (i = 0; i < n; i++)
+ ASSERT (elements_of_set1[i] == elements_of_set2[i]);
+ free (elements_of_set2);
+ free (elements_of_set1);
+}
+
+static void
+check_all (gl_set_t set1, gl_set_t set2)
+{
+ check_equals (set1, set2);
+}
+
+static bool
+string_equals (const void *elt1, const void *elt2)
+{
+ return strcmp ((const char *) elt1, (const char *) elt2) == 0;
+}
+
+static size_t
+string_hashcode (const void *elt)
+{
+ size_t hashcode = 0;
+ const char *s;
+ for (s = (const char *) elt; *s != '\0'; s++)
+ hashcode += (unsigned char) *s;
+ return hashcode;
+}
+
+int
+main (int argc, char *argv[])
+{
+ gl_set_t set1, set2;
+
+ /* 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 set1. */
+ set1 = gl_set_nx_create_empty (GL_ARRAY_SET, string_equals, string_hashcode, NULL);
+ ASSERT (set1 != NULL);
+
+ /* Create set2. */
+ set2 = gl_set_nx_create_empty (GL_HASH_SET, string_equals, string_hashcode, NULL);
+ ASSERT (set2 != NULL);
+
+ check_all (set1, set2);
+
+ /* Initialize them. */
+ for (i = 0; i < initial_size; i++)
+ {
+ const char *obj = RANDOM_OBJECT ();
+ ASSERT (gl_set_nx_add (set1, obj) == gl_set_nx_add (set2, obj));
+ check_all (set1, set2);
+ }
+
+ for (repeat = 0; repeat < 100000; repeat++)
+ {
+ unsigned int operation = RANDOM (3);
+ switch (operation)
+ {
+ case 0:
+ {
+ const char *obj = RANDOM_OBJECT ();
+ ASSERT (gl_set_search (set1, obj) == gl_set_search (set2, obj));
+ }
+ break;
+ case 1:
+ {
+ const char *obj = RANDOM_OBJECT ();
+ ASSERT (gl_set_nx_add (set1, obj) == gl_set_nx_add (set2, obj));
+ }
+ break;
+ case 2:
+ {
+ const char *obj = RANDOM_OBJECT ();
+ ASSERT (gl_set_remove (set1, obj) == gl_set_remove (set2, obj));
+ }
+ break;
+ }
+ check_all (set1, set2);
+ }
+
+ gl_set_free (set1);
+ gl_set_free (set2);
+ }
+
+ return 0;
+}
--
2.7.4
