1 |
dpavlin |
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 |