X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Fhmap.h;h=c1004d380ced5a8abc14a18e35fb56c52b89489f;hb=c520ca964de11d794d830630b24c97ad9a6de0ce;hp=e73d84fd153764ec96935c6242dc2388820c5757;hpb=b5c82cc9aabe7e641011130240ae1b2e84348e23;p=pspp diff --git a/src/libpspp/hmap.h b/src/libpspp/hmap.h index e73d84fd15..c1004d380c 100644 --- a/src/libpspp/hmap.h +++ b/src/libpspp/hmap.h @@ -1,5 +1,5 @@ /* 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 @@ -59,7 +59,7 @@ 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 @@ -115,13 +115,16 @@ } */ +#include #include +#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. */ @@ -155,6 +158,7 @@ struct hmap /* 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. */ @@ -180,6 +184,7 @@ static inline struct hmap_node *hmap_next (const struct hmap *, 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 *); @@ -212,6 +217,30 @@ void hmap_moved (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 @@ -243,8 +272,8 @@ static inline struct hmap_node *hmap_first_nonempty_bucket__ ( 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; } @@ -304,7 +333,7 @@ hmap_first_with_hash (const struct hmap *map, size_t 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); } @@ -343,7 +372,7 @@ hmap_insert (struct hmap *map, struct hmap_node *node, size_t 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; @@ -352,6 +381,48 @@ hmap_insert_fast (struct hmap *map, struct hmap_node *node, size_t 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. @@ -405,7 +476,7 @@ hmap_delete (struct hmap *map, struct hmap_node *node) 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); } @@ -433,16 +504,24 @@ hmap_first (const struct hmap *map) 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; } @@ -456,7 +535,7 @@ hmap_count (const struct hmap *map) 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); } @@ -466,9 +545,9 @@ hmap_capacity (const struct hmap *map) /* 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; @@ -493,7 +572,7 @@ hmap_first_nonempty_bucket__ (const struct hmap *map, size_t start) 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; } @@ -502,7 +581,7 @@ hmap_mask_to_capacity__ (size_t mask) 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; }