src/libpspp/hmap.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2008, 2009, 2010 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/hmap.h>
  22 #include <assert.h>
  23 #include <stdlib.h>
  24
  25 #include "xalloc.h"
  26
  27 static size_t capacity_to_mask (size_t capacity);
  28
  29 /* Initializes MAP as a new hash map that is initially empty. */
  30 void
  31 hmap_init (struct hmap *map)
  32 {
  33   map->count = 0;
  34   map->mask = 0;
  35   map->buckets = &map->one;
  36   map->one = NULL;
  37 }
  38
  39 /* Exchanges the contents of hash maps A and B. */
  40 void
  41 hmap_swap (struct hmap *a, struct hmap *b)
  42 {
  43   struct hmap tmp = *a;
  44   *a = *b;
  45   *b = tmp;
  46   if (!a->mask)
  47     a->buckets = &a->one;
  48   if (!b->mask)
  49     b->buckets = &b->one;
  50 }
  51
  52 /* Removes all of the elements from MAP, without destroying MAP itself and
  53    without accessing the existing elements (if any). */
  54 void
  55 hmap_clear (struct hmap *map)
  56 {
  57   size_t i;
  58
  59   for (i = 0; i <= map->mask; i++)
  60     map->buckets[i] = NULL;
  61   map->count = 0;
  62 }
  63
  64 /* Frees the memory, if any, allocated by hash map MAP.  This has
  65    no effect on the actual data items in MAP, if any, because the
  66    client is responsible for allocating and freeing them.  It
  67    could, however, render them inaccessible if the only pointers
  68    to them were from MAP itself, so in such a situation one
  69    should iterate through the map and free the data items before
  70    destroying it. */
  71 void
  72 hmap_destroy (struct hmap *map)
  73 {
  74   if (map != NULL && map->buckets != &map->one)
  75     free (map->buckets);
  76 }
  77
  78 /* Reallocates MAP's hash buckets so that NEW_MASK becomes the
  79    hash value bit-mask used to choose a hash bucket, then
  80    rehashes any data elements in MAP into the new hash buckets.
  81
  82    NEW_MASK must be a power of 2 minus 1 (including 0), that is,
  83    its value in binary must be all 1-bits.  */
  84 static void
  85 hmap_rehash (struct hmap *map, size_t new_mask)
  86 {
  87   struct hmap_node **new_buckets;
  88   struct hmap_node *node, *next;
  89
  90   assert ((new_mask & (new_mask + 1)) == 0);
  91   if (new_mask)
  92     new_buckets = xcalloc (new_mask + 1, sizeof *new_buckets);
  93   else
  94     {
  95       new_buckets = &map->one;
  96       new_buckets[0] = NULL;
  97     }
  98
  99   if (map->count > 0)
 100     {
 101       for (node = hmap_first (map); node != NULL; node = next)
 102         {
 103           size_t new_idx = node->hash & new_mask;
 104           struct hmap_node **new_bucket = &new_buckets[new_idx];
 105           next = hmap_next (map, node);
 106           node->next = *new_bucket;
 107           *new_bucket = node;
 108         }
 109     }
 110   if (map->buckets != &map->one)
 111     free (map->buckets);
 112   map->buckets = new_buckets;
 113   map->mask = new_mask;
 114 }
 115
 116 /* Ensures that MAP has sufficient space to store at least
 117    CAPACITY data elements, allocating a new set of buckets and
 118    rehashing if necessary. */
 119 void
 120 hmap_reserve (struct hmap *map, size_t capacity)
 121 {
 122   if (capacity > hmap_capacity (map))
 123     hmap_rehash (map, capacity_to_mask (capacity));
 124 }
 125
 126 /* Shrinks MAP's set of buckets to the minimum number needed to
 127    store its current number of elements, allocating a new set of
 128    buckets and rehashing if that would save space. */
 129 void
 130 hmap_shrink (struct hmap *map)
 131 {
 132   size_t new_mask = capacity_to_mask (map->count);
 133   if (new_mask < map->mask)
 134     hmap_rehash (map, new_mask);
 135 }
 136
 137 /* Moves NODE around in MAP to compensate for its hash value
 138    having changed to NEW_HASH.
 139
 140    This function does not verify that MAP does not already
 141    contain a data item that duplicates NODE's new value.  If
 142    duplicates should be disallowed (which is the usual case),
 143    then the client must check for duplicates before changing
 144    NODE's value. */
 145 void
 146 hmap_changed (struct hmap *map, struct hmap_node *node, size_t new_hash)
 147 {
 148   if ((new_hash ^ node->hash) & map->mask)
 149     {
 150       hmap_delete (map, node);
 151       hmap_insert_fast (map, node, new_hash);
 152     }
 153   else
 154     node->hash = new_hash;
 155 }
 156
 157 /* Hash map nodes may be moved around in memory as necessary,
 158    e.g. as the result of an realloc operation on a block that
 159    contains a node.  Once this is done, call this function
 160    passing NODE that was moved, its former location in memory
 161    OLD, and its hash map MAP before attempting any other
 162    operation on MAP, NODE, or any other node in MAP.
 163
 164    It is not safe to move more than one node, then to call this
 165    function for each node.  Instead, move a single node, call
 166    this function, move another node, and so on.  Alternatively,
 167    remove all affected nodes from the hash map, move them, then
 168    re-insert all of them.
 169
 170    Assuming uniform hashing and no duplicate data items in MAP,
 171    this function runs in constant time. */
 172 void
 173 hmap_moved (struct hmap *map,
 174             struct hmap_node *node, const struct hmap_node *old)
 175 {
 176   struct hmap_node **p = &map->buckets[node->hash & map->mask];
 177   while (*p != old)
 178     p = &(*p)->next;
 179   *p = node;
 180 }
 181 \f
 182 /* Returns the minimum-value mask required to allow for a hash
 183    table capacity of at least CAPACITY.  The return value will be
 184    a bit-mask suitable for use as the "mask" member of struct
 185    hmap, that is, a power of 2 minus 1 (including 0). */
 186 static size_t
 187 capacity_to_mask (size_t capacity)
 188 {
 189   /* Calculate the minimum mask necesary to support the given
 190      capacity. */
 191   size_t mask = 0;
 192   while (hmap_mask_to_capacity__ (mask) < capacity)
 193     mask = (mask << 1) | 1;
 194
 195   /* If the mask is nonzero, make it at least 3, because there is
 196      little point in allocating an array of just 2 pointers. */
 197   mask |= (mask & 1) << 1;
 198
 199   return mask;
 200 }