From 65d43159b0f6c9db2cae327473eddf13d2394ff6 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Wed, 25 Nov 2009 21:21:03 -0800 Subject: [PATCH] New data type string_set, a set of unique strings. --- src/libpspp/automake.mk | 2 + src/libpspp/string-set.c | 261 ++++++++++++ src/libpspp/string-set.h | 148 +++++++ tests/automake.mk | 9 + tests/libpspp/string-set-test.c | 681 ++++++++++++++++++++++++++++++++ 5 files changed, 1101 insertions(+) create mode 100644 src/libpspp/string-set.c create mode 100644 src/libpspp/string-set.h create mode 100644 tests/libpspp/string-set-test.c diff --git a/src/libpspp/automake.mk b/src/libpspp/automake.mk index 746756d8..bba2dff9 100644 --- a/src/libpspp/automake.mk +++ b/src/libpspp/automake.mk @@ -65,6 +65,8 @@ src_libpspp_libpspp_la_SOURCES = \ src/libpspp/sparse-xarray.h \ src/libpspp/start-date.c \ src/libpspp/start-date.h \ + src/libpspp/string-set.c \ + src/libpspp/string-set.h \ src/libpspp/str.c \ src/libpspp/str.h \ src/libpspp/taint.c \ diff --git a/src/libpspp/string-set.c b/src/libpspp/string-set.c new file mode 100644 index 00000000..3fd370db --- /dev/null +++ b/src/libpspp/string-set.c @@ -0,0 +1,261 @@ +/* PSPP - a program for statistical analysis. + Copyright (C) 2009 Free Software Foundation, Inc. + + 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 . */ + +/* If you add routines in this file, please add a corresponding test to + string-set-test.c. */ + +#include + +#include + +#include +#include + +#include + +#include "gl/xalloc.h" + +static struct string_set_node *string_set_find_node__ ( + const struct string_set *, const char *, unsigned int hash); +static void string_set_insert__ (struct string_set *, char *, + unsigned int hash); +static bool string_set_delete__ (struct string_set *, const char *, + unsigned int hash); + +/* Initializes SET as a new string set that is initially empty. */ +void +string_set_init (struct string_set *set) +{ + hmap_init (&set->hmap); +} + +/* Initializes SET as a new string set that initially contains the same strings + as OLD. */ +void +string_set_clone (struct string_set *set, const struct string_set *old) +{ + const struct string_set_node *node; + const char *s; + + string_set_init (set); + hmap_reserve (&set->hmap, string_set_count (old)); + STRING_SET_FOR_EACH (s, node, old) + string_set_insert__ (set, xstrdup (s), node->hmap_node.hash); +} + +/* Exchanges the contents of string sets A and B. */ +void +string_set_swap (struct string_set *a, struct string_set *b) +{ + hmap_swap (&a->hmap, &b->hmap); +} + +/* Frees SET and its nodes and strings. */ +void +string_set_destroy (struct string_set *set) +{ + if (set != NULL) + { + string_set_clear (set); + hmap_destroy (&set->hmap); + } +} + +/* Returns true if SET contains S, false otherwise. */ +bool +string_set_contains (const struct string_set *set, const char *s) +{ + return string_set_find_node (set, s) != NULL; +} + +/* Returns the node in SET that contains S, or a null pointer if SET does not + contain S. */ +struct string_set_node * +string_set_find_node (const struct string_set *set, const char *s) +{ + return string_set_find_node__ (set, s, hash_string (s, 0)); +} + +/* Inserts a copy of S into SET. Returns true if successful, false if SET + is unchanged because it already contained S. */ +bool +string_set_insert (struct string_set *set, const char *s) +{ + unsigned int hash = hash_string (s, 0); + if (!string_set_find_node__ (set, s, hash)) + { + string_set_insert__ (set, xstrdup (s), hash); + return true; + } + else + return false; +} + +/* Inserts S, which must be a malloc'd string, into SET, transferring ownership + of S to SET. Returns true if successful, false if SET is unchanged because + it already contained a copy of S. (In the latter case, S is freed.) */ +bool +string_set_insert_nocopy (struct string_set *set, char *s) +{ + unsigned int hash = hash_string (s, 0); + if (!string_set_find_node__ (set, s, hash)) + { + string_set_insert__ (set, s, hash); + return true; + } + else + { + free (s); + return false; + } +} + +/* Deletes S from SET. Returns true if successful, false if SET is unchanged + because it did not contain a copy of S. */ +bool +string_set_delete (struct string_set *set, const char *s) +{ + return string_set_delete__ (set, s, hash_string (s, 0)); +} + +/* Deletes NODE from SET, and frees NODE and its string. */ +void +string_set_delete_node (struct string_set *set, struct string_set_node *node) +{ + free (string_set_delete_nofree (set, node)); +} + +/* Deletes NODE from SET and frees NODE. Returns the string that NODE + contained, transferring ownership to the caller. */ +char * +string_set_delete_nofree (struct string_set *set, struct string_set_node *node) +{ + char *string = node->string; + hmap_delete (&set->hmap, &node->hmap_node); + free (node); + return string; +} + +/* Removes all nodes from SET. */ +void +string_set_clear (struct string_set *set) +{ + struct string_set_node *node, *next; + + HMAP_FOR_EACH_SAFE (node, next, struct string_set_node, hmap_node, + &set->hmap) + string_set_delete_node (set, node); +} + +/* Calculates A = union(A, B). + + If B may be modified, string_set_union_and_intersection() is + faster than this function. */ +void +string_set_union (struct string_set *a, const struct string_set *b) +{ + struct string_set_node *node; + HMAP_FOR_EACH (node, struct string_set_node, hmap_node, &b->hmap) + if (!string_set_find_node__ (a, node->string, node->hmap_node.hash)) + string_set_insert__ (a, xstrdup (node->string), node->hmap_node.hash); +} + +/* Calculates A = union(A, B) and B = intersect(A, B). + + If only the intersection is needed, string_set_intersect() is + faster. */ +void +string_set_union_and_intersection (struct string_set *a, struct string_set *b) +{ + struct string_set_node *node, *next; + + HMAP_FOR_EACH_SAFE (node, next, struct string_set_node, hmap_node, + &b->hmap) + if (!string_set_find_node__ (a, node->string, node->hmap_node.hash)) + { + hmap_delete (&b->hmap, &node->hmap_node); + hmap_insert (&a->hmap, &node->hmap_node, node->hmap_node.hash); + } +} + +/* Calculates A = intersect(A, B). */ +void +string_set_intersect (struct string_set *a, const struct string_set *b) +{ + struct string_set_node *node, *next; + + HMAP_FOR_EACH_SAFE (node, next, struct string_set_node, hmap_node, + &a->hmap) + if (!string_set_find_node__ (b, node->string, node->hmap_node.hash)) + string_set_delete_node (a, node); +} + +/* Removes from A all of the strings in B. */ +void +string_set_subtract (struct string_set *a, const struct string_set *b) +{ + struct string_set_node *node, *next; + + if (string_set_count (a) < string_set_count (b)) + { + HMAP_FOR_EACH_SAFE (node, next, struct string_set_node, hmap_node, + &a->hmap) + if (string_set_find_node__ (b, node->string, node->hmap_node.hash)) + string_set_delete_node (a, node); + } + else + { + HMAP_FOR_EACH (node, struct string_set_node, hmap_node, &b->hmap) + string_set_delete__ (a, node->string, node->hmap_node.hash); + } +} + +/* Internal functions. */ + +static struct string_set_node * +string_set_find_node__ (const struct string_set *set, const char *s, + unsigned int hash) +{ + struct string_set_node *node; + + HMAP_FOR_EACH_WITH_HASH (node, struct string_set_node, hmap_node, + hash, &set->hmap) + if (!strcmp (s, node->string)) + return node; + + return NULL; +} + +static void +string_set_insert__ (struct string_set *set, char *s, unsigned int hash) +{ + struct string_set_node *node = xmalloc (sizeof *node); + node->string = s; + hmap_insert (&set->hmap, &node->hmap_node, hash); +} + +static bool +string_set_delete__ (struct string_set *set, const char *s, unsigned int hash) +{ + struct string_set_node *node = string_set_find_node__ (set, s, hash); + if (node != NULL) + { + string_set_delete_node (set, node); + return true; + } + else + return false; +} diff --git a/src/libpspp/string-set.h b/src/libpspp/string-set.h new file mode 100644 index 00000000..a604e151 --- /dev/null +++ b/src/libpspp/string-set.h @@ -0,0 +1,148 @@ +/* PSPP - a program for statistical analysis. + Copyright (C) 2009 Free Software Foundation, Inc. + + 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 . */ + +#ifndef LIBPSPP_STRING_SET_H +#define LIBPSPP_STRING_SET_H + +/* Set of unique strings. + + This is a convenient wrapper around a "struct hmap" for storing strings. */ + +#include +#include + +/* A node in the string set. */ +struct string_set_node + { + struct hmap_node hmap_node; + char *string; + }; + +/* Returns the string within NODE. The caller must not modify or free the + returned string. */ +static inline const char * +string_set_node_get_string (const struct string_set_node *node) +{ + return node->string; +} + +/* An unordered set of unique strings. */ +struct string_set + { + struct hmap hmap; + }; + +/* Suitable for use as the initializer for a string_set named SET. Typical + usage: + struct string_set set = STRING_SET_INITIALIZER (set); + STRING_SET_INITIALIZER is an alternative to calling string_set_init. */ +#define STRING_SET_INITIALIZER(SET) { HMAP_INITIALIZER ((SET).hmap) } + +void string_set_init (struct string_set *); +void string_set_clone (struct string_set *, const struct string_set *); +void string_set_swap (struct string_set *, struct string_set *); +void string_set_destroy (struct string_set *); + +static inline size_t string_set_count (const struct string_set *); +static inline bool string_set_is_empty (const struct string_set *); + +bool string_set_contains (const struct string_set *, const char *); +struct string_set_node *string_set_find_node (const struct string_set *, + const char *); + +bool string_set_insert (struct string_set *, const char *); +bool string_set_insert_nocopy (struct string_set *, char *); +bool string_set_delete (struct string_set *, const char *); +void string_set_delete_node (struct string_set *, struct string_set_node *); +char *string_set_delete_nofree (struct string_set *, struct string_set_node *); + +void string_set_clear (struct string_set *); +void string_set_union (struct string_set *, const struct string_set *); +void string_set_union_and_intersection (struct string_set *, + struct string_set *); +void string_set_intersect (struct string_set *, const struct string_set *); +void string_set_subtract (struct string_set *, const struct string_set *); + +static inline const struct string_set_node *string_set_first ( + const struct string_set *); +static inline const struct string_set_node *string_set_next ( + const struct string_set *, const struct string_set_node *); + +/* Macros for conveniently iterating through a string_set, e.g. to print all of + the strings in "my_set": + + struct string_set_node *node; + const char *string; + + STRING_SET_FOR_EACH (string, node, &my_set) + puts (string); + */ +#define STRING_SET_FOR_EACH(STRING, NODE, SET) \ + for ((NODE) = string_set_first (SET); \ + ((NODE) != NULL \ + ? ((STRING) = string_set_node_get_string (NODE), \ + 1) \ + : 0); \ + (NODE) = string_set_next (SET, NODE)) +#define STRING_SET_FOR_EACH_SAFE(STRING, NODE, NEXT, SET) \ + for ((NODE) = string_set_first (SET); \ + ((NODE) != NULL \ + ? ((STRING) = string_set_node_get_string (NODE), \ + (NEXT) = string_set_next (SET, NODE), \ + 1) \ + : 0); \ + (NODE) = (NEXT)) + +/* Returns the number of strings currently in SET. */ +static inline size_t +string_set_count (const struct string_set *set) +{ + return hmap_count (&set->hmap); +} + +/* Returns true if SET currently contains no strings, false otherwise. */ +static inline bool +string_set_is_empty (const struct string_set *set) +{ + return hmap_is_empty (&set->hmap); +} + +/* Returns the first node in SET, or a null pointer if SET is empty. See the + hmap_first function for information about complexity (O(1) amortized) and + ordering (arbitrary). + + The STRING_SET_FOR_EACH and STRING_SET_FOR_EACH_SAFE macros provide + convenient ways to iterate over all the nodes in a string set. */ +static inline const struct string_set_node * +string_set_first (const struct string_set *set) +{ + return HMAP_FIRST (struct string_set_node, hmap_node, &set->hmap); +} + +/* Returns the next node in SET following NODE, or a null pointer if NODE is + the last node in SET. See the hmap_next function for information about + complexity (O(1) amortized) and ordering (arbitrary). + + The STRING_SET_FOR_EACH and STRING_SET_FOR_EACH_SAFE macros provide + convenient ways to iterate over all the nodes in a string set. */ +static inline const struct string_set_node * +string_set_next (const struct string_set *set, + const struct string_set_node *node) +{ + return HMAP_NEXT (node, struct string_set_node, hmap_node, &set->hmap); +} + +#endif /* libpspp/string-set.h */ diff --git a/tests/automake.mk b/tests/automake.mk index 8a974a32..180d656b 100644 --- a/tests/automake.mk +++ b/tests/automake.mk @@ -194,6 +194,7 @@ nodist_TESTS = \ tests/libpspp/range-set-test \ tests/libpspp/sparse-array-test \ tests/libpspp/str-test \ + tests/libpspp/string-set-test \ tests/libpspp/tower-test TESTS = $(dist_TESTS) $(nodist_TESTS) @@ -288,6 +289,14 @@ tests_libpspp_str_test_SOURCES = \ tests/libpspp/str-test.c tests_libpspp_str_test_LDADD = src/libpspp/libpspp.la gl/libgl.la $(LIBINTL) +tests_libpspp_string_set_test_SOURCES = \ + src/libpspp/hash-functions.c \ + src/libpspp/hmap.c \ + src/libpspp/string-set.c \ + tests/libpspp/string-set-test.c +tests_libpspp_string_set_test_LDADD = gl/libgl.la $(LIBINTL) +tests_libpspp_string_set_test_CPPFLAGS = $(AM_CPPFLAGS) -DASSERT_LEVEL=10 + tests_libpspp_tower_test_SOURCES = \ src/libpspp/abt.c \ src/libpspp/abt.h \ diff --git a/tests/libpspp/string-set-test.c b/tests/libpspp/string-set-test.c new file mode 100644 index 00000000..6aafef44 --- /dev/null +++ b/tests/libpspp/string-set-test.c @@ -0,0 +1,681 @@ +/* PSPP - a program for statistical analysis. + Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. + + 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 . */ + +/* This is a test program for the string_set_* routines defined in + string-set.c. This test program aims to be as comprehensive as possible. + "gcov -a -b" should report almost complete coverage of lines, blocks and + branches in string-set.c, except that one branch caused by hash collision is + not exercised because our hash function has so few collisions. "valgrind + --leak-check=yes --show-reachable=yes" should give a clean report. */ + +#include + +#include + +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +/* Currently running test. */ +static const char *test_name; + +/* Exit with a failure code. + (Place a breakpoint on this function while debugging.) */ +static void +check_die (void) +{ + exit (EXIT_FAILURE); +} + +/* If OK is not true, prints a message about failure on the + current source file and the given LINE and terminates. */ +static void +check_func (bool ok, int line) +{ + if (!ok) + { + printf ("Check failed in %s test at %s, line %d\n", + test_name, __FILE__, line); + check_die (); + } +} + +/* Verifies that EXPR evaluates to true. + If not, prints a message citing the calling line number and + terminates. */ +#define check(EXPR) check_func ((EXPR), __LINE__) + +/* Prints a message about memory exhaustion and exits with a + failure code. */ +static void +xalloc_die (void) +{ + printf ("virtual memory exhausted\n"); + exit (EXIT_FAILURE); +} + +static void *xmalloc (size_t n) MALLOC_LIKE; +static void *xnmalloc (size_t n, size_t m) MALLOC_LIKE; +static void *xmemdup (const void *p, size_t n) MALLOC_LIKE; + +/* Allocates and returns N bytes of memory. */ +static void * +xmalloc (size_t n) +{ + if (n != 0) + { + void *p = malloc (n); + if (p == NULL) + xalloc_die (); + + return p; + } + else + return NULL; +} + +static void * +xmemdup (const void *p, size_t n) +{ + void *q = xmalloc (n); + memcpy (q, p, n); + return q; +} + +/* Clone STRING. */ +static char * +xstrdup (const char *string) +{ + return xmemdup (string, strlen (string) + 1); +} + +/* Allocates and returns N * M bytes of memory. */ +static void * +xnmalloc (size_t n, size_t m) +{ + if ((size_t) -1 / m <= n) + xalloc_die (); + return xmalloc (n * m); +} + +/* Support routines. */ + +enum { MAX_VALUE = 1024 }; + +static char *string_table[MAX_VALUE]; + +static const char * +make_string (int value) +{ + char **s; + + assert (value >= 0 && value < MAX_VALUE); + s = &string_table[value]; + if (*s == NULL) + { + *s = xmalloc (16); + sprintf (*s, "%d", value); + } + return *s; +} + +static void +free_strings (void) +{ + int i; + + for (i = 0; i < MAX_VALUE; i++) + free (string_table[i]); +} + +/* Swaps *A and *B. */ +static void +swap (int *a, int *b) +{ + int t = *a; + *a = *b; + *b = t; +} + +/* Reverses the order of the CNT integers starting at VALUES. */ +static void +reverse (int *values, size_t cnt) +{ + size_t i = 0; + size_t j = cnt; + + while (j > i) + swap (&values[i++], &values[--j]); +} + +/* Arranges the CNT elements in VALUES into the lexicographically + next greater permutation. Returns true if successful. + If VALUES is already the lexicographically greatest + permutation of its elements (i.e. ordered from greatest to + smallest), arranges them into the lexicographically least + permutation (i.e. ordered from smallest to largest) and + returns false. */ +static bool +next_permutation (int *values, size_t cnt) +{ + if (cnt > 0) + { + size_t i = cnt - 1; + while (i != 0) + { + i--; + if (values[i] < values[i + 1]) + { + size_t j; + for (j = cnt - 1; values[i] >= values[j]; j--) + continue; + swap (values + i, values + j); + reverse (values + (i + 1), cnt - (i + 1)); + return true; + } + } + + reverse (values, cnt); + } + + return false; +} + +/* Returns N!. */ +static unsigned int +factorial (unsigned int n) +{ + unsigned int value = 1; + while (n > 1) + value *= n--; + return value; +} + +/* Randomly shuffles the CNT elements in ARRAY, each of which is + SIZE bytes in size. */ +static void +random_shuffle (void *array_, size_t cnt, size_t size) +{ + char *array = array_; + char *tmp = xmalloc (size); + size_t i; + + for (i = 0; i < cnt; i++) + { + size_t j = rand () % (cnt - i) + i; + if (i != j) + { + memcpy (tmp, array + j * size, size); + memcpy (array + j * size, array + i * size, size); + memcpy (array + i * size, tmp, size); + } + } + + free (tmp); +} + +/* Checks that SET contains the CNT strings in DATA, that its structure is + correct, and that certain operations on SET produce the expected results. */ +static void +check_string_set (struct string_set *set, const int data[], size_t cnt) +{ + size_t i; + + check (string_set_is_empty (set) == (cnt == 0)); + check (string_set_count (set) == cnt); + + for (i = 0; i < cnt; i++) + { + struct string_set_node *node; + const char *s = make_string (data[i]); + + check (string_set_contains (set, s)); + check (!string_set_insert (set, s)); + check (!string_set_insert_nocopy (set, xstrdup (s))); + + node = string_set_find_node (set, s); + check (node != NULL); + check (!strcmp (s, string_set_node_get_string (node))); + } + + check (!string_set_contains (set, "xxx")); + check (string_set_find_node (set, "") == NULL); + + if (cnt == 0) + check (string_set_first (set) == NULL); + else + { + const struct string_set_node *node; + int *data_copy; + int left; + + data_copy = xmemdup (data, cnt * sizeof *data); + left = cnt; + for (node = string_set_first (set), i = 0; i < cnt; + node = string_set_next (set, node), i++) + { + const char *s = string_set_node_get_string (node); + size_t j; + + for (j = 0; j < left; j++) + if (!strcmp (s, make_string (data_copy[j]))) + { + data_copy[j] = data_copy[--left]; + goto next; + } + check_die (); + + next: ; + } + check (node == NULL); + free (data_copy); + } +} + +/* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a set in the + order specified by INSERTIONS, then deletes them in the order specified by + DELETIONS, checking the set's contents for correctness after each + operation. */ +static void +test_insert_delete (const int insertions[], + const int deletions[], + size_t cnt) +{ + struct string_set set; + size_t i; + + string_set_init (&set); + check_string_set (&set, NULL, 0); + for (i = 0; i < cnt; i++) + { + check (string_set_insert (&set, make_string (insertions[i]))); + check_string_set (&set, insertions, i + 1); + } + for (i = 0; i < cnt; i++) + { + check (string_set_delete (&set, make_string (deletions[i]))); + check_string_set (&set, deletions + i + 1, cnt - i - 1); + } + string_set_destroy (&set); +} + +/* Inserts strings into a set in each possible order, then removes them in each + possible order, up to a specified maximum size. */ +static void +test_insert_any_remove_any (void) +{ + const int max_elems = 5; + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt++) + { + int *insertions, *deletions; + unsigned int ins_perm_cnt; + int i; + + insertions = xnmalloc (cnt, sizeof *insertions); + deletions = xnmalloc (cnt, sizeof *deletions); + for (i = 0; i < cnt; i++) + insertions[i] = i; + + for (ins_perm_cnt = 0; + ins_perm_cnt == 0 || next_permutation (insertions, cnt); + ins_perm_cnt++) + { + unsigned int del_perm_cnt; + int i; + + for (i = 0; i < cnt; i++) + deletions[i] = i; + + for (del_perm_cnt = 0; + del_perm_cnt == 0 || next_permutation (deletions, cnt); + del_perm_cnt++) + test_insert_delete (insertions, deletions, cnt); + + check (del_perm_cnt == factorial (cnt)); + } + check (ins_perm_cnt == factorial (cnt)); + + free (insertions); + free (deletions); + } +} + +/* Inserts strings into a set in each possible order, then removes them in the + same order, up to a specified maximum size. */ +static void +test_insert_any_remove_same (void) +{ + const int max_elems = 7; + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt++) + { + int *values; + unsigned int permutation_cnt; + int i; + + values = xnmalloc (cnt, sizeof *values); + for (i = 0; i < cnt; i++) + values[i] = i; + + for (permutation_cnt = 0; + permutation_cnt == 0 || next_permutation (values, cnt); + permutation_cnt++) + test_insert_delete (values, values, cnt); + check (permutation_cnt == factorial (cnt)); + + free (values); + } +} + +/* Inserts strings into a set in each possible order, then + removes them in reverse order, up to a specified maximum + size. */ +static void +test_insert_any_remove_reverse (void) +{ + const int max_elems = 7; + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt++) + { + int *insertions, *deletions; + unsigned int permutation_cnt; + int i; + + insertions = xnmalloc (cnt, sizeof *insertions); + deletions = xnmalloc (cnt, sizeof *deletions); + for (i = 0; i < cnt; i++) + insertions[i] = i; + + for (permutation_cnt = 0; + permutation_cnt == 0 || next_permutation (insertions, cnt); + permutation_cnt++) + { + memcpy (deletions, insertions, sizeof *insertions * cnt); + reverse (deletions, cnt); + + test_insert_delete (insertions, deletions, cnt); + } + check (permutation_cnt == factorial (cnt)); + + free (insertions); + free (deletions); + } +} + +/* Inserts and removes strings in a set, in random order. */ +static void +test_random_sequence (void) +{ + const int max_elems = 64; + const int max_trials = 8; + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt += 2) + { + int *insertions, *deletions; + int trial; + int i; + + insertions = xnmalloc (cnt, sizeof *insertions); + deletions = xnmalloc (cnt, sizeof *deletions); + for (i = 0; i < cnt; i++) + insertions[i] = i; + for (i = 0; i < cnt; i++) + deletions[i] = i; + + for (trial = 0; trial < max_trials; trial++) + { + random_shuffle (insertions, cnt, sizeof *insertions); + random_shuffle (deletions, cnt, sizeof *deletions); + + test_insert_delete (insertions, deletions, cnt); + } + + free (insertions); + free (deletions); + } +} + +/* Inserts strings into a set in ascending order, then delete in ascending + order. */ +static void +test_insert_ordered (void) +{ + const int max_elems = 64; + int *values; + struct string_set set; + int i; + + string_set_init (&set); + values = xnmalloc (max_elems, sizeof *values); + for (i = 0; i < max_elems; i++) + { + values[i] = i; + string_set_insert_nocopy (&set, xstrdup (make_string (i))); + check_string_set (&set, values, i + 1); + } + for (i = 0; i < max_elems; i++) + { + string_set_delete (&set, make_string (i)); + check_string_set (&set, values + i + 1, max_elems - i - 1); + } + string_set_destroy (&set); + free (values); +} + +static void +test_boolean_ops (void (*function)(struct string_set *a, struct string_set *b, + unsigned int *a_pat, unsigned int *b_pat)) +{ + enum { MAX_STRINGS = 7 }; + unsigned int a_pat, b_pat; + + for (a_pat = 0; a_pat < (1u << MAX_STRINGS); a_pat++) + for (b_pat = 0; b_pat < (1u << MAX_STRINGS); b_pat++) + { + unsigned int new_a_pat = a_pat; + unsigned int new_b_pat = b_pat; + struct string_set a, b; + int a_strings[MAX_STRINGS], b_strings[MAX_STRINGS]; + size_t i, n_a, n_b; + + string_set_init (&a); + string_set_init (&b); + for (i = 0; i < MAX_STRINGS; i++) + { + if (a_pat & (1u << i)) + string_set_insert (&a, make_string (i)); + if (b_pat & (1u << i)) + string_set_insert (&b, make_string (i)); + } + + function (&a, &b, &new_a_pat, &new_b_pat); + + n_a = n_b = 0; + for (i = 0; i < MAX_STRINGS; i++) + { + if (new_a_pat & (1u << i)) + a_strings[n_a++] = i; + if (new_b_pat & (1u << i)) + b_strings[n_b++] = i; + } + check_string_set (&a, a_strings, n_a); + check_string_set (&b, b_strings, n_b); + string_set_destroy (&a); + string_set_destroy (&b); + } +} + +static void +union_cb (struct string_set *a, struct string_set *b, + unsigned int *a_pat, unsigned int *b_pat) +{ + string_set_union (a, b); + *a_pat |= *b_pat; +} + +static void +test_union (void) +{ + test_boolean_ops (union_cb); +} + +static void +union_and_intersection_cb (struct string_set *a, struct string_set *b, + unsigned int *a_pat, unsigned int *b_pat) +{ + unsigned int orig_a_pat = *a_pat; + unsigned int orig_b_pat = *b_pat; + + string_set_union_and_intersection (a, b); + *a_pat = orig_a_pat | orig_b_pat; + *b_pat = orig_a_pat & orig_b_pat; +} + +static void +test_union_and_intersection (void) +{ + test_boolean_ops (union_and_intersection_cb); +} + +static void +intersect_cb (struct string_set *a, struct string_set *b, + unsigned int *a_pat, unsigned int *b_pat) +{ + string_set_intersect (a, b); + *a_pat &= *b_pat; +} + +static void +test_intersect (void) +{ + test_boolean_ops (intersect_cb); +} + +static void +subtract_cb (struct string_set *a, struct string_set *b, + unsigned int *a_pat, unsigned int *b_pat) +{ + string_set_subtract (a, b); + *a_pat &= ~*b_pat; +} + +static void +test_subtract (void) +{ + test_boolean_ops (subtract_cb); +} + +static void +swap_cb (struct string_set *a, struct string_set *b, + unsigned int *a_pat, unsigned int *b_pat) +{ + unsigned int tmp; + string_set_swap (a, b); + tmp = *a_pat; + *a_pat = *b_pat; + *b_pat = tmp; +} + +static void +test_swap (void) +{ + test_boolean_ops (swap_cb); +} + +static void +clear_cb (struct string_set *a, struct string_set *b UNUSED, + unsigned int *a_pat, unsigned int *b_pat UNUSED) +{ + string_set_clear (a); + *a_pat = 0; +} + +static void +test_clear (void) +{ + test_boolean_ops (clear_cb); +} + +static void +clone_cb (struct string_set *a, struct string_set *b, + unsigned int *a_pat, unsigned int *b_pat) +{ + string_set_destroy (a); + string_set_clone (a, b); + *a_pat = *b_pat; +} + +static void +test_clone (void) +{ + test_boolean_ops (clone_cb); +} + +static void +test_destroy_null (void) +{ + string_set_destroy (NULL); +} + +/* Main program. */ + +/* Runs TEST_FUNCTION and prints a message about NAME. */ +static void +run_test (void (*test_function) (void), const char *name) +{ + test_name = name; + putchar ('.'); + fflush (stdout); + test_function (); +} + +int +main (void) +{ + run_test (test_insert_any_remove_any, "insert any order, delete any order"); + run_test (test_insert_any_remove_same, + "insert any order, delete same order"); + run_test (test_insert_any_remove_reverse, + "insert any order, delete reverse order"); + run_test (test_random_sequence, "insert and delete in random sequence"); + run_test (test_insert_ordered, "insert in ascending order"); + run_test (test_union, "union"); + run_test (test_union_and_intersection, "union and intersection"); + run_test (test_intersect, "intersect"); + run_test (test_subtract, "subtract"); + run_test (test_swap, "swap"); + run_test (test_clear, "clear"); + run_test (test_clone, "clone"); + run_test (test_destroy_null, "destroying null table"); + + putchar ('\n'); + + free_strings (); + + return 0; +} -- 2.30.2