Start using trie's instead of hash-maps.

9 files changed, 77 insertions, 27 deletions

diff --git a/Makefile b/Makefile
index 9b8281fe..f5a36c8f 100644
--- a/Makefile
+++ b/Makefile
@@ -3,17 +3,18 @@
 CC  := gcc
 LEX := flex
 
-CFLAGS  = -Wall -DSAFE_STR -ggdb
+CFLAGS  = -Wall -DSAFE_STR -DSAFE_HASH -ggdb
 #LFLAGS  =
 #LDFLAGS = 
 
 C_FILES = $(wildcard *.c)
+INC_FILES = $(wildcard *.inc)
 O_FILES = $(C_FILES:.c=.o)
 H_FILES = $(wildcard *.h)
 
 all: parse
 
-%.o : %.c $(H_FILES)
+%.o : %.c $(H_FILES) $(INC_FILES)
 	$(CC) -c -o $@ $< ${CFLAGS}
 
 parse: $(O_FILES)
diff --git a/hash.h b/hash.h
index 7706f089..07c31460 100644
--- a/hash.h
+++ b/hash.h
@@ -7,13 +7,15 @@
 
 unsigned long hash(char*);
 
-#define TABLE(T)     TP(table_,     T)
+#define TABLE(T)     TP(table__,    T)
 #define HASH_PUT(T)  TP(hash_put_,  T)
 #define HASH_GET(T)  TP(hash_get_,  T)
 // #define HASH_INIT(T) TP(hash_init_, T)
 // #define HASH_INIT(T) CONSTRUCTOR_T(hash_ ## T, 1)
 #define HASH_INIT(T) CONSTRUCTOR_GEN(hash, T, 1)
 
+#define HASH_FREE(T) TP(hash_free_, T)
+
 #endif /* HASH_H */
 #ifdef TYPE
 
@@ -33,4 +35,10 @@ int HASH_INIT(TYPE) ( TABLE(TYPE)* table, int init_size );
 
 TYPE* HASH_GET(TYPE) ( TABLE(TYPE)* table, char* key );
 
+/*
+ * Free's all item's stored in table.
+ * And finally frees table.
+ */
+int HASH_FREE(TYPE) ( TABLE(TYPE)* table );
+
 #endif /* HASH_H */
diff --git a/hash_help.inc b/hash_help.inc
index ddaf4ae0..34766b54 100644
--- a/hash_help.inc
+++ b/hash_help.inc
@@ -2,12 +2,18 @@
 #error "Set TYPE to something before including this header"
 #else
 
