scale variables work more sanely
[pspp] / src / libpspp / string-set.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2009, 2011 Free Software Foundation, Inc.
3
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.
8
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.
13
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/>. */
16
17 /* If you add routines in this file, please add a corresponding test to
18    string-set-test.c. */
19
20 #include <config.h>
21
22 #include "libpspp/string-set.h"
23
24 #include <stdlib.h>
25 #include <string.h>
26
27 #include "libpspp/hash-functions.h"
28
29 #include "gl/xalloc.h"
30
31 static struct string_set_node *string_set_find_node__ (
32   const struct string_set *, const char *, unsigned int hash);
33 static void string_set_insert__ (struct string_set *, char *,
34                                  unsigned int hash);
35 static bool string_set_delete__ (struct string_set *, const char *,
36                                  unsigned int hash);
37
38 /* Initializes SET as a new string set that is initially empty. */
39 void
40 string_set_init (struct string_set *set)
41 {
42   hmap_init (&set->hmap);
43 }
44
45 /* Initializes SET as a new string set that initially contains the same strings
46    as OLD. */
47 void
48 string_set_clone (struct string_set *set, const struct string_set *old)
49 {
50   const struct string_set_node *node;
51   const char *s;
52
53   string_set_init (set);
54   hmap_reserve (&set->hmap, string_set_count (old));
55   STRING_SET_FOR_EACH (s, node, old)
56     string_set_insert__ (set, xstrdup (s), node->hmap_node.hash);
57 }
58
59 /* Exchanges the contents of string sets A and B. */
60 void
61 string_set_swap (struct string_set *a, struct string_set *b)
62 {
63   hmap_swap (&a->hmap, &b->hmap);
64 }
65
66 /* Frees SET and its nodes and strings. */
67 void
68 string_set_destroy (struct string_set *set)
69 {
70   if (set != NULL)
71     {
72       string_set_clear (set);
73       hmap_destroy (&set->hmap);
74     }
75 }
76
77 /* Returns true if SET contains S, false otherwise. */
78 bool
79 string_set_contains (const struct string_set *set, const char *s)
80 {
81   return string_set_find_node (set, s) != NULL;
82 }
83
84 /* Returns the node in SET that contains S, or a null pointer if SET does not
85    contain S. */
86 struct string_set_node *
87 string_set_find_node (const struct string_set *set, const char *s)
88 {
89   return string_set_find_node__ (set, s, hash_string (s, 0));
90 }
91
92 /* Inserts a copy of S into SET.  Returns true if successful, false if SET
93    is unchanged because it already contained S. */
94 bool
95 string_set_insert (struct string_set *set, const char *s)
96 {
97   unsigned int hash = hash_string (s, 0);
98   if (!string_set_find_node__ (set, s, hash))
99     {
100       string_set_insert__ (set, xstrdup (s), hash);
101       return true;
102     }
103   else
104     return false;
105 }
106
107 /* Inserts S, which must be a malloc'd string, into SET, transferring ownership
108    of S to SET.  Returns true if successful, false if SET is unchanged because
109    it already contained a copy of S.  (In the latter case, S is freed.) */
110 bool
111 string_set_insert_nocopy (struct string_set *set, char *s)
112 {
113   unsigned int hash = hash_string (s, 0);
114   if (!string_set_find_node__ (set, s, hash))
115     {
116       string_set_insert__ (set, s, hash);
117       return true;
118     }
119   else
120     {
121       free (s);
122       return false;
123     }
124 }
125
126 /* Deletes S from SET.  Returns true if successful, false if SET is unchanged
127    because it did not contain a copy of S. */
128 bool
129 string_set_delete (struct string_set *set, const char *s)
130 {
131   return string_set_delete__ (set, s, hash_string (s, 0));
132 }
133
134 /* Deletes NODE from SET, and frees NODE and its string. */
135 void
136 string_set_delete_node (struct string_set *set, struct string_set_node *node)
137 {
138   free (string_set_delete_nofree (set, node));
139 }
140
141 /* Deletes NODE from SET and frees NODE.  Returns the string that NODE
142    contained, transferring ownership to the caller. */
143 char *
144 string_set_delete_nofree (struct string_set *set, struct string_set_node *node)
145 {
146   char *string = node->string;
147   hmap_delete (&set->hmap, &node->hmap_node);
148   free (node);
149   return string;
150 }
151
152 /* Removes all nodes from SET. */
153 void
154 string_set_clear (struct string_set *set)
155 {
156   struct string_set_node *node, *next;
157
158   HMAP_FOR_EACH_SAFE (node, next, struct string_set_node, hmap_node,
159                       &set->hmap)
160     string_set_delete_node (set, node);
161 }
162
163 /* Calculates A = union(A, B).
164
165    If B may be modified, string_set_union_and_intersection() is
166    faster than this function. */
167 void
168 string_set_union (struct string_set *a, const struct string_set *b)
169 {
170   struct string_set_node *node;
171   HMAP_FOR_EACH (node, struct string_set_node, hmap_node, &b->hmap)
172     if (!string_set_find_node__ (a, node->string, node->hmap_node.hash))
173       string_set_insert__ (a, xstrdup (node->string), node->hmap_node.hash);
174 }
175
176 /* Calculates A = union(A, B) and B = intersect(A, B).
177
178    If only the intersection is needed, string_set_intersect() is
179    faster. */
180 void
181 string_set_union_and_intersection (struct string_set *a, struct string_set *b)
182 {
183   struct string_set_node *node, *next;
184
185   HMAP_FOR_EACH_SAFE (node, next, struct string_set_node, hmap_node,
186                       &b->hmap)
187     if (!string_set_find_node__ (a, node->string, node->hmap_node.hash))
188       {
189         hmap_delete (&b->hmap, &node->hmap_node);
190         hmap_insert (&a->hmap, &node->hmap_node, node->hmap_node.hash);
191       }
192 }
193
194 /* Calculates A = intersect(A, B). */
195 void
196 string_set_intersect (struct string_set *a, const struct string_set *b)
197 {
198   struct string_set_node *node, *next;
199
200   HMAP_FOR_EACH_SAFE (node, next, struct string_set_node, hmap_node,
201                       &a->hmap)
202     if (!string_set_find_node__ (b, node->string, node->hmap_node.hash))
203       string_set_delete_node (a, node);
204 }
205
206 /* Removes from A all of the strings in B. */
207 void
208 string_set_subtract (struct string_set *a, const struct string_set *b)
209 {
210   struct string_set_node *node, *next;
211
212   if (string_set_count (a) < string_set_count (b))
213     {
214       HMAP_FOR_EACH_SAFE (node, next, struct string_set_node, hmap_node,
215                           &a->hmap)
216         if (string_set_find_node__ (b, node->string, node->hmap_node.hash))
217           string_set_delete_node (a, node);
218     }
219   else
220     {
221       HMAP_FOR_EACH (node, struct string_set_node, hmap_node, &b->hmap)
222         string_set_delete__ (a, node->string, node->hmap_node.hash);
223     }
224 }
225 \f
226 /* Internal functions. */
227
228 static struct string_set_node *
229 string_set_find_node__ (const struct string_set *set, const char *s,
230                         unsigned int hash)
231 {
232   struct string_set_node *node;
233
234   HMAP_FOR_EACH_WITH_HASH (node, struct string_set_node, hmap_node,
235                            hash, &set->hmap)
236     if (!strcmp (s, node->string))
237       return node;
238
239   return NULL;
240 }
241
242 static void
243 string_set_insert__ (struct string_set *set, char *s, unsigned int hash)
244 {
245   struct string_set_node *node = xmalloc (sizeof *node);
246   node->string = s;
247   hmap_insert (&set->hmap, &node->hmap_node, hash);
248 }
249
250 static bool
251 string_set_delete__ (struct string_set *set, const char *s, unsigned int hash)
252 {
253   struct string_set_node *node = string_set_find_node__ (set, s, hash);
254   if (node != NULL)
255     {
256       string_set_delete_node (set, node);
257       return true;
258     }
259   else
260     return false;
261 }