Last active
April 18, 2020 13:01
-
-
Save sidsbrmnn/611262f84998cdd1f50c2f2389dfeeb8 to your computer and use it in GitHub Desktop.
Hash table in C
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| #include <stdlib.h> | |
| #include <string.h> | |
| #define TABLE_SIZE 10000 | |
| typedef struct entry_t { | |
| char *key; | |
| char *value; | |
| struct entry_t *next; | |
| } entry_t; | |
| typedef struct { | |
| entry_t **entries; | |
| } ht_t; | |
| unsigned int hash(const char *key) { | |
| unsigned long int value = 0; | |
| unsigned int key_len = strlen(key); | |
| for (unsigned int i = 0; i < key_len; i++) { | |
| value = value * 37 + key[i]; | |
| } | |
| value = value % TABLE_SIZE; | |
| return value; | |
| } | |
| ht_t *ht_create(void) { | |
| ht_t *hashtable = (ht_t *)malloc(sizeof(ht_t) * 1); | |
| hashtable->entries = calloc(TABLE_SIZE, sizeof(entry_t *)); | |
| return hashtable; | |
| } | |
| entry_t *ht_pair(const char *key, const char *value) { | |
| entry_t *entry = malloc(sizeof(entry_t) * 1); | |
| entry->key = malloc(strlen(key) + 1); | |
| entry->value = malloc(strlen(value) + 1); | |
| strcpy(entry->key, key); | |
| strcpy(entry->value, value); | |
| entry->next = NULL; | |
| return entry; | |
| } | |
| const char *ht_get(ht_t *hashtable, const char *key) { | |
| unsigned int slot = hash(key); | |
| entry_t *entry = hashtable->entries[slot]; | |
| if (entry == NULL) { | |
| return NULL; | |
| } | |
| while (entry != NULL) { | |
| if (strcmp(entry->key, key) == 0) { | |
| return entry->value; | |
| } | |
| entry = entry->next; | |
| } | |
| return NULL; | |
| } | |
| void ht_set(ht_t *hashtable, const char *key, const char *value) { | |
| unsigned int slot = hash(key); | |
| entry_t *entry = hashtable->entries[slot]; | |
| if (entry == NULL) { | |
| hashtable->entries[slot] = ht_pair(key, value); | |
| return; | |
| } | |
| entry_t *prev; | |
| while (entry != NULL) { | |
| if (strcmp(entry->key, key) == 0) { | |
| free(entry->value); | |
| entry->value = malloc(sizeof(value) + 1); | |
| strcpy(entry->value, value); | |
| return; | |
| } | |
| prev = entry; | |
| entry = entry->next; | |
| } | |
| prev->next = ht_pair(key, value); | |
| } | |
| void ht_del(ht_t *hashtable, const char *key) { | |
| unsigned int slot = hash(key); | |
| entry_t *entry = hashtable->entries[slot]; | |
| if (entry == NULL) { | |
| return; | |
| } | |
| entry_t *prev; | |
| int index = 0; | |
| while (entry != NULL) { | |
| if (strcmp(entry->key, key) == 0) { | |
| if (entry->next == NULL && index == 0) { | |
| hashtable->entries[slot] = NULL; | |
| } | |
| if (entry->next != NULL && index == 0) { | |
| hashtable->entries[slot] = entry->next; | |
| } | |
| if (entry->next == NULL && index != 0) { | |
| prev->next = NULL; | |
| } | |
| if (entry->next != NULL && index != 0) { | |
| prev->next = entry->next; | |
| } | |
| free(entry->key); | |
| free(entry->value); | |
| free(entry); | |
| return; | |
| } | |
| prev = entry; | |
| entry = entry->next; | |
| index++; | |
| } | |
| } | |
| void ht_dump(ht_t *hashtable) { | |
| for (int i = 0; i < TABLE_SIZE; ++i) { | |
| entry_t *entry = hashtable->entries[i]; | |
| if (entry == NULL) { | |
| continue; | |
| } | |
| printf("slot[%4d]: ", i); | |
| while (entry != NULL) { | |
| printf("%s=%s ", entry->key, entry->value); | |
| entry = entry->next; | |
| } | |
| printf("\n"); | |
| } | |
| } | |
| int main(int argc, char const **argv) { | |
| /* code */ | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment