aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/basic_traits.c76
-rw-r--r--src/basic_traits.h27
-rw-r--r--src/hash_table.c119
-rw-r--r--src/hash_table.h105
-rw-r--r--src/list.c3
-rw-r--r--src/list.h134
-rw-r--r--src/mmhash.c57
-rw-r--r--src/mmhash.h8
-rw-r--r--src/pqueue.c17
-rw-r--r--src/pqueue.h79
-rw-r--r--src/rb_tree.h143
-rw-r--r--src/sort.c14
-rw-r--r--src/sort.h54
-rw-r--r--src/str.c137
-rw-r--r--src/str.h24
-rw-r--r--src/tree_map.c398
-rw-r--r--src/tree_map.h148
-rw-r--r--src/type_alias.h19
-rw-r--r--src/vec.c16
-rw-r--r--src/vec.h117
20 files changed, 0 insertions, 1695 deletions
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 <string.h>
-#include <inttypes.h>
-
-#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 <stdio.h>
-
-#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 <stdlib.h>
-#include <string.h>
-
-#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 <stdbool.h>
-#include <stdint.h>
-
-#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 <stdlib.h>
-
-#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 <stdint.h>
-
-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 <stdlib.h>
-#include <string.h>
-
-#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 <provos@citi.umich.edu>
- * 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 <stdlib.h>
-
-#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 <stdlib.h>
-#include <string.h>
-
-#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 <ctype.h>
-#include <stdarg.h>
-#include <stdbool.h>
-#include <stddef.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-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 <stdio.h>
-
-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 <provos@citi.umich.edu>
- * 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 <provos@citi.umich.edu>
- * 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 <stdlib.h>
-
-#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 <stdint.h>
-#include <stdbool.h>
-
-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 <string.h>
-
-#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 <stdlib.h>
-#include <string.h>
-#include <stdio.h>
-
-#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
generated by cgit v1.0 at 2025-12-29 20:49:38 +0000