001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *   https://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing,
013 * software distributed under the License is distributed on an
014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015 * KIND, either express or implied.  See the License for the
016 * specific language governing permissions and limitations
017 * under the License.
018 */
019package org.apache.bcel.generic;
020
021import java.util.Arrays;
022
023/**
024 * SWITCH - Branch depending on int value, generates either LOOKUPSWITCH or TABLESWITCH instruction, depending on
025 * whether the match values (int[]) can be sorted with no gaps between the numbers.
026 */
027public final class SWITCH implements CompoundInstruction {
028
029    /**
030     * @return match is sorted in ascending order with no gap bigger than maxGap?
031     */
032    private static boolean matchIsOrdered(final int[] match, final int matchLength, final int maxGap) {
033        for (int i = 1; i < matchLength; i++) {
034            if (match[i] - match[i - 1] > maxGap) {
035                return false;
036            }
037        }
038        return true;
039    }
040
041    /**
042     * Sorts match and targets array with QuickSort.
043     */
044    private static void sort(final int l, final int r, final int[] match, final InstructionHandle[] targets) {
045        int i = l;
046        int j = r;
047        int h;
048        final int m = match[l + r >>> 1];
049        InstructionHandle h2;
050        do {
051            while (match[i] < m) {
052                i++;
053            }
054            while (m < match[j]) {
055                j--;
056            }
057            if (i <= j) {
058                h = match[i];
059                match[i] = match[j];
060                match[j] = h; // Swap elements
061                h2 = targets[i];
062                targets[i] = targets[j];
063                targets[j] = h2; // Swap instructions, too
064                i++;
065                j--;
066            }
067        } while (i <= j);
068        if (l < j) {
069            sort(l, j, match, targets);
070        }
071        if (i < r) {
072            sort(i, r, match, targets);
073        }
074    }
075
076    private final Select instruction;
077
078    public SWITCH(final int[] match, final InstructionHandle[] targets, final InstructionHandle target) {
079        this(match, targets, target, 1);
080    }
081
082    /**
083     * Template for switch() constructs. If the match array can be sorted in ascending order with gaps no larger than
084     * maxGap between the numbers, a TABLESWITCH instruction is generated, and a LOOKUPSWITCH otherwise. The former may be
085     * more efficient, but needs more space.
086     *
087     * Note, that the key array always will be sorted, though we leave the original arrays unaltered.
088     *
089     * @param match array of match values (case 2: ... case 7: ..., etc.)
090     * @param targets the instructions to be branched to for each case
091     * @param target the default target
092     * @param maxGap maximum gap that may between case branches
093     */
094    public SWITCH(final int[] match, final InstructionHandle[] targets, final InstructionHandle target, final int maxGap) {
095        final int[] matchClone = match.clone();
096        final InstructionHandle[] targetsClone = targets.clone();
097        final int matchLength = match.length;
098        if (matchLength < 2) {
099            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}