//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){};
}
Dict dic = {};
dictPut(&dic, "one", 1);
dictPut(&dic, "two", 2);
//no such key: take the default value instead
int *found = dictGet(&dic, "three");
int value3 = found != nullptr ? *found : 0;
//value3 is 0
//or put the default value into the dictionary
if (dictGet(&dic, "three") == nullptr) {
dictPut(&dic, "three", 0);
}
//dic is {"one": 1, "three": 0, "two": 2}
printf("value3 is %d\n", value3);
dictPrint("dic", &dic);
dictFree(&dic);