diff options
| -rw-r--r-- | .gitignore | 2 | ||||
| -rw-r--r-- | Makefile | 8 | ||||
| -rw-r--r-- | src/hash_table.c | 91 | ||||
| -rw-r--r-- | src/hash_table.h | 3 | ||||
| -rw-r--r-- | src/priority_queue.h | 2 | ||||
| -rw-r--r-- | src/str.c | 7 | ||||
| -rw-r--r-- | tests/test_augment_rbtree.c | 2 | ||||
| -rw-r--r-- | tests/test_htable.c | 1 | ||||
| -rw-r--r-- | tests/test_pque.c | 1 | ||||
| -rw-r--r-- | tests/test_rbtree.c | 2 | ||||
| -rw-r--r-- | tests/test_str.c | 7 |
11 files changed, 81 insertions, 45 deletions
@@ -5,3 +5,5 @@ build/ *.bin *.a doing/ +.cache/ +compile_commands.json @@ -1,4 +1,8 @@ cc = gcc +cflags = \ + -g \ + -fsanitize=address + src = $(shell ls src/*.c) obj = $(src:.c=.o) @@ -21,10 +25,10 @@ test: $(tests_bin) @scripts/runall.sh $^ $(obj):%.o:%.c - $(cc) -c -g $< -MD -MF $@.d -o $@ + $(cc) -c $(cflags) $< -MD -MF $@.d -o $@ $(tests_bin):%.bin:%.c libalgds.a - $(cc) -g -Isrc/ $< libalgds.a -MD -MF $@.d -o $@ + $(cc) $(cflags) -Isrc/ $< libalgds.a -MD -MF $@.d -o $@ clean: -rm $(shell find tests/ -name '*.bin') diff --git a/src/hash_table.c b/src/hash_table.c index 3b635f4..e738a9b 100644 --- a/src/hash_table.c +++ b/src/hash_table.c @@ -7,9 +7,6 @@ #define HTFL_VAL 1 #define HTFL_DEL 2 -static void *hash_table_end(hash_table_t *ht) { - return ht->buf + ht->cap * (ht->elemsz + 1); -} static void rebuild(hash_table_t *ht) { hash_table_t newht; @@ -20,22 +17,20 @@ static void rebuild(hash_table_t *ht) { iter = hash_table_next(ht, iter); } free(ht->buf); + free(ht->flagbuf); *ht = newht; } -static uint8_t getflag(void *iter) { return *(uint8_t *)(iter - 1); } - -static void setflag(void *iter, uint8_t flag) { *(uint8_t *)(iter - 1) = flag; } - void init_hash_table(hash_table_t *ht, int64_t elemsz, int64_t cap, uint64_t (*hash)(void *), bool (*eq)(void *, void *)) { if (cap < 16) cap = 16; - ht->buf = malloc(cap * (elemsz + 1)); - memset(ht->buf, 0, cap * (elemsz + 1)); + ht->buf = malloc(cap * elemsz); + ht->flagbuf = malloc(cap); + memset(ht->buf, 0, cap * elemsz); + memset(ht->flagbuf, 0, cap); ht->size = 0; ht->cap = cap; ht->taken = 0; - ht->begin = NULL; ht->elemsz = elemsz; ht->hash = hash; ht->eq = eq; @@ -47,53 +42,69 @@ bool hash_table_insert(hash_table_t *ht, void *elem) { } ht->taken++; ht->size++; - int64_t hashcode = ht->hash(elem) % ht->cap; - void *pos = ht->buf + hashcode * (ht->elemsz + 1) + 1; - while (getflag(pos) != HTFL_NUL) { - if (getflag(pos) == HTFL_VAL && ht->eq(pos, elem)) return false; - pos += ht->elemsz + 1; - if (pos >= hash_table_end(ht)) { // arrived end, restart from beginning - pos = ht->buf + 1; + int64_t pos = ht->hash(elem) % ht->cap; + while (ht->flagbuf[pos] != HTFL_NUL) { + if (ht->flagbuf[pos] == HTFL_VAL + && ht->eq(ht->buf + pos * ht->elemsz, elem)) { + return false; + } + pos++; + if (pos >= ht->cap) { // arrived end, restart from beginning + pos = 0; } } - memcpy(pos, elem, ht->elemsz); - setflag(pos, HTFL_VAL); - if (pos < ht->begin || ht->begin == NULL) { - ht->begin = pos; - } + memcpy(ht->buf + pos * ht->elemsz, elem, ht->elemsz); + ht->flagbuf[pos] = HTFL_VAL; return true; } -void hash_table_remove(hash_table_t *ht, void *iter) { +void hash_table_remove(hash_table_t *ht, void * ptr) { ht->size--; - setflag(iter, HTFL_DEL); - if (iter == ht->begin) { - ht->begin = hash_table_next(ht, iter); - } + int64_t pos = (ptr - ht->buf) / ht->elemsz; + ht->flagbuf[pos] = HTFL_DEL; +} + +void *hash_table_ref(hash_table_t *ht, int64_t pos) { + return ht->buf + pos * ht->elemsz; } void *hash_table_find(hash_table_t *ht, void *elem) { - int64_t hashcode = ht->hash(elem) % ht->cap; - void *pos = ht->buf + hashcode * (ht->elemsz + 1) + 1; - while (getflag(pos) != HTFL_NUL) { - if (getflag(pos) == HTFL_VAL && ht->eq(pos, elem)) return pos; - pos += ht->elemsz + 1; - if (pos >= hash_table_end(ht)) { // arrived end, restart from beginning - pos = ht->buf + 1; + int64_t pos = ht->hash(elem) % ht->cap; + while (ht->flagbuf[pos] != HTFL_NUL) { + if (ht->flagbuf[pos] == HTFL_VAL + && ht->eq(hash_table_ref(ht, pos), elem)) { + return hash_table_ref(ht, pos); + } + pos++; + if (pos >= ht->cap) { // arrived end, restart from beginning + pos = 0; } } return NULL; } -void *hash_table_begin(hash_table_t *ht) { return ht->begin; } +void* hash_table_begin(hash_table_t *ht) { + if (ht->size <= 0) return NULL; + for (int64_t i = 0; i < ht->cap; i++) { + if (ht->flagbuf[i] == HTFL_VAL) { + return hash_table_ref(ht, i); + } + } + return NULL; +} void *hash_table_next(hash_table_t *ht, void *iter) { - void *pos = iter; + int64_t pos = (iter - ht->buf) / ht->elemsz; do { - pos += ht->elemsz + 1; - if (pos >= hash_table_end(ht)) { + pos++; + if (pos >= ht->cap) { return NULL; } - } while (getflag(pos) != HTFL_VAL); - return pos; + } while (ht->flagbuf[pos] != HTFL_VAL); + return hash_table_ref(ht, pos); +} + +void destroy_hash_table(hash_table_t *ht) { + free(ht->buf); + free(ht->flagbuf); } diff --git a/src/hash_table.h b/src/hash_table.h index 1bf6cfe..3e18be6 100644 --- a/src/hash_table.h +++ b/src/hash_table.h @@ -6,10 +6,10 @@ struct hash_table { void *buf; + char *flagbuf; int64_t size; int64_t cap; int64_t taken; - void *begin; int64_t elemsz; uint64_t (*hash)(void *); bool (*eq)(void *, void *); @@ -25,5 +25,6 @@ void hash_table_remove(hash_table_t *ht, void *iter); void *hash_table_find(hash_table_t *ht, void *elem); void *hash_table_begin(hash_table_t *ht); void *hash_table_next(hash_table_t *ht, void *iter); +void destroy_hash_table(hash_table_t *ht); #endif diff --git a/src/priority_queue.h b/src/priority_queue.h index 895bb42..98250c9 100644 --- a/src/priority_queue.h +++ b/src/priority_queue.h @@ -14,6 +14,6 @@ void init_priority_queue(priority_queue_t *pq, int cap, int elemsz, int (*cmp)(void *, void *)); void priority_queue_push(priority_queue_t *pq, void *elem); void priority_queue_pop(priority_queue_t *pq); -void *priority_queue_top(); +void *priority_queue_top(priority_queue_t *pq); #endif @@ -65,12 +65,17 @@ void destroy_str_list(char **list) { char *str_strip(char *str) { if (str == NULL) return NULL; int len = strlen(str); + if (len == 0) { + char* ret = malloc(1); + ret[0] = '\0'; + return ret; + } char *begin = str; char *end = str + len - 1; while (isspace(*begin) && begin < end) { begin++; } - while (isspace(*end) && end >= begin) { + while (end >= begin && isspace(*end)) { end--; } len = end - begin + 1; diff --git a/tests/test_augment_rbtree.c b/tests/test_augment_rbtree.c index 0389405..9ee3921 100644 --- a/tests/test_augment_rbtree.c +++ b/tests/test_augment_rbtree.c @@ -113,6 +113,7 @@ static void test_largedata() { IntIntEntry *iter = rb_tree_find(&tree, &input[i]); assert(iter != NULL); rb_tree_remove(&tree, iter); + free(iter); } // check tree validity d = depth(tree.rbh_root); @@ -126,4 +127,5 @@ static void test_largedata() { assert(iter->key == i * 3); i++; } + destroy_rb_tree(&tree, NULL); } diff --git a/tests/test_htable.c b/tests/test_htable.c index 310d141..77413d3 100644 --- a/tests/test_htable.c +++ b/tests/test_htable.c @@ -66,6 +66,7 @@ int main() { for (int i = 0; i < 10000; i++) { assert(found[i]); } + destroy_hash_table(&ht); printf("[PASS] htable\n"); } diff --git a/tests/test_pque.c b/tests/test_pque.c index 01e6e1c..a6565bd 100644 --- a/tests/test_pque.c +++ b/tests/test_pque.c @@ -35,6 +35,7 @@ int main() { int *top = priority_queue_top(&pq); assert(*top == expected[i]); } + free(pq.buf); printf("[PASS] pque\n"); return 0; } diff --git a/tests/test_rbtree.c b/tests/test_rbtree.c index b1fbc32..e001d9b 100644 --- a/tests/test_rbtree.c +++ b/tests/test_rbtree.c @@ -115,6 +115,7 @@ static void test_largedata() { IntIntEntry *iter = rb_tree_find(&tree, &input[i]); assert(iter != NULL); rb_tree_remove(&tree, iter); + free(iter); } // check tree validity d = depth(tree.rbh_root); @@ -125,4 +126,5 @@ static void test_largedata() { assert(iter->key == i * 3); i++; } + destroy_rb_tree(&tree, NULL); } diff --git a/tests/test_str.c b/tests/test_str.c index 85e4f31..bde028e 100644 --- a/tests/test_str.c +++ b/tests/test_str.c @@ -61,24 +61,31 @@ void test_str_strip() { s = str_strip("hello "); assert(strcmp(s, "hello") == 0); + free(s); s = str_strip("hello"); assert(strcmp(s, "hello") == 0); + free(s); s = str_strip("\nhello "); assert(strcmp(s, "hello") == 0); + free(s); s = str_strip("\nhello"); assert(strcmp(s, "hello") == 0); + free(s); s = str_strip(""); assert(strcmp(s, "") == 0); + free(s); s = str_strip("\n\t "); assert(strcmp(s, "") == 0); + free(s); s = str_strip(" "); assert(strcmp(s, "") == 0); + free(s); } void test_str_bulider() { |