/*************************************************************************** * 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__ */