src/HashTable.c

   1 /**
   2  * @file HashTable.c
   3  */
   4
   5 #include "cgds/HashTable.h"
   6
   7 void _hashtable_init(HashTable* hashTable, size_t dataSize, size_t hashSize)
   8 {
   9     hashTable->hashSize = hashSize;
  10   hashTable->dataSize = dataSize;
  11     hashTable->head = safe_malloc(hashSize * sizeof(HashCell*));
  12     for (UInt i = 0; i < hashSize; i++)
  13     hashTable->head[i] = NULL;
  14   hashTable->size = 0;
  15 }
  16
  17 HashTable* _hashtable_new(size_t dataSize, size_t hashSize)
  18 {
  19     HashTable* hashTable = (HashTable*) safe_malloc(sizeof (HashTable));
  20     _hashtable_init(hashTable, dataSize, hashSize);
  21     return hashTable;
  22 }
  23
  24 HashTable* hashtable_copy(HashTable* hashTable)
  25 {
  26     HashTable* hashTableCopy =
  27     _hashtable_new(hashTable->dataSize, hashTable->hashSize);
  28     hashTableCopy->size = hashTable->size;
  29   for (UInt i = 0; i < hashTable->hashSize; i++)
  30     {
  31     HashCell *cell = hashTable->head[i],
  32              *cellCopy = hashTableCopy->head[i],
  33              *prev = NULL;
  34     while (cell != NULL)
  35     {
  36       // cellCopy == NULL (from empty list)
  37       cellCopy = (HashCell*) safe_malloc(sizeof(HashCell*));
  38           cellCopy->key = (char*) safe_malloc(strlen(cell->key) + 1);
  39       strcpy(cellCopy->key, cell->key);
  40           cellCopy->data = safe_malloc(hashTable->dataSize);
  41           memcpy(cellCopy->data, cell->data, hashTable->dataSize);
  42       if (prev == NULL) hashTableCopy->head[i] = cellCopy;
  43       else prev->next = cellCopy;
  44       prev = cellCopy;
  45       cell = cell->next;
  46     }
  47     if (cellCopy != NULL) cellCopy->next = NULL;
  48     }
  49     return hashTableCopy;
  50 }
  51
  52 bool hashtable_empty(HashTable* hashTable)
  53 {
  54     return (hashTable->size == 0);
  55 }
  56
  57 UInt hashtable_size(HashTable* hashTable)
  58 {
  59     return hashTable->size;
  60 }
  61
  62 // Function (string) key --> (integer) hash [internal usage]
  63 UInt _compute_hash(char* key, size_t hashSize)
  64 {
  65   UInt res = 0;
  66   for (unsigned char* s = key; *s != '\0'; s++)
  67     // NOTE: '31' from here https://stackoverflow.com/a/4384446
  68     res += *s + 31 * res;
  69   return res % hashSize;
  70 }
  71
  72 void* _hashtable_get(HashTable* hashTable, char* key)
  73 {
  74   UInt hashIdx = _compute_hash(key, hashTable->hashSize);
  75   HashCell* cell = hashTable->head[hashIdx];
  76   while (cell != NULL)
  77   {
  78     if (strcmp(cell->key, key) == 0) return cell->data;
  79     cell = cell->next;
  80   }
  81   return NULL;
  82 }
  83
  84 void _hashtable_set(HashTable* hashTable, char* key, void* data)
  85 {
  86   UInt hashIdx = _compute_hash(key, hashTable->hashSize);
  87   HashCell
  88     *cell = hashTable->head[hashIdx],
  89     *prev = NULL;
  90   while (cell != NULL)
  91   {
  92     if (strcmp(cell->key, key) == 0)
  93     {
  94       // Modify:
  95       memcpy(cell->data, data, hashTable->dataSize);
  96       return;
  97     }
  98     prev = cell;
  99     cell = cell->next;
 100   }
 101   // New element: insert after prev (which may be NULL)
 102   HashCell* newCell = (HashCell*) safe_malloc(sizeof(HashCell));
 103   newCell->key = (char*) safe_malloc(strlen(key) + 1);
 104   strcpy(newCell->key, key);
 105   newCell->data = safe_malloc(hashTable->dataSize);
 106   memcpy(newCell->data, data, hashTable->dataSize);
 107   newCell->next = NULL;
 108   if (prev == NULL)
 109     hashTable->head[hashIdx] = newCell;
 110   else
 111     prev->next = newCell;
 112   hashTable->size++;
 113 }
 114
 115 void hashtable_delete(HashTable* hashTable, char* key)
 116 {
 117   UInt hashIdx = _compute_hash(key, hashTable->hashSize);
 118   HashCell
 119     *cell = hashTable->head[hashIdx],
 120     *prev = NULL;
 121   while (cell != NULL)
 122   {
 123     if (strcmp(cell->key, key) == 0)
 124     {
 125       if (prev == NULL)
 126         hashTable->head[hashIdx] = cell->next;
 127       else
 128         prev->next = cell->next;
 129       safe_free(cell->key);
 130       safe_free(cell->data);
 131       safe_free(cell);
 132       hashTable->size--;
 133       break;
 134     }
 135     prev = cell;
 136     cell = cell->next;
 137   }
 138 }
 139
 140 void hashtable_clear(HashTable* hashTable)
 141 {
 142     for (UInt i = 0; i < hashTable->hashSize; i++)
 143   {
 144     HashCell* cell = hashTable->head[i];
 145     while (cell != NULL)
 146     {
 147       HashCell* next = cell->next;
 148       safe_free(cell->key);
 149       safe_free(cell->data);
 150       safe_free(cell);
 151       cell = next;
 152     }
 153     hashTable->head[i] = NULL;
 154   }
 155     hashTable->size = 0;
 156 }
 157
 158 void hashtable_destroy(HashTable* hashTable)
 159 {
 160     hashtable_clear(hashTable);
 161     safe_free(hashTable->head);
 162   safe_free(hashTable);
 163 }