aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--README.md10
-rw-r--r--src/basic_traits.c9
-rw-r--r--src/hash_table.c1
-rw-r--r--src/hash_table.h1
-rw-r--r--src/rb_tree.h79
-rw-r--r--src/tree_map.c (renamed from src/rb_tree.c)14
-rw-r--r--src/tree_map.h148
-rw-r--r--src/type_alias.h8
-rw-r--r--tests/test_augment_rbtree.c2
-rw-r--r--tests/test_rbtree.c42
10 files changed, 296 insertions, 18 deletions
diff --git a/README.md b/README.md
index dc13fd6..ee8d7c4 100644
--- a/README.md
+++ b/README.md
@@ -1,14 +1,14 @@
-# Algorithms and Data Structures
+# Type-safe Generic Algorithms and Data Structures for C
-- Red-black tree
-- Augmented red-black tree
+- Generic Red-black tree
- Generic Vector
- Generic Priority queue
-- Murmur Hash
- Generic Hash Table
+- Generic quick sort
+- Augmented red-black tree
+- Murmur Hash
- String utilities
- Region-based memory management
-- Generic quick sort
## Build
diff --git a/src/basic_traits.c b/src/basic_traits.c
index b7c4d3a..5d2a8fb 100644
--- a/src/basic_traits.c
+++ b/src/basic_traits.c
@@ -1,6 +1,7 @@
#include "basic_traits.h"
#include <string.h>
+#include <inttypes.h>
#include "mmhash.h"
@@ -35,16 +36,16 @@ void Bool_show(Bool self, FILE* fp) {
else fprintf(fp, "false");
}
void Int_show(Int self, FILE* fp) {
- fprintf(fp, "%d", self);
+ fprintf(fp, "%"PRId32, self);
}
void Long_show(Long self, FILE* fp) {
- fprintf(fp, "%lld", self);
+ fprintf(fp, "%"PRId64, self);
}
void UInt_show(UInt self, FILE* fp) {
- fprintf(fp, "%ud", self);
+ fprintf(fp, "%"PRIu32, self);
}
void ULong_show(ULong self, FILE* fp) {
- fprintf(fp, "%llud", self);
+ fprintf(fp, "%"PRIu64, self);
}
void VoidPtr_show(VoidPtr self, FILE* fp) {
fprintf(fp, "%p", self);
diff --git a/src/hash_table.c b/src/hash_table.c
index c768df8..bedeb4a 100644
--- a/src/hash_table.c
+++ b/src/hash_table.c
@@ -16,6 +16,7 @@ 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);
diff --git a/src/hash_table.h b/src/hash_table.h
index ba42628..9b45dff 100644
--- a/src/hash_table.h
+++ b/src/hash_table.h
@@ -92,6 +92,7 @@ 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*));
diff --git a/src/rb_tree.h b/src/rb_tree.h
index 2f00bf0..7c91cea 100644
--- a/src/rb_tree.h
+++ b/src/rb_tree.h
@@ -28,6 +28,75 @@
#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;
@@ -60,5 +129,15 @@ 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/rb_tree.c b/src/tree_map.c
index 10c4418..0232a54 100644
--- a/src/rb_tree.c
+++ b/src/tree_map.c
@@ -23,11 +23,23 @@
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
-#include "rb_tree.h"
+#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); }
diff --git a/src/tree_map.h b/src/tree_map.h
new file mode 100644
index 0000000..5e905a8
--- /dev/null
+++ b/src/tree_map.h
@@ -0,0 +1,148 @@
+/*
+ * 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
index fbee6ef..8f818ed 100644
--- a/src/type_alias.h
+++ b/src/type_alias.h
@@ -5,10 +5,10 @@
#include <stdbool.h>
typedef bool Bool;
-typedef int Int;
-typedef long long Long;
-typedef unsigned int UInt;
-typedef unsigned long long ULong;
+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;
diff --git a/tests/test_augment_rbtree.c b/tests/test_augment_rbtree.c
index 9d671db..73559dc 100644
--- a/tests/test_augment_rbtree.c
+++ b/tests/test_augment_rbtree.c
@@ -3,7 +3,7 @@
#include <string.h>
#include <time.h>
-#include "rb_tree.h"
+#include "tree_map.h"
typedef struct {
RBNode node;
diff --git a/tests/test_rbtree.c b/tests/test_rbtree.c
index 7ef5c61..78453e4 100644
--- a/tests/test_rbtree.c
+++ b/tests/test_rbtree.c
@@ -3,7 +3,7 @@
#include <string.h>
#include <time.h>
-#include "rb_tree.h"
+#include "tree_map.h"
typedef struct {
RBNode node;
@@ -26,8 +26,7 @@ int depth(void *n) {
return max(depth(node->entry.rbe_left), depth(node->entry.rbe_right)) + 1;
}
-int main() {
- printf("[TEST] rbtree\n");
+void basic_test() {
RBTree tree = {NULL, cmpfunc, NULL};
Int2IntRBNode *n;
@@ -56,7 +55,44 @@ int main() {
}
destroy_rb_tree(&tree, NULL);
+}
+
+void tree_map_basic_test() {
+ Int2IntTreeMap tree;
+ Int2IntTreeMap_init(&tree);
+
+ int a[5] = {1, 2, 3, 4, 5};
+ for (int i = 0; i < 5; i++) {
+ Int2IntTreeMap_insert(&tree, a[i], a[i]*2);
+ }
+
+ Int2IntTreeMapIter iter = Int2IntTreeMap_find(&tree, 3);
+ assert(iter->key == 3);
+ assert(iter->value == 6);
+
+ assert(*Int2IntTreeMap_get(&tree, 3) == 6);
+
+ Int2IntTreeMap_remove(&tree, iter);
+ free(iter);
+
+ iter = Int2IntTreeMap_min(&tree);
+ int expected[4] = {1, 2, 4, 5};
+ int i = 0;
+ for (; iter != NULL; iter = Int2IntTreeMap_next(&tree, iter)) {
+ assert(iter->key == expected[i]);
+ i++;
+ }
+ Int2IntTreeMap_free(&tree);
+}
+
+
+int main() {
+ printf("[TEST] rbtree\n");
+
+ basic_test();
+ tree_map_basic_test();
test_largedata();
+
printf("[PASS] rbtree\n");
return 0;
}
generated by cgit v1.0 at 2025-12-29 13:43:04 +0000