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
  89     *cell = hashTable->head[hashIdx],
  90     *prev = NULL;
  91   while (cell != NULL)
  92   {
  93     if (strcmp(cell->key, key) == 0)
  94     {
  95       // Modify:
  96       memcpy(cell->data, data, hashTable->dataSize);
  97       return;
  98     }
  99     prev = cell;
 100     cell = cell->next;
 101   }
 102   // New element: insert after prev (which may be NULL)
 103   HashCell* newCell = (HashCell*) safe_malloc(sizeof(HashCell));
 104   newCell->key = (char*) safe_malloc(strlen(key) + 1);
 105   strcpy(newCell->key, key);
 106   newCell->data = safe_malloc(hashTable->dataSize);
 107   memcpy(newCell->data, data, hashTable->dataSize);
 108   newCell->next = NULL;
 109   if (prev == NULL)
 110     hashTable->head[hashIdx] = newCell;
 111   else
 112     prev->next = newCell;
 113   hashTable->size++;
 114 }
 115
 116 void hashtable_delete(HashTable* hashTable, char* key)
 117 {
 118   UInt hashIdx = _compute_hash(key, hashTable->hashSize);
 119   HashCell
 120     *cell = hashTable->head[hashIdx],
 121     *prev = NULL;
 122   while (cell != NULL)
 123   {
 124     if (strcmp(cell->key, key) == 0)
 125     {
 126       if (prev == NULL)
 127         hashTable->head[hashIdx] = cell->next;
 128       else
 129         prev->next = cell->next;
 130       safe_free(cell->key);
 131       safe_free(cell->data);
 132       safe_free(cell);
 133       hashTable->size--;
 134       break;
 135     }
 136     prev = cell;
 137     cell = cell->next;
 138   }
 139 }
 140
 141 void hashtable_clear(HashTable* hashTable)
 142 {
 143   for (UInt i = 0; i < hashTable->hashSize; i++)
 144   {
 145     HashCell* cell = hashTable->head[i];
 146     while (cell != NULL)
 147     {
 148       HashCell* next = cell->next;
 149       safe_free(cell->key);
 150       safe_free(cell->data);
 151       safe_free(cell);
 152       cell = next;
 153     }
 154     hashTable->head[i] = NULL;
 155   }
 156   hashTable->size = 0;
 157 }
 158
 159 void hashtable_destroy(HashTable* hashTable)
 160 {
 161   hashtable_clear(hashTable);
 162   safe_free(hashTable->head);
 163   safe_free(hashTable);
 164 }