diff options
Diffstat (limited to 'lib/hmap.h')
| -rw-r--r-- | lib/hmap.h | 254 |
1 files changed, 254 insertions, 0 deletions
diff --git a/lib/hmap.h b/lib/hmap.h new file mode 100644 index 000000000..7f4b00fc3 --- /dev/null +++ b/lib/hmap.h @@ -0,0 +1,254 @@ +/* + * Copyright (c) 2008, 2009 Nicira Networks. + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef HMAP_H +#define HMAP_H 1 + +#include <stdbool.h> +#include <stdlib.h> +#include "util.h" + +/* A hash map node, to be embedded inside the data structure being mapped. */ +struct hmap_node { + size_t hash; /* Hash value. */ + struct hmap_node *next; /* Next in linked list. */ +}; + +/* Returns the hash value embedded in 'node'. */ +static inline size_t hmap_node_hash(const struct hmap_node *node) +{ + return node->hash; +} + +/* A hash map. */ +struct hmap { + struct hmap_node **buckets; + struct hmap_node *one; + size_t mask; + size_t n; +}; + +/* Initializer for an empty hash map. */ +#define HMAP_INITIALIZER(HMAP) { &(HMAP)->one, NULL, 0, 0 } + +/* Initialization. */ +void hmap_init(struct hmap *); +void hmap_destroy(struct hmap *); +void hmap_swap(struct hmap *a, struct hmap *b); +static inline size_t hmap_count(const struct hmap *); +static inline bool hmap_is_empty(const struct hmap *); + +/* Adjusting capacity. */ +void hmap_expand(struct hmap *); +void hmap_shrink(struct hmap *); +void hmap_reserve(struct hmap *, size_t capacity); + +/* Insertion and deletion. */ +static inline void hmap_insert_fast(struct hmap *, + struct hmap_node *, size_t hash); +static inline void hmap_insert(struct hmap *, struct hmap_node *, size_t hash); +static inline void hmap_remove(struct hmap *, struct hmap_node *); +static inline void hmap_moved(struct hmap *, + struct hmap_node *, struct hmap_node *); +static inline void hmap_replace(struct hmap *, const struct hmap_node *old, + struct hmap_node *new); + +/* Search. */ +#define HMAP_FOR_EACH_WITH_HASH(NODE, STRUCT, MEMBER, HASH, HMAP) \ + for ((NODE) = CONTAINER_OF(hmap_first_with_hash(HMAP, HASH), \ + STRUCT, MEMBER); \ + &(NODE)->MEMBER != NULL; \ + (NODE) = CONTAINER_OF(hmap_next_with_hash(&(NODE)->MEMBER), \ + STRUCT, MEMBER)) + +static inline struct hmap_node *hmap_first_with_hash(const struct hmap *, + size_t hash); +static inline struct hmap_node *hmap_next_with_hash(const struct hmap_node *); + +/* Iteration. + * + * The _SAFE version is needed when NODE may be freed. It is not needed when + * NODE may be removed from the hash map but its members remain accessible and + * intact. */ +#define HMAP_FOR_EACH(NODE, STRUCT, MEMBER, HMAP) \ + for ((NODE) = CONTAINER_OF(hmap_first(HMAP), STRUCT, MEMBER); \ + &(NODE)->MEMBER != NULL; \ + (NODE) = CONTAINER_OF(hmap_next(HMAP, &(NODE)->MEMBER), \ + STRUCT, MEMBER)) + +#define HMAP_FOR_EACH_SAFE(NODE, NEXT, STRUCT, MEMBER, HMAP) \ + for ((NODE) = CONTAINER_OF(hmap_first(HMAP), STRUCT, MEMBER); \ + (&(NODE)->MEMBER != NULL \ + ? (NEXT) = CONTAINER_OF(hmap_next(HMAP, &(NODE)->MEMBER), \ + STRUCT, MEMBER), 1 \ + : 0); \ + (NODE) = (NEXT)) + +static inline struct hmap_node *hmap_first(const struct hmap *); +static inline struct hmap_node *hmap_next(const struct hmap *, + const struct hmap_node *); + +/* Returns the number of nodes currently in 'hmap'. */ +static inline size_t +hmap_count(const struct hmap *hmap) +{ + return hmap->n; +} + +/* Returns true if 'hmap' currently contains no nodes, + * false otherwise. */ +static inline bool +hmap_is_empty(const struct hmap *hmap) +{ + return hmap->n == 0; +} + +/* Inserts 'node', with the given 'hash', into 'hmap'. 'hmap' is never + * expanded automatically. */ +static inline void +hmap_insert_fast(struct hmap *hmap, struct hmap_node *node, size_t hash) +{ + struct hmap_node **bucket = &hmap->buckets[hash & hmap->mask]; + node->hash = hash; + node->next = *bucket; + *bucket = node; + hmap->n++; +} + +/* Inserts 'node', with the given 'hash', into 'hmap', and expands 'hmap' if + * necessary to optimize search performance. */ +static inline void +hmap_insert(struct hmap *hmap, struct hmap_node *node, size_t hash) +{ + hmap_insert_fast(hmap, node, hash); + if (hmap->n / 2 > hmap->mask) { + hmap_expand(hmap); + } +} + +/* Removes 'node' from 'hmap'. Does not shrink the hash table; call + * hmap_shrink() directly if desired. */ +static inline void +hmap_remove(struct hmap *hmap, struct hmap_node *node) +{ + struct hmap_node **bucket = &hmap->buckets[node->hash & hmap->mask]; + while (*bucket != node) { + bucket = &(*bucket)->next; + } + *bucket = node->next; + hmap->n--; +} + +/* Adjusts 'hmap' to compensate for 'old_node' having moved position in memory + * to 'node' (e.g. due to realloc()). */ +static inline void +hmap_moved(struct hmap *hmap, + struct hmap_node *old_node, struct hmap_node *node) +{ + struct hmap_node **bucket = &hmap->buckets[node->hash & hmap->mask]; + while (*bucket != old_node) { + bucket = &(*bucket)->next; + } + *bucket = node; +} + +/* Puts 'new' in the position in 'hmap' currently occupied by 'old'. The 'new' + * node must hash to the same value as 'old'. The client is responsible for + * ensuring that the replacement does not violate any client-imposed + * invariants (e.g. uniqueness of keys within a map). + * + * Afterward, 'old' is not part of 'hmap', and the client is responsible for + * freeing it (if this is desirable). */ +static inline void +hmap_replace(struct hmap *hmap, + const struct hmap_node *old, struct hmap_node *new) +{ + struct hmap_node **bucket = &hmap->buckets[old->hash & hmap->mask]; + while (*bucket != old) { + bucket = &(*bucket)->next; + } + *bucket = new; + new->hash = old->hash; +} + +static inline struct hmap_node * +hmap_next_with_hash__(const struct hmap_node *node, size_t hash) +{ + while (node != NULL && node->hash != hash) { + node = node->next; + } + return (struct hmap_node *) node; +} + +/* Returns the first node in 'hmap' with the given 'hash', or a null pointer if + * no nodes have that hash value. */ +static inline struct hmap_node * +hmap_first_with_hash(const struct hmap *hmap, size_t hash) +{ + return hmap_next_with_hash__(hmap->buckets[hash & hmap->mask], hash); +} + +/* Returns the next node in the same hash map as 'node' with the same hash + * value, or a null pointer if no more nodes have that hash value. + * + * If the hash map has been reallocated since 'node' was visited, some nodes + * may be skipped; if new nodes with the same hash value have been added, they + * will be skipped. (Removing 'node' from the hash map does not prevent + * calling this function, since node->next is preserved, although freeing + * 'node' of course does.) */ +static inline struct hmap_node * +hmap_next_with_hash(const struct hmap_node *node) +{ + return hmap_next_with_hash__(node->next, node->hash); +} + +static inline struct hmap_node * +hmap_next__(const struct hmap *hmap, size_t start) +{ + size_t i; + for (i = start; i <= hmap->mask; i++) { + struct hmap_node *node = hmap->buckets[i]; + if (node) { + return node; + } + } + return NULL; +} + +/* Returns the first node in 'hmap', in arbitrary order, or a null pointer if + * 'hmap' is empty. */ +static inline struct hmap_node * +hmap_first(const struct hmap *hmap) +{ + return hmap_next__(hmap, 0); +} + +/* Returns the next node in 'hmap' following 'node', in arbitrary order, or a + * null pointer if 'node' is the last node in 'hmap'. + * + * If the hash map has been reallocated since 'node' was visited, some nodes + * may be skipped or visited twice. (Removing 'node' from the hash map does + * not prevent calling this function, since node->next is preserved, although + * freeing 'node' of course does.) */ +static inline struct hmap_node * +hmap_next(const struct hmap *hmap, const struct hmap_node *node) +{ + return (node->next + ? node->next + : hmap_next__(hmap, (node->hash & hmap->mask) + 1)); +} + +#endif /* hmap.h */ |