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