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

Last change on this file since 46 was 46, checked in by megakiss, 11 years ago

459Mhz로 OTC 주파수 변경
  • Property svn:executable set to *
File size: 7.6 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.c $
11 * $brcm_Revision: 2 $
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.c $
20 *
21 * 2   7/8/09 11:48a vsilyaev
22 * PR 55989: Fixed use of typecasting
23 *
24 * 1   8/6/07 3:59p vsilyaev
25 * PR 33812: Initial implementation of AA binary search tree
26 *
27 ***************************************************************************/
28
29#include "bstd.h"
30#include "baa_tree.h"
31BDBG_MODULE(baa_tree);
32
33
34#define B_AA_NODE_LEVEL(node) ((node)->aa_node.aan_level)
35#define B_AA_LAST_NODE(tree) (&(tree)->aat_root)
36#define B_AA_ROOT_NODE(tree) (&(tree)->aat_root)
37
38
39void 
40baat_init(struct baa_tree_head *tree)
41{
42        tree->aat_root.aa_node.aan_level = 0;
43        tree->aat_root.aa_node.aan_left = B_AA_LAST_NODE(tree);
44        tree->aat_root.aa_node.aan_right = B_AA_LAST_NODE(tree);
45        tree->aat_root.aa_node.aan_parent = B_AA_ROOT_NODE(tree);
46        return;
47}
48
49
50struct baa_tree_node *
51baat_first(const struct baa_tree_head *tree, unsigned off) 
52{
53        struct baa_tree_node *root = tree->aat_root.aa_node.aan_left;
54        struct baa_tree_node *parent = NULL;
55        while(root!=B_AA_LAST_NODE(tree)) {
56                parent = root;
57                root = root->aa_node.aan_left;
58        }
59    if(parent) {
60            return B_AA_TREE_CAST(parent, baa_tree_node, off);
61    } else {
62            return NULL;
63    }
64}
65
66struct baa_tree_node *
67baat_last(const struct baa_tree_head *tree, unsigned off) 
68{
69        struct baa_tree_node *root = tree->aat_root.aa_node.aan_left;
70        struct baa_tree_node *parent = NULL;
71        while(root!=B_AA_LAST_NODE(tree)) {
72                parent = root;
73                root = root->aa_node.aan_right;
74        }
75    if(parent) {
76            return B_AA_TREE_CAST(parent, baa_tree_node, off);
77    } else {
78        return NULL;
79    }
80}
81
82struct baa_tree_node *
83baat_next(struct baa_tree_head *tree, struct baa_tree_node *node, unsigned off)
84{
85        struct baa_tree_node *next;
86        node = B_AA_TREE_NODE(node, off);
87
88        next = node->aa_node.aan_right;
89        if(B_AA_LAST_NODE(tree)!=next) {
90                node = next;
91                while(B_AA_LAST_NODE(tree)!=(next=node->aa_node.aan_left)) {
92                        node = next;
93                }
94        } else {
95                while( (B_AA_ROOT_NODE(tree) != (next=node->aa_node.aan_parent)) && (node==next->aa_node.aan_right)) {
96                        node = next;
97                }
98                node = next;
99                if(node==B_AA_ROOT_NODE(tree)) {
100                        return NULL;
101                }
102        }
103        return B_AA_TREE_CAST(node, baa_tree_node, off);
104}
105
106struct baa_tree_node *
107baat_prev(struct baa_tree_head *tree, struct baa_tree_node *node, unsigned off)
108{
109        struct baa_tree_node *prev;
110
111        node = B_AA_TREE_NODE(node, off);
112
113        prev = node->aa_node.aan_left;
114        if(B_AA_LAST_NODE(tree)!=prev) {
115                node = prev;
116                while(B_AA_LAST_NODE(tree)!=(prev=node->aa_node.aan_right)) {
117                        node = prev;
118                }
119        } else {
120                while( (B_AA_ROOT_NODE(tree) != (prev=node->aa_node.aan_parent)) && (node==prev->aa_node.aan_left)) {
121                        node = prev;
122                }
123                node = prev;
124                if(node==B_AA_ROOT_NODE(tree)) {
125                        return NULL;
126                }
127        }
128        return B_AA_TREE_CAST(node, baa_tree_node, off);
129}
130
131static void 
132baat_skew(struct baa_tree_node *parent)
133{
134        struct baa_tree_node *new_parent = parent->aa_node.aan_left;
135
136        BDBG_ASSERT(new_parent);
137
138        if(parent->aa_node.aan_parent->aa_node.aan_left == parent) {
139                parent->aa_node.aan_parent->aa_node.aan_left = new_parent;
140        } else {
141                parent->aa_node.aan_parent->aa_node.aan_right = new_parent;
142        }
143        new_parent->aa_node.aan_parent = parent->aa_node.aan_parent;
144        parent->aa_node.aan_parent = new_parent;
145
146        parent->aa_node.aan_left = new_parent->aa_node.aan_right;
147        parent->aa_node.aan_left->aa_node.aan_parent = parent;
148        new_parent->aa_node.aan_right = parent;
149
150        parent->aa_node.aan_level = B_AA_NODE_LEVEL(parent->aa_node.aan_left)+1;
151
152        return;
153}
154
155static bool
156baat_split(struct baa_tree_head *tree, struct baa_tree_node *parent)
157{
158        struct baa_tree_node *new_parent = parent->aa_node.aan_right;
159
160        if(B_AA_LAST_NODE(tree)!=new_parent && parent->aa_node.aan_right->aa_node.aan_right->aa_node.aan_level == parent->aa_node.aan_level) {
161                if(parent->aa_node.aan_parent->aa_node.aan_left == parent) {
162                        parent->aa_node.aan_parent->aa_node.aan_left = new_parent;
163                } else {
164                        parent->aa_node.aan_parent->aa_node.aan_right = new_parent;
165                }
166                new_parent->aa_node.aan_parent = parent->aa_node.aan_parent;
167                parent->aa_node.aan_parent = new_parent;
168
169                parent->aa_node.aan_right = new_parent->aa_node.aan_left;
170                parent->aa_node.aan_right->aa_node.aan_parent = parent;
171                new_parent->aa_node.aan_left = parent;
172                new_parent->aa_node.aan_level++;
173                return true;
174        }
175        return false;
176}
177
178
179void 
180baat_insert_node(struct baa_tree_head *tree, struct baa_tree_node *new_node, struct baa_tree_node *parent, int cmp)
181{
182        struct baa_tree_node *node;
183
184        if(cmp<0) {
185                parent->aa_node.aan_left = new_node;
186        } else {
187                parent->aa_node.aan_right = new_node;
188        } 
189        new_node->aa_node.aan_level = 1;
190        new_node->aa_node.aan_left = B_AA_LAST_NODE(tree);
191        new_node->aa_node.aan_right = B_AA_LAST_NODE(tree);
192        new_node->aa_node.aan_parent = parent;
193        for(node=parent; node!= B_AA_ROOT_NODE(tree) ; node = node->aa_node.aan_parent) {
194                if(node->aa_node.aan_level != B_AA_NODE_LEVEL(node->aa_node.aan_left) + 1) {
195                        baat_skew(node);
196                        if( (node->aa_node.aan_level != node->aa_node.aan_right->aa_node.aan_level)) {
197                                node = node->aa_node.aan_parent;
198                        }
199                }
200                if(!baat_split(tree, node->aa_node.aan_parent)) {
201                        break;
202                }
203        }
204}
205
206
207
208void 
209baat_remove(struct baa_tree_head *tree, struct baa_tree_node *node)
210{
211         struct baa_tree_node *leaf;
212         struct baa_tree_node *parent;
213
214         if(B_AA_LAST_NODE(tree)!=node->aa_node.aan_left) {
215                 for(leaf=node->aa_node.aan_left;B_AA_LAST_NODE(tree)!=leaf->aa_node.aan_right;leaf=leaf->aa_node.aan_right) {
216                 }
217         } else {
218                 if(B_AA_LAST_NODE(tree)!=node->aa_node.aan_right) {
219                         leaf = node->aa_node.aan_right;
220                 } else {
221                         leaf = node;
222                 }
223         }
224         parent = leaf->aa_node.aan_parent == node ? leaf : leaf->aa_node.aan_parent;
225         if(leaf->aa_node.aan_parent->aa_node.aan_left == leaf) {
226                 leaf->aa_node.aan_parent->aa_node.aan_left = B_AA_LAST_NODE(tree);
227         } else {
228                 leaf->aa_node.aan_parent->aa_node.aan_right = B_AA_LAST_NODE(tree);
229         }
230         if(node!=leaf) { /* swap leaf and node */
231                 if(node->aa_node.aan_parent->aa_node.aan_left == node) {
232                         node->aa_node.aan_parent->aa_node.aan_left = leaf;
233                 } else {
234                         node->aa_node.aan_parent->aa_node.aan_right = leaf;
235                 }
236                 leaf->aa_node.aan_parent = node->aa_node.aan_parent;
237                 node->aa_node.aan_left->aa_node.aan_parent = leaf;
238                 leaf->aa_node.aan_left = node->aa_node.aan_left;
239
240                 node->aa_node.aan_right->aa_node.aan_parent = leaf;
241                 leaf->aa_node.aan_right = node->aa_node.aan_right;
242
243                 leaf->aa_node.aan_level = node->aa_node.aan_level;
244         }
245         while(parent!=B_AA_ROOT_NODE(tree)) {
246                 if(parent->aa_node.aan_level > B_AA_NODE_LEVEL(parent->aa_node.aan_left)+1) {
247                         parent->aa_node.aan_level--;
248                         if(baat_split(tree, parent)) {
249                                 if(baat_split(tree, parent)) {
250                                         baat_skew(parent->aa_node.aan_parent->aa_node.aan_parent);
251                                         break;
252                                 }
253                         }
254                         parent = parent->aa_node.aan_parent;
255                 } else if(parent->aa_node.aan_level <= B_AA_NODE_LEVEL(parent->aa_node.aan_right)+1) {
256                         break;
257                 } else {
258                         baat_skew(parent);
259                         if(parent->aa_node.aan_level > parent->aa_node.aan_parent->aa_node.aan_level) {
260                                 baat_skew(parent);
261                                 baat_split(tree, parent->aa_node.aan_parent->aa_node.aan_parent);
262                                 break;
263                         }
264                         parent = parent->aa_node.aan_parent->aa_node.aan_parent;
265                 }
266         }
267     return;
268}
269
Note: See TracBrowser for help on using the repository browser.