| /* |
| * 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; |
| } |
| } |