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"
29 static struct string_map_node *string_map_find_node_with_hash (
30 const struct string_map *, const char *key, size_t length,
32 static bool string_map_delete__ (struct string_map *, const char *key,
34 static struct string_map_node *string_map_insert__ (struct string_map *,
35 char *key, char *value,
38 /* Sets NODE's value to a copy of NEW_VALUE and returns the node's previous
39 value. The caller is responsible for freeing the returned string (with
42 string_map_node_swap_value (struct string_map_node *node,
43 const char *new_value)
45 return string_map_node_swap_value_nocopy (node, xstrdup (new_value));
48 /* Sets NODE's value to NEW_VALUE, which must be a malloc()'d string,
49 transferring ownership of NEW_VALUE to the node. Returns the node's
50 previous value, which the caller is responsible for freeing (with
53 string_map_node_swap_value_nocopy (struct string_map_node *node,
56 char *old_value = node->value;
57 node->value = new_value;
61 /* Replaces NODE's value by a copy of VALUE. */
63 string_map_node_set_value (struct string_map_node *node, const char *value)
65 string_map_node_set_value_nocopy (node, xstrdup (value));
68 /* Replaces NODE's value by VALUE, which must be a malloc()'d string,
69 transferring ownership of VALUE to the node.. */
71 string_map_node_set_value_nocopy (struct string_map_node *node, char *value)
77 /* Frees NODE and and its key and value. Ordinarily nodes are owned by
78 string_maps, but this function should only be used by a caller that owns
79 NODE, such as one that has called string_map_delete_nofree() for the
82 string_map_node_destroy (struct string_map_node *node)
89 /* Initializes MAP as an initially empty string map. */
91 string_map_init (struct string_map *map)
93 hmap_init (&map->hmap);
96 /* Initializes MAP as a new string map that initially contains the same pairs
99 string_map_clone (struct string_map *map, const struct string_map *old)
101 const struct string_map_node *node;
102 const char *key, *value;
104 string_map_init (map);
105 hmap_reserve (&map->hmap, string_map_count (old));
106 STRING_MAP_FOR_EACH_KEY_VALUE (key, value, node, old)
107 string_map_insert__ (map, xstrdup (key), xstrdup (value),
108 node->hmap_node.hash);
111 /* Exchanges the contents of string maps A and B. */
113 string_map_swap (struct string_map *a, struct string_map *b)
115 hmap_swap (&a->hmap, &b->hmap);
118 /* Frees MAP and its nodes and key-value pairs. */
120 string_map_destroy (struct string_map *map)
124 string_map_clear (map);
125 hmap_destroy (&map->hmap);
129 /* Returns true if MAP contains KEY as a key, otherwise false. */
131 string_map_contains (const struct string_map *map, const char *key)
133 return string_map_find_node (map, key) != NULL;
136 /* If MAP contains KEY, which is LENGTH bytes long, as a key, returns the
137 corresponding value. Otherwise, returns a null pointer. */
139 string_map_find__ (const struct string_map *map, const char *key,
142 const struct string_map_node *node = string_map_find_node__ (map, key,
144 return node != NULL ? node->value : NULL;
147 /* If MAP contains KEY as a key, returns the corresponding value. Otherwise,
148 returns a null pointer. */
150 string_map_find (const struct string_map *map, const char *key)
152 const struct string_map_node *node = string_map_find_node (map, key);
153 return node != NULL ? node->value : NULL;
156 /* If MAP contains KEY as a key, returns the corresponding node. Otherwise,
157 returns a null pointer. */
158 struct string_map_node *
159 string_map_find_node__ (const struct string_map *map, const char *key,
162 return string_map_find_node_with_hash (map, key, length,
163 hash_bytes (key, length, 0));
166 /* If MAP contains KEY as a key, returns the corresponding node. Otherwise,
167 returns a null pointer. */
168 struct string_map_node *
169 string_map_find_node (const struct string_map *map, const char *key)
171 return string_map_find_node__ (map, key, strlen (key));
174 /* If MAP contains KEY as a key, deletes that key's node and returns its value,
175 which the caller is responsible for freeing (using free()). Otherwise,
176 returns a null pointer. */
178 string_map_find_and_delete (struct string_map *map, const char *key)
180 struct string_map_node *node = string_map_find_node (map, key);
186 string_map_delete_node (map, node);
191 /* If MAP does not contain KEY as a key, inserts a new node containing copies
192 of KEY and VALUE and returns the new node. Otherwise, returns the existing
193 node that contains KEY. */
194 struct string_map_node *
195 string_map_insert (struct string_map *map, const char *key, const char *value)
197 size_t length = strlen (key);
198 unsigned int hash = hash_bytes (key, length, 0);
199 struct string_map_node *node = string_map_find_node_with_hash (map, key,
202 node = string_map_insert__ (map, xstrdup (key), xstrdup (value), hash);
206 /* If MAP does not contain KEY as a key, inserts a new node containing KEY and
207 VALUE and returns the new node. Otherwise, returns the existing node that
208 contains KEY. Either way, ownership of KEY and VALUE is transferred to
210 struct string_map_node *
211 string_map_insert_nocopy (struct string_map *map, char *key, char *value)
213 size_t length = strlen (key);
214 unsigned int hash = hash_bytes (key, length, 0);
215 struct string_map_node *node = string_map_find_node_with_hash (map, key,
218 node = string_map_insert__ (map, key, value, hash);
227 /* If MAP does not contain KEY as a key, inserts a new node containing copies
228 of KEY and VALUE. Otherwise, replaces the existing node's value by a copy
229 of VALUE. Returns the node. */
230 struct string_map_node *
231 string_map_replace (struct string_map *map, const char *key, const char *value)
233 size_t length = strlen (key);
234 unsigned int hash = hash_bytes (key, length, 0);
235 struct string_map_node *node = string_map_find_node_with_hash (map, key,
238 node = string_map_insert__ (map, xstrdup (key), xstrdup (value), hash);
240 string_map_node_set_value (node, value);
244 /* If MAP does not contain KEY as a key, inserts a new node containing KEY and
245 VALUE. Otherwise, replaces the existing node's value by VALUE. Either way,
246 ownership of KEY and VALUE is transferred to MAP. Returns the node. */
247 struct string_map_node *
248 string_map_replace_nocopy (struct string_map *map, char *key, char *value)
250 size_t length = strlen (key);
251 unsigned int hash = hash_bytes (key, length, 0);
252 struct string_map_node *node = string_map_find_node_with_hash (map, key,
255 node = string_map_insert__ (map, key, value, hash);
259 string_map_node_set_value_nocopy (node, value);
264 /* Searches MAP for a node with KEY as its key. If found, deletes the node
265 and its key and value and returns true. Otherwise, returns false without
268 string_map_delete (struct string_map *map, const char *key)
270 return string_map_delete__ (map, key, hash_string (key, 0));
273 /* Deletes NODE from MAP and destroys the node and its key and value. */
275 string_map_delete_node (struct string_map *map, struct string_map_node *node)
277 string_map_delete_nofree (map, node);
278 string_map_node_destroy (node);
281 /* Deletes NODE from MAP. Transfers ownership of NODE to the caller, which
282 becomes responsible for destroying it. */
284 string_map_delete_nofree (struct string_map *map, struct string_map_node *node)
286 hmap_delete (&map->hmap, &node->hmap_node);
289 /* Removes all nodes from MAP and frees them and their keys and values. */
291 string_map_clear (struct string_map *map)
293 struct string_map_node *node, *next;
295 STRING_MAP_FOR_EACH_NODE_SAFE (node, next, map)
296 string_map_delete_node (map, node);
299 /* Inserts a copy of each of the nodes in SRC into DST. When SRC and DST both
300 have a particular key, the value in DST's node is left unchanged. */
302 string_map_insert_map (struct string_map *dst, const struct string_map *src)
304 const struct string_map_node *node;
306 STRING_MAP_FOR_EACH_NODE (node, src)
308 if (!string_map_find_node_with_hash (dst, node->key, strlen (node->key),
309 node->hmap_node.hash))
310 string_map_insert__ (dst, xstrdup (node->key), xstrdup (node->value),
311 node->hmap_node.hash);
315 /* Inserts a copy of each of the nodes in SRC into DST. When SRC and DST both
316 have a particular key, the value in DST's node is replaced by a copy of the
317 value in SRC's node. */
319 string_map_replace_map (struct string_map *dst, const struct string_map *src)
321 const struct string_map_node *snode;
323 STRING_MAP_FOR_EACH_NODE (snode, src)
325 struct string_map_node *dnode;
326 dnode = string_map_find_node_with_hash (dst, snode->key,
328 snode->hmap_node.hash);
330 string_map_node_set_value (dnode, snode->value);
332 string_map_insert__ (dst, xstrdup (snode->key), xstrdup (snode->value),
333 snode->hmap_node.hash);
337 /* Inserts each of the keys in MAP into KEYS. KEYS must already have been
338 initialized (using string_set_init()). */
340 string_map_get_keys (const struct string_map *map, struct string_set *keys)
342 const struct string_map_node *node;
345 STRING_MAP_FOR_EACH_KEY (key, node, map)
346 string_set_insert (keys, key);
349 /* Inserts each of the values in MAP into VALUES. VALUES must already have
350 been initialized (using string_set_init()). */
352 string_map_get_values (const struct string_map *map, struct string_set *values)
354 const struct string_map_node *node;
357 STRING_MAP_FOR_EACH_VALUE (value, node, map)
358 string_set_insert (values, value);
361 static struct string_map_node *
362 string_map_find_node_with_hash (const struct string_map *map, const char *key,
363 size_t length, unsigned int hash)
365 struct string_map_node *node;
367 HMAP_FOR_EACH_WITH_HASH (node, struct string_map_node, hmap_node,
369 if (!strncmp (key, node->key, length) && node->key[length] == '\0')
376 string_map_delete__ (struct string_map *map, const char *key,
379 struct string_map_node *node
380 = string_map_find_node_with_hash (map, key, strlen (key), hash);
383 string_map_delete_node (map, node);
390 static struct string_map_node *
391 string_map_insert__ (struct string_map *map, char *key, char *value,
394 struct string_map_node *node = xmalloc (sizeof *node);
397 hmap_insert (&map->hmap, &node->hmap_node, hash);