Re: generic container for sets

[Bruno Haible]

These *-set patches introduced a bit of code duplication. This patch here
reduces the code duplication again.


2018-12-11  Bruno Haible  

hash-set, linkedhash-set: Reduce code duplication.
* lib/gl_anyhash1.h: Rename from lib/gl_anyhash_list1.h and
lib/gl_anyhash_set1.h.
* lib/gl_anyhash2.h: Rename from lib/gl_anyhash_list2.h and
lib/gl_anyhash_set2.h. Parameterize.
(hash_resize_after_add): New function, from lib/gl_anyhash_set2.h.
* lib/gl_anytreehash_list1.h (hash_resize_after_add): Remove function.
* lib/gl_avltreehash_list.c: Include gl_anyhash1.h instead of
gl_anyhash_list1.h. Include gl_anyhash2.h instead of gl_anyhash_list2.h.
* lib/gl_rbtreehash_list.c: Likewise.
* lib/gl_linkedhash_list.c: Likewise.
(hash_resize_after_add): Remove function.
* lib/gl_linkedhash_set.c: Include gl_anyhash1.h instead of
gl_anyhash_set1.h. Include gl_anyhash2.h instead of gl_anyhash_set2.h.
* gl_hash_set.c: Likewise.
* modules/avltreehash-list (Files, Makefile.am): Update file list.
* modules/rbtreehash-list (Files, Makefile.am): Likewise.
* modules/linkedhash-list (Files, Makefile.am): Likewise.
* modules/linkedhash-set (Files, Makefile.am): Likewise.
* modules/hash-set (Files, Makefile.am): Likewise.

