X-Git-Url: https://git.auder.net/?p=cgds.git;a=blobdiff_plain;f=src%2FHashTable.c;fp=src%2FHashTable.c;h=7bd310cc042917e69b0fb62136081e35ff74613c;hp=0000000000000000000000000000000000000000;hb=1ff641f9960fa6c6081817a5641afb22fad91dcd;hpb=71e16e325e3936549a5f3a140e6298fce333fd27

diff --git a/src/HashTable.c b/src/HashTable.c
new file mode 100644
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);
+}