1 files changed, 414 insertions, 0 deletions
diff --git a/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/util/SFormsFastMapDirect.java b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/util/SFormsFastMapDirect.java
new file mode 100644
index 000000000000..996607a2bdbc
--- /dev/null
+++ b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/util/SFormsFastMapDirect.java
@@ -0,0 +1,414 @@
+/*
+ * Copyright 2000-2014 JetBrains s.r.o.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.jetbrains.java.decompiler.util;
+
+import org.jetbrains.java.decompiler.modules.decompiler.exps.VarExprent;
+import org.jetbrains.java.decompiler.util.FastSparseSetFactory.FastSparseSet;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map.Entry;
+import java.util.Set;
+
+public class SFormsFastMapDirect {
+
+  private int size;
+
+  @SuppressWarnings("unchecked") private FastSparseSet<Integer>[][] elements = new FastSparseSet[3][];
+
+  private int[][] next = new int[3][];
+
+  public SFormsFastMapDirect() {
+    this(true);
+  }
+
+  private SFormsFastMapDirect(boolean initialize) {
+    if (initialize) {
+      for (int i = 2; i >= 0; i--) {
+        @SuppressWarnings("unchecked") FastSparseSet<Integer>[] empty = new FastSparseSet[0];
+        elements[i] = empty;
+        next[i] = new int[0];
+      }
+    }
+  }
+
+  public SFormsFastMapDirect(SFormsFastMapDirect map) {
+    for (int i = 2; i >= 0; i--) {
+      FastSparseSet<Integer>[] arr = map.elements[i];
+      int[] arrnext = map.next[i];
+
+      int length = arr.length;
+      @SuppressWarnings("unchecked") FastSparseSet<Integer>[] arrnew = new FastSparseSet[length];
+      int[] arrnextnew = new int[length];
+
+      System.arraycopy(arr, 0, arrnew, 0, length);
+      System.arraycopy(arrnext, 0, arrnextnew, 0, length);
+
+      elements[i] = arrnew;
+      next[i] = arrnextnew;
+
+      size = map.size;
+    }
+  }
+
+  public SFormsFastMapDirect getCopy() {
+
+    SFormsFastMapDirect map = new SFormsFastMapDirect(false);
+    map.size = size;
+
+    FastSparseSet[][] mapelements = map.elements;
+    int[][] mapnext = map.next;
+
+    for (int i = 2; i >= 0; i--) {
+      FastSparseSet<Integer>[] arr = elements[i];
+      int length = arr.length;
+
+      if (length > 0) {
+        int[] arrnext = next[i];
+
+        @SuppressWarnings("unchecked") FastSparseSet<Integer>[] arrnew = new FastSparseSet[length];
+        int[] arrnextnew = new int[length];
+
+        System.arraycopy(arrnext, 0, arrnextnew, 0, length);
+
+        mapelements[i] = arrnew;
+        mapnext[i] = arrnextnew;
+
+        int pointer = 0;
+        do {
+          FastSparseSet<Integer> set = arr[pointer];
+          if (set != null) {
+            arrnew[pointer] = set.getCopy();
+          }
+
+          pointer = arrnext[pointer];
+        }
+        while (pointer != 0);
+      }
+      else {
+        mapelements[i] = new FastSparseSet[0];
+        mapnext[i] = new int[0];
+      }
+    }
+
+    return map;
+  }
+
+  public int size() {
+    return size;
+  }
+
+  public boolean isEmpty() {
+    return size == 0;
+  }
+
+  public void put(int key, FastSparseSet<Integer> value) {
+    putInternal(key, value, false);
+  }
+
+  public void remove(int key) {
+    putInternal(key, null, true);
+  }
+
+  public void removeAllFields() {
+    FastSparseSet<Integer>[] arr = elements[2];
+    int[] arrnext = next[2];
+
+    for (int i = arr.length - 1; i >= 0; i--) {
+      FastSparseSet<Integer> val = arr[i];
+      if (val != null) {
+        arr[i] = null;
+        size--;
+      }
+      arrnext[i] = 0;
+    }
+  }
+
+  public void putInternal(final int key, final FastSparseSet<Integer> value, boolean remove) {
+
+    int index = 0;
+    int ikey = key;
+    if (ikey < 0) {
+      index = 2;
+      ikey = -ikey;
+    }
+    else if (ikey >= VarExprent.STACK_BASE) {
+      index = 1;
+      ikey -= VarExprent.STACK_BASE;
+    }
+
+    FastSparseSet<Integer>[] arr = elements[index];
+    if (ikey >= arr.length) {
+      if (remove) {
+        return;
+      }
+      else {
+        arr = ensureCapacity(index, ikey + 1, false);
+      }
+    }
+
+    FastSparseSet<Integer> oldval = arr[ikey];
+    arr[ikey] = value;
+
+    int[] arrnext = next[index];
+
+    if (oldval == null && value != null) {
+      size++;
+      changeNext(arrnext, ikey, arrnext[ikey], ikey);
+    }
+    else if (oldval != null && value == null) {
+      size--;
+      changeNext(arrnext, ikey, ikey, arrnext[ikey]);
+    }
+  }
+
+  private static void changeNext(int[] arrnext, int key, int oldnext, int newnext) {
+    for (int i = key - 1; i >= 0; i--) {
+      if (arrnext[i] == oldnext) {
+        arrnext[i] = newnext;
+      }
+      else {
+        break;
+      }
+    }
+  }
+
+  public boolean containsKey(int key) {
+    return get(key) != null;
+  }
+
+  public FastSparseSet<Integer> get(int key) {
+
+    int index = 0;
+    if (key < 0) {
+      index = 2;
+      key = -key;
+    }
+    else if (key >= VarExprent.STACK_BASE) {
+      index = 1;
+      key -= VarExprent.STACK_BASE;
+    }
+
+    FastSparseSet<Integer>[] arr = elements[index];
+
+    if (key < arr.length) {
+      return arr[key];
+    }
+    return null;
+  }
+
+  public void complement(SFormsFastMapDirect map) {
+
+    for (int i = 2; i >= 0; i--) {
+      FastSparseSet<Integer>[] lstOwn = elements[i];
+
+      if (lstOwn.length == 0) {
+        continue;
+      }
+
+      FastSparseSet<Integer>[] lstExtern = map.elements[i];
+      int[] arrnext = next[i];
+
+      int pointer = 0;
+      do {
+        FastSparseSet<Integer> first = lstOwn[pointer];
+
+        if (first != null) {
+          if (pointer >= lstExtern.length) {
+            break;
+          }
+          FastSparseSet<Integer> second = lstExtern[pointer];
+
+          if (second != null) {
+            first.complement(second);
+            if (first.isEmpty()) {
+              lstOwn[pointer] = null;
+              size--;
+              changeNext(arrnext, pointer, pointer, arrnext[pointer]);
+            }
+          }
+        }
+
+        pointer = arrnext[pointer];
+      }
+      while (pointer != 0);
+    }
+  }
+
+  public void intersection(SFormsFastMapDirect map) {
+
+    for (int i = 2; i >= 0; i--) {
+      FastSparseSet<Integer>[] lstOwn = elements[i];
+
+      if (lstOwn.length == 0) {
+        continue;
+      }
+
+      FastSparseSet<Integer>[] lstExtern = map.elements[i];
+      int[] arrnext = next[i];
+
+      int pointer = 0;
+      do {
+        FastSparseSet<Integer> first = lstOwn[pointer];
+
+        if (first != null) {
+          FastSparseSet<Integer> second = null;
+          if (pointer < lstExtern.length) {
+            second = lstExtern[pointer];
+          }
+
+          if (second != null) {
+            first.intersection(second);
+          }
+
+          if (second == null || first.isEmpty()) {
+            lstOwn[pointer] = null;
+            size--;
+            changeNext(arrnext, pointer, pointer, arrnext[pointer]);
+          }
+        }
+
+        pointer = arrnext[pointer];
+      }
+      while (pointer != 0);
+    }
+  }
+
+  public void union(SFormsFastMapDirect map) {
+
+    for (int i = 2; i >= 0; i--) {
+      FastSparseSet<Integer>[] lstExtern = map.elements[i];
+
+      if (lstExtern.length == 0) {
+        continue;
+      }
+
+      FastSparseSet<Integer>[] lstOwn = elements[i];
+      int[] arrnext = next[i];
+      int[] arrnextExtern = map.next[i];
+
+      int pointer = 0;
+      do {
+        if (pointer >= lstOwn.length) {
+          lstOwn = ensureCapacity(i, lstExtern.length, true);
+          arrnext = next[i];
+        }
+
+        FastSparseSet<Integer> second = lstExtern[pointer];
+
+        if (second != null) {
+          FastSparseSet<Integer> first = lstOwn[pointer];
+
+          if (first == null) {
+            lstOwn[pointer] = second.getCopy();
+            size++;
+            changeNext(arrnext, pointer, arrnext[pointer], pointer);
+          }
+          else {
+            first.union(second);
+          }
+        }
+
+        pointer = arrnextExtern[pointer];
+      }
+      while (pointer != 0);
+    }
+  }
+
+  public String toString() {
+
+    StringBuilder buffer = new StringBuilder("{");
+
+    List<Entry<Integer, FastSparseSet<Integer>>> lst = entryList();
+    if (lst != null) {
+      boolean first = true;
+      for (Entry<Integer, FastSparseSet<Integer>> entry : lst) {
+        if (!first) {
+          buffer.append(", ");
+        }
+        else {
+          first = false;
+        }
+
+        Set<Integer> set = entry.getValue().toPlainSet();
+        buffer.append(entry.getKey()).append("={").append(set.toString()).append("}");
+      }
+    }
+
+    buffer.append("}");
+    return buffer.toString();
+  }
+
+  public List<Entry<Integer, FastSparseSet<Integer>>> entryList() {
+    List<Entry<Integer, FastSparseSet<Integer>>> list = new ArrayList<Entry<Integer, FastSparseSet<Integer>>>();
+
+    for (int i = 2; i >= 0; i--) {
+      int ikey = 0;
+      for (final FastSparseSet<Integer> ent : elements[i]) {
+        if (ent != null) {
+          final int key = i == 0 ? ikey : (i == 1 ? ikey + VarExprent.STACK_BASE : -ikey);
+
+          list.add(new Entry<Integer, FastSparseSet<Integer>>() {
+
+            private Integer var = key;
+            private FastSparseSet<Integer> val = ent;
+
+            public Integer getKey() {
+              return var;
+            }
+
+            public FastSparseSet<Integer> getValue() {
+              return val;
+            }
+
+            public FastSparseSet<Integer> setValue(FastSparseSet<Integer> newvalue) {
+              return null;
+            }
+          });
+        }
+
+        ikey++;
+      }
+    }
+
+    return list;
+  }
+
+  private FastSparseSet<Integer>[] ensureCapacity(int index, int size, boolean exact) {
+
+    FastSparseSet<Integer>[] arr = elements[index];
+    int[] arrnext = next[index];
+
+    int minsize = size;
+    if (!exact) {
+      minsize = 2 * arr.length / 3 + 1;
+      if (size > minsize) {
+        minsize = size;
+      }
+    }
+
+    @SuppressWarnings("unchecked") FastSparseSet<Integer>[] arrnew = new FastSparseSet[minsize];
+    System.arraycopy(arr, 0, arrnew, 0, arr.length);
+
+    int[] arrnextnew = new int[minsize];
+    System.arraycopy(arrnext, 0, arrnextnew, 0, arrnext.length);
+
+    elements[index] = arrnew;
+    next[index] = arrnextnew;
+
+    return arrnew;
+  }
+}