1 | /*****************************************************************************/ |
2 | /* */ |
3 | /* casenode.c */ |
4 | /* */ |
5 | /* Node for the tree that is generated for a switch statement */ |
6 | /* */ |
7 | /* */ |
8 | /* */ |
9 | /* (C) 2001 Ullrich von Bassewitz */ |
10 | /* Wacholderweg 14 */ |
11 | /* D-70597 Stuttgart */ |
12 | /* EMail: uz@cc65.org */ |
13 | /* */ |
14 | /* */ |
15 | /* This software is provided 'as-is', without any expressed or implied */ |
16 | /* warranty. In no event will the authors be held liable for any damages */ |
17 | /* arising from the use of this software. */ |
18 | /* */ |
19 | /* Permission is granted to anyone to use this software for any purpose, */ |
20 | /* including commercial applications, and to alter it and redistribute it */ |
21 | /* freely, subject to the following restrictions: */ |
22 | /* */ |
23 | /* 1. The origin of this software must not be misrepresented; you must not */ |
24 | /* claim that you wrote the original software. If you use this software */ |
25 | /* in a product, an acknowledgment in the product documentation would be */ |
26 | /* appreciated but is not required. */ |
27 | /* 2. Altered source versions must be plainly marked as such, and must not */ |
28 | /* be misrepresented as being the original software. */ |
29 | /* 3. This notice may not be removed or altered from any source */ |
30 | /* distribution. */ |
31 | /* */ |
32 | /*****************************************************************************/ |
33 | |
34 | |
35 | |
36 | #include <limits.h> |
37 | |
38 | /* common */ |
39 | #include "coll.h" |
40 | #include "xmalloc.h" |
41 | |
42 | /* cc65 */ |
43 | #include "asmlabel.h" |
44 | #include "error.h" |
45 | #include "casenode.h" |
46 | |
47 | |
48 | |
49 | /*****************************************************************************/ |
50 | /* Code */ |
51 | /*****************************************************************************/ |
52 | |
53 | |
54 | |
55 | CaseNode* NewCaseNode (unsigned char Value) |
56 | /* Create and initialize a new CaseNode */ |
57 | { |
58 | /* Allocate memory */ |
59 | CaseNode* N = xmalloc (sizeof (CaseNode)); |
60 | |
61 | /* Initialize the fields */ |
62 | N->Value = Value; |
63 | N->Label = 0; |
64 | N->Nodes = 0; |
65 | |
66 | /* Return the new node */ |
67 | return N; |
68 | } |
69 | |
70 | |
71 | |
72 | void FreeCaseNode (CaseNode* N) |
73 | /* Delete a case node plus all sub nodes */ |
74 | { |
75 | if (N->Nodes) { |
76 | FreeCaseNodeColl (N->Nodes); |
77 | } |
78 | xfree (N); |
79 | } |
80 | |
81 | |
82 | |
83 | void FreeCaseNodeColl (Collection* Nodes) |
84 | /* Free a collection of case nodes */ |
85 | { |
86 | unsigned I; |
87 | for (I = 0; I < CollCount (Nodes); ++I) { |
88 | FreeCaseNode (CollAtUnchecked (Nodes, I)); |
89 | } |
90 | FreeCollection (Nodes); |
91 | } |
92 | |
93 | |
94 | |
95 | int SearchCaseNode (const Collection* Nodes, unsigned char Key, int* Index) |
96 | /* Search for a node in the given collection. If the node has been found, |
97 | ** set Index to the index of the node and return true. If the node was not |
98 | ** found, set Index the the insertion position of the node and return |
99 | ** false. |
100 | */ |
101 | { |
102 | /* Do a binary search */ |
103 | int First = 0; |
104 | int Last = CollCount (Nodes) - 1; |
105 | int S = 0; |
106 | |
107 | while (First <= Last) { |
108 | |
109 | /* Set current to mid of range */ |
110 | int Current = (Last + First) / 2; |
111 | |
112 | /* Get the entry from this position */ |
113 | const CaseNode* N = CollConstAt (Nodes, Current); |
114 | |
115 | /* Compare the values */ |
116 | if (N->Value < Key) { |
117 | First = Current + 1; |
118 | } else { |
119 | Last = Current - 1; |
120 | if (N->Value == Key) { |
121 | /* Found. We cannot have duplicates, so end the search here. */ |
122 | S = 1; |
123 | First = Current; |
124 | } |
125 | } |
126 | |
127 | } |
128 | |
129 | *Index = First; |
130 | return S; |
131 | } |
132 | |
133 | |
134 | |
135 | unsigned InsertCaseValue (Collection* Nodes, unsigned long Val, unsigned Depth) |
136 | /* Insert a new case value into a CaseNode tree with the given depth. Return |
137 | ** the code label for the value. |
138 | */ |
139 | { |
140 | CaseNode* N = 0; |
141 | unsigned CaseLabel = GetLocalLabel (); /* Code label */ |
142 | |
143 | while (Depth--) { |
144 | |
145 | int Index; |
146 | |
147 | /* Get the key */ |
148 | unsigned char Key = (Val >> (Depth * CHAR_BIT)) & 0xFF; |
149 | |
150 | /* Search for the node in the collection */ |
151 | if (SearchCaseNode (Nodes, Key, &Index) == 0) { |
152 | |
153 | /* Node not found - insert one */ |
154 | N = NewCaseNode (Key); |
155 | CollInsert (Nodes, N, Index); |
156 | |
157 | /* If this is not the last round, create the collection for |
158 | ** the subnodes, otherwise get a label for the code. |
159 | */ |
160 | if (Depth > 0) { |
161 | N->Nodes = NewCollection (); |
162 | } else { |
163 | N->Label = CaseLabel; |
164 | } |
165 | |
166 | } else { |
167 | /* Node found, get it */ |
168 | N = CollAt (Nodes, Index); |
169 | |
170 | /* If this is the last round and we found a node, we have a |
171 | ** duplicate case label in a switch. |
172 | */ |
173 | if (Depth == 0) { |
174 | Error ("Duplicate case label" ); |
175 | } |
176 | } |
177 | |
178 | /* Get the collection from the node for the next round. */ |
179 | Nodes = N->Nodes; |
180 | } |
181 | |
182 | /* Return the label of the node we found/created */ |
183 | return CaseLabel; |
184 | } |
185 | |