Implement HashTable + fix some extra blank spaces, remove Bool type (using bool ...

[cgds.git] / src / HashTable.c

diff --git a/src/HashTable.c b/src/HashTable.c
new file mode 100644 (file)
index 0000000..7bd310c
--- /dev/null
+++ b/src/HashTable.c
@@ -0,0 +1,163 @@
+/**
+ * @file HashTable.c
+ */
+
+#include "cgds/HashTable.h"
+
+void _hashtable_init(HashTable* hashTable, size_t dataSize, size_t hashSize)
+{
+       hashTable->hashSize = hashSize;
+  hashTable->dataSize = dataSize;
+       hashTable->head = safe_malloc(hashSize * sizeof(HashCell*));
+       for (UInt i = 0; i < hashSize; i++)
+    hashTable->head[i] = NULL;
+  hashTable->size = 0;
+}
+
+HashTable* _hashtable_new(size_t dataSize, size_t hashSize)
+{
+       HashTable* hashTable = (HashTable*) safe_malloc(sizeof (HashTable));
+       _hashtable_init(hashTable, dataSize, hashSize);
+       return hashTable;
+}
+
+HashTable* hashtable_copy(HashTable* hashTable)
+{
+       HashTable* hashTableCopy =
+    _hashtable_new(hashTable->dataSize, hashTable->hashSize);
+       hashTableCopy->size = hashTable->size;
+  for (UInt i = 0; i < hashTable->hashSize; i++)
+       {
+    HashCell *cell = hashTable->head[i],
+             *cellCopy = hashTableCopy->head[i],
+             *prev = NULL;
+    while (cell != NULL)
+    {
+      // cellCopy == NULL (from empty list)
+      cellCopy = (HashCell*) safe_malloc(sizeof(HashCell*));
+                 cellCopy->key = (char*) safe_malloc(strlen(cell->key) + 1);
+      strcpy(cellCopy->key, cell->key);
+                 cellCopy->data = safe_malloc(hashTable->dataSize);
+                 memcpy(cellCopy->data, cell->data, hashTable->dataSize);
+      if (prev == NULL) hashTableCopy->head[i] = cellCopy;
+      else prev->next = cellCopy;
+      prev = cellCopy;
+      cell = cell->next;
+    }
+    if (cellCopy != NULL) cellCopy->next = NULL;
+       }
+       return hashTableCopy;
+}
+
+bool hashtable_empty(HashTable* hashTable)
+{
+       return (hashTable->size == 0);
+}
+
+UInt hashtable_size(HashTable* hashTable)
+{
+       return hashTable->size;
+}
+
+// Function (string) key --> (integer) hash [internal usage]
+UInt _compute_hash(char* key, size_t hashSize)
+{
+  UInt res = 0;
+  for (unsigned char* s = key; *s != '\0'; s++)
+    // NOTE: '31' from here https://stackoverflow.com/a/4384446
+    res += *s + 31 * res;
+  return res % hashSize;
+}
+
+void* _hashtable_get(HashTable* hashTable, char* key)
+{
+  UInt hashIdx = _compute_hash(key, hashTable->hashSize);
+  HashCell* cell = hashTable->head[hashIdx];
+  while (cell != NULL)
+  {
+    if (strcmp(cell->key, key) == 0) return cell->data;
+    cell = cell->next;
+  }
+  return NULL;
+}
+
+void _hashtable_set(HashTable* hashTable, char* key, void* data)
+{
+  UInt hashIdx = _compute_hash(key, hashTable->hashSize);
+  HashCell
+    *cell = hashTable->head[hashIdx],
+    *prev = NULL;
+  while (cell != NULL)
+  {
+    if (strcmp(cell->key, key) == 0)
+    {
+      // Modify:
+      memcpy(cell->data, data, hashTable->dataSize);
+      return;
+    }
+    prev = cell;
+    cell = cell->next;
+  }
+  // New element: insert after prev (which may be NULL)
+  HashCell* newCell = (HashCell*) safe_malloc(sizeof(HashCell));
+  newCell->key = (char*) safe_malloc(strlen(key) + 1);
+  strcpy(newCell->key, key);
+  newCell->data = safe_malloc(hashTable->dataSize);
+  memcpy(newCell->data, data, hashTable->dataSize);
+  newCell->next = NULL;
+  if (prev == NULL)
+    hashTable->head[hashIdx] = newCell;
+  else
+    prev->next = newCell;
+  hashTable->size++;
+}
+
+void hashtable_delete(HashTable* hashTable, char* key)
+{
+  UInt hashIdx = _compute_hash(key, hashTable->hashSize);
+  HashCell
+    *cell = hashTable->head[hashIdx],
+    *prev = NULL;
+  while (cell != NULL)
+  {
+    if (strcmp(cell->key, key) == 0)
+    {
+      if (prev == NULL)
+        hashTable->head[hashIdx] = cell->next;
+      else
+        prev->next = cell->next;
+      safe_free(cell->key);
+      safe_free(cell->data);
+      safe_free(cell);
+      hashTable->size--;
+      break;
+    }
+    prev = cell;
+    cell = cell->next;
+  }
+}
+
+void hashtable_clear(HashTable* hashTable)
+{
+       for (UInt i = 0; i < hashTable->hashSize; i++)
+  {
+    HashCell* cell = hashTable->head[i];
+    while (cell != NULL)
+    {
+      HashCell* next = cell->next;
+      safe_free(cell->key);
+      safe_free(cell->data);
+      safe_free(cell);
+      cell = next;
+    }
+    hashTable->head[i] = NULL;
+  }
+       hashTable->size = 0;
+}
+
+void hashtable_destroy(HashTable* hashTable)
+{
+       hashtable_clear(hashTable);
+       safe_free(hashTable->head);
+  safe_free(hashTable);
+}