001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 * 017 */ 018package org.apache.bcel.generic; 019 020/** 021 * SWITCH - Branch depending on int value, generates either LOOKUPSWITCH or 022 * TABLESWITCH instruction, depending on whether the match values (int[]) can be 023 * sorted with no gaps between the numbers. 024 * 025 */ 026public final class SWITCH implements CompoundInstruction { 027 028 private int[] match; 029 private InstructionHandle[] targets; 030 private Select instruction; 031 private int match_length; 032 033 034 /** 035 * Template for switch() constructs. If the match array can be 036 * sorted in ascending order with gaps no larger than max_gap 037 * between the numbers, a TABLESWITCH instruction is generated, and 038 * a LOOKUPSWITCH otherwise. The former may be more efficient, but 039 * needs more space. 040 * 041 * Note, that the key array always will be sorted, though we leave 042 * the original arrays unaltered. 043 * 044 * @param match array of match values (case 2: ... case 7: ..., etc.) 045 * @param targets the instructions to be branched to for each case 046 * @param target the default target 047 * @param max_gap maximum gap that may between case branches 048 */ 049 public SWITCH(final int[] match, final InstructionHandle[] targets, final InstructionHandle target, final int max_gap) { 050 this.match = match.clone(); 051 this.targets = targets.clone(); 052 if ((match_length = match.length) < 2) { 053 instruction = new TABLESWITCH(match, targets, target); 054 } else { 055 sort(0, match_length - 1); 056 if (matchIsOrdered(max_gap)) { 057 fillup(max_gap, target); 058 instruction = new TABLESWITCH(this.match, this.targets, target); 059 } else { 060 instruction = new LOOKUPSWITCH(this.match, this.targets, target); 061 } 062 } 063 } 064 065 066 public SWITCH(final int[] match, final InstructionHandle[] targets, final InstructionHandle target) { 067 this(match, targets, target, 1); 068 } 069 070 071 private void fillup( final int max_gap, final InstructionHandle target ) { 072 final int max_size = match_length + match_length * max_gap; 073 final int[] m_vec = new int[max_size]; 074 final InstructionHandle[] t_vec = new InstructionHandle[max_size]; 075 int count = 1; 076 m_vec[0] = match[0]; 077 t_vec[0] = targets[0]; 078 for (int i = 1; i < match_length; i++) { 079 final int prev = match[i - 1]; 080 final int gap = match[i] - prev; 081 for (int j = 1; j < gap; j++) { 082 m_vec[count] = prev + j; 083 t_vec[count] = target; 084 count++; 085 } 086 m_vec[count] = match[i]; 087 t_vec[count] = targets[i]; 088 count++; 089 } 090 match = new int[count]; 091 targets = new InstructionHandle[count]; 092 System.arraycopy(m_vec, 0, match, 0, count); 093 System.arraycopy(t_vec, 0, targets, 0, count); 094 } 095 096 097 /** 098 * Sort match and targets array with QuickSort. 099 */ 100 private void sort( final int l, final int r ) { 101 int i = l; 102 int j = r; 103 int h; 104 final int m = match[(l + r) >>> 1]; 105 InstructionHandle h2; 106 do { 107 while (match[i] < m) { 108 i++; 109 } 110 while (m < match[j]) { 111 j--; 112 } 113 if (i <= j) { 114 h = match[i]; 115 match[i] = match[j]; 116 match[j] = h; // Swap elements 117 h2 = targets[i]; 118 targets[i] = targets[j]; 119 targets[j] = h2; // Swap instructions, too 120 i++; 121 j--; 122 } 123 } while (i <= j); 124 if (l < j) { 125 sort(l, j); 126 } 127 if (i < r) { 128 sort(i, r); 129 } 130 } 131 132 133 /** 134 * @return match is sorted in ascending order with no gap bigger than max_gap? 135 */ 136 private boolean matchIsOrdered( final int max_gap ) { 137 for (int i = 1; i < match_length; i++) { 138 if (match[i] - match[i - 1] > max_gap) { 139 return false; 140 } 141 } 142 return true; 143 } 144 145 146 @Override 147 public InstructionList getInstructionList() { 148 return new InstructionList(instruction); 149 } 150 151 152 public Instruction getInstruction() { 153 return instruction; 154 } 155}