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}