    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 *
    017 */
    018package org.apache.bcel.generic;
    019
    020/**
    021 * SWITCH - Branch depending on int value, generates either LOOKUPSWITCH or TABLESWITCH instruction, depending on
    022 * whether the match values (int[]) can be sorted with no gaps between the numbers.
    023 *
    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     * max_gap 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 max_gap maximum gap that may between case branches
    047     */
    048    public SWITCH(final int[] match, final InstructionHandle[] targets, final InstructionHandle target, final int max_gap) {
    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(max_gap)) {
    056                fillup(max_gap, 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 max_gap, final InstructionHandle target) {
    065        final int max_size = matchLength + matchLength * max_gap;
    066        final int[] m_vec = new int[max_size];
    067        final InstructionHandle[] t_vec = new InstructionHandle[max_size];
    068        int count = 1;
    069        m_vec[0] = match[0];
    070        t_vec[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                m_vec[count] = prev + j;
    076                t_vec[count] = target;
    077                count++;
    078            }
    079            m_vec[count] = match[i];
    080            t_vec[count] = targets[i];
    081            count++;
    082        }
    083        match = new int[count];
    084        targets = new InstructionHandle[count];
    085        System.arraycopy(m_vec, 0, match, 0, count);
    086        System.arraycopy(t_vec, 0, targets, 0, count);
    087    }
    088
    089    public Instruction getInstruction() {
    090        return instruction;
    091    }
    092
    093    @Override
    094    public InstructionList getInstructionList() {
    095        return new InstructionList(instruction);
    096    }
    097
    098    /**
    099     * @return match is sorted in ascending order with no gap bigger than max_gap?
    100     */
    101    private boolean matchIsOrdered(final int max_gap) {
    102        for (int i = 1; i < matchLength; i++) {
    103            if (match[i] - match[i - 1] > max_gap) {
    104                return false;
    105            }
    106        }
    107        return true;
    108    }
    109
    110    /**
    111     * Sort match and targets array with QuickSort.
    112     */
    113    private void sort(final int l, final int r) {
    114        int i = l;
    115        int j = r;
    116        int h;
    117        final int m = match[l + r >>> 1];
    118        InstructionHandle h2;
    119        do {
    120            while (match[i] < m) {
    121                i++;
    122            }
    123            while (m < match[j]) {
    124                j--;
    125            }
    126            if (i <= j) {
    127                h = match[i];
    128                match[i] = match[j];
    129                match[j] = h; // Swap elements
    130                h2 = targets[i];
    131                targets[i] = targets[j];
    132                targets[j] = h2; // Swap instructions, too
    133                i++;
    134                j--;
    135            }
    136        } while (i <= j);
    137        if (l < j) {
    138            sort(l, j);
    139        }
    140        if (i < r) {
    141            sort(i, r);
    142        }
    143    }
    144}