Commit | Line | Data |
---|---|---|
86530b38 AT |
1 | /* |
2 | * ========== Copyright Header Begin ========================================== | |
3 | * | |
4 | * OpenSPARC T2 Processor File: utility.c | |
5 | * Copyright (C) 1995-2007 Sun Microsystems, Inc. All Rights Reserved | |
6 | * 4150 Network Circle, Santa Clara, California 95054, U.S.A. | |
7 | * | |
8 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | |
9 | * | |
10 | * This program is free software; you can redistribute it and/or modify | |
11 | * it under the terms of the GNU General Public License as published by | |
12 | * the Free Software Foundation; version 2 of the License. | |
13 | * | |
14 | * This program is distributed in the hope that it will be useful, | |
15 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
16 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
17 | * GNU General Public License for more details. | |
18 | * | |
19 | * You should have received a copy of the GNU General Public License | |
20 | * along with this program; if not, write to the Free Software | |
21 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
22 | * | |
23 | * For the avoidance of doubt, and except that if any non-GPL license | |
24 | * choice is available it will apply instead, Sun elects to use only | |
25 | * the General Public License version 2 (GPLv2) at this time for any | |
26 | * software where a choice of GPL license versions is made | |
27 | * available with the language indicating that GPLv2 or any later version | |
28 | * may be used, or where a choice of which version of the GPL is applied is | |
29 | * otherwise unspecified. | |
30 | * | |
31 | * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, | |
32 | * CA 95054 USA or visit www.sun.com if you need additional information or | |
33 | * have any questions. | |
34 | * | |
35 | * | |
36 | * ========== Copyright Header End ============================================ | |
37 | */ | |
38 | #include "utility.h" | |
39 | ||
40 | ||
41 | l2warm_avl_node_ptr l2warm_search_node(l2warm_avl_node_ptr* t_ptr, long long* addr); | |
42 | ||
43 | /*------------------------------------------------------------------------------- | |
44 | create new avl_node. | |
45 | state bit : | |
46 | 0 dirty, | |
47 | 1 valid | |
48 | 2 clean | |
49 | --------------------------------------------------------------------------------*/ | |
50 | l2warm_avl_node_ptr l2warm_create_avl_node(long long addr){ | |
51 | l2warm_avl_node_ptr n_ptr; | |
52 | n_ptr = (l2warm_avl_node_ptr)malloc(sizeof(struct l2warm_avl_node)); | |
53 | if(n_ptr != 0){ | |
54 | n_ptr->state = 2; | |
55 | n_ptr->addr = addr; | |
56 | n_ptr->balance = 0; | |
57 | n_ptr->leftPtr = 0; | |
58 | n_ptr->rightPtr= 0; | |
59 | } | |
60 | else { | |
61 | io_printf("Out of memory\n"); | |
62 | tf_dofinish(); | |
63 | } | |
64 | return n_ptr; | |
65 | } | |
66 | ||
67 | /*------------------------------------------------------------------------------- | |
68 | check difference. | |
69 | --------------------------------------------------------------------------------*/ | |
70 | int l2warm_difference(l2warm_avl_node_ptr t_ptr){ | |
71 | int left, right; | |
72 | left = -1;right = -1; | |
73 | ||
74 | if(t_ptr == 0)return 0; | |
75 | if(t_ptr->leftPtr != 0)left = t_ptr->leftPtr->balance; | |
76 | if(t_ptr->rightPtr != 0)right = t_ptr->rightPtr->balance; | |
77 | return (left - right); | |
78 | } | |
79 | /*------------------------------------------------------------------------------- | |
80 | rotate nodes pointed to by pivotptr. | |
81 | pivotptr: leftPtr. | |
82 | --------------------------------------------------------------------------------*/ | |
83 | void l2warm_rotate_right(l2warm_avl_node_ptr* pivot_ptr){ | |
84 | l2warm_avl_node_ptr t_ptr; | |
85 | ||
86 | if((*pivot_ptr) != 0){ | |
87 | if((*pivot_ptr)->leftPtr != 0){ | |
88 | t_ptr = (*pivot_ptr)->leftPtr; | |
89 | (*pivot_ptr)->leftPtr = t_ptr->rightPtr; | |
90 | t_ptr->rightPtr = *pivot_ptr; | |
91 | *pivot_ptr = t_ptr; // t_ptr becomes new root of this whole subtree. | |
92 | } | |
93 | } | |
94 | } | |
95 | /*------------------------------------------------------------------------------- | |
96 | rotate nodes pointed to by pivotptr. | |
97 | pivotptr: leftPtr. | |
98 | --------------------------------------------------------------------------------*/ | |
99 | void l2warm_rotate_left(l2warm_avl_node_ptr* pivot_ptr){ | |
100 | l2warm_avl_node_ptr t_ptr; | |
101 | ||
102 | if((*pivot_ptr) != 0){ | |
103 | if((*pivot_ptr)->rightPtr != 0){ | |
104 | t_ptr = (*pivot_ptr)->rightPtr; | |
105 | (*pivot_ptr)->rightPtr = t_ptr->leftPtr; | |
106 | t_ptr->leftPtr = *pivot_ptr; | |
107 | *pivot_ptr = t_ptr; // t_ptr becomes new root of this whole subtree. | |
108 | } | |
109 | } | |
110 | } | |
111 | /*------------------------------------------------------------------------------- | |
112 | rotate nodes pointed to by pivotptr. | |
113 | pivotptr: leftPtr. | |
114 | --------------------------------------------------------------------------------*/ | |
115 | void l2warm_balance_right(l2warm_avl_node_ptr* t_ptr){ | |
116 | ||
117 | if(l2warm_difference((*t_ptr)->rightPtr) == 0){ | |
118 | l2warm_rotate_left(&(*t_ptr)); | |
119 | (*t_ptr)->balance--; | |
120 | (*t_ptr)->leftPtr->balance++; | |
121 | ||
122 | } | |
123 | else if(l2warm_difference((*t_ptr)->rightPtr) < 0){ | |
124 | l2warm_rotate_left(&(*t_ptr)); | |
125 | (*t_ptr)->leftPtr->balance -= 2; | |
126 | } | |
127 | else{ | |
128 | l2warm_rotate_right(&(*t_ptr)->rightPtr); | |
129 | l2warm_rotate_left(&(*t_ptr)); | |
130 | (*t_ptr)->balance++; | |
131 | (*t_ptr)->leftPtr->balance -= 2; | |
132 | (*t_ptr)->rightPtr->balance--; | |
133 | } | |
134 | } | |
135 | /*------------------------------------------------------------------------------- | |
136 | rotate nodes pointed to by pivotptr. | |
137 | pivotptr: rightPtr. | |
138 | --------------------------------------------------------------------------------*/ | |
139 | void l2warm_balance_left(l2warm_avl_node_ptr* t_ptr){ | |
140 | ||
141 | if(l2warm_difference((*t_ptr)->leftPtr) == 0){ | |
142 | l2warm_rotate_right(&(*t_ptr)); | |
143 | (*t_ptr)->balance--; | |
144 | (*t_ptr)->rightPtr->balance++; | |
145 | ||
146 | } | |
147 | else if(l2warm_difference((*t_ptr)->leftPtr) < 0){ | |
148 | l2warm_rotate_right(&(*t_ptr)); | |
149 | (*t_ptr)->rightPtr->balance -= 2; | |
150 | } | |
151 | else{ | |
152 | l2warm_rotate_left(&(*t_ptr)->leftPtr); | |
153 | l2warm_rotate_right(&(*t_ptr)); | |
154 | (*t_ptr)->balance++; | |
155 | (*t_ptr)->rightPtr->balance -= 2; | |
156 | (*t_ptr)->leftPtr->balance--; | |
157 | } | |
158 | } | |
159 | /*------------------------------------------------------------------------------- | |
160 | update balance. | |
161 | --------------------------------------------------------------------------------*/ | |
162 | void l2warm_fixFB(l2warm_avl_node_ptr t_ptr){ | |
163 | int left, right; | |
164 | left = -1;right = -1; | |
165 | ||
166 | if(t_ptr->leftPtr != 0)left = t_ptr->leftPtr->balance; | |
167 | if(t_ptr->rightPtr != 0)right = t_ptr->rightPtr->balance; | |
168 | if(left > right)t_ptr->balance = left + 1; | |
169 | else t_ptr->balance = right + 1; | |
170 | } | |
171 | /*------------------------------------------------------------------------------- | |
172 | write data into memory. | |
173 | --------------------------------------------------------------------------------*/ | |
174 | int l2warm_insert_avl_node(l2warm_avl_node_ptr *t_ptr, long long* addr){ | |
175 | ||
176 | if((*t_ptr) == 0){ | |
177 | (*t_ptr) = l2warm_create_avl_node(*addr); // add new node to tree. | |
178 | ||
179 | if((*t_ptr) == 0){ | |
180 | io_printf("Error : Out of Memory\n"); | |
181 | tf_dofinish(); | |
182 | } | |
183 | } | |
184 | else if(*addr == (*t_ptr)->addr)return 1; | |
185 | else{ | |
186 | if(*addr < (*t_ptr)->addr)l2warm_insert_avl_node(&(*t_ptr)->leftPtr, addr); | |
187 | else l2warm_insert_avl_node(&(*t_ptr)->rightPtr, addr); | |
188 | l2warm_fixFB(*t_ptr); | |
189 | if(l2warm_difference(*t_ptr) > 1) l2warm_balance_left (&(*t_ptr)); | |
190 | else if(l2warm_difference(*t_ptr) < -1) l2warm_balance_right(&(*t_ptr)); | |
191 | } | |
192 | return 0; | |
193 | } | |
194 | /*------------------------------------------------------------------------------- | |
195 | search address on avl. | |
196 | --------------------------------------------------------------------------------*/ | |
197 | l2warm_avl_node_ptr l2warm_search_node(l2warm_avl_node_ptr* t_ptr, long long* addr){ | |
198 | ||
199 | if((*t_ptr)->addr == *addr){ | |
200 | return *t_ptr; | |
201 | } | |
202 | if((*t_ptr)->addr > *addr){ | |
203 | if((*t_ptr)->leftPtr == 0){ | |
204 | return 0; | |
205 | } | |
206 | return l2warm_search_node(&(*t_ptr)->leftPtr, addr); | |
207 | } | |
208 | else{ | |
209 | if((*t_ptr)->rightPtr == 0){ | |
210 | return 0; | |
211 | } | |
212 | return l2warm_search_node(&(*t_ptr)->rightPtr, addr); | |
213 | } | |
214 | } | |
215 |