bintree.h

 
/*---------------------------------------------------------------
 HISTORY
 7-Dec-2004     Graeme McKerrell    
   Updated to use the "lub" prefix
27-Feb-2004     Graeme McKerrell    
   updated to simplify node initialisation
9-Feb-2004      Graeme McKerrell    
   updated to make the comparision function compare a "clientnode" and
   "key"
   Updated getkey() function to fill out a provides "key" from a "clientnode"
23-Jan-2004     Graeme McKerrell    
   Initial version
--------------------------------------------------------------
Copyright (C) 2004 3Com Corporation. All Rights Reserved.
**************************************************************** */
#ifndef _lub_bintree_h
#define _lub_bintree_h
#include <stddef.h>
 
/****************************************************************
 * TYPE DEFINITIONS
 **************************************************************** */
typedef struct lub_bintree_node_s lub_bintree_node_t;
struct lub_bintree_node_s
{lub_bintree_node_t *left; lub_bintree_node_t *right;
};
 
typedef int
        lub_bintree_compare_fn(const void *clientnode,
                       const void *clientkey);
#define lub_bintree_MAX_KEY_STORAGE (200)
typedef struct lub_bintree_key_s lub_bintree_key_t;
struct lub_bintree_key_s
{char storage[lub_bintree_MAX_KEY_STORAGE];int  magic;
};
 
typedef void
        lub_bintree_getkey_fn(const void        *clientnode,
                              lub_bintree_key_t *key);
 
typedef struct lub_bintree_s lub_bintree_t;
struct lub_bintree_s
{lub_bintree_node_t     *root;size_t                  node_offset;lub_bintree_compare_fn *compareFn;lub_bintree_getkey_fn  *getkeyFn;
};
 
typedef struct lub_bintree_iterator_s lub_bintree_iterator_t;
struct lub_bintree_iterator_s
{lub_bintree_t    *tree;lub_bintree_key_t key;
};
 
/****************************************************************
 * BINTREE OPERATIONS
 **************************************************************** */
extern void
    lub_bintree_init(
        lub_bintree_t         *tree,
        size_t                 node_offset,
        lub_bintree_compare_fn compareFn,
        lub_bintree_getkey_fn  getkeyFn
    );
 
extern void
        lub_bintree_node_init(
            lub_bintree_node_t *node
        );
 
/*****************************************
 * NODE MANIPULATION OPERATIONS
 ***************************************** */
extern int
        lub_bintree_insert(
            lub_bintree_t *tree,
            void          *clientnode
        );
 
extern void
        lub_bintree_remove(
            lub_bintree_t *tree,
            void          *clientnode
        );
 
/*****************************************
 * NODE RETRIEVAL OPERATIONS
 ***************************************** */
extern void *
    lub_bintree_findfirst(
        lub_bintree_t *tree
    );
 
extern void *
    lub_bintree_findlast(
        lub_bintree_t *tree
    );
 
extern void *
    lub_bintree_find(
        lub_bintree_t *tree,
            const void    *key
    );
 
extern void *
    lub_bintree_findnext(
        lub_bintree_t *tree,
            const void    *key
    );
 
extern void *
    lub_bintree_findprevious(
        lub_bintree_t *tree,
                const void    *key
    );
 
/*****************************************
 * ITERATION OPERATIONS
 ***************************************** */
extern void
        lub_bintree_iterator_init(
            lub_bintree_iterator_t *iter,
            lub_bintree_t          *tree,
            const void             *clientnode
            );
 
extern void *
    lub_bintree_iterator_next(
        lub_bintree_iterator_t *iter
    );
 
extern void *
    lub_bintree_iterator_previous(
        lub_bintree_iterator_t *iter
    );
extern void
    lub_bintree_dump(
    lub_bintree_t *tree
    );
 
#endif /* _lub_bintree_h */