//C has no dictionary: this is a small hash table
//with string keys and int values
constexpr int BUCKETS = 16;
typedef struct Entry {
char *key;
int value;
struct Entry *next;
} Entry;
typedef struct {
Entry *buckets[BUCKETS];
size_t count;
} Dict;
unsigned dictHash(const char *key) {
unsigned hash = 5381;
for (; *key != '\0'; key++) {
hash = hash * 33 + (unsigned char)*key;
}
return hash % BUCKETS;
}
//a pointer to the value, or nullptr if there is no such key
int *dictGet(Dict *d, const char *key) {
Entry *e = d->buckets[dictHash(key)];
while (e != nullptr && strcmp(e->key, key) != 0) {
e = e->next;
}
return e != nullptr ? &e->value : nullptr;
}
//adds the pair, or replaces the value of the key
void dictPut(Dict *d, const char *key, int value) {
int *old = dictGet(d, key);
if (old != nullptr) {
*old = value;
return;
}
unsigned bucket = dictHash(key);
Entry *e = malloc(sizeof *e);
*e = (Entry){strdup(key), value, d->buckets[bucket]};
d->buckets[bucket] = e;
d->count++;
}
//prints the pairs in the order of the buckets
void dictPrint(const char *name, const Dict *d) {
printf("%s is {", name);
const char *separator = "";
for (int i = 0; i < BUCKETS; i++) {
for (Entry *e = d->buckets[i]; e != nullptr; e = e->next) {
printf("%s\"%s\": %d", separator, e->key, e->value);
separator = ", ";
}
}
printf("}\n");
}
//frees every pair and leaves the dictionary empty
void dictFree(Dict *d) {
for (int i = 0; i < BUCKETS; i++) {
for (Entry *e = d->buckets[i], *next; e != nullptr; e = next) {
next = e->next;
free(e->key);
free(e);
}
}
*d = (Dict){};
}
//puts every pair of from into to: a repeated key takes the new value
void dictMerge(Dict *to, const Dict *from) {
for (int i = 0; i < BUCKETS; i++) {
for (Entry *e = from->buckets[i]; e != nullptr; e = e->next) {
dictPut(to, e->key, e->value);
}
}
}
Dict d1 = {};
dictPut(&d1, "one", 1);
Dict d2 = {};
dictPut(&d2, "two", 2);
Dict d3 = {};
dictPut(&d3, "three", 3);
dictPut(&d3, "one", 11);
Dict dAll = {};
dictMerge(&dAll, &d1);
dictMerge(&dAll, &d2);
//dAll is {"one": 1, "two": 2}
dictPrint("dAll", &dAll);
dictMerge(&dAll, &d3);
//dAll is {"one": 11, "three": 3, "two": 2}
dictPrint("dAll", &dAll);
dictFree(&d1);
dictFree(&d2);
dictFree(&d3);
dictFree(&dAll);