This is a C module useful for implementing hash maps in C, where all the keys are a single type and all the values are a single type. Its advantages include:
However, like C++'s std::map, it has the disadvantage of generating code for each different set of parameters (key type, value type, hash function, key equality function) that you wish to construct a hash map of.
Here is some abbreviated sample code using it (download full listing here):
#include "hash.h"
/* Maps str to a number >= 0 and < hash_size */
int hash_string(const char* str, const int hash_size) {
...
}
int string_equal(const char* str1, const char* str2) {
return strcmp(str1, str2) == 0;
}
DECLARE_HASH(string_int, char*, int)
DEFINE_HASH(string_int, char*, int, hash_string, string_equal)
int main(void) {
char buffer[256]; /* Prestring would be better */
string_int_hash map = string_int_hash_new();
for(;;) {
fgets(buffer, 256, stdin);
if (buffer[0] == '?') {
/* Get count of line in rest of buffer from hash */
int* pcount = string_int_hash_get(map, buffer + 1);
/* If it gave NULL, line wasn't in hash, so count is zero */
int count = pcount == NULL ? 0 : *pcount;
printf("%d occurrence%s seen\n", count, count==1 ? "" : "s");
continue;
}
else if (buffer[0] == '-') {
string_int_hash_remove(&map, buffer + 1);
puts("Removed");
continue;
}
/* Add to hash with count of 1 if not in hash, else increment */
if (string_int_hash_contains_key(map, buffer))
string_int_hash_set(&map, buffer, *string_int_hash_get(map, buffer) + 1);
else
string_int_hash_set(&map, strdup(buffer), 1);
}
/* Cleanup: Iterate over hash and free strdup'ed strings */
HASH_ITERATE(string_int, map, iter,
free(*string_int_hash_key(iter));
)
string_int_hash_clear(&map);
return 0;
}
Note that normally the DECLARE_HASH would
go in a header file.
In a header file, declare the key and value types you'll be using,
if necessary, and after those declarations, use
DECLARE_HASH, passing it the prefix to use for the new
hash types and functions, the key type, and the value type:
DECLARE_HASH(string_int, char *, int)
This sample declares the string_int_hash and
string_int_hash_iterator types, along with all
the functions for manipulating them. Then, in some source file, you
must define:
DEFINE_HASH, which
takes the same arguments as DECLARE_HASH, plus
the hash and equality function names.Once you've done this, you can then create this type of hash at any time
using prefix_hash_new(), where prefix is
the prefix you gave to DECLARE_HASH, eg:
string_int_hash map = string_int_hash_new();
When you are done with the hash, you must use
prefix_hash_clear() to free memory in use by the hash:
string_int_hash_clear(&map);
The initial hash is empty, as the predicate
prefix_hash_empty() can verify. If you know you will have
a certain number of elements, it may improve efficiency to call
prefix_hash_resize() ahead of time with an estimated
upper bound on the number of elements you will enter:
string_int_hash_resize(&map, 200);
Use prefix_hash_set(hash, key, value) to associate a
particular value with a particular key, which adds the key-value pair
to the hash if it is not present, or replaces the existing associated
value if it is. You can later retrieve a pointer to the associated
value for a specific key using prefix_hash_get(hash,
key):
string_int_hash_set(&map, "fred", 2); /* hash now { fred=>2 } */
string_int_hash_set(&map, "doug", 5); /* hash now { fred=>2, doug=>5 } */
string_int_hash_set(&map, "fred", 11); /* hash now { fred=>11, doug=>5 } */
int* pfred = string_int_hash_get(map, "fred"); /* *pfred == 11 */
int* pdoug = string_int_hash_get(map, "doug"); /* *pdoug == 5 */
int* piggy = string_int_hash_get(map, "iggy"); /* piggy == NULL */
To test whether a certain key is in the hash table, use
prefix_hash_contains_key():
string_int_hash_contains_key(map, "doug"); /* Returns nonzero */ string_int_hash_contains_key(map, "iggy"); /* Returns zero */
To remove a key-value pair with a certain key, use
string_int_hash_remove:
string_int_has_remove(&map, "fred"); /* hash now { doug=>5 } */
If you're a lazy typer, feel free to define short-term macros:
#define set(k,v) string_int_hash_set(&map, (k), (v))
#define get(k) string_int_hash_get(map, (k))
set("fred", 2);
set("doug", 5);
set("fred", 11);
int* pfred = get("fred");
int* pdoug = get("doug");
int* piggy = get("iggy");
#undef get
#undef set
The easiest way to iterate over the key-value pairs in a hash is using
HASH_ITERATE, which takes four arguments:
DECLARE_HASHIn the body of the loop, the supplied iterator is visible,
which can be used with prefix_hash_key and
prefix_hash_value to get the key or
value from the current pair. The keywords break
and continue also work as expected, and you
can remove hash items using their iterator with
prefix_hash_remove_iterator, but note that
this advances the iterator:
HASH_ITERATE(string_int, map, iter,
char* key = *string_int_hash_key(iter);
int value = *string_int_hash_value(iter);
printf("%s => %d\n", key, value);
if (value == 5) {
string_int_hash_remove_iterator(&iter);
break;
}
)
You can also directly access iterators, for finer control.
Use prefix_hash_first to get an iterator positioned
on the first key-value pair, use prefix_hash_next to
advance it to the next pair, and use prefix_hash_done
to test if the iterator has advanced beyond the end of the hash.
Thus, the above sample could be written out as:
string_int_hash_iterator iter =
string_int_hash_first(&map);
while (!string_int_hash_done(iter)) {
char* key = *string_int_hash_key(iter);
int value = *string_int_hash_value(iter);
printf("%s => %d\n", key, value);
if (value == 5) {
string_int_hash_remove_iterator(&iter);
break;
}
string_int_hash_next(&iter);
}
None yet, but mail me if you come up with a cool use.
The implementation is contained in hash.h, and requires list.h. For a sample, see hash-test.c. The archive hash.tar.gz contains all of these.
hash.tar.gz
hash.h
(view html)
list.h
(view html)
hash-test.c
(view html)