/* 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
}
*/
+#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
+static inline size_t
hmap_node_hash (const struct hmap_node *node)
{
return node->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.
: 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)
projects / pspp / blobdiff