    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}