Commit | Line | Data |
---|---|---|
86530b38 AT |
1 | // ========== Copyright Header Begin ========================================== |
2 | // | |
3 | // OpenSPARC T2 Processor File: XactorBinTree.vr | |
4 | // Copyright (C) 1995-2007 Sun Microsystems, Inc. All Rights Reserved | |
5 | // 4150 Network Circle, Santa Clara, California 95054, U.S.A. | |
6 | // | |
7 | // * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | |
8 | // | |
9 | // This program is free software; you can redistribute it and/or modify | |
10 | // it under the terms of the GNU General Public License as published by | |
11 | // the Free Software Foundation; version 2 of the License. | |
12 | // | |
13 | // This program is distributed in the hope that it will be useful, | |
14 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | // GNU General Public License for more details. | |
17 | // | |
18 | // You should have received a copy of the GNU General Public License | |
19 | // along with this program; if not, write to the Free Software | |
20 | // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
21 | // | |
22 | // For the avoidance of doubt, and except that if any non-GPL license | |
23 | // choice is available it will apply instead, Sun elects to use only | |
24 | // the General Public License version 2 (GPLv2) at this time for any | |
25 | // software where a choice of GPL license versions is made | |
26 | // available with the language indicating that GPLv2 or any later version | |
27 | // may be used, or where a choice of which version of the GPL is applied is | |
28 | // otherwise unspecified. | |
29 | // | |
30 | // Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, | |
31 | // CA 95054 USA or visit www.sun.com if you need additional information or | |
32 | // have any questions. | |
33 | // | |
34 | // ========== Copyright Header End ============================================ | |
35 | #include <vera_defines.vrh> | |
36 | #include "XactorUtilities.vrh" | |
37 | #include "XactorBasePacket.vrh" | |
38 | #include "XactorBaseExpectDataStruct.vrh" | |
39 | #include "XactorDefines.vri" | |
40 | #include "XactorComponentsDefines.vri" | |
41 | ||
42 | typedef class TreeNode; | |
43 | ||
44 | // This class declares and implements the node used by the binary tree data structure. | |
45 | class TreeNode { | |
46 | ||
47 | event RemoveEvents[XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS]; // Removed is an event flag that will be | |
48 | // triggered when the node is removed | |
49 | XactorBasePacket Item; // Xactor Packet | |
50 | TreeNode Left; // Pointer to the left node | |
51 | TreeNode Right; // Pointer to the right node | |
52 | TreeNode Parent; // Pointer to the parent node | |
53 | ||
54 | task new (XactorBasePacket i, | |
55 | var event e[XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS] | |
56 | ) { | |
57 | ||
58 | integer EventCnt; | |
59 | ||
60 | for(EventCnt = 0; EventCnt <= XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS - 1; EventCnt++) { | |
61 | RemoveEvents[EventCnt] = e[EventCnt]; | |
62 | } | |
63 | ||
64 | Item = i; | |
65 | Left = null; | |
66 | Right = null; | |
67 | Parent = null; | |
68 | } | |
69 | } | |
70 | ||
71 | // This is the class that declares and implements the binary tree | |
72 | // data structure. | |
73 | class XactorBinTree extends XactorBaseExpectDataStruct { | |
74 | ||
75 | // Head node of the binary tree | |
76 | protected TreeNode Head; | |
77 | ||
78 | task new (); | |
79 | ||
80 | virtual protected task AssignEvent(var event Dest[XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS], | |
81 | var event Src[XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS] | |
82 | ); | |
83 | ||
84 | // Local method. Will search Key within the binary tree. | |
85 | virtual protected function TreeNode WCTreeSearch(TreeNode x, | |
86 | XactorBasePacket Key | |
87 | ); | |
88 | ||
89 | // Local method. Will search Key within the binary tree. | |
90 | virtual protected function TreeNode TreeSearch(TreeNode x, | |
91 | XactorBasePacket Key | |
92 | ); | |
93 | ||
94 | // Local method. Will search Key within the binary tree. | |
95 | virtual protected function TreeNode RefTreeSearch(TreeNode x, | |
96 | XactorBasePacket Key | |
97 | ); | |
98 | ||
99 | // Local method. Will return the left most node of the tree (the one | |
100 | // with the minimum value) | |
101 | virtual protected function TreeNode TreeMin(TreeNode x); | |
102 | ||
103 | // Local method. Returns the successor to node x | |
104 | virtual protected function TreeNode TreeSuccessor(TreeNode x); | |
105 | ||
106 | // Public method. Inserts a new node with the specified values. | |
107 | virtual task Insert (XactorBasePacket Item, | |
108 | var event e[XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS] | |
109 | ); | |
110 | ||
111 | virtual protected task DeleteNode (var TreeNode z); | |
112 | ||
113 | // Checks if there are duplicated packets after a node is deleted. | |
114 | // No Wildcards | |
115 | virtual protected task CheckDuplicatedExpects (XactorBasePacket Key, | |
116 | TreeNode NodePtr | |
117 | ); | |
118 | ||
119 | // Public method. Deletes a node with the specified values and returns | |
120 | // Success = 1 if the node was found and deleted and Success = 0 otherwise. | |
121 | virtual task Delete (XactorBasePacket Key, | |
122 | var bit Success | |
123 | ); | |
124 | ||
125 | // Public method. Deletes a node with the specified values and returns | |
126 | // Success = 1 if the node was found and deleted and Success = 0 otherwise. | |
127 | virtual task RefDelete (XactorBasePacket Key, | |
128 | var bit Success | |
129 | ); | |
130 | ||
131 | // Checks for duplicated expects after a node is deleted | |
132 | // Use of wildcards | |
133 | virtual protected task CheckWCDuplicatedExpects (XactorBasePacket Key, | |
134 | TreeNode NodePtr | |
135 | ); | |
136 | ||
137 | // Using Wildcards, deletes first node that match Key | |
138 | virtual task WildCardDelete1 (XactorBasePacket Key, | |
139 | var bit Success | |
140 | ); | |
141 | ||
142 | // Local method. Will do and inorder traversal of the binary tree | |
143 | // and will return the number of nodes through Counter | |
144 | virtual protected task InorderCount(TreeNode Node, | |
145 | var integer Counter | |
146 | ); | |
147 | ||
148 | // Public method. Will return the number of nodes in the binary tree. | |
149 | virtual function integer CountNodes(); | |
150 | ||
151 | // Local method. will do an inorder walk of the binary tree and will | |
152 | // print every node. Each "compressed" expected value is decoded by | |
153 | // a packet object. Once decoded, each field will be stored within the | |
154 | // same packet and printed. | |
155 | virtual protected task InorderPrint(TreeNode Node); | |
156 | ||
157 | // Public method. Calls InorderPrint to print the nodes within the | |
158 | // binary tree. | |
159 | virtual task PrintNodes(); | |
160 | ||
161 | // Public method. Returns 1 if Item is within the binary tree and | |
162 | // 0 otherwise. Accepts "wildcards" | |
163 | virtual function bit InStructure(XactorBasePacket Item); | |
164 | ||
165 | // Public method. Returns 1 if the binary tree is empty and 0 otherwise. | |
166 | virtual function bit Empty(); | |
167 | ||
168 | // Local method. Inorder walk of the binary tree. It triggers the event | |
169 | // of every node. | |
170 | virtual protected task InorderReset(TreeNode Node); | |
171 | ||
172 | // Public method. Calls InorderReset and after that, it deletes the complete | |
173 | // binary tree. | |
174 | virtual task Reset(); | |
175 | ||
176 | } | |
177 | ||
178 | //////////////// | |
179 | // Definitions | |
180 | //////////////// | |
181 | ||
182 | task XactorBinTree::new () { | |
183 | Head = null; | |
184 | } | |
185 | ||
186 | task XactorBinTree::AssignEvent(var event Dest[XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS], | |
187 | var event Src[XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS] | |
188 | ) { | |
189 | integer EventCnt; | |
190 | ||
191 | for(EventCnt = 0; EventCnt <= XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS - 1; EventCnt++) { | |
192 | Dest[EventCnt] = Src[EventCnt]; | |
193 | } | |
194 | } | |
195 | ||
196 | // Local method. Will search Key within the binary tree. | |
197 | function TreeNode XactorBinTree::WCTreeSearch(TreeNode x, | |
198 | XactorBasePacket Key | |
199 | ) { | |
200 | if((x == null) || (x.Item.PktCompare("=?=", Key))) | |
201 | WCTreeSearch = x; | |
202 | else { | |
203 | if(x.Item.PktCompare(">", Key)) | |
204 | WCTreeSearch = WCTreeSearch(x.Left, Key); | |
205 | else | |
206 | WCTreeSearch = WCTreeSearch(x.Right, Key); | |
207 | } | |
208 | } | |
209 | ||
210 | // Local method. Will search Key within the binary tree. | |
211 | function TreeNode XactorBinTree::TreeSearch(TreeNode x, | |
212 | XactorBasePacket Key | |
213 | ) { | |
214 | if((x == null) || (x.Item.PktCompare("===", Key))) | |
215 | TreeSearch = x; | |
216 | else { | |
217 | if(x.Item.PktCompare(">", Key)) | |
218 | TreeSearch = TreeSearch(x.Left, Key); | |
219 | else | |
220 | TreeSearch = TreeSearch(x.Right, Key); | |
221 | } | |
222 | } | |
223 | ||
224 | // Local method. Will search Key within the binary tree. | |
225 | function TreeNode XactorBinTree::RefTreeSearch(TreeNode x, | |
226 | XactorBasePacket Key | |
227 | ) { | |
228 | if((x == null) || (x.Item === Key)) | |
229 | RefTreeSearch = x; | |
230 | else { | |
231 | if(x.Item.PktCompare(">", Key)) | |
232 | RefTreeSearch = RefTreeSearch(x.Left, Key); | |
233 | else | |
234 | RefTreeSearch = RefTreeSearch(x.Right, Key); | |
235 | } | |
236 | } | |
237 | ||
238 | // Local method. Will return the left most node of the tree (the one | |
239 | // with the minimum value) | |
240 | function TreeNode XactorBinTree::TreeMin(TreeNode x) { | |
241 | while(x.Left != null) | |
242 | x = x.Left; | |
243 | TreeMin = x; | |
244 | } | |
245 | ||
246 | // Local method. Returns the successor to node x | |
247 | function TreeNode XactorBinTree::TreeSuccessor(TreeNode x) { | |
248 | TreeNode y; | |
249 | ||
250 | if(x.Right != null) | |
251 | TreeSuccessor = TreeMin(x.Right); | |
252 | else { | |
253 | y = x.Parent; | |
254 | while((y != null) && (x == y.Right)) { | |
255 | x = y; | |
256 | y = y.Parent; | |
257 | } | |
258 | TreeSuccessor = y; | |
259 | } | |
260 | } | |
261 | ||
262 | // Public method. Inserts a new node with the specified values. | |
263 | task XactorBinTree::Insert (XactorBasePacket Item, | |
264 | var event e[XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS] | |
265 | ) { | |
266 | TreeNode x; | |
267 | TreeNode y; | |
268 | TreeNode z; | |
269 | ||
270 | z = new(Item, e); | |
271 | y = null; | |
272 | x = Head; | |
273 | ||
274 | if(Head != null) | |
275 | while(x != null) { | |
276 | y = x; | |
277 | if((x.Item.PktCompare("<", z.Item)) || (x.Item.PktCompare("=?=", z.Item))) { | |
278 | if(x.Item.PktCompare("=?=", z.Item)) { | |
279 | x.Item.PktDisplay(RTYP_XACTOR_FMWORK_DUP_EXPECT_ERR, "Posting a duplicated Expect"); | |
280 | } | |
281 | x = x.Right; | |
282 | } | |
283 | else { | |
284 | x = x.Left; | |
285 | } | |
286 | } | |
287 | ||
288 | z.Parent = y; | |
289 | if(y == null) | |
290 | Head = z; | |
291 | else { | |
292 | if((y.Item.PktCompare("<", z.Item)) || (y.Item.PktCompare("=?=", z.Item))) | |
293 | y.Right = z; | |
294 | else | |
295 | y.Left = z; | |
296 | } | |
297 | } | |
298 | ||
299 | task XactorBinTree::DeleteNode (var TreeNode z) { | |
300 | ||
301 | TreeNode y; | |
302 | TreeNode x; | |
303 | ||
304 | if((z.Left == null) || (z.Right == null)) | |
305 | y = z; | |
306 | else | |
307 | y = TreeSuccessor(z); | |
308 | ||
309 | if(y.Left != null) | |
310 | x = y.Left; | |
311 | else | |
312 | x = y.Right; | |
313 | ||
314 | if(x != null) | |
315 | x.Parent = y.Parent; | |
316 | ||
317 | if(y.Parent == null) | |
318 | Head = x; | |
319 | else { | |
320 | if(y == y.Parent.Left) | |
321 | y.Parent.Left = x; | |
322 | else | |
323 | y.Parent.Right = x; | |
324 | } | |
325 | if(y != z) { | |
326 | AssignEvent(z.RemoveEvents, y.RemoveEvents); | |
327 | z.Item = y.Item; | |
328 | } | |
329 | } | |
330 | ||
331 | // Checks if there are duplicated packets after a node is deleted. | |
332 | // No Wildcards | |
333 | task XactorBinTree::CheckDuplicatedExpects (XactorBasePacket Key, | |
334 | TreeNode NodePtr | |
335 | ) { | |
336 | TreeNode z; | |
337 | ||
338 | z = TreeSearch(NodePtr, Key); | |
339 | ||
340 | if(z !== null) { | |
341 | z.Item.PktDisplay(RTYP_XACTOR_FMWORK_SAMPLED_DUP_XACTION_ERR, "Sampled Transaction satisfies duplicated Expect"); | |
342 | if(z.Right != null) { | |
343 | CheckDuplicatedExpects (Key, | |
344 | z.Right | |
345 | ); | |
346 | } | |
347 | } | |
348 | } | |
349 | ||
350 | // Public method. Deletes a node with the specified values and returns | |
351 | // Success = 1 if the node was found and deleted and Success = 0 otherwise. | |
352 | task XactorBinTree::Delete (XactorBasePacket Key, | |
353 | var bit Success | |
354 | ) { | |
355 | TreeNode z; | |
356 | ||
357 | z = TreeSearch(Head, Key); | |
358 | ||
359 | if(z !== null) { | |
360 | Key.SetID(z.Item.GetID()); | |
361 | if(z.Right != null) | |
362 | CheckDuplicatedExpects(Key, | |
363 | z.Right | |
364 | ); | |
365 | trigger(ON, z.RemoveEvents[XACT_COMP_EXPECT_REMOVED_EVENT]); // Remove event | |
366 | trigger(ON, z.RemoveEvents[XACT_COMP_EXPECT_REMOVED_BY_XACTOR_EVENT]); // Removed by xactor | |
367 | ||
368 | Success = 1'b1; | |
369 | DeleteNode(z); | |
370 | } | |
371 | else { | |
372 | Success = 1'b0; | |
373 | } | |
374 | } | |
375 | ||
376 | // Public method. Deletes a node with the specified values and returns | |
377 | // Success = 1 if the node was found and deleted and Success = 0 otherwise. | |
378 | task XactorBinTree::RefDelete (XactorBasePacket Key, | |
379 | var bit Success | |
380 | ) { | |
381 | TreeNode z; | |
382 | ||
383 | z = RefTreeSearch(Head, Key); | |
384 | ||
385 | if(z !== null) { | |
386 | Key.SetID(z.Item.GetID()); | |
387 | ||
388 | trigger(ON, z.RemoveEvents[XACT_COMP_EXPECT_REMOVED_EVENT]); // Remove event | |
389 | trigger(ON, z.RemoveEvents[XACT_COMP_EXPECT_REMOVED_BY_USER_EVENT]); // Removed by user | |
390 | ||
391 | Success = 1'b1; | |
392 | DeleteNode(z); | |
393 | } | |
394 | else { | |
395 | Success = 1'b0; | |
396 | } | |
397 | } | |
398 | ||
399 | ||
400 | // Checks for duplicated expects after a node is deleted | |
401 | // Use of wildcards | |
402 | task XactorBinTree::CheckWCDuplicatedExpects (XactorBasePacket Key, | |
403 | TreeNode NodePtr | |
404 | ) { | |
405 | TreeNode z; | |
406 | ||
407 | z = WCTreeSearch(NodePtr, Key); | |
408 | ||
409 | if(z !== null) { | |
410 | z.Item.PktDisplay(RTYP_XACTOR_FMWORK_SAMPLED_DUP_XACTION_ERR, "Sampled Transaction satisfies duplicated Expect"); | |
411 | if(z.Right !== null) { | |
412 | CheckWCDuplicatedExpects (Key, | |
413 | z.Right | |
414 | ); | |
415 | } | |
416 | } | |
417 | } | |
418 | ||
419 | // Using Wildcards, deletes first node that match Key | |
420 | task XactorBinTree::WildCardDelete1 (XactorBasePacket Key, | |
421 | var bit Success | |
422 | ) { | |
423 | TreeNode z; | |
424 | ||
425 | z = WCTreeSearch(Head, Key); | |
426 | ||
427 | if(z != null) { | |
428 | Key.SetID(z.Item.GetID()); | |
429 | z.Item.PktCopy(Key); // Copy contents of sampled packet to expected packet | |
430 | if(z.Right != null) | |
431 | CheckWCDuplicatedExpects(Key, z.Right); | |
432 | ||
433 | trigger(ON, z.RemoveEvents[XACT_COMP_EXPECT_REMOVED_EVENT]); // Remove event | |
434 | trigger(ON, z.RemoveEvents[XACT_COMP_EXPECT_REMOVED_BY_XACTOR_EVENT]); // Removed by xactor | |
435 | ||
436 | Success = 1'b1; | |
437 | DeleteNode(z); | |
438 | } | |
439 | else | |
440 | Success = 1'b0; | |
441 | } | |
442 | ||
443 | // Local method. Will do and inorder traversal of the binary tree | |
444 | // and will return the number of nodes through Counter | |
445 | task XactorBinTree::InorderCount(TreeNode Node, | |
446 | var integer Counter | |
447 | ) { | |
448 | if(Node != null) { | |
449 | InorderCount(Node.Left, Counter); | |
450 | Counter++; | |
451 | InorderCount(Node.Right, Counter); | |
452 | } | |
453 | } | |
454 | ||
455 | // Public method. Will return the number of nodes in the binary tree. | |
456 | function integer XactorBinTree::CountNodes() { | |
457 | integer Counter = 0; | |
458 | ||
459 | if(Head != null) | |
460 | InorderCount(Head, Counter); | |
461 | ||
462 | CountNodes = Counter; | |
463 | } | |
464 | ||
465 | // Local method. will do an inorder walk of the binary tree and will | |
466 | // print every node. Each "compressed" expected value is decoded by | |
467 | // a packet object. Once decoded, each field will be stored within the | |
468 | // same packet and printed. | |
469 | task XactorBinTree::InorderPrint(TreeNode Node | |
470 | ) { | |
471 | if(Node != null) { | |
472 | InorderPrint(Node.Left); | |
473 | Node.Item.PktDisplay(RTYP_INFO, "Dump Expect List"); | |
474 | InorderPrint(Node.Right); | |
475 | } | |
476 | } | |
477 | ||
478 | // Public method. Calls InorderPrint to print the nodes within the | |
479 | // binary tree. | |
480 | task XactorBinTree::PrintNodes() { | |
481 | if(Head != null) | |
482 | InorderPrint(Head); | |
483 | } | |
484 | ||
485 | // Public method. Returns 1 if Item is within the binary tree and | |
486 | // 0 otherwise. Accepts "wildcards" | |
487 | function bit XactorBinTree::InStructure (XactorBasePacket Item | |
488 | ) { | |
489 | TreeNode x; | |
490 | ||
491 | x = TreeSearch(Head, Item); | |
492 | ||
493 | if(x != null) | |
494 | InStructure = 1'b1; | |
495 | else | |
496 | InStructure = 1'b0; | |
497 | } | |
498 | ||
499 | // Public method. Returns 1 if the binary tree is empty and 0 otherwise. | |
500 | function bit XactorBinTree::Empty() { | |
501 | if (Head == null) | |
502 | Empty = 1'b1; | |
503 | else | |
504 | Empty = 1'b0; | |
505 | } | |
506 | ||
507 | // Local method. Inorder walk of the binary tree. It triggers the event | |
508 | // of every node. | |
509 | task XactorBinTree::InorderReset(TreeNode Node | |
510 | ) { | |
511 | if(Node != null) { | |
512 | InorderReset(Node.Left); | |
513 | trigger(ON, Node.RemoveEvents[XACT_COMP_EXPECT_REMOVED_EVENT]); // Trigger remove event | |
514 | trigger(ON, Node.RemoveEvents[XACT_COMP_EXPECT_REMOVED_BY_USER_EVENT]); // Trigger removed | |
515 | // by user event | |
516 | InorderReset(Node.Right); | |
517 | } | |
518 | } | |
519 | ||
520 | // Public method. Calls InorderReset and after that, it deletes the complete | |
521 | // binary tree. | |
522 | task XactorBinTree::Reset() { | |
523 | if(Head != null) | |
524 | InorderReset(Head); | |
525 | ||
526 | Head = null; | |
527 | } | |
528 | ||
529 | ||
530 | ||
531 | ||
532 | ||
533 | ||
534 | ||
535 | ||
536 | ||
537 |