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

Last change on this file was 76, checked in by megakiss, 10 years ago

1W 대기전력을 만족시키기 위하여 POWEROFF시 튜너를 Standby 상태로 함
  • Property svn:executable set to *
File size: 6.1 KB
Line 
1/***************************************************************************
2 *     Copyright (c) 2007 Broadcom Corporation
3 *     All Rights Reserved
4 *     Confidential Property of Broadcom Corporation
5 *
6 *  THIS SOFTWARE MAY ONLY BE USED SUBJECT TO AN EXECUTED SOFTWARE LICENSE
7 *  AGREEMENT  BETWEEN THE USER AND BROADCOM.  YOU HAVE NO RIGHT TO USE OR
8 *  EXPLOIT THIS MATERIAL EXCEPT SUBJECT TO THE TERMS OF SUCH AN AGREEMENT.
9 *
10 * $brcm_Workfile: baa_tree.h $
11 * $brcm_Revision: 3 $
12 * $brcm_Date: 7/8/09 11:48a $
13 *
14 * Module Description:
15 *
16 * Interface for AA tree, type of binary search tree
17 * Revision History:
18 *
19 * $brcm_Log: /BSEAV/lib/utils/baa_tree.h $
20 *
21 * 3   7/8/09 11:48a vsilyaev
22 * PR 55989: Fixed use of typecasting
23 *
24 * 2   8/17/07 3:37p vsilyaev
25 * PR 33812: Added FIND_SOME function
26 *
27 * 1   8/6/07 3:59p vsilyaev
28 * PR 33812: Initial implementation of AA binary search tree
29 *
30 ***************************************************************************/
31#ifndef BAA_TREE_H__
32#define BAA_TREE_H__
33
34
35#ifdef __cplusplus
36extern "C"
37{
38#endif
39
40struct baa_tree_node;
41
42#define BAA_TREE_ENTRY(type) struct { \
43                struct baa_tree_node *aan_parent, *aan_left, *aan_right; \
44                unsigned aan_level; }
45
46struct baa_tree_node {
47        BAA_TREE_ENTRY(aa_node) aa_node;
48};
49
50struct baa_tree_head {
51        struct baa_tree_node aat_root;
52};
53
54#define B_AA_TREE_CAST(node, type, off) ((struct type *)((uint8_t *)(node)-off))
55#define B_AA_TREE_OFF(type, field) ((uint8_t *)&(((struct type*)0)->field) - (uint8_t *)0)
56#define B_AA_TREE_NODE(node, off) ((struct baa_tree_node *)((uint8_t *)(node)+off))
57
58#define BAA_TREE_HEAD(name, type) struct name { struct baa_tree_head aa_tree; }
59
60#define BAA_TREE_GENERATE_FIND(name, type_key, type, field, compare) \
61static struct type *name##_baat_find(const struct name *tree, type_key key) { \
62        const unsigned off = B_AA_TREE_OFF(type, field); \
63        struct baa_tree_node *node; \
64        for(node=tree->aa_tree.aat_root.aa_node.aan_left;;) { \
65                struct baa_tree_node *next; int cmp; \
66                next = node->aa_node.aan_left; \
67                if(node==&tree->aa_tree.aat_root) { break; } \
68                cmp = compare(B_AA_TREE_CAST(node, type, off), key);\
69                if (cmp > 0) { next = node->aa_node.aan_right; \
70                } else if (cmp==0) { return B_AA_TREE_CAST(node, type, off); \
71                } /* else cmp < 0 */ node = next; \
72        } return NULL; }
73
74#define BAA_TREE_GENERATE_FIND_SOME(name, type_key, type, field, compare) \
75static struct type *name##_baat_find_some(const struct name *tree, type_key key) { \
76        const unsigned off = B_AA_TREE_OFF(type, field); \
77        struct baa_tree_node *node, *prev; \
78        prev = node=tree->aa_tree.aat_root.aa_node.aan_left;\
79        if(node==&tree->aa_tree.aat_root) { return NULL; } \
80        for(;;) { \
81                struct baa_tree_node *next; int cmp; \
82                next = node->aa_node.aan_left; \
83                if(node==&tree->aa_tree.aat_root) { break; } \
84                cmp = compare(B_AA_TREE_CAST(node, type, off), key);\
85                if (cmp > 0) { next = node->aa_node.aan_right; \
86                } else if (cmp==0) { prev = node;break;  \
87                } /* else cmp < 0 */ prev = node ; node = next; \
88        } return B_AA_TREE_CAST(prev, type, off); }
89
90#define BAA_TREE_GENERATE_INSERT(name, type_key, type, field, compare) \
91static struct type * name##_baat_insert(struct name *tree, type_key key, struct type *new_node) { \
92        const unsigned off = B_AA_TREE_OFF(type, field); \
93        struct baa_tree_node *node = tree->aa_tree.aat_root.aa_node.aan_left; \
94        struct baa_tree_node *parent = &tree->aa_tree.aat_root; int cmp = -1; \
95        BDBG_ASSERT(compare(new_node, key)==0); \
96        while(node!=&tree->aa_tree.aat_root) { \
97                cmp = compare(B_AA_TREE_CAST(node, type, off), key); parent = node; \
98                if(cmp<0) { node = node->aa_node.aan_left; } \
99                else if (cmp>0) { node = node->aa_node.aan_right; } \
100                else { return B_AA_TREE_CAST(node, type, off); } \
101        } baat_insert_node(&tree->aa_tree, B_AA_TREE_NODE(new_node, off), parent, cmp); return new_node; }
102
103#define BAA_TREE_GENERATE_REMOVE(name, type, field) \
104        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)));}
105
106#define BAA_TREE_GENERATE_FIRST(name, type, field) \
107        static struct type * name##_baat_first(struct name *tree) { return (struct type *)baat_first(&tree->aa_tree, B_AA_TREE_OFF(type, field));}
108
109#define BAA_TREE_GENERATE_LAST(name, type, field) \
110        static struct type * name##_baat_last(struct name *tree) { return (struct type *)baat_last(&tree->aa_tree, B_AA_TREE_OFF(type, field));}
111
112#define BAA_TREE_GENERATE_PREV(name, type, field) \
113        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));}
114
115#define BAA_TREE_GENERATE_NEXT(name, type, field) \
116        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));}
117
118void baat_init(struct baa_tree_head *tree);
119struct baa_tree_node *baat_first(const struct baa_tree_head *tree, unsigned off);
120struct baa_tree_node *baat_last(const struct baa_tree_head *tree, unsigned off);
121struct baa_tree_node *baat_next(struct baa_tree_head *tree, struct baa_tree_node *node, unsigned off);
122struct baa_tree_node *baat_prev(struct baa_tree_head *tree, struct baa_tree_node *node, unsigned off);
123void baat_insert_node(struct baa_tree_head *tree, struct baa_tree_node *new_node, struct baa_tree_node *parent, int cmp);
124void baat_remove(struct baa_tree_head *tree, struct baa_tree_node *node);
125
126
127#define BAA_TREE_INIT(name, head) baat_init(&(head)->aa_tree)
128
129#define BAA_TREE_INSERT(name, head, key, elm) name##_baat_insert((head), (key), (elm))
130#define BAA_TREE_FIND(name, head, key) name##_baat_find(head, key)
131#define BAA_TREE_FIND_SOME(name, head, key) name##_baat_find_some(head, key)
132#define BAA_TREE_REMOVE(name, head, elm) name##_baat_remove((head), (elm))
133#define BAA_TREE_FIRST(name, head) name##_baat_first(head)
134#define BAA_TREE_LAST(name, head) name##_baat_last(head)
135#define BAA_TREE_NEXT(name, head, elm) name##_baat_next(head, elm)
136#define BAA_TREE_PREV(name, head, elm) name##_baat_prev(head, elm)
137
138
139#ifdef __cplusplus
140}
141#endif
142
143
144
145#endif /* BAA_TREE_H__ */
146
147
148
149
Note: See TracBrowser for help on using the repository browser.