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
55CaseNode* 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
72void 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
83void 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
95int 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
135unsigned 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