git.mutantstargoat.com Git - vrtris/blob - src/rbtree.h

   1 /*
   2 rbtree - simple balanced binary search tree (red-black tree) library.
   3 Copyright (C) 2011-2014  John Tsiombikas <nuclear@member.fsf.org>
   4
   5 rbtree is free software, feel free to use, modify, and redistribute it, under
   6 the terms of the 3-clause BSD license. See COPYING for details.
   7  */
   8 #ifndef RBTREE_H_
   9 #define RBTREE_H_
  10
  11 struct rbtree;
  12
  13
  14 struct rbnode {
  15         void *key, *data;
  16         int red;
  17         struct rbnode *left, *right;
  18         struct rbnode *next;    /* for iterator stack */
  19 };
  20
  21
  22 typedef void *(*rb_alloc_func_t)(size_t);
  23 typedef void (*rb_free_func_t)(void*);
  24
  25 typedef int (*rb_cmp_func_t)(const void*, const void*);
  26 typedef void (*rb_del_func_t)(struct rbnode*, void*);
  27
  28 #define RB_KEY_ADDR             (rb_cmp_func_t)(0)
  29 #define RB_KEY_INT              (rb_cmp_func_t)(1)
  30 #define RB_KEY_STRING   (rb_cmp_func_t)(3)
  31
  32
  33 #ifdef __cplusplus
  34 extern "C" {
  35 #endif
  36
  37 struct rbtree *rb_create(rb_cmp_func_t cmp_func);
  38 void rb_free(struct rbtree *rb);
  39
  40 int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func);
  41 void rb_destroy(struct rbtree *rb);
  42
  43 void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free);
  44 void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func);
  45 void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls);
  46 /* TODO add user deep copy function */
  47
  48 void rb_clear(struct rbtree *rb);
  49 int rb_copy(struct rbtree *dest, struct rbtree *src);
  50
  51 int rb_size(struct rbtree *rb);
  52
  53 int rb_insert(struct rbtree *rb, void *key, void *data);
  54 int rb_inserti(struct rbtree *rb, int key, void *data);
  55
  56 int rb_delete(struct rbtree *rb, void *key);
  57 int rb_deletei(struct rbtree *rb, int key);
  58
  59 struct rbnode *rb_find(struct rbtree *rb, void *key);
  60 struct rbnode *rb_findi(struct rbtree *rb, int key);
  61
  62 void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls);
  63
  64 struct rbnode *rb_root(struct rbtree *rb);
  65
  66 void rb_begin(struct rbtree *rb);
  67 struct rbnode *rb_next(struct rbtree *rb);
  68
  69 void *rb_node_key(struct rbnode *node);
  70 int rb_node_keyi(struct rbnode *node);
  71 void *rb_node_data(struct rbnode *node);
  72
  73 #ifdef __cplusplus
  74 }
  75 #endif
  76
  77
  78 #endif  /* RBTREE_H_ */