source: svn/newcon3bcm2_21bu/BSEAV/lib/utils/baa_tree.h @ 46

/***************************************************************************
 *     Copyright (c) 2007 Broadcom Corporation
 *     All Rights Reserved
 *     Confidential Property of Broadcom Corporation
 *
 *  THIS SOFTWARE MAY ONLY BE USED SUBJECT TO AN EXECUTED SOFTWARE LICENSE
 *  AGREEMENT  BETWEEN THE USER AND BROADCOM.  YOU HAVE NO RIGHT TO USE OR
 *  EXPLOIT THIS MATERIAL EXCEPT SUBJECT TO THE TERMS OF SUCH AN AGREEMENT.
 *
 * $brcm_Workfile: baa_tree.h $
 * $brcm_Revision: 3 $
 * $brcm_Date: 7/8/09 11:48a $
 *
 * Module Description:
 *
 * Interface for AA tree, type of binary search tree
 * Revision History:
 *
 * $brcm_Log: /BSEAV/lib/utils/baa_tree.h $
 * 
 * 3   7/8/09 11:48a vsilyaev
 * PR 55989: Fixed use of typecasting
 * 
 * 2   8/17/07 3:37p vsilyaev
 * PR 33812: Added FIND_SOME function
 * 
 * 1   8/6/07 3:59p vsilyaev
 * PR 33812: Initial implementation of AA binary search tree
 * 
 ***************************************************************************/
#ifndef BAA_TREE_H__
#define BAA_TREE_H__


#ifdef __cplusplus
extern "C"
{
#endif

struct baa_tree_node;

#define BAA_TREE_ENTRY(type) struct { \
                struct baa_tree_node *aan_parent, *aan_left, *aan_right; \
                unsigned aan_level; }

struct baa_tree_node {
        BAA_TREE_ENTRY(aa_node) aa_node;
};

struct baa_tree_head {
        struct baa_tree_node aat_root;
};

#define B_AA_TREE_CAST(node, type, off) ((struct type *)((uint8_t *)(node)-off))
#define B_AA_TREE_OFF(type, field) ((uint8_t *)&(((struct type*)0)->field) - (uint8_t *)0)
#define B_AA_TREE_NODE(node, off) ((struct baa_tree_node *)((uint8_t *)(node)+off))

#define BAA_TREE_HEAD(name, type) struct name { struct baa_tree_head aa_tree; }

#define BAA_TREE_GENERATE_FIND(name, type_key, type, field, compare) \
static struct type *name##_baat_find(const struct name *tree, type_key key) { \
        const unsigned off = B_AA_TREE_OFF(type, field); \
        struct baa_tree_node *node; \
        for(node=tree->aa_tree.aat_root.aa_node.aan_left;;) { \
                struct baa_tree_node *next; int cmp; \
                next = node->aa_node.aan_left; \
                if(node==&tree->aa_tree.aat_root) { break; } \
                cmp = compare(B_AA_TREE_CAST(node, type, off), key);\
                if (cmp > 0) { next = node->aa_node.aan_right; \
                } else if (cmp==0) { return B_AA_TREE_CAST(node, type, off); \
                } /* else cmp < 0 */ node = next; \
        } return NULL; } 

#define BAA_TREE_GENERATE_FIND_SOME(name, type_key, type, field, compare) \
static struct type *name##_baat_find_some(const struct name *tree, type_key key) { \
        const unsigned off = B_AA_TREE_OFF(type, field); \
        struct baa_tree_node *node, *prev; \
        prev = node=tree->aa_tree.aat_root.aa_node.aan_left;\
        if(node==&tree->aa_tree.aat_root) { return NULL; } \
        for(;;) { \
                struct baa_tree_node *next; int cmp; \
                next = node->aa_node.aan_left; \
                if(node==&tree->aa_tree.aat_root) { break; } \
                cmp = compare(B_AA_TREE_CAST(node, type, off), key);\
                if (cmp > 0) { next = node->aa_node.aan_right; \
                } else if (cmp==0) { prev = node;break;  \
                } /* else cmp < 0 */ prev = node ; node = next; \
        } return B_AA_TREE_CAST(prev, type, off); } 

