src/libpspp/hmap.c

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