1 pnkfelix 1.1.2.1 // AppelRegAllocStd.java, created Sat Jul 7 16:36:00 2001 by pnkfelix
2 pnkfelix 1.1.2.1 // Copyright (C) 2000 Felix S. Klock II <pnkfelix@mit.edu>
3 pnkfelix 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 pnkfelix 1.1.2.1 package harpoon.Analysis.Instr;
5 pnkfelix 1.1.2.1
6 pnkfelix 1.1.2.1 import harpoon.Backend.Generic.Code;
7 pnkfelix 1.1.2.1 import harpoon.IR.Assem.Instr;
8 pnkfelix 1.1.2.1 import harpoon.IR.Assem.InstrGroup;
9 pnkfelix 1.1.2.1
10 pnkfelix 1.1.2.1 import harpoon.Analysis.BasicBlock;
11 pnkfelix 1.1.2.1
12 pnkfelix 1.1.2.1 import harpoon.Temp.Temp;
13 pnkfelix 1.1.2.1 import harpoon.Util.Util;
14 pnkfelix 1.1.2.1
15 cananian 1.6 import java.util.AbstractCollection;
16 cananian 1.6 import java.util.Arrays;
17 pnkfelix 1.1.2.1 import java.util.Collection;
18 cananian 1.6 import java.util.Collections;
19 cananian 1.6 import java.util.HashMap;
20 cananian 1.6 import java.util.HashSet;
21 cananian 1.6 import java.util.Iterator;
22 cananian 1.6 import java.util.List;
23 cananian 1.6 import java.util.Map;
24 pnkfelix 1.1.2.1 import java.util.Set;
25 cananian 1.6
26 cananian 1.6 import net.cscott.jutil.FilterIterator;
27 cananian 1.6 import net.cscott.jutil.CombineIterator;
28 pnkfelix 1.1.2.1
29 pnkfelix 1.1.2.1 public class AppelRegAllocStd extends AppelRegAlloc {
30 pnkfelix 1.1.2.1 // Instr i -> Move m such m.instr = i
31 cananian 1.6 private Map<Instr,Move> instrToMove = new HashMap<Instr,Move>();
32 pnkfelix 1.1.2.1
33 pnkfelix 1.1.2.1 // Web w -> Listof Node
34 cananian 1.6 private Map<Web,List<Node>> webToNodes = new HashMap<Web,List<Node>>();
35 pnkfelix 1.1.2.1
36 pnkfelix 1.1.2.1 public AppelRegAllocStd(Code code) {
37 pnkfelix 1.1.2.1 super(code);
38 pnkfelix 1.1.2.1 }
39 pnkfelix 1.1.2.1
40 pnkfelix 1.1.2.1 protected void initializeSets() {
41 pnkfelix 1.1.2.1 super.initializeSets();
42 pnkfelix 1.1.2.1 webToNodes.clear();
43 pnkfelix 1.1.2.1 instrToMove.clear();
44 pnkfelix 1.1.2.1 }
45 pnkfelix 1.1.2.1
46 cananian 1.6 protected List<Node> nodesFor( Web web ) {
47 pnkfelix 1.1.2.1 if (CHECK_INV)
48 cananian 1.3.2.1 assert webToNodes.containsKey( web ) : "! should have nodes for "+web;
49 cananian 1.6 return webToNodes.get( web );
50 pnkfelix 1.1.2.1 }
51 pnkfelix 1.1.2.1
52 pnkfelix 1.1.2.1
53 pnkfelix 1.1.2.1 protected Node makePrecolored(Temp t) {
54 pnkfelix 1.1.2.1 Node n = super.makePrecolored(t);
55 cananian 1.6 webToNodes.put(n.web, Collections.singletonList(n));
56 pnkfelix 1.1.2.1 return n;
57 pnkfelix 1.1.2.1 }
58 pnkfelix 1.1.2.1
59 pnkfelix 1.1.2.1 protected void makeInitial(Temp t) {
60 pnkfelix 1.1.2.1 Set assns = rfi().getRegAssignments(t);
61 pnkfelix 1.1.2.1 List assn = (List) assns.iterator().next();
62 pnkfelix 1.1.2.1
63 cananian 1.6 for(Object webO : tempToWebs.getValues(t)){
64 cananian 1.6 Web web = (Web) webO;
65 pnkfelix 1.1.2.1 Node[] nodes = new Node[ assn.size() ];
66 pnkfelix 1.1.2.1 for(int i=0; i < nodes.length; i++) {
67 pnkfelix 1.1.2.1 Node n = new Node(initial, web);
68 pnkfelix 1.1.2.1 nodes[i] = n;
69 pnkfelix 1.1.2.1 }
70 pnkfelix 1.1.2.1 webToNodes.put( web, Arrays.asList( nodes ));
71 pnkfelix 1.1.2.1 }
72 pnkfelix 1.1.2.1 }
73 pnkfelix 1.1.2.1
74 pnkfelix 1.1.2.1 protected void checkDegreeInv() {
75 pnkfelix 1.1.2.1 // u isIn (simplifyWorklist \/ freezeWorklist \/ spillWorklist ) ==>
76 pnkfelix 1.1.2.1 // degree(u) = | adjList(u) /\ ( precolored \/ simplifyWorklist \/
77 pnkfelix 1.1.2.1 // freezeWorklist \/ spillWorklist ) |
78 pnkfelix 1.1.2.1 // ( tranlates to )
79 pnkfelix 1.1.2.1 // foreach u in (simplify U freeze U spill )
80 pnkfelix 1.1.2.1 // degree(u) = | {n | n isIn adjList(u) &&
81 pnkfelix 1.1.2.1 // n isIn precolored \/ simplify \/
82 pnkfelix 1.1.2.1 // freeze \/ spill } |
83 pnkfelix 1.1.2.1
84 pnkfelix 1.1.2.1 HashSet outerSeen = new HashSet();
85 pnkfelix 1.1.2.1
86 pnkfelix 1.1.2.1 NodeIter ni=combine(new NodeIter[]{simplify_worklist.iter(),
87 pnkfelix 1.1.2.1 freeze_worklist.iter(),
88 pnkfelix 1.1.2.1 spill_worklist.iter()});
89 pnkfelix 1.1.2.1 while( ni.hasNext() ) {
90 pnkfelix 1.1.2.1 Node u = ni.next();
91 pnkfelix 1.1.2.1
92 pnkfelix 1.1.2.1 if (CHECK_INV)
93 cananian 1.3.2.1 assert ! outerSeen.contains(u) : " already saw " + u;
94 pnkfelix 1.1.2.1
95 pnkfelix 1.1.2.1 outerSeen.add(u);
96 pnkfelix 1.1.2.1
97 pnkfelix 1.1.2.1 int deg = u.degree;
98 pnkfelix 1.1.2.1 for(NodeIter adj=adjacent(u); adj.hasNext();) {
99 pnkfelix 1.1.2.1 Node a = adj.next();
100 pnkfelix 1.1.2.1
101 pnkfelix 1.1.2.1 if( a.isPrecolored() ||
102 pnkfelix 1.1.2.1 a.isSimplifyWorkL() ||
103 pnkfelix 1.1.2.1 a.isFreezeWorkL() ||
104 pnkfelix 1.1.2.1 a.isSpillWorkL() ) {
105 pnkfelix 1.1.2.1 deg--;
106 pnkfelix 1.1.2.1 }
107 pnkfelix 1.1.2.1 }
108 cananian 1.3.2.1 assert deg == 0 : "degree inv. violated";
109 pnkfelix 1.1.2.1 }
110 pnkfelix 1.1.2.1 }
111 pnkfelix 1.1.2.1
112 pnkfelix 1.1.2.1 protected void buildInterferenceGraph() {
113 pnkfelix 1.1.2.1 for(Iterator bbs=bbFact.blocksIterator(); bbs.hasNext();) {
114 pnkfelix 1.1.2.1 BasicBlock bb = (BasicBlock) bbs.next();
115 pnkfelix 1.1.2.1 Set/*Node*/ live = liveOut(bb);
116 pnkfelix 1.1.2.1
117 pnkfelix 1.1.2.1 for(Instr i = lastStm(bb); !i.equals( firstStm(bb) ); i = pred(i)){
118 pnkfelix 1.1.2.1 if( i.isMove() ){
119 pnkfelix 1.1.2.1 live.removeAll( useCN( i ) );
120 pnkfelix 1.1.2.1 for( NodeIter ni = usedef(i); ni.hasNext(); ){
121 pnkfelix 1.1.2.1 Node n = ni.next();
122 pnkfelix 1.1.2.1 n.moves.add( moveFor(i) );
123 pnkfelix 1.1.2.1 }
124 pnkfelix 1.1.2.1 worklist_moves.add( moveFor(i) );
125 pnkfelix 1.1.2.1 }
126 pnkfelix 1.1.2.1
127 pnkfelix 1.1.2.1 live.addAll( defCN(i) );
128 pnkfelix 1.1.2.1 for( NodeIter di = def(i); di.hasNext(); ){
129 pnkfelix 1.1.2.1 Node d = di.next();
130 cananian 1.6 for(Object nO : live){
131 cananian 1.6 Node n = (Node) nO;
132 pnkfelix 1.1.2.1 addEdge( n, d );
133 pnkfelix 1.1.2.1 }
134 pnkfelix 1.1.2.1 }
135 pnkfelix 1.1.2.1 live.removeAll( defCN(i) );
136 pnkfelix 1.1.2.1 live. addAll( useCN(i) );
137 pnkfelix 1.1.2.1 }
138 pnkfelix 1.1.2.1
139 pnkfelix 1.1.2.1 }
140 pnkfelix 1.1.2.1
141 pnkfelix 1.1.2.1 }
142 pnkfelix 1.1.2.1
143 pnkfelix 1.1.2.1 protected void addEdge( Node u, Node v ) {
144 pnkfelix 1.1.2.1 // FSK: (6/27/01) adding because having these edges is dumb.
145 pnkfelix 1.1.2.1 // Shouldn't break anything. And yet...
146 pnkfelix 1.1.2.1 if (u.isPrecolored() && v.isPrecolored()) {
147 pnkfelix 1.1.2.1 return;
148 pnkfelix 1.1.2.1 }
149 pnkfelix 1.1.2.1
150 pnkfelix 1.1.2.1 if( ! adjSet.contains(u,v) && ! u.equals(v) ){
151 pnkfelix 1.1.2.1 adjSet.add(u,v);
152 pnkfelix 1.1.2.1 adjSet.add(v,u);
153 pnkfelix 1.1.2.1
154 pnkfelix 1.1.2.1 if( ! u.isPrecolored() ){
155 pnkfelix 1.1.2.1 u.neighbors.add(v);
156 pnkfelix 1.1.2.1 u.degree++;
157 pnkfelix 1.1.2.1 }
158 pnkfelix 1.1.2.1 if( ! v.isPrecolored() ){
159 pnkfelix 1.1.2.1 v.neighbors.add(u);
160 pnkfelix 1.1.2.1 v.degree++;
161 pnkfelix 1.1.2.1 }
162 pnkfelix 1.1.2.1 }
163 pnkfelix 1.1.2.1 }
164 pnkfelix 1.1.2.1
165 pnkfelix 1.1.2.1 protected void decrementDegree( Node m, Node n ) {
166 pnkfelix 1.1.2.1 if (m.isPrecolored())
167 pnkfelix 1.1.2.1 return;
168 pnkfelix 1.1.2.1
169 pnkfelix 1.1.2.1 int d = m.degree;
170 pnkfelix 1.1.2.1 m.degree--;
171 pnkfelix 1.1.2.1 if( d == K
172 pnkfelix 1.1.2.1
173 pnkfelix 1.1.2.1 // FSK: this clause isn't in the book, but it *is* in
174 pnkfelix 1.1.2.1 // FSK: CSAHack.RegAlloc.Color. Appel assumes that m is
175 pnkfelix 1.1.2.1 // FSK: in spillWorklist, but its possible for a node to
176 pnkfelix 1.1.2.1 // FSK: be in Freeze (and Simplify?), have its degree
177 pnkfelix 1.1.2.1 // FSK: incremented to K in Combine(u,v), and then this
178 pnkfelix 1.1.2.1 // FSK: method is called. So we explicitly check if m is
179 pnkfelix 1.1.2.1 // FSK: in spillWorklist first.
180 pnkfelix 1.1.2.1 // TODO: verify that this is the right behavior (intuitively, it should be...)
181 pnkfelix 1.1.2.1 && m.isSpillWorkL()
182 pnkfelix 1.1.2.1
183 pnkfelix 1.1.2.1
184 pnkfelix 1.1.2.1 ) {
185 pnkfelix 1.1.2.1
186 pnkfelix 1.1.2.1 enableMoves(m);
187 pnkfelix 1.1.2.1 enableMoves( adjacent(m) );
188 pnkfelix 1.1.2.1
189 pnkfelix 1.1.2.1 spill_worklist.remove(m);
190 pnkfelix 1.1.2.1 if( moveRelated( m )) {
191 pnkfelix 1.1.2.1 freeze_worklist.add( m );
192 pnkfelix 1.1.2.1 } else {
193 pnkfelix 1.1.2.1 simplify_worklist.add( m );
194 pnkfelix 1.1.2.1 }
195 pnkfelix 1.1.2.1 }
196 pnkfelix 1.1.2.1 }
197 pnkfelix 1.1.2.1
198 pnkfelix 1.1.2.1 protected boolean conservative(Node u, Node v) {
199 pnkfelix 1.1.2.1 return conservative(adjacent(u), adjacent(v));
200 pnkfelix 1.1.2.1 }
201 pnkfelix 1.1.2.1 // returns conservative( ni1 \/ ni2 )
202 pnkfelix 1.1.2.1 // conservative coalescing heuristic due to Preston Briggs
203 pnkfelix 1.1.2.1 private boolean conservative(NodeIter ni1, NodeIter ni2) {
204 pnkfelix 1.1.2.1 NodeIter union;
205 pnkfelix 1.1.2.1 // [ FIXED, but am seeing signs that "conservation" is being broken.
206 pnkfelix 1.1.2.1 // could just be inherent heuristical effects though ]
207 pnkfelix 1.1.2.1 // FSK combine(...) is not a strict union.
208 pnkfelix 1.1.2.1 // union = combine( new NodeIter[]{ ni1, ni2 } );
209 pnkfelix 1.1.2.1 union = union(ni1, ni2);
210 pnkfelix 1.1.2.1
211 pnkfelix 1.1.2.1 return conservative( union );
212 pnkfelix 1.1.2.1 }
213 pnkfelix 1.1.2.1 private NodeIter union(NodeIter n1, NodeIter n2) {
214 pnkfelix 1.1.2.1 HashSet s = new HashSet();
215 pnkfelix 1.1.2.1 while(n1.hasNext()){ s.add(n1.next()); }
216 pnkfelix 1.1.2.1 while(n2.hasNext()){ s.add(n2.next()); }
217 pnkfelix 1.1.2.1 return nodesIter( s.iterator() );
218 pnkfelix 1.1.2.1 }
219 pnkfelix 1.1.2.1
220 pnkfelix 1.1.2.1 private boolean conservative(NodeIter nodes) {
221 pnkfelix 1.1.2.1 int k = 0;
222 pnkfelix 1.1.2.1 while( nodes.hasNext() ){
223 pnkfelix 1.1.2.1 Node n = nodes.next();
224 pnkfelix 1.1.2.1 if (n.degree >= K)
225 pnkfelix 1.1.2.1 k++;
226 pnkfelix 1.1.2.1 }
227 pnkfelix 1.1.2.1 return k < K;
228 pnkfelix 1.1.2.1 }
229 pnkfelix 1.1.2.1
230 pnkfelix 1.1.2.1
231 pnkfelix 1.1.2.1 protected void assignColors() {
232 pnkfelix 1.1.2.1 while( !select_stack.isEmpty() ){
233 pnkfelix 1.1.2.1 Node n = select_stack.pop();
234 pnkfelix 1.1.2.1 ColorSet okColors = new ColorSet(K);
235 pnkfelix 1.1.2.1 for( NodeIter adj=n.neighbors.iter(); adj.hasNext(); ) {
236 pnkfelix 1.1.2.1 Node w = adj.next(); w = getAlias(w);
237 pnkfelix 1.1.2.1 if( w.isColored() ||
238 pnkfelix 1.1.2.1 w.isPrecolored() ){
239 pnkfelix 1.1.2.1 okColors.remove( w.color[0] );
240 pnkfelix 1.1.2.1 }
241 pnkfelix 1.1.2.1 }
242 pnkfelix 1.1.2.1 // TODO: Add code here to handle assigning a color to more
243 pnkfelix 1.1.2.1 // than one node at once, ala Brigg's multigraphs...
244 pnkfelix 1.1.2.1 if( okColors.isEmpty() ){
245 pnkfelix 1.1.2.1 spilled_nodes.add(n);
246 pnkfelix 1.1.2.1 } else {
247 pnkfelix 1.1.2.1 colored_nodes.add(n);
248 pnkfelix 1.1.2.1 n.color[0] = okColors.available();
249 pnkfelix 1.1.2.1 }
250 pnkfelix 1.1.2.1 }
251 pnkfelix 1.1.2.1
252 pnkfelix 1.1.2.1 for( NodeIter ni=coalesced_nodes.iter(); ni.hasNext(); ){
253 pnkfelix 1.1.2.1 Node n = ni.next();
254 pnkfelix 1.1.2.1 n.color[0] = getAlias(n).color[0];
255 pnkfelix 1.1.2.1 }
256 pnkfelix 1.1.2.1 }
257 pnkfelix 1.1.2.1
258 pnkfelix 1.1.2.1 protected void performFinalAssignment(Temp[] regs) {
259 pnkfelix 1.1.2.1 for(Iterator instrs=code.getElementsI(); instrs.hasNext();){
260 pnkfelix 1.1.2.1 Instr inst = (Instr) instrs.next();
261 pnkfelix 1.1.2.1
262 pnkfelix 1.1.2.1
263 pnkfelix 1.1.2.1 // FSK: we're looking at the real deal here, not the
264 pnkfelix 1.1.2.1 // abstract InstrGroupings
265 pnkfelix 1.1.2.1 Iterator refs = new CombineIterator
266 pnkfelix 1.1.2.1 // ( useCT(inst).iterator(), defCT(inst).iterator() );
267 pnkfelix 1.1.2.1 ( inst.useC().iterator(), inst.defC().iterator() );
268 pnkfelix 1.1.2.1
269 pnkfelix 1.1.2.1
270 pnkfelix 1.1.2.1 while( refs.hasNext() ){
271 pnkfelix 1.1.2.1 Temp t = (Temp) refs.next();
272 pnkfelix 1.1.2.1 if (isRegister(t)) continue;
273 pnkfelix 1.1.2.1 if (null == bbFact.getBlock
274 pnkfelix 1.1.2.1 (inst.getEntry( InstrGroup.AGGREGATE ))){
275 pnkfelix 1.1.2.1 System.err.println
276 pnkfelix 1.1.2.1 ("WARNING: code believed to be unreachable emitted");
277 pnkfelix 1.1.2.1 code.assignRegister
278 pnkfelix 1.1.2.1 (inst,t,(List)rfi().getRegAssignments(t).iterator().next());
279 pnkfelix 1.1.2.1 } else {
280 pnkfelix 1.1.2.1 Web w = webFor(t, inst);
281 pnkfelix 1.1.2.1 List nodes = nodesFor( w );
282 pnkfelix 1.1.2.1 List regList = toRegList( nodes, regs );
283 cananian 1.3.2.1 assert ! regList.isEmpty();
284 pnkfelix 1.1.2.1 code.assignRegister( inst, t, regList );
285 pnkfelix 1.1.2.1 }
286 pnkfelix 1.1.2.1 }
287 pnkfelix 1.1.2.1 }
288 pnkfelix 1.1.2.1
289 pnkfelix 1.1.2.1 fixupSpillCode();
290 pnkfelix 1.1.2.1
291 pnkfelix 1.1.2.1 }
292 pnkfelix 1.1.2.1
293 pnkfelix 1.1.2.1 /** REQUIRES: i.isMove()
294 pnkfelix 1.1.2.1 returns a Move corresponding to Instr i.
295 pnkfelix 1.1.2.1 */
296 pnkfelix 1.1.2.1 private Move moveFor(Instr i) {
297 cananian 1.3.2.1 assert i.isMove();
298 pnkfelix 1.1.2.1
299 pnkfelix 1.1.2.1 if( instrToMove.containsKey(i) ) {
300 cananian 1.6 return instrToMove.get(i);
301 pnkfelix 1.1.2.1 } else {
302 pnkfelix 1.1.2.1 // TODO: Fix to assign collections, not first elems!
303 cananian 1.3.2.1 assert defCN(i).size() == 1;
304 cananian 1.3.2.1 assert useCN(i).size() == 1;
305 pnkfelix 1.1.2.1 Node dst = (Node) defCN(i).iterator().next();
306 pnkfelix 1.1.2.1 Node src = (Node) useCN(i).iterator().next();
307 pnkfelix 1.1.2.1 Move m = new Move(i, dst, src);
308 pnkfelix 1.1.2.1 instrToMove.put(i, m);
309 pnkfelix 1.1.2.1 return m;
310 pnkfelix 1.1.2.1 }
311 pnkfelix 1.1.2.1 }
312 pnkfelix 1.1.2.1
313 pnkfelix 1.1.2.1 private List toRegList(List nodes, Temp[] colorToReg) {
314 pnkfelix 1.1.2.1 Temp[] regs = new Temp[nodes.size()];
315 pnkfelix 1.1.2.1 for(int i=0; i<regs.length; i++) {
316 pnkfelix 1.1.2.1 Node n = (Node)nodes.get(i);
317 pnkfelix 1.1.2.1 if (! (0 <= n.color[0] && n.color[0] < colorToReg.length) ) {
318 pnkfelix 1.1.2.1 code.printPreallocatedCode();
319 pnkfelix 1.1.2.1 // printAllColors();
320 pnkfelix 1.1.2.1 System.out.println();
321 pnkfelix 1.1.2.1 System.out.println("node:"+n+" history:"+n.nodeSet_history);
322 cananian 1.3.2.1 assert false : ("node:"+n+" should have valid color, not:"+n.color[0]);
323 pnkfelix 1.1.2.1 }
324 pnkfelix 1.1.2.1 regs[i] = colorToReg[ n.color[0] ];
325 pnkfelix 1.1.2.1 }
326 pnkfelix 1.1.2.1 return Arrays.asList( regs );
327 pnkfelix 1.1.2.1 }
328 pnkfelix 1.1.2.1
329 pnkfelix 1.1.2.1 private Collection instrIDs(final Collection instrs) {
330 pnkfelix 1.1.2.1 return new AbstractCollection() {
331 pnkfelix 1.1.2.1 public int size() { return instrs.size(); }
332 pnkfelix 1.1.2.1 public Iterator iterator()
333 pnkfelix 1.1.2.1 { return new FilterIterator
334 pnkfelix 1.1.2.1 (instrs.iterator(), new FilterIterator.Filter()
335 pnkfelix 1.1.2.1 { public Object map(Object o)
336 pnkfelix 1.1.2.1 { return new Integer(((Instr)o).getID()); }}); }};
337 pnkfelix 1.1.2.1 }
338 pnkfelix 1.1.2.1 private void printAllColors() {
339 cananian 1.6 for(Web w : webToNodes.keySet()){
340 pnkfelix 1.1.2.1 String accum =
341 pnkfelix 1.1.2.1 "Temp:"+w.temp+
342 pnkfelix 1.1.2.1 " defs:"+instrIDs(w.defs)+
343 pnkfelix 1.1.2.1 " uses:"+instrIDs(w.uses)+
344 pnkfelix 1.1.2.1 " colors:[";
345 cananian 1.6 for(Iterator<Node> nI=webToNodes.get(w).iterator(); nI.hasNext();){
346 cananian 1.6 Node node = nI.next();
347 pnkfelix 1.1.2.1 for(int i=0; i<node.color.length; i++) {
348 pnkfelix 1.1.2.1 accum += node.color[i] + ":";
349 pnkfelix 1.1.2.1 }
350 pnkfelix 1.1.2.1 if (nI.hasNext()) {
351 pnkfelix 1.1.2.1 accum += ", ";
352 pnkfelix 1.1.2.1 }
353 pnkfelix 1.1.2.1 }
354 pnkfelix 1.1.2.1 accum += "]";
355 pnkfelix 1.1.2.1 System.out.println(accum);
356 pnkfelix 1.1.2.1 }
357 pnkfelix 1.1.2.1 }
358 pnkfelix 1.1.2.1
359 pnkfelix 1.1.2.1 static class ColorSet {
360 pnkfelix 1.1.2.1 boolean[] colors;
361 pnkfelix 1.1.2.1 int size;
362 pnkfelix 1.1.2.1 public ColorSet(int numColors) {
363 pnkfelix 1.1.2.1 size = numColors;
364 pnkfelix 1.1.2.1 colors = new boolean[numColors];
365 pnkfelix 1.1.2.1 for(int i=0; i < colors.length; i++) {
366 pnkfelix 1.1.2.1 colors[i] = true;
367 pnkfelix 1.1.2.1 }
368 pnkfelix 1.1.2.1 }
369 pnkfelix 1.1.2.1 /** requires: ! this.isEmpty() */
370 pnkfelix 1.1.2.1 public int available() {
371 pnkfelix 1.1.2.1 for(int i=0; i<colors.length; i++) {
372 pnkfelix 1.1.2.1 if (colors[i])
373 pnkfelix 1.1.2.1 return i;
374 pnkfelix 1.1.2.1 }
375 pnkfelix 1.1.2.1 throw new RuntimeException();
376 pnkfelix 1.1.2.1 }
377 pnkfelix 1.1.2.1 public void remove(int color) {
378 pnkfelix 1.1.2.1 if (color < colors.length) {
379 pnkfelix 1.1.2.1 if ( colors[ color ] )
380 pnkfelix 1.1.2.1 size--;
381 pnkfelix 1.1.2.1 colors[ color ] = false;
382 pnkfelix 1.1.2.1 } else {
383 pnkfelix 1.1.2.1 // removing an unused register-only color; NOP
384 pnkfelix 1.1.2.1 }
385 pnkfelix 1.1.2.1 }
386 pnkfelix 1.1.2.1 public boolean isEmpty() { return size == 0; }
387 pnkfelix 1.1.2.1 }
388 pnkfelix 1.1.2.1
389 cananian 1.2 }