1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2009, 2010, 2012 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/cast.h"
28 #include "libpspp/hash-functions.h"
29 #include "libpspp/i18n.h"
31 #include "gl/xalloc.h"
33 static struct stringi_set_node *stringi_set_find_node__ (
34 const struct stringi_set *, const char *, unsigned int hash);
35 static struct stringi_set_node *stringi_set_find_node_len__ (
36 const struct stringi_set *, const char *, size_t length, unsigned int hash);
37 static void stringi_set_insert__ (struct stringi_set *, char *,
39 static bool stringi_set_delete__ (struct stringi_set *, const char *,
42 /* Initializes SET as a new string set that is initially empty. */
44 stringi_set_init (struct stringi_set *set)
46 hmap_init (&set->hmap);
49 /* Initializes SET as a new string set that initially contains the same strings
52 stringi_set_clone (struct stringi_set *set, const struct stringi_set *old)
54 const struct stringi_set_node *node;
57 stringi_set_init (set);
58 hmap_reserve (&set->hmap, stringi_set_count (old));
59 STRINGI_SET_FOR_EACH (s, node, old)
60 stringi_set_insert__ (set, xstrdup (s), node->hmap_node.hash);
63 /* Exchanges the contents of string sets A and B. */
65 stringi_set_swap (struct stringi_set *a, struct stringi_set *b)
67 hmap_swap (&a->hmap, &b->hmap);
70 /* Frees SET and its nodes and strings. */
72 stringi_set_destroy (struct stringi_set *set)
76 stringi_set_clear (set);
77 hmap_destroy (&set->hmap);
81 /* Returns true if SET contains S (or a similar string with different case),
84 stringi_set_contains (const struct stringi_set *set, const char *s)
86 return stringi_set_contains_len (set, s, strlen (s));
89 /* Returns true if SET contains S with the given LENGTH (or a similar string
90 with different case), false otherwise. */
92 stringi_set_contains_len (const struct stringi_set *set, const char *s,
95 return stringi_set_find_node_len (set, s, length) != NULL;
98 /* Returns the node in SET that contains S, or a null pointer if SET does not
100 struct stringi_set_node *
101 stringi_set_find_node (const struct stringi_set *set, const char *s)
103 return stringi_set_find_node_len (set, s, strlen (s));
106 /* Returns the node in SET that contains S with the given LENGTH, or a null
107 pointer if SET does not contain S. */
108 struct stringi_set_node *
109 stringi_set_find_node_len (const struct stringi_set *set, const char *s,
112 return stringi_set_find_node_len__ (set, s, length,
113 utf8_hash_case_bytes (s, length, 0));
116 /* Inserts a copy of S into SET. Returns true if successful, false if SET
117 is unchanged because it already contained S. */
119 stringi_set_insert (struct stringi_set *set, const char *s)
121 unsigned int hash = utf8_hash_case_string (s, 0);
122 if (!stringi_set_find_node__ (set, s, hash))
124 stringi_set_insert__ (set, xstrdup (s), hash);
131 /* Inserts S, which must be a malloc'd string, into SET, transferring ownership
132 of S to SET. Returns true if successful, false if SET is unchanged because
133 it already contained a copy of S. (In the latter case, S is freed.) */
135 stringi_set_insert_nocopy (struct stringi_set *set, char *s)
137 unsigned int hash = utf8_hash_case_string (s, 0);
138 if (!stringi_set_find_node__ (set, s, hash))
140 stringi_set_insert__ (set, s, hash);
150 /* Deletes S from SET. Returns true if successful, false if SET is unchanged
151 because it did not contain a copy of S. */
153 stringi_set_delete (struct stringi_set *set, const char *s)
155 return stringi_set_delete__ (set, s, utf8_hash_case_string (s, 0));
158 /* Deletes NODE from SET, and frees NODE and its string. */
160 stringi_set_delete_node (struct stringi_set *set,
161 struct stringi_set_node *node)
163 free (stringi_set_delete_nofree (set, node));
166 /* Deletes NODE from SET and frees NODE. Returns the string that NODE
167 contained, transferring ownership to the caller. */
169 stringi_set_delete_nofree (struct stringi_set *set,
170 struct stringi_set_node *node)
172 char *string = node->string;
173 hmap_delete (&set->hmap, &node->hmap_node);
178 /* Removes all nodes from SET. */
180 stringi_set_clear (struct stringi_set *set)
182 struct stringi_set_node *node, *next;
184 HMAP_FOR_EACH_SAFE (node, next, struct stringi_set_node, hmap_node,
186 stringi_set_delete_node (set, node);
189 /* Calculates A = union(A, B).
191 If B may be modified, stringi_set_union_and_intersection() is
192 faster than this function. */
194 stringi_set_union (struct stringi_set *a, const struct stringi_set *b)
196 struct stringi_set_node *node;
197 HMAP_FOR_EACH (node, struct stringi_set_node, hmap_node, &b->hmap)
198 if (!stringi_set_find_node__ (a, node->string, node->hmap_node.hash))
199 stringi_set_insert__ (a, xstrdup (node->string), node->hmap_node.hash);
202 /* Calculates A = union(A, B) and B = intersect(A, B).
204 If only the intersection is needed, stringi_set_intersect() is
207 stringi_set_union_and_intersection (struct stringi_set *a,
208 struct stringi_set *b)
210 struct stringi_set_node *node, *next;
212 HMAP_FOR_EACH_SAFE (node, next, struct stringi_set_node, hmap_node,
214 if (!stringi_set_find_node__ (a, node->string, node->hmap_node.hash))
216 hmap_delete (&b->hmap, &node->hmap_node);
217 hmap_insert (&a->hmap, &node->hmap_node, node->hmap_node.hash);
221 /* Calculates A = intersect(A, B). */
223 stringi_set_intersect (struct stringi_set *a, const struct stringi_set *b)
225 struct stringi_set_node *node, *next;
227 HMAP_FOR_EACH_SAFE (node, next, struct stringi_set_node, hmap_node,
229 if (!stringi_set_find_node__ (b, node->string, node->hmap_node.hash))
230 stringi_set_delete_node (a, node);
233 /* Removes from A all of the strings in B. */
235 stringi_set_subtract (struct stringi_set *a, const struct stringi_set *b)
237 struct stringi_set_node *node, *next;
239 if (stringi_set_count (a) < stringi_set_count (b))
241 HMAP_FOR_EACH_SAFE (node, next, struct stringi_set_node, hmap_node,
243 if (stringi_set_find_node__ (b, node->string, node->hmap_node.hash))
244 stringi_set_delete_node (a, node);
248 HMAP_FOR_EACH (node, struct stringi_set_node, hmap_node, &b->hmap)
249 stringi_set_delete__ (a, node->string, node->hmap_node.hash);
253 /* Allocates and returns an array that points to each of the strings in SET.
254 The caller must not free or modify any of the strings. Removing a string
255 from SET invalidates the corresponding element of the returned array. The
256 caller it is responsible for freeing the returned array itself (with
259 The returned array is in the same order as observed by stringi_set_first()
260 and stringi_set_next(), that is, no particular order. */
262 stringi_set_get_array (const struct stringi_set *set)
264 const struct stringi_set_node *node;
269 array = xnmalloc (stringi_set_count (set), sizeof *array);
272 STRINGI_SET_FOR_EACH (s, node, set)
273 array[i++] = CONST_CAST (char *, s);
279 compare_strings (const void *a_, const void *b_)
281 const char *const *a = a_;
282 const char *const *b = b_;
283 return utf8_strcasecmp (*a, *b);
286 /* Allocates and returns an array that points to each of the strings in SET.
287 The caller must not free or modify any of the strings. Removing a string
288 from SET invalidates the corresponding element of the returned array. The
289 caller it is responsible for freeing the returned array itself (with
292 The returned array is ordered according to utf8_strcasecmp(). */
294 stringi_set_get_sorted_array (const struct stringi_set *set)
296 char **array = stringi_set_get_array (set);
297 qsort (array, stringi_set_count (set), sizeof *array, compare_strings);
301 /* Internal functions. */
303 static struct stringi_set_node *
304 stringi_set_find_node__ (const struct stringi_set *set, const char *s,
307 return stringi_set_find_node_len__ (set, s, strlen (s), hash);
310 static struct stringi_set_node *
311 stringi_set_find_node_len__ (const struct stringi_set *set, const char *s,
312 size_t length, unsigned int hash)
314 struct stringi_set_node *node;
316 HMAP_FOR_EACH_WITH_HASH (node, struct stringi_set_node, hmap_node,
318 if (!utf8_strncasecmp (s, length, node->string, strlen (node->string)))
325 stringi_set_insert__ (struct stringi_set *set, char *s, unsigned int hash)
327 struct stringi_set_node *node = xmalloc (sizeof *node);
329 hmap_insert (&set->hmap, &node->hmap_node, hash);
333 stringi_set_delete__ (struct stringi_set *set, const char *s,
336 struct stringi_set_node *node = stringi_set_find_node__ (set, s, hash);
339 stringi_set_delete_node (set, node);