#define BAA_TREE_GENERATE_INSERT(name, type_key, type, field, compare) \
static struct type * name##_baat_insert(struct name *tree, type_key key, struct type *new_node) { \
        const unsigned off = B_AA_TREE_OFF(type, field); \
        struct baa_tree_node *node = tree->aa_tree.aat_root.aa_node.aan_left; \
        struct baa_tree_node *parent = &tree->aa_tree.aat_root; int cmp = -1; \
        BDBG_ASSERT(compare(new_node, key)==0); \
        while(node!=&tree->aa_tree.aat_root) { \
                cmp = compare(B_AA_TREE_CAST(node, type, off), key); parent = node; \
                if(cmp<0) { node = node->aa_node.aan_left; } \
                else if (cmp>0) { node = node->aa_node.aan_right; } \
                else { return B_AA_TREE_CAST(node, type, off); } \
        } baat_insert_node(&tree->aa_tree, B_AA_TREE_NODE(new_node, off), parent, cmp); return new_node; }

#define BAA_TREE_GENERATE_REMOVE(name, type, field) \
        static void name##_baat_remove(struct name *tree, struct type *node) { baat_remove(&tree->aa_tree, B_AA_TREE_NODE(node, B_AA_TREE_OFF(type, field)));}

#define BAA_TREE_GENERATE_FIRST(name, type, field) \
        static struct type * name##_baat_first(struct name *tree) { return (struct type *)baat_first(&tree->aa_tree, B_AA_TREE_OFF(type, field));}

#define BAA_TREE_GENERATE_LAST(name, type, field) \
        static struct type * name##_baat_last(struct name *tree) { return (struct type *)baat_last(&tree->aa_tree, B_AA_TREE_OFF(type, field));}

#define BAA_TREE_GENERATE_PREV(name, type, field) \
        static struct type * name##_baat_prev(struct name *tree, struct type *node) { return (struct type *)baat_prev(&tree->aa_tree, (struct baa_tree_node *)node, B_AA_TREE_OFF(type, field));}

#define BAA_TREE_GENERATE_NEXT(name, type, field) \
        static struct type * name##_baat_next(struct name *tree, struct type *node) { return (struct type *)baat_next(&tree->aa_tree, (struct baa_tree_node *)node, B_AA_TREE_OFF(type, field));}

void baat_init(struct baa_tree_head *tree);
struct baa_tree_node *baat_first(const struct baa_tree_head *tree, unsigned off);
struct baa_tree_node *baat_last(const struct baa_tree_head *tree, unsigned off);
struct baa_tree_node *baat_next(struct baa_tree_head *tree, struct baa_tree_node *node, unsigned off);
struct baa_tree_node *baat_prev(struct baa_tree_head *tree, struct baa_tree_node *node, unsigned off);
void baat_insert_node(struct baa_tree_head *tree, struct baa_tree_node *new_node, struct baa_tree_node *parent, int cmp);
void baat_remove(struct baa_tree_head *tree, struct baa_tree_node *node);


#define BAA_TREE_INIT(name, head) baat_init(&(head)->aa_tree)

#define BAA_TREE_INSERT(name, head, key, elm) name##_baat_insert((head), (key), (elm))
#define BAA_TREE_FIND(name, head, key) name##_baat_find(head, key)
#define BAA_TREE_FIND_SOME(name, head, key) name##_baat_find_some(head, key)
#define BAA_TREE_REMOVE(name, head, elm) name##_baat_remove((head), (elm))
#define BAA_TREE_FIRST(name, head) name##_baat_first(head)
#define BAA_TREE_LAST(name, head) name##_baat_last(head)
#define BAA_TREE_NEXT(name, head, elm) name##_baat_next(head, elm)
#define BAA_TREE_PREV(name, head, elm) name##_baat_prev(head, elm)


#ifdef __cplusplus
}
#endif



#endif /* BAA_TREE_H__ */