crude metaballs
[metatoy] / src / rbtree.c
diff --git a/src/rbtree.c b/src/rbtree.c
deleted file mode 100644 (file)
index 765e542..0000000
+++ /dev/null
@@ -1,518 +0,0 @@
-/*
-rbtree - simple balanced binary search tree (red-black tree) library.
-Copyright (C) 2011-2014  John Tsiombikas <nuclear@member.fsf.org>
-
-rbtree is free software, feel free to use, modify, and redistribute it, under
-the terms of the 3-clause BSD license. See COPYING for details.
-*/
-#include <stdio.h>
-#include <stdlib.h>
-#include <stdint.h>
-#include <string.h>
-#include "rbtree.h"
-
-#define INT2PTR(x)     ((void*)(intptr_t)(x))
-#define PTR2INT(x)     ((int)(intptr_t)(x))
-
-struct rbtree {
-       struct rbnode *root;
-
-       rb_alloc_func_t alloc;
-       rb_free_func_t free;
-
-       rb_cmp_func_t cmp;
-       rb_del_func_t del;
-       void *del_cls;
-
-       struct rbnode *rstack, *iter;
-};
-
-static int cmpaddr(const void *ap, const void *bp);
-static int cmpint(const void *ap, const void *bp);
-
-static int count_nodes(struct rbnode *node);
-static void del_tree(struct rbnode *node, void (*delfunc)(struct rbnode*, void*), void *cls);
-static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data);
-static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key);
-/*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key);*/
-static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls);
-
-struct rbtree *rb_create(rb_cmp_func_t cmp_func)
-{
-       struct rbtree *rb;
-
-       if(!(rb = malloc(sizeof *rb))) {
-               return 0;
-       }
-       if(rb_init(rb, cmp_func) == -1) {
-               free(rb);
-               return 0;
-       }
-       return rb;
-}
-
-void rb_free(struct rbtree *rb)
-{
-       rb_destroy(rb);
-       free(rb);
-}
-
-
-int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func)
-{
-       memset(rb, 0, sizeof *rb);
-
-       if(!cmp_func) {
-               rb->cmp = cmpaddr;
-       } else if(cmp_func == RB_KEY_INT) {
-               rb->cmp = cmpint;
-       } else if(cmp_func == RB_KEY_STRING) {
-               rb->cmp = (rb_cmp_func_t)strcmp;
-       } else {
-               rb->cmp = cmp_func;
-       }
-
-       rb->alloc = malloc;
-       rb->free = free;
-       return 0;
-}
-
-void rb_destroy(struct rbtree *rb)
-{
-       del_tree(rb->root, rb->del, rb->del_cls);
-}
-
-void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free)
-{
-       rb->alloc = alloc;
-       rb->free = free;
-}
-
-
-void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func)
-{
-       rb->cmp = func;
-}
-
-void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls)
-{
-       rb->del = func;
-       rb->del_cls = cls;
-}
-
-
-void rb_clear(struct rbtree *rb)
-{
-       del_tree(rb->root, rb->del, rb->del_cls);
-       rb->root = 0;
-}
-
-int rb_copy(struct rbtree *dest, struct rbtree *src)
-{
-       struct rbnode *node;
-
-       rb_clear(dest);
-       rb_begin(src);
-       while((node = rb_next(src))) {
-               if(rb_insert(dest, node->key, node->data) == -1) {
-                       return -1;
-               }
-       }
-       return 0;
-}
-
-int rb_size(struct rbtree *rb)
-{
-       return count_nodes(rb->root);
-}
-
-int rb_insert(struct rbtree *rb, void *key, void *data)
-{
-       rb->root = insert(rb, rb->root, key, data);
-       rb->root->red = 0;
-       return 0;
-}
-
-int rb_inserti(struct rbtree *rb, int key, void *data)
-{
-       rb->root = insert(rb, rb->root, INT2PTR(key), data);
-       rb->root->red = 0;
-       return 0;
-}
-
-
-int rb_delete(struct rbtree *rb, void *key)
-{
-       if((rb->root = delete(rb, rb->root, key))) {
-               rb->root->red = 0;
-       }
-       return 0;
-}
-
-int rb_deletei(struct rbtree *rb, int key)
-{
-       if((rb->root = delete(rb, rb->root, INT2PTR(key)))) {
-               rb->root->red = 0;
-       }
-       return 0;
-}
-
-
-struct rbnode *rb_find(struct rbtree *rb, void *key)
-{
-       struct rbnode *node = rb->root;
-
-       while(node) {
-               int cmp = rb->cmp(key, node->key);
-               if(cmp == 0) {
-                       return node;
-               }
-               node = cmp < 0 ? node->left : node->right;
-       }
-       return 0;
-}
-
-struct rbnode *rb_findi(struct rbtree *rb, int key)
-{
-       return rb_find(rb, INT2PTR(key));
-}
-
-
-void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls)
-{
-       traverse(rb->root, func, cls);
-}
-
-
-struct rbnode *rb_root(struct rbtree *rb)
-{
-       return rb->root;
-}
-
-void rb_begin(struct rbtree *rb)
-{
-       rb->rstack = 0;
-       rb->iter = rb->root;
-}
-
-#define push(sp, x)            ((x)->next = (sp), (sp) = (x))
-#define pop(sp)                        ((sp) = (sp)->next)
-#define top(sp)                        (sp)
-
-struct rbnode *rb_next(struct rbtree *rb)
-{
-       struct rbnode *res = 0;
-
-       while(rb->rstack || rb->iter) {
-               if(rb->iter) {
-                       push(rb->rstack, rb->iter);
-                       rb->iter = rb->iter->left;
-               } else {
-                       rb->iter = top(rb->rstack);
-                       pop(rb->rstack);
-                       res = rb->iter;
-                       rb->iter = rb->iter->right;
-                       break;
-               }
-       }
-       return res;
-}
-
-void *rb_node_key(struct rbnode *node)
-{
-       return node ? node->key : 0;
-}
-
-int rb_node_keyi(struct rbnode *node)
-{
-       return node ? PTR2INT(node->key) : 0;
-}
-
-void *rb_node_data(struct rbnode *node)
-{
-       return node ? node->data : 0;
-}
-
-void rb_node_setdata(struct rbnode *node, void *data)
-{
-       node->data = data;
-}
-
-static int cmpaddr(const void *ap, const void *bp)
-{
-       return ap < bp ? -1 : (ap > bp ? 1 : 0);
-}
-
-static int cmpint(const void *ap, const void *bp)
-{
-       return PTR2INT(ap) - PTR2INT(bp);
-}
-
-
-/* ---- left-leaning 2-3 red-black implementation ---- */
-
-/* helper prototypes */
-static int is_red(struct rbnode *tree);
-static void color_flip(struct rbnode *tree);
-static struct rbnode *rot_left(struct rbnode *a);
-static struct rbnode *rot_right(struct rbnode *a);
-static struct rbnode *find_min(struct rbnode *tree);
-static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree);
-/*static struct rbnode *move_red_right(struct rbnode *tree);*/
-static struct rbnode *move_red_left(struct rbnode *tree);
-static struct rbnode *fix_up(struct rbnode *tree);
-
-static int count_nodes(struct rbnode *node)
-{
-       if(!node)
-               return 0;
-
-       return 1 + count_nodes(node->left) + count_nodes(node->right);
-}
-
-static void del_tree(struct rbnode *node, rb_del_func_t delfunc, void *cls)
-{
-       if(!node)
-               return;
-
-       del_tree(node->left, delfunc, cls);
-       del_tree(node->right, delfunc, cls);
-
-       if(delfunc) {
-               delfunc(node, cls);
-       }
-       free(node);
-}
-
-static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data)
-{
-       int cmp;
-
-       if(!tree) {
-               struct rbnode *node = rb->alloc(sizeof *node);
-               node->red = 1;
-               node->key = key;
-               node->data = data;
-               node->left = node->right = 0;
-               return node;
-       }
-
-       cmp = rb->cmp(key, tree->key);
-
-       if(cmp < 0) {
-               tree->left = insert(rb, tree->left, key, data);
-       } else if(cmp > 0) {
-               tree->right = insert(rb, tree->right, key, data);
-       } else {
-               if(rb->del) {
-                       /* The key passed in was allocated in a way that would be cleaned by the
-                        * user-supplied delete function. We can't just assign the data and ignore
-                        * key in this case, or we'll leak memory. But we also can't make a dummy
-                        * node and pass that to rb->del, because it might also expect to free data.
-                        * So we must instead delete the existing node's contents, and use the new ones.
-                        */
-                       rb->del(tree, rb->del_cls);
-                       tree->key = key;
-               }
-               tree->data = data;
-       }
-
-       /* fix right-leaning reds */
-       if(is_red(tree->right)) {
-               tree = rot_left(tree);
-       }
-       /* fix two reds in a row */
-       if(is_red(tree->left) && is_red(tree->left->left)) {
-               tree = rot_right(tree);
-       }
-
-       /* if 4-node, split it by color inversion */
-       if(is_red(tree->left) && is_red(tree->right)) {
-               color_flip(tree);
-       }
-
-       return tree;
-}
-
-static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key)
-{
-       int cmp;
-
-       if(!tree) {
-               return 0;
-       }
-
-       cmp = rb->cmp(key, tree->key);
-
-       if(cmp < 0) {
-               if(!is_red(tree->left) && !is_red(tree->left->left)) {
-                       tree = move_red_left(tree);
-               }
-               tree->left = delete(rb, tree->left, key);
-       } else {
-               /* need reds on the right */
-               if(is_red(tree->left)) {
-                       tree = rot_right(tree);
-               }
-
-               /* found it at the bottom (XXX what certifies left is null?) */
-               if(cmp == 0 && !tree->right) {
-                       if(rb->del) {
-                               rb->del(tree, rb->del_cls);
-                       }
-                       rb->free(tree);
-                       return 0;
-               }
-
-               if(!is_red(tree->right) && !is_red(tree->right->left)) {
-                       tree = move_red_left(tree);
-               }
-
-               if(key == tree->key) {
-                       struct rbnode *rmin = find_min(tree->right);
-                       tree->key = rmin->key;
-                       tree->data = rmin->data;
-                       tree->right = del_min(rb, tree->right);
-               } else {
-                       tree->right = delete(rb, tree->right, key);
-               }
-       }
-
-       return fix_up(tree);
-}
-
-/*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key)
-{
-       int cmp;
-
-       if(!node)
-               return 0;
-
-       if((cmp = rb->cmp(key, node->key)) == 0) {
-               return node;
-       }
-       return find(rb, cmp < 0 ? node->left : node->right, key);
-}*/
-
-static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls)
-{
-       if(!node)
-               return;
-
-       traverse(node->left, func, cls);
-       func(node, cls);
-       traverse(node->right, func, cls);
-}
-
-/* helpers */
-
-static int is_red(struct rbnode *tree)
-{
-       return tree && tree->red;
-}
-
-static void color_flip(struct rbnode *tree)
-{
-       tree->red = !tree->red;
-       tree->left->red = !tree->left->red;
-       tree->right->red = !tree->right->red;
-}
-
-static struct rbnode *rot_left(struct rbnode *a)
-{
-       struct rbnode *b = a->right;
-       a->right = b->left;
-       b->left = a;
-       b->red = a->red;
-       a->red = 1;
-       return b;
-}
-
-static struct rbnode *rot_right(struct rbnode *a)
-{
-       struct rbnode *b = a->left;
-       a->left = b->right;
-       b->right = a;
-       b->red = a->red;
-       a->red = 1;
-       return b;
-}
-
-static struct rbnode *find_min(struct rbnode *tree)
-{
-       if(!tree)
-               return 0;
-
-       while(tree->left) {
-               tree = tree->left;
-       }
-       return tree;
-}
-
-static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree)
-{
-       if(!tree->left) {
-               if(rb->del) {
-                       rb->del(tree->left, rb->del_cls);
-               }
-               rb->free(tree->left);
-               return 0;
-       }
-
-       /* make sure we've got red (3/4-nodes) at the left side so we can delete at the bottom */
-       if(!is_red(tree->left) && !is_red(tree->left->left)) {
-               tree = move_red_left(tree);
-       }
-       tree->left = del_min(rb, tree->left);
-
-       /* fix right-reds, red-reds, and split 4-nodes on the way up */
-       return fix_up(tree);
-}
-
-#if 0
-/* push a red link on this node to the right */
-static struct rbnode *move_red_right(struct rbnode *tree)
-{
-       /* flipping it makes both children go red, so we have a red to the right */
-       color_flip(tree);
-
-       /* if after the flip we've got a red-red situation to the left, fix it */
-       if(is_red(tree->left->left)) {
-               tree = rot_right(tree);
-               color_flip(tree);
-       }
-       return tree;
-}
-#endif
-
-/* push a red link on this node to the left */
-static struct rbnode *move_red_left(struct rbnode *tree)
-{
-       /* flipping it makes both children go red, so we have a red to the left */
-       color_flip(tree);
-
-       /* if after the flip we've got a red-red on the right-left, fix it */
-       if(is_red(tree->right->left)) {
-               tree->right = rot_right(tree->right);
-               tree = rot_left(tree);
-               color_flip(tree);
-       }
-       return tree;
-}
-
-static struct rbnode *fix_up(struct rbnode *tree)
-{
-       /* fix right-leaning */
-       if(is_red(tree->right)) {
-               tree = rot_left(tree);
-       }
-       /* change invalid red-red pairs into a proper 4-node */
-       if(is_red(tree->left) && is_red(tree->left->left)) {
-               tree = rot_right(tree);
-       }
-       /* split 4-nodes */
-       if(is_red(tree->left) && is_red(tree->right)) {
-               color_flip(tree);
-       }
-       return tree;
-}