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