/[dynamips]/upstream/dynamips-0.2.7/rbtree.h
This is repository of my old source code which isn't updated any more. Go to git.rot13.org for current projects!
ViewVC logotype

Contents of /upstream/dynamips-0.2.7/rbtree.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 10 - (show annotations)
Sat Oct 6 16:29:14 2007 UTC (16 years, 5 months ago) by dpavlin
File MIME type: text/plain
File size: 2484 byte(s)
dynamips-0.2.7

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

  ViewVC Help
Powered by ViewVC 1.1.26