View Javadoc
1   /*
2    * reserved comment block
3    * DO NOT REMOVE OR ALTER!
4    */
5   package com.sun.org.apache.bcel.internal.generic;
6   
7   /* ====================================================================
8    * The Apache Software License, Version 1.1
9    *
10   * Copyright (c) 2001 The Apache Software Foundation.  All rights
11   * reserved.
12   *
13   * Redistribution and use in source and binary forms, with or without
14   * modification, are permitted provided that the following conditions
15   * are met:
16   *
17   * 1. Redistributions of source code must retain the above copyright
18   *    notice, this list of conditions and the following disclaimer.
19   *
20   * 2. Redistributions in binary form must reproduce the above copyright
21   *    notice, this list of conditions and the following disclaimer in
22   *    the documentation and/or other materials provided with the
23   *    distribution.
24   *
25   * 3. The end-user documentation included with the redistribution,
26   *    if any, must include the following acknowledgment:
27   *       "This product includes software developed by the
28   *        Apache Software Foundation (http://www.apache.org/)."
29   *    Alternately, this acknowledgment may appear in the software itself,
30   *    if and wherever such third-party acknowledgments normally appear.
31   *
32   * 4. The names "Apache" and "Apache Software Foundation" and
33   *    "Apache BCEL" must not be used to endorse or promote products
34   *    derived from this software without prior written permission. For
35   *    written permission, please contact apache@apache.org.
36   *
37   * 5. Products derived from this software may not be called "Apache",
38   *    "Apache BCEL", nor may "Apache" appear in their name, without
39   *    prior written permission of the Apache Software Foundation.
40   *
41   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
42   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
43   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
44   * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
45   * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
46   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
47   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
48   * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
49   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
50   * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
51   * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
52   * SUCH DAMAGE.
53   * ====================================================================
54   *
55   * This software consists of voluntary contributions made by many
56   * individuals on behalf of the Apache Software Foundation.  For more
57   * information on the Apache Software Foundation, please see
58   * <http://www.apache.org/>.
59   */
60  
61  /**
62   * SWITCH - Branch depending on int value, generates either LOOKUPSWITCH or
63   * TABLESWITCH instruction, depending on whether the match values (int[]) can be
64   * sorted with no gaps between the numbers.
65   *
66   * @author  <A HREF="mailto:markus.dahm@berlin.de">M. Dahm</A>
67   */
68  public final class SWITCH implements CompoundInstruction {
69    private int[]               match;
70    private InstructionHandle[] targets;
71    private Select              instruction;
72    private int                 match_length;
73  
74    /**
75     * Template for switch() constructs. If the match array can be
76     * sorted in ascending order with gaps no larger than max_gap
77     * between the numbers, a TABLESWITCH instruction is generated, and
78     * a LOOKUPSWITCH otherwise. The former may be more efficient, but
79     * needs more space.
80     *
81     * Note, that the key array always will be sorted, though we leave
82     * the original arrays unaltered.
83     *
84     * @param match array of match values (case 2: ... case 7: ..., etc.)
85     * @param targets the instructions to be branched to for each case
86     * @param target the default target
87     * @param max_gap maximum gap that may between case branches
88     */
89    public SWITCH(int[] match, InstructionHandle[] targets,
90                  InstructionHandle target, int max_gap) {
91      this.match   = (int[])match.clone();
92      this.targets = (InstructionHandle[])targets.clone();
93  
94      if((match_length = match.length) < 2) // (almost) empty switch, or just default
95        instruction = new TABLESWITCH(match, targets, target);
96      else {
97        sort(0, match_length - 1);
98  
99        if(matchIsOrdered(max_gap)) {
100         fillup(max_gap, target);
101 
102         instruction = new TABLESWITCH(this.match, this.targets, target);
103       }
104       else
105         instruction = new LOOKUPSWITCH(this.match, this.targets, target);
106     }
107   }
108 
109   public SWITCH(int[] match, InstructionHandle[] targets,
110                 InstructionHandle target) {
111     this(match, targets, target, 1);
112   }
113 
114   private final void fillup(int max_gap, InstructionHandle target) {
115     int                 max_size = match_length + match_length * max_gap;
116     int[]               m_vec    = new int[max_size];
117     InstructionHandle[] t_vec    = new InstructionHandle[max_size];
118     int                 count    = 1;
119 
120     m_vec[0] = match[0];
121     t_vec[0] = targets[0];
122 
123     for(int i=1; i < match_length; i++) {
124       int prev = match[i-1];
125       int gap  = match[i] - prev;
126 
127       for(int j=1; j < gap; j++) {
128         m_vec[count] = prev + j;
129         t_vec[count] = target;
130         count++;
131       }
132 
133       m_vec[count] = match[i];
134       t_vec[count] = targets[i];
135       count++;
136     }
137 
138     match   = new int[count];
139     targets = new InstructionHandle[count];
140 
141     System.arraycopy(m_vec, 0, match, 0, count);
142     System.arraycopy(t_vec, 0, targets, 0, count);
143   }
144 
145   /**
146    * Sort match and targets array with QuickSort.
147    */
148   private final void sort(int l, int r) {
149     int i = l, j = r;
150     int h, m = match[(l + r) / 2];
151     InstructionHandle h2;
152 
153     do {
154       while(match[i] < m) i++;
155       while(m < match[j]) j--;
156 
157       if(i <= j) {
158         h=match[i]; match[i]=match[j]; match[j]=h; // Swap elements
159         h2=targets[i]; targets[i]=targets[j]; targets[j]=h2; // Swap instructions, too
160         i++; j--;
161       }
162     } while(i <= j);
163 
164     if(l < j) sort(l, j);
165     if(i < r) sort(i, r);
166   }
167 
168   /**
169    * @return match is sorted in ascending order with no gap bigger than max_gap?
170    */
171   private final boolean matchIsOrdered(int max_gap) {
172     for(int i=1; i < match_length; i++)
173       if(match[i] - match[i-1] > max_gap)
174         return false;
175 
176     return true;
177   }
178 
179   public final InstructionList getInstructionList() {
180     return new InstructionList(instruction);
181   }
182 
183   public final Instruction getInstruction() {
184     return instruction;
185   }
186 }