diff --git a/lib/gl_anyhash1.h b/lib/gl_anyhash1.h
new file mode 100644
index 000..86bdee3
--- /dev/null
+++ b/lib/gl_anyhash1.h
@@ -0,0 +1,30 @@
+/* Hash table for sequential list, set, and map data type.
+   Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc.
+   Written by Bruno Haible , 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 .  */
+
+/* Common code of
+   gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c,
+   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 key (for map data type) or
+   - the value (for list, set data types) 
*/
+};
+typedef struct gl_hash_entry * gl_hash_entry_t;
diff --git a/lib/gl_anyhash2.h b/lib/gl_anyhash2.h
new file mode 100644
index 000..d4c5430
--- /dev/null
+++ b/lib/gl_anyhash2.h
@@ -0,0 +1,81 @@
+/* Hash table for sequential list, set, and map data type.
+   Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc.
+   Written by Bruno Haible , 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 .  */
+
+/* Common code of
+   gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c,
+   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 (CONTAINER_T container, size_t estimate)
+{
+  size_t new_size = next_prime (estimate);
+
+  if (new_size > container->table_size)
+{
+  gl_hash_entry_t *old_table = container->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 = container->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 = 

Re: generic container for sets

[Bruno Haible]

A small optimization.


2018-12-11  Bruno Haible  

array-set: Optimize.
* lib/gl_array_set.c (gl_array_search, gl_array_remove): Test equals_fn
outside the loop, not inside the loop.

diff --git a/lib/gl_array_set.c b/lib/gl_array_set.c
index dd77ef1..8e985af 100644
--- a/lib/gl_array_set.c
+++ b/lib/gl_array_set.c
@@ -79,11 +79,22 @@ gl_array_search (gl_set_t set, const void *elt)
 {
   gl_setelement_equals_fn equals = set->base.equals_fn;
   const void **elements = set->elements;
-  size_t i;
+  if (equals != NULL)
+{
+  size_t i;
 
-  for (i = 0; i < count; i++)
-if (equals != NULL ? equals (elements[i], elt) : elements[i] == elt)
-  return true;
+  for (i = 0; i < count; i++)
+if (equals (elements[i], elt))
+  return true;
+}
+  else
+{
+  size_t i;
+
+  for (i = 0; i < count; i++)
+if (elements[i] == elt)
+  return true;
+}
 }
   return false;
 }
@@ -155,14 +166,29 @@ gl_array_remove (gl_set_t set, const void *elt)
 {
   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;
-  }
+
+  if (equals != NULL)
+{
+  size_t i;
+
+  for (i = 0; i < count; i++)
+if (equals (elements[i], elt))
+  {
+gl_array_remove_at (set, i);
+return true;
+  }
+}
+  else
+{
+  size_t i;
+
+  for (i = 0; i < count; i++)
+if (elements[i] == elt)
+  {
+gl_array_remove_at (set, i);
+return true;
+  }
+}
 }
   return false;
 }

Re: generic container for sets

[Bruno Haible]

Oops, I made a wrong use of qsort() in the tests. This should fix it.


2018-12-11  Bruno Haible  

array-set, linkedhash-set, hash-set: Fix tests.
* tests/test-array_set.c (cmp_objects_in_array): New function.
(check_equals): Use it.
* tests/test-hash_set.c: Likewise.
* tests/test-linkedhash_set.c: Likewise.

diff --git a/tests/test-array_set.c b/tests/test-array_set.c
index 35465ac..91f1294 100644
--- a/tests/test-array_set.c
+++ b/tests/test-array_set.c
@@ -36,6 +36,14 @@ static const char *objects[30] =
 #define RANDOM(n) (rand () % (n))
 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
 
+static int
+cmp_objects_in_array (const void *objptr1, const void *objptr2)
+{
+  const void *obj1 = *(const void * const *)objptr1;
+  const void *obj2 = *(const void * const *)objptr2;
+  return strcmp ((const char *) obj1, (const char *) obj2);
+}
+
 static void
 check_equals (gl_set_t set1, gl_oset_t set2)
 {
@@ -65,10 +73,8 @@ check_equals (gl_set_t set1, gl_oset_t set2)
 
   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);
+  qsort (elements_of_set1, n, sizeof (const void *), cmp_objects_in_array);
+  qsort (elements_of_set2, n, sizeof (const void *), cmp_objects_in_array);
 }
   for (i = 0; i < n; i++)
 ASSERT (elements_of_set1[i] == elements_of_set2[i]);
diff --git a/tests/test-hash_set.c b/tests/test-hash_set.c
index d791074..a2138ef 100644
--- a/tests/test-hash_set.c
+++ b/tests/test-hash_set.c
@@ -35,6 +35,14 @@ static const char *objects[30] =
 #define RANDOM(n) (rand () % (n))
 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
 
+static int
+cmp_objects_in_array (const void *objptr1, const void *objptr2)
+{
+  const void *obj1 = *(const void * const *)objptr1;
+  const void *obj2 = *(const void * const *)objptr2;
+  return strcmp ((const char *) obj1, (const char *) obj2);
+}
+
 static void
 check_equals (gl_set_t set1, gl_set_t set2)
 {
@@ -64,10 +72,8 @@ check_equals (gl_set_t set1, gl_set_t set2)
 
   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);
+  qsort (elements_of_set1, n, sizeof (const void *), cmp_objects_in_array);
+  qsort (elements_of_set2, n, sizeof (const void *), cmp_objects_in_array);
 }
   for (i = 0; i < n; i++)
 ASSERT (elements_of_set1[i] == elements_of_set2[i]);
diff --git a/tests/test-linkedhash_set.c b/tests/test-linkedhash_set.c
index 7ff92e8..6ad33a5 100644
--- a/tests/test-linkedhash_set.c
+++ b/tests/test-linkedhash_set.c
@@ -35,6 +35,14 @@ static const char *objects[30] =
 #define RANDOM(n) (rand () % (n))
 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
 
+static int
+cmp_objects_in_array (const void *objptr1, const void *objptr2)
+{
+  const void *obj1 = *(const void * const *)objptr1;
+  const void *obj2 = *(const void * const *)objptr2;
+  return strcmp ((const char *) obj1, (const char *) obj2);
+}
+
 static void
 check_equals (gl_set_t set1, gl_set_t set2)
 {
@@ -64,10 +72,8 @@ check_equals (gl_set_t set1, gl_set_t set2)
 
   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);
+  qsort (elements_of_set1, n, sizeof (const void *), cmp_objects_in_array);
+  qsort (elements_of_set2, n, sizeof (const void *), cmp_objects_in_array);
 }
   for (i = 0; i < n; i++)
 ASSERT (elements_of_set1[i] == elements_of_set2[i]);

Re: generic container for sets

[Bruno Haible]

There were no comments. So I pushed this.

Bruno