Playing with hash tables.

hashtable.c

#include <malloc.h>
#include <stdio.h>
#include <string.h>
#include <readline/readline.h>
#include <readline/history.h>

typedef struct HashNode {
	struct HashNode *next;
	char *key;
	char *value;
} HashNode;

typedef struct HashTable {
	HashNode **buckets;
	size_t numBuckets;
} HashTable;

HashTable *
hash_new(size_t numBuckets)
{
	HashTable *hash = malloc(sizeof *hash);

	if (hash != NULL) {
		hash->buckets = calloc(numBuckets, sizeof hash->buckets[0]);
		hash->numBuckets = numBuckets;

		if (hash->buckets == NULL) {
			free(hash);
			hash = NULL;
		}
	}

	return hash;
}

unsigned int
hash_string(HashTable *hash, const char *key)
{
	unsigned int value = 0;

	while (*key != '\0') {
		value += *key++;
	}

	return value % hash->numBuckets;
}

HashNode **
hash_find_node(HashTable *hash, const char *key)
{
	HashNode **node = &hash->buckets[hash_string(hash, key)];

	while ((*node) != NULL) {
		if (strcmp((*node)->key, key) == 0) {
			return node;;
		}
			
		node = &(*node)->next;
	}

	return node;
}

const char *
hash_get(HashTable *hash, const char *key)
{
	HashNode **node = hash_find_node(hash, key);

	if (*node != NULL) {
		return (*node)->value;
	}

	return NULL;
}

int
hash_put(HashTable *hash, const char *key, const char *value)
{
	HashNode **node = hash_find_node(hash, key);
	char *value_copy = strdup(value);

	if (value_copy == NULL) {
		return 0;
	}

	if (*node != NULL) {
		free((*node)->value);
		(*node)->value = value_copy;
	} else {
		char *key_copy = strdup(key);

		if (key_copy == NULL) {
			free(value_copy);
			return 0;
		}
		
		*node = calloc(1, sizeof **node);
		if (*node == NULL) {
			free(key_copy);
			free(value_copy);
			return 0;
		}

		(*node)->key = key_copy;
		(*node)->value = value_copy;
	}

	return 1;
}

int
hash_remove(HashTable *hash, const char *key)
{
	HashNode **node = hash_find_node(hash, key);

	if (*node != NULL) {
		HashNode *next = (*node)->next;

		free((*node)->key);
		free((*node)->value);
		free(*node);
		*node = next;
		return 1;
	}

	return 0;
}

void
hash_print(HashTable *hash)
{
	size_t i;

	for (i = 0; i < hash->numBuckets; i++) {
		HashNode *node = hash->buckets[i];

		printf("Bucket %lu:\n", i);

		while (node != NULL) {
			printf("  %s: %s\n", node->key, node->value);
			node = node->next;
		}
	}
}

int
main(int argc, char **argv)
{
	HashTable *hash = hash_new(8);
	char *line;

	if (hash == NULL) {
		printf("Out of memory.\n");
		return 1;
	}

	while ((line = readline("> ")) != NULL) {
		char *cmd;

		cmd = strtok(line, " ");

		if (cmd == NULL) {
			goto next;
		} else if (strcmp(cmd, "put") == 0) {
			char *key = strtok(NULL, " ");
			char *value = strtok(NULL, " ");

			if (key == NULL || value == NULL) {
				printf("Usage: put <key> <value>\n");
				goto next;
			}

			if (!hash_put(hash, key, value)) {
				printf("Out of memory.\n");
			}
		} else if (strcmp(cmd, "get") == 0) {
			char *key = strtok(NULL, " ");
			const char *value;

			if (key == NULL) {
				printf("Usage: get <key>\n");
				goto next;
			}

			value = hash_get(hash, key);
			if (value == NULL) {
				printf("Unknown key.\n");
			} else {
				printf("%s\n", value);
			}
		} else if (strcmp(cmd, "remove") == 0) {
			char *key = strtok(NULL, " ");

			if (key == NULL) {
				printf("Usage: remove <key>\n");
				goto next;
			}

			if (!hash_remove(hash, key)) {
				printf("No such key.\n");
			}
		} else if (strcmp(cmd, "print") == 0) {
			hash_print(hash);
		} else if (strcmp(cmd, "quit") == 0) {
			free(line);
			break;
		} else {
			printf("Unknown command.\n");
			goto next;
		}

	next:
		free(line);
	}

	return 0;
}