1 /*
   2  * reserved comment block
   3  * DO NOT REMOVE OR ALTER!
   4  */
   5 /*
   6  * Licensed to the Apache Software Foundation (ASF) under one or more
   7  * contributor license agreements.  See the NOTICE file distributed with
   8  * this work for additional information regarding copyright ownership.
   9  * The ASF licenses this file to You under the Apache License, Version 2.0
  10  * (the "License"); you may not use this file except in compliance with
  11  * the License.  You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  * Unless required by applicable law or agreed to in writing, software
  16  * distributed under the License is distributed on an "AS IS" BASIS,
  17  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  18  * See the License for the specific language governing permissions and
  19  * limitations under the License.
  20  */
  21 
  22 package com.sun.org.apache.bcel.internal.generic;
  23 
  24 
  25 /**
  26  * SWITCH - Branch depending on int value, generates either LOOKUPSWITCH or
  27  * TABLESWITCH instruction, depending on whether the match values (int[]) can be
  28  * sorted with no gaps between the numbers.
  29  *
  30  * @author  <A HREF="mailto:markus.dahm@berlin.de">M. Dahm</A>
  31  */
  32 public final class SWITCH implements CompoundInstruction {
  33   private int[]               match;
  34   private InstructionHandle[] targets;
  35   private Select              instruction;
  36   private int                 match_length;
  37 
  38   /**
  39    * Template for switch() constructs. If the match array can be
  40    * sorted in ascending order with gaps no larger than max_gap
  41    * between the numbers, a TABLESWITCH instruction is generated, and
  42    * a LOOKUPSWITCH otherwise. The former may be more efficient, but
  43    * needs more space.
  44    *
  45    * Note, that the key array always will be sorted, though we leave
  46    * the original arrays unaltered.
  47    *
  48    * @param match array of match values (case 2: ... case 7: ..., etc.)
  49    * @param targets the instructions to be branched to for each case
  50    * @param target the default target
  51    * @param max_gap maximum gap that may between case branches
  52    */
  53   public SWITCH(int[] match, InstructionHandle[] targets,
  54                 InstructionHandle target, int max_gap) {
  55     this.match   = (int[])match.clone();
  56     this.targets = (InstructionHandle[])targets.clone();
  57 
  58     if((match_length = match.length) < 2) // (almost) empty switch, or just default
  59       instruction = new TABLESWITCH(match, targets, target);
  60     else {
  61       sort(0, match_length - 1);
  62 
  63       if(matchIsOrdered(max_gap)) {
  64         fillup(max_gap, target);
  65 
  66         instruction = new TABLESWITCH(this.match, this.targets, target);
  67       }
  68       else
  69         instruction = new LOOKUPSWITCH(this.match, this.targets, target);
  70     }
  71   }
  72 
  73   public SWITCH(int[] match, InstructionHandle[] targets,
  74                 InstructionHandle target) {
  75     this(match, targets, target, 1);
  76   }
  77 
  78   private final void fillup(int max_gap, InstructionHandle target) {
  79     int                 max_size = match_length + match_length * max_gap;
  80     int[]               m_vec    = new int[max_size];
  81     InstructionHandle[] t_vec    = new InstructionHandle[max_size];
  82     int                 count    = 1;
  83 
  84     m_vec[0] = match[0];
  85     t_vec[0] = targets[0];
  86 
  87     for(int i=1; i < match_length; i++) {
  88       int prev = match[i-1];
  89       int gap  = match[i] - prev;
  90 
  91       for(int j=1; j < gap; j++) {
  92         m_vec[count] = prev + j;
  93         t_vec[count] = target;
  94         count++;
  95       }
  96 
  97       m_vec[count] = match[i];
  98       t_vec[count] = targets[i];
  99       count++;
 100     }
 101 
 102     match   = new int[count];
 103     targets = new InstructionHandle[count];
 104 
 105     System.arraycopy(m_vec, 0, match, 0, count);
 106     System.arraycopy(t_vec, 0, targets, 0, count);
 107   }
 108 
 109   /**
 110    * Sort match and targets array with QuickSort.
 111    */
 112   private final void sort(int l, int r) {
 113     int i = l, j = r;
 114     int h, m = match[(l + r) / 2];
 115     InstructionHandle h2;
 116 
 117     do {
 118       while(match[i] < m) i++;
 119       while(m < match[j]) j--;
 120 
 121       if(i <= j) {
 122         h=match[i]; match[i]=match[j]; match[j]=h; // Swap elements
 123         h2=targets[i]; targets[i]=targets[j]; targets[j]=h2; // Swap instructions, too
 124         i++; j--;
 125       }
 126     } while(i <= j);
 127 
 128     if(l < j) sort(l, j);
 129     if(i < r) sort(i, r);
 130   }
 131 
 132   /**
 133    * @return match is sorted in ascending order with no gap bigger than max_gap?
 134    */
 135   private final boolean matchIsOrdered(int max_gap) {
 136     for(int i=1; i < match_length; i++)
 137       if(match[i] - match[i-1] > max_gap)
 138         return false;
 139 
 140     return true;
 141   }
 142 
 143   public final InstructionList getInstructionList() {
 144     return new InstructionList(instruction);
 145   }
 146 
 147   public final Instruction getInstruction() {
 148     return instruction;
 149   }
 150 }