1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2009, 2010, 2012 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 #include <config.h>
18
19 #include "libpspp/stringi-map.h"
20
21 #include <stdlib.h>
22 #include <string.h>
23
24 #include "libpspp/hash-functions.h"
25 #include "libpspp/i18n.h"
26 #include "libpspp/string-set.h"
27 #include "libpspp/stringi-set.h"
28
29 #include "gl/xalloc.h"
30
31 static struct stringi_map_node *stringi_map_find_node__ (
32 const struct stringi_map *, const char *key, unsigned int hash);
33 static bool stringi_map_delete__ (struct stringi_map *, const char *key,
34 unsigned int hash);
35 static struct stringi_map_node *stringi_map_insert__ (struct stringi_map *,
36 char *key, char *value,
37 unsigned int hash);
38
39 /* Sets NODE's value to a copy of NEW_VALUE and returns the node's previous
40 value. The caller is responsible for freeing the returned string (with
41 free()). */
42 char *
stringi_map_node_swap_value(struct stringi_map_node * node,const char * new_value)43 stringi_map_node_swap_value (struct stringi_map_node *node,
44 const char *new_value)
45 {
46 return stringi_map_node_swap_value_nocopy (node, xstrdup (new_value));
47 }
48
49 /* Sets NODE's value to NEW_VALUE, which must be a malloc()'d string,
50 transferring ownership of NEW_VALUE to the node. Returns the node's
51 previous value, which the caller is responsible for freeing (with
52 free()). */
53 char *
stringi_map_node_swap_value_nocopy(struct stringi_map_node * node,char * new_value)54 stringi_map_node_swap_value_nocopy (struct stringi_map_node *node,
55 char *new_value)
56 {
57 char *old_value = node->value;
58 node->value = new_value;
59 return old_value;
60 }
61
62 /* Replaces NODE's value by a copy of VALUE. */
63 void
stringi_map_node_set_value(struct stringi_map_node * node,const char * value)64 stringi_map_node_set_value (struct stringi_map_node *node, const char *value)
65 {
66 stringi_map_node_set_value_nocopy (node, xstrdup (value));
67 }
68
69 /* Replaces NODE's value by VALUE, which must be a malloc()'d string,
70 transferring ownership of VALUE to the node.. */
71 void
stringi_map_node_set_value_nocopy(struct stringi_map_node * node,char * value)72 stringi_map_node_set_value_nocopy (struct stringi_map_node *node, char *value)
73 {
74 free (node->value);
75 node->value = value;
76 }
77
78 /* Frees NODE and and its key and value. Ordinarily nodes are owned by
79 stringi_maps, but this function should only be used by a caller that owns
80 NODE, such as one that has called stringi_map_delete_nofree() for the
81 node. */
82 void
stringi_map_node_destroy(struct stringi_map_node * node)83 stringi_map_node_destroy (struct stringi_map_node *node)
84 {
85 free (node->key);
86 free (node->value);
87 free (node);
88 }
89
90 /* Initializes MAP as an initially empty case-insensitive string map. */
91 void
stringi_map_init(struct stringi_map * map)92 stringi_map_init (struct stringi_map *map)
93 {
94 hmap_init (&map->hmap);
95 }
96
97 /* Initializes MAP as a new string map that initially contains the same pairs
98 as OLD. */
99 void
stringi_map_clone(struct stringi_map * map,const struct stringi_map * old)100 stringi_map_clone (struct stringi_map *map, const struct stringi_map *old)
101 {
102 const struct stringi_map_node *node;
103 const char *key, *value;
104
105 stringi_map_init (map);
106 hmap_reserve (&map->hmap, stringi_map_count (old));
107 STRINGI_MAP_FOR_EACH_KEY_VALUE (key, value, node, old)
108 stringi_map_insert__ (map, xstrdup (key), xstrdup (value),
109 node->hmap_node.hash);
110 }
111
112 /* Exchanges the contents of string maps A and B. */
113 void
stringi_map_swap(struct stringi_map * a,struct stringi_map * b)114 stringi_map_swap (struct stringi_map *a, struct stringi_map *b)
115 {
116 hmap_swap (&a->hmap, &b->hmap);
117 }
118
119 /* Frees MAP and its nodes and key-value pairs. */
120 void
stringi_map_destroy(struct stringi_map * map)121 stringi_map_destroy (struct stringi_map *map)
122 {
123 if (map != NULL)
124 {
125 stringi_map_clear (map);
126 hmap_destroy (&map->hmap);
127 }
128 }
129
130 /* Returns true if MAP contains KEY (or an equivalent with different case) as a
131 key, otherwise false. */
132 bool
stringi_map_contains(const struct stringi_map * map,const char * key)133 stringi_map_contains (const struct stringi_map *map, const char *key)
134 {
135 return stringi_map_find_node (map, key) != NULL;
136 }
137
138 /* If MAP contains KEY (or an equivalent with different case) as a key, returns
139 the corresponding value. Otherwise, returns a null pointer. */
140 const char *
stringi_map_find(const struct stringi_map * map,const char * key)141 stringi_map_find (const struct stringi_map *map, const char *key)
142 {
143 const struct stringi_map_node *node = stringi_map_find_node (map, key);
144 return node != NULL ? node->value : NULL;
145 }
146
147 /* If MAP contains KEY (or an equivalent with different case) as a key, returns
148 the corresponding node. Otherwise, returns a null pointer. */
149 struct stringi_map_node *
stringi_map_find_node(const struct stringi_map * map,const char * key)150 stringi_map_find_node (const struct stringi_map *map, const char *key)
151 {
152 return stringi_map_find_node__ (map, key, utf8_hash_case_string (key, 0));
153 }
154
155 /* If MAP contains KEY (or an equivalent with different case) as a key, deletes
156 that key's node and returns its value, which the caller is responsible for
157 freeing (using free()). Otherwise, returns a null pointer. */
158 char *
stringi_map_find_and_delete(struct stringi_map * map,const char * key)159 stringi_map_find_and_delete (struct stringi_map *map, const char *key)
160 {
161 struct stringi_map_node *node = stringi_map_find_node (map, key);
162 char *value = NULL;
163 if (node != NULL)
164 {
165 value = node->value;
166 node->value = NULL;
167 stringi_map_delete_node (map, node);
168 }
169 return value;
170 }
171
172 /* If MAP does not contain KEY (or an equivalent with different case) as a key,
173 inserts a new node containing copies of KEY and VALUE and returns the new
174 node. Otherwise, returns the existing node that contains KEY. */
175 struct stringi_map_node *
stringi_map_insert(struct stringi_map * map,const char * key,const char * value)176 stringi_map_insert (struct stringi_map *map, const char *key,
177 const char *value)
178 {
179 unsigned int hash = utf8_hash_case_string (key, 0);
180 struct stringi_map_node *node = stringi_map_find_node__ (map, key, hash);
181 if (node == NULL)
182 node = stringi_map_insert__ (map, xstrdup (key), xstrdup (value), hash);
183 return node;
184 }
185
186 /* If MAP does not contain KEY (or an equivalent with different case) as a key,
187 inserts a new node containing KEY and VALUE and returns the new node.
188 Otherwise, returns the existing node that contains KEY. Either way,
189 ownership of KEY and VALUE is transferred to MAP. */
190 struct stringi_map_node *
stringi_map_insert_nocopy(struct stringi_map * map,char * key,char * value)191 stringi_map_insert_nocopy (struct stringi_map *map, char *key, char *value)
192 {
193 unsigned int hash = utf8_hash_case_string (key, 0);
194 struct stringi_map_node *node = stringi_map_find_node__ (map, key, hash);
195 if (node == NULL)
196 node = stringi_map_insert__ (map, key, value, hash);
197 else
198 {
199 free (key);
200 free (value);
201 }
202 return node;
203 }
204
205 /* If MAP does not contain KEY (or an equivalent with different case) as a key,
206 inserts a new node containing copies of KEY and VALUE. Otherwise, replaces
207 the existing node's value by a copy of VALUE. Returns the node. */
208 struct stringi_map_node *
stringi_map_replace(struct stringi_map * map,const char * key,const char * value)209 stringi_map_replace (struct stringi_map *map, const char *key,
210 const char *value)
211 {
212 unsigned int hash = utf8_hash_case_string (key, 0);
213 struct stringi_map_node *node = stringi_map_find_node__ (map, key, hash);
214 if (node == NULL)
215 node = stringi_map_insert__ (map, xstrdup (key), xstrdup (value), hash);
216 else
217 stringi_map_node_set_value (node, value);
218 return node;
219 }
220
221 /* If MAP does not contain KEY (or an equivalent with different case) as a key,
222 inserts a new node containing KEY and VALUE. Otherwise, replaces the
223 existing node's value by VALUE. Either way, ownership of KEY and VALUE is
224 transferred to MAP. Returns the node. */
225 struct stringi_map_node *
stringi_map_replace_nocopy(struct stringi_map * map,char * key,char * value)226 stringi_map_replace_nocopy (struct stringi_map *map, char *key, char *value)
227 {
228 unsigned int hash = utf8_hash_case_string (key, 0);
229 struct stringi_map_node *node = stringi_map_find_node__ (map, key, hash);
230 if (node == NULL)
231 node = stringi_map_insert__ (map, key, value, hash);
232 else
233 {
234 free (key);
235 stringi_map_node_set_value_nocopy (node, value);
236 }
237 return node;
238 }
239
240 /* Searches MAP for a node with KEY (or an equivalent with different case) as
241 its key. If found, deletes the node and its key and value and returns true.
242 Otherwise, returns false without modifying MAP. */
243 bool
stringi_map_delete(struct stringi_map * map,const char * key)244 stringi_map_delete (struct stringi_map *map, const char *key)
245 {
246 return stringi_map_delete__ (map, key, utf8_hash_case_string (key, 0));
247 }
248
249 /* Deletes NODE from MAP and destroys the node and its key and value. */
250 void
stringi_map_delete_node(struct stringi_map * map,struct stringi_map_node * node)251 stringi_map_delete_node (struct stringi_map *map,
252 struct stringi_map_node *node)
253 {
254 stringi_map_delete_nofree (map, node);
255 stringi_map_node_destroy (node);
256 }
257
258 /* Deletes NODE from MAP. Transfers ownership of NODE to the caller, which
259 becomes responsible for destroying it. */
260 void
stringi_map_delete_nofree(struct stringi_map * map,struct stringi_map_node * node)261 stringi_map_delete_nofree (struct stringi_map *map,
262 struct stringi_map_node *node)
263 {
264 hmap_delete (&map->hmap, &node->hmap_node);
265 }
266
267 /* Removes all nodes from MAP and frees them and their keys and values. */
268 void
stringi_map_clear(struct stringi_map * map)269 stringi_map_clear (struct stringi_map *map)
270 {
271 struct stringi_map_node *node, *next;
272
273 STRINGI_MAP_FOR_EACH_NODE_SAFE (node, next, map)
274 stringi_map_delete_node (map, node);
275 }
276
277 /* Inserts a copy of each of the nodes in SRC into DST. When SRC and DST both
278 have a particular key (or keys that differ only in case), the value in DST's
279 node is left unchanged. */
280 void
stringi_map_insert_map(struct stringi_map * dst,const struct stringi_map * src)281 stringi_map_insert_map (struct stringi_map *dst, const struct stringi_map *src)
282 {
283 const struct stringi_map_node *node;
284
285 STRINGI_MAP_FOR_EACH_NODE (node, src)
286 {
287 if (!stringi_map_find_node__ (dst, node->key, node->hmap_node.hash))
288 stringi_map_insert__ (dst, xstrdup (node->key), xstrdup (node->value),
289 node->hmap_node.hash);
290 }
291 }
292
293 /* Inserts a copy of each of the nodes in SRC into DST. When SRC and DST both
294 have a particular key (or keys that differ only in case), the value in DST's
295 node is replaced by a copy of the value in SRC's node. */
296 void
stringi_map_replace_map(struct stringi_map * dst,const struct stringi_map * src)297 stringi_map_replace_map (struct stringi_map *dst,
298 const struct stringi_map *src)
299 {
300 const struct stringi_map_node *snode;
301
302 STRINGI_MAP_FOR_EACH_NODE (snode, src)
303 {
304 struct stringi_map_node *dnode;
305 dnode = stringi_map_find_node__ (dst, snode->key, snode->hmap_node.hash);
306 if (dnode != NULL)
307 stringi_map_node_set_value (dnode, snode->value);
308 else
309 stringi_map_insert__ (dst,
310 xstrdup (snode->key), xstrdup (snode->value),
311 snode->hmap_node.hash);
312 }
313 }
314
315 /* Inserts each of the keys in MAP into KEYS. KEYS must already have been
316 initialized (using stringi_set_init()). */
317 void
stringi_map_get_keys(const struct stringi_map * map,struct stringi_set * keys)318 stringi_map_get_keys (const struct stringi_map *map, struct stringi_set *keys)
319 {
320 const struct stringi_map_node *node;
321 const char *key;
322
323 STRINGI_MAP_FOR_EACH_KEY (key, node, map)
324 stringi_set_insert (keys, key);
325 }
326
327 /* Inserts each of the values in MAP into VALUES. VALUES must already have
328 been initialized (using string_set_init()). */
329 void
stringi_map_get_values(const struct stringi_map * map,struct string_set * values)330 stringi_map_get_values (const struct stringi_map *map,
331 struct string_set *values)
332 {
333 const struct stringi_map_node *node;
334 const char *value;
335
336 STRINGI_MAP_FOR_EACH_VALUE (value, node, map)
337 string_set_insert (values, value);
338 }
339
340 static struct stringi_map_node *
stringi_map_find_node__(const struct stringi_map * map,const char * key,unsigned int hash)341 stringi_map_find_node__ (const struct stringi_map *map, const char *key,
342 unsigned int hash)
343 {
344 struct stringi_map_node *node;
345
346 HMAP_FOR_EACH_WITH_HASH (node, struct stringi_map_node, hmap_node,
347 hash, &map->hmap)
348 if (!utf8_strcasecmp (key, node->key))
349 return node;
350
351 return NULL;
352 }
353
354 static bool
stringi_map_delete__(struct stringi_map * map,const char * key,unsigned int hash)355 stringi_map_delete__ (struct stringi_map *map, const char *key,
356 unsigned int hash)
357 {
358 struct stringi_map_node *node = stringi_map_find_node__ (map, key, hash);
359 if (node != NULL)
360 {
361 stringi_map_delete_node (map, node);
362 return true;
363 }
364 else
365 return false;
366 }
367
368 static struct stringi_map_node *
stringi_map_insert__(struct stringi_map * map,char * key,char * value,unsigned int hash)369 stringi_map_insert__ (struct stringi_map *map, char *key, char *value,
370 unsigned int hash)
371 {
372 struct stringi_map_node *node = xmalloc (sizeof *node);
373 node->key = key;
374 node->value = value;
375 hmap_insert (&map->hmap, &node->hmap_node, hash);
376 return node;
377 }
378
379