+#include "err.h"
+
 int HASH_PUT(TYPE) ( TABLE(TYPE)* table, TYPE* value) {
 	// TODO genicify the hash function
 	unsigned long h = hash(value->key.mem) % table->size;
-	table->values[h] = value;
+	TYPE* mem = table->values[h];
+
+	// fprintf(stderr, "INFO: %i: [%s] := [%s]\n", table->item_count, value->key.mem, value->val.mem);
 
 	/* TODO conflict resolution */
+	if (mem != NULL) ERR("Hash collision");
+   	mem = value;
 
 	++table->item_count;
 	return 0;
@@ -25,15 +31,32 @@ int HASH_INIT(TYPE) ( TABLE(TYPE)* table, int init_size ) {
 
 TYPE* HASH_GET(TYPE) ( TABLE(TYPE)* table, char* key ) {
 	unsigned long h = hash(key) % table->size;
-	// TYPE* mem = (table->values + h);
 	TYPE* mem = table->values[h];
 	if (mem == NULL) {
+		fprintf(stderr, "Trying to access %s\n", key);
+		ERR("Nothing in field");
 		return 0;
 	} else if (strcmp(mem->key.mem, key) == 0) {
 		return mem;
 	} else {
 		/* TODO fix retrival on invalid key */
+		ERR("Other error");
+		return 0;
+	}
+}
+
+int HASH_FREE(TYPE) ( TABLE(TYPE)* table ) {
+	/*
+	 * TODO an early return is possible by checking if all items have
+	 * been found. table->item_count
+	 */
+	for (int i = 0; i < table->size; i++) {
+		TYPE* mem = table->values[i];
+		if (mem == NULL) continue;
+
+		free(mem);
 	}
+	free(table->values);
 	return 0;
 }
 
diff --git a/macro.h b/macro.h
index ca3fce24..89178cb3 100644
--- a/macro.h
+++ b/macro.h
@@ -11,6 +11,7 @@
 #define TP(a, b) a ## b
 #define TP3(a, b, c) a ## b ## c
 #define TP4(a, b, c, d) a ## b ## c ## d
+#define TP5(a, b, c, d, e) a ## b ## c ## d ## e
 
 /*
  * Get length of __VA_ARGS__
@@ -24,12 +25,17 @@
 	TP3(T, _init_, ARG_COUNT)
 
 /*
+ * TODO rename all the constructor macros to something clearer and
+ * shorter.
+ */
+
+/*
  * Constructor type name
  */
-#define CONSTRUCTOR_T(T, C) TP3(T, _init_, C)
+#define CONSTRUCTOR_T(T, C) TP3(T, __init__, C)
 
 #define CONSTRUCTOR_GEN(parent, child, C) \
-	CONSTRUCTOR_T(parent ## _ ## child, C)
+	CONSTRUCTOR_T(parent ## __ ## child, C)
 
 /*
  * Returns full type of constructor
diff --git a/main.c b/main.c
index 278aac26..ee6dfa89 100644
--- a/main.c
+++ b/main.c
@@ -8,6 +8,8 @@
 #include <sys/stat.h>
 #include <fcntl.h>
 
+#include <string.h>
+
 #include "parse.h"
 #include "macro.h"
 
@@ -60,7 +62,9 @@ int main (int argc, char* argv[argc]) {
 			cal.n_events);
 	for (size_t i = 0; i < cal.n_events; i++) {
 		// printf("%3lu. %s\n", i + 1, cal.events[i].summary.mem);
-		printf("%3lu. %s\n", i + 1, get_property(&cal.events[i], "SUMMARY")->val.mem);
+		// TODO this segfaults
+		// apparently get_property returns 0 in some cases
+		printf("%3lu. %s\n", i + 1, get_property(cal.events[i], "SUMMARY")->val.mem);
 	}
 
 	closedir(dir);
diff --git a/parse.c b/parse.c
index a2ceae6a..83693e8c 100644
--- a/parse.c
+++ b/parse.c
@@ -26,6 +26,7 @@ int parse_file(FILE* f, vcalendar* cal) {
 
 	int line = 0;
 
+	// TODO these are never freed. 
 	NEW(vevent, ev, /**/ 100);
 
 	SNEW(content_line, cline, keylen, vallen);
@@ -69,13 +70,11 @@ int parse_file(FILE* f, vcalendar* cal) {
 				}
 
 				/* At TRUE end of line */
-				/*
 				if (str.ptr + 1 > vallen) {
 					vallen = str.ptr + 1;
-					// TODO this fails
 					strbuf_realloc(&cline.val, vallen);
 				}
-				*/
+
 				strbuf_copy(&cline.val, &str);
 				strbuf_cap(&cline.val);
 
diff --git a/strbuf.c b/strbuf.c
index 7f61313b..f5680a22 100644
--- a/strbuf.c
+++ b/strbuf.c
@@ -101,12 +101,13 @@ int strbuf_reset(strbuf* s)
 int strbuf_init_copy(strbuf* dest, strbuf* src) {
 #ifdef SAFE_STR
 	if (dest->alloc != 0) {
+		printf("%lu  ", dest->alloc);
 		ERR("Dest already allocated");
 		return 1;
 	}
 #endif
 
-	strbuf_init_1(dest, src->len + 1);
+	CONSTRUCT(strbuf, dest, src->len + 1);
 	strbuf_copy(dest, src);
 
 	return 0;
diff --git a/vcal.c b/vcal.c
index e1dd3d63..ceb5980b 100644
--- a/vcal.c
+++ b/vcal.c
@@ -3,20 +3,25 @@
 #include <string.h>
 
 #define TYPE content_line
-#include "hash_help.inc"
+// #include "hash_help.inc"
+#include "trie.inc"
 #undef TYPE
 
 int CONSTRUCTOR_DECL(vevent, int init_size) {
-	HASH_INIT(content_line)(&this->clines, init_size);
+	// HASH_INIT(content_line)(&this->clines, init_size);
+	CONSTRUCT(TRIE(content_line), &this->clines);
 	return 0;
 }
 
 content_line* get_property (vevent* ev, char* key) {
-	return HASH_GET(content_line)(&ev->clines, key);
+	// return HASH_GET(content_line)(&ev->clines, key);
+	return TRIE_GET(content_line)(&ev->clines, key);
 }
 
 int add_content_line (vevent* ev, content_line* c) {
-	return HASH_PUT(content_line)(&ev->clines, c);
+	// return HASH_PUT(content_line)(&ev->clines, c);
+	// TODO memmory safety on strbuf?
+	return TRIE_PUT(content_line)(&ev->clines, c->key.mem, c);
 }
 
 int CONSTRUCTOR_DECL(content_line) {
@@ -70,12 +75,13 @@ int vevent_init_copy(vevent* dest, vevent* src) {
 	return 0;
 }
 
-/* TODO reimplement this */
 int free_vevent (vevent* ev) {
 	// strbuf_free(&ev->dtstart);
 	// strbuf_free(&ev->dtend);
 	// strbuf_free(&ev->summary);
 	// strbuf_free(&ev->description);
+	// HASH_FREE(content_line)(&ev->clines);
+	TRIE_FREE(content_line)(&ev->clines);
 	return 0;
 }
 
@@ -88,7 +94,7 @@ int push_event(vcalendar* cal, vevent* ev) {
 	}
 
 	// vevent_init_copy(&cal->events[cal->n_events], ev);
-	cal->events[cal->n_events] = *ev;
+	cal->events[cal->n_events] = ev;
 
 	cal->n_events++;
 	return 0;
@@ -103,7 +109,7 @@ int CONSTRUCTOR_DECL(vcalendar) {
 
 int free_vcalendar (vcalendar* cal) {
 	for (size_t i = 0; i < cal->n_events; i++) {
-		free_vevent(& cal->events[i]);
+		free_vevent(cal->events[i]);
 	}
 	free (cal->events);
 	return 0;
diff --git a/vcal.h b/vcal.h
index 285d2d0b..0876e0a9 100644
--- a/vcal.h
+++ b/vcal.h
@@ -24,21 +24,20 @@ typedef struct {
 } content_line;
 
 #define TYPE content_line
-#include "hash.h"
+// #include "hash.h"
+#include "trie.h"
 #undef TYPE
 
-struct s_vevent {
+typedef struct s_vevent {
 	/*
 	strbuf dtstart;
 	strbuf dtend;
 	strbuf summary;
 	strbuf description;
 	*/
-	TABLE(content_line) clines;
-};
-
-struct s_vevent;
-typedef struct s_vevent vevent;
+	// TABLE(content_line) clines;
+	TRIE(content_line) clines;
+} vevent;
 
 int CONSTRUCTOR_DECL(vevent, int init_size);
 
@@ -69,12 +68,15 @@ int free_vevent(vevent* ev);
 typedef struct {
 	size_t n_events;
 	size_t alloc;
-	vevent* events;
+	vevent** events;
 } vcalendar;
 
 int CONSTRUCTOR_DECL(vcalendar);
 int free_vcalendar (vcalendar* cal);
 
+/*
+ * Appends ev to cal. Doesn't copy ev
+ */
 int push_event(vcalendar* cal, vevent* ev);
 
 #endif /* VCAL_H */