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

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