Return to rbtree.h CVS log

Up to [Dynamips Cisco Emulator] / cf

Annotation of cf/rbtree.h, revision 1.1.1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.