Created
June 28, 2020 13:30
-
-
Save abel0b/7cf1cc62f5b53771d379856adff2ca6d to your computer and use it in GitHub Desktop.
Simple dictionary / hash table implementation in C
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include "dict.h" | |
#include <stdlib.h> | |
#include <string.h> | |
#include <stdio.h> | |
static int NUMBUCKETS = 8; | |
static int INITBUCKETCAPACITY = 8; | |
void dict_new(struct Dict* dict) { | |
dict->numbuckets = NUMBUCKETS; | |
dict->sizes = malloc(sizeof(dict->sizes[0]) * dict->numbuckets); | |
memset(dict->sizes, 0, sizeof(dict->sizes[0]) * dict->numbuckets); | |
dict->capacities = malloc(sizeof(dict->capacities[0]) * dict->numbuckets); | |
memset(dict->capacities, 0, sizeof(dict->capacities[0]) * dict->numbuckets); | |
dict->buckets = NULL; | |
} | |
static int hash(struct Dict* dict, char* key) { | |
int hashval = 0; | |
for(; *key != '\0'; ++ key) { | |
hashval += *key * 11; | |
} | |
return hashval % dict->numbuckets; | |
} | |
void dict_set(struct Dict* dict, char* key, void* value) { | |
int bucketid = hash(dict, key); | |
if (!dict->buckets) dict->buckets = malloc(sizeof(dict->buckets[0]) * dict->numbuckets); | |
if (!dict->capacities[bucketid]) { | |
dict->capacities[bucketid] = INITBUCKETCAPACITY; | |
dict->buckets[bucketid] = malloc(sizeof(dict->buckets[0][0]) * dict->capacities[bucketid]); | |
} | |
else if (dict->capacities[bucketid] == dict->sizes[bucketid]) { | |
dict->capacities[bucketid] *= 2; | |
dict->buckets[bucketid] = realloc(dict->buckets[bucketid], sizeof(dict->buckets[0][0]) * dict->capacities[bucketid]); | |
} | |
dict->buckets[bucketid][dict->sizes[bucketid]].key = key; | |
dict->buckets[bucketid][dict->sizes[bucketid]].value = value; | |
++ dict->sizes[bucketid]; | |
} | |
void * dict_get(struct Dict* dict, char* key) { | |
int bucketid = hash(dict, key); | |
for(int ii = 0; ii < dict->sizes[bucketid]; ++ ii) { | |
if (strcmp(key, dict->buckets[bucketid][ii].key) == 0) { | |
return dict->buckets[bucketid][ii].value; | |
} | |
} | |
return NULL; | |
} | |
void dict_del(struct Dict* dict) { | |
for(int ii = 0; ii < dict->numbuckets; ++ ii) { | |
if (dict->capacities[ii]) free(dict->buckets[ii]); | |
} | |
free(dict->buckets); | |
free(dict->sizes); | |
free(dict->capacities); | |
} | |
void dict_display(struct Dict* dict) { | |
for(int ii = 0; ii < dict->numbuckets; ++ ii) { | |
if (dict->sizes[ii]) { | |
for(int jj = 0; jj < dict->sizes[ii]; ++ jj) { | |
printf("%s => %p\n", dict->buckets[ii][jj].key, dict->buckets[ii][jj].value); | |
} | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#ifndef DICT__H | |
#define DICT__H | |
struct DictEntry { | |
char * key; | |
void * value; | |
}; | |
struct Dict { | |
int numbuckets; | |
struct DictEntry** buckets; | |
int * sizes; | |
int * capacities; | |
}; | |
void dict_new(struct Dict* dict); | |
void dict_set(struct Dict* dict, char * key, void * value); | |
void * dict_get(struct Dict* dict, char * key); | |
void dict_display(struct Dict* dict); | |
void dict_del(struct Dict* dict); | |
#endif |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment