    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
    022 * TABLESWITCH instruction, depending on whether the match values (int[]) can be
    023 * sorted with no gaps between the numbers.
    024 *
    025 * @version $Id: SWITCH.java 1806200 2017-08-25 16:33:06Z ggregory $
    026 */
    027public final class SWITCH implements CompoundInstruction {
    028
    029    private int[] match;
    030    private InstructionHandle[] targets;
    031    private Select instruction;
    032    private int match_length;
    033
    034
    035    /**
    036     * Template for switch() constructs. If the match array can be
    037     * sorted in ascending order with gaps no larger than max_gap
    038     * between the numbers, a TABLESWITCH instruction is generated, and
    039     * a LOOKUPSWITCH otherwise. The former may be more efficient, but
    040     * needs more space.
    041     *
    042     * Note, that the key array always will be sorted, though we leave
    043     * the original arrays unaltered.
    044     *
    045     * @param match array of match values (case 2: ... case 7: ..., etc.)
    046     * @param targets the instructions to be branched to for each case
    047     * @param target the default target
    048     * @param max_gap maximum gap that may between case branches
    049     */
    050    public SWITCH(final int[] match, final InstructionHandle[] targets, final InstructionHandle target, final int max_gap) {
    051        this.match = match.clone();
    052        this.targets = targets.clone();
    053        if ((match_length = match.length) < 2) {
    054            instruction = new TABLESWITCH(match, targets, target);
    055        } else {
    056            sort(0, match_length - 1);
    057            if (matchIsOrdered(max_gap)) {
    058                fillup(max_gap, target);
    059                instruction = new TABLESWITCH(this.match, this.targets, target);
    060            } else {
    061                instruction = new LOOKUPSWITCH(this.match, this.targets, target);
    062            }
    063        }
    064    }
    065
    066
    067    public SWITCH(final int[] match, final InstructionHandle[] targets, final InstructionHandle target) {
    068        this(match, targets, target, 1);
    069    }
    070
    071
    072    private void fillup( final int max_gap, final InstructionHandle target ) {
    073        final int max_size = match_length + match_length * max_gap;
    074        final int[] m_vec = new int[max_size];
    075        final InstructionHandle[] t_vec = new InstructionHandle[max_size];
    076        int count = 1;
    077        m_vec[0] = match[0];
    078        t_vec[0] = targets[0];
    079        for (int i = 1; i < match_length; i++) {
    080            final int prev = match[i - 1];
    081            final int gap = match[i] - prev;
    082            for (int j = 1; j < gap; j++) {
    083                m_vec[count] = prev + j;
    084                t_vec[count] = target;
    085                count++;
    086            }
    087            m_vec[count] = match[i];
    088            t_vec[count] = targets[i];
    089            count++;
    090        }
    091        match = new int[count];
    092        targets = new InstructionHandle[count];
    093        System.arraycopy(m_vec, 0, match, 0, count);
    094        System.arraycopy(t_vec, 0, targets, 0, count);
    095    }
    096
    097
    098    /**
    099     * Sort match and targets array with QuickSort.
    100     */
    101    private void sort( final int l, final int r ) {
    102        int i = l;
    103        int j = r;
    104        int h;
    105        final int m = match[(l + r) / 2];
    106        InstructionHandle h2;
    107        do {
    108            while (match[i] < m) {
    109                i++;
    110            }
    111            while (m < match[j]) {
    112                j--;
    113            }
    114            if (i <= j) {
    115                h = match[i];
    116                match[i] = match[j];
    117                match[j] = h; // Swap elements
    118                h2 = targets[i];
    119                targets[i] = targets[j];
    120                targets[j] = h2; // Swap instructions, too
    121                i++;
    122                j--;
    123            }
    124        } while (i <= j);
    125        if (l < j) {
    126            sort(l, j);
    127        }
    128        if (i < r) {
    129            sort(i, r);
    130        }
    131    }
    132
    133
    134    /**
    135     * @return match is sorted in ascending order with no gap bigger than max_gap?
    136     */
    137    private boolean matchIsOrdered( final int max_gap ) {
    138        for (int i = 1; i < match_length; i++) {
    139            if (match[i] - match[i - 1] > max_gap) {
    140                return false;
    141            }
    142        }
    143        return true;
    144    }
    145
    146
    147    @Override
    148    public final InstructionList getInstructionList() {
    149        return new InstructionList(instruction);
    150    }
    151
    152
    153    public final Instruction getInstruction() {
    154        return instruction;
    155    }
    156}