X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Fhmap.h;h=c1004d380ced5a8abc14a18e35fb56c52b89489f;hb=8180c5dd1591446174c0753ee960921786113403;hp=095edf104674ba0af56b2a2da7d0bb4687807c0d;hpb=f550aee00a62fe1d8baf62d83cd7efef6cc2ee92;p=pspp diff --git a/src/libpspp/hmap.h b/src/libpspp/hmap.h index 095edf1046..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, 2009, 2010 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 @@ -117,7 +117,7 @@ #include #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 @@ -217,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 @@ -248,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; } @@ -309,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); } @@ -348,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; @@ -357,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. @@ -410,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); } @@ -438,7 +504,7 @@ 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 @@ -455,7 +521,7 @@ hmap_is_empty (const struct hmap *map) /* 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; } @@ -469,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); } @@ -479,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; @@ -506,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; } @@ -515,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; }