Return to rbtree.h CVS log

Up to [Dynamips Cisco Emulator] / cf

Annotation of cf/rbtree.h, revision 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.