Skip to content

Instantly share code, notes, and snippets.

@abel0b
Created June 28, 2020 13:30
Show Gist options
  • Save abel0b/7cf1cc62f5b53771d379856adff2ca6d to your computer and use it in GitHub Desktop.
Save abel0b/7cf1cc62f5b53771d379856adff2ca6d to your computer and use it in GitHub Desktop.
Simple dictionary / hash table implementation in C
#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);
}
}
}
}
#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