From 1208bdd0fccc5f1e380053d8e0a7f4df6fe8f805 Mon Sep 17 00:00:00 2001 From: Mistivia Date: Sun, 24 Mar 2024 09:36:51 +0800 Subject: git init --- .gitignore | 7 + Makefile | 37 +++++ README.md | 17 ++ scripts/runall.sh | 9 ++ src/arena.c | 40 +++++ src/arena.h | 23 +++ src/hash_table.c | 99 ++++++++++++ src/hash_table.h | 29 ++++ src/mmhash.c | 57 +++++++ src/mmhash.h | 8 + src/priority_queue.c | 73 +++++++++ src/priority_queue.h | 19 +++ src/rb_tree.c | 386 ++++++++++++++++++++++++++++++++++++++++++++ src/rb_tree.h | 64 ++++++++ src/str.c | 131 +++++++++++++++ src/str.h | 24 +++ tests/test_augment_rbtree.c | 129 +++++++++++++++ tests/test_htable.c | 71 ++++++++ tests/test_mmhash.c | 15 ++ tests/test_pque.c | 40 +++++ tests/test_rbtree.c | 128 +++++++++++++++ tests/test_str.c | 114 +++++++++++++ 22 files changed, 1520 insertions(+) create mode 100644 .gitignore create mode 100644 Makefile create mode 100644 README.md create mode 100755 scripts/runall.sh create mode 100644 src/arena.c create mode 100644 src/arena.h create mode 100644 src/hash_table.c create mode 100644 src/hash_table.h create mode 100644 src/mmhash.c create mode 100644 src/mmhash.h create mode 100644 src/priority_queue.c create mode 100644 src/priority_queue.h create mode 100644 src/rb_tree.c create mode 100644 src/rb_tree.h create mode 100644 src/str.c create mode 100644 src/str.h create mode 100644 tests/test_augment_rbtree.c create mode 100644 tests/test_htable.c create mode 100644 tests/test_mmhash.c create mode 100644 tests/test_pque.c create mode 100644 tests/test_rbtree.c create mode 100644 tests/test_str.c diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..4bb912d --- /dev/null +++ b/.gitignore @@ -0,0 +1,7 @@ +/test_* +*.o +*.d +build/ +*.bin +*.a +doing/ diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..3f409e9 --- /dev/null +++ b/Makefile @@ -0,0 +1,37 @@ +cc = gcc +src = $(shell ls src/*.c) +obj = $(src:.c=.o) + +tests=$(shell ls tests/*.c) +tests_bin=$(tests:.c=.bin) + +all: libalgds.a + -rm -rf build/ + -@mkdir -p build/include/algds/ + -@mkdir -p build/lib + mv libalgds.a build/lib/ + cp src/*.h build/include/algds + +libalgds.a: $(obj) + ar cr $@ $^ + +test: $(tests_bin) + @echo + @echo "Run tests:" + @scripts/runall.sh $^ + +$(obj):%.o:%.c + $(cc) -c -g $< -MD -MF $@.d -o $@ + +$(tests_bin):%.bin:%.c libalgds.a + $(cc) -g -Isrc/ $< libalgds.a -MD -MF $@.d -o $@ + +clean: + -rm $(shell find tests/ -name '*.bin') + -rm $(shell find . -name '*.o' -or -name '*.a' -or -name '*.d') + -rm -rf build + +DEPS := $(shell find . -name *.d) +ifneq ($(DEPS),) +include $(DEPS) +endif diff --git a/README.md b/README.md new file mode 100644 index 0000000..f990225 --- /dev/null +++ b/README.md @@ -0,0 +1,17 @@ +# Algorithms and Data Structures + +- Red-black tree +- Augmented red-black tree +- Priority queue +- Murmur Hash +- Hash Table +- String utilities +- Region-based memory management + +## Build + + make + +## Run Tests + + make test diff --git a/scripts/runall.sh b/scripts/runall.sh new file mode 100755 index 0000000..3fdc745 --- /dev/null +++ b/scripts/runall.sh @@ -0,0 +1,9 @@ +#!/usr/bin/env bash + +for var in "$@"; do + ./$var + if [ $? -ne 0 ]; then + exit 255 + fi +done + diff --git a/src/arena.c b/src/arena.c new file mode 100644 index 0000000..f45d11b --- /dev/null +++ b/src/arena.c @@ -0,0 +1,40 @@ +#include "arena.h" + +#include + +void init_arena(arena_t *r, int blocksz) { + if (blocksz < 4096) blocksz = 4096; + r->head = (struct memblock){NULL, 0, blocksz}; + r->head.buf = malloc(blocksz); + r->current = &(r->head); + r->blocksz = blocksz; +} + +void destroy_arena(arena_t *r) { + free(r->head.buf); + struct memblock *cur = r->head.next; + while (cur != NULL) { + struct memblock *prev = cur; + cur = cur->next; + free(prev->buf); + free(prev); + } +} + +void *arena_alloc(arena_t *r, int sz) { + int remain = r->current->cap - r->current->sz; + if (remain >= sz) { + void *ptr = r->current->buf + r->current->sz; + r->current->sz += sz; + return ptr; + } + int blocksz = sz > blocksz ? sz : blocksz; + struct memblock *nextblock = malloc(sizeof(struct memblock)); + void *ptr = malloc(blocksz); + nextblock->buf = ptr; + nextblock->cap = blocksz; + nextblock->sz = sz; + r->current->next = nextblock; + r->current = nextblock; + return ptr; +} diff --git a/src/arena.h b/src/arena.h new file mode 100644 index 0000000..80636e2 --- /dev/null +++ b/src/arena.h @@ -0,0 +1,23 @@ +#ifndef ALGDS_ARENA_H_ +#define ALGDS_ARENA_H_ + +struct memblock { + void *buf; + int sz; + int cap; + struct memblock *next; +}; +typedef struct memblock memblock_t; + +struct arena { + struct memblock head; + struct memblock *current; + int blocksz; +}; +typedef struct arena arena_t; + +void init_arena(arena_t *r, int blocksz); +void destroy_arena(arena_t *r); +void *arena_alloc(arena_t *r, int sz); + +#endif diff --git a/src/hash_table.c b/src/hash_table.c new file mode 100644 index 0000000..3b635f4 --- /dev/null +++ b/src/hash_table.c @@ -0,0 +1,99 @@ +#include "hash_table.h" + +#include +#include + +#define HTFL_NUL 0 +#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; + init_hash_table(&newht, ht->elemsz, ht->size * 6, ht->hash, ht->eq); + void *iter = hash_table_begin(ht); + while (iter != NULL) { + hash_table_insert(&newht, iter); + iter = hash_table_next(ht, iter); + } + free(ht->buf); + *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->size = 0; + ht->cap = cap; + ht->taken = 0; + ht->begin = NULL; + ht->elemsz = elemsz; + ht->hash = hash; + ht->eq = eq; +} + +bool hash_table_insert(hash_table_t *ht, void *elem) { + if (ht->taken + 1 > ht->cap / 2) { + rebuild(ht); + } + 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; + } + } + memcpy(pos, elem, ht->elemsz); + setflag(pos, HTFL_VAL); + if (pos < ht->begin || ht->begin == NULL) { + ht->begin = pos; + } + return true; +} + +void hash_table_remove(hash_table_t *ht, void *iter) { + ht->size--; + setflag(iter, HTFL_DEL); + if (iter == ht->begin) { + ht->begin = hash_table_next(ht, iter); + } +} + +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; + } + } + return NULL; +} + +void *hash_table_begin(hash_table_t *ht) { return ht->begin; } + +void *hash_table_next(hash_table_t *ht, void *iter) { + void *pos = iter; + do { + pos += ht->elemsz + 1; + if (pos >= hash_table_end(ht)) { + return NULL; + } + } while (getflag(pos) != HTFL_VAL); + return pos; +} diff --git a/src/hash_table.h b/src/hash_table.h new file mode 100644 index 0000000..1bf6cfe --- /dev/null +++ b/src/hash_table.h @@ -0,0 +1,29 @@ +#ifndef HTABLE_H_ +#define HTABLE_H_ + +#include +#include + +struct hash_table { + void *buf; + int64_t size; + int64_t cap; + int64_t taken; + void *begin; + int64_t elemsz; + uint64_t (*hash)(void *); + bool (*eq)(void *, void *); +}; +typedef struct hash_table hash_table_t; + +void init_hash_table(hash_table_t *ht, int64_t elemsz, int64_t cap, + uint64_t (*hash)(void *), bool (*eq)(void *, void *)); +bool hash_table_insert(hash_table_t *ht, void *elem); +void hash_table_remove(hash_table_t *ht, void *iter); + +// return a iterator +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); + +#endif diff --git a/src/mmhash.c b/src/mmhash.c new file mode 100644 index 0000000..7897b9e --- /dev/null +++ b/src/mmhash.c @@ -0,0 +1,57 @@ +#include "mmhash.h" + +/*----------------------------------------------------------------------------- +// MurmurHash2, 64-bit versions, by Austin Appleby +// +// The same caveats as 32-bit MurmurHash2 apply here - beware of alignment +// and endian-ness issues if used across multiple platforms. +// +// 64-bit hash for 64-bit platforms +*/ + +uint64_t mmhash(const void *key, int len, uint64_t seed) { + const uint64_t m = 0xc6a4a7935bd1e995LL; + const int r = 47; + + uint64_t h = seed ^ (len * m); + + const uint64_t *data = (const uint64_t *)key; + const uint64_t *end = data + (len / 8); + + while (data != end) { + uint64_t k = *data++; + + k *= m; + k ^= k >> r; + k *= m; + + h ^= k; + h *= m; + } + + const unsigned char *data2 = (const unsigned char *)data; + + switch (len & 7) { + case 7: + h ^= ((uint64_t)data2[6]) << 48; + case 6: + h ^= ((uint64_t)data2[5]) << 40; + case 5: + h ^= ((uint64_t)data2[4]) << 32; + case 4: + h ^= ((uint64_t)data2[3]) << 24; + case 3: + h ^= ((uint64_t)data2[2]) << 16; + case 2: + h ^= ((uint64_t)data2[1]) << 8; + case 1: + h ^= ((uint64_t)data2[0]); + h *= m; + }; + + h ^= h >> r; + h *= m; + h ^= h >> r; + + return h; +} diff --git a/src/mmhash.h b/src/mmhash.h new file mode 100644 index 0000000..a795cb1 --- /dev/null +++ b/src/mmhash.h @@ -0,0 +1,8 @@ +#ifndef ALGDS_HASH_H_ +#define ALGDS_HASH_H_ + +#include + +uint64_t mmhash(const void *key, int len, uint64_t seed); + +#endif diff --git a/src/priority_queue.c b/src/priority_queue.c new file mode 100644 index 0000000..59d64df --- /dev/null +++ b/src/priority_queue.c @@ -0,0 +1,73 @@ +#include "priority_queue.h" + +#include +#include + +void init_priority_queue(priority_queue_t *pq, int cap, int elem_sz, + int (*cmp)(void *, void *)) { + pq->cap = cap; + pq->size = 0; + pq->elemsz = elem_sz; + pq->cmp = cmp; + pq->buf = malloc(cap * elem_sz); +} + +static void swap(priority_queue_t *pq, int a, int b) { + char buf[pq->elemsz]; + void *tmp = buf; + int elemsz = pq->elemsz; + memcpy(tmp, pq->buf + a * elemsz, elemsz); + memcpy(pq->buf + a * elemsz, pq->buf + b * elemsz, elemsz); + memcpy(pq->buf + b * elemsz, tmp, elemsz); +} + +static int cmp(priority_queue_t *pq, int a, int b) { + return pq->cmp(pq->buf + a * pq->elemsz, pq->buf + b * pq->elemsz); +} + +void priority_queue_push(priority_queue_t *pq, void *elem) { + if (pq->size + 1 > pq->cap) { + pq->buf = realloc(pq->buf, 2 * pq->cap * pq->elemsz); + pq->cap *= 2; + } + memcpy(pq->buf + pq->size * pq->elemsz, elem, pq->elemsz); + pq->size++; + if (pq->size == 0) { + return; + } + int i = pq->size - 1; + while (i > 0 && cmp(pq, i, i / 2) > 0) { + swap(pq, i, i / 2); + i /= 2; + } +} + +static void heapify(priority_queue_t *pq, int idx) { + int left, right, largest; + left = 2 * idx + 1; + right = 2 * idx + 2; + if (left < pq->size && cmp(pq, left, idx) > 0) { + largest = left; + } else { + largest = idx; + } + if (right < pq->size && cmp(pq, right, largest) > 0) { + largest = right; + } + if (largest != idx) { + swap(pq, largest, idx); + heapify(pq, largest); + } +} + +void priority_queue_pop(priority_queue_t *pq) { + if (pq->size == 0) return; + memcpy(pq->buf, pq->buf + (pq->size - 1) * pq->elemsz, pq->elemsz); + pq->size -= 1; + heapify(pq, 0); +} + +void *priority_queue_top(priority_queue_t *pq) { + if (pq->size == 0) return NULL; + return pq->buf; +} diff --git a/src/priority_queue.h b/src/priority_queue.h new file mode 100644 index 0000000..895bb42 --- /dev/null +++ b/src/priority_queue.h @@ -0,0 +1,19 @@ +#ifndef PQUEUE_H_ +#define PQUEUE_H_ + +struct priority_queue { + void *buf; + int elemsz; + int cap; + int size; + int (*cmp)(void *, void *); +}; +typedef struct priority_queue priority_queue_t; + +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(); + +#endif diff --git a/src/rb_tree.c b/src/rb_tree.c new file mode 100644 index 0000000..f2bcd0c --- /dev/null +++ b/src/rb_tree.c @@ -0,0 +1,386 @@ +/* + * Copyright 2002 Niels Provos + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "rb_tree.h" + +#define RED 1 +#define BLACK 0 + +static rb_node_t *rb_tree_minmax(rb_tree_t *, int); +void *rb_tree_min(rb_tree_t *head) { return rb_tree_minmax(head, -1); } +void *rb_tree_max(rb_tree_t *head) { return rb_tree_minmax(head, 1); } + +void *rb_tree_left(void *node) { + rb_node_t *elm = node; + if (node == NULL) return NULL; + return elm->entry.rbe_left; +} +void *rb_tree_right(void *node) { + rb_node_t *elm = node; + if (node == NULL) return NULL; + return elm->entry.rbe_right; +} +void *rb_tree_parent(void *node) { + rb_node_t *elm = node; + if (node == NULL) return NULL; + return elm->entry.rbe_parent; +} + +static void augment(rb_tree_t *head, rb_node_t *elm) { + if (head->augment != NULL) head->augment(elm); +} + +static void rb_tree_insert_color(rb_tree_t *head, rb_node_t *elm); +static void rb_tree_remove_color(rb_tree_t *head, rb_node_t *parent, + rb_node_t *elm); + +static void rotate_left(rb_tree_t *head, rb_node_t *elm) { + rb_node_t *tmp = elm->entry.rbe_right; + if ((elm->entry.rbe_right = tmp->entry.rbe_left)) { + tmp->entry.rbe_left->entry.rbe_parent = elm; + } + augment(head, elm); + if ((tmp->entry.rbe_parent = elm->entry.rbe_parent)) { + if (elm == elm->entry.rbe_parent->entry.rbe_left) + elm->entry.rbe_parent->entry.rbe_left = tmp; + else + elm->entry.rbe_parent->entry.rbe_right = tmp; + } else { + head->rbh_root = tmp; + } + tmp->entry.rbe_left = elm; + elm->entry.rbe_parent = tmp; + augment(head, tmp); + if (tmp->entry.rbe_parent) { + augment(head, tmp->entry.rbe_parent); + } +} + +static void rotate_right(rb_tree_t *head, rb_node_t *elm) { + rb_node_t *tmp = elm->entry.rbe_left; + if ((elm->entry.rbe_left = tmp->entry.rbe_right)) { + tmp->entry.rbe_right->entry.rbe_parent = elm; + } + augment(head, elm); + if ((tmp->entry.rbe_parent = elm->entry.rbe_parent)) { + if (elm == elm->entry.rbe_parent->entry.rbe_left) + elm->entry.rbe_parent->entry.rbe_left = tmp; + else + elm->entry.rbe_parent->entry.rbe_right = tmp; + } else { + head->rbh_root = tmp; + } + tmp->entry.rbe_right = elm; + elm->entry.rbe_parent = tmp; + augment(head, tmp); + if (tmp->entry.rbe_parent) { + augment(head, tmp->entry.rbe_parent); + } +} + +static void rb_tree_insert_color(rb_tree_t *head, rb_node_t *elm) { + rb_node_t *parent, *gparent, *tmp; + while ((parent = elm->entry.rbe_parent) && parent->entry.rbe_color == 1) { + gparent = parent->entry.rbe_parent; + if (parent == gparent->entry.rbe_left) { + tmp = gparent->entry.rbe_right; + if (tmp && tmp->entry.rbe_color == 1) { + tmp->entry.rbe_color = BLACK; + parent->entry.rbe_color = BLACK; + gparent->entry.rbe_color = RED; + elm = gparent; + continue; + } + if (parent->entry.rbe_right == elm) { + rotate_left(head, parent); + tmp = parent; + parent = elm; + elm = tmp; + } + parent->entry.rbe_color = BLACK; + gparent->entry.rbe_color = RED; + rotate_right(head, gparent); + } else { + tmp = gparent->entry.rbe_left; + if (tmp && tmp->entry.rbe_color == 1) { + tmp->entry.rbe_color = BLACK; + parent->entry.rbe_color = BLACK; + gparent->entry.rbe_color = RED; + ; + elm = gparent; + continue; + } + if (parent->entry.rbe_left == elm) { + rotate_right(head, parent); + tmp = parent; + parent = elm; + elm = tmp; + } + parent->entry.rbe_color = BLACK; + gparent->entry.rbe_color = RED; + rotate_left(head, gparent); + } + } + head->rbh_root->entry.rbe_color = BLACK; +} + +static void rb_tree_remove_color(rb_tree_t *head, rb_node_t *parent, + rb_node_t *elm) { + rb_node_t *tmp; + while ((elm == NULL || elm->entry.rbe_color == 0) && + elm != head->rbh_root) { + if (parent->entry.rbe_left == elm) { + tmp = parent->entry.rbe_right; + if (tmp->entry.rbe_color == 1) { + tmp->entry.rbe_color = BLACK; + parent->entry.rbe_color = RED; + rotate_left(head, parent); + tmp = parent->entry.rbe_right; + } + if ((tmp->entry.rbe_left == NULL || + tmp->entry.rbe_left->entry.rbe_color == 0) && + (tmp->entry.rbe_right == NULL || + tmp->entry.rbe_right->entry.rbe_color == 0)) { + tmp->entry.rbe_color = RED; + elm = parent; + parent = elm->entry.rbe_parent; + } else { + if (tmp->entry.rbe_right == NULL || + tmp->entry.rbe_right->entry.rbe_color == 0) { + rb_node_t *oleft; + if ((oleft = tmp->entry.rbe_left)) + oleft->entry.rbe_color = BLACK; + tmp->entry.rbe_color = RED; + rotate_right(head, tmp); + tmp = parent->entry.rbe_right; + } + tmp->entry.rbe_color = parent->entry.rbe_color; + parent->entry.rbe_color = BLACK; + if (tmp->entry.rbe_right) + tmp->entry.rbe_right->entry.rbe_color = BLACK; + rotate_left(head, parent); + elm = head->rbh_root; + break; + } + } else { + tmp = parent->entry.rbe_left; + if (tmp->entry.rbe_color == 1) { + tmp->entry.rbe_color = BLACK; + parent->entry.rbe_color = RED; + rotate_right(head, parent); + tmp = parent->entry.rbe_left; + } + if ((tmp->entry.rbe_left == NULL || + tmp->entry.rbe_left->entry.rbe_color == 0) && + (tmp->entry.rbe_right == NULL || + tmp->entry.rbe_right->entry.rbe_color == 0)) { + tmp->entry.rbe_color = RED; + elm = parent; + parent = elm->entry.rbe_parent; + } else { + if (tmp->entry.rbe_left == NULL || + tmp->entry.rbe_left->entry.rbe_color == 0) { + rb_node_t *oright; + if ((oright = tmp->entry.rbe_right)) + oright->entry.rbe_color = BLACK; + tmp->entry.rbe_color = RED; + rotate_left(head, tmp); + tmp = parent->entry.rbe_left; + } + tmp->entry.rbe_color = parent->entry.rbe_color; + parent->entry.rbe_color = BLACK; + if (tmp->entry.rbe_left) + tmp->entry.rbe_left->entry.rbe_color = BLACK; + rotate_right(head, parent); + elm = head->rbh_root; + break; + } + } + } + if (elm) elm->entry.rbe_color = BLACK; +} + +void rb_tree_remove(rb_tree_t *head, void *elmv) { + rb_node_t *elm = elmv; + rb_node_t *child, *parent; + int color; + if (elm->entry.rbe_left == NULL) + child = elm->entry.rbe_right; + else if (elm->entry.rbe_right == NULL) + child = elm->entry.rbe_left; + else { + rb_node_t *old = elm, *left; + elm = elm->entry.rbe_right; + while ((left = elm->entry.rbe_left)) + elm = left; + child = elm->entry.rbe_right; + parent = elm->entry.rbe_parent; + color = elm->entry.rbe_color; + if (child) child->entry.rbe_parent = parent; + if (parent) { + if (parent->entry.rbe_left == elm) + parent->entry.rbe_left = child; + else + parent->entry.rbe_right = child; + augment(head, parent); + } else + head->rbh_root = child; + if (elm->entry.rbe_parent == old) parent = elm; + elm->entry = old->entry; + if (old->entry.rbe_parent) { + if ((old->entry.rbe_parent)->entry.rbe_left == old) + (old->entry.rbe_parent)->entry.rbe_left = elm; + else + (old->entry.rbe_parent)->entry.rbe_right = elm; + augment(head, old->entry.rbe_parent); + } else + head->rbh_root = elm; + old->entry.rbe_left->entry.rbe_parent = elm; + if (old->entry.rbe_right) old->entry.rbe_right->entry.rbe_parent = elm; + if (parent) { + left = parent; + if (head->augment != NULL) { + do { + augment(head, left); + } while ((left = left->entry.rbe_parent)); + } + } + goto color; + } + parent = elm->entry.rbe_parent; + color = elm->entry.rbe_color; + if (child) child->entry.rbe_parent = parent; + if (parent) { + if (parent->entry.rbe_left == elm) + parent->entry.rbe_left = child; + else + parent->entry.rbe_right = child; + rb_node_t *goback = parent; + if (head->augment != NULL) { + do { + augment(head, goback); + } while ((goback = goback->entry.rbe_parent)); + } + } else + head->rbh_root = child; +color: + if (color == 0) rb_tree_remove_color(head, parent, child); +} + +void *rb_tree_insert(rb_tree_t *head, void *elmv) { + rb_node_t *elm = elmv; + rb_node_t *tmp; + rb_node_t *parent = NULL; + int comp = 0; + tmp = head->rbh_root; + while (tmp) { + parent = tmp; + comp = head->cmp((void *)elm->content, (void *)parent->content); + if (comp < 0) + tmp = tmp->entry.rbe_left; + else if (comp > 0) + tmp = tmp->entry.rbe_right; + else + return tmp; + } + elm->entry.rbe_parent = parent; + elm->entry.rbe_left = elm->entry.rbe_right = NULL; + elm->entry.rbe_color = RED; + if (parent != NULL) { + if (comp < 0) + parent->entry.rbe_left = elm; + else + parent->entry.rbe_right = elm; + rb_node_t *goback = parent; + if (head->augment != NULL) { + do { + augment(head, goback); + } while ((goback = goback->entry.rbe_parent)); + } + } else + head->rbh_root = elm; + rb_tree_insert_color(head, elm); + return (NULL); +} + +void *rb_tree_find(rb_tree_t *head, void *key) { + rb_node_t *tmp = head->rbh_root; + int comp; + while (tmp) { + comp = head->cmp(key, (void *)tmp->content); + if (comp < 0) + tmp = tmp->entry.rbe_left; + else if (comp > 0) + tmp = tmp->entry.rbe_right; + else + return tmp; + } + return (NULL); +} + +void *rb_tree_next(rb_tree_t *head, void *elmv) { + rb_node_t *elm = elmv; + if (elm->entry.rbe_right) { + elm = elm->entry.rbe_right; + while (elm->entry.rbe_left) + elm = elm->entry.rbe_left; + } else { + if (elm->entry.rbe_parent && + (elm == (elm->entry.rbe_parent)->entry.rbe_left)) + elm = elm->entry.rbe_parent; + else { + while (elm->entry.rbe_parent && + (elm == (elm->entry.rbe_parent)->entry.rbe_right)) + elm = elm->entry.rbe_parent; + elm = elm->entry.rbe_parent; + } + } + return elm; +} + +static rb_node_t *rb_tree_minmax(rb_tree_t *head, int val) { + rb_node_t *tmp = head->rbh_root; + rb_node_t *parent = NULL; + while (tmp) { + parent = tmp; + if (val < 0) + tmp = tmp->entry.rbe_left; + else + tmp = tmp->entry.rbe_right; + } + return parent; +}; + +static void destroy_rb_tree_impl(rb_node_t *node, void (*free_cb)(void *)) { + if (node == NULL) return; + if (free_cb != NULL) free_cb(node->content); + destroy_rb_tree_impl(node->entry.rbe_left, free_cb); + destroy_rb_tree_impl(node->entry.rbe_right, free_cb); + free(node); +} + +void destroy_rb_tree(rb_tree_t *head, void (*free_cb)(void *)) { + destroy_rb_tree_impl(head->rbh_root, free_cb); +} diff --git a/src/rb_tree.h b/src/rb_tree.h new file mode 100644 index 0000000..936cd34 --- /dev/null +++ b/src/rb_tree.h @@ -0,0 +1,64 @@ +/* + * Copyright 2002 Niels Provos + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef RB_TREE_H_ +#define RB_TREE_H_ + +#include + +struct rb_node { + struct { + struct rb_node *rbe_left; + struct rb_node *rbe_right; + struct rb_node *rbe_parent; + int rbe_color; + } entry; + char content[0]; +}; +typedef struct rb_node rb_node_t; + +struct rb_tree { + rb_node_t *rbh_root; + int (*cmp)(void *k1, void *k2); + void (*augment)(void *elm); +}; +typedef struct rb_tree rb_tree_t; + +void rb_tree_remove(rb_tree_t *, void *iter); + +// return a iterator +void *rb_tree_insert(rb_tree_t *, void *treenode); +void *rb_tree_find(rb_tree_t *, void *val); +void *rb_tree_next(rb_tree_t *, void *iter); +void *rb_tree_min(rb_tree_t *); +void *rb_tree_max(rb_tree_t *); +void *rb_tree_left(void *node); +void *rb_tree_right(void *node); +void *rb_tree_parent(void *node); + +void destroy_rb_tree(rb_tree_t *, void (*freeCb)(void *)); + +#endif + diff --git a/src/str.c b/src/str.c new file mode 100644 index 0000000..22aebac --- /dev/null +++ b/src/str.c @@ -0,0 +1,131 @@ +#include "str.h" + +#include +#include +#include +#include +#include +#include +#include + +char **str_split(char *str, char delim) { + char **ret; + + if (str == NULL) return NULL; + if (*str == '\n') { + ret = malloc(sizeof(char *)); + *ret = NULL; + return ret; + } + int count = 0; + char *begin = str; + for (char *p = str; *p != '\0'; p++) { + if (*p != delim && !(delim == '\0' && isspace(*p))) { + continue; + } + int size = p - begin; + if (size > 0) count++; + } + count++; + ret = malloc((count + 1) * sizeof(char *)); + memset(ret, 0, (count + 1) * sizeof(char *)); + + begin = str; + int i = 0; + bool finished = false; + for (char *p = str; !finished; p++) { + if (*p == '\0') finished = true; + if (*p != delim && *p != '\0' && !(delim == '\0' && isspace(*p))) { + continue; + } + int size = p - begin; + if (size == 0) { + begin = p + 1; + continue; + } + char *buf = malloc(sizeof(char) * (size + 1)); + buf[size] = '\0'; + memcpy(buf, begin, size * sizeof(char)); + begin = p + 1; + ret[i] = buf; + i++; + } + return ret; +} + +void destroy_str_list(char **list) { + char **p = list; + while (*p != NULL) { + free(*p); + p++; + } + free(list); +} + +char *str_strip(char *str) { + if (str == NULL) return NULL; + int len = strlen(str); + char *begin = str; + char *end = str + len - 1; + while (isspace(*begin) && begin < end) { + begin++; + } + while (isspace(*end) && end >= begin) { + end--; + } + len = end - begin + 1; + char *buf = malloc(sizeof(char) * (len) + 1); + buf[len] = '\0'; + memcpy(buf, begin, len); + return buf; +} + +void init_str_builder(str_builder_t *sb) { + *sb = (str_builder_t){.size = 0, .cap = 16}; + sb->buf = malloc(sizeof(char) * 17); +} + +static void sb_reserve(str_builder_t *sb, int extra) { + if (sb->size + extra <= sb->cap) { + return; + } + int new_cap = (sb->size + extra) * 2; + sb->buf = realloc(sb->buf, new_cap + 1); + memset(sb->buf + sb->cap, 0, new_cap - sb->cap + 1); + sb->cap = new_cap; +} + +void str_builder_append(str_builder_t *sb, char *format, ...) { + va_list va1; + va_list va2; + va_start(va1, format); + va_copy(va2, va1); + int size = vsnprintf(NULL, 0, format, va1); + sb_reserve(sb, size); + vsnprintf(sb->buf + sb->size, sb->cap - sb->size + 1, format, va2); +} + +void str_builder_append_char(str_builder_t *sb, char c) { + sb_reserve(sb, 1); + sb->buf[sb->size] = c; + sb->size++; +} + +char *fgetline(FILE *fp) { + str_builder_t sb; + init_str_builder(&sb); + while (true) { + int c = fgetc(fp); + if (c == EOF && sb.size == 0) return NULL; + if (c != EOF) str_builder_append_char(&sb, c); + if (c == EOF || c == '\n') return sb.buf; + } + return NULL; +} + +int fpeek(FILE *fp) { + int c = fgetc(fp); + if (c == EOF) return c; + ungetc(c, fp); + return c; +} diff --git a/src/str.h b/src/str.h new file mode 100644 index 0000000..441451e --- /dev/null +++ b/src/str.h @@ -0,0 +1,24 @@ +#ifndef ALGDS_STR_H_ +#define ALGDS_STR_H_ + +#include + +char *str_strip(char *str); +char **str_split(char *str, char delim); +void destroy_str_list(char **list); + +struct str_builder { + char *buf; + int size; + int cap; +}; +typedef struct str_builder str_builder_t; + +void init_str_builder(str_builder_t *sb); +void str_builder_append(str_builder_t *sb, char *format, ...); +void str_builder_append_char(str_builder_t *sb, char c); + +char *fgetline(FILE *fp); +int fpeek(FILE *fp); + +#endif diff --git a/tests/test_augment_rbtree.c b/tests/test_augment_rbtree.c new file mode 100644 index 0000000..0389405 --- /dev/null +++ b/tests/test_augment_rbtree.c @@ -0,0 +1,129 @@ +#include +#include +#include +#include + +#include "rb_tree.h" + +typedef struct { + rb_node_t node; + int key; + int value; + int amount; +} IntIntEntry; + +static int cmpfunc(void *x, void *y) { + int *a = x, *b = y; + return *a < *b ? -1 : *a > *b; +} + +static void augment(void *n) { + IntIntEntry *node = n; + IntIntEntry *left = rb_tree_left(node); + IntIntEntry *right = rb_tree_right(node); + node->amount = 1; + node->amount += left == NULL ? 0 : left->amount; + node->amount += right == NULL ? 0 : right->amount; +} + +static void test_largedata(); + +static int max(int a, int b) { return a > b ? a : b; } + +int depth(void *n) { + rb_node_t *node = n; + if (node == NULL) return 0; + return max(depth(node->entry.rbe_left), depth(node->entry.rbe_right)) + 1; +} + +void checkaugment(IntIntEntry *node) { + if (node == NULL) return; + IntIntEntry *left = rb_tree_left(node); + IntIntEntry *right = rb_tree_right(node); + int amount = 1; + amount += left == NULL ? 0 : left->amount; + amount += right == NULL ? 0 : right->amount; + assert(amount == node->amount); + checkaugment(left); + checkaugment(right); +} + +int main() { + printf("[TEST] augment rbtree\n"); + test_largedata(); + printf("[PASS] augment rbtree\n"); + return 0; +} + +#define TESTSZ 10000 +int input[TESTSZ]; + +void shuffle(int *input, int n) { + for (int i = n - 1; i > 0; i--) { + int j = rand() % i; + int tmp = input[i]; + input[i] = input[j]; + input[j] = tmp; + } +} + +static void test_largedata() { + // generate random input + time_t t; + srand((unsigned)time(&t)); + for (int i = 0; i < TESTSZ; i++) { + input[i] = i; + } + shuffle(input, TESTSZ); + // insert + rb_tree_t tree = {NULL, cmpfunc, augment}; + IntIntEntry *n; + for (int i = 0; i < TESTSZ; i++) { + n = malloc(sizeof(*n)); + n->key = input[i]; + n->value = input[i]; + n->amount = 1; + rb_tree_insert(&tree, n); + } + // check tree validity + int d = depth(tree.rbh_root); + assert(d >= 13 && d <= 28); + IntIntEntry *root = (IntIntEntry *)(tree.rbh_root); + assert(root->amount == TESTSZ); + checkaugment(root); + IntIntEntry *iter = rb_tree_min(&tree); + int i = 0; + for (; iter != NULL; iter = rb_tree_next(&tree, iter)) { + assert(iter->key == i); + i++; + } + // delete when: key % 3 != 0 + memset(input, 0, sizeof(int) * TESTSZ); + int count = 0; + for (int i = 0; i < TESTSZ; i++) { + if (i % 3 != 0) { + input[count] = i; + } else { + continue; + } + count++; + } + shuffle(input, count); + for (int i = 0; i < count; i++) { + IntIntEntry *iter = rb_tree_find(&tree, &input[i]); + assert(iter != NULL); + rb_tree_remove(&tree, iter); + } + // check tree validity + d = depth(tree.rbh_root); + assert(d >= 11 && d <= 24); + root = (IntIntEntry *)(tree.rbh_root); + assert(root->amount == TESTSZ - count); + checkaugment(root); + iter = rb_tree_min(&tree); + i = 0; + for (; iter != NULL; iter = rb_tree_next(&tree, iter)) { + assert(iter->key == i * 3); + i++; + } +} diff --git a/tests/test_htable.c b/tests/test_htable.c new file mode 100644 index 0000000..310d141 --- /dev/null +++ b/tests/test_htable.c @@ -0,0 +1,71 @@ +#include +#include +#include +#include + +#include "hash_table.h" +#include "mmhash.h" + +static uint64_t hash(void *i) { return mmhash(i, sizeof(int), 0); } + +static bool eq(void *x, void *y) { + int *a = x, *b = y; + return *a == *b; +} + +bool found[10000]; + +int main() { + printf("[TEST] htable\n"); + + hash_table_t ht; + init_hash_table(&ht, sizeof(int), -1, hash, eq); + for (int i = 0; i < 10000; i++) { + hash_table_insert(&ht, &i); + assert(ht.size == i + 1); + assert(ht.taken == i + 1); + assert(ht.cap >= i + 1); + } + + for (int i = 0; i < 10000; i++) { + assert(hash_table_find(&ht, &i) != NULL); + int t = 10000 + i; + assert(hash_table_find(&ht, &t) == NULL); + } + + memset(found, 0, sizeof(bool) * 10000); + int *iter = hash_table_begin(&ht); + while (iter != NULL) { + found[*iter] = true; + iter = hash_table_next(&ht, iter); + } + for (int i = 0; i < 10000; i++) { + assert(found[i]); + } + + for (int i = 0; i < 5000; i++) { + int *iter = hash_table_find(&ht, &i); + hash_table_remove(&ht, iter); + } + for (int i = 0; i < 5000; i++) { + assert(hash_table_find(&ht, &i) == NULL); + int t = 5000 + i; + assert(hash_table_find(&ht, &t) != NULL); + } + + for (int i = 0; i < 5000; i++) { + hash_table_insert(&ht, &i); + } + + memset(found, 0, sizeof(bool) * 10000); + iter = hash_table_begin(&ht); + while (iter != NULL) { + found[*iter] = true; + iter = hash_table_next(&ht, iter); + } + for (int i = 0; i < 10000; i++) { + assert(found[i]); + } + + printf("[PASS] htable\n"); +} diff --git a/tests/test_mmhash.c b/tests/test_mmhash.c new file mode 100644 index 0000000..3a9895c --- /dev/null +++ b/tests/test_mmhash.c @@ -0,0 +1,15 @@ +#include +#include +#include + +#include "mmhash.h" + +int main() { + printf("[TEST] hash\n"); + char buf[] = "hello, world\n"; + uint64_t hash0 = mmhash(buf, strlen(buf), 0); + uint64_t hash1 = mmhash(buf, 3, 0); + assert(hash0 != hash1); + printf("[PASS] hash\n"); + return 0; +} diff --git a/tests/test_pque.c b/tests/test_pque.c new file mode 100644 index 0000000..01e6e1c --- /dev/null +++ b/tests/test_pque.c @@ -0,0 +1,40 @@ +#include +#include +#include + +#include "priority_queue.h" + +int intcmp(void *_a, void *_b) { + int a = *(int *)_a; + int b = *(int *)_b; + if (a < b) return 1; + if (a > b) return -1; + return 0; +} + +int main() { + printf("[TEST] pque\n"); + priority_queue_t pq; + init_priority_queue(&pq, 3, sizeof(int), intcmp); + int elems[10] = {1, 3, 2, 4, 6, 5, 9, 7, 8, 10}; + for (int i = 0; i < 10; i++) { + int e = elems[i]; + priority_queue_push(&pq, &e); + } + for (int i = 1; i < 11; i++) { + int *top = priority_queue_top(&pq); + assert(i == *top); + priority_queue_pop(&pq); + } + assert(priority_queue_top(&pq) == NULL); + int elems2[10] = {10, 8, 7, 9, 5, 6, 4, 2, 3, 1}; + int expected[10] = {10, 8, 7, 7, 5, 5, 4, 2, 2, 1}; + for (int i = 0; i < 10; i++) { + int e = elems2[i]; + priority_queue_push(&pq, &e); + int *top = priority_queue_top(&pq); + assert(*top == expected[i]); + } + printf("[PASS] pque\n"); + return 0; +} diff --git a/tests/test_rbtree.c b/tests/test_rbtree.c new file mode 100644 index 0000000..b1fbc32 --- /dev/null +++ b/tests/test_rbtree.c @@ -0,0 +1,128 @@ +#include +#include +#include +#include + +#include "rb_tree.h" + +typedef struct { + rb_node_t node; + int key; + int value; +} IntIntEntry; + +static int cmpfunc(void *x, void *y) { + int *a = x, *b = y; + return *a < *b ? -1 : *a > *b; +} + +static void test_largedata(); + +static int max(int a, int b) { return a > b ? a : b; } + +int depth(void *n) { + rb_node_t *node = n; + if (node == NULL) return 0; + return max(depth(node->entry.rbe_left), depth(node->entry.rbe_right)) + 1; +} + +int main() { + printf("[TEST] rbtree\n"); + rb_tree_t tree = {NULL, cmpfunc, NULL}; + IntIntEntry *n; + + int a[5] = {1, 2, 3, 4, 5}; + for (int i = 0; i < 5; i++) { + n = malloc(sizeof(*n)); + n->key = a[i]; + n->value = i; + rb_tree_insert(&tree, n); + } + + int find = 3; + IntIntEntry *iter; + iter = rb_tree_find(&tree, &find); + assert(iter->key == 3); + + rb_tree_remove(&tree, iter); + free(iter); + + iter = rb_tree_min(&tree); + int expected[4] = {1, 2, 4, 5}; + int i = 0; + for (; iter != NULL; iter = rb_tree_next(&tree, iter)) { + assert(iter->key == expected[i]); + i++; + } + + destroy_rb_tree(&tree, NULL); + test_largedata(); + printf("[PASS] rbtree\n"); + return 0; +} + +#define TESTSZ 10000 +int input[TESTSZ]; + +void shuffle(int *input, int n) { + for (int i = n - 1; i > 0; i--) { + int j = rand() % i; + int tmp = input[i]; + input[i] = input[j]; + input[j] = tmp; + } +} + +static void test_largedata() { + // generate random input + time_t t; + srand((unsigned)time(&t)); + for (int i = 0; i < TESTSZ; i++) { + input[i] = i; + } + shuffle(input, TESTSZ); + // insert + rb_tree_t tree = {NULL, cmpfunc, NULL}; + IntIntEntry *n; + for (int i = 0; i < TESTSZ; i++) { + n = malloc(sizeof(*n)); + n->key = input[i]; + n->value = input[i]; + rb_tree_insert(&tree, n); + } + // check tree validity + int d = depth(tree.rbh_root); + assert(d >= 13 && d <= 28); + IntIntEntry *iter = rb_tree_min(&tree); + int i = 0; + for (; iter != NULL; iter = rb_tree_next(&tree, iter)) { + assert(iter->key == i); + i++; + } + // delete when: key % 3 != 0 + memset(input, 0, sizeof(int) * TESTSZ); + int count = 0; + for (int i = 0; i < TESTSZ; i++) { + if (i % 3 != 0) { + input[count] = i; + } else { + continue; + } + count++; + } + shuffle(input, count); + for (int i = 0; i < count; i++) { + IntIntEntry *iter = rb_tree_find(&tree, &input[i]); + assert(iter != NULL); + rb_tree_remove(&tree, iter); + } + // check tree validity + d = depth(tree.rbh_root); + assert(d >= 11 && d <= 24); + iter = rb_tree_min(&tree); + i = 0; + for (; iter != NULL; iter = rb_tree_next(&tree, iter)) { + assert(iter->key == i * 3); + i++; + } +} diff --git a/tests/test_str.c b/tests/test_str.c new file mode 100644 index 0000000..85e4f31 --- /dev/null +++ b/tests/test_str.c @@ -0,0 +1,114 @@ +#include +#include +#include +#include + +#include + +void test_str_split() { + char *s = "abc 123 233 xyz"; + char **list = str_split(s, ' '); + assert(list[4] == NULL); + assert(list[3] != NULL); + assert(strcmp(list[0], "abc") == 0); + assert(strcmp(list[3], "xyz") == 0); + destroy_str_list(list); + + s = "abc 123 233 xyz"; + list = str_split(s, ' '); + assert(list[4] == NULL); + assert(list[3] != NULL); + assert(strcmp(list[0], "abc") == 0); + assert(strcmp(list[3], "xyz") == 0); + destroy_str_list(list); + + s = " abc 123 233 xyz"; + list = str_split(s, ' '); + assert(list[4] == NULL); + assert(list[3] != NULL); + assert(strcmp(list[0], "abc") == 0); + assert(strcmp(list[3], "xyz") == 0); + destroy_str_list(list); + + s = " abc \t 123\n 233\nxyz"; + list = str_split(s, '\0'); + assert(list[4] == NULL); + assert(list[3] != NULL); + assert(strcmp(list[0], "abc") == 0); + assert(strcmp(list[3], "xyz") == 0); + destroy_str_list(list); + + s = "a"; + list = str_split(s, ' '); + assert(list[1] == NULL); + assert(list[0] != NULL); + assert(strcmp(list[0], "a") == 0); + destroy_str_list(list); + + s = ""; + list = str_split(s, ' '); + assert(list[0] == NULL); + destroy_str_list(list); + + s = " "; + list = str_split(s, ' '); + assert(list[0] == NULL); + destroy_str_list(list); +} + +void test_str_strip() { + char *s; + + s = str_strip("hello "); + assert(strcmp(s, "hello") == 0); + + s = str_strip("hello"); + assert(strcmp(s, "hello") == 0); + + s = str_strip("\nhello "); + assert(strcmp(s, "hello") == 0); + + s = str_strip("\nhello"); + assert(strcmp(s, "hello") == 0); + + s = str_strip(""); + assert(strcmp(s, "") == 0); + + s = str_strip("\n\t "); + assert(strcmp(s, "") == 0); + + s = str_strip(" "); + assert(strcmp(s, "") == 0); +} + +void test_str_bulider() { + str_builder_t sb; + init_str_builder(&sb); + + str_builder_append(&sb, "%s", "hello"); + assert(sb.size == 5); + assert(strcmp(sb.buf, "hello") == 0); + assert(strlen(sb.buf) == 5); + + str_builder_append(&sb, "hello"); + assert(sb.size == 10); + assert(strcmp(sb.buf, "hellohello") == 0); + + str_builder_append(&sb, "%c1", 'c'); + assert(sb.size == 12); + assert(strcmp(sb.buf, "hellohelloc1") == 0); + + str_builder_append_char(&sb, 'x'); + assert(sb.size == 13); + assert(strcmp(sb.buf, "hellohelloc1x") == 0); +} + +int main() { + printf("[TEST] str\n"); + + test_str_split(); + test_str_strip(); + + printf("[PASS] str\n"); + return 0; +} -- cgit v1.0