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    /**
079     * Constructs a SWITCH with default maxGap of 1.
080     *
081     * @param match array of match values.
082     * @param targets The instructions to be branched to for each case.
083     * @param target The default target.
084     */
085    public SWITCH(final int[] match, final InstructionHandle[] targets, final InstructionHandle target) {
086        this(match, targets, target, 1);
087    }
088
089    /**
090     * Template for switch() constructs. If the match array can be sorted in ascending order with gaps no larger than
091     * maxGap between the numbers, a TABLESWITCH instruction is generated, and a LOOKUPSWITCH otherwise. The former may be
092     * more efficient, but needs more space.
093     *
094     * Note, that the key array always will be sorted, though we leave the original arrays unaltered.
095     *
096     * @param match array of match values (case 2: ... case 7: ..., etc.).
097     * @param targets The instructions to be branched to for each case.
098     * @param target The default target.
099     * @param maxGap maximum gap that may between case branches.
100     */
101    public SWITCH(final int[] match, final InstructionHandle[] targets, final InstructionHandle target, final int maxGap) {
102        final int[] matchClone = match.clone();
103        final InstructionHandle[] targetsClone = targets.clone();
104        final int matchLength = match.length;
105        if (matchLength < 2) {
106            instruction = new TABLESWITCH(match, targets, target);
107        } else {
108            sort(0, matchLength - 1, matchClone, targetsClone);
109            if (matchIsOrdered(matchClone, matchLength, maxGap)) {
110                final int maxSize = matchLength + matchLength * maxGap;
111                final int[] mVec = new int[maxSize];
112                final InstructionHandle[] tVec = new InstructionHandle[maxSize];
113                int count = 1;
114                mVec[0] = matchClone[0];
115                tVec[0] = targetsClone[0];
116                for (int i = 1; i < matchLength; i++) {
117                    final int prev = matchClone[i - 1];
118                    final int gap = matchClone[i] - prev;
119                    for (int j = 1; j < gap; j++) {
120                        mVec[count] = prev + j;
121                        tVec[count] = target;
122                        count++;
123                    }
124                    mVec[count] = matchClone[i];
125                    tVec[count] = targetsClone[i];
126                    count++;
127                }
128                instruction = new TABLESWITCH(Arrays.copyOf(mVec, count), Arrays.copyOf(tVec, count), target);
129            } else {
130                instruction = new LOOKUPSWITCH(matchClone, targetsClone, target);
131            }
132        }
133    }
134
135    /**
136     * Gets the instruction.
137     *
138     * @return The instruction.
139     */
140    public Instruction getInstruction() {
141        return instruction;
142    }
143
144    @Override
145    public InstructionList getInstructionList() {
146        return new InstructionList(instruction);
147    }
148}