diff options
Diffstat (limited to 'examples/c_files/hash.c')
| -rw-r--r-- | examples/c_files/hash.c | 200 |
1 files changed, 200 insertions, 0 deletions
diff --git a/examples/c_files/hash.c b/examples/c_files/hash.c new file mode 100644 index 0000000..7ec500e --- /dev/null +++ b/examples/c_files/hash.c @@ -0,0 +1,200 @@ +/*
+** C implementation of a hash table ADT
+*/
+typedef enum tagReturnCode {SUCCESS, FAIL} ReturnCode;
+
+
+typedef struct tagEntry
+{
+ char* key;
+ char* value;
+} Entry;
+
+
+
+typedef struct tagNode
+{
+ Entry* entry;
+
+ struct tagNode* next;
+} Node;
+
+
+typedef struct tagHash
+{
+ unsigned int table_size;
+
+ Node** heads;
+
+} Hash;
+
+
+static unsigned int hash_func(const char* str, unsigned int table_size)
+{
+ unsigned int hash_value;
+ unsigned int a = 127;
+
+ for (hash_value = 0; *str != 0; ++str)
+ hash_value = (a*hash_value + *str) % table_size;
+
+ return hash_value;
+}
+
+
+ReturnCode HashCreate(Hash** hash, unsigned int table_size)
+{
+ unsigned int i;
+
+ if (table_size < 1)
+ return FAIL;
+
+ //
+ // Allocate space for the Hash
+ //
+ if (((*hash) = malloc(sizeof(**hash))) == NULL)
+ return FAIL;
+
+ //
+ // Allocate space for the array of list heads
+ //
+ if (((*hash)->heads = malloc(table_size*sizeof(*((*hash)->heads)))) == NULL)
+ return FAIL;
+
+ //
+ // Initialize Hash info
+ //
+ for (i = 0; i < table_size; ++i)
+ {
+ (*hash)->heads[i] = NULL;
+ }
+
+ (*hash)->table_size = table_size;
+
+ return SUCCESS;
+}
+
+
+ReturnCode HashInsert(Hash* hash, const Entry* entry)
+{
+ unsigned int index = hash_func(entry->key, hash->table_size);
+ Node* temp = hash->heads[index];
+
+ HashRemove(hash, entry->key);
+
+ if ((hash->heads[index] = malloc(sizeof(Node))) == NULL)
+ return FAIL;
+
+ hash->heads[index]->entry = malloc(sizeof(Entry));
+ hash->heads[index]->entry->key = malloc(strlen(entry->key)+1);
+ hash->heads[index]->entry->value = malloc(strlen(entry->value)+1);
+ strcpy(hash->heads[index]->entry->key, entry->key);
+ strcpy(hash->heads[index]->entry->value, entry->value);
+
+ hash->heads[index]->next = temp;
+
+ return SUCCESS;
+}
+
+
+
+const Entry* HashFind(const Hash* hash, const char* key)
+{
+ unsigned int index = hash_func(key, hash->table_size);
+ Node* temp = hash->heads[index];
+
+ while (temp != NULL)
+ {
+ if (!strcmp(key, temp->entry->key))
+ return temp->entry;
+
+ temp = temp->next;
+ }
+
+ return NULL;
+}
+
+
+ReturnCode HashRemove(Hash* hash, const char* key)
+{
+ unsigned int index = hash_func(key, hash->table_size);
+ Node* temp1 = hash->heads[index];
+ Node* temp2 = temp1;
+
+ while (temp1 != NULL)
+ {
+ if (!strcmp(key, temp1->entry->key))
+ {
+ if (temp1 == hash->heads[index])
+ hash->heads[index] = hash->heads[index]->next;
+ else
+ temp2->next = temp1->next;
+
+ free(temp1->entry->key);
+ free(temp1->entry->value);
+ free(temp1->entry);
+ free(temp1);
+ temp1 = NULL;
+
+ return SUCCESS;
+ }
+
+ temp2 = temp1;
+ temp1 = temp1->next;
+ }
+
+ return FAIL;
+}
+
+
+void HashPrint(Hash* hash, void (*PrintFunc)(char*, char*))
+{
+ unsigned int i;
+
+ if (hash == NULL || hash->heads == NULL)
+ return;
+
+ for (i = 0; i < hash->table_size; ++i)
+ {
+ Node* temp = hash->heads[i];
+
+ while (temp != NULL)
+ {
+ PrintFunc(temp->entry->key, temp->entry->value);
+ temp = temp->next;
+ }
+ }
+}
+
+
+
+void HashDestroy(Hash* hash)
+{
+ unsigned int i;
+
+ if (hash == NULL)
+ return;
+
+ for (i = 0; i < hash->table_size; ++i)
+ {
+ Node* temp = hash->heads[i];
+
+ while (temp != NULL)
+ {
+ Node* temp2 = temp;
+
+ free(temp->entry->key);
+ free(temp->entry->value);
+ free(temp->entry);
+
+ temp = temp->next;
+
+ free(temp2);
+ }
+ }
+
+ free(hash->heads);
+ hash->heads = NULL;
+
+ free(hash);
+}
+
|