HashTable in C

hashtable.c

#include <assert.h>
#include <stdlib.h>
#include <string.h>

#include "hashtable.h"


#include <stdio.h>


void ht_setup(struct HashTable* table, int capacity) {
	assert(table != NULL);

	if (capacity < HT_MINIMUM_CAPACITY) {
		capacity = HT_MINIMUM_CAPACITY;
	}

	ht_allocate(table, capacity);
	table->size = 0;
}

void ht_destroy(struct HashTable* table) {
	struct Node* node;
	struct Node* next;

	assert(table != NULL);

	for (int i = 0; i < table->capacity; ++i) {
		node = table->nodes[i];
		while (node) {
			next = node->next;
			free(node);
			node = next;
		}
	}

	free(table->nodes);
}

int ht_insert(struct HashTable* table, struct Connection* connection) {
	struct Node* node;
	int index;

	assert(table != NULL);

	if (table->size == table->threshold) {
		ht_resize(table);
	}

	index = ht_hash(table, connection->segment_id);
	node = table->nodes[index];

	for (; node; node = node->next) {
		if (ht_id(node) == connection->segment_id) {
			node->connection = *connection;
			return HT_UPDATED;
		}
	}

	node = ht_create_node(connection, table->nodes[index]);
	table->nodes[index] = node;

	++table->size;

	return HT_INSERTED;
}

struct Connection* ht_get(struct HashTable* table, int id) {
	struct Node* node;
	int index;

	assert(table != NULL);

	index = ht_hash(table, id);
	node = table->nodes[index];

	for (; node; node = node->next) {
		if (ht_id(node) == id) {
			return &node->connection;
		}
	}

	return NULL;
}

int ht_remove(struct HashTable* table, int id) {
	struct Node* node;
	struct Node* previous;
	int index;

	assert(table != NULL);

	index = ht_hash(table, id);
	node = table->nodes[index];

	for (previous = NULL; node; previous = node, node = node->next) {
		if (ht_id(node) == id) {
			if (previous) {
				previous->next = node->next;
			} else {
				table->nodes[index] = node->next;
			}

			free(node);

			if (--table->size == table->threshold / 4) {
				ht_resize(table);
			}

			return HT_OK;
		}
	}

	return HT_NOT_FOUND;
}

void ht_clear(struct HashTable* table) {
	ht_destroy(table);
	ht_allocate(table, HT_MINIMUM_CAPACITY);
	table->size = 0;
}

int ht_is_empty(struct HashTable* table) {
	return table->size == 0;
}

void ht_allocate(struct HashTable* table, int capacity) {
	int bytes;

	bytes = sizeof(struct Node*) * capacity;
	table->nodes = (struct Node**)malloc(bytes);
	memset(table->nodes, 0, bytes);

	table->capacity = capacity;
	table->threshold = capacity * HT_LOAD_FACTOR;
}

struct Node* ht_create_node(struct Connection* connection, struct Node* next) {
	struct Node* node = (struct Node*)malloc(sizeof(struct Node));

	node->connection = *connection;
	node->next = next;

	return node;
}

int ht_hash(struct HashTable* table, int id) {
	const int a = 69;
	const int b = 99;
	const int p = 123;

	return (((a * id) + b) % p) % table->capacity;
}

void ht_resize(struct HashTable* table) {
	int old_capacity = table->capacity;
	int new_capacity = table->size * 2;

	if (new_capacity < HT_MINIMUM_CAPACITY) return;

	struct Node** old = table->nodes;

	ht_allocate(table, new_capacity);
	ht_rehash(table, old, old_capacity);

	free(old);
}

void ht_rehash(struct HashTable* table, struct Node** old, int old_capacity) {
	struct Node* node;
	struct Node* next;
	int new_index;
	int i;

	for (i = 0; i < old_capacity; ++i) {
		for (node = old[i]; node;) {
			next = node->next;

			new_index = ht_hash(table, ht_id(node));
			node->next = table->nodes[new_index];
			table->nodes[new_index] = node;

			node = next;
		}
	}
}

int ht_id(struct Node* node) {
	return node->connection.segment_id;
}

hashtable.h

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include "connection.h"

#define HT_MINIMUM_CAPACITY 8
#define HT_LOAD_FACTOR 5

#define HT_UPDATED 0
#define HT_INSERTED 1

#define HT_NOT_FOUND 0
#define HT_OK 1

struct Node {
	struct Connection connection;

	struct Node* next;
};

struct HashTable {
	int size;
	int threshold;
	int capacity;

	// The node table
	struct Node** nodes;
};

void ht_setup(struct HashTable* table, int capacity);
void ht_destroy(struct HashTable* table);

int ht_insert(struct HashTable* table, struct Connection* connection);
struct Connection* ht_get(struct HashTable* table, int id);

int ht_remove(struct HashTable* table, int id);
void ht_clear(struct HashTable* table);

int ht_is_empty(struct HashTable* table);

/***** PRIVATE *****/

void ht_allocate(struct HashTable* table, int capacity);

struct Node* ht_create_node(struct Connection* connection, struct Node* next);

int ht_hash(struct HashTable* table, int id);

void ht_resize(struct HashTable* table);

void ht_rehash(struct HashTable* table, struct Node** old, int old_capacity);

int ht_id(struct Node* node);

#endif /* HASHTABLE_H */