1 |
/* |
2 |
* IPFlow Collector |
3 |
* Copyright (c) 2004 Christophe Fillot. |
4 |
* E-mail: cf@utc.fr |
5 |
* |
6 |
* rbtree.c: Red/Black Trees. |
7 |
*/ |
8 |
|
9 |
#ifndef __RBTREE_H__ |
10 |
#define __RBTREE_H__ 1 |
11 |
|
12 |
static const char rcsid_rbtree[] = "$Id$"; |
13 |
|
14 |
#include <sys/types.h> |
15 |
#include "mempool.h" |
16 |
|
17 |
/* Comparison function for 2 keys */ |
18 |
typedef int (*tree_fcompare)(void *key1,void *key2,void *opt); |
19 |
|
20 |
/* User function to call when using rbtree_foreach */ |
21 |
typedef void (*tree_fforeach)(void *key,void *value,void *opt); |
22 |
|
23 |
/* Node colors */ |
24 |
enum { |
25 |
RBTREE_RED = 0, |
26 |
RBTREE_BLACK, |
27 |
}; |
28 |
|
29 |
/* |
30 |
* Description of a node in a Red/Black tree. To be more efficient, keys are |
31 |
* stored with a void * pointer, allowing to use different type keys. |
32 |
*/ |
33 |
typedef struct rbtree_node rbtree_node; |
34 |
struct rbtree_node { |
35 |
/* Key and Value */ |
36 |
void *key,*value; |
37 |
|
38 |
/* Left and right nodes */ |
39 |
rbtree_node *left,*right; |
40 |
|
41 |
/* Parent node */ |
42 |
rbtree_node *parent; |
43 |
|
44 |
/* Node color */ |
45 |
short color; |
46 |
}; |
47 |
|
48 |
/* |
49 |
* Description of a Red/Black tree. For commodity, a name can be given to the |
50 |
* tree. "rbtree_comp" is a pointer to a function, defined by user, which |
51 |
* compares keys during node operations. |
52 |
*/ |
53 |
typedef struct rbtree_tree rbtree_tree; |
54 |
struct rbtree_tree { |
55 |
int node_count; /* Number of Nodes */ |
56 |
mempool_t mp; /* Memory pool */ |
57 |
rbtree_node nil; /* Sentinel */ |
58 |
rbtree_node *root; /* Root node */ |
59 |
tree_fcompare key_cmp; /* Key comparison function */ |
60 |
void *opt_data; /* Optional data for comparison */ |
61 |
}; |
62 |
|
63 |
/* Insert a node in an Red/Black tree */ |
64 |
int rbtree_insert(rbtree_tree *tree,void *key,void *value); |
65 |
|
66 |
/* Removes a node out of a tree */ |
67 |
void *rbtree_remove(rbtree_tree *tree,void *key); |
68 |
|
69 |
/* |
70 |
* Lookup for a node corresponding to "key". If node does not exist, |
71 |
* function returns null pointer. |
72 |
*/ |
73 |
void *rbtree_lookup(rbtree_tree *tree,void *key); |
74 |
|
75 |
/* Call the specified function for each node */ |
76 |
int rbtree_foreach(rbtree_tree *tree,tree_fforeach user_fn,void *opt); |
77 |
|
78 |
/* Compute the height of a Red/Black tree */ |
79 |
int rbtree_height(rbtree_tree *tree); |
80 |
|
81 |
/* Returns the number of nodes */ |
82 |
int rbtree_node_count(rbtree_tree *tree); |
83 |
|
84 |
/* Purge all nodes */ |
85 |
void rbtree_purge(rbtree_tree *tree); |
86 |
|
87 |
/* Check tree consistency */ |
88 |
int rbtree_check(rbtree_tree *tree); |
89 |
|
90 |
/* Create a new Red/Black tree */ |
91 |
rbtree_tree *rbtree_create(tree_fcompare key_cmp,void *opt_data); |
92 |
|
93 |
/* Delete an Red/Black tree */ |
94 |
void rbtree_delete(rbtree_tree *tree); |
95 |
|
96 |
#endif |