kern
diff src/rbtree.h @ 68:0a205396e1a0
- 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 |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/rbtree.h Mon Oct 10 04:16:01 2011 +0300 1.3 @@ -0,0 +1,82 @@ 1.4 +#ifndef RBTREE_H_ 1.5 +#define RBTREE_H_ 1.6 + 1.7 +struct rbtree; 1.8 +struct rbnode; 1.9 + 1.10 + 1.11 +typedef void *(*rb_alloc_func_t)(size_t); 1.12 +typedef void (*rb_free_func_t)(void*); 1.13 + 1.14 +typedef int (*rb_cmp_func_t)(void*, void*); 1.15 +typedef void (*rb_del_func_t)(struct rbnode*, void*); 1.16 + 1.17 + 1.18 +struct rbtree { 1.19 + struct rbnode *root; 1.20 + 1.21 + rb_alloc_func_t alloc; 1.22 + rb_free_func_t free; 1.23 + 1.24 + rb_cmp_func_t cmp; 1.25 + rb_del_func_t del; 1.26 + void *del_cls; 1.27 + 1.28 + struct rbnode *rstack, *iter; 1.29 +}; 1.30 + 1.31 + 1.32 +struct rbnode { 1.33 + void *key, *data; 1.34 + int red; 1.35 + struct rbnode *left, *right; 1.36 + struct rbnode *next; /* for iterator stack */ 1.37 +}; 1.38 + 1.39 +#define RB_KEY_ADDR (rb_cmp_func_t)(0) 1.40 +#define RB_KEY_INT (rb_cmp_func_t)(1) 1.41 +#define RB_KEY_STRING (rb_cmp_func_t)(3) 1.42 + 1.43 + 1.44 +#ifdef __cplusplus 1.45 +extern "C" { 1.46 +#endif 1.47 + 1.48 +struct rbtree *rb_create(rb_cmp_func_t cmp_func); 1.49 +void rb_free(struct rbtree *rb); 1.50 + 1.51 +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func); 1.52 +void rb_destroy(struct rbtree *rb); 1.53 + 1.54 +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free); 1.55 +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func); 1.56 +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls); 1.57 + 1.58 +int rb_size(struct rbtree *rb); 1.59 + 1.60 +int rb_insert(struct rbtree *rb, void *key, void *data); 1.61 +int rb_inserti(struct rbtree *rb, int key, void *data); 1.62 + 1.63 +int rb_delete(struct rbtree *rb, void *key); 1.64 +int rb_deletei(struct rbtree *rb, int key); 1.65 + 1.66 +void *rb_find(struct rbtree *rb, void *key); 1.67 +void *rb_findi(struct rbtree *rb, int key); 1.68 + 1.69 +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls); 1.70 + 1.71 +struct rbnode *rb_root(struct rbtree *rb); 1.72 + 1.73 +void rb_begin(struct rbtree *rb); 1.74 +struct rbnode *rb_next(struct rbtree *rb); 1.75 + 1.76 +void *rb_node_key(struct rbnode *node); 1.77 +int rb_node_keyi(struct rbnode *node); 1.78 +void *rb_node_data(struct rbnode *node); 1.79 + 1.80 +#ifdef __cplusplus 1.81 +} 1.82 +#endif 1.83 + 1.84 + 1.85 +#endif /* RBTREE_H_ */