#include #include #include #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) struct hmap_entry { unsigned int hash; void *data; struct hmap_entry *next; }; struct hashmap { struct hmap_entry **table; unsigned int tablesize; unsigned int num_entries; float max_load_factor; float min_load_factor; }; struct hashmap_iter { struct hashmap *hmap; struct hmap_entry *next; void *entry; unsigned int key; unsigned int pos; }; /* A hash function vaguely based on K&R's hash. */ static unsigned int strhash(const char *s) { unsigned int hash = 5477; char c; while ((c = *s++)) hash = ((hash << 5) + hash) + (c ^ 7); return hash; } static unsigned int inthash(unsigned int x) { x = ((x >> 16) ^ x) * 0x45d9f3b; x = ((x >> 16) ^ x) * 0x45d9f3b; x = ((x >> 16) ^ x); return x; } static int hashmap_create(struct hashmap *hmap, unsigned int init_size) { hmap->table = calloc(init_size, sizeof(*hmap->table)); if (!hmap->table) return 0; hmap->tablesize = init_size; hmap->num_entries = 0; hmap->max_load_factor = 0.72f; hmap->min_load_factor = 0.20f; return 1; } static unsigned int hashmap_bucket(const struct hashmap *hmap, unsigned int hash) { return hash & (hmap->tablesize - 1); } static int hashmap_rehash(struct hashmap *hmap, unsigned int new_size) { struct hmap_entry **new_table = calloc(new_size, sizeof(*hmap->table)); unsigned int i, old_size = hmap->tablesize; /* Allocation failure */ if (!new_table) return 0; /* * Assign the new size so we can pass the hashmap * to hashmap_bucket(). */ hmap->tablesize = new_size; for (i = 0; i < old_size; i++) { struct hmap_entry *entry = hmap->table[i]; /* Rehash all the elements */ while (entry) { unsigned int pos = hashmap_bucket(hmap, entry->hash); struct hmap_entry *next = entry->next; entry->next = new_table[pos]; new_table[pos] = entry; entry = next; } } free(hmap->table); hmap->table = new_table; return 1; } static int hashmap_put(struct hashmap *hmap, unsigned int hash, void *data) { unsigned int pos = hashmap_bucket(hmap, hash); struct hmap_entry *entry = hmap->table[pos]; float load_factor = 0.0f; while (entry) { if (hash == entry->hash) { entry->data = (void *)data; return 1; } entry = entry->next; } entry = malloc(sizeof(*entry)); if (!entry) return 0; entry->hash = hash; entry->data = data; entry->next = hmap->table[pos]; hmap->table[pos] = entry; /* Grow the hashmap if the current load-factor exceeds the max load-factor. */ load_factor = (float)hmap->num_entries++ / hmap->tablesize; if (load_factor >= hmap->max_load_factor) hashmap_rehash(hmap, hmap->tablesize << 1); return 0; } static void *hashmap_lookup(struct hashmap *hmap, unsigned int hash) { struct hmap_entry *entry = hmap->table[hashmap_bucket(hmap, hash)]; while (entry && hash != entry->hash) entry = entry->next; return entry ? entry->data : NULL; } static void *hashmap_remove(struct hashmap *hmap, unsigned int hash) { struct hmap_entry **entry = &hmap->table[hashmap_bucket(hmap, hash)]; void *ret = NULL; float load_factor = 0.0f; while (*entry) { if (hash == (*entry)->hash) { struct hmap_entry *next = (*entry)->next; ret = (*entry)->data; free(*entry); (*entry) = next; break; } entry = &(*entry)->next; } load_factor = (float)--hmap->num_entries / hmap->tablesize; if (load_factor < hmap->min_load_factor) hashmap_rehash(hmap, hmap->tablesize >> 1); return ret; } static void hashmap_free(struct hashmap *hmap) { unsigned int pos = 0; for ( ; pos < hmap->tablesize; pos++) { struct hmap_entry *entry = hmap->table[pos]; while (entry) { struct hmap_entry *next = entry->next; free(entry); entry = next; } } free(hmap->table); memset(hmap, 0, sizeof(*hmap)); } static unsigned int hashmap_get_num_entries(const struct hashmap *hmap) { return hmap->num_entries; } static unsigned int hashmap_get_size(const struct hashmap *hmap) { return hmap->tablesize; } static void hashmap_iter_init(struct hashmap_iter *iter, struct hashmap *hmap) { iter->hmap = hmap; iter->next = iter->entry = NULL; iter->key = iter->pos = 0; } static void *hashmap_iter_next(struct hashmap_iter *iter) { struct hmap_entry *curr = iter->next; for (;;) { if (curr) { iter->next = curr->next; iter->entry = curr->data; iter->key = curr->hash; return curr->data; } if (iter->pos >= iter->hmap->tablesize) { iter->pos = 0; return NULL; } curr = iter->hmap->table[iter->pos++]; } } #define hashmap_dump_str(iter, hmap) \ do { \ while (hashmap_iter_next(&iter)) { \ const char **ds = iter.entry; \ printf("Hashmap Entry: %-15s hash: %-8u bucket: %u\n", \ *ds, iter.key, iter.pos); \ } \ printf("\tHashmap size: %-6u\tNum Entries: %u\n", \ hashmap_get_size(&hmap), \ hashmap_get_num_entries(&hmap)); \ } while (0) #define hashmap_dump_int(iter, hmap) \ do { \ while (hashmap_iter_next(&iter)) { \ unsigned int num = *(unsigned int *)iter.entry; \ printf("Hashmap Entry: %-12u hash: %-12u bucket: %u\n", \ num, iter.key, iter.pos); \ } \ printf("\tHashmap size: %-6u\tNum Entries: %u\n", \ hashmap_get_size(&hmap), \ hashmap_get_num_entries(&hmap)); \ } while (0) #define print_separator(col, c) \ do { \ int len = (col); \ while (len-- && putchar(c)); \ putchar('\n'); \ } while (0) #define print_header(msg, len) \ do { \ print_separator((len), '_'); \ puts(msg); \ print_separator((len), '_'); \ } while (0) static void try_hashmap_of_strint(void) { struct hashmap hmap; struct hashmap_iter iter; unsigned int i; struct kv_pair { const char *key; int data; } *rm, *kvp_ptr, kvp[] = { { "", 23 }, { "", 24 }, { "", 9 }, { "", 14 }, { "", 23 }, { "", 50 }, { "", 11 }, { "", 27 } }; if (!hashmap_create(&hmap, 4)) { fputs("Hashmap allocation failure.\n", stderr); return; } for (i = 0; i < ARRAY_SIZE(kvp); i++) hashmap_put(&hmap, strhash(kvp[i].key), &kvp[i]); rm = hashmap_lookup(&hmap, strhash("Mana344")); if (rm) printf("FOUND: Key: %s Data: %d\n", rm->key, rm->data); else puts("Could not find Mana344!"); hashmap_iter_init(&iter, &hmap); while (hashmap_iter_next(&iter)) { kvp_ptr = iter.entry; printf("Key: %s Data: %d\n", kvp_ptr->key, kvp_ptr->data); } hashmap_free(&hmap); } static void try_hashmap_of_intint(void) { struct hashmap hmap; struct hashmap_iter iter; unsigned int i, *rm, numbers[] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288 }; if (!hashmap_create(&hmap, 8)) { fputs("Hashmap allocation failure!\n", stderr); return; } printf("\t[FILLED] Hashmap size: %-6u\tNum Entries: %u\n", hashmap_get_size(&hmap), hashmap_get_num_entries(&hmap)); for (i = 0; i < ARRAY_SIZE(numbers); i++) { unsigned int hash = inthash(numbers[i]); printf("[Inserted]: int with hash: %u%c", hash, i & 1 ? '\n' : ' '); hashmap_put(&hmap, hash, &numbers[i]); } hashmap_iter_init(&iter, &hmap); while (hashmap_iter_next(&iter)) { unsigned int num = *(unsigned int *)iter.entry; unsigned int hash = iter.key; unsigned int bk = iter.pos; printf("Entry: %-6u %-12u\tBucket: %-6u\n", num, hash, bk); } /* Remove value 64 from the hashmap. */ rm = hashmap_remove(&hmap, inthash(64)); if (rm) puts("Removed value 64!"); else puts("Failed to remove value 64!"); rm = hashmap_remove(&hmap, inthash(32)); if (rm) puts("Removed value 32!"); else puts("Failed to remove value 32!"); hashmap_dump_int(iter, hmap); printf("\t[FILLED] Hashmap size: %-6u\tNum Entries: %u\n", hashmap_get_size(&hmap), hashmap_get_num_entries(&hmap)); hashmap_free(&hmap); } static void try_hashmap_of_strstr(void) { struct hashmap hmap; struct hashmap_iter iter; unsigned int i; const char **rm, **s, *distro[] = { "Canonical", "Ubuntu", "Redhat", "Fedora", "Deepin", "Deepin OS", "FSF", "Trisquel", "Novell", "OpenSUSE", "BSD", "OpenBSD" }; if (!hashmap_create(&hmap, 8)) { fputs("Hashmap allocation failure!\n", stderr); return; } printf("[Unfilled]: Hashmap size; %u\tnum_entries: %u\n", hashmap_get_size(&hmap), hashmap_get_num_entries(&hmap)); for (i = 0; i < ARRAY_SIZE(distro)-1; i += 2) hashmap_put(&hmap, strhash(distro[i]), &distro[i+1]); printf("[Filled]: Hashmap size; %u\tnum_entries: %u\n", hashmap_get_size(&hmap), hashmap_get_num_entries(&hmap)); puts("\nValues in hashmap:"); hashmap_iter_init(&iter, &hmap); hashmap_dump_str(iter, hmap); puts("\nValues in hashmap:"); hashmap_dump_str(iter, hmap); hashmap_free(&hmap); } int main(void) { print_header("\nHASHMAP OF KEY-VALUE PAIR: {STR, INT}:", 40); try_hashmap_of_strint(); print_header("\nHASHMAP OF KEY-VALUE PAIR: {INT, INT}:", 40); try_hashmap_of_intint(); print_header("\nHASHMAP OF KEY-VALUE PAIR: {STR, STR}:", 40); try_hashmap_of_strstr(); return 0; }

[Data Structures] : Generic Hashmap in C