1 /*
2 * reserved comment block
3 * DO NOT REMOVE OR ALTER!
4 */
5 package com.sun.org.apache.bcel.internal.generic;
6
7 /* ====================================================================
8 * The Apache Software License, Version 1.1
9 *
10 * Copyright (c) 2001 The Apache Software Foundation. All rights
11 * reserved.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
15 * are met:
16 *
17 * 1. Redistributions of source code must retain the above copyright
18 * notice, this list of conditions and the following disclaimer.
19 *
20 * 2. Redistributions in binary form must reproduce the above copyright
21 * notice, this list of conditions and the following disclaimer in
22 * the documentation and/or other materials provided with the
23 * distribution.
24 *
25 * 3. The end-user documentation included with the redistribution,
26 * if any, must include the following acknowledgment:
27 * "This product includes software developed by the
28 * Apache Software Foundation (http://www.apache.org/)."
29 * Alternately, this acknowledgment may appear in the software itself,
30 * if and wherever such third-party acknowledgments normally appear.
31 *
32 * 4. The names "Apache" and "Apache Software Foundation" and
33 * "Apache BCEL" must not be used to endorse or promote products
34 * derived from this software without prior written permission. For
35 * written permission, please contact apache@apache.org.
36 *
37 * 5. Products derived from this software may not be called "Apache",
38 * "Apache BCEL", nor may "Apache" appear in their name, without
39 * prior written permission of the Apache Software Foundation.
40 *
41 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
42 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
43 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
44 * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
45 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
46 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
47 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
48 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
49 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
50 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
51 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
52 * SUCH DAMAGE.
53 * ====================================================================
54 *
55 * This software consists of voluntary contributions made by many
56 * individuals on behalf of the Apache Software Foundation. For more
57 * information on the Apache Software Foundation, please see
58 * <http://www.apache.org/>.
59 */
60
61 /**
62 * SWITCH - Branch depending on int value, generates either LOOKUPSWITCH or
63 * TABLESWITCH instruction, depending on whether the match values (int[]) can be
64 * sorted with no gaps between the numbers.
65 *
66 * @author <A HREF="mailto:markus.dahm@berlin.de">M. Dahm</A>
67 */
68 public final class SWITCH implements CompoundInstruction {
69 private int[] match;
70 private InstructionHandle[] targets;
71 private Select instruction;
72 private int match_length;
73
74 /**
75 * Template for switch() constructs. If the match array can be
76 * sorted in ascending order with gaps no larger than max_gap
77 * between the numbers, a TABLESWITCH instruction is generated, and
78 * a LOOKUPSWITCH otherwise. The former may be more efficient, but
79 * needs more space.
80 *
81 * Note, that the key array always will be sorted, though we leave
82 * the original arrays unaltered.
83 *
84 * @param match array of match values (case 2: ... case 7: ..., etc.)
85 * @param targets the instructions to be branched to for each case
86 * @param target the default target
87 * @param max_gap maximum gap that may between case branches
88 */
89 public SWITCH(int[] match, InstructionHandle[] targets,
90 InstructionHandle target, int max_gap) {
91 this.match = (int[])match.clone();
92 this.targets = (InstructionHandle[])targets.clone();
93
94 if((match_length = match.length) < 2) // (almost) empty switch, or just default
95 instruction = new TABLESWITCH(match, targets, target);
96 else {
97 sort(0, match_length - 1);
98
99 if(matchIsOrdered(max_gap)) {
100 fillup(max_gap, target);
101
102 instruction = new TABLESWITCH(this.match, this.targets, target);
103 }
104 else
105 instruction = new LOOKUPSWITCH(this.match, this.targets, target);
106 }
107 }
108
109 public SWITCH(int[] match, InstructionHandle[] targets,
110 InstructionHandle target) {
111 this(match, targets, target, 1);
112 }
113
114 private final void fillup(int max_gap, InstructionHandle target) {
115 int max_size = match_length + match_length * max_gap;
116 int[] m_vec = new int[max_size];
117 InstructionHandle[] t_vec = new InstructionHandle[max_size];
118 int count = 1;
119
120 m_vec[0] = match[0];
121 t_vec[0] = targets[0];
122
123 for(int i=1; i < match_length; i++) {
124 int prev = match[i-1];
125 int gap = match[i] - prev;
126
127 for(int j=1; j < gap; j++) {
128 m_vec[count] = prev + j;
129 t_vec[count] = target;
130 count++;
131 }
132
133 m_vec[count] = match[i];
134 t_vec[count] = targets[i];
135 count++;
136 }
137
138 match = new int[count];
139 targets = new InstructionHandle[count];
140
141 System.arraycopy(m_vec, 0, match, 0, count);
142 System.arraycopy(t_vec, 0, targets, 0, count);
143 }
144
145 /**
146 * Sort match and targets array with QuickSort.
147 */
148 private final void sort(int l, int r) {
149 int i = l, j = r;
150 int h, m = match[(l + r) / 2];
151 InstructionHandle h2;
152
153 do {
154 while(match[i] < m) i++;
155 while(m < match[j]) j--;
156
157 if(i <= j) {
158 h=match[i]; match[i]=match[j]; match[j]=h; // Swap elements
159 h2=targets[i]; targets[i]=targets[j]; targets[j]=h2; // Swap instructions, too
160 i++; j--;
161 }
162 } while(i <= j);
163
164 if(l < j) sort(l, j);
165 if(i < r) sort(i, r);
166 }
167
168 /**
169 * @return match is sorted in ascending order with no gap bigger than max_gap?
170 */
171 private final boolean matchIsOrdered(int max_gap) {
172 for(int i=1; i < match_length; i++)
173 if(match[i] - match[i-1] > max_gap)
174 return false;
175
176 return true;
177 }
178
179 public final InstructionList getInstructionList() {
180 return new InstructionList(instruction);
181 }
182
183 public final Instruction getInstruction() {
184 return instruction;
185 }
186 }