/* PSPP - a program for statistical analysis.
- Copyright (C) 2008 Free Software Foundation, Inc.
+ Copyright (C) 2008, 2009, 2010, 2011, 2012 Free Software Foundation, Inc.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
hmap_init (&map);
or, alternatively:
struct hmap map = HMAP_INITIALIZER (map);
-
+
Each node in the hash table, presumably a structure type, must
include a struct hmap_node member. Here's an example:
struct foo
}
*/
+#include <stdbool.h>
#include <stddef.h>
+#include "libpspp/cast.h"
/* Returns the data structure corresponding to the given NODE,
assuming that NODE is embedded as the given MEMBER name in
data type STRUCT. NODE must not be a null pointer. */
#define HMAP_DATA(NODE, STRUCT, MEMBER) \
- ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
+ (CHECK_POINTER_HAS_TYPE (NODE, struct hmap_node *), \
+ UP_CAST (NODE, STRUCT, MEMBER))
/* Like HMAP_DATA, except that a null NODE yields a null pointer
result. */
/* Creation and destruction. */
void hmap_init (struct hmap *);
void hmap_swap (struct hmap *, struct hmap *);
+void hmap_clear (struct hmap *);
void hmap_destroy (struct hmap *);
/* Storage management. */
const struct hmap_node *);
/* Counting. */
+static bool hmap_is_empty (const struct hmap *);
static inline size_t hmap_count (const struct hmap *);
static inline size_t hmap_capacity (const struct hmap *);
: 0); \
(DATA) = (NEXT))
+/* These macros are like the *_WITH_HASH macros above, except that they don't
+ skip data elements that are in the same hash bucket but have different hash
+ values. This is a small optimization in code where comparing keys is just
+ as fast as comparing hashes (e.g. the key is an "int") or comparing keys
+ would duplicate comparing the hashes (e.g. the hash is the first word of a
+ multi-word random key).
+
+ These macros evaluate HASH only once. They evaluate their
+ other arguments many times. */
+#define HMAP_FIRST_IN_BUCKET(STRUCT, MEMBER, HMAP, HASH) \
+ HMAP_NULLABLE_DATA (hmap_first_in_bucket (HMAP, HASH), STRUCT, MEMBER)
+#define HMAP_NEXT_IN_BUCKET(DATA, STRUCT, MEMBER) \
+ HMAP_NULLABLE_DATA (hmap_next_in_bucket (&(DATA)->MEMBER), STRUCT, MEMBER)
+#define HMAP_FOR_EACH_IN_BUCKET(DATA, STRUCT, MEMBER, HASH, HMAP) \
+ for ((DATA) = HMAP_FIRST_IN_BUCKET (STRUCT, MEMBER, HMAP, HASH); \
+ (DATA) != NULL; \
+ (DATA) = HMAP_NEXT_IN_BUCKET (DATA, STRUCT, MEMBER))
+#define HMAP_FOR_EACH_IN_BUCKET_SAFE(DATA, NEXT, STRUCT, MEMBER, HASH, HMAP) \
+ for ((DATA) = HMAP_FIRST_IN_BUCKET (STRUCT, MEMBER, HMAP, HASH); \
+ ((DATA) != NULL \
+ ? ((NEXT) = HMAP_NEXT_IN_BUCKET (DATA, STRUCT, MEMBER), 1) \
+ : 0); \
+ (DATA) = (NEXT))
+
/* Convenience macros for iteration.
These macros automatically use HMAP_DATA to obtain the data
static inline size_t hmap_mask_to_capacity__ (size_t mask);
/* Returns the hash value associated with NODE. */
-size_t
-hmap_node_hash (const struct hmap_node *node)
+static inline size_t
+hmap_node_hash (const struct hmap_node *node)
{
return node->hash;
}
interface to this particular function that is often more
convenient. */
static inline struct hmap_node *
-hmap_next_with_hash (const struct hmap_node *node)
+hmap_next_with_hash (const struct hmap_node *node)
{
return hmap_find_hash__ (node->next, node->hash);
}
then the client must check for duplicates itself before
inserting the new node. */
static inline void
-hmap_insert_fast (struct hmap *map, struct hmap_node *node, size_t hash)
+hmap_insert_fast (struct hmap *map, struct hmap_node *node, size_t hash)
{
struct hmap_node **bucket = &map->buckets[hash & map->mask];
node->hash = hash;
map->count++;
}
+/* Returns the first node in MAP in the bucket for HASH, or a null pointer if
+ that bucket in HASH is empty.
+
+ This function runs in constant time.
+
+ Nodes are returned in arbitrary order that may change whenever the hash
+ table's current capacity changes, as reported by hmap_capacity(). Calls to
+ hmap_insert(), hmap_reserve(), and hmap_shrink() can change the capacity of
+ a hash map. Inserting a node with hmap_insert_fast() or deleting one with
+ hmap_delete() will not change the relative ordering of nodes.
+
+ The HMAP_FOR_EACH_IN_BUCKET and HMAP_FOR_EACH_IN_BUCKET_SAFE macros provide
+ convenient ways to iterate over all the nodes with a given hash. The
+ HMAP_FIRST_IN_BUCKET macro is an interface to this particular function that
+ is often more convenient. */
+static inline struct hmap_node *
+hmap_first_in_bucket (const struct hmap *map, size_t hash)
+{
+ return map->buckets[hash & map->mask];
+}
+
+/* Returns the next node following NODE within the same bucket, or a null
+ pointer if NODE is the last node in its bucket.
+
+ This function runs in constant time.
+
+ Nodes are returned in arbitrary order that may change whenever the hash
+ table's current capacity changes, as reported by hmap_capacity(). Calls to
+ hmap_insert(), hmap_reserve(), and hmap_shrink() can change the capacity of
+ a hash map. Inserting a node with hmap_insert_fast() or deleting one with
+ hmap_delete() will not change the relative ordering of nodes.
+
+ The HMAP_FOR_EACH_IN_BUCKET and HMAP_FOR_EACH_IN_BUCKET_SAFE macros provide
+ convenient ways to iterate over all the nodes with a given hash. The
+ HMAP_NEXT_IN_BUCKET macro is an interface to this particular function that
+ is often more convenient. */
+static inline struct hmap_node *
+hmap_next_in_bucket (const struct hmap_node *node)
+{
+ return node->next;
+}
+
/* Removes NODE from MAP. The client is responsible for freeing
any data associated with NODE, if necessary.
The HMAP_FIRST macro is an interface to this particular
function that is often more convenient. */
static inline struct hmap_node *
-hmap_first (const struct hmap *map)
+hmap_first (const struct hmap *map)
{
return hmap_first_nonempty_bucket__ (map, 0);
}
The HMAP_NEXT macro is an interface to this particular
function that is often more convenient. */
static inline struct hmap_node *
-hmap_next (const struct hmap *map, const struct hmap_node *node)
+hmap_next (const struct hmap *map, const struct hmap_node *node)
{
return (node->next != NULL
? node->next
: hmap_first_nonempty_bucket__ (map, (node->hash & map->mask) + 1));
}
+/* Returns true if MAP currently contains no data items, false
+ otherwise. */
+static inline bool
+hmap_is_empty (const struct hmap *map)
+{
+ return map->count == 0;
+}
+
/* Returns the number of data items currently in MAP. */
static inline size_t
-hmap_count (const struct hmap *map)
+hmap_count (const struct hmap *map)
{
return map->count;
}
capacity. However, inserting many more elements than the
map's capacity will degrade search performance. */
static inline size_t
-hmap_capacity (const struct hmap *map)
+hmap_capacity (const struct hmap *map)
{
return hmap_mask_to_capacity__ (map->mask);
}
/* Returns the first node at or after NODE in NODE's chain that
has hash value HASH. */
static inline struct hmap_node *
-hmap_find_hash__ (struct hmap_node *node, size_t hash)
+hmap_find_hash__ (struct hmap_node *node, size_t hash)
{
- for (; node != NULL; node = node->next)
+ for (; node != NULL; node = node->next)
if (node->hash == hash)
break;
return node;
MASK must be a power of 2 minus 1 (including 0), that is, its
value in binary must be all 1-bits. */
static inline size_t
-hmap_mask_to_capacity__ (size_t mask)
+hmap_mask_to_capacity__ (size_t mask)
{
return (mask + 1) * 2;
}
argument more than once). */
static inline void *
hmap_nullable_data__ (struct hmap_node *node, size_t member_offset)
-{
+{
return node != NULL ? (char *) node - member_offset : NULL;
}
projects / pspp / blobdiff