+/* 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