#include "gl/xalloc.h"
-static size_t capacity_to_mask (size_t capacity);
+static int capacity_to_shift (size_t capacity);
/* Initializes MAP as a new hash map that is initially empty. */
void
hmap_init (struct hmap *map)
{
+ map->buckets = map->two;
+ map->two[0] = map->two[1] = NULL;
map->count = 0;
- map->mask = 0;
- map->buckets = &map->one;
- map->one = NULL;
+ map->shift = HMAP_MAX_SHIFT;
}
/* Exchanges the contents of hash maps A and B. */
struct hmap tmp = *a;
*a = *b;
*b = tmp;
- if (!a->mask)
- a->buckets = &a->one;
- if (!b->mask)
- b->buckets = &b->one;
+ if (a->buckets == b->two)
+ a->buckets = a->two;
+ if (b->buckets == a->two)
+ b->buckets = b->two;
}
/* Removes all of the elements from MAP, without destroying MAP itself and
{
size_t i;
- for (i = 0; i <= map->mask; i++)
+ for (i = 0; i <= SIZE_MAX >> map->shift; i++)
map->buckets[i] = NULL;
map->count = 0;
}
void
hmap_destroy (struct hmap *map)
{
- if (map != NULL && map->buckets != &map->one)
+ if (map != NULL && map->buckets != map->two)
free (map->buckets);
}
-/* Reallocates MAP's hash buckets so that NEW_MASK becomes the
- hash value bit-mask used to choose a hash bucket, then
+/* Inserts NODE into MAP with hash value HASH. If the insertion causes MAP's
+ current capacity, as reported by hmap_capacity(), to be exceeded, rehashes
+ MAP with an increased number of hash buckets.
+
+ This function runs in constant time amortized over all the insertions into
+ MAP.
+
+ This function does not verify that MAP does not already contain a data item
+ with the same value as NODE. If duplicates should be disallowed (which is
+ the usual case), then the client must check for duplicates itself before
+ inserting the new node. */
+void
+hmap_insert (struct hmap *map, struct hmap_node *node, size_t hash)
+{
+ hmap_insert_fast (map, node, hash);
+ if (map->count > hmap_capacity (map))
+ hmap_reserve (map, map->count);
+}
+
+/* Inserts NODE into MAP with hash value HASH. Does not check whether this
+ causes MAP's current capacity to be exceeded. The caller must take
+ responsibility for that (or use hmap_insert() instead).
+
+ This function runs in time linear in the number of nodes already in the
+ bucket. Given a good hash function, this yields constant time on average.
+
+ This function does not verify that MAP does not already contain a data item
+ with the same value as NODE. If duplicates should be disallowed (which is
+ the usual case), then the client must check for duplicates itself before
+ inserting the new node. */
+void
+hmap_insert_fast (struct hmap *map, struct hmap_node *node, size_t hash)
+{
+ struct hmap_node **bucket;
+
+ for (bucket = &map->buckets[hash >> map->shift]; *bucket != NULL;
+ bucket = &(*bucket)->next)
+ if ((*bucket)->hash > hash)
+ break;
+
+ node->hash = hash;
+ node->next = *bucket;
+ *bucket = node;
+ map->count++;
+}
+
+/* Reallocates MAP's hash buckets so that NEW_SHIFT becomes MAP->shift and
rehashes any data elements in MAP into the new hash buckets.
- NEW_MASK must be a power of 2 minus 1 (including 0), that is,
- its value in binary must be all 1-bits. */
+ NEW_SHIFT must be between 2 and HMAP_MAX_SHIFT, inclusive. */
static void
-hmap_rehash (struct hmap *map, size_t new_mask)
+hmap_rehash (struct hmap *map, size_t new_shift)
{
struct hmap_node **new_buckets;
struct hmap_node *node, *next;
- assert ((new_mask & (new_mask + 1)) == 0);
- if (new_mask)
- new_buckets = xcalloc (new_mask + 1, sizeof *new_buckets);
- else
+ assert (new_shift != map->shift);
+
+ if (new_shift < HMAP_MAX_SHIFT)
+ new_buckets = xcalloc ((SIZE_MAX >> new_shift) + 1, sizeof *new_buckets);
+ else
{
- new_buckets = &map->one;
- new_buckets[0] = NULL;
+ new_buckets = map->two;
+ new_buckets[0] = new_buckets[1] = NULL;
}
-
+
if (map->count > 0)
{
for (node = hmap_first (map); node != NULL; node = next)
{
- size_t new_idx = node->hash & new_mask;
- struct hmap_node **new_bucket = &new_buckets[new_idx];
+ struct hmap_node **bucket;
+
next = hmap_next (map, node);
- node->next = *new_bucket;
- *new_bucket = node;
- }
+ for (bucket = &new_buckets[node->hash >> new_shift]; *bucket != NULL;
+ bucket = &(*bucket)->next)
+ continue;
+ *bucket = node;
+ node->next = NULL;
+ }
}
- if (map->buckets != &map->one)
+ if (map->buckets != map->two)
free (map->buckets);
map->buckets = new_buckets;
- map->mask = new_mask;
+ map->shift = new_shift;
}
/* Ensures that MAP has sufficient space to store at least
hmap_reserve (struct hmap *map, size_t capacity)
{
if (capacity > hmap_capacity (map))
- hmap_rehash (map, capacity_to_mask (capacity));
+ hmap_rehash (map, capacity_to_shift (capacity));
}
/* Shrinks MAP's set of buckets to the minimum number needed to
void
hmap_shrink (struct hmap *map)
{
- size_t new_mask = capacity_to_mask (map->count);
- if (new_mask < map->mask)
- hmap_rehash (map, new_mask);
+ size_t new_shift = capacity_to_shift (map->count);
+ if (new_shift > map->shift)
+ hmap_rehash (map, new_shift);
}
/* Moves NODE around in MAP to compensate for its hash value
void
hmap_changed (struct hmap *map, struct hmap_node *node, size_t new_hash)
{
- if ((new_hash ^ node->hash) & map->mask)
+ if (new_hash != node->hash)
{
hmap_delete (map, node);
hmap_insert_fast (map, node, new_hash);
}
- else
- node->hash = new_hash;
}
/* Hash map nodes may be moved around in memory as necessary,
hmap_moved (struct hmap *map,
struct hmap_node *node, const struct hmap_node *old)
{
- struct hmap_node **p = &map->buckets[node->hash & map->mask];
+ struct hmap_node **p = &map->buckets[node->hash >> map->shift];
while (*p != old)
p = &(*p)->next;
*p = node;
}
\f
-/* Returns the minimum-value mask required to allow for a hash
- table capacity of at least CAPACITY. The return value will be
- a bit-mask suitable for use as the "mask" member of struct
- hmap, that is, a power of 2 minus 1 (including 0). */
-static size_t
-capacity_to_mask (size_t capacity)
+/* Returns the highest "shift" value that allow for a hash table capacity of at
+ least CAPACITY. The return value will be between 2 and HMAP_MAX_SHIFT,
+ inclusive. */
+static int
+capacity_to_shift (size_t capacity)
{
- /* Calculate the minimum mask necesary to support the given
- capacity. */
- size_t mask = 0;
- while (hmap_mask_to_capacity__ (mask) < capacity)
- mask = (mask << 1) | 1;
+ int shift;
- /* If the mask is nonzero, make it at least 3, because there is
- little point in allocating an array of just 2 pointers. */
- mask |= (mask & 1) << 1;
+ for (shift = HMAP_MAX_SHIFT; shift > 2; shift--)
+ if (hmap_shift_to_capacity__ (shift) >= capacity)
+ break;
- return mask;
+ return shift;
}
projects / pspp / blobdiff