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