    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}