pintos-os.org Git - pspp/blob - src/libpspp/stringi-map.c

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