1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/.hgignore	Sun Oct 09 07:48:14 2011 +0300
     1.3 @@ -0,0 +1,6 @@
     1.4 +\.o$
     1.5 +\.d$
     1.6 +\.swp$
     1.7 +^Makefile$
     1.8 +rbtree\.a$
     1.9 +rbtree\.so

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/Makefile.in	Sun Oct 09 07:48:14 2011 +0300
     2.3 @@ -0,0 +1,58 @@
     2.4 +src = $(wildcard src/*.c)
     2.5 +obj = $(src:.c=.o)
     2.6 +dep = $(obj:.o=.d)
     2.7 +
     2.8 +name = rbtree
     2.9 +
    2.10 +AR = ar
    2.11 +CC = gcc
    2.12 +CFLAGS = -pedantic -Wall $(dbg) $(opt) -fPIC
    2.13 +
    2.14 +ifeq ($(shell uname -s), Darwin)
    2.15 +	lib_a = $(name).a
    2.16 +	lib_so = $(name).dylib
    2.17 +	shared = -dynamiclib $(lib_so)
    2.18 +else
    2.19 +	lib_a = lib$(name).a
    2.20 +	devlink = lib$(name).so
    2.21 +	soname = $(devlink).0
    2.22 +	lib_so = $(soname).0
    2.23 +	shared = -shared -Wl,-soname=$(soname)
    2.24 +endif
    2.25 +
    2.26 +.PHONY: all
    2.27 +all: $(lib_so) $(lib_a)
    2.28 +
    2.29 +$(lib_a): $(obj)
    2.30 +	$(AR) rcs $(lib_a) $(obj)
    2.31 +
    2.32 +$(lib_so): $(obj)
    2.33 +	$(CC) -o $@ $(shared) $(obj) $(LDFLAGS)
    2.34 +
    2.35 +-include $(dep)
    2.36 +
    2.37 +%.d: %.c
    2.38 +	@$(CPP) $(CFLAGS) $< -MM -MT $(@:.d=.o) >$@
    2.39 +
    2.40 +.PHONY: clean
    2.41 +clean:
    2.42 +	rm -f $(obj) $(lib_a) $(lib_so)
    2.43 +
    2.44 +.PHONY: install
    2.45 +install:
    2.46 +	mkdir -p $(PREFIX)/include $(PREFIX)/lib
    2.47 +	cp src/rbtree.h $(PREFIX)/include/rbtree.h
    2.48 +	cp $(lib_a) $(PREFIX)/lib/$(lib_a)
    2.49 +	cp $(lib_so) $(PREFIX)/lib/$(lib_so)
    2.50 +	[ -n "$(soname)" ] \
    2.51 +		&& rm -f $(PREFIX)/lib/$(soname) $(PREFIX)/lib/$(devlink) \
    2.52 +		&& ln -s $(PREFIX)/lib/$(lib_so) $(PREFIX)/lib/$(soname) \
    2.53 +		&& ln -s $(PREFIX)/lib/$(soname) $(PREFIX)/lib/$(devlink) \
    2.54 +		|| true
    2.55 +
    2.56 +.PHONY: uninstall
    2.57 +	rm -f $(PREFIX)/include/rbtree.h
    2.58 +	rm -f $(PREFIX)/lib/$(lib_a)
    2.59 +	rm -f $(PREFIX)/lib/$(lib_so)
    2.60 +	rm -f $(PREFIX)/lib/$(soname)
    2.61 +	rm -f $(PREFIX)/lib/$(devlink)

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/configure	Sun Oct 09 07:48:14 2011 +0300
     3.3 @@ -0,0 +1,36 @@
     3.4 +#!/bin/sh
     3.5 +
     3.6 +prefix=/usr/local
     3.7 +opt=false
     3.8 +dbg=true
     3.9 +
    3.10 +while [ $# != 0 ]; do
    3.11 +	case $1 in
    3.12 +	--prefix=*)
    3.13 +		prefix=`echo $1 | sed 's/^--prefix=//'`
    3.14 +		;;
    3.15 +	--enable-opt)
    3.16 +		opt=true
    3.17 +		;;
    3.18 +	--disable-opt)
    3.19 +		opt=false
    3.20 +		;;
    3.21 +	--enable-dbg)
    3.22 +		dbg=true
    3.23 +		;;
    3.24 +	--disable-dbg)
    3.25 +		dbg=false
    3.26 +		;;
    3.27 +	esac
    3.28 +	shift
    3.29 +done
    3.30 +
    3.31 +echo 'Configuring librbtree...'
    3.32 +
    3.33 +echo "# do not modify this file manually, it's generated by configure" >Makefile
    3.34 +echo "PREFIX = $prefix" >>Makefile
    3.35 +$opt && echo '-O3' | xargs echo 'opt =' >>Makefile
    3.36 +$dbg && echo '-g' | xargs echo 'dbg =' >>Makefile
    3.37 +cat Makefile.in >>Makefile
    3.38 +
    3.39 +echo 'Done. Run make (or gmake) to compile.'

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/src/rbtree.c	Sun Oct 09 07:48:14 2011 +0300
     4.3 @@ -0,0 +1,456 @@
     4.4 +#include <stdio.h>
     4.5 +#include <stdlib.h>
     4.6 +#include <string.h>
     4.7 +#include "rbtree.h"
     4.8 +
     4.9 +#define INT2PTR(x)	((void*)(x))
    4.10 +#define PTR2INT(x)	((int)(x))
    4.11 +
    4.12 +struct rbtree {
    4.13 +	struct rbnode *root;
    4.14 +
    4.15 +	rb_alloc_func_t alloc;
    4.16 +	rb_free_func_t free;
    4.17 +
    4.18 +	rb_cmp_func_t cmp;
    4.19 +	rb_del_func_t del;
    4.20 +	void *del_cls;
    4.21 +
    4.22 +	struct rbnode *rstack, *iter;
    4.23 +};
    4.24 +
    4.25 +static int cmpaddr(void *ap, void *bp);
    4.26 +static int cmpint(void *ap, void *bp);
    4.27 +
    4.28 +static int count_nodes(struct rbnode *node);
    4.29 +static void del_tree(struct rbnode *node, void (*delfunc)(struct rbnode*, void*), void *cls);
    4.30 +static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data);
    4.31 +static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key);
    4.32 +static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key);
    4.33 +static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls);
    4.34 +
    4.35 +struct rbtree *rb_create(rb_cmp_func_t cmp_func)
    4.36 +{
    4.37 +	struct rbtree *rb;
    4.38 +
    4.39 +	if(!(rb = malloc(sizeof *rb))) {
    4.40 +		return 0;
    4.41 +	}
    4.42 +	if(rb_init(rb, cmp_func) == -1) {
    4.43 +		free(rb);
    4.44 +		return 0;
    4.45 +	}
    4.46 +	return rb;
    4.47 +}
    4.48 +
    4.49 +void rb_free(struct rbtree *rb)
    4.50 +{
    4.51 +	rb_destroy(rb);
    4.52 +	free(rb);
    4.53 +}
    4.54 +
    4.55 +
    4.56 +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func)
    4.57 +{
    4.58 +	memset(rb, 0, sizeof *rb);
    4.59 +
    4.60 +	if(cmp_func == RB_KEY_INT) {
    4.61 +		rb->cmp = cmpint;
    4.62 +	} else if(cmp_func == RB_KEY_STRING) {
    4.63 +		rb->cmp = (rb_cmp_func_t)strcmp;
    4.64 +	} else {
    4.65 +		rb->cmp = cmpaddr;
    4.66 +	}
    4.67 +
    4.68 +	rb->alloc = malloc;
    4.69 +	rb->free = free;
    4.70 +	return 0;
    4.71 +}
    4.72 +
    4.73 +void rb_destroy(struct rbtree *rb)
    4.74 +{
    4.75 +	del_tree(rb->root, rb->del, rb->del_cls);
    4.76 +}
    4.77 +
    4.78 +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free)
    4.79 +{
    4.80 +	rb->alloc = alloc;
    4.81 +	rb->free = free;
    4.82 +}
    4.83 +
    4.84 +
    4.85 +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func)
    4.86 +{
    4.87 +	rb->cmp = func;
    4.88 +}
    4.89 +
    4.90 +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls)
    4.91 +{
    4.92 +	rb->del = func;
    4.93 +	rb->del_cls = cls;
    4.94 +}
    4.95 +
    4.96 +int rb_size(struct rbtree *rb)
    4.97 +{
    4.98 +	return count_nodes(rb->root);
    4.99 +}
   4.100 +
   4.101 +int rb_insert(struct rbtree *rb, void *key, void *data)
   4.102 +{
   4.103 +	rb->root = insert(rb, rb->root, key, data);
   4.104 +	rb->root->red = 0;
   4.105 +	return 0;
   4.106 +}
   4.107 +
   4.108 +int rb_inserti(struct rbtree *rb, int key, void *data)
   4.109 +{
   4.110 +	rb->root = insert(rb, rb->root, INT2PTR(key), data);
   4.111 +	rb->root->red = 0;
   4.112 +	return 0;
   4.113 +}
   4.114 +
   4.115 +
   4.116 +int rb_delete(struct rbtree *rb, void *key)
   4.117 +{
   4.118 +	rb->root = delete(rb, rb->root, key);
   4.119 +	rb->root->red = 0;
   4.120 +	return 0;
   4.121 +}
   4.122 +
   4.123 +int rb_deletei(struct rbtree *rb, int key)
   4.124 +{
   4.125 +	rb->root = delete(rb, rb->root, INT2PTR(key));
   4.126 +	rb->root->red = 0;
   4.127 +	return 0;
   4.128 +}
   4.129 +
   4.130 +
   4.131 +void *rb_find(struct rbtree *rb, void *key)
   4.132 +{
   4.133 +	return find(rb, rb->root, key);
   4.134 +}
   4.135 +
   4.136 +void *rb_findi(struct rbtree *rb, int key)
   4.137 +{
   4.138 +	return find(rb, rb->root, INT2PTR(key));
   4.139 +}
   4.140 +
   4.141 +
   4.142 +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls)
   4.143 +{
   4.144 +	traverse(rb->root, func, cls);
   4.145 +}
   4.146 +
   4.147 +
   4.148 +struct rbnode *rb_root(struct rbtree *rb)
   4.149 +{
   4.150 +	return rb->root;
   4.151 +}
   4.152 +
   4.153 +void rb_begin(struct rbtree *rb)
   4.154 +{
   4.155 +	rb->rstack = 0;
   4.156 +	rb->iter = rb->root;
   4.157 +}
   4.158 +
   4.159 +#define push(sp, x)		((x)->next = (sp), (sp) = (x))
   4.160 +#define pop(sp)			((sp) = (sp)->next)
   4.161 +#define top(sp)			(sp)
   4.162 +
   4.163 +struct rbnode *rb_next(struct rbtree *rb)
   4.164 +{
   4.165 +	struct rbnode *res = 0;
   4.166 +
   4.167 +	while(rb->rstack || rb->iter) {
   4.168 +		if(rb->iter) {
   4.169 +			push(rb->rstack, rb->iter);
   4.170 +			rb->iter = rb->iter->left;
   4.171 +		} else {
   4.172 +			rb->iter = top(rb->rstack);
   4.173 +			pop(rb->rstack);
   4.174 +			res = rb->iter;
   4.175 +			rb->iter = rb->iter->right;
   4.176 +			break;
   4.177 +		}
   4.178 +	}
   4.179 +	return res;
   4.180 +}
   4.181 +
   4.182 +void *rb_node_key(struct rbnode *node)
   4.183 +{
   4.184 +	return node ? node->key : 0;
   4.185 +}
   4.186 +
   4.187 +int rb_node_keyi(struct rbnode *node)
   4.188 +{
   4.189 +	return node ? PTR2INT(node->key) : 0;
   4.190 +}
   4.191 +
   4.192 +void *rb_node_data(struct rbnode *node)
   4.193 +{
   4.194 +	return node ? node->data : 0;
   4.195 +}
   4.196 +
   4.197 +static int cmpaddr(void *ap, void *bp)
   4.198 +{
   4.199 +	return ap < bp ? -1 : (ap > bp ? 1 : 0);
   4.200 +}
   4.201 +
   4.202 +static int cmpint(void *ap, void *bp)
   4.203 +{
   4.204 +	return PTR2INT(ap) - PTR2INT(bp);
   4.205 +}
   4.206 +
   4.207 +
   4.208 +/* ---- left-leaning 2-3 red-black implementation ---- */
   4.209 +
   4.210 +/* helper prototypes */
   4.211 +static int is_red(struct rbnode *tree);
   4.212 +static void color_flip(struct rbnode *tree);
   4.213 +static struct rbnode *rot_left(struct rbnode *a);
   4.214 +static struct rbnode *rot_right(struct rbnode *a);
   4.215 +static struct rbnode *find_min(struct rbnode *tree);
   4.216 +static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree);
   4.217 +/*static struct rbnode *move_red_right(struct rbnode *tree);*/
   4.218 +static struct rbnode *move_red_left(struct rbnode *tree);
   4.219 +static struct rbnode *fix_up(struct rbnode *tree);
   4.220 +
   4.221 +static int count_nodes(struct rbnode *node)
   4.222 +{
   4.223 +	if(!node)
   4.224 +		return 0;
   4.225 +
   4.226 +	return 1 + count_nodes(node->left) + count_nodes(node->right);
   4.227 +}
   4.228 +
   4.229 +static void del_tree(struct rbnode *node, rb_del_func_t delfunc, void *cls)
   4.230 +{
   4.231 +	if(!node)
   4.232 +		return;
   4.233 +
   4.234 +	del_tree(node->left, delfunc, cls);
   4.235 +	del_tree(node->right, delfunc, cls);
   4.236 +
   4.237 +	delfunc(node, cls);
   4.238 +	free(node);
   4.239 +}
   4.240 +
   4.241 +static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data)
   4.242 +{
   4.243 +	int cmp;
   4.244 +
   4.245 +	if(!tree) {
   4.246 +		struct rbnode *node = rb->alloc(sizeof *node);
   4.247 +		node->red = 1;
   4.248 +		node->key = key;
   4.249 +		node->data = data;
   4.250 +		node->left = node->right = 0;
   4.251 +		return node;
   4.252 +	}
   4.253 +
   4.254 +	cmp = rb->cmp(key, tree->key);
   4.255 +
   4.256 +	if(cmp < 0) {
   4.257 +		tree->left = insert(rb, tree->left, key, data);
   4.258 +	} else if(cmp > 0) {
   4.259 +		tree->right = insert(rb, tree->right, key, data);
   4.260 +	} else {
   4.261 +		tree->data = data;
   4.262 +	}
   4.263 +
   4.264 +	/* fix right-leaning reds */
   4.265 +	if(is_red(tree->right)) {
   4.266 +		tree = rot_left(tree);
   4.267 +	}
   4.268 +	/* fix two reds in a row */
   4.269 +	if(is_red(tree->left) && is_red(tree->left->left)) {
   4.270 +		tree = rot_right(tree);
   4.271 +	}
   4.272 +
   4.273 +	/* if 4-node, split it by color inversion */
   4.274 +	if(is_red(tree->left) && is_red(tree->right)) {
   4.275 +		color_flip(tree);
   4.276 +	}
   4.277 +
   4.278 +	return tree;
   4.279 +}
   4.280 +
   4.281 +static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key)
   4.282 +{
   4.283 +	int cmp;
   4.284 +
   4.285 +	if(!tree) {
   4.286 +		return 0;
   4.287 +	}
   4.288 +
   4.289 +	cmp = rb->cmp(key, tree->key);
   4.290 +
   4.291 +	if(cmp < 0) {
   4.292 +		if(!is_red(tree->left) && !is_red(tree->left->left)) {
   4.293 +			tree = move_red_left(tree);
   4.294 +		}
   4.295 +		tree->left = delete(rb, tree->left, key);
   4.296 +	} else {
   4.297 +		/* need reds on the right */
   4.298 +		if(is_red(tree->left)) {
   4.299 +			tree = rot_right(tree);
   4.300 +		}
   4.301 +
   4.302 +		/* found it at the bottom (XXX what certifies left is null?) */
   4.303 +		if(cmp == 0 && !tree->right) {
   4.304 +			if(rb->del) {
   4.305 +				rb->del(tree, rb->del_cls);
   4.306 +			}
   4.307 +			rb->free(tree);
   4.308 +			return 0;
   4.309 +		}
   4.310 +
   4.311 +		if(!is_red(tree->right) && !is_red(tree->right->left)) {
   4.312 +			tree = move_red_left(tree);
   4.313 +		}
   4.314 +
   4.315 +		if(key == tree->key) {
   4.316 +			struct rbnode *rmin = find_min(tree->right);
   4.317 +			tree->key = rmin->key;
   4.318 +			tree->data = rmin->data;
   4.319 +			tree->right = del_min(rb, tree->right);
   4.320 +		} else {
   4.321 +			tree->right = delete(rb, tree->right, key);
   4.322 +		}
   4.323 +	}
   4.324 +
   4.325 +	return fix_up(tree);
   4.326 +}
   4.327 +
   4.328 +static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key)
   4.329 +{
   4.330 +	int cmp;
   4.331 +
   4.332 +	if(!node)
   4.333 +		return 0;
   4.334 +
   4.335 +	if((cmp = rb->cmp(key, node->key)) == 0) {
   4.336 +		return node;
   4.337 +	}
   4.338 +	return find(rb, cmp < 0 ? node->left : node->right, key);
   4.339 +}
   4.340 +
   4.341 +static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls)
   4.342 +{
   4.343 +	if(!node)
   4.344 +		return;
   4.345 +
   4.346 +	traverse(node->left, func, cls);
   4.347 +	func(node, cls);
   4.348 +	traverse(node->right, func, cls);
   4.349 +}
   4.350 +
   4.351 +/* helpers */
   4.352 +
   4.353 +static int is_red(struct rbnode *tree)
   4.354 +{
   4.355 +	return tree && tree->red;
   4.356 +}
   4.357 +
   4.358 +static void color_flip(struct rbnode *tree)
   4.359 +{
   4.360 +	tree->red = !tree->red;
   4.361 +	tree->left->red = !tree->left->red;
   4.362 +	tree->right->red = !tree->right->red;
   4.363 +}
   4.364 +
   4.365 +static struct rbnode *rot_left(struct rbnode *a)
   4.366 +{
   4.367 +	struct rbnode *b = a->right;
   4.368 +	a->right = b->left;
   4.369 +	b->left = a;
   4.370 +	b->red = a->red;
   4.371 +	a->red = 1;
   4.372 +	return b;
   4.373 +}
   4.374 +
   4.375 +static struct rbnode *rot_right(struct rbnode *a)
   4.376 +{
   4.377 +	struct rbnode *b = a->left;
   4.378 +	a->left = b->right;
   4.379 +	b->right = a;
   4.380 +	b->red = a->red;
   4.381 +	a->red = 1;
   4.382 +	return b;
   4.383 +}
   4.384 +
   4.385 +static struct rbnode *find_min(struct rbnode *tree)
   4.386 +{
   4.387 +	if(!tree || !tree->left) {
   4.388 +		return tree;
   4.389 +	}
   4.390 +	return find_min(tree->left);
   4.391 +}
   4.392 +
   4.393 +static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree)
   4.394 +{
   4.395 +	if(!tree->left) {
   4.396 +		if(rb->del) {
   4.397 +			rb->del(tree->left, rb->del_cls);
   4.398 +		}
   4.399 +		rb->free(tree->left);
   4.400 +		return 0;
   4.401 +	}
   4.402 +
   4.403 +	/* make sure we've got red (3/4-nodes) at the left side so we can delete at the bottom */
   4.404 +	if(!is_red(tree->left) && !is_red(tree->left->left)) {
   4.405 +		tree = move_red_left(tree);
   4.406 +	}
   4.407 +	tree->left = del_min(rb, tree->left);
   4.408 +
   4.409 +	/* fix right-reds, red-reds, and split 4-nodes on the way up */
   4.410 +	return fix_up(tree);
   4.411 +}
   4.412 +
   4.413 +#if 0
   4.414 +/* push a red link on this node to the right */
   4.415 +static struct rbnode *move_red_right(struct rbnode *tree)
   4.416 +{
   4.417 +	/* flipping it makes both children go red, so we have a red to the right */
   4.418 +	color_flip(tree);
   4.419 +
   4.420 +	/* if after the flip we've got a red-red situation to the left, fix it */
   4.421 +	if(is_red(tree->left->left)) {
   4.422 +		tree = rot_right(tree);
   4.423 +		color_flip(tree);
   4.424 +	}
   4.425 +	return tree;
   4.426 +}
   4.427 +#endif
   4.428 +
   4.429 +/* push a red link on this node to the left */
   4.430 +static struct rbnode *move_red_left(struct rbnode *tree)
   4.431 +{
   4.432 +	/* flipping it makes both children go red, so we have a red to the left */
   4.433 +	color_flip(tree);
   4.434 +
   4.435 +	/* if after the flip we've got a red-red on the right-left, fix it */
   4.436 +	if(is_red(tree->right->left)) {
   4.437 +		tree->right = rot_right(tree->right);
   4.438 +		tree = rot_left(tree);
   4.439 +		color_flip(tree);
   4.440 +	}
   4.441 +	return tree;
   4.442 +}
   4.443 +
   4.444 +static struct rbnode *fix_up(struct rbnode *tree)
   4.445 +{
   4.446 +	/* fix right-leaning */
   4.447 +	if(is_red(tree->right)) {
   4.448 +		tree = rot_left(tree);
   4.449 +	}
   4.450 +	/* change invalid red-red pairs into a proper 4-node */
   4.451 +	if(is_red(tree->left) && is_red(tree->left->left)) {
   4.452 +		tree = rot_right(tree);
   4.453 +	}
   4.454 +	/* split 4-nodes */
   4.455 +	if(is_red(tree->left) && is_red(tree->right)) {
   4.456 +		color_flip(tree);
   4.457 +	}
   4.458 +	return tree;
   4.459 +}

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/src/rbtree.h	Sun Oct 09 07:48:14 2011 +0300
     5.3 @@ -0,0 +1,68 @@
     5.4 +#ifndef RBTREE_H_
     5.5 +#define RBTREE_H_
     5.6 +
     5.7 +struct rbtree;
     5.8 +
     5.9 +
    5.10 +struct rbnode {
    5.11 +	void *key, *data;
    5.12 +	int red;
    5.13 +	struct rbnode *left, *right;
    5.14 +	struct rbnode *next;	/* for iterator stack */
    5.15 +};
    5.16 +
    5.17 +
    5.18 +typedef void *(*rb_alloc_func_t)(size_t);
    5.19 +typedef void (*rb_free_func_t)(void*);
    5.20 +
    5.21 +typedef int (*rb_cmp_func_t)(void*, void*);
    5.22 +typedef void (*rb_del_func_t)(struct rbnode*, void*);
    5.23 +
    5.24 +#define RB_KEY_ADDR		(rb_cmp_func_t)(0)
    5.25 +#define RB_KEY_INT		(rb_cmp_func_t)(1)
    5.26 +#define RB_KEY_STRING	(rb_cmp_func_t)(3)
    5.27 +
    5.28 +typedef struct rbnode* rbiter_t;
    5.29 +
    5.30 +#ifdef __cplusplus
    5.31 +extern "C" {
    5.32 +#endif
    5.33 +
    5.34 +struct rbtree *rb_create(rb_cmp_func_t cmp_func);
    5.35 +void rb_free(struct rbtree *rb);
    5.36 +
    5.37 +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func);
    5.38 +void rb_destroy(struct rbtree *rb);
    5.39 +
    5.40 +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free);
    5.41 +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func);
    5.42 +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls);
    5.43 +
    5.44 +int rb_size(struct rbtree *rb);
    5.45 +
    5.46 +int rb_insert(struct rbtree *rb, void *key, void *data);
    5.47 +int rb_inserti(struct rbtree *rb, int key, void *data);
    5.48 +
    5.49 +int rb_delete(struct rbtree *rb, void *key);
    5.50 +int rb_deletei(struct rbtree *rb, int key);
    5.51 +
    5.52 +void *rb_find(struct rbtree *rb, void *key);
    5.53 +void *rb_findi(struct rbtree *rb, int key);
    5.54 +
    5.55 +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls);
    5.56 +
    5.57 +struct rbnode *rb_root(struct rbtree *rb);
    5.58 +
    5.59 +void rb_begin(struct rbtree *rb);
    5.60 +struct rbnode *rb_node_next(struct rbtree *rb);
    5.61 +
    5.62 +void *rb_node_key(struct rbnode *node);
    5.63 +int rb_node_keyi(struct rbnode *node);
    5.64 +void *rb_node_data(struct rbnode *node);
    5.65 +
    5.66 +#ifdef __cplusplus
    5.67 +}
    5.68 +#endif
    5.69 +
    5.70 +
    5.71 +#endif	/* RBTREE_H_ */

     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/test/Makefile	Sun Oct 09 07:48:14 2011 +0300
     6.3 @@ -0,0 +1,32 @@
     6.4 +obj = test.o
     6.5 +bin = test
     6.6 +
     6.7 +font = linux-libertine.ttf
     6.8 +
     6.9 +CC = gcc
    6.10 +CFLAGS = -pedantic -Wall -g -I../src -I/usr/local/include
    6.11 +LDFLAGS = -L.. -L/usr/local/lib $(libgl) -lrbtree -ldrawtext
    6.12 +
    6.13 +ifeq ($(shell uname -s), Darwin)
    6.14 +	libgl = -framework OpenGL -framework GLUT
    6.15 +else
    6.16 +	libgl = -lGL -lglut
    6.17 +endif
    6.18 +
    6.19 +.PHONY: all
    6.20 +all: $(bin) $(font)
    6.21 +
    6.22 +$(bin): $(obj)
    6.23 +	$(CC) -o $@ $(obj) $(LDFLAGS)
    6.24 +
    6.25 +$(font):
    6.26 +	wget http://downloads.sourceforge.net/project/linuxlibertine/linuxlibertine/5.1.3-2/LinLibertineTTF_5.1.3_2011_06_21.tgz
    6.27 +	mkdir -p linlibertine
    6.28 +	cd linlibertine; tar xzvf ../LinLibertineTTF_5.1.3_2011_06_21.tgz
    6.29 +	rm -f LinLibertineTTF_5.1.3_2011_06_21.tgz
    6.30 +	cp linlibertine/LinLibertine_R.ttf $@
    6.31 +
    6.32 +
    6.33 +.PHONY: clean
    6.34 +clean:
    6.35 +	rm -f $(obj) $(bin)

     7.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     7.2 +++ b/test/test.c	Sun Oct 09 07:48:14 2011 +0300
     7.3 @@ -0,0 +1,395 @@
     7.4 +#include <stdio.h>
     7.5 +#include <stdlib.h>
     7.6 +#include <string.h>
     7.7 +#include <ctype.h>
     7.8 +#include <math.h>
     7.9 +#include <assert.h>
    7.10 +#include <alloca.h>
    7.11 +
    7.12 +#ifndef __APPLE__
    7.13 +#include <GL/glut.h>
    7.14 +#else
    7.15 +#include <GLUT/glut.h>
    7.16 +#endif
    7.17 +#include <rbtree.h>
    7.18 +#include <drawtext.h>
    7.19 +
    7.20 +#define FONTSZ	18
    7.21 +
    7.22 +void init_gl(int argc, char **argv);
    7.23 +float rbvis_width(struct rbnode *tree);
    7.24 +void rbvis_draw(struct rbnode *tree, float x, float y);
    7.25 +
    7.26 +void draw_roundbox(float xsz, float ysz, float rad, int segm, const float *col, float border, const float *bcol);
    7.27 +void draw_fillet(float rad, int segm);
    7.28 +
    7.29 +struct rbtree *tree;
    7.30 +int num_nodes;
    7.31 +struct dtx_font *font;
    7.32 +char input_buffer[64];
    7.33 +int win_xsz, win_ysz;
    7.34 +
    7.35 +int main(int argc, char **argv)
    7.36 +{
    7.37 +	int i;
    7.38 +
    7.39 +	if(argv[1]) {
    7.40 +		if(!isdigit(argv[1][0])) {
    7.41 +			fprintf(stderr, "pass a fucking number, not: %s\n", argv[1]);
    7.42 +			return 1;
    7.43 +		}
    7.44 +		num_nodes = atoi(argv[1]);
    7.45 +	}
    7.46 +
    7.47 +	if(!(font = dtx_open_font("linux-libertine.ttf", FONTSZ))) {
    7.48 +		fprintf(stderr, "failed to open font\n");
    7.49 +		return 1;
    7.50 +	}
    7.51 +
    7.52 +	if(!(tree = rb_create(RB_KEY_INT))) {
    7.53 +		return 1;
    7.54 +	}
    7.55 +
    7.56 +	for(i=0; i<num_nodes; i++) {
    7.57 +		rb_inserti(tree, i, 0);
    7.58 +	}
    7.59 +
    7.60 +	init_gl(argc, argv);
    7.61 +	return 0;
    7.62 +}
    7.63 +
    7.64 +#define NWIDTH	28.0
    7.65 +#define NHEIGHT 24.0
    7.66 +#define PADDING	0
    7.67 +#define DY	(NHEIGHT + NHEIGHT / 2.0)
    7.68 +
    7.69 +#define VIS(node)	((struct visinfo*)(node)->data)
    7.70 +
    7.71 +void disp(void);
    7.72 +void reshape(int x, int y);
    7.73 +void keyb(unsigned char key, int x, int y);
    7.74 +void draw_rect(float x, float y, float width, float height, const char *text, int red);
    7.75 +void draw_link(float x0, float y0, float x1, float y1, int red);
    7.76 +
    7.77 +void init_gl(int argc, char **argv)
    7.78 +{
    7.79 +	glutInitWindowSize(1280, 720);
    7.80 +	glutInit(&argc, argv);
    7.81 +	glutInitDisplayMode(GLUT_RGB | GLUT_DOUBLE | GLUT_MULTISAMPLE);
    7.82 +
    7.83 +	glutCreateWindow("foo");
    7.84 +
    7.85 +	dtx_use_font(font, FONTSZ);
    7.86 +
    7.87 +	glutDisplayFunc(disp);
    7.88 +	glutReshapeFunc(reshape);
    7.89 +	glutKeyboardFunc(keyb);
    7.90 +
    7.91 +	glEnable(GL_DEPTH_TEST);
    7.92 +	glEnable(GL_MULTISAMPLE);
    7.93 +
    7.94 +	glutMainLoop();
    7.95 +}
    7.96 +
    7.97 +void disp(void)
    7.98 +{
    7.99 +	struct rbnode *root = rb_root(tree);
   7.100 +
   7.101 +	glClearColor(0.57, 0.64, 0.59, 1.0);
   7.102 +	glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
   7.103 +
   7.104 +	glMatrixMode(GL_MODELVIEW);
   7.105 +	glLoadIdentity();
   7.106 +
   7.107 +	if(input_buffer[0]) {
   7.108 +		char *prompt = "select node to delete: ";
   7.109 +		char *buf = alloca(strlen(prompt) + strlen(input_buffer));
   7.110 +
   7.111 +		glPushMatrix();
   7.112 +		glTranslatef(10, 10, -0.9);
   7.113 +		glColor3f(0, 0, 0);
   7.114 +		sprintf(buf, "%s%s", prompt, input_buffer);
   7.115 +		dtx_string(buf);
   7.116 +		glPopMatrix();
   7.117 +	}
   7.118 +
   7.119 +	if(root) {
   7.120 +		rbvis_draw(root, rbvis_width(root->left) + NWIDTH, 550);
   7.121 +	}
   7.122 +
   7.123 +	glutSwapBuffers();
   7.124 +	assert(glGetError() == GL_NO_ERROR);
   7.125 +}
   7.126 +
   7.127 +
   7.128 +float rbvis_width(struct rbnode *tree)
   7.129 +{
   7.130 +	if(!tree)
   7.131 +		return NWIDTH;
   7.132 +
   7.133 +	return NWIDTH + rbvis_width(tree->left) + rbvis_width(tree->right) + PADDING * 3.0;
   7.134 +}
   7.135 +
   7.136 +void rbvis_draw(struct rbnode *tree, float x, float y)
   7.137 +{
   7.138 +	float leftx, rightx, nexty;
   7.139 +	static const float hxsz = NWIDTH / 2.0;
   7.140 +	static const float hysz = NHEIGHT / 2.0;
   7.141 +	char text[16];
   7.142 +
   7.143 +	if(!tree)
   7.144 +		return;
   7.145 +
   7.146 +	leftx = x - (tree->left ? rbvis_width(tree->left->right) + NWIDTH : rbvis_width(tree->left) / 2.0);
   7.147 +	rightx = x + (tree->right ? rbvis_width(tree->right->left) + NWIDTH : rbvis_width(tree->right) / 2.0);
   7.148 +
   7.149 +	nexty = y - DY;
   7.150 +
   7.151 +	sprintf(text, "%d", rb_node_keyi(tree));
   7.152 +	draw_rect(x - hxsz, y - hysz, NWIDTH, NHEIGHT, text, tree->red);
   7.153 +
   7.154 +	rbvis_draw(tree->left, leftx, nexty);
   7.155 +	rbvis_draw(tree->right, rightx, nexty);
   7.156 +
   7.157 +	if(tree->left)
   7.158 +		draw_link(x, y, leftx, nexty, tree->left->red);
   7.159 +	if(tree->right)
   7.160 +		draw_link(x, y, rightx, nexty, tree->right->red);
   7.161 +}
   7.162 +
   7.163 +void draw_rect(float x, float y, float width, float height, const char *text, int red)
   7.164 +{
   7.165 +	float node_col[] = {0.63, 0.71, 0.82, 1.0};
   7.166 +	float bord_col[] = {0, 0, 0, 1};
   7.167 +
   7.168 +	if(red) {
   7.169 +		bord_col[0] = 1.0;
   7.170 +	}
   7.171 +
   7.172 +	glMatrixMode(GL_MODELVIEW);
   7.173 +	glPushMatrix();
   7.174 +	glTranslatef(x + width / 2.0, y + height / 2.0, 0.0);
   7.175 +
   7.176 +	draw_roundbox(width, height, 8, 6, node_col, 1.2, bord_col);
   7.177 +
   7.178 +	glColor3f(0.15, 0.15, 0.15);
   7.179 +	glTranslatef(-dtx_string_width(text) / 2.0, -dtx_string_height(text) / 2.0, 0.1);
   7.180 +	dtx_string(text);
   7.181 +	glMatrixMode(GL_MODELVIEW);
   7.182 +	glPopMatrix();
   7.183 +}
   7.184 +
   7.185 +void draw_link(float x0, float y0, float x1, float y1, int red)
   7.186 +{
   7.187 +	glPushAttrib(GL_LINE_BIT);
   7.188 +	if(red) {
   7.189 +		glLineWidth(3);
   7.190 +	} else {
   7.191 +		glLineWidth(2);
   7.192 +	}
   7.193 +
   7.194 +	glBegin(GL_LINES);
   7.195 +	if(red) {
   7.196 +		glColor3f(0.8, 0.36, 0.3);
   7.197 +	} else {
   7.198 +		glColor3f(0, 0, 0);
   7.199 +	}
   7.200 +	glVertex3f(x0, y0, -0.8);
   7.201 +	glVertex3f(x1, y1, -0.8);
   7.202 +	glEnd();
   7.203 +
   7.204 +	glPopAttrib();
   7.205 +}
   7.206 +
   7.207 +void draw_roundbox(float xsz, float ysz, float rad, int segm, const float *col, float border, const float *bcol)
   7.208 +{
   7.209 +	float hin_xsz, hin_ysz;
   7.210 +
   7.211 +	if(border > 0.0f) {
   7.212 +		glPushMatrix();
   7.213 +		glTranslatef(0, 0, -0.001);
   7.214 +		draw_roundbox(xsz + 2 * border, ysz + 2 * border, rad + border, segm, bcol, 0.0, bcol);
   7.215 +		glPopMatrix();
   7.216 +	}
   7.217 +
   7.218 +	/* half inner size */
   7.219 +	hin_xsz = (xsz - 2.0 * rad) / 2.0;
   7.220 +	hin_ysz = (ysz - 2.0 * rad) / 2.0;
   7.221 +
   7.222 +	glColor4fv(col);
   7.223 +
   7.224 +	glBegin(GL_QUADS);
   7.225 +	/* center */
   7.226 +	glVertex2f(-hin_xsz, -hin_ysz);
   7.227 +	glVertex2f(hin_xsz, -hin_ysz);
   7.228 +	glVertex2f(hin_xsz, hin_ysz);
   7.229 +	glVertex2f(-hin_xsz, hin_ysz);
   7.230 +	/* right */
   7.231 +	glVertex2f(hin_xsz, -hin_ysz);
   7.232 +	glVertex2f(hin_xsz + rad, -hin_ysz);
   7.233 +	glVertex2f(hin_xsz + rad, hin_ysz);
   7.234 +	glVertex2f(hin_xsz, hin_ysz);
   7.235 +	/* top */
   7.236 +	glVertex2f(-hin_xsz, hin_ysz);
   7.237 +	glVertex2f(hin_xsz, hin_ysz);
   7.238 +	glVertex2f(hin_xsz, hin_ysz + rad);
   7.239 +	glVertex2f(-hin_xsz, hin_ysz + rad);
   7.240 +	/* left */
   7.241 +	glVertex2f(-hin_xsz - rad, -hin_ysz);
   7.242 +	glVertex2f(-hin_xsz, -hin_ysz);
   7.243 +	glVertex2f(-hin_xsz, hin_ysz);
   7.244 +	glVertex2f(-hin_xsz - rad, hin_ysz);
   7.245 +	/* bottom */
   7.246 +	glVertex2f(-hin_xsz, -hin_ysz - rad);
   7.247 +	glVertex2f(hin_xsz, -hin_ysz - rad);
   7.248 +	glVertex2f(hin_xsz, -hin_ysz);
   7.249 +	glVertex2f(-hin_xsz, -hin_ysz);
   7.250 +	glEnd();
   7.251 +
   7.252 +	glMatrixMode(GL_MODELVIEW);
   7.253 +
   7.254 +	glPushMatrix();
   7.255 +	glTranslatef(hin_xsz, hin_ysz, 0);
   7.256 +	draw_fillet(rad, segm);
   7.257 +	glPopMatrix();
   7.258 +
   7.259 +	glPushMatrix();
   7.260 +	glTranslatef(-hin_xsz, hin_ysz, 0);
   7.261 +	glRotatef(90, 0, 0, 1);
   7.262 +	draw_fillet(rad, segm);
   7.263 +	glPopMatrix();
   7.264 +
   7.265 +	glPushMatrix();
   7.266 +	glTranslatef(-hin_xsz, -hin_ysz, 0);
   7.267 +	glRotatef(180, 0, 0, 1);
   7.268 +	draw_fillet(rad, segm);
   7.269 +	glPopMatrix();
   7.270 +
   7.271 +	glPushMatrix();
   7.272 +	glTranslatef(hin_xsz, -hin_ysz, 0);
   7.273 +	glRotatef(270, 0, 0, 1);
   7.274 +	draw_fillet(rad, segm);
   7.275 +	glPopMatrix();
   7.276 +}
   7.277 +
   7.278 +void draw_fillet(float rad, int segm)
   7.279 +{
   7.280 +	int i;
   7.281 +
   7.282 +	glBegin(GL_TRIANGLE_FAN);
   7.283 +	glVertex2f(0, 0);
   7.284 +	for(i=0; i<segm; i++) {
   7.285 +		float theta = 0.5 * M_PI * (float)i / (float)(segm - 1);
   7.286 +		float x = cos(theta) * rad;
   7.287 +		float y = sin(theta) * rad;
   7.288 +		glVertex2f(x, y);
   7.289 +	}
   7.290 +	glEnd();
   7.291 +}
   7.292 +
   7.293 +
   7.294 +void reshape(int x, int y)
   7.295 +{
   7.296 +	win_xsz = x;
   7.297 +	win_ysz = y;
   7.298 +
   7.299 +	glViewport(0, 0, x, y);
   7.300 +
   7.301 +	glMatrixMode(GL_PROJECTION);
   7.302 +	glLoadIdentity();
   7.303 +	glOrtho(0, x, 0, y, -1, 1);
   7.304 +}
   7.305 +
   7.306 +void keyb(unsigned char key, int x, int y)
   7.307 +{
   7.308 +	static int wposx = -1, wposy;
   7.309 +	static char *inp_next;
   7.310 +
   7.311 +	switch(key) {
   7.312 +	case 27:
   7.313 +		exit(0);
   7.314 +
   7.315 +	case 'f':
   7.316 +	case 'F':
   7.317 +		if(wposx >= 0) {
   7.318 +			glutPositionWindow(wposx, wposy);
   7.319 +			wposx = -1;
   7.320 +		} else {
   7.321 +			wposx = glutGet(GLUT_WINDOW_X);
   7.322 +			wposy = glutGet(GLUT_WINDOW_Y);
   7.323 +			glutFullScreen();
   7.324 +		}
   7.325 +		break;
   7.326 +
   7.327 +	case 'a':
   7.328 +		rb_inserti(tree, num_nodes++, 0);
   7.329 +		glutPostRedisplay();
   7.330 +		break;
   7.331 +
   7.332 +	case 'r':
   7.333 +		{
   7.334 +			int x;
   7.335 +			do {
   7.336 +				x = rand() % 1024;
   7.337 +			} while(rb_findi(tree, x));
   7.338 +
   7.339 +			rb_inserti(tree, x, 0);
   7.340 +		}
   7.341 +		glutPostRedisplay();
   7.342 +		break;
   7.343 +
   7.344 +	case 'd':
   7.345 +		inp_next = input_buffer;
   7.346 +		*inp_next++ = ' ';
   7.347 +		*inp_next = 0;
   7.348 +		glutPostRedisplay();
   7.349 +		break;
   7.350 +
   7.351 +	case '0':
   7.352 +	case '1':
   7.353 +	case '2':
   7.354 +	case '3':
   7.355 +	case '4':
   7.356 +	case '5':
   7.357 +	case '6':
   7.358 +	case '7':
   7.359 +	case '8':
   7.360 +	case '9':
   7.361 +		if(inp_next) {
   7.362 +			*inp_next++ = key;
   7.363 +			*inp_next = 0;
   7.364 +			glutPostRedisplay();
   7.365 +		}
   7.366 +		break;
   7.367 +
   7.368 +	case '\b':
   7.369 +		if(inp_next > input_buffer) {
   7.370 +			*--inp_next = 0;
   7.371 +			glutPostRedisplay();
   7.372 +		}
   7.373 +		break;
   7.374 +
   7.375 +	case '\n':
   7.376 +	case '\r':
   7.377 +		if(inp_next) {
   7.378 +			int x;
   7.379 +			char *endp;
   7.380 +
   7.381 +			*inp_next = 0;
   7.382 +			inp_next = 0;
   7.383 +
   7.384 +			if((x = strtol(input_buffer, &endp, 10)), endp == input_buffer) {
   7.385 +				fprintf(stderr, "invalid input: %s\n", input_buffer);
   7.386 +			} else if(!rb_findi(tree, x)) {
   7.387 +				fprintf(stderr, "%d not found in the tree\n", x);
   7.388 +			} else {
   7.389 +				printf("deleting: %d\n", x);
   7.390 +				rb_deletei(tree, x);
   7.391 +			}
   7.392 +			input_buffer[0] = 0;
   7.393 +			glutPostRedisplay();
   7.394 +		}
   7.395 +		break;
   7.396 +	}
   7.397 +}
   7.398 +