Return to rbtree.h CVS log

Up to [Dynamips Cisco Emulator] / cf

Annotation of cf/rbtree.h, revision 1.1.1.2

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>
1.1.1.2 ! root       15: #include "mempool.h"
1.1       root       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 */
1.1.1.2 ! root       56:    mempool_t mp;                  /* Memory pool */
1.1       root       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

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