kern

annotate src/rbtree.h @ 68:0a205396e1a0

find changesets by author, revision, files, or words in the commit message
- added a generic red-black tree data structure - added a VM map as an red-black tree of vm_pages in the process structure - constructed the vm map of the memory passed by the kernel initially to the first process.
author John Tsiombikas <nuclear@mutantstargoat.com>
date Mon, 10 Oct 2011 04:16:01 +0300
parents
children b45e2d5f0ae1
rev   line source
nuclear@68 1 #ifndef RBTREE_H_
nuclear@68 2 #define RBTREE_H_
nuclear@68 3
nuclear@68 4 struct rbtree;
nuclear@68 5 struct rbnode;
nuclear@68 6
nuclear@68 7
nuclear@68 8 typedef void *(*rb_alloc_func_t)(size_t);
nuclear@68 9 typedef void (*rb_free_func_t)(void*);
nuclear@68 10
nuclear@68 11 typedef int (*rb_cmp_func_t)(void*, void*);
nuclear@68 12 typedef void (*rb_del_func_t)(struct rbnode*, void*);
nuclear@68 13
nuclear@68 14
nuclear@68 15 struct rbtree {
nuclear@68 16 struct rbnode *root;
nuclear@68 17
nuclear@68 18 rb_alloc_func_t alloc;
nuclear@68 19 rb_free_func_t free;
nuclear@68 20
nuclear@68 21 rb_cmp_func_t cmp;
nuclear@68 22 rb_del_func_t del;
nuclear@68 23 void *del_cls;
nuclear@68 24
nuclear@68 25 struct rbnode *rstack, *iter;
nuclear@68 26 };
nuclear@68 27
nuclear@68 28
nuclear@68 29 struct rbnode {
nuclear@68 30 void *key, *data;
nuclear@68 31 int red;
nuclear@68 32 struct rbnode *left, *right;
nuclear@68 33 struct rbnode *next; /* for iterator stack */
nuclear@68 34 };
nuclear@68 35
nuclear@68 36 #define RB_KEY_ADDR (rb_cmp_func_t)(0)
nuclear@68 37 #define RB_KEY_INT (rb_cmp_func_t)(1)
nuclear@68 38 #define RB_KEY_STRING (rb_cmp_func_t)(3)
nuclear@68 39
nuclear@68 40
nuclear@68 41 #ifdef __cplusplus
nuclear@68 42 extern "C" {
nuclear@68 43 #endif
nuclear@68 44
nuclear@68 45 struct rbtree *rb_create(rb_cmp_func_t cmp_func);
nuclear@68 46 void rb_free(struct rbtree *rb);
nuclear@68 47
nuclear@68 48 int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func);
nuclear@68 49 void rb_destroy(struct rbtree *rb);
nuclear@68 50
nuclear@68 51 void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free);
nuclear@68 52 void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func);
nuclear@68 53 void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls);
nuclear@68 54
nuclear@68 55 int rb_size(struct rbtree *rb);
nuclear@68 56
nuclear@68 57 int rb_insert(struct rbtree *rb, void *key, void *data);
nuclear@68 58 int rb_inserti(struct rbtree *rb, int key, void *data);
nuclear@68 59
nuclear@68 60 int rb_delete(struct rbtree *rb, void *key);
nuclear@68 61 int rb_deletei(struct rbtree *rb, int key);
nuclear@68 62
nuclear@68 63 void *rb_find(struct rbtree *rb, void *key);
nuclear@68 64 void *rb_findi(struct rbtree *rb, int key);
nuclear@68 65
nuclear@68 66 void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls);
nuclear@68 67
nuclear@68 68 struct rbnode *rb_root(struct rbtree *rb);
nuclear@68 69
nuclear@68 70 void rb_begin(struct rbtree *rb);
nuclear@68 71 struct rbnode *rb_next(struct rbtree *rb);
nuclear@68 72
nuclear@68 73 void *rb_node_key(struct rbnode *node);
nuclear@68 74 int rb_node_keyi(struct rbnode *node);
nuclear@68 75 void *rb_node_data(struct rbnode *node);
nuclear@68 76
nuclear@68 77 #ifdef __cplusplus
nuclear@68 78 }
nuclear@68 79 #endif
nuclear@68 80
nuclear@68 81
nuclear@68 82 #endif /* RBTREE_H_ */