From 999fcf0f7655c03265c222cc67617f0f510979bf Mon Sep 17 00:00:00 2001 From: Mistivia Date: Tue, 22 Jul 2025 15:28:30 +0800 Subject: change dir structure --- Makefile | 8 +- basic_traits.c | 76 ++++++++++ basic_traits.h | 27 ++++ hash_table.c | 119 ++++++++++++++++ hash_table.h | 105 ++++++++++++++ list.c | 3 + list.h | 134 ++++++++++++++++++ mmhash.c | 57 ++++++++ mmhash.h | 8 ++ pqueue.c | 17 +++ pqueue.h | 79 +++++++++++ rb_tree.h | 143 +++++++++++++++++++ sort.c | 14 ++ sort.h | 54 ++++++++ src/basic_traits.c | 76 ---------- src/basic_traits.h | 27 ---- src/hash_table.c | 119 ---------------- src/hash_table.h | 105 -------------- src/list.c | 3 - src/list.h | 134 ------------------ src/mmhash.c | 57 -------- src/mmhash.h | 8 -- src/pqueue.c | 17 --- src/pqueue.h | 79 ----------- src/rb_tree.h | 143 ------------------- src/sort.c | 14 -- src/sort.h | 54 -------- src/str.c | 137 ------------------ src/str.h | 24 ---- src/tree_map.c | 398 ----------------------------------------------------- src/tree_map.h | 148 -------------------- src/type_alias.h | 19 --- src/vec.c | 16 --- src/vec.h | 117 ---------------- str.c | 137 ++++++++++++++++++ str.h | 24 ++++ tree_map.c | 398 +++++++++++++++++++++++++++++++++++++++++++++++++++++ tree_map.h | 148 ++++++++++++++++++++ type_alias.h | 19 +++ vec.c | 16 +++ vec.h | 117 ++++++++++++++++ 41 files changed, 1697 insertions(+), 1701 deletions(-) create mode 100644 basic_traits.c create mode 100644 basic_traits.h create mode 100644 hash_table.c create mode 100644 hash_table.h create mode 100644 list.c create mode 100644 list.h create mode 100644 mmhash.c create mode 100644 mmhash.h create mode 100644 pqueue.c create mode 100644 pqueue.h create mode 100644 rb_tree.h create mode 100644 sort.c create mode 100644 sort.h delete mode 100644 src/basic_traits.c delete mode 100644 src/basic_traits.h delete mode 100644 src/hash_table.c delete mode 100644 src/hash_table.h delete mode 100644 src/list.c delete mode 100644 src/list.h delete mode 100644 src/mmhash.c delete mode 100644 src/mmhash.h delete mode 100644 src/pqueue.c delete mode 100644 src/pqueue.h delete mode 100644 src/rb_tree.h delete mode 100644 src/sort.c delete mode 100644 src/sort.h delete mode 100644 src/str.c delete mode 100644 src/str.h delete mode 100644 src/tree_map.c delete mode 100644 src/tree_map.h delete mode 100644 src/type_alias.h delete mode 100644 src/vec.c delete mode 100644 src/vec.h create mode 100644 str.c create mode 100644 str.h create mode 100644 tree_map.c create mode 100644 tree_map.h create mode 100644 type_alias.h create mode 100644 vec.c create mode 100644 vec.h diff --git a/Makefile b/Makefile index 3811231..6ae975c 100644 --- a/Makefile +++ b/Makefile @@ -9,17 +9,13 @@ else cflags = -flto -O2 endif -src = $(shell ls src/*.c) +src = $(shell ls *.c) obj = $(src:.c=.o) tests=$(shell ls tests/*.c) tests_bin=$(tests:.c=.bin) all: libalgds.a - mkdir -p build/lib - mkdir -p build/include/algds - cp src/*.h build/include/algds - cp libalgds.a build/lib/ libalgds.a: $(obj) ar cr $@ $^ @@ -33,7 +29,7 @@ $(obj):%.o:%.c $(cc) -c $(cflags) $< -MD -MF $@.d -o $@ $(tests_bin):%.bin:%.c libalgds.a - $(cc) $(cflags) -Isrc/ $< libalgds.a -MD -MF $@.d -o $@ + $(cc) $(cflags) -I./ $< libalgds.a -MD -MF $@.d -o $@ clean: -rm -rf build/ diff --git a/basic_traits.c b/basic_traits.c new file mode 100644 index 0000000..5d2a8fb --- /dev/null +++ b/basic_traits.c @@ -0,0 +1,76 @@ +#include "basic_traits.h" + +#include +#include + +#include "mmhash.h" + +#define BASIC_TRAITS_IMPL(T) \ + bool T##_eq(T lhs, T rhs) { \ + return lhs == rhs; \ + } \ + int T##_cmp(T lhs, T rhs) { \ + if (lhs == rhs) return 0; \ + if (lhs < rhs) return -1; \ + return 1; \ + } \ + uint64_t T##_hash(T x) { \ + return mmhash(&x, sizeof(T), 0); \ + } \ + +BASIC_TRAITS_IMPL(Char); +BASIC_TRAITS_IMPL(Bool); +BASIC_TRAITS_IMPL(Int); +BASIC_TRAITS_IMPL(Long); +BASIC_TRAITS_IMPL(UInt); +BASIC_TRAITS_IMPL(ULong); +BASIC_TRAITS_IMPL(Double); +BASIC_TRAITS_IMPL(Float); +BASIC_TRAITS_IMPL(VoidPtr); + +void Char_show(Char self, FILE* fp) { + fprintf(fp, "%c", self); +} +void Bool_show(Bool self, FILE* fp) { + if (self) fprintf(fp, "true"); + else fprintf(fp, "false"); +} +void Int_show(Int self, FILE* fp) { + fprintf(fp, "%"PRId32, self); +} +void Long_show(Long self, FILE* fp) { + fprintf(fp, "%"PRId64, self); +} +void UInt_show(UInt self, FILE* fp) { + fprintf(fp, "%"PRIu32, self); +} +void ULong_show(ULong self, FILE* fp) { + fprintf(fp, "%"PRIu64, self); +} +void VoidPtr_show(VoidPtr self, FILE* fp) { + fprintf(fp, "%p", self); +} +void Double_show(Double self, FILE* fp) { + fprintf(fp, "%lf", self); +} +void Float_show(Float self, FILE* fp) { + fprintf(fp, "%f", self); +} +void String_show(String self, FILE* fp) { + fprintf(fp, "%s", self); +} + +bool String_eq(String lhs, String rhs) { + return strcmp(lhs, rhs) == 0; +} + +int String_cmp(String lhs, String rhs) { + return strcmp(lhs, rhs); +} + +uint64_t String_hash(String x) { + size_t len = strlen(x); + return mmhash(x, len, 0); +} + + diff --git a/basic_traits.h b/basic_traits.h new file mode 100644 index 0000000..45aaba9 --- /dev/null +++ b/basic_traits.h @@ -0,0 +1,27 @@ +#ifndef ALGDS_BAISC_TRAITS_H_ +#define ALGDS_BAISC_TRAITS_H_ + +#include + +#include "type_alias.h" + +// basic traits +#define BASIC_TRAITS_DEF(T) \ + Bool T##_eq(T lhs, T rhs); \ + Int T##_cmp(T lhs, T rhs); \ + uint64_t T##_hash(T x); \ + void T##_show(T x, FILE* fp); \ + +BASIC_TRAITS_DEF(Int); +BASIC_TRAITS_DEF(Bool); +BASIC_TRAITS_DEF(Long); +BASIC_TRAITS_DEF(Char); +BASIC_TRAITS_DEF(UInt); +BASIC_TRAITS_DEF(ULong); +BASIC_TRAITS_DEF(Double); +BASIC_TRAITS_DEF(Float); +BASIC_TRAITS_DEF(VoidPtr); +BASIC_TRAITS_DEF(String); + + +#endif diff --git a/hash_table.c b/hash_table.c new file mode 100644 index 0000000..bedeb4a --- /dev/null +++ b/hash_table.c @@ -0,0 +1,119 @@ +#include "hash_table.h" + +#include +#include + +#include "basic_traits.h" + +#define HTFL_NUL 0 +#define HTFL_VAL 1 +#define HTFL_DEL 2 + +HASH_TABLE_IMPL(String, Int); +HASH_TABLE_IMPL(String, String); +HASH_TABLE_IMPL(String, Double); +HASH_TABLE_IMPL(String, VoidPtr); +HASH_TABLE_IMPL(Int, Int); +HASH_TABLE_IMPL(Int, Double); +HASH_TABLE_IMPL(VoidPtr, Int); +HASH_TABLE_IMPL(VoidPtr, VoidPtr); +HASH_TABLE_IMPL(VoidPtr, String); + + +static void rebuild(HashTable *ht, uint64_t (*hash)(void*), bool (*eq)(void*, void*)) { + HashTable newht; + init_hash_table(&newht, ht->elemsz, ht->size * 6); + void *iter = hash_table_begin(ht); + while (iter != NULL) { + hash_table_insert(&newht, iter, hash, eq); + iter = hash_table_next(ht, iter); + } + free(ht->buf); + free(ht->flagbuf); + *ht = newht; +} + +void init_hash_table(HashTable *ht, int64_t elemsz, int64_t cap) { + if (cap < 16) cap = 16; + 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->elemsz = elemsz; +} + +bool hash_table_insert(HashTable *ht, void *elem, uint64_t (*hash)(void*), bool (*eq)(void*, void*)) { + if (ht->taken + 1 > ht->cap / 2) { + rebuild(ht, hash, eq); + } + ht->taken++; + ht->size++; + int64_t pos = hash(elem) % ht->cap; + while (ht->flagbuf[pos] != HTFL_NUL) { + if (ht->flagbuf[pos] == HTFL_VAL + && eq(ht->buf + pos * ht->elemsz, elem)) { + return false; + } + pos++; + if (pos >= ht->cap) { // arrived end, restart from beginning + pos = 0; + } + } + memcpy(ht->buf + pos * ht->elemsz, elem, ht->elemsz); + ht->flagbuf[pos] = HTFL_VAL; + return true; +} + +void hash_table_remove(HashTable *ht, void * ptr) { + ht->size--; + int64_t pos = (ptr - ht->buf) / ht->elemsz; + ht->flagbuf[pos] = HTFL_DEL; +} + +void *hash_table_ref(HashTable *ht, int64_t pos) { + return ht->buf + pos * ht->elemsz; +} + +void *hash_table_find(HashTable *ht, void *elem, uint64_t (*hash)(void*), bool (*eq)(void*, void*)) { + int64_t pos = hash(elem) % ht->cap; + while (ht->flagbuf[pos] != HTFL_NUL) { + if (ht->flagbuf[pos] == HTFL_VAL + && 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(HashTable *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(HashTable *ht, void *iter) { + int64_t pos = (iter - ht->buf) / ht->elemsz; + do { + pos++; + if (pos >= ht->cap) { + return NULL; + } + } while (ht->flagbuf[pos] != HTFL_VAL); + return hash_table_ref(ht, pos); +} + +void destroy_hash_table(HashTable *ht) { + free(ht->buf); + free(ht->flagbuf); +} diff --git a/hash_table.h b/hash_table.h new file mode 100644 index 0000000..9b45dff --- /dev/null +++ b/hash_table.h @@ -0,0 +1,105 @@ +#ifndef HTABLE_H_ +#define HTABLE_H_ + +#include +#include + +#include "type_alias.h" + +struct hash_table { + void *buf; + char *flagbuf; + int64_t size; + int64_t cap; + int64_t taken; + int64_t elemsz; +}; +typedef struct hash_table HashTable; + +#define HASH_TABLE_DEF(K, V) \ + typedef struct { \ + K key; \ + V val; \ + } K##2##V##HashTableEntry; \ + typedef K##2##V##HashTableEntry *K##2##V##HashTableIter; \ + typedef struct { \ + HashTable ht; \ + } K##2##V##HashTable; \ + void K##2##V##HashTable_init(K##2##V##HashTable *self); \ + bool K##2##V##HashTable_insert(K##2##V##HashTable *self, K key, V value); \ + void K##2##V##HashTable_remove(K##2##V##HashTable *ht, K##2##V##HashTableIter iter); \ + V* K##2##V##HashTable_get(K##2##V##HashTable *self, K key); \ + K##2##V##HashTableIter K##2##V##HashTable_find(K##2##V##HashTable *self, K key); \ + K##2##V##HashTableIter K##2##V##HashTable_begin(K##2##V##HashTable *self); \ + K##2##V##HashTableIter K##2##V##HashTable_next(K##2##V##HashTable *self, K##2##V##HashTableIter iter); \ + void K##2##V##HashTable_free(K##2##V##HashTable *self); \ + K##2##V##HashTable K##2##V##HashTable_move(K##2##V##HashTable *self); \ + +#define HASH_TABLE_IMPL(K, V) \ + static uint64_t K##2##V##HashTable_hash(void *vk) { \ + K *k = vk; \ + return K##_hash(*k); \ + } \ + static bool K##2##V##HashTable_eq(void *vk1, void *vk2) { \ + K *k1 = vk1, *k2 = vk2; \ + return K##_eq(*k1, *k2); \ + } \ + void K##2##V##HashTable_init(K##2##V##HashTable *self) { \ + init_hash_table(&self->ht, sizeof(K##2##V##HashTableEntry), 16); \ + } \ + bool K##2##V##HashTable_insert(K##2##V##HashTable *self, K key, V value) { \ + K##2##V##HashTableEntry entry; \ + entry.key = key; \ + entry.val = value; \ + return hash_table_insert(&self->ht, &entry, K##2##V##HashTable_hash, K##2##V##HashTable_eq); \ + } \ + K##2##V##HashTableIter K##2##V##HashTable_find(K##2##V##HashTable *self, K key) { \ + return hash_table_find(&self->ht, &key, K##2##V##HashTable_hash, K##2##V##HashTable_eq); \ + } \ + V* K##2##V##HashTable_get(K##2##V##HashTable *self, K key) { \ + K##2##V##HashTableEntry* entry = hash_table_find(&self->ht, &key, K##2##V##HashTable_hash, K##2##V##HashTable_eq); \ + if (entry == NULL) return NULL; \ + return &(entry->val); \ + } \ + void K##2##V##HashTable_remove(K##2##V##HashTable *self, K##2##V##HashTableIter iter) { \ + hash_table_remove(&self->ht, iter); \ + } \ + K##2##V##HashTableIter K##2##V##HashTable_begin(K##2##V##HashTable *self) { \ + return hash_table_begin(&self->ht); \ + } \ + K##2##V##HashTableIter K##2##V##HashTable_next(K##2##V##HashTable *self, K##2##V##HashTableIter iter) { \ + return hash_table_next(&self->ht, iter); \ + } \ + void K##2##V##HashTable_free(K##2##V##HashTable *self) { \ + destroy_hash_table(&self->ht); \ + } \ + K##2##V##HashTable K##2##V##HashTable_move(K##2##V##HashTable *self) { \ + K##2##V##HashTable dup; \ + dup.ht = self->ht; \ + self->ht.buf = NULL; \ + self->ht.flagbuf = NULL; \ + self->ht.size = 0; \ + self->ht.cap = 0; \ + self->ht.taken = 0; \ + return dup; \ + } \ + +HASH_TABLE_DEF(String, Int); +HASH_TABLE_DEF(String, String); +HASH_TABLE_DEF(String, Double); +HASH_TABLE_DEF(String, VoidPtr); +HASH_TABLE_DEF(Int, Int); +HASH_TABLE_DEF(Int, Double); +HASH_TABLE_DEF(VoidPtr, Int); +HASH_TABLE_DEF(VoidPtr, String); +HASH_TABLE_DEF(VoidPtr, VoidPtr); + +void init_hash_table(HashTable *ht, int64_t elemsz, int64_t cap); +bool hash_table_insert(HashTable *ht, void *elem, uint64_t (*hash)(void*), bool (*eq)(void*, void*)); +void hash_table_remove(HashTable *ht, void *iter); +void *hash_table_find(HashTable *ht, void *elem, uint64_t (*hash)(void*), bool (*eq)(void*, void*)); +void *hash_table_begin(HashTable *ht); +void *hash_table_next(HashTable *ht, void *iter); +void destroy_hash_table(HashTable *ht); + +#endif diff --git a/list.c b/list.c new file mode 100644 index 0000000..2d08bd5 --- /dev/null +++ b/list.c @@ -0,0 +1,3 @@ +#include "list.h" + +LIST_IMPL(Int); diff --git a/list.h b/list.h new file mode 100644 index 0000000..a2453b6 --- /dev/null +++ b/list.h @@ -0,0 +1,134 @@ +#ifndef ALGDS_LIST_H_ +#define ALGDS_LIST_H_ + +#include + +#include "type_alias.h" + + +#define LIST_DEF(T) \ + struct T##List_node { \ + T val; \ + struct T##List_node *prev; \ + struct T##List_node *next; \ + }; \ + typedef struct T##List_node T##ListNode; \ + typedef T##ListNode *T##ListIter; \ + typedef struct { \ + T##ListNode *vhead; \ + T##ListNode *vtail; \ + size_t len; \ + } T##List; \ + void T##List_init(T##List *self); \ + void T##List_free(T##List *self); \ + void T##List_move(T##List *self); \ + T##ListIter T##List_insert_before(T##List *self, T##ListIter iter, T val); \ + T##ListIter T##List_insert_after(T##List *self, T##ListIter iter, T val); \ + void T##List_remove(T##List *self, T##ListIter iter); \ + T##ListIter T##List_begin(T##List *self); \ + T##ListIter T##List_last(T##List *self); \ + T##ListIter T##List_end(T##List *self); \ + T##ListIter T##List_next(T##ListIter iter); \ + T##ListIter T##List_prev(T##ListIter iter); \ + size_t T##List_len(T##List *self); \ + T##ListIter T##List_push_back(T##List *self, T val); \ + T##ListIter T##List_push_front(T##List *self, T val); \ + void T##List_pop_back(T##List *self); \ + void T##List_pop_front(T##List *self); \ + +LIST_DEF(Int); + +#define LIST_IMPL(T) \ + void T##List_init(T##List *self) { \ + self->vhead = malloc(sizeof(T##ListNode)); \ + self->vtail = malloc(sizeof(T##ListNode)); \ + self->vhead->next = self->vtail; \ + self->vhead->prev = NULL; \ + self->vtail->next = NULL; \ + self->vtail->prev = self->vhead; \ + self->len = 0; \ + } \ + void T##List_free(T##List *self) { \ + T##ListIter cur = self->vhead; \ + while (cur != NULL) { \ + T##ListIter next = cur->next; \ + free(cur); \ + cur = next; \ + } \ + } \ + void T##List_move(T##List *self) { \ + T##List dup; \ + dup.vhead = self->vhead; \ + dup.vtail = self->vtail; \ + dup.len = self->len; \ + self->vhead = NULL; \ + self->vtail = NULL; \ + self->len = 0; \ + } \ + T##ListIter T##List_insert_before(T##List *self, T##ListIter iter, T val) { \ + if (iter->prev == NULL) return NULL; \ + T##ListIter newnode = malloc(sizeof(T##ListNode)); \ + newnode->prev = iter->prev; \ + newnode->next = iter; \ + newnode->val = val; \ + iter->prev->next = newnode; \ + iter->prev = newnode; \ + self->len++; \ + return newnode; \ + } \ + T##ListIter T##List_insert_after(T##List *self, T##ListIter iter, T val) { \ + if (iter->next == NULL) return NULL; \ + T##ListIter newnode = malloc(sizeof(T##ListNode)); \ + newnode->next = iter->next; \ + newnode->prev= iter; \ + newnode->val = val; \ + iter->next->prev= newnode; \ + iter->next = newnode; \ + self->len++; \ + return newnode; \ + } \ + void T##List_remove(T##List *self, T##ListIter iter) { \ + if (iter->prev == NULL || iter->next == NULL) return; \ + iter->prev->next = iter->next; \ + iter->next->prev = iter->prev; \ + free(iter); \ + self->len--; \ + } \ + T##ListIter T##List_begin(T##List *self) { \ + return self->vhead->next; \ + } \ + T##ListIter T##List_last(T##List *self) { \ + if (self->vtail->prev == self->vhead) return NULL; \ + return self->vtail->prev; \ + } \ + T##ListIter T##List_end(T##List *self) { \ + return self->vtail; \ + } \ + T##ListIter T##List_next(T##ListIter iter) { \ + if (iter == NULL) return NULL; \ + return iter->next; \ + } \ + T##ListIter T##List_prev(T##ListIter iter) { \ + if (iter == NULL) return NULL; \ + if (iter->prev == NULL) return NULL; \ + if (iter->prev->prev == NULL) return NULL; \ + return iter->prev; \ + } \ + size_t T##List_len(T##List *self) { \ + return self->len; \ + } \ + T##ListIter T##List_push_back(T##List *self, T val) { \ + return T##List_insert_before(self, self->vtail, val); \ + } \ + T##ListIter T##List_push_front(T##List *self, T val) { \ + return T##List_insert_after(self, self->vhead, val); \ + } \ + void T##List_pop_back(T##List *self) { \ + T##List_remove(self, self->vtail->prev); \ + } \ + void T##List_pop_front(T##List *self) { \ + T##List_remove(self, self->vhead->next); \ + } \ + +#endif + diff --git a/mmhash.c b/mmhash.c new file mode 100644 index 0000000..7897b9e --- /dev/null +++ b/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/mmhash.h b/mmhash.h new file mode 100644 index 0000000..a795cb1 --- /dev/null +++ b/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/pqueue.c b/pqueue.c new file mode 100644 index 0000000..d070735 --- /dev/null +++ b/pqueue.c @@ -0,0 +1,17 @@ +#include "pqueue.h" + +#include +#include + +#include "basic_traits.h" + +PQUEUE_IMPL(Int); +PQUEUE_IMPL(Bool); +PQUEUE_IMPL(Long); +PQUEUE_IMPL(Char); +PQUEUE_IMPL(UInt); +PQUEUE_IMPL(ULong); +PQUEUE_IMPL(Double); +PQUEUE_IMPL(Float); +PQUEUE_IMPL(String); +PQUEUE_IMPL(VoidPtr); diff --git a/pqueue.h b/pqueue.h new file mode 100644 index 0000000..2cf78ec --- /dev/null +++ b/pqueue.h @@ -0,0 +1,79 @@ +#ifndef PQUEUE_H_ +#define PQUEUE_H_ + +#include "vec.h" + +#define PQUEUE_DEF(T) \ + typedef struct { \ + T##Vector vec; \ + } T##PQueue; \ + void T##PQueue_init(T##PQueue *self); \ + void T##PQueue_push(T##PQueue *self, T elem); \ + void T##PQueue_pop(T##PQueue *self); \ + T* T##PQueue_top(T##PQueue *self); \ + T##PQueue T##PQueue_move(T##PQueue *self); \ + void T##PQueue_free(T##PQueue *self); \ + +PQUEUE_DEF(Int); +PQUEUE_DEF(Bool); +PQUEUE_DEF(Long); +PQUEUE_DEF(Char); +PQUEUE_DEF(UInt); +PQUEUE_DEF(ULong); +PQUEUE_DEF(Double); +PQUEUE_DEF(Float); +PQUEUE_DEF(String); +PQUEUE_DEF(VoidPtr); + +#define PQUEUE_IMPL(T) \ + static int T##PQueue_cmp(T##PQueue *self, int a, int b) { \ + return T##_cmp(*T##Vector_ref(&self->vec, a), *T##Vector_ref(&self->vec, b)); \ + } \ + void T##PQueue_init(T##PQueue *self) { \ + T##Vector_init(&self->vec); \ + } \ + void T##PQueue_push(T##PQueue *self, T elem) { \ + T##Vector_push_back(&self->vec, elem); \ + int i = self->vec.size - 1; \ + while (i > 0 && T##PQueue_cmp(self, i, i / 2) > 0) { \ + T##Vector_swap(&self->vec, i, i / 2); \ + i /= 2; \ + } \ + } \ + static void T##PQueue_heapify(T##PQueue *self, int idx) { \ + int left, right, largest; \ + left = 2 * idx + 1; \ + right = 2 * idx + 2; \ + if (left < self->vec.size && T##PQueue_cmp(self, left, idx) > 0) { \ + largest = left; \ + } else { \ + largest = idx; \ + } \ + if (right < self->vec.size && T##PQueue_cmp(self, right, largest) > 0) { \ + largest = right; \ + } \ + if (largest != idx) { \ + T##Vector_swap(&self->vec, largest, idx); \ + T##PQueue_heapify(self, largest); \ + } \ + } \ + void T##PQueue_pop(T##PQueue *self) { \ + if (self->vec.size == 0) return; \ + memcpy(T##Vector_ref(&self->vec, 0), T##Vector_ref(&self->vec, self->vec.size - 1), sizeof(T)); \ + T##Vector_pop(&self->vec); \ + T##PQueue_heapify(self, 0); \ + } \ + T* T##PQueue_top(T##PQueue *self) { \ + if (self->vec.size == 0) return NULL; \ + return self->vec.buffer; \ + } \ + T##PQueue T##PQueue_move(T##PQueue *self) { \ + T##PQueue dup; \ + dup.vec = T##Vector_move(&self->vec); \ + return dup; \ + } \ + void T##PQueue_free(T##PQueue *self) { \ + T##Vector_free(&self->vec); \ + } \ + +#endif diff --git a/rb_tree.h b/rb_tree.h new file mode 100644 index 0000000..7c91cea --- /dev/null +++ b/rb_tree.h @@ -0,0 +1,143 @@ +/* + * 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 + +#include "type_alias.h" + +#define TREE_MAP_DEF(K, V) \ + typedef struct { \ + RBNode rbnode; \ + K key; \ + V value; \ + } K##2##V##TreeMapNode; \ + typedef K##2##V##TreeMapNode *K##2##V##TreeMapIter; \ + typedef struct { \ + RBTree tree; \ + } K##2##V##TreeMap; \ + void K##2##V##TreeMap_init(K##2##V##TreeMap *self); \ + K##2##V##TreeMapIter K##2##V##TreeMap_insert(K##2##V##TreeMap *self, K key, V value); \ + K##2##V##TreeMapIter K##2##V##TreeMap_find(K##2##V##TreeMap *self, K key); \ + V* K##2##V##TreeMap_get(K##2##V##TreeMap *self, K key); \ + K##2##V##TreeMapIter K##2##V##TreeMap_next(K##2##V##TreeMap *self, K##2##V##TreeMapIter iter); \ + void K##2##V##TreeMap_remove(K##2##V##TreeMap *self, K##2##V##TreeMapIter iter); \ + K##2##V##TreeMapIter K##2##V##TreeMap_min(K##2##V##TreeMap *self); \ + K##2##V##TreeMapIter K##2##V##TreeMap_max(K##2##V##TreeMap *self); \ + K##2##V##TreeMapIter K##2##V##TreeMap_left(K##2##V##TreeMapIter iter); \ + K##2##V##TreeMapIter K##2##V##TreeMap_right(K##2##V##TreeMapIter iter); \ + K##2##V##TreeMapIter K##2##V##TreeMap_parent(K##2##V##TreeMapIter iter); \ + +#define TREE_MAP_IMPL(K, V) \ + static int K##2##V##TreeMap_cmp(void *vlhs, void *vrhs) { \ + K *lhs = vlhs, *rhs = vrhs; \ + return K##_cmp(*lhs, *rhs); \ + } \ + void K##2##V##TreeMap_init(K##2##V##TreeMap *self) { \ + self->tree.rbh_root = NULL; \ + self->tree.cmp = K##2##V##TreeMap_cmp; \ + self->tree.augment = NULL; \ + } \ + K##2##V##TreeMapIter K##2##V##TreeMap_insert(K##2##V##TreeMap *self, K key, V value) { \ + K##2##V##TreeMapNode *newnode = malloc(sizeof(K##2##V##TreeMapNode)); \ + newnode->key = key; \ + newnode->value = value; \ + return rb_tree_insert(&self->tree, newnode); \ + } \ + K##2##V##TreeMapIter K##2##V##TreeMap_find(K##2##V##TreeMap *self, K key) { \ + return rb_tree_find(&self->tree, &key); \ + } \ + V* K##2##V##TreeMap_get(K##2##V##TreeMap *self, K key) { \ + K##2##V##TreeMapIter iter = rb_tree_find(&self->tree, &key); \ + return &iter->value; \ + } \ + void K##2##V##TreeMap_remove(K##2##V##TreeMap *self, K##2##V##TreeMapIter iter) { \ + rb_tree_remove(self, iter); \ + } \ + K##2##V##TreeMapIter K##2##V##TreeMap_next(K##2##V##TreeMap *self, K##2##V##TreeMapIter iter) { \ + return rb_tree_next(&self->tree, iter); \ + } \ + K##2##V##TreeMapIter K##2##V##TreeMap_min(K##2##V##TreeMap *self) { \ + return rb_tree_min(&self->tree); \ + } \ + K##2##V##TreeMapIter K##2##V##TreeMap_max(K##2##V##TreeMap *self) { \ + return rb_tree_max(&self->tree); \ + } \ + K##2##V##TreeMapIter K##2##V##TreeMap_left(K##2##V##TreeMapIter iter) { \ + return rb_tree_left(iter); \ + } \ + K##2##V##TreeMapIter K##2##V##TreeMap_right(K##2##V##TreeMapIter iter) { \ + return rb_tree_right(iter); \ + } \ + K##2##V##TreeMapIter K##2##V##TreeMap_parent(K##2##V##TreeMapIter iter) { \ + return rb_tree_parent(iter); \ + } \ + +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 RBNode; + +struct rb_tree { + RBNode *rbh_root; + int (*cmp)(void *k1, void *k2); + void (*augment)(void *elm); +}; +typedef struct rb_tree RBTree; + +void rb_tree_remove(RBTree *, void *iter); + +// return a iterator +void *rb_tree_insert(RBTree *, void *treenode); +void *rb_tree_find(RBTree *, void *val); +void *rb_tree_next(RBTree *, void *iter); +void *rb_tree_min(RBTree *); +void *rb_tree_max(RBTree *); +void *rb_tree_left(void *node); +void *rb_tree_right(void *node); +void *rb_tree_parent(void *node); + +void destroy_rb_tree(RBTree *, void (*freeCb)(void *)); + +TREE_MAP_DEF(String, Int); +TREE_MAP_DEF(String, String); +TREE_MAP_DEF(String, Double); +TREE_MAP_DEF(String, VoidPtr); +TREE_MAP_DEF(Int, Int); +TREE_MAP_DEF(Int, Double); +TREE_MAP_DEF(VoidPtr, Int); +TREE_MAP_DEF(VoidPtr, String); +TREE_MAP_DEF(VoidPtr, VoidPtr); + +#endif + diff --git a/sort.c b/sort.c new file mode 100644 index 0000000..ed5a1e3 --- /dev/null +++ b/sort.c @@ -0,0 +1,14 @@ +#include "sort.h" + +#include "basic_traits.h" + + +QSORT_IMPL(Int); +QSORT_IMPL(Bool); +QSORT_IMPL(Long); +QSORT_IMPL(Char); +QSORT_IMPL(UInt); +QSORT_IMPL(ULong); +QSORT_IMPL(Double); +QSORT_IMPL(Float); +QSORT_IMPL(String); diff --git a/sort.h b/sort.h new file mode 100644 index 0000000..9266093 --- /dev/null +++ b/sort.h @@ -0,0 +1,54 @@ +#ifndef ALGDS_SORT_H_ +#define ALGDS_SORT_H_ + +#include +#include + +#include "type_alias.h" + +#define QSORT_DEF(T) \ + void T##_qsort(T* arr, int n); + +#define QSORT_IMPL(T) \ + void T##_qsort_swap(T* arr, int lhs, int rhs) { \ + if (lhs == rhs) return; \ + T buf; \ + buf = arr[lhs]; \ + arr[lhs] = arr[rhs]; \ + arr[rhs] = buf; \ + } \ + void T##_qsort(T* arr, int n) { \ + if (n <= 1) return; \ + int pivot = rand() % n; \ + T##_qsort_swap(arr, 0, pivot); \ + int lp = 1, rp = n-1; \ + while (lp < rp) { \ + if (T##_cmp(arr[lp], arr[0]) < 0) { \ + lp++; \ + continue; \ + } \ + if (T##_cmp(arr[rp], arr[0]) >= 0) { \ + rp--; \ + continue; \ + } \ + T##_qsort_swap(arr, lp, rp); \ + lp++; \ + rp--; \ + } \ + if (T##_cmp(arr[rp], arr[0]) > 0) rp--; \ + T##_qsort_swap(arr, 0, rp); \ + T##_qsort(arr, rp); \ + T##_qsort(arr+rp+1, n-rp-1); \ + } + +QSORT_DEF(Int); +QSORT_DEF(Bool); +QSORT_DEF(Long); +QSORT_DEF(Char); +QSORT_DEF(UInt); +QSORT_DEF(ULong); +QSORT_DEF(Double); +QSORT_DEF(Float); +QSORT_DEF(String); + +#endif diff --git a/src/basic_traits.c b/src/basic_traits.c deleted file mode 100644 index 5d2a8fb..0000000 --- a/src/basic_traits.c +++ /dev/null @@ -1,76 +0,0 @@ -#include "basic_traits.h" - -#include -#include - -#include "mmhash.h" - -#define BASIC_TRAITS_IMPL(T) \ - bool T##_eq(T lhs, T rhs) { \ - return lhs == rhs; \ - } \ - int T##_cmp(T lhs, T rhs) { \ - if (lhs == rhs) return 0; \ - if (lhs < rhs) return -1; \ - return 1; \ - } \ - uint64_t T##_hash(T x) { \ - return mmhash(&x, sizeof(T), 0); \ - } \ - -BASIC_TRAITS_IMPL(Char); -BASIC_TRAITS_IMPL(Bool); -BASIC_TRAITS_IMPL(Int); -BASIC_TRAITS_IMPL(Long); -BASIC_TRAITS_IMPL(UInt); -BASIC_TRAITS_IMPL(ULong); -BASIC_TRAITS_IMPL(Double); -BASIC_TRAITS_IMPL(Float); -BASIC_TRAITS_IMPL(VoidPtr); - -void Char_show(Char self, FILE* fp) { - fprintf(fp, "%c", self); -} -void Bool_show(Bool self, FILE* fp) { - if (self) fprintf(fp, "true"); - else fprintf(fp, "false"); -} -void Int_show(Int self, FILE* fp) { - fprintf(fp, "%"PRId32, self); -} -void Long_show(Long self, FILE* fp) { - fprintf(fp, "%"PRId64, self); -} -void UInt_show(UInt self, FILE* fp) { - fprintf(fp, "%"PRIu32, self); -} -void ULong_show(ULong self, FILE* fp) { - fprintf(fp, "%"PRIu64, self); -} -void VoidPtr_show(VoidPtr self, FILE* fp) { - fprintf(fp, "%p", self); -} -void Double_show(Double self, FILE* fp) { - fprintf(fp, "%lf", self); -} -void Float_show(Float self, FILE* fp) { - fprintf(fp, "%f", self); -} -void String_show(String self, FILE* fp) { - fprintf(fp, "%s", self); -} - -bool String_eq(String lhs, String rhs) { - return strcmp(lhs, rhs) == 0; -} - -int String_cmp(String lhs, String rhs) { - return strcmp(lhs, rhs); -} - -uint64_t String_hash(String x) { - size_t len = strlen(x); - return mmhash(x, len, 0); -} - - diff --git a/src/basic_traits.h b/src/basic_traits.h deleted file mode 100644 index 45aaba9..0000000 --- a/src/basic_traits.h +++ /dev/null @@ -1,27 +0,0 @@ -#ifndef ALGDS_BAISC_TRAITS_H_ -#define ALGDS_BAISC_TRAITS_H_ - -#include - -#include "type_alias.h" - -// basic traits -#define BASIC_TRAITS_DEF(T) \ - Bool T##_eq(T lhs, T rhs); \ - Int T##_cmp(T lhs, T rhs); \ - uint64_t T##_hash(T x); \ - void T##_show(T x, FILE* fp); \ - -BASIC_TRAITS_DEF(Int); -BASIC_TRAITS_DEF(Bool); -BASIC_TRAITS_DEF(Long); -BASIC_TRAITS_DEF(Char); -BASIC_TRAITS_DEF(UInt); -BASIC_TRAITS_DEF(ULong); -BASIC_TRAITS_DEF(Double); -BASIC_TRAITS_DEF(Float); -BASIC_TRAITS_DEF(VoidPtr); -BASIC_TRAITS_DEF(String); - - -#endif diff --git a/src/hash_table.c b/src/hash_table.c deleted file mode 100644 index bedeb4a..0000000 --- a/src/hash_table.c +++ /dev/null @@ -1,119 +0,0 @@ -#include "hash_table.h" - -#include -#include - -#include "basic_traits.h" - -#define HTFL_NUL 0 -#define HTFL_VAL 1 -#define HTFL_DEL 2 - -HASH_TABLE_IMPL(String, Int); -HASH_TABLE_IMPL(String, String); -HASH_TABLE_IMPL(String, Double); -HASH_TABLE_IMPL(String, VoidPtr); -HASH_TABLE_IMPL(Int, Int); -HASH_TABLE_IMPL(Int, Double); -HASH_TABLE_IMPL(VoidPtr, Int); -HASH_TABLE_IMPL(VoidPtr, VoidPtr); -HASH_TABLE_IMPL(VoidPtr, String); - - -static void rebuild(HashTable *ht, uint64_t (*hash)(void*), bool (*eq)(void*, void*)) { - HashTable newht; - init_hash_table(&newht, ht->elemsz, ht->size * 6); - void *iter = hash_table_begin(ht); - while (iter != NULL) { - hash_table_insert(&newht, iter, hash, eq); - iter = hash_table_next(ht, iter); - } - free(ht->buf); - free(ht->flagbuf); - *ht = newht; -} - -void init_hash_table(HashTable *ht, int64_t elemsz, int64_t cap) { - if (cap < 16) cap = 16; - 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->elemsz = elemsz; -} - -bool hash_table_insert(HashTable *ht, void *elem, uint64_t (*hash)(void*), bool (*eq)(void*, void*)) { - if (ht->taken + 1 > ht->cap / 2) { - rebuild(ht, hash, eq); - } - ht->taken++; - ht->size++; - int64_t pos = hash(elem) % ht->cap; - while (ht->flagbuf[pos] != HTFL_NUL) { - if (ht->flagbuf[pos] == HTFL_VAL - && eq(ht->buf + pos * ht->elemsz, elem)) { - return false; - } - pos++; - if (pos >= ht->cap) { // arrived end, restart from beginning - pos = 0; - } - } - memcpy(ht->buf + pos * ht->elemsz, elem, ht->elemsz); - ht->flagbuf[pos] = HTFL_VAL; - return true; -} - -void hash_table_remove(HashTable *ht, void * ptr) { - ht->size--; - int64_t pos = (ptr - ht->buf) / ht->elemsz; - ht->flagbuf[pos] = HTFL_DEL; -} - -void *hash_table_ref(HashTable *ht, int64_t pos) { - return ht->buf + pos * ht->elemsz; -} - -void *hash_table_find(HashTable *ht, void *elem, uint64_t (*hash)(void*), bool (*eq)(void*, void*)) { - int64_t pos = hash(elem) % ht->cap; - while (ht->flagbuf[pos] != HTFL_NUL) { - if (ht->flagbuf[pos] == HTFL_VAL - && 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(HashTable *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(HashTable *ht, void *iter) { - int64_t pos = (iter - ht->buf) / ht->elemsz; - do { - pos++; - if (pos >= ht->cap) { - return NULL; - } - } while (ht->flagbuf[pos] != HTFL_VAL); - return hash_table_ref(ht, pos); -} - -void destroy_hash_table(HashTable *ht) { - free(ht->buf); - free(ht->flagbuf); -} diff --git a/src/hash_table.h b/src/hash_table.h deleted file mode 100644 index 9b45dff..0000000 --- a/src/hash_table.h +++ /dev/null @@ -1,105 +0,0 @@ -#ifndef HTABLE_H_ -#define HTABLE_H_ - -#include -#include - -#include "type_alias.h" - -struct hash_table { - void *buf; - char *flagbuf; - int64_t size; - int64_t cap; - int64_t taken; - int64_t elemsz; -}; -typedef struct hash_table HashTable; - -#define HASH_TABLE_DEF(K, V) \ - typedef struct { \ - K key; \ - V val; \ - } K##2##V##HashTableEntry; \ - typedef K##2##V##HashTableEntry *K##2##V##HashTableIter; \ - typedef struct { \ - HashTable ht; \ - } K##2##V##HashTable; \ - void K##2##V##HashTable_init(K##2##V##HashTable *self); \ - bool K##2##V##HashTable_insert(K##2##V##HashTable *self, K key, V value); \ - void K##2##V##HashTable_remove(K##2##V##HashTable *ht, K##2##V##HashTableIter iter); \ - V* K##2##V##HashTable_get(K##2##V##HashTable *self, K key); \ - K##2##V##HashTableIter K##2##V##HashTable_find(K##2##V##HashTable *self, K key); \ - K##2##V##HashTableIter K##2##V##HashTable_begin(K##2##V##HashTable *self); \ - K##2##V##HashTableIter K##2##V##HashTable_next(K##2##V##HashTable *self, K##2##V##HashTableIter iter); \ - void K##2##V##HashTable_free(K##2##V##HashTable *self); \ - K##2##V##HashTable K##2##V##HashTable_move(K##2##V##HashTable *self); \ - -#define HASH_TABLE_IMPL(K, V) \ - static uint64_t K##2##V##HashTable_hash(void *vk) { \ - K *k = vk; \ - return K##_hash(*k); \ - } \ - static bool K##2##V##HashTable_eq(void *vk1, void *vk2) { \ - K *k1 = vk1, *k2 = vk2; \ - return K##_eq(*k1, *k2); \ - } \ - void K##2##V##HashTable_init(K##2##V##HashTable *self) { \ - init_hash_table(&self->ht, sizeof(K##2##V##HashTableEntry), 16); \ - } \ - bool K##2##V##HashTable_insert(K##2##V##HashTable *self, K key, V value) { \ - K##2##V##HashTableEntry entry; \ - entry.key = key; \ - entry.val = value; \ - return hash_table_insert(&self->ht, &entry, K##2##V##HashTable_hash, K##2##V##HashTable_eq); \ - } \ - K##2##V##HashTableIter K##2##V##HashTable_find(K##2##V##HashTable *self, K key) { \ - return hash_table_find(&self->ht, &key, K##2##V##HashTable_hash, K##2##V##HashTable_eq); \ - } \ - V* K##2##V##HashTable_get(K##2##V##HashTable *self, K key) { \ - K##2##V##HashTableEntry* entry = hash_table_find(&self->ht, &key, K##2##V##HashTable_hash, K##2##V##HashTable_eq); \ - if (entry == NULL) return NULL; \ - return &(entry->val); \ - } \ - void K##2##V##HashTable_remove(K##2##V##HashTable *self, K##2##V##HashTableIter iter) { \ - hash_table_remove(&self->ht, iter); \ - } \ - K##2##V##HashTableIter K##2##V##HashTable_begin(K##2##V##HashTable *self) { \ - return hash_table_begin(&self->ht); \ - } \ - K##2##V##HashTableIter K##2##V##HashTable_next(K##2##V##HashTable *self, K##2##V##HashTableIter iter) { \ - return hash_table_next(&self->ht, iter); \ - } \ - void K##2##V##HashTable_free(K##2##V##HashTable *self) { \ - destroy_hash_table(&self->ht); \ - } \ - K##2##V##HashTable K##2##V##HashTable_move(K##2##V##HashTable *self) { \ - K##2##V##HashTable dup; \ - dup.ht = self->ht; \ - self->ht.buf = NULL; \ - self->ht.flagbuf = NULL; \ - self->ht.size = 0; \ - self->ht.cap = 0; \ - self->ht.taken = 0; \ - return dup; \ - } \ - -HASH_TABLE_DEF(String, Int); -HASH_TABLE_DEF(String, String); -HASH_TABLE_DEF(String, Double); -HASH_TABLE_DEF(String, VoidPtr); -HASH_TABLE_DEF(Int, Int); -HASH_TABLE_DEF(Int, Double); -HASH_TABLE_DEF(VoidPtr, Int); -HASH_TABLE_DEF(VoidPtr, String); -HASH_TABLE_DEF(VoidPtr, VoidPtr); - -void init_hash_table(HashTable *ht, int64_t elemsz, int64_t cap); -bool hash_table_insert(HashTable *ht, void *elem, uint64_t (*hash)(void*), bool (*eq)(void*, void*)); -void hash_table_remove(HashTable *ht, void *iter); -void *hash_table_find(HashTable *ht, void *elem, uint64_t (*hash)(void*), bool (*eq)(void*, void*)); -void *hash_table_begin(HashTable *ht); -void *hash_table_next(HashTable *ht, void *iter); -void destroy_hash_table(HashTable *ht); - -#endif diff --git a/src/list.c b/src/list.c deleted file mode 100644 index 2d08bd5..0000000 --- a/src/list.c +++ /dev/null @@ -1,3 +0,0 @@ -#include "list.h" - -LIST_IMPL(Int); diff --git a/src/list.h b/src/list.h deleted file mode 100644 index a2453b6..0000000 --- a/src/list.h +++ /dev/null @@ -1,134 +0,0 @@ -#ifndef ALGDS_LIST_H_ -#define ALGDS_LIST_H_ - -#include - -#include "type_alias.h" - - -#define LIST_DEF(T) \ - struct T##List_node { \ - T val; \ - struct T##List_node *prev; \ - struct T##List_node *next; \ - }; \ - typedef struct T##List_node T##ListNode; \ - typedef T##ListNode *T##ListIter; \ - typedef struct { \ - T##ListNode *vhead; \ - T##ListNode *vtail; \ - size_t len; \ - } T##List; \ - void T##List_init(T##List *self); \ - void T##List_free(T##List *self); \ - void T##List_move(T##List *self); \ - T##ListIter T##List_insert_before(T##List *self, T##ListIter iter, T val); \ - T##ListIter T##List_insert_after(T##List *self, T##ListIter iter, T val); \ - void T##List_remove(T##List *self, T##ListIter iter); \ - T##ListIter T##List_begin(T##List *self); \ - T##ListIter T##List_last(T##List *self); \ - T##ListIter T##List_end(T##List *self); \ - T##ListIter T##List_next(T##ListIter iter); \ - T##ListIter T##List_prev(T##ListIter iter); \ - size_t T##List_len(T##List *self); \ - T##ListIter T##List_push_back(T##List *self, T val); \ - T##ListIter T##List_push_front(T##List *self, T val); \ - void T##List_pop_back(T##List *self); \ - void T##List_pop_front(T##List *self); \ - -LIST_DEF(Int); - -#define LIST_IMPL(T) \ - void T##List_init(T##List *self) { \ - self->vhead = malloc(sizeof(T##ListNode)); \ - self->vtail = malloc(sizeof(T##ListNode)); \ - self->vhead->next = self->vtail; \ - self->vhead->prev = NULL; \ - self->vtail->next = NULL; \ - self->vtail->prev = self->vhead; \ - self->len = 0; \ - } \ - void T##List_free(T##List *self) { \ - T##ListIter cur = self->vhead; \ - while (cur != NULL) { \ - T##ListIter next = cur->next; \ - free(cur); \ - cur = next; \ - } \ - } \ - void T##List_move(T##List *self) { \ - T##List dup; \ - dup.vhead = self->vhead; \ - dup.vtail = self->vtail; \ - dup.len = self->len; \ - self->vhead = NULL; \ - self->vtail = NULL; \ - self->len = 0; \ - } \ - T##ListIter T##List_insert_before(T##List *self, T##ListIter iter, T val) { \ - if (iter->prev == NULL) return NULL; \ - T##ListIter newnode = malloc(sizeof(T##ListNode)); \ - newnode->prev = iter->prev; \ - newnode->next = iter; \ - newnode->val = val; \ - iter->prev->next = newnode; \ - iter->prev = newnode; \ - self->len++; \ - return newnode; \ - } \ - T##ListIter T##List_insert_after(T##List *self, T##ListIter iter, T val) { \ - if (iter->next == NULL) return NULL; \ - T##ListIter newnode = malloc(sizeof(T##ListNode)); \ - newnode->next = iter->next; \ - newnode->prev= iter; \ - newnode->val = val; \ - iter->next->prev= newnode; \ - iter->next = newnode; \ - self->len++; \ - return newnode; \ - } \ - void T##List_remove(T##List *self, T##ListIter iter) { \ - if (iter->prev == NULL || iter->next == NULL) return; \ - iter->prev->next = iter->next; \ - iter->next->prev = iter->prev; \ - free(iter); \ - self->len--; \ - } \ - T##ListIter T##List_begin(T##List *self) { \ - return self->vhead->next; \ - } \ - T##ListIter T##List_last(T##List *self) { \ - if (self->vtail->prev == self->vhead) return NULL; \ - return self->vtail->prev; \ - } \ - T##ListIter T##List_end(T##List *self) { \ - return self->vtail; \ - } \ - T##ListIter T##List_next(T##ListIter iter) { \ - if (iter == NULL) return NULL; \ - return iter->next; \ - } \ - T##ListIter T##List_prev(T##ListIter iter) { \ - if (iter == NULL) return NULL; \ - if (iter->prev == NULL) return NULL; \ - if (iter->prev->prev == NULL) return NULL; \ - return iter->prev; \ - } \ - size_t T##List_len(T##List *self) { \ - return self->len; \ - } \ - T##ListIter T##List_push_back(T##List *self, T val) { \ - return T##List_insert_before(self, self->vtail, val); \ - } \ - T##ListIter T##List_push_front(T##List *self, T val) { \ - return T##List_insert_after(self, self->vhead, val); \ - } \ - void T##List_pop_back(T##List *self) { \ - T##List_remove(self, self->vtail->prev); \ - } \ - void T##List_pop_front(T##List *self) { \ - T##List_remove(self, self->vhead->next); \ - } \ - -#endif - diff --git a/src/mmhash.c b/src/mmhash.c deleted file mode 100644 index 7897b9e..0000000 --- a/src/mmhash.c +++ /dev/null @@ -1,57 +0,0 @@ -#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 deleted file mode 100644 index a795cb1..0000000 --- a/src/mmhash.h +++ /dev/null @@ -1,8 +0,0 @@ -#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/pqueue.c b/src/pqueue.c deleted file mode 100644 index d070735..0000000 --- a/src/pqueue.c +++ /dev/null @@ -1,17 +0,0 @@ -#include "pqueue.h" - -#include -#include - -#include "basic_traits.h" - -PQUEUE_IMPL(Int); -PQUEUE_IMPL(Bool); -PQUEUE_IMPL(Long); -PQUEUE_IMPL(Char); -PQUEUE_IMPL(UInt); -PQUEUE_IMPL(ULong); -PQUEUE_IMPL(Double); -PQUEUE_IMPL(Float); -PQUEUE_IMPL(String); -PQUEUE_IMPL(VoidPtr); diff --git a/src/pqueue.h b/src/pqueue.h deleted file mode 100644 index 2cf78ec..0000000 --- a/src/pqueue.h +++ /dev/null @@ -1,79 +0,0 @@ -#ifndef PQUEUE_H_ -#define PQUEUE_H_ - -#include "vec.h" - -#define PQUEUE_DEF(T) \ - typedef struct { \ - T##Vector vec; \ - } T##PQueue; \ - void T##PQueue_init(T##PQueue *self); \ - void T##PQueue_push(T##PQueue *self, T elem); \ - void T##PQueue_pop(T##PQueue *self); \ - T* T##PQueue_top(T##PQueue *self); \ - T##PQueue T##PQueue_move(T##PQueue *self); \ - void T##PQueue_free(T##PQueue *self); \ - -PQUEUE_DEF(Int); -PQUEUE_DEF(Bool); -PQUEUE_DEF(Long); -PQUEUE_DEF(Char); -PQUEUE_DEF(UInt); -PQUEUE_DEF(ULong); -PQUEUE_DEF(Double); -PQUEUE_DEF(Float); -PQUEUE_DEF(String); -PQUEUE_DEF(VoidPtr); - -#define PQUEUE_IMPL(T) \ - static int T##PQueue_cmp(T##PQueue *self, int a, int b) { \ - return T##_cmp(*T##Vector_ref(&self->vec, a), *T##Vector_ref(&self->vec, b)); \ - } \ - void T##PQueue_init(T##PQueue *self) { \ - T##Vector_init(&self->vec); \ - } \ - void T##PQueue_push(T##PQueue *self, T elem) { \ - T##Vector_push_back(&self->vec, elem); \ - int i = self->vec.size - 1; \ - while (i > 0 && T##PQueue_cmp(self, i, i / 2) > 0) { \ - T##Vector_swap(&self->vec, i, i / 2); \ - i /= 2; \ - } \ - } \ - static void T##PQueue_heapify(T##PQueue *self, int idx) { \ - int left, right, largest; \ - left = 2 * idx + 1; \ - right = 2 * idx + 2; \ - if (left < self->vec.size && T##PQueue_cmp(self, left, idx) > 0) { \ - largest = left; \ - } else { \ - largest = idx; \ - } \ - if (right < self->vec.size && T##PQueue_cmp(self, right, largest) > 0) { \ - largest = right; \ - } \ - if (largest != idx) { \ - T##Vector_swap(&self->vec, largest, idx); \ - T##PQueue_heapify(self, largest); \ - } \ - } \ - void T##PQueue_pop(T##PQueue *self) { \ - if (self->vec.size == 0) return; \ - memcpy(T##Vector_ref(&self->vec, 0), T##Vector_ref(&self->vec, self->vec.size - 1), sizeof(T)); \ - T##Vector_pop(&self->vec); \ - T##PQueue_heapify(self, 0); \ - } \ - T* T##PQueue_top(T##PQueue *self) { \ - if (self->vec.size == 0) return NULL; \ - return self->vec.buffer; \ - } \ - T##PQueue T##PQueue_move(T##PQueue *self) { \ - T##PQueue dup; \ - dup.vec = T##Vector_move(&self->vec); \ - return dup; \ - } \ - void T##PQueue_free(T##PQueue *self) { \ - T##Vector_free(&self->vec); \ - } \ - -#endif diff --git a/src/rb_tree.h b/src/rb_tree.h deleted file mode 100644 index 7c91cea..0000000 --- a/src/rb_tree.h +++ /dev/null @@ -1,143 +0,0 @@ -/* - * 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 - -#include "type_alias.h" - -#define TREE_MAP_DEF(K, V) \ - typedef struct { \ - RBNode rbnode; \ - K key; \ - V value; \ - } K##2##V##TreeMapNode; \ - typedef K##2##V##TreeMapNode *K##2##V##TreeMapIter; \ - typedef struct { \ - RBTree tree; \ - } K##2##V##TreeMap; \ - void K##2##V##TreeMap_init(K##2##V##TreeMap *self); \ - K##2##V##TreeMapIter K##2##V##TreeMap_insert(K##2##V##TreeMap *self, K key, V value); \ - K##2##V##TreeMapIter K##2##V##TreeMap_find(K##2##V##TreeMap *self, K key); \ - V* K##2##V##TreeMap_get(K##2##V##TreeMap *self, K key); \ - K##2##V##TreeMapIter K##2##V##TreeMap_next(K##2##V##TreeMap *self, K##2##V##TreeMapIter iter); \ - void K##2##V##TreeMap_remove(K##2##V##TreeMap *self, K##2##V##TreeMapIter iter); \ - K##2##V##TreeMapIter K##2##V##TreeMap_min(K##2##V##TreeMap *self); \ - K##2##V##TreeMapIter K##2##V##TreeMap_max(K##2##V##TreeMap *self); \ - K##2##V##TreeMapIter K##2##V##TreeMap_left(K##2##V##TreeMapIter iter); \ - K##2##V##TreeMapIter K##2##V##TreeMap_right(K##2##V##TreeMapIter iter); \ - K##2##V##TreeMapIter K##2##V##TreeMap_parent(K##2##V##TreeMapIter iter); \ - -#define TREE_MAP_IMPL(K, V) \ - static int K##2##V##TreeMap_cmp(void *vlhs, void *vrhs) { \ - K *lhs = vlhs, *rhs = vrhs; \ - return K##_cmp(*lhs, *rhs); \ - } \ - void K##2##V##TreeMap_init(K##2##V##TreeMap *self) { \ - self->tree.rbh_root = NULL; \ - self->tree.cmp = K##2##V##TreeMap_cmp; \ - self->tree.augment = NULL; \ - } \ - K##2##V##TreeMapIter K##2##V##TreeMap_insert(K##2##V##TreeMap *self, K key, V value) { \ - K##2##V##TreeMapNode *newnode = malloc(sizeof(K##2##V##TreeMapNode)); \ - newnode->key = key; \ - newnode->value = value; \ - return rb_tree_insert(&self->tree, newnode); \ - } \ - K##2##V##TreeMapIter K##2##V##TreeMap_find(K##2##V##TreeMap *self, K key) { \ - return rb_tree_find(&self->tree, &key); \ - } \ - V* K##2##V##TreeMap_get(K##2##V##TreeMap *self, K key) { \ - K##2##V##TreeMapIter iter = rb_tree_find(&self->tree, &key); \ - return &iter->value; \ - } \ - void K##2##V##TreeMap_remove(K##2##V##TreeMap *self, K##2##V##TreeMapIter iter) { \ - rb_tree_remove(self, iter); \ - } \ - K##2##V##TreeMapIter K##2##V##TreeMap_next(K##2##V##TreeMap *self, K##2##V##TreeMapIter iter) { \ - return rb_tree_next(&self->tree, iter); \ - } \ - K##2##V##TreeMapIter K##2##V##TreeMap_min(K##2##V##TreeMap *self) { \ - return rb_tree_min(&self->tree); \ - } \ - K##2##V##TreeMapIter K##2##V##TreeMap_max(K##2##V##TreeMap *self) { \ - return rb_tree_max(&self->tree); \ - } \ - K##2##V##TreeMapIter K##2##V##TreeMap_left(K##2##V##TreeMapIter iter) { \ - return rb_tree_left(iter); \ - } \ - K##2##V##TreeMapIter K##2##V##TreeMap_right(K##2##V##TreeMapIter iter) { \ - return rb_tree_right(iter); \ - } \ - K##2##V##TreeMapIter K##2##V##TreeMap_parent(K##2##V##TreeMapIter iter) { \ - return rb_tree_parent(iter); \ - } \ - -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 RBNode; - -struct rb_tree { - RBNode *rbh_root; - int (*cmp)(void *k1, void *k2); - void (*augment)(void *elm); -}; -typedef struct rb_tree RBTree; - -void rb_tree_remove(RBTree *, void *iter); - -// return a iterator -void *rb_tree_insert(RBTree *, void *treenode); -void *rb_tree_find(RBTree *, void *val); -void *rb_tree_next(RBTree *, void *iter); -void *rb_tree_min(RBTree *); -void *rb_tree_max(RBTree *); -void *rb_tree_left(void *node); -void *rb_tree_right(void *node); -void *rb_tree_parent(void *node); - -void destroy_rb_tree(RBTree *, void (*freeCb)(void *)); - -TREE_MAP_DEF(String, Int); -TREE_MAP_DEF(String, String); -TREE_MAP_DEF(String, Double); -TREE_MAP_DEF(String, VoidPtr); -TREE_MAP_DEF(Int, Int); -TREE_MAP_DEF(Int, Double); -TREE_MAP_DEF(VoidPtr, Int); -TREE_MAP_DEF(VoidPtr, String); -TREE_MAP_DEF(VoidPtr, VoidPtr); - -#endif - diff --git a/src/sort.c b/src/sort.c deleted file mode 100644 index ed5a1e3..0000000 --- a/src/sort.c +++ /dev/null @@ -1,14 +0,0 @@ -#include "sort.h" - -#include "basic_traits.h" - - -QSORT_IMPL(Int); -QSORT_IMPL(Bool); -QSORT_IMPL(Long); -QSORT_IMPL(Char); -QSORT_IMPL(UInt); -QSORT_IMPL(ULong); -QSORT_IMPL(Double); -QSORT_IMPL(Float); -QSORT_IMPL(String); diff --git a/src/sort.h b/src/sort.h deleted file mode 100644 index 9266093..0000000 --- a/src/sort.h +++ /dev/null @@ -1,54 +0,0 @@ -#ifndef ALGDS_SORT_H_ -#define ALGDS_SORT_H_ - -#include -#include - -#include "type_alias.h" - -#define QSORT_DEF(T) \ - void T##_qsort(T* arr, int n); - -#define QSORT_IMPL(T) \ - void T##_qsort_swap(T* arr, int lhs, int rhs) { \ - if (lhs == rhs) return; \ - T buf; \ - buf = arr[lhs]; \ - arr[lhs] = arr[rhs]; \ - arr[rhs] = buf; \ - } \ - void T##_qsort(T* arr, int n) { \ - if (n <= 1) return; \ - int pivot = rand() % n; \ - T##_qsort_swap(arr, 0, pivot); \ - int lp = 1, rp = n-1; \ - while (lp < rp) { \ - if (T##_cmp(arr[lp], arr[0]) < 0) { \ - lp++; \ - continue; \ - } \ - if (T##_cmp(arr[rp], arr[0]) >= 0) { \ - rp--; \ - continue; \ - } \ - T##_qsort_swap(arr, lp, rp); \ - lp++; \ - rp--; \ - } \ - if (T##_cmp(arr[rp], arr[0]) > 0) rp--; \ - T##_qsort_swap(arr, 0, rp); \ - T##_qsort(arr, rp); \ - T##_qsort(arr+rp+1, n-rp-1); \ - } - -QSORT_DEF(Int); -QSORT_DEF(Bool); -QSORT_DEF(Long); -QSORT_DEF(Char); -QSORT_DEF(UInt); -QSORT_DEF(ULong); -QSORT_DEF(Double); -QSORT_DEF(Float); -QSORT_DEF(String); - -#endif diff --git a/src/str.c b/src/str.c deleted file mode 100644 index 2d7d177..0000000 --- a/src/str.c +++ /dev/null @@ -1,137 +0,0 @@ -#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); - 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 (end >= begin && isspace(*end)) { - 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); - sb->size += size; -} - -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 deleted file mode 100644 index 441451e..0000000 --- a/src/str.h +++ /dev/null @@ -1,24 +0,0 @@ -#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/src/tree_map.c b/src/tree_map.c deleted file mode 100644 index 0232a54..0000000 --- a/src/tree_map.c +++ /dev/null @@ -1,398 +0,0 @@ -/* - * 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 "tree_map.h" - -#include "basic_traits.h" - -#define RED 1 -#define BLACK 0 - -TREE_MAP_IMPL(String, Int); -TREE_MAP_IMPL(String, String); -TREE_MAP_IMPL(String, Double); -TREE_MAP_IMPL(String, VoidPtr); -TREE_MAP_IMPL(Int, Int); -TREE_MAP_IMPL(Int, Double); -TREE_MAP_IMPL(VoidPtr, Int); -TREE_MAP_IMPL(VoidPtr, String); -TREE_MAP_IMPL(VoidPtr, VoidPtr); - -static RBNode *rb_tree_minmax(RBTree *, int); -void *rb_tree_min(RBTree *head) { return rb_tree_minmax(head, -1); } -void *rb_tree_max(RBTree *head) { return rb_tree_minmax(head, 1); } - -void *rb_tree_left(void *node) { - RBNode *elm = node; - if (node == NULL) return NULL; - return elm->entry.rbe_left; -} -void *rb_tree_right(void *node) { - RBNode *elm = node; - if (node == NULL) return NULL; - return elm->entry.rbe_right; -} -void *rb_tree_parent(void *node) { - RBNode *elm = node; - if (node == NULL) return NULL; - return elm->entry.rbe_parent; -} - -static void augment(RBTree *head, RBNode *elm) { - if (head->augment != NULL) head->augment(elm); -} - -static void rb_tree_insert_color(RBTree *head, RBNode *elm); -static void rb_tree_remove_color(RBTree *head, RBNode *parent, - RBNode *elm); - -static void rotate_left(RBTree *head, RBNode *elm) { - RBNode *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(RBTree *head, RBNode *elm) { - RBNode *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(RBTree *head, RBNode *elm) { - RBNode *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(RBTree *head, RBNode *parent, - RBNode *elm) { - RBNode *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) { - RBNode *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) { - RBNode *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(RBTree *head, void *elmv) { - RBNode *elm = elmv; - RBNode *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 { - RBNode *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; - RBNode *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(RBTree *head, void *elmv) { - RBNode *elm = elmv; - RBNode *tmp; - RBNode *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; - RBNode *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(RBTree *head, void *key) { - RBNode *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(RBTree *head, void *elmv) { - RBNode *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 RBNode *rb_tree_minmax(RBTree *head, int val) { - RBNode *tmp = head->rbh_root; - RBNode *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(RBNode *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(RBTree *head, void (*free_cb)(void *)) { - destroy_rb_tree_impl(head->rbh_root, free_cb); -} diff --git a/src/tree_map.h b/src/tree_map.h deleted file mode 100644 index 5e905a8..0000000 --- a/src/tree_map.h +++ /dev/null @@ -1,148 +0,0 @@ -/* - * 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 - -#include "type_alias.h" - -#define TREE_MAP_DEF(K, V) \ - typedef struct { \ - RBNode rbnode; \ - K key; \ - V value; \ - } K##2##V##TreeMapNode; \ - typedef K##2##V##TreeMapNode *K##2##V##TreeMapIter; \ - typedef struct { \ - RBTree tree; \ - } K##2##V##TreeMap; \ - void K##2##V##TreeMap_init(K##2##V##TreeMap *self); \ - K##2##V##TreeMapIter K##2##V##TreeMap_insert(K##2##V##TreeMap *self, K key, V value); \ - K##2##V##TreeMapIter K##2##V##TreeMap_find(K##2##V##TreeMap *self, K key); \ - V* K##2##V##TreeMap_get(K##2##V##TreeMap *self, K key); \ - K##2##V##TreeMapIter K##2##V##TreeMap_next(K##2##V##TreeMap *self, K##2##V##TreeMapIter iter); \ - K##2##V##TreeMapIter K##2##V##TreeMap_min(K##2##V##TreeMap *self); \ - K##2##V##TreeMapIter K##2##V##TreeMap_max(K##2##V##TreeMap *self); \ - void K##2##V##TreeMap_remove(K##2##V##TreeMap *self, K##2##V##TreeMapIter iter); \ - K##2##V##TreeMapIter K##2##V##TreeMap_left(K##2##V##TreeMapIter iter); \ - K##2##V##TreeMapIter K##2##V##TreeMap_right(K##2##V##TreeMapIter iter); \ - K##2##V##TreeMapIter K##2##V##TreeMap_parent(K##2##V##TreeMapIter iter); \ - void K##2##V##TreeMap_free(K##2##V##TreeMap *self); \ - -#define TREE_MAP_IMPL(K, V) \ - static int K##2##V##TreeMap_cmp(void *vlhs, void *vrhs) { \ - K *lhs = vlhs, *rhs = vrhs; \ - return K##_cmp(*lhs, *rhs); \ - } \ - void K##2##V##TreeMap_init(K##2##V##TreeMap *self) { \ - self->tree.rbh_root = NULL; \ - self->tree.cmp = K##2##V##TreeMap_cmp; \ - self->tree.augment = NULL; \ - } \ - K##2##V##TreeMapIter K##2##V##TreeMap_insert(K##2##V##TreeMap *self, K key, V value) { \ - K##2##V##TreeMapNode *newnode = malloc(sizeof(K##2##V##TreeMapNode)); \ - newnode->key = key; \ - newnode->value = value; \ - return rb_tree_insert(&self->tree, newnode); \ - } \ - K##2##V##TreeMapIter K##2##V##TreeMap_find(K##2##V##TreeMap *self, K key) { \ - return rb_tree_find(&self->tree, &key); \ - } \ - V* K##2##V##TreeMap_get(K##2##V##TreeMap *self, K key) { \ - K##2##V##TreeMapIter iter = rb_tree_find(&self->tree, &key); \ - if (iter == NULL) return NULL; \ - return &iter->value; \ - } \ - void K##2##V##TreeMap_remove(K##2##V##TreeMap *self, K##2##V##TreeMapIter iter) { \ - rb_tree_remove(&self->tree, iter); \ - } \ - K##2##V##TreeMapIter K##2##V##TreeMap_next(K##2##V##TreeMap *self, K##2##V##TreeMapIter iter) { \ - return rb_tree_next(&self->tree, iter); \ - } \ - K##2##V##TreeMapIter K##2##V##TreeMap_min(K##2##V##TreeMap *self) { \ - return rb_tree_min(&self->tree); \ - } \ - K##2##V##TreeMapIter K##2##V##TreeMap_max(K##2##V##TreeMap *self) { \ - return rb_tree_max(&self->tree); \ - } \ - K##2##V##TreeMapIter K##2##V##TreeMap_left(K##2##V##TreeMapIter iter) { \ - return rb_tree_left(iter); \ - } \ - K##2##V##TreeMapIter K##2##V##TreeMap_right(K##2##V##TreeMapIter iter) { \ - return rb_tree_right(iter); \ - } \ - K##2##V##TreeMapIter K##2##V##TreeMap_parent(K##2##V##TreeMapIter iter) { \ - return rb_tree_parent(iter); \ - } \ - void K##2##V##TreeMap_free(K##2##V##TreeMap *self) { \ - return destroy_rb_tree(&self->tree, NULL); \ - } \ - -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 RBNode; - -struct rb_tree { - RBNode *rbh_root; - int (*cmp)(void *k1, void *k2); - void (*augment)(void *elm); -}; -typedef struct rb_tree RBTree; - -void rb_tree_remove(RBTree *, void *iter); - -// return a iterator -void *rb_tree_insert(RBTree *, void *treenode); -void *rb_tree_find(RBTree *, void *val); -void *rb_tree_next(RBTree *, void *iter); -void *rb_tree_min(RBTree *); -void *rb_tree_max(RBTree *); -void *rb_tree_left(void *node); -void *rb_tree_right(void *node); -void *rb_tree_parent(void *node); - -void destroy_rb_tree(RBTree *, void (*freeCb)(void *)); - -TREE_MAP_DEF(String, Int); -TREE_MAP_DEF(String, String); -TREE_MAP_DEF(String, Double); -TREE_MAP_DEF(String, VoidPtr); -TREE_MAP_DEF(Int, Int); -TREE_MAP_DEF(Int, Double); -TREE_MAP_DEF(VoidPtr, Int); -TREE_MAP_DEF(VoidPtr, String); -TREE_MAP_DEF(VoidPtr, VoidPtr); - -#endif - diff --git a/src/type_alias.h b/src/type_alias.h deleted file mode 100644 index 8f818ed..0000000 --- a/src/type_alias.h +++ /dev/null @@ -1,19 +0,0 @@ -#ifndef ALGDS_TYPE_ALIAS_H_ -#define ALGDS_TYPE_ALIAS_H_ - -#include -#include - -typedef bool Bool; -typedef int32_t Int; -typedef int64_t Long; -typedef uint32_t UInt; -typedef uint64_t ULong; -typedef char Char; -typedef float Float; -typedef double Double; -typedef const char *String; -typedef const void *VoidPtr; - - -#endif diff --git a/src/vec.c b/src/vec.c deleted file mode 100644 index 9e9abe5..0000000 --- a/src/vec.c +++ /dev/null @@ -1,16 +0,0 @@ -#include "vec.h" - -#include - -#include "basic_traits.h" - -VECTOR_IMPL(Int); -VECTOR_IMPL(Bool); -VECTOR_IMPL(Long); -VECTOR_IMPL(Char); -VECTOR_IMPL(UInt); -VECTOR_IMPL(ULong); -VECTOR_IMPL(Double); -VECTOR_IMPL(Float); -VECTOR_IMPL(String); -VECTOR_IMPL(VoidPtr); diff --git a/src/vec.h b/src/vec.h deleted file mode 100644 index df2242d..0000000 --- a/src/vec.h +++ /dev/null @@ -1,117 +0,0 @@ -#ifndef ALGDS_VEC_H_ -#define ALGDS_VEC_H_ - -#include -#include -#include - -#include "type_alias.h" - -#define VECTOR_DEF(T) \ - typedef struct { \ - T* buffer; \ - int size; \ - int cap; \ - } T##Vector; \ - \ - void T##Vector_init(T##Vector *self); \ - void T##Vector_push_back(T##Vector *self, T elem); \ - void T##Vector_insert_before(T##Vector *self, int n, T elem); \ - void T##Vector_pop(T##Vector *self); \ - bool T##Vector_empty(T##Vector *self); \ - void T##Vector_remove(T##Vector *self, size_t n); \ - size_t T##Vector_len(T##Vector *self); \ - T* T##Vector_begin(T##Vector *self); \ - T* T##Vector_last(T##Vector *self); \ - T* T##Vector_end(T##Vector *self); \ - T* T##Vector_ref(T##Vector *self, size_t n); \ - void T##Vector_swap(T##Vector *self, int i, int j); \ - T##Vector T##Vector_move(T##Vector *self); \ - void T##Vector_show(T##Vector *self, FILE* fp); \ - void T##Vector_free(T##Vector *self); - -#define VECTOR_IMPL(T) \ - void T##Vector_init(T##Vector *self) { \ - self->buffer = (T*)malloc(sizeof(T) * 16); \ - self->cap = 16; \ - self->size = 0; \ - } \ - \ - void T##Vector_push_back(T##Vector *self, T elem) { \ - if (self->size + 1 > self->cap) { \ - self->buffer = realloc(self->buffer, sizeof(T) * self->cap * 2); \ - self->cap *= 2; \ - } \ - self->buffer[self->size] = elem; \ - self->size += 1; \ - } \ - void T##Vector_insert_before(T##Vector *self, int n, T elem) { \ - if (n < 0 || n > self->size) { \ - return; \ - } \ - if (self->size + 1 > self->cap) { \ - self->buffer = malloc(sizeof(T) * self->cap * 2); \ - self->cap *= 2; \ - } \ - if (n != self->size) { \ - memmove(self->buffer + n + 1, \ - self->buffer + n, \ - sizeof(T) * (self->size - n)); \ - self->buffer[n] = elem; \ - self->size += 1; \ - } \ - } \ - void T##Vector_pop(T##Vector *self) { \ - self->size -= 1; \ - } \ - void T##Vector_remove(T##Vector *self, size_t n) { \ - if (n < 0 || n >= self->size) return; \ - memmove(self->buffer + n, \ - self->buffer + n + 1, \ - sizeof(T) * self->size - n - 1); \ - self->size -= 1; \ - } \ - T* T##Vector_begin(T##Vector *self) { return self->buffer; } \ - bool T##Vector_empty(T##Vector *self) { return self->size == 0; } \ - T* T##Vector_end(T##Vector *self) { return self->buffer + self->size; } \ - T* T##Vector_last(T##Vector *self) { return self->buffer + self->size - 1; } \ - T* T##Vector_ref(T##Vector *self, size_t n) { return self->buffer + n; } \ - void T##Vector_swap(T##Vector *self, int i, int j) { \ - T buf; \ - memcpy(&buf, self->buffer + i, sizeof(T)); \ - memcpy(self->buffer + i, self->buffer + j, sizeof(T)); \ - memcpy(self->buffer + j, &buf, sizeof(T)); \ - } \ - T##Vector T##Vector_move(T##Vector *self) { \ - T##Vector dup = *self; \ - self->buffer = NULL; \ - self->size = 0; \ - self->cap = 0; \ - return dup; \ - } \ - void T##Vector_show(T##Vector *self, FILE* fp) { \ - fprintf(fp, "["); \ - for (int i = 0; i < self->size-1; i++) { \ - T##_show(self->buffer[i], fp); \ - fprintf(fp, ", "); \ - } \ - if (self->size > 1) { \ - T##_show(self->buffer[self->size - 1], fp); \ - } \ - fprintf(fp, "]"); \ - } \ - size_t T##Vector_len(T##Vector *self) { return self->size; } \ - void T##Vector_free(T##Vector *self) { free(self->buffer); } - -VECTOR_DEF(Int); -VECTOR_DEF(Bool); -VECTOR_DEF(Long); -VECTOR_DEF(Char); -VECTOR_DEF(UInt); -VECTOR_DEF(ULong); -VECTOR_DEF(Double); -VECTOR_DEF(Float); -VECTOR_DEF(String); -VECTOR_DEF(VoidPtr); - -#endif diff --git a/str.c b/str.c new file mode 100644 index 0000000..2d7d177 --- /dev/null +++ b/str.c @@ -0,0 +1,137 @@ +#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); + 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 (end >= begin && isspace(*end)) { + 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); + sb->size += size; +} + +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/str.h b/str.h new file mode 100644 index 0000000..441451e --- /dev/null +++ b/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/tree_map.c b/tree_map.c new file mode 100644 index 0000000..0232a54 --- /dev/null +++ b/tree_map.c @@ -0,0 +1,398 @@ +/* + * 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 "tree_map.h" + +#include "basic_traits.h" + +#define RED 1 +#define BLACK 0 + +TREE_MAP_IMPL(String, Int); +TREE_MAP_IMPL(String, String); +TREE_MAP_IMPL(String, Double); +TREE_MAP_IMPL(String, VoidPtr); +TREE_MAP_IMPL(Int, Int); +TREE_MAP_IMPL(Int, Double); +TREE_MAP_IMPL(VoidPtr, Int); +TREE_MAP_IMPL(VoidPtr, String); +TREE_MAP_IMPL(VoidPtr, VoidPtr); + +static RBNode *rb_tree_minmax(RBTree *, int); +void *rb_tree_min(RBTree *head) { return rb_tree_minmax(head, -1); } +void *rb_tree_max(RBTree *head) { return rb_tree_minmax(head, 1); } + +void *rb_tree_left(void *node) { + RBNode *elm = node; + if (node == NULL) return NULL; + return elm->entry.rbe_left; +} +void *rb_tree_right(void *node) { + RBNode *elm = node; + if (node == NULL) return NULL; + return elm->entry.rbe_right; +} +void *rb_tree_parent(void *node) { + RBNode *elm = node; + if (node == NULL) return NULL; + return elm->entry.rbe_parent; +} + +static void augment(RBTree *head, RBNode *elm) { + if (head->augment != NULL) head->augment(elm); +} + +static void rb_tree_insert_color(RBTree *head, RBNode *elm); +static void rb_tree_remove_color(RBTree *head, RBNode *parent, + RBNode *elm); + +static void rotate_left(RBTree *head, RBNode *elm) { + RBNode *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(RBTree *head, RBNode *elm) { + RBNode *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(RBTree *head, RBNode *elm) { + RBNode *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(RBTree *head, RBNode *parent, + RBNode *elm) { + RBNode *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) { + RBNode *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) { + RBNode *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(RBTree *head, void *elmv) { + RBNode *elm = elmv; + RBNode *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 { + RBNode *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; + RBNode *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(RBTree *head, void *elmv) { + RBNode *elm = elmv; + RBNode *tmp; + RBNode *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; + RBNode *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(RBTree *head, void *key) { + RBNode *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(RBTree *head, void *elmv) { + RBNode *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 RBNode *rb_tree_minmax(RBTree *head, int val) { + RBNode *tmp = head->rbh_root; + RBNode *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(RBNode *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(RBTree *head, void (*free_cb)(void *)) { + destroy_rb_tree_impl(head->rbh_root, free_cb); +} diff --git a/tree_map.h b/tree_map.h new file mode 100644 index 0000000..5e905a8 --- /dev/null +++ b/tree_map.h @@ -0,0 +1,148 @@ +/* + * 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 + +#include "type_alias.h" + +#define TREE_MAP_DEF(K, V) \ + typedef struct { \ + RBNode rbnode; \ + K key; \ + V value; \ + } K##2##V##TreeMapNode; \ + typedef K##2##V##TreeMapNode *K##2##V##TreeMapIter; \ + typedef struct { \ + RBTree tree; \ + } K##2##V##TreeMap; \ + void K##2##V##TreeMap_init(K##2##V##TreeMap *self); \ + K##2##V##TreeMapIter K##2##V##TreeMap_insert(K##2##V##TreeMap *self, K key, V value); \ + K##2##V##TreeMapIter K##2##V##TreeMap_find(K##2##V##TreeMap *self, K key); \ + V* K##2##V##TreeMap_get(K##2##V##TreeMap *self, K key); \ + K##2##V##TreeMapIter K##2##V##TreeMap_next(K##2##V##TreeMap *self, K##2##V##TreeMapIter iter); \ + K##2##V##TreeMapIter K##2##V##TreeMap_min(K##2##V##TreeMap *self); \ + K##2##V##TreeMapIter K##2##V##TreeMap_max(K##2##V##TreeMap *self); \ + void K##2##V##TreeMap_remove(K##2##V##TreeMap *self, K##2##V##TreeMapIter iter); \ + K##2##V##TreeMapIter K##2##V##TreeMap_left(K##2##V##TreeMapIter iter); \ + K##2##V##TreeMapIter K##2##V##TreeMap_right(K##2##V##TreeMapIter iter); \ + K##2##V##TreeMapIter K##2##V##TreeMap_parent(K##2##V##TreeMapIter iter); \ + void K##2##V##TreeMap_free(K##2##V##TreeMap *self); \ + +#define TREE_MAP_IMPL(K, V) \ + static int K##2##V##TreeMap_cmp(void *vlhs, void *vrhs) { \ + K *lhs = vlhs, *rhs = vrhs; \ + return K##_cmp(*lhs, *rhs); \ + } \ + void K##2##V##TreeMap_init(K##2##V##TreeMap *self) { \ + self->tree.rbh_root = NULL; \ + self->tree.cmp = K##2##V##TreeMap_cmp; \ + self->tree.augment = NULL; \ + } \ + K##2##V##TreeMapIter K##2##V##TreeMap_insert(K##2##V##TreeMap *self, K key, V value) { \ + K##2##V##TreeMapNode *newnode = malloc(sizeof(K##2##V##TreeMapNode)); \ + newnode->key = key; \ + newnode->value = value; \ + return rb_tree_insert(&self->tree, newnode); \ + } \ + K##2##V##TreeMapIter K##2##V##TreeMap_find(K##2##V##TreeMap *self, K key) { \ + return rb_tree_find(&self->tree, &key); \ + } \ + V* K##2##V##TreeMap_get(K##2##V##TreeMap *self, K key) { \ + K##2##V##TreeMapIter iter = rb_tree_find(&self->tree, &key); \ + if (iter == NULL) return NULL; \ + return &iter->value; \ + } \ + void K##2##V##TreeMap_remove(K##2##V##TreeMap *self, K##2##V##TreeMapIter iter) { \ + rb_tree_remove(&self->tree, iter); \ + } \ + K##2##V##TreeMapIter K##2##V##TreeMap_next(K##2##V##TreeMap *self, K##2##V##TreeMapIter iter) { \ + return rb_tree_next(&self->tree, iter); \ + } \ + K##2##V##TreeMapIter K##2##V##TreeMap_min(K##2##V##TreeMap *self) { \ + return rb_tree_min(&self->tree); \ + } \ + K##2##V##TreeMapIter K##2##V##TreeMap_max(K##2##V##TreeMap *self) { \ + return rb_tree_max(&self->tree); \ + } \ + K##2##V##TreeMapIter K##2##V##TreeMap_left(K##2##V##TreeMapIter iter) { \ + return rb_tree_left(iter); \ + } \ + K##2##V##TreeMapIter K##2##V##TreeMap_right(K##2##V##TreeMapIter iter) { \ + return rb_tree_right(iter); \ + } \ + K##2##V##TreeMapIter K##2##V##TreeMap_parent(K##2##V##TreeMapIter iter) { \ + return rb_tree_parent(iter); \ + } \ + void K##2##V##TreeMap_free(K##2##V##TreeMap *self) { \ + return destroy_rb_tree(&self->tree, NULL); \ + } \ + +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 RBNode; + +struct rb_tree { + RBNode *rbh_root; + int (*cmp)(void *k1, void *k2); + void (*augment)(void *elm); +}; +typedef struct rb_tree RBTree; + +void rb_tree_remove(RBTree *, void *iter); + +// return a iterator +void *rb_tree_insert(RBTree *, void *treenode); +void *rb_tree_find(RBTree *, void *val); +void *rb_tree_next(RBTree *, void *iter); +void *rb_tree_min(RBTree *); +void *rb_tree_max(RBTree *); +void *rb_tree_left(void *node); +void *rb_tree_right(void *node); +void *rb_tree_parent(void *node); + +void destroy_rb_tree(RBTree *, void (*freeCb)(void *)); + +TREE_MAP_DEF(String, Int); +TREE_MAP_DEF(String, String); +TREE_MAP_DEF(String, Double); +TREE_MAP_DEF(String, VoidPtr); +TREE_MAP_DEF(Int, Int); +TREE_MAP_DEF(Int, Double); +TREE_MAP_DEF(VoidPtr, Int); +TREE_MAP_DEF(VoidPtr, String); +TREE_MAP_DEF(VoidPtr, VoidPtr); + +#endif + diff --git a/type_alias.h b/type_alias.h new file mode 100644 index 0000000..8f818ed --- /dev/null +++ b/type_alias.h @@ -0,0 +1,19 @@ +#ifndef ALGDS_TYPE_ALIAS_H_ +#define ALGDS_TYPE_ALIAS_H_ + +#include +#include + +typedef bool Bool; +typedef int32_t Int; +typedef int64_t Long; +typedef uint32_t UInt; +typedef uint64_t ULong; +typedef char Char; +typedef float Float; +typedef double Double; +typedef const char *String; +typedef const void *VoidPtr; + + +#endif diff --git a/vec.c b/vec.c new file mode 100644 index 0000000..9e9abe5 --- /dev/null +++ b/vec.c @@ -0,0 +1,16 @@ +#include "vec.h" + +#include + +#include "basic_traits.h" + +VECTOR_IMPL(Int); +VECTOR_IMPL(Bool); +VECTOR_IMPL(Long); +VECTOR_IMPL(Char); +VECTOR_IMPL(UInt); +VECTOR_IMPL(ULong); +VECTOR_IMPL(Double); +VECTOR_IMPL(Float); +VECTOR_IMPL(String); +VECTOR_IMPL(VoidPtr); diff --git a/vec.h b/vec.h new file mode 100644 index 0000000..df2242d --- /dev/null +++ b/vec.h @@ -0,0 +1,117 @@ +#ifndef ALGDS_VEC_H_ +#define ALGDS_VEC_H_ + +#include +#include +#include + +#include "type_alias.h" + +#define VECTOR_DEF(T) \ + typedef struct { \ + T* buffer; \ + int size; \ + int cap; \ + } T##Vector; \ + \ + void T##Vector_init(T##Vector *self); \ + void T##Vector_push_back(T##Vector *self, T elem); \ + void T##Vector_insert_before(T##Vector *self, int n, T elem); \ + void T##Vector_pop(T##Vector *self); \ + bool T##Vector_empty(T##Vector *self); \ + void T##Vector_remove(T##Vector *self, size_t n); \ + size_t T##Vector_len(T##Vector *self); \ + T* T##Vector_begin(T##Vector *self); \ + T* T##Vector_last(T##Vector *self); \ + T* T##Vector_end(T##Vector *self); \ + T* T##Vector_ref(T##Vector *self, size_t n); \ + void T##Vector_swap(T##Vector *self, int i, int j); \ + T##Vector T##Vector_move(T##Vector *self); \ + void T##Vector_show(T##Vector *self, FILE* fp); \ + void T##Vector_free(T##Vector *self); + +#define VECTOR_IMPL(T) \ + void T##Vector_init(T##Vector *self) { \ + self->buffer = (T*)malloc(sizeof(T) * 16); \ + self->cap = 16; \ + self->size = 0; \ + } \ + \ + void T##Vector_push_back(T##Vector *self, T elem) { \ + if (self->size + 1 > self->cap) { \ + self->buffer = realloc(self->buffer, sizeof(T) * self->cap * 2); \ + self->cap *= 2; \ + } \ + self->buffer[self->size] = elem; \ + self->size += 1; \ + } \ + void T##Vector_insert_before(T##Vector *self, int n, T elem) { \ + if (n < 0 || n > self->size) { \ + return; \ + } \ + if (self->size + 1 > self->cap) { \ + self->buffer = malloc(sizeof(T) * self->cap * 2); \ + self->cap *= 2; \ + } \ + if (n != self->size) { \ + memmove(self->buffer + n + 1, \ + self->buffer + n, \ + sizeof(T) * (self->size - n)); \ + self->buffer[n] = elem; \ + self->size += 1; \ + } \ + } \ + void T##Vector_pop(T##Vector *self) { \ + self->size -= 1; \ + } \ + void T##Vector_remove(T##Vector *self, size_t n) { \ + if (n < 0 || n >= self->size) return; \ + memmove(self->buffer + n, \ + self->buffer + n + 1, \ + sizeof(T) * self->size - n - 1); \ + self->size -= 1; \ + } \ + T* T##Vector_begin(T##Vector *self) { return self->buffer; } \ + bool T##Vector_empty(T##Vector *self) { return self->size == 0; } \ + T* T##Vector_end(T##Vector *self) { return self->buffer + self->size; } \ + T* T##Vector_last(T##Vector *self) { return self->buffer + self->size - 1; } \ + T* T##Vector_ref(T##Vector *self, size_t n) { return self->buffer + n; } \ + void T##Vector_swap(T##Vector *self, int i, int j) { \ + T buf; \ + memcpy(&buf, self->buffer + i, sizeof(T)); \ + memcpy(self->buffer + i, self->buffer + j, sizeof(T)); \ + memcpy(self->buffer + j, &buf, sizeof(T)); \ + } \ + T##Vector T##Vector_move(T##Vector *self) { \ + T##Vector dup = *self; \ + self->buffer = NULL; \ + self->size = 0; \ + self->cap = 0; \ + return dup; \ + } \ + void T##Vector_show(T##Vector *self, FILE* fp) { \ + fprintf(fp, "["); \ + for (int i = 0; i < self->size-1; i++) { \ + T##_show(self->buffer[i], fp); \ + fprintf(fp, ", "); \ + } \ + if (self->size > 1) { \ + T##_show(self->buffer[self->size - 1], fp); \ + } \ + fprintf(fp, "]"); \ + } \ + size_t T##Vector_len(T##Vector *self) { return self->size; } \ + void T##Vector_free(T##Vector *self) { free(self->buffer); } + +VECTOR_DEF(Int); +VECTOR_DEF(Bool); +VECTOR_DEF(Long); +VECTOR_DEF(Char); +VECTOR_DEF(UInt); +VECTOR_DEF(ULong); +VECTOR_DEF(Double); +VECTOR_DEF(Float); +VECTOR_DEF(String); +VECTOR_DEF(VoidPtr); + +#endif -- cgit v1.0