From ebe5c7e428b57dca758b1b3a1d8b7d4b423b19a9 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Hugo=20H=C3=B6rnquist?= Date: Tue, 22 Jan 2019 11:42:58 +0100 Subject: Start using trie's instead of hash-maps. --- Makefile | 5 +++-- hash.h | 10 +++++++++- hash_help.inc | 27 +++++++++++++++++++++++++-- macro.h | 10 ++++++++-- main.c | 6 +++++- parse.c | 5 ++--- strbuf.c | 3 ++- vcal.c | 20 +++++++++++++------- vcal.h | 18 ++++++++++-------- 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__ @@ -23,13 +24,18 @@ #define NEW_HELPER(T, ARG_COUNT) \ 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 #include +#include + #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 #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 */ -- cgit v1.2.3