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