00001
00002
00003
00004
00005
00006
00007 #ifndef _NM_RBT_T
00008 #define _NM_RBT_T
00009
00010 #ifdef __cplusplus
00011 extern "C" {
00012 #endif
00013
00014
00015
00016
00017
00018
00019
00020 #define NM_RBN_RED 0
00021 #define NM_RBN_BLACK 1
00022
00023
00024 struct nm_rbn {
00025 struct nm_rbn *left;
00026 struct nm_rbn *right;
00027 struct nm_rbn *parent;
00028 int color;
00029 void *key;
00030 };
00031
00032
00033 typedef int (*nm_rbn_comparator_t)(void *, void *);
00034
00035
00036 typedef void (*nm_rbn_node_fn)(struct nm_rbn *, void *, int);
00037
00038 struct nm_rbt {
00039 struct nm_rbn *root;
00040 nm_rbn_comparator_t comparator;
00041 };
00042
00043 void nm_rbt_init(struct nm_rbt *t, nm_rbn_comparator_t c);
00044 struct nm_rbn *nm_rbt_find(struct nm_rbt *t, void *k);
00045 struct nm_rbn *nm_rbt_find_min(struct nm_rbt *t);
00046 struct nm_rbn *nm_rbt_find_max(struct nm_rbt *t);
00047 void nm_rbt_ins(struct nm_rbt *t, struct nm_rbn *n);
00048 void nm_rbt_del(struct nm_rbt *t, struct nm_rbn *n);
00049 void nm_rbt_traverse(struct nm_rbt *t, nm_rbn_node_fn f, void *fn_data);
00050 int nm_rbt_is_leaf(struct nm_rbn *n);
00051
00052 #ifdef __cplusplus
00053 }
00054 #endif
00055
00056 #endif