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