src/libpspp/hmap.c

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