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) % hashSize;
  69   return res;
  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)
  79       return cell->data;
  80     cell = cell->next;
  81   }
  82   return NULL;
  83 }
  84
  85 void _hashtable_set(HashTable* hashTable, char* key, void* data)
  86 {
  87   UInt hashIdx = _compute_hash(key, hashTable->hashSize);
  88   HashCell *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 *cell = hashTable->head[hashIdx],
 119            *prev = NULL;
 120   while (cell != NULL)
 121   {
 122     if (strcmp(cell->key, key) == 0)
 123     {
 124       if (prev == NULL)
 125         hashTable->head[hashIdx] = cell->next;
 126       else
 127         prev->next = cell->next;
 128       safe_free(cell->key);
 129       safe_free(cell->data);
 130       safe_free(cell);
 131       hashTable->size--;
 132       break;
 133     }
 134     prev = cell;
 135     cell = cell->next;
 136   }
 137 }
 138
 139 void hashtable_clear(HashTable* hashTable)
 140 {
 141   for (UInt i = 0; i < hashTable->hashSize; i++)
 142   {
 143     HashCell* cell = hashTable->head[i];
 144     while (cell != NULL)
 145     {
 146       HashCell* next = cell->next;
 147       safe_free(cell->key);
 148       safe_free(cell->data);
 149       safe_free(cell);
 150       cell = next;
 151     }
 152     hashTable->head[i] = NULL;
 153   }
 154   hashTable->size = 0;
 155 }
 156
 157 void hashtable_destroy(HashTable* hashTable)
 158 {
 159   hashtable_clear(hashTable);
 160   safe_free(hashTable->head);
 161   safe_free(hashTable);
 162 }