ccousas

hash_table.c (4834B)

---

 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
 #define TABLE_SIZE 5
 
 typedef struct ENTRY {
     char* key;
     char* value;
     struct ENTRY* sig;
 } ENTRY_T;
 
 typedef struct {
     ENTRY_T** entries;
 } HTABLE_T;
 
 
 
 HTABLE_T* htable_init() {
     HTABLE_T* hashtable = malloc(sizeof(HTABLE_T)); // Allocate HashTable
     hashtable->entries = calloc(TABLE_SIZE, sizeof(ENTRY_T)); // Allocate entries
 
     // Set each entry to NULL (needed for proper operation)
     for (int i = 0; i < TABLE_SIZE; i++) {
         hashtable->entries[i] = NULL;
     }
 
     return hashtable;
 }
 
 
 
 unsigned int hash(const char* key) {
     unsigned long int value = 0;
 
     for (unsigned int i = 0; i < strlen(key); i++){
         value = value * 37 + key[i];
     }
     value = value % TABLE_SIZE;
     return value;
 }
 
 
 
 // Inicializa un nodo entry
 ENTRY_T* htable_pair(const char* key, const char* value){
     // Allocate the entry
     ENTRY_T* entry = malloc(sizeof(entry));
     entry->key = malloc(strlen(key)+1); // +1 polo NULL TERMINATOR '\0'
     entry->value = malloc(strlen(value) + 1);
 
     // Copy the key and value in place
     strcpy(entry->key, key);
     strcpy(entry->value, value);
 
     // sig (seguinte) starts out NULL but may be set later on
     entry->sig = NULL;
     return entry;
 }
 
 
 void htable_set (HTABLE_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] = htable_pair(key, value);
         return;
     }
 
     // Mira se estas intentando introducir unha clave que xa tes no hashTable para actualizala
     ENTRY_T* prev;
     while (entry != NULL) {
         // Comproba
         if (!strcmp(entry->key, key)) {
             // Update value
             free(entry->value);
             entry->value = malloc(strlen(value) + 1);
             strcpy(entry->value, value);
             return;
         }
 
         // walk to next
         prev = entry;
         entry = prev->sig;
     }
 
     // End of node list reached -> add new element
     prev->sig = htable_pair(key, value);
 }
 
 
 // Devolve NULL senon existe
 char* htable_get(HTABLE_T* hashtable, const char* key) {
     unsigned int slot = hash(key);
 
     // Try to find a valid slot
     ENTRY_T* entry = hashtable->entries[slot];
 
     // No slot means no entry
     if (entry == NULL) return NULL;
 
     // Walk through each entry in the slot, which could just be a single thing
     while (entry != NULL) {
         // Return a value if found
         if (!strcmp(entry->key, key) == 0) {
             return entry->value;
         }
 
         // Proceed to next key if available
         entry = entry->sig;
     }
 
     // Reaching here means there were >= 1 entries but no key match
     return NULL;
 }
 
 
 void htable_remove(HTABLE_T* hashtable, const char* key) {
     unsigned int slot = hash(key);
     // Try to find a valid slot
     ENTRY_T* entry = hashtable->entries[slot];
     ENTRY_T** tmp = &(hashtable->entries[slot]);
     if (entry == NULL) return;
 
     // Se esta na cabeza e ten sig deixas o sig a cabeza
     // Senon ten sig borraslle a cabeza
     if (!strcmp(entry->key, key)) {
         if (entry->sig == NULL) {
             hashtable->entries[slot] = NULL;
             free(entry);
         }
         else {
             hashtable->entries[slot] = entry->sig;
             free(entry);
         }
     }
     else {
         ENTRY_T* aux;
         while (*tmp != NULL) {
             if (!strcmp((*tmp)->key, key)) {
                 // Borrar a entry
                 aux = *tmp;
                 *tmp = (*tmp)->sig;
                 return;
             }
             tmp = &((*tmp)->sig);
         }
     }
     return;
 }
 
 
 void htable_print(HTABLE_T* hashtable) {
     for (int i = 0; i < TABLE_SIZE; i++) {
         ENTRY_T* entry = hashtable->entries[i];
 
         if (entry == NULL) continue;
 
         printf("slot[%4d]: ", i);
         for(;;) {
             printf("%s=%s ", entry->key, entry->value);
 
             if(entry->sig == NULL) break;
             entry = entry->sig;
         }
 
         printf("\n");
     }
 }
 
 
 
 int main() {
     HTABLE_T* ht = htable_init();
 
     htable_set(ht, "name1", "em");
     htable_set(ht, "name2", "russian");
     htable_set(ht, "name3", "pizza");
     htable_set(ht, "name4", "doge");
     htable_set(ht, "name5", "pyro");
     htable_set(ht, "name6", "joost");
     htable_set(ht, "name7", "kalix");
     htable_set(ht, "name8", "lemon");
     htable_set(ht, "name9", "lollipop");
     htable_set(ht, "name10", "oreo");
     htable_set(ht, "name11", "apache");
     htable_set(ht, "name12", "fanta");
     htable_set(ht, "name13", "kake");
     htable_set(ht, "name14", "tuna");
     htable_set(ht, "name15", "presunto");
 
     htable_remove(ht, "name7");
     htable_remove(ht, "name2");
 
     htable_print(ht);
     return 0;
 }