commit d8c1f68d45e1aee828c8d8f0820ad36ef513addb parent d8057530fc93e4f82f2c14438d8650fe1464d251 Author: Paul Longtine <paullongtine@gmail.com> Date: Wed Jan 20 11:21:35 2016 completed hashtable implementation Diffstat: src/vm/inc/ht.h | 5 +- src/vm/inc/types.h | 19 +++++-- src/vm/src/ht.c | 112 ++++++++++++++++++++++++++++++++++++++--- src/vm/tests/ht/expected_output | 3 +- src/vm/tests/ht/test | Bin 0 -> 13493 bytes src/vm/tests/ht/test.c | 8 +++- 6 files changed, 135 insertions(+), 12 deletions(-)
diff --git a/src/vm/inc/ht.h b/src/vm/inc/ht.h @@ -4,7 +4,10 @@ #ifndef HT_H #define HT_H +#include <stdio.h> #include <stdlib.h> +#include <limits.h> +#include <string.h> #include "types.h" #include "helper.h" @@ -24,7 +27,7 @@ typedef struct ht_t { */ ht_t* ht_init(int); -/* Creates the table of buckets for the hashtable +/* Creates the table of empty buckets for the hashtable */ ht_entry** ht_init_table(int); diff --git a/src/vm/inc/types.h b/src/vm/inc/types.h @@ -1,12 +1,12 @@ /* types.h -> Provide implemenation of types */ -#include <stdlib.h> -#include <stdio.h> - #ifndef TYPES_H #define TYPES_H +#include <stdlib.h> +#include <stdio.h> + typedef enum { VOID, FUNC, @@ -17,7 +17,8 @@ typedef enum { G_STRING, S_ARRAY, D_ARRAY, - A_ARRAY + K_ARRAY, + G_FIFO } b_type; typedef struct var_cont { @@ -25,6 +26,16 @@ typedef struct var_cont { void* data; } var_cont; +typedef void var_data_void; + +typedef int var_data_int; + +typedef char var_data_char; + +typedef struct var_data_str { + char* str; +} var_data_str; + /* Initialze variable with type */ var_cont* var_new(b_type); diff --git a/src/vm/src/ht.c b/src/vm/src/ht.c @@ -1,4 +1,9 @@ +#define _XOPEN_SOUCE 500 + +#include <stdio.h> #include <stdlib.h> +#include <limits.h> +#include <string.h> #include "ht.h" #include "types.h" @@ -10,7 +15,6 @@ ht_t* ht_init(int size) ASSERT(hashtable != NULL, "Could not allocate memory\n"); hashtable->size = size; - hashtable->table = ht_init_table(hashtable->size); return hashtable; @@ -18,14 +22,12 @@ ht_t* ht_init(int size) ht_entry** ht_init_table(int size) { - ht_entry** table = (ht_entry**)malloc(sizeof(ht_entry)*size); + ht_entry** table = (ht_entry**)malloc(sizeof(ht_entry*)*size); ASSERT(table != NULL, "Could not allocate memory\n"); for (int i = 0; i < size; i++) { - table[i]->key = NULL; - table[i]->value = var_new(0); - table[i]->next = NULL; + table[i] = NULL; } return table; @@ -40,7 +42,9 @@ void ht_destroy_table(ht_entry** table, int size) { for (int i = 0; i < size; i++) { - ht_destroy_entry(table[i]); + if (table[i] != NULL){ + ht_destroy_entry(table[i]); + } } } @@ -53,7 +57,101 @@ void ht_destroy_entry(ht_entry* entry) if (entry->next != NULL) ht_destroy_entry(entry->next); - + free(entry); } +void ht_set(ht_t* hashtable, char* key, var_cont* value) +{ + int bucket = 0; + ht_entry* np = NULL; + ht_entry* next = NULL; + ht_entry* last = NULL; + + bucket = ht_hash(hashtable, key); + + next = hashtable->table[ bucket ]; + + /* Get relavent key/value pair if it exists in the bucket */ + while (next != NULL && next->key != NULL && strcmp(key, next->key) > 0) + { + last = next; + next = next->next; + } + + if (next != NULL && next->key != NULL && strcmp(key, next->key) == 0) + { + var_del(next->value); + next->value = value; + } + else + { + np = ht_newpair(key, value); + + if (next == hashtable->table[bucket]) + { + np->next = next; + hashtable->table[bucket] = np; + } + else if (next == NULL) + { + last->next = np; + } + else + { + np->next = next; + last->next = np; + } + } +} + +var_cont* ht_get(ht_t* hashtable, char* key) +{ + int bucket = ht_hash(hashtable, key); + + ht_entry* pair = hashtable->table[bucket]; + while (pair != NULL && pair->key != NULL && strcmp(key, pair->key) > 0) + { + pair = pair->next; + } + + if (pair == NULL || pair->key == NULL || strcmp(key, pair->key) != 0) + { + return var_new(0); + } + else + { + return pair->value; + } +} + +ht_entry* ht_newpair(char* key, var_cont* value) +{ + ht_entry* newpair; + + newpair = malloc(sizeof(ht_entry)); + ASSERT(newpair != NULL, "Couldn't allocate memory!"); + + newpair->key = strdup(key); + ASSERT(newpair->key != NULL, "Null keys are bad mhmkay"); + + newpair->value = value; + + return newpair; +} + +int ht_hash(ht_t* hashtable, char* key) +{ + unsigned long int hashval; + int i = 0; + + /* Convert our string to an integer */ + while (hashval < ULONG_MAX && i < strlen(key)) + { + hashval = hashval << 8; + hashval += key[ i ]; + i++; + } + + return hashval % hashtable->size; +} diff --git a/src/vm/tests/ht/expected_output b/src/vm/tests/ht/expected_output @@ -0,0 +1,3 @@ +0 +1 +2 diff --git a/src/vm/tests/ht/test b/src/vm/tests/ht/test Binary files differ diff --git a/src/vm/tests/ht/test.c b/src/vm/tests/ht/test.c @@ -5,6 +5,14 @@ int main(int argc, char* argv[]) { ht_t* hashtable = ht_init(65536); + ht_set(hashtable, "key1", var_new(0)); + ht_set(hashtable, "key2", var_new(1)); + ht_set(hashtable, "key3", var_new(2)); + + printf("%i\n", ht_get(hashtable, "key1")->type); + printf("%i\n", ht_get(hashtable, "key2")->type); + printf("%i\n", ht_get(hashtable, "key3")->type); + ht_destroy(hashtable); return 0; }
