1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2009, 2010 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
17 /* If you add routines in this file, please add a corresponding test to
18 stringi-set-test.c. */
22 #include <libpspp/stringi-set.h>
27 #include <libpspp/hash-functions.h>
29 #include "gl/xalloc.h"
31 static struct stringi_set_node *stringi_set_find_node__ (
32 const struct stringi_set *, const char *, unsigned int hash);
33 static void stringi_set_insert__ (struct stringi_set *, char *,
35 static bool stringi_set_delete__ (struct stringi_set *, const char *,
38 /* Initializes SET as a new string set that is initially empty. */
40 stringi_set_init (struct stringi_set *set)
42 hmap_init (&set->hmap);
45 /* Initializes SET as a new string set that initially contains the same strings
48 stringi_set_clone (struct stringi_set *set, const struct stringi_set *old)
50 const struct stringi_set_node *node;
53 stringi_set_init (set);
54 hmap_reserve (&set->hmap, stringi_set_count (old));
55 STRINGI_SET_FOR_EACH (s, node, old)
56 stringi_set_insert__ (set, xstrdup (s), node->hmap_node.hash);
59 /* Exchanges the contents of string sets A and B. */
61 stringi_set_swap (struct stringi_set *a, struct stringi_set *b)
63 hmap_swap (&a->hmap, &b->hmap);
66 /* Frees SET and its nodes and strings. */
68 stringi_set_destroy (struct stringi_set *set)
72 stringi_set_clear (set);
73 hmap_destroy (&set->hmap);
77 /* Returns true if SET contains S (or a similar string with different case),
80 stringi_set_contains (const struct stringi_set *set, const char *s)
82 return stringi_set_find_node (set, s) != NULL;
85 /* Returns the node in SET that contains S, or a null pointer if SET does not
87 struct stringi_set_node *
88 stringi_set_find_node (const struct stringi_set *set, const char *s)
90 return stringi_set_find_node__ (set, s, hash_case_string (s, 0));
93 /* Inserts a copy of S into SET. Returns true if successful, false if SET
94 is unchanged because it already contained S. */
96 stringi_set_insert (struct stringi_set *set, const char *s)
98 unsigned int hash = hash_case_string (s, 0);
99 if (!stringi_set_find_node__ (set, s, hash))
101 stringi_set_insert__ (set, xstrdup (s), hash);
108 /* Inserts S, which must be a malloc'd string, into SET, transferring ownership
109 of S to SET. Returns true if successful, false if SET is unchanged because
110 it already contained a copy of S. (In the latter case, S is freed.) */
112 stringi_set_insert_nocopy (struct stringi_set *set, char *s)
114 unsigned int hash = hash_case_string (s, 0);
115 if (!stringi_set_find_node__ (set, s, hash))
117 stringi_set_insert__ (set, s, hash);
127 /* Deletes S from SET. Returns true if successful, false if SET is unchanged
128 because it did not contain a copy of S. */
130 stringi_set_delete (struct stringi_set *set, const char *s)
132 return stringi_set_delete__ (set, s, hash_case_string (s, 0));
135 /* Deletes NODE from SET, and frees NODE and its string. */
137 stringi_set_delete_node (struct stringi_set *set,
138 struct stringi_set_node *node)
140 free (stringi_set_delete_nofree (set, node));
143 /* Deletes NODE from SET and frees NODE. Returns the string that NODE
144 contained, transferring ownership to the caller. */
146 stringi_set_delete_nofree (struct stringi_set *set,
147 struct stringi_set_node *node)
149 char *string = node->string;
150 hmap_delete (&set->hmap, &node->hmap_node);
155 /* Removes all nodes from SET. */
157 stringi_set_clear (struct stringi_set *set)
159 struct stringi_set_node *node, *next;
161 HMAP_FOR_EACH_SAFE (node, next, struct stringi_set_node, hmap_node,
163 stringi_set_delete_node (set, node);
166 /* Calculates A = union(A, B).
168 If B may be modified, stringi_set_union_and_intersection() is
169 faster than this function. */
171 stringi_set_union (struct stringi_set *a, const struct stringi_set *b)
173 struct stringi_set_node *node;
174 HMAP_FOR_EACH (node, struct stringi_set_node, hmap_node, &b->hmap)
175 if (!stringi_set_find_node__ (a, node->string, node->hmap_node.hash))
176 stringi_set_insert__ (a, xstrdup (node->string), node->hmap_node.hash);
179 /* Calculates A = union(A, B) and B = intersect(A, B).
181 If only the intersection is needed, stringi_set_intersect() is
184 stringi_set_union_and_intersection (struct stringi_set *a,
185 struct stringi_set *b)
187 struct stringi_set_node *node, *next;
189 HMAP_FOR_EACH_SAFE (node, next, struct stringi_set_node, hmap_node,
191 if (!stringi_set_find_node__ (a, node->string, node->hmap_node.hash))
193 hmap_delete (&b->hmap, &node->hmap_node);
194 hmap_insert (&a->hmap, &node->hmap_node, node->hmap_node.hash);
198 /* Calculates A = intersect(A, B). */
200 stringi_set_intersect (struct stringi_set *a, const struct stringi_set *b)
202 struct stringi_set_node *node, *next;
204 HMAP_FOR_EACH_SAFE (node, next, struct stringi_set_node, hmap_node,
206 if (!stringi_set_find_node__ (b, node->string, node->hmap_node.hash))
207 stringi_set_delete_node (a, node);
210 /* Removes from A all of the strings in B. */
212 stringi_set_subtract (struct stringi_set *a, const struct stringi_set *b)
214 struct stringi_set_node *node, *next;
216 if (stringi_set_count (a) < stringi_set_count (b))
218 HMAP_FOR_EACH_SAFE (node, next, struct stringi_set_node, hmap_node,
220 if (stringi_set_find_node__ (b, node->string, node->hmap_node.hash))
221 stringi_set_delete_node (a, node);
225 HMAP_FOR_EACH (node, struct stringi_set_node, hmap_node, &b->hmap)
226 stringi_set_delete__ (a, node->string, node->hmap_node.hash);
230 /* Internal functions. */
232 static struct stringi_set_node *
233 stringi_set_find_node__ (const struct stringi_set *set, const char *s,
236 struct stringi_set_node *node;
238 HMAP_FOR_EACH_WITH_HASH (node, struct stringi_set_node, hmap_node,
240 if (!strcasecmp (s, node->string))
247 stringi_set_insert__ (struct stringi_set *set, char *s, unsigned int hash)
249 struct stringi_set_node *node = xmalloc (sizeof *node);
251 hmap_insert (&set->hmap, &node->hmap_node, hash);
255 stringi_set_delete__ (struct stringi_set *set, const char *s,
258 struct stringi_set_node *node = stringi_set_find_node__ (set, s, hash);
261 stringi_set_delete_node (set, node);