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/>. */
19 #include "libpspp/stringi-map.h"
24 #include "libpspp/hash-functions.h"
25 #include "libpspp/i18n.h"
26 #include "libpspp/string-set.h"
27 #include "libpspp/stringi-set.h"
29 #include "gl/xalloc.h"
30 #include "gl/xmemdup0.h"
32 static struct stringi_map_node *stringi_map_find_node__ (
33 const struct stringi_map *, const char *key, size_t key_len,
35 static bool stringi_map_delete__ (struct stringi_map *, const char *key,
36 size_t key_len, unsigned int hash);
37 static struct stringi_map_node *stringi_map_insert__ (struct stringi_map *,
38 char *key, char *value,
41 /* Sets NODE's value to a copy of NEW_VALUE and returns the node's previous
42 value. The caller is responsible for freeing the returned string (with
45 stringi_map_node_swap_value (struct stringi_map_node *node,
46 const char *new_value)
48 return stringi_map_node_swap_value_nocopy (node, xstrdup (new_value));
51 /* Sets NODE's value to NEW_VALUE, which must be a malloc()'d string,
52 transferring ownership of NEW_VALUE to the node. Returns the node's
53 previous value, which the caller is responsible for freeing (with
56 stringi_map_node_swap_value_nocopy (struct stringi_map_node *node,
59 char *old_value = node->value;
60 node->value = new_value;
64 /* Replaces NODE's value by a copy of VALUE. */
66 stringi_map_node_set_value (struct stringi_map_node *node, const char *value)
68 stringi_map_node_set_value_nocopy (node, xstrdup (value));
71 /* Replaces NODE's value by VALUE, which must be a malloc()'d string,
72 transferring ownership of VALUE to the node.. */
74 stringi_map_node_set_value_nocopy (struct stringi_map_node *node, char *value)
80 /* Frees NODE and its key and value. Ordinarily nodes are owned by
81 stringi_maps, but this function should only be used by a caller that owns
82 NODE, such as one that has called stringi_map_delete_nofree() for the
85 stringi_map_node_destroy (struct stringi_map_node *node)
92 /* Initializes MAP as an initially empty case-insensitive string map. */
94 stringi_map_init (struct stringi_map *map)
96 hmap_init (&map->hmap);
99 /* Initializes MAP as a new string map that initially contains the same pairs
102 stringi_map_clone (struct stringi_map *map, const struct stringi_map *old)
104 const struct stringi_map_node *node;
105 const char *key, *value;
107 stringi_map_init (map);
108 hmap_reserve (&map->hmap, stringi_map_count (old));
109 STRINGI_MAP_FOR_EACH_KEY_VALUE (key, value, node, old)
110 stringi_map_insert__ (map, xstrdup (key), xstrdup (value),
111 node->hmap_node.hash);
114 /* Exchanges the contents of string maps A and B. */
116 stringi_map_swap (struct stringi_map *a, struct stringi_map *b)
118 hmap_swap (&a->hmap, &b->hmap);
121 /* Frees MAP and its nodes and key-value pairs. */
123 stringi_map_destroy (struct stringi_map *map)
127 stringi_map_clear (map);
128 hmap_destroy (&map->hmap);
132 /* Returns true if MAP contains KEY (or an equivalent with different case) as a
133 key, otherwise false. */
135 stringi_map_contains (const struct stringi_map *map, const char *key)
137 return stringi_map_find_node (map, key, strlen (key)) != NULL;
140 /* If MAP contains KEY (or an equivalent with different case) as a key, returns
141 the corresponding value. Otherwise, returns a null pointer. */
143 stringi_map_find (const struct stringi_map *map, const char *key)
145 return stringi_map_find__ (map, key, strlen (key));
148 /* If MAP contains KEY with the specified KEY_LEN (or an equivalent with
149 different case) as a key, returns the corresponding value. Otherwise,
150 returns a null pointer. */
152 stringi_map_find__ (const struct stringi_map *map, const char *key,
155 const struct stringi_map_node *node = stringi_map_find_node (map, key,
157 return node != NULL ? node->value : NULL;
160 /* If MAP contains KEY with the specified KEY_LEN (or an equivalent with
161 different case) as a key, returns the corresponding node. Otherwise,
162 returns a null pointer. */
163 struct stringi_map_node *
164 stringi_map_find_node (const struct stringi_map *map, const char *key,
167 return stringi_map_find_node__ (map, key, key_len,
168 utf8_hash_case_bytes (key, key_len, 0));
171 /* If MAP contains KEY (or an equivalent with different case) as a key, deletes
172 that key's node and returns its value, which the caller is responsible for
173 freeing (using free()). Otherwise, returns a null pointer. */
175 stringi_map_find_and_delete (struct stringi_map *map, const char *key)
177 struct stringi_map_node *node = stringi_map_find_node (map, key,
184 stringi_map_delete_node (map, node);
189 /* If MAP does not contain KEY (or an equivalent with different case) as a key,
190 inserts a new node containing copies of KEY and VALUE and returns the new
191 node. Otherwise, returns the existing node that contains KEY. */
192 struct stringi_map_node *
193 stringi_map_insert (struct stringi_map *map, const char *key,
196 size_t key_len = strlen (key);
197 unsigned int hash = utf8_hash_case_bytes (key, key_len, 0);
198 struct stringi_map_node *node = stringi_map_find_node__ (map, key, key_len,
201 node = stringi_map_insert__ (map, xmemdup0 (key, key_len),
202 xstrdup (value), hash);
206 /* If MAP does not contain KEY (or an equivalent with different case) as a key,
207 inserts a new node containing KEY and VALUE and returns the new node.
208 Otherwise, returns the existing node that contains KEY. Either way,
209 ownership of KEY and VALUE is transferred to MAP. */
210 struct stringi_map_node *
211 stringi_map_insert_nocopy (struct stringi_map *map, char *key, char *value)
213 size_t key_len = strlen (key);
214 unsigned int hash = utf8_hash_case_bytes (key, key_len, 0);
215 struct stringi_map_node *node = stringi_map_find_node__ (map, key, key_len,
218 node = stringi_map_insert__ (map, key, value, hash);
227 /* If MAP does not contain KEY (or an equivalent with different case) as a key,
228 inserts a new node containing copies of KEY and VALUE. Otherwise, replaces
229 the existing node's value by a copy of VALUE. Returns the node. */
230 struct stringi_map_node *
231 stringi_map_replace (struct stringi_map *map, const char *key,
234 size_t key_len = strlen (key);
235 unsigned int hash = utf8_hash_case_bytes (key, key_len, 0);
236 struct stringi_map_node *node = stringi_map_find_node__ (map, key, key_len,
239 node = stringi_map_insert__ (map, xstrdup (key), xstrdup (value), hash);
241 stringi_map_node_set_value (node, value);
245 /* If MAP does not contain KEY (or an equivalent with different case) as a key,
246 inserts a new node containing KEY and VALUE. Otherwise, replaces the
247 existing node's value by VALUE. Either way, ownership of KEY and VALUE is
248 transferred to MAP. Returns the node. */
249 struct stringi_map_node *
250 stringi_map_replace_nocopy (struct stringi_map *map, char *key, char *value)
252 size_t key_len = strlen (key);
253 unsigned int hash = utf8_hash_case_bytes (key, key_len, 0);
254 struct stringi_map_node *node = stringi_map_find_node__ (map, key, key_len,
257 node = stringi_map_insert__ (map, key, value, hash);
261 stringi_map_node_set_value_nocopy (node, value);
266 /* Searches MAP for a node with KEY (or an equivalent with different case) as
267 its key. If found, deletes the node and its key and value and returns true.
268 Otherwise, returns false without modifying MAP. */
270 stringi_map_delete (struct stringi_map *map, const char *key)
272 size_t key_len = strlen (key);
273 return stringi_map_delete__ (map, key, key_len,
274 utf8_hash_case_bytes (key, key_len, 0));
277 /* Deletes NODE from MAP and destroys the node and its key and value. */
279 stringi_map_delete_node (struct stringi_map *map,
280 struct stringi_map_node *node)
282 stringi_map_delete_nofree (map, node);
283 stringi_map_node_destroy (node);
286 /* Deletes NODE from MAP. Transfers ownership of NODE to the caller, which
287 becomes responsible for destroying it. */
289 stringi_map_delete_nofree (struct stringi_map *map,
290 struct stringi_map_node *node)
292 hmap_delete (&map->hmap, &node->hmap_node);
295 /* Removes all nodes from MAP and frees them and their keys and values. */
297 stringi_map_clear (struct stringi_map *map)
299 struct stringi_map_node *node, *next;
301 STRINGI_MAP_FOR_EACH_NODE_SAFE (node, next, map)
302 stringi_map_delete_node (map, node);
305 /* Inserts a copy of each of the nodes in SRC into DST. When SRC and DST both
306 have a particular key (or keys that differ only in case), the value in DST's
307 node is left unchanged. */
309 stringi_map_insert_map (struct stringi_map *dst, const struct stringi_map *src)
311 const struct stringi_map_node *node;
313 STRINGI_MAP_FOR_EACH_NODE (node, src)
315 size_t key_len = strlen (node->key);
316 if (!stringi_map_find_node__ (dst, node->key, key_len,
317 node->hmap_node.hash))
318 stringi_map_insert__ (dst, xmemdup0 (node->key, key_len),
319 xstrdup (node->value),
320 node->hmap_node.hash);
324 /* Inserts a copy of each of the nodes in SRC into DST. When SRC and DST both
325 have a particular key (or keys that differ only in case), the value in DST's
326 node is replaced by a copy of the value in SRC's node. */
328 stringi_map_replace_map (struct stringi_map *dst,
329 const struct stringi_map *src)
331 const struct stringi_map_node *snode;
333 STRINGI_MAP_FOR_EACH_NODE (snode, src)
335 size_t key_len = strlen (snode->key);
336 struct stringi_map_node *dnode;
337 dnode = stringi_map_find_node__ (dst, snode->key, key_len,
338 snode->hmap_node.hash);
340 stringi_map_node_set_value (dnode, snode->value);
342 stringi_map_insert__ (dst, xmemdup0 (snode->key, key_len),
343 xstrdup (snode->value),
344 snode->hmap_node.hash);
348 /* Inserts each of the keys in MAP into KEYS. KEYS must already have been
349 initialized (using stringi_set_init()). */
351 stringi_map_get_keys (const struct stringi_map *map, struct stringi_set *keys)
353 const struct stringi_map_node *node;
356 STRINGI_MAP_FOR_EACH_KEY (key, node, map)
357 stringi_set_insert (keys, key);
360 /* Inserts each of the values in MAP into VALUES. VALUES must already have
361 been initialized (using string_set_init()). */
363 stringi_map_get_values (const struct stringi_map *map,
364 struct string_set *values)
366 const struct stringi_map_node *node;
369 STRINGI_MAP_FOR_EACH_VALUE (value, node, map)
370 string_set_insert (values, value);
373 static struct stringi_map_node *
374 stringi_map_find_node__ (const struct stringi_map *map, const char *key,
375 size_t key_len, unsigned int hash)
377 struct stringi_map_node *node;
379 HMAP_FOR_EACH_WITH_HASH (node, struct stringi_map_node, hmap_node,
381 if (!utf8_strncasecmp (key, key_len, node->key, strlen (node->key)))
388 stringi_map_delete__ (struct stringi_map *map, const char *key,
389 size_t key_len, unsigned int hash)
391 struct stringi_map_node *node = stringi_map_find_node__ (map, key, key_len,
395 stringi_map_delete_node (map, node);
402 static struct stringi_map_node *
403 stringi_map_insert__ (struct stringi_map *map, char *key, char *value,
406 struct stringi_map_node *node = xmalloc (sizeof *node);
409 hmap_insert (&map->hmap, &node->hmap_node, hash);