1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.bcel.generic;
18
19 import java.util.Arrays;
20
21 /**
22 * SWITCH - Branch depending on int value, generates either LOOKUPSWITCH or TABLESWITCH instruction, depending on
23 * whether the match values (int[]) can be sorted with no gaps between the numbers.
24 */
25 public final class SWITCH implements CompoundInstruction {
26
27 /**
28 * @return match is sorted in ascending order with no gap bigger than maxGap?
29 */
30 private static boolean matchIsOrdered(final int[] match, final int matchLength, final int maxGap) {
31 for (int i = 1; i < matchLength; i++) {
32 if (match[i] - match[i - 1] > maxGap) {
33 return false;
34 }
35 }
36 return true;
37 }
38
39 /**
40 * Sorts match and targets array with QuickSort.
41 */
42 private static void sort(final int l, final int r, final int[] match, final InstructionHandle[] targets) {
43 int i = l;
44 int j = r;
45 int h;
46 final int m = match[l + r >>> 1];
47 InstructionHandle h2;
48 do {
49 while (match[i] < m) {
50 i++;
51 }
52 while (m < match[j]) {
53 j--;
54 }
55 if (i <= j) {
56 h = match[i];
57 match[i] = match[j];
58 match[j] = h; // Swap elements
59 h2 = targets[i];
60 targets[i] = targets[j];
61 targets[j] = h2; // Swap instructions, too
62 i++;
63 j--;
64 }
65 } while (i <= j);
66 if (l < j) {
67 sort(l, j, match, targets);
68 }
69 if (i < r) {
70 sort(i, r, match, targets);
71 }
72 }
73
74 private final Select instruction;
75
76 public SWITCH(final int[] match, final InstructionHandle[] targets, final InstructionHandle target) {
77 this(match, targets, target, 1);
78 }
79
80 /**
81 * Template for switch() constructs. If the match array can be sorted in ascending order with gaps no larger than
82 * maxGap between the numbers, a TABLESWITCH instruction is generated, and a LOOKUPSWITCH otherwise. The former may be
83 * more efficient, but needs more space.
84 *
85 * Note, that the key array always will be sorted, though we leave the original arrays unaltered.
86 *
87 * @param match array of match values (case 2: ... case 7: ..., etc.)
88 * @param targets the instructions to be branched to for each case
89 * @param target the default target
90 * @param maxGap maximum gap that may between case branches
91 */
92 public SWITCH(final int[] match, final InstructionHandle[] targets, final InstructionHandle target, final int maxGap) {
93 final int[] matchClone = match.clone();
94 final InstructionHandle[] targetsClone = targets.clone();
95 final int matchLength = match.length;
96 if (matchLength < 2) {
97 instruction = new TABLESWITCH(match, targets, target);
98 } else {
99 sort(0, matchLength - 1, matchClone, targetsClone);
100 if (matchIsOrdered(matchClone, matchLength, maxGap)) {
101 final int maxSize = matchLength + matchLength * maxGap;
102 final int[] mVec = new int[maxSize];
103 final InstructionHandle[] tVec = new InstructionHandle[maxSize];
104 int count = 1;
105 mVec[0] = match[0];
106 tVec[0] = targets[0];
107 for (int i = 1; i < matchLength; i++) {
108 final int prev = match[i - 1];
109 final int gap = match[i] - prev;
110 for (int j = 1; j < gap; j++) {
111 mVec[count] = prev + j;
112 tVec[count] = target;
113 count++;
114 }
115 mVec[count] = match[i];
116 tVec[count] = targets[i];
117 count++;
118 }
119 instruction = new TABLESWITCH(Arrays.copyOf(mVec, count), Arrays.copyOf(tVec, count), target);
120 } else {
121 instruction = new LOOKUPSWITCH(matchClone, targetsClone, target);
122 }
123 }
124 }
125
126 public Instruction getInstruction() {
127 return instruction;
128 }
129
130 @Override
131 public InstructionList getInstructionList() {
132 return new InstructionList(instruction);
133 }
134 }