| /* |
| ** C implementation of a hash table ADT |
| */ |
| typedef enum tagReturnCode {SUCCESS, FAIL} ReturnCode; |
| |
| |
| typedef struct tagEntry |
| { |
| char* key; |
| char* value; |
| } Entry; |
| |
| |
| |
| typedef struct tagNode |
| { |
| Entry* entry; |
| |
| struct tagNode* next; |
| } Node; |
| |
| |
| typedef struct tagHash |
| { |
| unsigned int table_size; |
| |
| Node** heads; |
| |
| } Hash; |
| |
| |
| static unsigned int hash_func(const char* str, unsigned int table_size) |
| { |
| unsigned int hash_value; |
| unsigned int a = 127; |
| |
| for (hash_value = 0; *str != 0; ++str) |
| hash_value = (a*hash_value + *str) % table_size; |
| |
| return hash_value; |
| } |
| |
| |
| ReturnCode HashCreate(Hash** hash, unsigned int table_size) |
| { |
| unsigned int i; |
| |
| if (table_size < 1) |
| return FAIL; |
| |
| // |
| // Allocate space for the Hash |
| // |
| if (((*hash) = malloc(sizeof(**hash))) == NULL) |
| return FAIL; |
| |
| // |
| // Allocate space for the array of list heads |
| // |
| if (((*hash)->heads = malloc(table_size*sizeof(*((*hash)->heads)))) == NULL) |
| return FAIL; |
| |
| // |
| // Initialize Hash info |
| // |
| for (i = 0; i < table_size; ++i) |
| { |
| (*hash)->heads[i] = NULL; |
| } |
| |
| (*hash)->table_size = table_size; |
| |
| return SUCCESS; |
| } |
| |
| |
| ReturnCode HashInsert(Hash* hash, const Entry* entry) |
| { |
| unsigned int index = hash_func(entry->key, hash->table_size); |
| Node* temp = hash->heads[index]; |
| |
| HashRemove(hash, entry->key); |
| |
| if ((hash->heads[index] = malloc(sizeof(Node))) == NULL) |
| return FAIL; |
| |
| hash->heads[index]->entry = malloc(sizeof(Entry)); |
| hash->heads[index]->entry->key = malloc(strlen(entry->key)+1); |
| hash->heads[index]->entry->value = malloc(strlen(entry->value)+1); |
| strcpy(hash->heads[index]->entry->key, entry->key); |
| strcpy(hash->heads[index]->entry->value, entry->value); |
| |
| hash->heads[index]->next = temp; |
| |
| return SUCCESS; |
| } |
| |
| |
| |
| const Entry* HashFind(const Hash* hash, const char* key) |
| { |
| unsigned int index = hash_func(key, hash->table_size); |
| Node* temp = hash->heads[index]; |
| |
| while (temp != NULL) |
| { |
| if (!strcmp(key, temp->entry->key)) |
| return temp->entry; |
| |
| temp = temp->next; |
| } |
| |
| return NULL; |
| } |
| |
| |
| ReturnCode HashRemove(Hash* hash, const char* key) |
| { |
| unsigned int index = hash_func(key, hash->table_size); |
| Node* temp1 = hash->heads[index]; |
| Node* temp2 = temp1; |
| |
| while (temp1 != NULL) |
| { |
| if (!strcmp(key, temp1->entry->key)) |
| { |
| if (temp1 == hash->heads[index]) |
| hash->heads[index] = hash->heads[index]->next; |
| else |
| temp2->next = temp1->next; |
| |
| free(temp1->entry->key); |
| free(temp1->entry->value); |
| free(temp1->entry); |
| free(temp1); |
| temp1 = NULL; |
| |
| return SUCCESS; |
| } |
| |
| temp2 = temp1; |
| temp1 = temp1->next; |
| } |
| |
| return FAIL; |
| } |
| |
| |
| void HashPrint(Hash* hash, void (*PrintFunc)(char*, char*)) |
| { |
| unsigned int i; |
| |
| if (hash == NULL || hash->heads == NULL) |
| return; |
| |
| for (i = 0; i < hash->table_size; ++i) |
| { |
| Node* temp = hash->heads[i]; |
| |
| while (temp != NULL) |
| { |
| PrintFunc(temp->entry->key, temp->entry->value); |
| temp = temp->next; |
| } |
| } |
| } |
| |
| |
| |
| void HashDestroy(Hash* hash) |
| { |
| unsigned int i; |
| |
| if (hash == NULL) |
| return; |
| |
| for (i = 0; i < hash->table_size; ++i) |
| { |
| Node* temp = hash->heads[i]; |
| |
| while (temp != NULL) |
| { |
| Node* temp2 = temp; |
| |
| free(temp->entry->key); |
| free(temp->entry->value); |
| free(temp->entry); |
| |
| temp = temp->next; |
| |
| free(temp2); |
| } |
| } |
| |
| free(hash->heads); |
| hash->heads = NULL; |
| |
| free(hash); |
| } |
| |