From 2f0781104330d1ae4fae041560ee3a5cb892c3b6 Mon Sep 17 00:00:00 2001 From: Mistivia Date: Mon, 9 Jun 2025 17:54:55 +0800 Subject: genenric tree map --- README.md | 10 +- src/basic_traits.c | 9 +- src/hash_table.c | 1 + src/hash_table.h | 1 + src/rb_tree.c | 386 ------------------------------------------ src/rb_tree.h | 79 +++++++++ src/tree_map.c | 398 ++++++++++++++++++++++++++++++++++++++++++++ src/tree_map.h | 148 ++++++++++++++++ src/type_alias.h | 8 +- tests/test_augment_rbtree.c | 2 +- tests/test_rbtree.c | 42 ++++- 11 files changed, 681 insertions(+), 403 deletions(-) delete mode 100644 src/rb_tree.c create mode 100644 src/tree_map.c create mode 100644 src/tree_map.h 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 +#include #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.c b/src/rb_tree.c deleted file mode 100644 index 10c4418..0000000 --- a/src/rb_tree.c +++ /dev/null @@ -1,386 +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 "rb_tree.h" - -#define RED 1 -#define BLACK 0 - -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/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 +#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/tree_map.c b/src/tree_map.c new file mode 100644 index 0000000..0232a54 --- /dev/null +++ b/src/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/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 + * 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 index fbee6ef..8f818ed 100644 --- a/src/type_alias.h +++ b/src/type_alias.h @@ -5,10 +5,10 @@ #include 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 #include -#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 #include -#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; } -- cgit v1.0