/* Hash table functions. */ #include "headers.h" void hash_table_new( HashTable* const restrict ht, const u64 number_of_linked_lists, const u64 max_amount_of_items_in_a_linked_list, const f64 multiplication_amount ) { assert_comparison(ht, !=, NULL); assert_comparison(number_of_linked_lists, >, 0); assert_comparison(max_amount_of_items_in_a_linked_list, >, 0); assert_comparison(multiplication_amount, >, 0.000001); /* This hash table class uses lazy initial allocation. */ ht->linked_lists = NULL; ht->allocated_length = number_of_linked_lists; ht->length = 0; ht->max_amount_of_items_in_a_linked_list = max_amount_of_items_in_a_linked_list; ht->multiplication_amount = multiplication_amount; } static u64 hash_u64(HashTable* const restrict ht, const u64 key) { return key % ht->allocated_length; } /* The hash function. */ __attribute__((nonnull)) static u64 hash_string(HashTable* const restrict ht, const char* key, u64 length_of_key) { u64 number, additional_amount; assert_comparison(ht, !=, NULL); assert_comparison(key, !=, NULL); number = 1; additional_amount = 0; while (length_of_key--) { /* The number 171121 was chosen randomly, but it works well. */ number *= (key[length_of_key] + (additional_amount += 171121)); } return hash_u64(ht, number); } static u64 hash_appropriately_depending_on_type_of_key(HashTable* const restrict ht, const TypeUnion key, const u64 length_of_key, const HashType type_of_key) { if (type_of_key == HASH_TYPE_UINT) { return hash_u64(ht, key.u64_value); } return hash_string(ht, key.string_value, length_of_key); } __attribute__((nonnull)) static void hash_table_insert_for_resize(HashTable* ht, TypeUnion key, u64 length_of_key, HashType type_of_key, void* value) { HashItem *item, *new_head; u64 hash; assert_comparison(ht, !=, NULL); assert_comparison(key.string_value, !=, NULL); assert_comparison(value, !=, NULL); hash = hash_appropriately_depending_on_type_of_key(ht, key, length_of_key, type_of_key); for (item = ht->linked_lists[hash]; item; item = item->next) { /* If the key is already in the hash table... */ if (strnequal(key.string_value, item->key.string_value, length_of_key, item->length_of_key)) { /* set the value to the new value and return the new value. */ item->value = value; } } /* Create a new node... */ new_head = (HashItem*)m_alloc(sizeof(HashItem)); new_head->key = key; new_head->length_of_key = length_of_key; new_head->type_of_key = type_of_key; new_head->value = value; new_head->next = ht->linked_lists[hash]; /* and set it to be the head of the linked list. */ ht->linked_lists[hash] = new_head; } __attribute__((nonnull)) static void hash_table_resize(HashTable* ht) { u64 old_allocated_length; HashItem** old_linked_lists; assert_comparison(ht, !=, NULL); old_allocated_length = ht->allocated_length; old_linked_lists = ht->linked_lists; ht->linked_lists = (HashItem**)m_zero_initialized_alloc(ht->allocated_length * sizeof(HashItem*)); if (ht->linked_lists) { ht->allocated_length *= ht->multiplication_amount; } else { /* Can't allocate such a big block, so try a smaller one. */ f64 i; for (i = ht->allocated_length / 2.0; i > 1.0; i /= 2.0) { ht->linked_lists = (HashItem**)m_zero_initialized_alloc(ht->allocated_length * sizeof(HashItem*) * i); } ht->allocated_length *= i; ht->multiplication_amount = 0; } while (old_allocated_length--) { HashItem* item; for (item = old_linked_lists[old_allocated_length]; item;) { HashItem* next_item = item->next; hash_table_insert_for_resize(ht, item->key, item->length_of_key, item->type_of_key, item->value); m_free(item); item = next_item; } } m_free(old_linked_lists); } __attribute__((nonnull)) static bool hash_table_insert(HashTable* const restrict ht, TypeUnion key, HashType type_of_key, u64 length_of_key, void* value, const bool replace) { HashItem *item, *new_head; u64 hash, times; assert_comparison(ht, !=, NULL); assert_comparison(type_of_key == HASH_TYPE_UINT || key.string_value, !=, 0); assert_comparison(value, !=, NULL); hash = hash_appropriately_depending_on_type_of_key(ht, key, length_of_key, type_of_key); times = 0; if (!ht->linked_lists) { ht->linked_lists = (HashItem**)m_zero_initialized_alloc(ht->allocated_length * sizeof(HashItem*)); } for (item = ht->linked_lists[hash]; item; item = item->next) { if (times == ht->max_amount_of_items_in_a_linked_list) { ht->max_amount_of_items_in_a_linked_list += 10; #if DEBUG output_nullt_string("(in hash_table_insert()) resize from "); output_u64(ht->allocated_length); output_nullt_string(" to "); output_u64(ht->allocated_length * ht->multiplication_amount); output_nullt_string(".\n"); #endif hash_table_resize(ht); hash_table_insert_for_resize(ht, key, length_of_key, type_of_key, value); ++ht->length; return true; } if (type_of_key == HASH_TYPE_UINT && item->type_of_key == HASH_TYPE_UINT) { /* if the key is already in the hash table */ if (key.u64_value == item->key.u64_value) { if (replace) { item->key = key; item->value = value; return true; } else { return false; } } } else if (type_of_key == HASH_TYPE_UINT && item->type_of_key == HASH_TYPE_UINT) { /* if the key is already in the hash table */ if (strnequal(key.string_value, item->key.string_value, length_of_key, item->length_of_key)) { if (replace) { item->key = key; item->length_of_key = length_of_key; item->value = value; return true; } else { return false; } } } ++times; } /* Create a new node... */ new_head = (HashItem*)m_alloc(sizeof(HashItem)); new_head->key = key; new_head->length_of_key = length_of_key; new_head->type_of_key = type_of_key; new_head->value = value; new_head->next = ht->linked_lists[hash]; /* and set it to be the head of the linked list. */ ht->linked_lists[hash] = new_head; ++ht->length; return true; } bool hash_table_insert_string(HashTable* const restrict ht, char* key, const u64 length_of_key, void* value, const bool replace) { TypeUnion tu; tu.string_value = key; return hash_table_insert(ht, tu, HASH_TYPE_STRING, length_of_key, value, replace); } bool hash_table_insert_uint(HashTable* const restrict ht, const u64 key, void* value, const bool replace) { TypeUnion tu; tu.u64_value = key; return hash_table_insert(ht, tu, HASH_TYPE_UINT, 0, value, replace); } void** hash_table_get_value_with_string_key(HashTable* ht, const char* key, u64 length_of_key) { HashItem* item; u64 hash; static void* pointer_that_points_to_null = NULL; assert_comparison(ht, !=, NULL); assert_comparison(key, !=, NULL); /* If the hash table isn't allocated, there are no items in it; therefore, the key isn't in it. */ if (!ht->linked_lists) { return &pointer_that_points_to_null; } hash = hash_string(ht, key, length_of_key); for (item = ht->linked_lists[hash]; item; item = item->next) { /* If the key is in the hash table... */ if (item->type_of_key == HASH_TYPE_STRING && strnequal(key, item->key.string_value, length_of_key, item->length_of_key)) { /* then return the value. */ return &item->value; } } /* Otherwise, return the addresss of a static pointer that points to NULL. */ return &pointer_that_points_to_null; } void** hash_table_get_value_with_uint_key(HashTable* ht, u64 key) { HashItem* item; u64 hash; static void* pointer_that_points_to_null = NULL; assert_comparison(ht, !=, NULL); /* If the hash table isn't allocated, there are no items in it; therefore, the key isn't in it. */ if (!ht->linked_lists) { return &pointer_that_points_to_null; } hash = hash_u64(ht, key); for (item = ht->linked_lists[hash]; item; item = item->next) { /* If the key is in the hash table... */ if (item->type_of_key == HASH_TYPE_UINT && item->key.u64_value == item->key.u64_value) { /* then return the value. */ return &item->value; } } /* Otherwise, return the addresss of a static pointer that points to NULL. */ return &pointer_that_points_to_null; } void hash_iterator_init(HashTable* const restrict hash_table, HashIterator* const restrict hash_iterator) { assert_comparison(hash_table, !=, NULL); assert_comparison(hash_iterator, !=, NULL); hash_iterator->hash_table = hash_table; hash_iterator->current_hashitem = NULL; hash_iterator->how_far_in = (u64)-1; } bool /* not done iterating */ hash_iterator_next(HashIterator* const restrict iterator) { assert_comparison(iterator, !=, NULL); assert_comparison(iterator->hash_table, !=, NULL); /* If the hash table isn't allocated, there are zero items in it, and therefore we are done iterating. */ if (!iterator->hash_table->linked_lists) { return false; } while (1) { if (iterator->current_hashitem) { iterator->key = iterator->current_hashitem->key; iterator->length_of_key = iterator->current_hashitem->length_of_key; iterator->type_of_key = iterator->current_hashitem->type_of_key; iterator->value = &iterator->current_hashitem->value; iterator->current_hashitem = iterator->current_hashitem->next; return true; } else { ++iterator->how_far_in; if (iterator->how_far_in == iterator->hash_table->allocated_length) return false; iterator->current_hashitem = iterator->hash_table->linked_lists[iterator->how_far_in]; } } } void hash_table_del(HashTable* const restrict ht) { u64 i; assert_comparison(ht, !=, NULL); /* If the hash table isn't allocated, don't free it. */ if (!ht->linked_lists) return; i = ht->allocated_length; while (i--) { HashItem* item = ht->linked_lists[i]; while (item) { HashItem* next_item = item->next; m_free(item); item = next_item; } } m_free(ht->linked_lists); } /* Deletes the hash table and all the values contained therein. */ void hash_table_del_with_values(HashTable* const restrict ht, void (*value_deletion_function)(void*)) { u64 i; assert_comparison(ht, !=, NULL); /* If the hash table isn't allocated, don't free it. */ if (!ht->linked_lists) return; i = ht->allocated_length; while (i--) { HashItem* item = ht->linked_lists[i]; while (item) { HashItem* next_item = item->next; value_deletion_function(item->value); m_free(item->value); m_free(item); item = next_item; } } m_free(ht->linked_lists); }