1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2009, 2011 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/string-map.h"
24 #include "libpspp/hash-functions.h"
25 #include "libpspp/string-set.h"
27 #include "gl/xalloc.h"
28 #include "gl/xmemdup0.h"
30 static struct string_map_node *string_map_find_node_with_hash (
31 const struct string_map *, const char *key, size_t length,
33 static bool string_map_delete__ (struct string_map *, const char *key,
35 static struct string_map_node *string_map_insert__ (struct string_map *,
36 char *key, char *value,
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
43 string_map_node_swap_value (struct string_map_node *node,
44 const char *new_value)
46 return string_map_node_swap_value_nocopy (node, xstrdup (new_value));
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
54 string_map_node_swap_value_nocopy (struct string_map_node *node,
57 char *old_value = node->value;
58 node->value = new_value;
62 /* Replaces NODE's value by a copy of VALUE. */
64 string_map_node_set_value (struct string_map_node *node, const char *value)
66 string_map_node_set_value_nocopy (node, xstrdup (value));
69 /* Replaces NODE's value by VALUE, which must be a malloc()'d string,
70 transferring ownership of VALUE to the node.. */
72 string_map_node_set_value_nocopy (struct string_map_node *node, char *value)
78 /* Frees NODE and and its key and value. Ordinarily nodes are owned by
79 string_maps, but this function should only be used by a caller that owns
80 NODE, such as one that has called string_map_delete_nofree() for the
83 string_map_node_destroy (struct string_map_node *node)
90 /* Initializes MAP as an initially empty string map. */
92 string_map_init (struct string_map *map)
94 hmap_init (&map->hmap);
97 /* Initializes MAP as a new string map that initially contains the same pairs
100 string_map_clone (struct string_map *map, const struct string_map *old)
102 const struct string_map_node *node;
103 const char *key, *value;
105 string_map_init (map);
106 hmap_reserve (&map->hmap, string_map_count (old));
107 STRING_MAP_FOR_EACH_KEY_VALUE (key, value, node, old)
108 string_map_insert__ (map, xstrdup (key), xstrdup (value),
109 node->hmap_node.hash);
112 /* Exchanges the contents of string maps A and B. */
114 string_map_swap (struct string_map *a, struct string_map *b)
116 hmap_swap (&a->hmap, &b->hmap);
119 /* Frees MAP and its nodes and key-value pairs. */
121 string_map_destroy (struct string_map *map)
125 string_map_clear (map);
126 hmap_destroy (&map->hmap);
130 /* Returns true if MAP contains KEY as a key, otherwise false. */
132 string_map_contains (const struct string_map *map, const char *key)
134 return string_map_find_node (map, key) != NULL;
137 /* If MAP contains KEY, which is LENGTH bytes long, as a key, returns the
138 corresponding value. Otherwise, returns a null pointer. */
140 string_map_find__ (const struct string_map *map, const char *key,
143 const struct string_map_node *node = string_map_find_node__ (map, key,
145 return node != NULL ? node->value : NULL;
148 /* If MAP contains KEY as a key, returns the corresponding value. Otherwise,
149 returns a null pointer. */
151 string_map_find (const struct string_map *map, const char *key)
153 const struct string_map_node *node = string_map_find_node (map, key);
154 return node != NULL ? node->value : NULL;
157 /* If MAP contains KEY as a key, returns the corresponding node. Otherwise,
158 returns a null pointer. */
159 struct string_map_node *
160 string_map_find_node__ (const struct string_map *map, const char *key,
163 return string_map_find_node_with_hash (map, key, length,
164 hash_bytes (key, length, 0));
167 /* If MAP contains KEY as a key, returns the corresponding node. Otherwise,
168 returns a null pointer. */
169 struct string_map_node *
170 string_map_find_node (const struct string_map *map, const char *key)
172 return string_map_find_node__ (map, key, strlen (key));
175 /* If MAP contains KEY as a key, deletes that key's node and returns its value,
176 which the caller is responsible for freeing (using free()). Otherwise,
177 returns a null pointer. */
179 string_map_find_and_delete (struct string_map *map, const char *key)
181 struct string_map_node *node = string_map_find_node (map, key);
187 string_map_delete_node (map, node);
192 /* If MAP does not contain KEY as a key, inserts a new node containing copies
193 of KEY and VALUE and returns the new node. Otherwise, returns the existing
194 node that contains KEY. */
195 struct string_map_node *
196 string_map_insert (struct string_map *map, const char *key, const char *value)
198 size_t length = strlen (key);
199 unsigned int hash = hash_bytes (key, length, 0);
200 struct string_map_node *node = string_map_find_node_with_hash (map, key,
203 node = string_map_insert__ (map, xmemdup0 (key, length), xstrdup (value),
208 /* If MAP does not contain KEY as a key, inserts a new node containing KEY and
209 VALUE and returns the new node. Otherwise, returns the existing node that
210 contains KEY. Either way, ownership of KEY and VALUE is transferred to
212 struct string_map_node *
213 string_map_insert_nocopy (struct string_map *map, char *key, char *value)
215 size_t length = strlen (key);
216 unsigned int hash = hash_bytes (key, length, 0);
217 struct string_map_node *node = string_map_find_node_with_hash (map, key,
220 node = string_map_insert__ (map, key, value, hash);
229 /* If MAP does not contain KEY as a key, inserts a new node containing copies
230 of KEY and VALUE. Otherwise, replaces the existing node's value by a copy
231 of VALUE. Returns the node. */
232 struct string_map_node *
233 string_map_replace (struct string_map *map, const char *key, const char *value)
235 size_t length = strlen (key);
236 unsigned int hash = hash_bytes (key, length, 0);
237 struct string_map_node *node = string_map_find_node_with_hash (map, key,
240 node = string_map_insert__ (map, xmemdup0 (key, length),
241 xstrdup (value), hash);
243 string_map_node_set_value (node, value);
247 /* If MAP does not contain KEY as a key, inserts a new node containing KEY and
248 VALUE. Otherwise, replaces the existing node's value by VALUE. Either way,
249 ownership of KEY and VALUE is transferred to MAP. Returns the node. */
250 struct string_map_node *
251 string_map_replace_nocopy (struct string_map *map, char *key, char *value)
253 size_t length = strlen (key);
254 unsigned int hash = hash_bytes (key, length, 0);
255 struct string_map_node *node = string_map_find_node_with_hash (map, key,
258 node = string_map_insert__ (map, key, value, hash);
262 string_map_node_set_value_nocopy (node, value);
267 /* Searches MAP for a node with KEY as its key. If found, deletes the node
268 and its key and value and returns true. Otherwise, returns false without
271 string_map_delete (struct string_map *map, const char *key)
273 return string_map_delete__ (map, key, hash_string (key, 0));
276 /* Deletes NODE from MAP and destroys the node and its key and value. */
278 string_map_delete_node (struct string_map *map, struct string_map_node *node)
280 string_map_delete_nofree (map, node);
281 string_map_node_destroy (node);
284 /* Deletes NODE from MAP. Transfers ownership of NODE to the caller, which
285 becomes responsible for destroying it. */
287 string_map_delete_nofree (struct string_map *map, struct string_map_node *node)
289 hmap_delete (&map->hmap, &node->hmap_node);
292 /* Removes all nodes from MAP and frees them and their keys and values. */
294 string_map_clear (struct string_map *map)
296 struct string_map_node *node, *next;
298 STRING_MAP_FOR_EACH_NODE_SAFE (node, next, map)
299 string_map_delete_node (map, node);
302 /* Inserts a copy of each of the nodes in SRC into DST. When SRC and DST both
303 have a particular key, the value in DST's node is left unchanged. */
305 string_map_insert_map (struct string_map *dst, const struct string_map *src)
307 const struct string_map_node *node;
309 STRING_MAP_FOR_EACH_NODE (node, src)
311 if (!string_map_find_node_with_hash (dst, node->key, strlen (node->key),
312 node->hmap_node.hash))
313 string_map_insert__ (dst, xstrdup (node->key), xstrdup (node->value),
314 node->hmap_node.hash);
318 /* Inserts a copy of each of the nodes in SRC into DST. When SRC and DST both
319 have a particular key, the value in DST's node is replaced by a copy of the
320 value in SRC's node. */
322 string_map_replace_map (struct string_map *dst, const struct string_map *src)
324 const struct string_map_node *snode;
326 STRING_MAP_FOR_EACH_NODE (snode, src)
328 struct string_map_node *dnode;
329 dnode = string_map_find_node_with_hash (dst, snode->key,
331 snode->hmap_node.hash);
333 string_map_node_set_value (dnode, snode->value);
335 string_map_insert__ (dst, xstrdup (snode->key), xstrdup (snode->value),
336 snode->hmap_node.hash);
340 /* Inserts each of the keys in MAP into KEYS. KEYS must already have been
341 initialized (using string_set_init()). */
343 string_map_get_keys (const struct string_map *map, struct string_set *keys)
345 const struct string_map_node *node;
348 STRING_MAP_FOR_EACH_KEY (key, node, map)
349 string_set_insert (keys, key);
352 /* Inserts each of the values in MAP into VALUES. VALUES must already have
353 been initialized (using string_set_init()). */
355 string_map_get_values (const struct string_map *map, struct string_set *values)
357 const struct string_map_node *node;
360 STRING_MAP_FOR_EACH_VALUE (value, node, map)
361 string_set_insert (values, value);
364 /* Returns true if A and B have the same content, false otherwise. */
366 string_map_equals (const struct string_map *a, const struct string_map *b)
368 if (string_map_count (a) != string_map_count (b))
371 const struct string_map_node *a_node;
372 STRING_MAP_FOR_EACH_NODE (a_node, a)
374 const struct string_map_node *b_node = string_map_find_node_with_hash (
375 b, a_node->key, strlen (a_node->key), a_node->hmap_node.hash);
376 if (!b_node || strcmp (a_node->value, b_node->value))
383 static struct string_map_node *
384 string_map_find_node_with_hash (const struct string_map *map, const char *key,
385 size_t length, unsigned int hash)
387 struct string_map_node *node;
389 HMAP_FOR_EACH_WITH_HASH (node, struct string_map_node, hmap_node,
391 if (!strncmp (key, node->key, length) && node->key[length] == '\0')
398 string_map_delete__ (struct string_map *map, const char *key,
401 struct string_map_node *node
402 = string_map_find_node_with_hash (map, key, strlen (key), hash);
405 string_map_delete_node (map, node);
412 static struct string_map_node *
413 string_map_insert__ (struct string_map *map, char *key, char *value,
416 struct string_map_node *node = xmalloc (sizeof *node);
419 hmap_insert (&map->hmap, &node->hmap_node, hash);