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

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2008, 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 #ifdef HAVE_CONFIG_H
  18 #include <config.h>
  19 #endif
  20
  21 #include "libpspp/hmapx.h"
  22 #include <stdlib.h>
  23 #include "gl/xalloc.h"
  24
  25 /* Frees the memory, if any, allocated by hash map MAP, including
  26    all hmapx_nodes that it contains.  The user-defined data items
  27    that the hmapx_nodes point to are not affected.  If those
  28    items should be freed, then it should be done by iterating
  29    through MAP's contents before destroying MAP. */
  30 void
  31 hmapx_destroy (struct hmapx *map)
  32 {
  33   if (map != NULL)
  34     {
  35       if (!(hmapx_is_empty (map)))
  36         {
  37           struct hmapx_node *node, *next;
  38           for (node = hmapx_first (map); node != NULL; node = next)
  39             {
  40               next = hmapx_next (map, node);
  41               free (node);
  42             }
  43         }
  44       hmap_destroy (&map->hmap);
  45     }
  46 }
  47
  48 /* Removes all hmapx_nodes from MAP and frees them.  The user-defined data
  49    items that the hmapx_nodes point to are not affected. */
  50 void
  51 hmapx_clear (struct hmapx *map)
  52 {
  53   struct hmapx_node *node, *next;
  54
  55   for (node = hmapx_first (map); node; node = next)
  56     {
  57       next = hmapx_next (map, node);
  58       hmapx_delete (map, node);
  59     }
  60 }
  61
  62 /* Allocates and returns a new hmapx_node with DATA as its data
  63    item. */
  64 static struct hmapx_node *
  65 make_hmapx_node (void *data)
  66 {
  67   struct hmapx_node *node = xmalloc (sizeof *node);
  68   node->data = data;
  69   return node;
  70 }
  71
  72 /* Inserts DATA into MAP with hash value HASH and returns the new
  73    hmapx_node created to contain DATA.  If the insertion causes
  74    MAP's current capacity, as reported by hmapx_capacity(), to be
  75    exceeded, rehashes MAP with an increased number of hash
  76    buckets.
  77
  78    This function runs in constant time amortized over all the
  79    insertions into MAP.
  80
  81    This function does not verify that MAP does not already
  82    contain a data item with the same value as DATA.  If
  83    duplicates should be disallowed (which is the usual case),
  84    then the client must check for duplicates itself before
  85    inserting the new item. */
  86 struct hmapx_node *
  87 hmapx_insert (struct hmapx *map, void *data, size_t hash)
  88 {
  89   struct hmapx_node *node = make_hmapx_node (data);
  90   hmap_insert (&map->hmap, &node->hmap_node, hash);
  91   return node;
  92 }
  93
  94 /* Inserts DATA into MAP with hash value HASH and returns the new
  95    hmapx_node created to contain DATA.  Does not check whether
  96    this causes MAP's current capacity to be exceeded.  The caller
  97    must take responsibility for that (or use hmapx_insert()
  98    instead).
  99
 100    This function runs in constant time.
 101
 102    This function does not verify that MAP does not already
 103    contain a data item with the same value as DATA.  If
 104    duplicates should be disallowed (which is the usual case),
 105    then the client must check for duplicates itself before
 106    inserting the new node. */
 107 struct hmapx_node *
 108 hmapx_insert_fast (struct hmapx *map, void *data, size_t hash)
 109 {
 110   struct hmapx_node *node = make_hmapx_node (data);
 111   hmap_insert_fast (&map->hmap, &node->hmap_node, hash);
 112   return node;
 113 }