diff options
Diffstat (limited to 'plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/util/SFormsFastMapDirect.java')
-rw-r--r-- | plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/util/SFormsFastMapDirect.java | 414 |
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; + } +} |