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