diff options
Diffstat (limited to 'hashtable.c')
-rw-r--r-- | hashtable.c | 439 |
1 files changed, 0 insertions, 439 deletions
diff --git a/hashtable.c b/hashtable.c deleted file mode 100644 index c365acb3c75e..000000000000 --- a/hashtable.c +++ /dev/null @@ -1,439 +0,0 @@ -#include <assert.h> -#include <stdlib.h> -#include <string.h> - - -#include <stdio.h> - - -#include "hashtable.h" - -int ht_setup(HashTable* table, - size_t key_size, - size_t value_size, - size_t capacity) { - assert(table != NULL); - - if (table == NULL) return HT_ERROR; - - if (capacity < HT_MINIMUM_CAPACITY) { - capacity = HT_MINIMUM_CAPACITY; - } - - if (_ht_allocate(table, capacity) == HT_ERROR) { - return HT_ERROR; - } - - table->key_size = key_size; - table->value_size = value_size; - table->hash = _ht_default_hash; - table->compare = _ht_default_compare; - table->size = 0; - - return HT_SUCCESS; -} - -int ht_copy(HashTable* first, HashTable* second) { - size_t chain; - HTNode* node; - - assert(first != NULL); - assert(ht_is_initialized(second)); - - if (first == NULL) return HT_ERROR; - if (!ht_is_initialized(second)) return HT_ERROR; - - if (_ht_allocate(first, second->capacity) == HT_ERROR) { - return HT_ERROR; - } - - first->key_size = second->key_size; - first->value_size = second->value_size; - first->hash = second->hash; - first->compare = second->compare; - first->size = second->size; - - for (chain = 0; chain < second->capacity; ++chain) { - for (node = second->nodes[chain]; node; node = node->next) { - if (_ht_push_front(first, chain, node->key, node->value) == HT_ERROR) { - return HT_ERROR; - } - } - } - - return HT_SUCCESS; -} - -int ht_move(HashTable* first, HashTable* second) { - assert(first != NULL); - assert(ht_is_initialized(second)); - - if (first == NULL) return HT_ERROR; - if (!ht_is_initialized(second)) return HT_ERROR; - - *first = *second; - second->nodes = NULL; - - return HT_SUCCESS; -} - -int ht_swap(HashTable* first, HashTable* second) { - assert(ht_is_initialized(first)); - assert(ht_is_initialized(second)); - - if (!ht_is_initialized(first)) return HT_ERROR; - if (!ht_is_initialized(second)) return HT_ERROR; - - _ht_int_swap(&first->key_size, &second->key_size); - _ht_int_swap(&first->value_size, &second->value_size); - _ht_int_swap(&first->size, &second->size); - _ht_pointer_swap((void**)&first->hash, (void**)&second->hash); - _ht_pointer_swap((void**)&first->compare, (void**)&second->compare); - _ht_pointer_swap((void**)&first->nodes, (void**)&second->nodes); - - return HT_SUCCESS; -} - -int ht_destroy(HashTable* table) { - HTNode* node; - HTNode* next; - size_t chain; - - assert(ht_is_initialized(table)); - if (!ht_is_initialized(table)) return HT_ERROR; - - for (chain = 0; chain < table->capacity; ++chain) { - node = table->nodes[chain]; - while (node) { - next = node->next; - _ht_destroy_node(node); - node = next; - } - } - - free(table->nodes); - - return HT_SUCCESS; -} - -int ht_insert(HashTable* table, void* key, void* value) { - size_t index; - HTNode* node; - - assert(ht_is_initialized(table)); - assert(key != NULL); - - if (!ht_is_initialized(table)) return HT_ERROR; - if (key == NULL) return HT_ERROR; - - if (_ht_should_grow(table)) { - _ht_adjust_capacity(table); - } - - index = _ht_hash(table, key); - for (node = table->nodes[index]; node; node = node->next) { - if (_ht_equal(table, key, node->key)) { - memcpy(node->value, value, table->value_size); - return HT_UPDATED; - } - } - - if (_ht_push_front(table, index, key, value) == HT_ERROR) { - return HT_ERROR; - } - - ++table->size; - - return HT_INSERTED; -} - -int ht_contains(HashTable* table, void* key) { - size_t index; - HTNode* node; - - assert(ht_is_initialized(table)); - assert(key != NULL); - - if (!ht_is_initialized(table)) return HT_ERROR; - if (key == NULL) return HT_ERROR; - - index = _ht_hash(table, key); - for (node = table->nodes[index]; node; node = node->next) { - if (_ht_equal(table, key, node->key)) { - return HT_FOUND; - } - } - - return HT_NOT_FOUND; -} - -void* ht_lookup(HashTable* table, void* key) { - HTNode* node; - size_t index; - - assert(table != NULL); - assert(key != NULL); - - if (table == NULL) return NULL; - if (key == NULL) return NULL; - - index = _ht_hash(table, key); - for (node = table->nodes[index]; node; node = node->next) { - if (_ht_equal(table, key, node->key)) { - return node->value; - } - } - - return NULL; -} - -const void* ht_const_lookup(const HashTable* table, void* key) { - const HTNode* node; - size_t index; - - assert(table != NULL); - assert(key != NULL); - - if (table == NULL) return NULL; - if (key == NULL) return NULL; - - index = _ht_hash(table, key); - for (node = table->nodes[index]; node; node = node->next) { - if (_ht_equal(table, key, node->key)) { - return node->value; - } - } - - return NULL; -} - -int ht_erase(HashTable* table, void* key) { - HTNode* node; - HTNode* previous; - size_t index; - - assert(table != NULL); - assert(key != NULL); - - if (table == NULL) return HT_ERROR; - if (key == NULL) return HT_ERROR; - - index = _ht_hash(table, key); - node = table->nodes[index]; - - for (previous = NULL; node; previous = node, node = node->next) { - if (_ht_equal(table, key, node->key)) { - if (previous) { - previous->next = node->next; - } else { - table->nodes[index] = node->next; - } - - _ht_destroy_node(node); - --table->size; - - if (_ht_should_shrink(table)) { - if (_ht_adjust_capacity(table) == HT_ERROR) { - return HT_ERROR; - } - } - - return HT_SUCCESS; - } - } - - return HT_NOT_FOUND; -} - -int ht_clear(HashTable* table) { - assert(table != NULL); - assert(table->nodes != NULL); - - if (table == NULL) return HT_ERROR; - if (table->nodes == NULL) return HT_ERROR; - - ht_destroy(table); - _ht_allocate(table, HT_MINIMUM_CAPACITY); - table->size = 0; - - return HT_SUCCESS; -} - -int ht_is_empty(HashTable* table) { - assert(table != NULL); - if (table == NULL) return HT_ERROR; - return table->size == 0; -} - -bool ht_is_initialized(HashTable* table) { - return table != NULL && table->nodes != NULL; -} - -int ht_reserve(HashTable* table, size_t minimum_capacity) { - assert(ht_is_initialized(table)); - if (!ht_is_initialized(table)) return HT_ERROR; - - /* - * We expect the "minimum capacity" to be in elements, not in array indices. - * This encapsulates the design. - */ - if (minimum_capacity > table->threshold) { - return _ht_resize(table, minimum_capacity / HT_LOAD_FACTOR); - } - - return HT_SUCCESS; -} - -/****************** PRIVATE ******************/ - -void _ht_int_swap(size_t* first, size_t* second) { - size_t temp = *first; - *first = *second; - *second = temp; -} - -void _ht_pointer_swap(void** first, void** second) { - void* temp = *first; - *first = *second; - *second = temp; -} - -int _ht_default_compare(void* first_key, void* second_key, size_t key_size) { - return memcmp(first_key, second_key, key_size); -} - -size_t _ht_default_hash(void* raw_key, size_t key_size) { - // djb2 string hashing algorithm - // sstp://www.cse.yorku.ca/~oz/hash.ssml - size_t byte; - size_t hash = 5381; - char* key = raw_key; - - for (byte = 0; byte < key_size; ++byte) { - // (hash << 5) + hash = hash * 33 - hash = ((hash << 5) + hash) ^ key[byte]; - } - - return hash; -} - -size_t _ht_hash(const HashTable* table, void* key) { -#ifdef HT_USING_POWER_OF_TWO - return table->hash(key, table->key_size) & table->capacity; -#else - return table->hash(key, table->key_size) % table->capacity; -#endif -} - -bool _ht_equal(const HashTable* table, void* first_key, void* second_key) { - return table->compare(first_key, second_key, table->key_size) == 0; -} - -bool _ht_should_grow(HashTable* table) { - assert(table->size <= table->capacity); - return table->size == table->capacity; -} - -bool _ht_should_shrink(HashTable* table) { - assert(table->size <= table->capacity); - return table->size == table->capacity * HT_SHRINK_THRESHOLD; -} - -HTNode* -_ht_create_node(HashTable* table, void* key, void* value, HTNode* next) { - HTNode* node; - - assert(table != NULL); - assert(key != NULL); - assert(value != NULL); - - if ((node = malloc(sizeof *node)) == NULL) { - return NULL; - } - if ((node->key = malloc(table->key_size)) == NULL) { - return NULL; - } - if ((node->value = malloc(table->value_size)) == NULL) { - return NULL; - } - - memcpy(node->key, key, table->key_size); - memcpy(node->value, value, table->value_size); - node->next = next; - - return node; -} - -int _ht_push_front(HashTable* table, size_t index, void* key, void* value) { - table->nodes[index] = _ht_create_node(table, key, value, table->nodes[index]); - return table->nodes[index] == NULL ? HT_ERROR : HT_SUCCESS; -} - -void _ht_destroy_node(HTNode* node) { - assert(node != NULL); - - free(node->key); - free(node->value); - free(node); -} - -int _ht_adjust_capacity(HashTable* table) { - return _ht_resize(table, table->size * HT_GROWTH_FACTOR); -} - -int _ht_allocate(HashTable* table, size_t capacity) { - if ((table->nodes = malloc(capacity * sizeof(HTNode*))) == NULL) { - return HT_ERROR; - } - memset(table->nodes, 0, capacity * sizeof(HTNode*)); - - table->capacity = capacity; - table->threshold = capacity * HT_LOAD_FACTOR; - - return HT_SUCCESS; -} - -int _ht_resize(HashTable* table, size_t new_capacity) { - HTNode** old; - size_t old_capacity; - - if (new_capacity < HT_MINIMUM_CAPACITY) { - if (table->capacity > HT_MINIMUM_CAPACITY) { - new_capacity = HT_MINIMUM_CAPACITY; - } else { - /* NO-OP */ - return HT_SUCCESS; - } - } - - old = table->nodes; - old_capacity = table->capacity; - if (_ht_allocate(table, new_capacity) == HT_ERROR) { - return HT_ERROR; - } - - _ht_rehash(table, old, old_capacity); - - free(old); - - return HT_SUCCESS; -} - -void _ht_rehash(HashTable* table, HTNode** old, size_t old_capacity) { - HTNode* node; - HTNode* next; - size_t new_index; - size_t chain; - - for (chain = 0; chain < old_capacity; ++chain) { - for (node = old[chain]; node;) { - next = node->next; - - new_index = _ht_hash(table, node->key); - node->next = table->nodes[new_index]; - table->nodes[new_index] = node; - - node = next; - } - } -} |