1.1 --- a/include/packio.h	Sun Sep 09 06:05:11 2012 +0300
     1.2 +++ b/include/packio.h	Sun Aug 09 03:15:07 2015 +0300
     1.3 @@ -2,27 +2,16 @@
     1.4  #define PACKIO_H_
     1.5  
     1.6  struct pack_file;
     1.7 -struct pack_dir;
     1.8 -
     1.9 -#define PACK_NAME_MAX	256
    1.10 -
    1.11 -struct pack_dirent {
    1.12 -	char d_name[PACK_NAME_MAX];
    1.13 -};
    1.14  
    1.15  /* not sure I like this capitalization, but it matches the libc counterparts */
    1.16  typedef struct pack_file PACKFILE;
    1.17 -typedef struct pack_dir PACKDIR;
    1.18  
    1.19  
    1.20  int pack_init(void);
    1.21  void pack_cleanup(void);
    1.22 -int pack_mount(const char *fname, const char *path);
    1.23 +int pack_addpk(const char *pkfname);
    1.24  
    1.25  int pack_exists(const char *path);
    1.26 -int pack_isfile(const char *path);
    1.27 -int pack_isdir(const char *path);
    1.28 -
    1.29  
    1.30  /* file i/o */
    1.31  PACKFILE *pack_fopen(const char *path, const char *mode);
    1.32 @@ -41,10 +30,5 @@
    1.33  int pack_fgetc(PACKFILE *fp);
    1.34  char *pack_fgets(char *buf, int size, PACKFILE *fp);
    1.35  
    1.36 -/* directory handling */
    1.37 -PACKDIR *pack_opendir(const char *name);
    1.38 -int pack_closedir(PACKDIR *dir);
    1.39 -struct pack_dirent *pack_readdir(PACKDIR *dir);
    1.40 -
    1.41  
    1.42  #endif	/* PACKIO_H_ */

     2.1 --- a/src/packio_impl.h	Sun Sep 09 06:05:11 2012 +0300
     2.2 +++ b/src/packio_impl.h	Sun Aug 09 03:15:07 2015 +0300
     2.3 @@ -1,23 +1,11 @@
     2.4  #ifndef PACKIO_IMPL_H_
     2.5  #define PACKIO_IMPL_H_
     2.6  
     2.7 -enum { NODE_FILE, NODE_DIR };
     2.8 -enum { FILE_REAL, FILE_VIRT };
     2.9 +#include "rbtree.h"
    2.10  
    2.11 -struct fsnode {
    2.12 -	int type, ftype;
    2.13 -	long size;
    2.14 -
    2.15 -	struct fsnode *clist, *clist_tail;
    2.16 -};
    2.17 -
    2.18 -struct pack_file {
    2.19 -	struct fsnode *node;
    2.20 -	long pos;
    2.21 -};
    2.22 -
    2.23 -struct pack_dir {
    2.24 -	struct fsnode *node;
    2.25 +struct packfile {
    2.26 +	int rev;	/* packfile revision */
    2.27 +	struct rbtree *files;
    2.28  };
    2.29  
    2.30  #endif	/* PACKIO_IMPL_H_ */

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/src/rbtree.c	Sun Aug 09 03:15:07 2015 +0300
     3.3 @@ -0,0 +1,501 @@
     3.4 +/*
     3.5 +rbtree - simple balanced binary search tree (red-black tree) library.
     3.6 +Copyright (C) 2011-2014  John Tsiombikas <nuclear@member.fsf.org>
     3.7 +
     3.8 +rbtree is free software, feel free to use, modify, and redistribute it, under
     3.9 +the terms of the 3-clause BSD license. See COPYING for details.
    3.10 + */
    3.11 +#include <stdio.h>
    3.12 +#include <stdlib.h>
    3.13 +#include <stdint.h>
    3.14 +#include <string.h>
    3.15 +#include "rbtree.h"
    3.16 +
    3.17 +#define INT2PTR(x)	((void*)(intptr_t)(x))
    3.18 +#define PTR2INT(x)	((int)(intptr_t)(x))
    3.19 +
    3.20 +struct rbtree {
    3.21 +	struct rbnode *root;
    3.22 +
    3.23 +	rb_alloc_func_t alloc;
    3.24 +	rb_free_func_t free;
    3.25 +
    3.26 +	rb_cmp_func_t cmp;
    3.27 +	rb_del_func_t del;
    3.28 +	void *del_cls;
    3.29 +
    3.30 +	struct rbnode *rstack, *iter;
    3.31 +};
    3.32 +
    3.33 +static int cmpaddr(const void *ap, const void *bp);
    3.34 +static int cmpint(const void *ap, const void *bp);
    3.35 +
    3.36 +static int count_nodes(struct rbnode *node);
    3.37 +static void del_tree(struct rbnode *node, void (*delfunc)(struct rbnode*, void*), void *cls);
    3.38 +static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data);
    3.39 +static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key);
    3.40 +/*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key);*/
    3.41 +static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls);
    3.42 +
    3.43 +struct rbtree *rb_create(rb_cmp_func_t cmp_func)
    3.44 +{
    3.45 +	struct rbtree *rb;
    3.46 +
    3.47 +	if(!(rb = malloc(sizeof *rb))) {
    3.48 +		return 0;
    3.49 +	}
    3.50 +	if(rb_init(rb, cmp_func) == -1) {
    3.51 +		free(rb);
    3.52 +		return 0;
    3.53 +	}
    3.54 +	return rb;
    3.55 +}
    3.56 +
    3.57 +void rb_free(struct rbtree *rb)
    3.58 +{
    3.59 +	rb_destroy(rb);
    3.60 +	free(rb);
    3.61 +}
    3.62 +
    3.63 +
    3.64 +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func)
    3.65 +{
    3.66 +	memset(rb, 0, sizeof *rb);
    3.67 +
    3.68 +	if(!cmp_func) {
    3.69 +		rb->cmp = cmpaddr;
    3.70 +	} else if(cmp_func == RB_KEY_INT) {
    3.71 +		rb->cmp = cmpint;
    3.72 +	} else if(cmp_func == RB_KEY_STRING) {
    3.73 +		rb->cmp = (rb_cmp_func_t)strcmp;
    3.74 +	} else {
    3.75 +		rb->cmp = cmp_func;
    3.76 +	}
    3.77 +
    3.78 +	rb->alloc = malloc;
    3.79 +	rb->free = free;
    3.80 +	return 0;
    3.81 +}
    3.82 +
    3.83 +void rb_destroy(struct rbtree *rb)
    3.84 +{
    3.85 +	del_tree(rb->root, rb->del, rb->del_cls);
    3.86 +}
    3.87 +
    3.88 +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free)
    3.89 +{
    3.90 +	rb->alloc = alloc;
    3.91 +	rb->free = free;
    3.92 +}
    3.93 +
    3.94 +
    3.95 +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func)
    3.96 +{
    3.97 +	rb->cmp = func;
    3.98 +}
    3.99 +
   3.100 +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls)
   3.101 +{
   3.102 +	rb->del = func;
   3.103 +	rb->del_cls = cls;
   3.104 +}
   3.105 +
   3.106 +
   3.107 +void rb_clear(struct rbtree *rb)
   3.108 +{
   3.109 +	del_tree(rb->root, rb->del, rb->del_cls);
   3.110 +	rb->root = 0;
   3.111 +}
   3.112 +
   3.113 +int rb_copy(struct rbtree *dest, struct rbtree *src)
   3.114 +{
   3.115 +	struct rbnode *node;
   3.116 +
   3.117 +	rb_clear(dest);
   3.118 +	rb_begin(src);
   3.119 +	while((node = rb_next(src))) {
   3.120 +		if(rb_insert(dest, node->key, node->data) == -1) {
   3.121 +			return -1;
   3.122 +		}
   3.123 +	}
   3.124 +	return 0;
   3.125 +}
   3.126 +
   3.127 +int rb_size(struct rbtree *rb)
   3.128 +{
   3.129 +	return count_nodes(rb->root);
   3.130 +}
   3.131 +
   3.132 +int rb_insert(struct rbtree *rb, void *key, void *data)
   3.133 +{
   3.134 +	rb->root = insert(rb, rb->root, key, data);
   3.135 +	rb->root->red = 0;
   3.136 +	return 0;
   3.137 +}
   3.138 +
   3.139 +int rb_inserti(struct rbtree *rb, int key, void *data)
   3.140 +{
   3.141 +	rb->root = insert(rb, rb->root, INT2PTR(key), data);
   3.142 +	rb->root->red = 0;
   3.143 +	return 0;
   3.144 +}
   3.145 +
   3.146 +
   3.147 +int rb_delete(struct rbtree *rb, void *key)
   3.148 +{
   3.149 +	rb->root = delete(rb, rb->root, key);
   3.150 +	rb->root->red = 0;
   3.151 +	return 0;
   3.152 +}
   3.153 +
   3.154 +int rb_deletei(struct rbtree *rb, int key)
   3.155 +{
   3.156 +	rb->root = delete(rb, rb->root, INT2PTR(key));
   3.157 +	rb->root->red = 0;
   3.158 +	return 0;
   3.159 +}
   3.160 +
   3.161 +
   3.162 +struct rbnode *rb_find(struct rbtree *rb, void *key)
   3.163 +{
   3.164 +	struct rbnode *node = rb->root;
   3.165 +
   3.166 +	while(node) {
   3.167 +		int cmp = rb->cmp(key, node->key);
   3.168 +		if(cmp == 0) {
   3.169 +			return node;
   3.170 +		}
   3.171 +		node = cmp < 0 ? node->left : node->right;
   3.172 +	}
   3.173 +	return 0;
   3.174 +}
   3.175 +
   3.176 +struct rbnode *rb_findi(struct rbtree *rb, int key)
   3.177 +{
   3.178 +	return rb_find(rb, INT2PTR(key));
   3.179 +}
   3.180 +
   3.181 +
   3.182 +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls)
   3.183 +{
   3.184 +	traverse(rb->root, func, cls);
   3.185 +}
   3.186 +
   3.187 +
   3.188 +struct rbnode *rb_root(struct rbtree *rb)
   3.189 +{
   3.190 +	return rb->root;
   3.191 +}
   3.192 +
   3.193 +void rb_begin(struct rbtree *rb)
   3.194 +{
   3.195 +	rb->rstack = 0;
   3.196 +	rb->iter = rb->root;
   3.197 +}
   3.198 +
   3.199 +#define push(sp, x)		((x)->next = (sp), (sp) = (x))
   3.200 +#define pop(sp)			((sp) = (sp)->next)
   3.201 +#define top(sp)			(sp)
   3.202 +
   3.203 +struct rbnode *rb_next(struct rbtree *rb)
   3.204 +{
   3.205 +	struct rbnode *res = 0;
   3.206 +
   3.207 +	while(rb->rstack || rb->iter) {
   3.208 +		if(rb->iter) {
   3.209 +			push(rb->rstack, rb->iter);
   3.210 +			rb->iter = rb->iter->left;
   3.211 +		} else {
   3.212 +			rb->iter = top(rb->rstack);
   3.213 +			pop(rb->rstack);
   3.214 +			res = rb->iter;
   3.215 +			rb->iter = rb->iter->right;
   3.216 +			break;
   3.217 +		}
   3.218 +	}
   3.219 +	return res;
   3.220 +}
   3.221 +
   3.222 +void *rb_node_key(struct rbnode *node)
   3.223 +{
   3.224 +	return node ? node->key : 0;
   3.225 +}
   3.226 +
   3.227 +int rb_node_keyi(struct rbnode *node)
   3.228 +{
   3.229 +	return node ? PTR2INT(node->key) : 0;
   3.230 +}
   3.231 +
   3.232 +void *rb_node_data(struct rbnode *node)
   3.233 +{
   3.234 +	return node ? node->data : 0;
   3.235 +}
   3.236 +
   3.237 +static int cmpaddr(const void *ap, const void *bp)
   3.238 +{
   3.239 +	return ap < bp ? -1 : (ap > bp ? 1 : 0);
   3.240 +}
   3.241 +
   3.242 +static int cmpint(const void *ap, const void *bp)
   3.243 +{
   3.244 +	return PTR2INT(ap) - PTR2INT(bp);
   3.245 +}
   3.246 +
   3.247 +
   3.248 +/* ---- left-leaning 2-3 red-black implementation ---- */
   3.249 +
   3.250 +/* helper prototypes */
   3.251 +static int is_red(struct rbnode *tree);
   3.252 +static void color_flip(struct rbnode *tree);
   3.253 +static struct rbnode *rot_left(struct rbnode *a);
   3.254 +static struct rbnode *rot_right(struct rbnode *a);
   3.255 +static struct rbnode *find_min(struct rbnode *tree);
   3.256 +static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree);
   3.257 +/*static struct rbnode *move_red_right(struct rbnode *tree);*/
   3.258 +static struct rbnode *move_red_left(struct rbnode *tree);
   3.259 +static struct rbnode *fix_up(struct rbnode *tree);
   3.260 +
   3.261 +static int count_nodes(struct rbnode *node)
   3.262 +{
   3.263 +	if(!node)
   3.264 +		return 0;
   3.265 +
   3.266 +	return 1 + count_nodes(node->left) + count_nodes(node->right);
   3.267 +}
   3.268 +
   3.269 +static void del_tree(struct rbnode *node, rb_del_func_t delfunc, void *cls)
   3.270 +{
   3.271 +	if(!node)
   3.272 +		return;
   3.273 +
   3.274 +	del_tree(node->left, delfunc, cls);
   3.275 +	del_tree(node->right, delfunc, cls);
   3.276 +
   3.277 +	if(delfunc) {
   3.278 +		delfunc(node, cls);
   3.279 +	}
   3.280 +	free(node);
   3.281 +}
   3.282 +
   3.283 +static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data)
   3.284 +{
   3.285 +	int cmp;
   3.286 +
   3.287 +	if(!tree) {
   3.288 +		struct rbnode *node = rb->alloc(sizeof *node);
   3.289 +		node->red = 1;
   3.290 +		node->key = key;
   3.291 +		node->data = data;
   3.292 +		node->left = node->right = 0;
   3.293 +		return node;
   3.294 +	}
   3.295 +
   3.296 +	cmp = rb->cmp(key, tree->key);
   3.297 +
   3.298 +	if(cmp < 0) {
   3.299 +		tree->left = insert(rb, tree->left, key, data);
   3.300 +	} else if(cmp > 0) {
   3.301 +		tree->right = insert(rb, tree->right, key, data);
   3.302 +	} else {
   3.303 +		tree->data = data;
   3.304 +	}
   3.305 +
   3.306 +	/* fix right-leaning reds */
   3.307 +	if(is_red(tree->right)) {
   3.308 +		tree = rot_left(tree);
   3.309 +	}
   3.310 +	/* fix two reds in a row */
   3.311 +	if(is_red(tree->left) && is_red(tree->left->left)) {
   3.312 +		tree = rot_right(tree);
   3.313 +	}
   3.314 +
   3.315 +	/* if 4-node, split it by color inversion */
   3.316 +	if(is_red(tree->left) && is_red(tree->right)) {
   3.317 +		color_flip(tree);
   3.318 +	}
   3.319 +
   3.320 +	return tree;
   3.321 +}
   3.322 +
   3.323 +static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key)
   3.324 +{
   3.325 +	int cmp;
   3.326 +
   3.327 +	if(!tree) {
   3.328 +		return 0;
   3.329 +	}
   3.330 +
   3.331 +	cmp = rb->cmp(key, tree->key);
   3.332 +
   3.333 +	if(cmp < 0) {
   3.334 +		if(!is_red(tree->left) && !is_red(tree->left->left)) {
   3.335 +			tree = move_red_left(tree);
   3.336 +		}
   3.337 +		tree->left = delete(rb, tree->left, key);
   3.338 +	} else {
   3.339 +		/* need reds on the right */
   3.340 +		if(is_red(tree->left)) {
   3.341 +			tree = rot_right(tree);
   3.342 +		}
   3.343 +
   3.344 +		/* found it at the bottom (XXX what certifies left is null?) */
   3.345 +		if(cmp == 0 && !tree->right) {
   3.346 +			if(rb->del) {
   3.347 +				rb->del(tree, rb->del_cls);
   3.348 +			}
   3.349 +			rb->free(tree);
   3.350 +			return 0;
   3.351 +		}
   3.352 +
   3.353 +		if(!is_red(tree->right) && !is_red(tree->right->left)) {
   3.354 +			tree = move_red_left(tree);
   3.355 +		}
   3.356 +
   3.357 +		if(key == tree->key) {
   3.358 +			struct rbnode *rmin = find_min(tree->right);
   3.359 +			tree->key = rmin->key;
   3.360 +			tree->data = rmin->data;
   3.361 +			tree->right = del_min(rb, tree->right);
   3.362 +		} else {
   3.363 +			tree->right = delete(rb, tree->right, key);
   3.364 +		}
   3.365 +	}
   3.366 +
   3.367 +	return fix_up(tree);
   3.368 +}
   3.369 +
   3.370 +/*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key)
   3.371 +{
   3.372 +	int cmp;
   3.373 +
   3.374 +	if(!node)
   3.375 +		return 0;
   3.376 +
   3.377 +	if((cmp = rb->cmp(key, node->key)) == 0) {
   3.378 +		return node;
   3.379 +	}
   3.380 +	return find(rb, cmp < 0 ? node->left : node->right, key);
   3.381 +}*/
   3.382 +
   3.383 +static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls)
   3.384 +{
   3.385 +	if(!node)
   3.386 +		return;
   3.387 +
   3.388 +	traverse(node->left, func, cls);
   3.389 +	func(node, cls);
   3.390 +	traverse(node->right, func, cls);
   3.391 +}
   3.392 +
   3.393 +/* helpers */
   3.394 +
   3.395 +static int is_red(struct rbnode *tree)
   3.396 +{
   3.397 +	return tree && tree->red;
   3.398 +}
   3.399 +
   3.400 +static void color_flip(struct rbnode *tree)
   3.401 +{
   3.402 +	tree->red = !tree->red;
   3.403 +	tree->left->red = !tree->left->red;
   3.404 +	tree->right->red = !tree->right->red;
   3.405 +}
   3.406 +
   3.407 +static struct rbnode *rot_left(struct rbnode *a)
   3.408 +{
   3.409 +	struct rbnode *b = a->right;
   3.410 +	a->right = b->left;
   3.411 +	b->left = a;
   3.412 +	b->red = a->red;
   3.413 +	a->red = 1;
   3.414 +	return b;
   3.415 +}
   3.416 +
   3.417 +static struct rbnode *rot_right(struct rbnode *a)
   3.418 +{
   3.419 +	struct rbnode *b = a->left;
   3.420 +	a->left = b->right;
   3.421 +	b->right = a;
   3.422 +	b->red = a->red;
   3.423 +	a->red = 1;
   3.424 +	return b;
   3.425 +}
   3.426 +
   3.427 +static struct rbnode *find_min(struct rbnode *tree)
   3.428 +{
   3.429 +	if(!tree)
   3.430 +		return 0;
   3.431 +
   3.432 +	while(tree->left) {
   3.433 +		tree = tree->left;
   3.434 +	}
   3.435 +	return tree;
   3.436 +}
   3.437 +
   3.438 +static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree)
   3.439 +{
   3.440 +	if(!tree->left) {
   3.441 +		if(rb->del) {
   3.442 +			rb->del(tree->left, rb->del_cls);
   3.443 +		}
   3.444 +		rb->free(tree->left);
   3.445 +		return 0;
   3.446 +	}
   3.447 +
   3.448 +	/* make sure we've got red (3/4-nodes) at the left side so we can delete at the bottom */
   3.449 +	if(!is_red(tree->left) && !is_red(tree->left->left)) {
   3.450 +		tree = move_red_left(tree);
   3.451 +	}
   3.452 +	tree->left = del_min(rb, tree->left);
   3.453 +
   3.454 +	/* fix right-reds, red-reds, and split 4-nodes on the way up */
   3.455 +	return fix_up(tree);
   3.456 +}
   3.457 +
   3.458 +#if 0
   3.459 +/* push a red link on this node to the right */
   3.460 +static struct rbnode *move_red_right(struct rbnode *tree)
   3.461 +{
   3.462 +	/* flipping it makes both children go red, so we have a red to the right */
   3.463 +	color_flip(tree);
   3.464 +
   3.465 +	/* if after the flip we've got a red-red situation to the left, fix it */
   3.466 +	if(is_red(tree->left->left)) {
   3.467 +		tree = rot_right(tree);
   3.468 +		color_flip(tree);
   3.469 +	}
   3.470 +	return tree;
   3.471 +}
   3.472 +#endif
   3.473 +
   3.474 +/* push a red link on this node to the left */
   3.475 +static struct rbnode *move_red_left(struct rbnode *tree)
   3.476 +{
   3.477 +	/* flipping it makes both children go red, so we have a red to the left */
   3.478 +	color_flip(tree);
   3.479 +
   3.480 +	/* if after the flip we've got a red-red on the right-left, fix it */
   3.481 +	if(is_red(tree->right->left)) {
   3.482 +		tree->right = rot_right(tree->right);
   3.483 +		tree = rot_left(tree);
   3.484 +		color_flip(tree);
   3.485 +	}
   3.486 +	return tree;
   3.487 +}
   3.488 +
   3.489 +static struct rbnode *fix_up(struct rbnode *tree)
   3.490 +{
   3.491 +	/* fix right-leaning */
   3.492 +	if(is_red(tree->right)) {
   3.493 +		tree = rot_left(tree);
   3.494 +	}
   3.495 +	/* change invalid red-red pairs into a proper 4-node */
   3.496 +	if(is_red(tree->left) && is_red(tree->left->left)) {
   3.497 +		tree = rot_right(tree);
   3.498 +	}
   3.499 +	/* split 4-nodes */
   3.500 +	if(is_red(tree->left) && is_red(tree->right)) {
   3.501 +		color_flip(tree);
   3.502 +	}
   3.503 +	return tree;
   3.504 +}

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/src/rbtree.h	Sun Aug 09 03:15:07 2015 +0300
     4.3 @@ -0,0 +1,78 @@
     4.4 +/*
     4.5 +rbtree - simple balanced binary search tree (red-black tree) library.
     4.6 +Copyright (C) 2011-2014  John Tsiombikas <nuclear@member.fsf.org>
     4.7 +
     4.8 +rbtree is free software, feel free to use, modify, and redistribute it, under
     4.9 +the terms of the 3-clause BSD license. See COPYING for details.
    4.10 + */
    4.11 +#ifndef RBTREE_H_
    4.12 +#define RBTREE_H_
    4.13 +
    4.14 +struct rbtree;
    4.15 +
    4.16 +
    4.17 +struct rbnode {
    4.18 +	void *key, *data;
    4.19 +	int red;
    4.20 +	struct rbnode *left, *right;
    4.21 +	struct rbnode *next;	/* for iterator stack */
    4.22 +};
    4.23 +
    4.24 +
    4.25 +typedef void *(*rb_alloc_func_t)(size_t);
    4.26 +typedef void (*rb_free_func_t)(void*);
    4.27 +
    4.28 +typedef int (*rb_cmp_func_t)(const void*, const void*);
    4.29 +typedef void (*rb_del_func_t)(struct rbnode*, void*);
    4.30 +
    4.31 +#define RB_KEY_ADDR		(rb_cmp_func_t)(0)
    4.32 +#define RB_KEY_INT		(rb_cmp_func_t)(1)
    4.33 +#define RB_KEY_STRING	(rb_cmp_func_t)(3)
    4.34 +
    4.35 +
    4.36 +#ifdef __cplusplus
    4.37 +extern "C" {
    4.38 +#endif
    4.39 +
    4.40 +struct rbtree *rb_create(rb_cmp_func_t cmp_func);
    4.41 +void rb_free(struct rbtree *rb);
    4.42 +
    4.43 +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func);
    4.44 +void rb_destroy(struct rbtree *rb);
    4.45 +
    4.46 +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free);
    4.47 +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func);
    4.48 +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls);
    4.49 +/* TODO add user deep copy function */
    4.50 +
    4.51 +void rb_clear(struct rbtree *rb);
    4.52 +int rb_copy(struct rbtree *dest, struct rbtree *src);
    4.53 +
    4.54 +int rb_size(struct rbtree *rb);
    4.55 +
    4.56 +int rb_insert(struct rbtree *rb, void *key, void *data);
    4.57 +int rb_inserti(struct rbtree *rb, int key, void *data);
    4.58 +
    4.59 +int rb_delete(struct rbtree *rb, void *key);
    4.60 +int rb_deletei(struct rbtree *rb, int key);
    4.61 +
    4.62 +struct rbnode *rb_find(struct rbtree *rb, void *key);
    4.63 +struct rbnode *rb_findi(struct rbtree *rb, int key);
    4.64 +
    4.65 +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls);
    4.66 +
    4.67 +struct rbnode *rb_root(struct rbtree *rb);
    4.68 +
    4.69 +void rb_begin(struct rbtree *rb);
    4.70 +struct rbnode *rb_next(struct rbtree *rb);
    4.71 +
    4.72 +void *rb_node_key(struct rbnode *node);
    4.73 +int rb_node_keyi(struct rbnode *node);
    4.74 +void *rb_node_data(struct rbnode *node);
    4.75 +
    4.76 +#ifdef __cplusplus
    4.77 +}
    4.78 +#endif
    4.79 +
    4.80 +
    4.81 +#endif	/* RBTREE_H_ */