conworlds

diff src/vr/rbtree.h @ 7:bd8202d6d28d

some progress...
author John Tsiombikas <nuclear@member.fsf.org>
date Fri, 22 Aug 2014 16:55:16 +0300
parents
children
line diff
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/vr/rbtree.h	Fri Aug 22 16:55:16 2014 +0300
     1.3 @@ -0,0 +1,78 @@
     1.4 +/*
     1.5 +rbtree - simple balanced binary search tree (red-black tree) library.
     1.6 +Copyright (C) 2011-2014  John Tsiombikas <nuclear@member.fsf.org>
     1.7 +
     1.8 +rbtree is free software, feel free to use, modify, and redistribute it, under
     1.9 +the terms of the 3-clause BSD license. See COPYING for details.
    1.10 + */
    1.11 +#ifndef RBTREE_H_
    1.12 +#define RBTREE_H_
    1.13 +
    1.14 +struct rbtree;
    1.15 +
    1.16 +
    1.17 +struct rbnode {
    1.18 +	void *key, *data;
    1.19 +	int red;
    1.20 +	struct rbnode *left, *right;
    1.21 +	struct rbnode *next;	/* for iterator stack */
    1.22 +};
    1.23 +
    1.24 +
    1.25 +typedef void *(*rb_alloc_func_t)(size_t);
    1.26 +typedef void (*rb_free_func_t)(void*);
    1.27 +
    1.28 +typedef int (*rb_cmp_func_t)(const void*, const void*);
    1.29 +typedef void (*rb_del_func_t)(struct rbnode*, void*);
    1.30 +
    1.31 +#define RB_KEY_ADDR		(rb_cmp_func_t)(0)
    1.32 +#define RB_KEY_INT		(rb_cmp_func_t)(1)
    1.33 +#define RB_KEY_STRING	(rb_cmp_func_t)(3)
    1.34 +
    1.35 +
    1.36 +#ifdef __cplusplus
    1.37 +extern "C" {
    1.38 +#endif
    1.39 +
    1.40 +struct rbtree *rb_create(rb_cmp_func_t cmp_func);
    1.41 +void rb_free(struct rbtree *rb);
    1.42 +
    1.43 +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func);
    1.44 +void rb_destroy(struct rbtree *rb);
    1.45 +
    1.46 +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free);
    1.47 +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func);
    1.48 +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls);
    1.49 +/* TODO add user deep copy function */
    1.50 +
    1.51 +void rb_clear(struct rbtree *rb);
    1.52 +int rb_copy(struct rbtree *dest, struct rbtree *src);
    1.53 +
    1.54 +int rb_size(struct rbtree *rb);
    1.55 +
    1.56 +int rb_insert(struct rbtree *rb, void *key, void *data);
    1.57 +int rb_inserti(struct rbtree *rb, int key, void *data);
    1.58 +
    1.59 +int rb_delete(struct rbtree *rb, void *key);
    1.60 +int rb_deletei(struct rbtree *rb, int key);
    1.61 +
    1.62 +void *rb_find(struct rbtree *rb, void *key);
    1.63 +void *rb_findi(struct rbtree *rb, int key);
    1.64 +
    1.65 +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls);
    1.66 +
    1.67 +struct rbnode *rb_root(struct rbtree *rb);
    1.68 +
    1.69 +void rb_begin(struct rbtree *rb);
    1.70 +struct rbnode *rb_next(struct rbtree *rb);
    1.71 +
    1.72 +void *rb_node_key(struct rbnode *node);
    1.73 +int rb_node_keyi(struct rbnode *node);
    1.74 +void *rb_node_data(struct rbnode *node);
    1.75 +
    1.76 +#ifdef __cplusplus
    1.77 +}
    1.78 +#endif
    1.79 +
    1.80 +
    1.81 +#endif	/* RBTREE_H_ */