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 */
017package org.apache.bcel.generic;
018
019import java.util.Arrays;
020
021/**
022 * SWITCH - Branch depending on int value, generates either LOOKUPSWITCH or TABLESWITCH instruction, depending on
023 * whether the match values (int[]) can be sorted with no gaps between the numbers.
024 */
025public final class SWITCH implements CompoundInstruction {
026
027    private int[] match;
028    private InstructionHandle[] targets;
029    private final Select instruction;
030    private final int matchLength;
031
032    public SWITCH(final int[] match, final InstructionHandle[] targets, final InstructionHandle target) {
033        this(match, targets, target, 1);
034    }
035
036    /**
037     * Template for switch() constructs. If the match array can be sorted in ascending order with gaps no larger than
038     * maxGap between the numbers, a TABLESWITCH instruction is generated, and a LOOKUPSWITCH otherwise. The former may be
039     * more efficient, but needs more space.
040     *
041     * Note, that the key array always will be sorted, though we leave the original arrays unaltered.
042     *
043     * @param match array of match values (case 2: ... case 7: ..., etc.)
044     * @param targets the instructions to be branched to for each case
045     * @param target the default target
046     * @param maxGap maximum gap that may between case branches
047     */
048    public SWITCH(final int[] match, final InstructionHandle[] targets, final InstructionHandle target, final int maxGap) {
049        this.match = match.clone();
050        this.targets = targets.clone();
051        if ((matchLength = match.length) < 2) {
052            instruction = new TABLESWITCH(match, targets, target);
053        } else {
054            sort(0, matchLength - 1);
055            if (matchIsOrdered(maxGap)) {
056                fillup(maxGap, target);
057                instruction = new TABLESWITCH(this.match, this.targets, target);
058            } else {
059                instruction = new LOOKUPSWITCH(this.match, this.targets, target);
060            }
061        }
062    }
063
064    private void fillup(final int maxGap, final InstructionHandle target) {
065        final int maxSize = matchLength + matchLength * maxGap;
066        final int[] mVec = new int[maxSize];
067        final InstructionHandle[] tVec = new InstructionHandle[maxSize];
068        int count = 1;
069        mVec[0] = match[0];
070        tVec[0] = targets[0];
071        for (int i = 1; i < matchLength; i++) {
072            final int prev = match[i - 1];
073            final int gap = match[i] - prev;
074            for (int j = 1; j < gap; j++) {
075                mVec[count] = prev + j;
076                tVec[count] = target;
077                count++;
078            }
079            mVec[count] = match[i];
080            tVec[count] = targets[i];
081            count++;
082        }
083        match = Arrays.copyOf(mVec, count);
084        targets = Arrays.copyOf(tVec, count);
085    }
086
087    public Instruction getInstruction() {
088        return instruction;
089    }
090
091    @Override
092    public InstructionList getInstructionList() {
093        return new InstructionList(instruction);
094    }
095
096    /**
097     * @return match is sorted in ascending order with no gap bigger than maxGap?
098     */
099    private boolean matchIsOrdered(final int maxGap) {
100        for (int i = 1; i < matchLength; i++) {
101            if (match[i] - match[i - 1] > maxGap) {
102                return false;
103            }
104        }
105        return true;
106    }
107
108    /**
109     * Sort match and targets array with QuickSort.
110     */
111    private void sort(final int l, final int r) {
112        int i = l;
113        int j = r;
114        int h;
115        final int m = match[l + r >>> 1];
116        InstructionHandle h2;
117        do {
118            while (match[i] < m) {
119                i++;
120            }
121            while (m < match[j]) {
122                j--;
123            }
124            if (i <= j) {
125                h = match[i];
126                match[i] = match[j];
127                match[j] = h; // Swap elements
128                h2 = targets[i];
129                targets[i] = targets[j];
130                targets[j] = h2; // Swap instructions, too
131                i++;
132                j--;
133            }
134        } while (i <= j);
135        if (l < j) {
136            sort(l, j);
137        }
138        if (i < r) {
139            sort(i, r);
140        }
141    }
142}