pintos-os.org Git - pspp/blob - 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 #include "gl/xmemdup0.h"
  29
  30 static struct string_map_node *string_map_find_node_with_hash (
  31   const struct string_map *, const char *key, size_t length,
  32   unsigned int hash);
  33 static bool string_map_delete__ (struct string_map *, const char *key,
  34                                  unsigned int hash);
  35 static struct string_map_node *string_map_insert__ (struct string_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 string_map_node_swap_value (struct string_map_node *node,
  44                             const char *new_value)
  45 {
  46   return string_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 string_map_node_swap_value_nocopy (struct string_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 string_map_node_set_value (struct string_map_node *node, const char *value)
  65 {
  66   string_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 string_map_node_set_value_nocopy (struct string_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    string_maps, but this function should only be used by a caller that owns
  80    NODE, such as one that has called string_map_delete_nofree() for the
  81    node. */
  82 void
  83 string_map_node_destroy (struct string_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 string map. */
  91 void
  92 string_map_init (struct string_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 string_map_clone (struct string_map *map, const struct string_map *old)
 101 {
 102   const struct string_map_node *node;
 103   const char *key, *value;
 104
 105   string_map_init (map);
 106   hmap_reserve (&map->hmap, string_map_count (old));
 107   STRING_MAP_FOR_EACH_KEY_VALUE (key, value, node, old)
 108     string_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 string_map_swap (struct string_map *a, struct string_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 string_map_destroy (struct string_map *map)
 122 {
 123   if (map != NULL)
 124     {
 125       string_map_clear (map);
 126       hmap_destroy (&map->hmap);
 127     }
 128 }
 129
 130 /* Returns true if MAP contains KEY as a key, otherwise false. */
 131 bool
 132 string_map_contains (const struct string_map *map, const char *key)
 133 {
 134   return string_map_find_node (map, key) != NULL;
 135 }
 136
 137 /* If MAP contains KEY, which is LENGTH bytes long, as a key, returns the
 138    corresponding value.  Otherwise, returns a null pointer. */
 139 const char *
 140 string_map_find__ (const struct string_map *map, const char *key,
 141                    size_t length)
 142 {
 143   const struct string_map_node *node = string_map_find_node__ (map, key,
 144                                                                length);
 145   return node != NULL ? node->value : NULL;
 146 }
 147
 148 /* If MAP contains KEY as a key, returns the corresponding value.  Otherwise,
 149    returns a null pointer. */
 150 const char *
 151 string_map_find (const struct string_map *map, const char *key)
 152 {
 153   const struct string_map_node *node = string_map_find_node (map, key);
 154   return node != NULL ? node->value : NULL;
 155 }
 156
 157 /* If MAP contains KEY as a key, returns the corresponding node.  Otherwise,
 158    returns a null pointer. */
 159 struct string_map_node *
 160 string_map_find_node__ (const struct string_map *map, const char *key,
 161                         size_t length)
 162 {
 163   return string_map_find_node_with_hash (map, key, length,
 164                                          hash_bytes (key, length, 0));
 165 }
 166
 167 /* If MAP contains KEY as a key, returns the corresponding node.  Otherwise,
 168    returns a null pointer. */
 169 struct string_map_node *
 170 string_map_find_node (const struct string_map *map, const char *key)
 171 {
 172   return string_map_find_node__ (map, key, strlen (key));
 173 }
 174
 175 /* If MAP contains KEY as a key, deletes that key's node and returns its value,
 176    which the caller is responsible for freeing (using free()).  Otherwise,
 177    returns a null pointer. */
 178 char *
 179 string_map_find_and_delete (struct string_map *map, const char *key)
 180 {
 181   struct string_map_node *node = string_map_find_node (map, key);
 182   char *value = NULL;
 183   if (node != NULL)
 184     {
 185       value = node->value;
 186       node->value = NULL;
 187       string_map_delete_node (map, node);
 188     }
 189   return value;
 190 }
 191
 192 /* If MAP does not contain KEY as a key, inserts a new node containing copies
 193    of KEY and VALUE and returns the new node.  Otherwise, returns the existing
 194    node that contains KEY. */
 195 struct string_map_node *
 196 string_map_insert (struct string_map *map, const char *key, const char *value)
 197 {
 198   size_t length = strlen (key);
 199   unsigned int hash = hash_bytes (key, length, 0);
 200   struct string_map_node *node = string_map_find_node_with_hash (map, key,
 201                                                                  length, hash);
 202   if (node == NULL)
 203     node = string_map_insert__ (map, xmemdup0 (key, length), xstrdup (value),
 204                                 hash);
 205   return node;
 206 }
 207
 208 /* If MAP does not contain KEY as a key, inserts a new node containing KEY and
 209    VALUE and returns the new node.  Otherwise, returns the existing node that
 210    contains KEY.  Either way, ownership of KEY and VALUE is transferred to
 211    MAP. */
 212 struct string_map_node *
 213 string_map_insert_nocopy (struct string_map *map, char *key, char *value)
 214 {
 215   size_t length = strlen (key);
 216   unsigned int hash = hash_bytes (key, length, 0);
 217   struct string_map_node *node = string_map_find_node_with_hash (map, key,
 218                                                                  length, hash);
 219   if (node == NULL)
 220     node = string_map_insert__ (map, key, value, hash);
 221   else
 222     {
 223       free (key);
 224       free (value);
 225     }
 226   return node;
 227 }
 228
 229 /* If MAP does not contain KEY as a key, inserts a new node containing copies
 230    of KEY and VALUE.  Otherwise, replaces the existing node's value by a copy
 231    of VALUE.  Returns the node. */
 232 struct string_map_node *
 233 string_map_replace (struct string_map *map, const char *key, const char *value)
 234 {
 235   size_t length = strlen (key);
 236   unsigned int hash = hash_bytes (key, length, 0);
 237   struct string_map_node *node = string_map_find_node_with_hash (map, key,
 238                                                                  length, hash);
 239   if (node == NULL)
 240     node = string_map_insert__ (map, xmemdup0 (key, length),
 241                                 xstrdup (value), hash);
 242   else
 243     string_map_node_set_value (node, value);
 244   return node;
 245 }
 246
 247 /* If MAP does not contain KEY as a key, inserts a new node containing KEY and
 248    VALUE.  Otherwise, replaces the existing node's value by VALUE.  Either way,
 249    ownership of KEY and VALUE is transferred to MAP.  Returns the node. */
 250 struct string_map_node *
 251 string_map_replace_nocopy (struct string_map *map, char *key, char *value)
 252 {
 253   size_t length = strlen (key);
 254   unsigned int hash = hash_bytes (key, length, 0);
 255   struct string_map_node *node = string_map_find_node_with_hash (map, key,
 256                                                                  length, hash);
 257   if (node == NULL)
 258     node = string_map_insert__ (map, key, value, hash);
 259   else
 260     {
 261       free (key);
 262       string_map_node_set_value_nocopy (node, value);
 263     }
 264   return node;
 265 }
 266
 267 /* Searches MAP for a node with KEY as its key.  If found, deletes the node
 268    and its key and value and returns true.  Otherwise, returns false without
 269    modifying MAP. */
 270 bool
 271 string_map_delete (struct string_map *map, const char *key)
 272 {
 273   return string_map_delete__ (map, key, hash_string (key, 0));
 274 }
 275
 276 /* Deletes NODE from MAP and destroys the node and its key and value. */
 277 void
 278 string_map_delete_node (struct string_map *map, struct string_map_node *node)
 279 {
 280   string_map_delete_nofree (map, node);
 281   string_map_node_destroy (node);
 282 }
 283
 284 /* Deletes NODE from MAP.  Transfers ownership of NODE to the caller, which
 285    becomes responsible for destroying it. */
 286 void
 287 string_map_delete_nofree (struct string_map *map, struct string_map_node *node)
 288 {
 289   hmap_delete (&map->hmap, &node->hmap_node);
 290 }
 291
 292 /* Removes all nodes from MAP and frees them and their keys and values. */
 293 void
 294 string_map_clear (struct string_map *map)
 295 {
 296   struct string_map_node *node, *next;
 297
 298   STRING_MAP_FOR_EACH_NODE_SAFE (node, next, map)
 299     string_map_delete_node (map, node);
 300 }
 301
 302 /* Inserts a copy of each of the nodes in SRC into DST.  When SRC and DST both
 303    have a particular key, the value in DST's node is left unchanged. */
 304 void
 305 string_map_insert_map (struct string_map *dst, const struct string_map *src)
 306 {
 307   const struct string_map_node *node;
 308
 309   STRING_MAP_FOR_EACH_NODE (node, src)
 310     {
 311       if (!string_map_find_node_with_hash (dst, node->key, strlen (node->key),
 312                                            node->hmap_node.hash))
 313         string_map_insert__ (dst, xstrdup (node->key), xstrdup (node->value),
 314                              node->hmap_node.hash);
 315     }
 316 }
 317
 318 /* Inserts a copy of each of the nodes in SRC into DST.  When SRC and DST both
 319    have a particular key, the value in DST's node is replaced by a copy of the
 320    value in SRC's node. */
 321 void
 322 string_map_replace_map (struct string_map *dst, const struct string_map *src)
 323 {
 324   const struct string_map_node *snode;
 325
 326   STRING_MAP_FOR_EACH_NODE (snode, src)
 327     {
 328       struct string_map_node *dnode;
 329       dnode = string_map_find_node_with_hash (dst, snode->key,
 330                                               strlen (snode->key),
 331                                               snode->hmap_node.hash);
 332       if (dnode != NULL)
 333         string_map_node_set_value (dnode, snode->value);
 334       else
 335         string_map_insert__ (dst, xstrdup (snode->key), xstrdup (snode->value),
 336                              snode->hmap_node.hash);
 337     }
 338 }
 339
 340 /* Inserts each of the keys in MAP into KEYS.  KEYS must already have been
 341    initialized (using string_set_init()). */
 342 void
 343 string_map_get_keys (const struct string_map *map, struct string_set *keys)
 344 {
 345   const struct string_map_node *node;
 346   const char *key;
 347
 348   STRING_MAP_FOR_EACH_KEY (key, node, map)
 349     string_set_insert (keys, key);
 350 }
 351
 352 /* Inserts each of the values in MAP into VALUES.  VALUES must already have
 353    been initialized (using string_set_init()). */
 354 void
 355 string_map_get_values (const struct string_map *map, struct string_set *values)
 356 {
 357   const struct string_map_node *node;
 358   const char *value;
 359
 360   STRING_MAP_FOR_EACH_VALUE (value, node, map)
 361     string_set_insert (values, value);
 362 }
 363
 364 /* Returns true if A and B have the same content, false otherwise. */
 365 bool
 366 string_map_equals (const struct string_map *a, const struct string_map *b)
 367 {
 368   if (string_map_count (a) != string_map_count (b))
 369     return false;
 370
 371    const struct string_map_node *a_node;
 372    STRING_MAP_FOR_EACH_NODE (a_node, a)
 373      {
 374        const struct string_map_node *b_node = string_map_find_node_with_hash (
 375          b, a_node->key, strlen (a_node->key), a_node->hmap_node.hash);
 376        if (!b_node || strcmp (a_node->value, b_node->value))
 377          return false;
 378      }
 379
 380    return true;
 381 }
 382 \f
 383 static struct string_map_node *
 384 string_map_find_node_with_hash (const struct string_map *map, const char *key,
 385                                 size_t length, unsigned int hash)
 386 {
 387   struct string_map_node *node;
 388
 389   HMAP_FOR_EACH_WITH_HASH (node, struct string_map_node, hmap_node,
 390                            hash, &map->hmap)
 391     if (!strncmp (key, node->key, length) && node->key[length] == '\0')
 392       return node;
 393
 394   return NULL;
 395 }
 396
 397 static bool
 398 string_map_delete__ (struct string_map *map, const char *key,
 399                      unsigned int hash)
 400 {
 401   struct string_map_node *node
 402     = string_map_find_node_with_hash (map, key, strlen (key), hash);
 403   if (node != NULL)
 404     {
 405       string_map_delete_node (map, node);
 406       return true;
 407     }
 408   else
 409     return false;
 410 }
 411
 412 static struct string_map_node *
 413 string_map_insert__ (struct string_map *map, char *key, char *value,
 414                      unsigned int hash)
 415 {
 416   struct string_map_node *node = xmalloc (sizeof *node);
 417   node->key = key;
 418   node->value = value;
 419   hmap_insert (&map->hmap, &node->hmap_node, hash);
 420   return node;
 421 }
 422