/[dynamips]/trunk/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

Annotation of /trunk/rbtree.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 11 - (hide annotations)
Sat Oct 6 16:33:40 2007 UTC (16 years, 5 months ago) by dpavlin
Original Path: upstream/dynamips-0.2.8-RC1/rbtree.h
File MIME type: text/plain
File size: 2484 byte(s)
dynamips-0.2.8-RC1

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

  ViewVC Help
Powered by ViewVC 1.1.26