src/libpspp/stringi-map.c

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