diff options
Diffstat (limited to 'src/org/jetbrains/java/decompiler/util/FastSparseSetFactory.java')
-rw-r--r-- | src/org/jetbrains/java/decompiler/util/FastSparseSetFactory.java | 1071 |
1 files changed, 538 insertions, 533 deletions
diff --git a/src/org/jetbrains/java/decompiler/util/FastSparseSetFactory.java b/src/org/jetbrains/java/decompiler/util/FastSparseSetFactory.java index 352dc2a..301a1ff 100644 --- a/src/org/jetbrains/java/decompiler/util/FastSparseSetFactory.java +++ b/src/org/jetbrains/java/decompiler/util/FastSparseSetFactory.java @@ -1,17 +1,18 @@ /* - * Fernflower - The Analytical Java Decompiler - * http://www.reversed-java.com + * Copyright 2000-2014 JetBrains s.r.o. * - * (C) 2008 - 2010, Stiver + * 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 * - * This software is NEITHER public domain NOR free software - * as per GNU License. See license.txt for more details. + * http://www.apache.org/licenses/LICENSE-2.0 * - * This software is distributed WITHOUT ANY WARRANTY; without - * even the implied warranty of MERCHANTABILITY or FITNESS FOR - * A PARTICULAR PURPOSE. + * 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 java.util.Collection; @@ -21,529 +22,533 @@ import java.util.Set; public class FastSparseSetFactory<E> { - private VBStyleCollection<int[], E> colValuesInternal = new VBStyleCollection<int[], E>(); - - private int lastBlock; - - private int lastMask; - - public FastSparseSetFactory(Collection<E> set) { - - int block = -1; - int mask = -1; - int index = 0; - - for(E element : set) { - - block = index / 32; - - if(index % 32 == 0) { - mask = 1; - } else { - mask <<= 1; - } - - colValuesInternal.putWithKey(new int[] {block, mask}, element); - - index++; - } - - lastBlock = block; - lastMask = mask; - } - - private int[] addElement(E element) { - - if(lastMask == -1 || lastMask == 0x80000000) { - lastMask = 1; - lastBlock++; - } else { - lastMask <<= 1; - } - - int[] pointer = new int[] {lastBlock, lastMask}; - colValuesInternal.putWithKey(pointer, element); - - return pointer; - } - - public FastSparseSet<E> spawnEmptySet() { - return new FastSparseSet<E>(this); - } - - public int getLastBlock() { - return lastBlock; - } - - public int getLastMask() { - return lastMask; - } - - private VBStyleCollection<int[], E> getInternalValuesCollection() { - return colValuesInternal; - } - - - public static class FastSparseSet<E> implements Iterable<E> { - - private FastSparseSetFactory<E> factory; - - private VBStyleCollection<int[], E> colValuesInternal; - - private int[] data; - private int[] next; - - private FastSparseSet(FastSparseSetFactory<E> factory) { - this.factory = factory; - this.colValuesInternal = factory.getInternalValuesCollection(); - - int length = factory.getLastBlock()+1; - this.data = new int[length]; - this.next = new int[length]; - } - - private FastSparseSet(FastSparseSetFactory<E> factory, int[] data, int[] next) { - this.factory = factory; - this.colValuesInternal = factory.getInternalValuesCollection(); - - this.data = data; - this.next = next; - } - - public FastSparseSet<E> getCopy() { - - int arrlength = data.length; - int[] cpdata = new int[arrlength]; - int[] cpnext = new int[arrlength]; - - System.arraycopy(data, 0, cpdata, 0, arrlength); - System.arraycopy(next, 0, cpnext, 0, arrlength); - - FastSparseSet<E> copy = new FastSparseSet<E>(factory, cpdata, cpnext); - - return copy; - } - - private int[] ensureCapacity(int index) { - - int newlength = data.length; - if(newlength == 0) { - newlength = 1; - } - - while(newlength <= index) { - newlength *=2; - } - - int[] newdata = new int[newlength]; - System.arraycopy(data, 0, newdata, 0, data.length); - data = newdata; - - int[] newnext = new int[newlength]; - System.arraycopy(next, 0, newnext, 0, next.length); - next = newnext; - - return newdata; - } - - public void add(E element) { - int[] index = colValuesInternal.getWithKey(element); - - if(index == null) { - index = factory.addElement(element); - } - - int block = index[0]; - if(block >= data.length) { - ensureCapacity(block); - } - - data[block] |= index[1]; - - changeNext(next, block, next[block], block); - } - - public void setAllElements() { - - int lastblock = factory.getLastBlock(); - int lastmask = factory.getLastMask(); - - if(lastblock >= data.length) { - ensureCapacity(lastblock); - } - - for(int i=lastblock-1;i>=0;i--) { - data[i] = 0xFFFFFFFF; - next[i] = i+1; - } - - data[lastblock] = lastmask | (lastmask-1); - next[lastblock] = 0; - } - - public void addAll(Set<E> set) { - for(E element : set) { - add(element); - } - } - - public void remove(E element) { - int[] index = colValuesInternal.getWithKey(element); - - if(index == null) { - index = factory.addElement(element); - } - - int block = index[0]; - if(block < data.length) { - data[block] &= ~index[1]; - - if(data[block] == 0) { - changeNext(next, block, block, next[block]); - } - } - } - - public void removeAll(Set<E> set) { - for(E element : set) { - remove(element); - } - } - - public boolean contains(E element) { - int[] index = colValuesInternal.getWithKey(element); - - if(index == null) { - index = factory.addElement(element); - } - - return index[0] >= data.length?false:((data[index[0]] & index[1]) != 0); - } - - public boolean contains(FastSparseSet<E> set) { - int[] extdata = set.getData(); - int[] intdata = data; - - int minlength = Math.min(extdata.length, intdata.length); - - for(int i=minlength-1;i>=0;i--) { - if((extdata[i] & ~intdata[i]) != 0) { - return false; - } - } - - for(int i=extdata.length-1;i>=minlength;i--) { - if(extdata[i] != 0) { - return false; - } - } - - return true; - } - - private void setNext() { - - int link = 0; - for(int i=data.length-1;i>=0;i--) { - next[i] = link; - if(data[i] != 0) { - link = i; - } - } - } - - private 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 void union(FastSparseSet<E> set) { - - int[] extdata = set.getData(); - int[] extnext = set.getNext(); - int[] intdata = data; - int intlength = intdata.length; - - int pointer = 0; - do { - if(pointer >= intlength) { - intdata = ensureCapacity(extdata.length - 1); - } - - boolean nextrec = (intdata[pointer] == 0); - intdata[pointer] |= extdata[pointer]; - - if(nextrec) { - changeNext(next, pointer, next[pointer], pointer); - } - - pointer = extnext[pointer]; - - } while(pointer!=0); - } - - public void intersection(FastSparseSet<E> set) { - int[] extdata = set.getData(); - int[] intdata = data; - - int minlength = Math.min(extdata.length, intdata.length); - - for(int i=minlength-1;i>=0;i--) { - intdata[i] &= extdata[i]; - } - - for(int i=intdata.length-1;i>=minlength;i--) { - intdata[i] = 0; - } - - setNext(); - } - - public void symdiff(FastSparseSet<E> set) { - int[] extdata = set.getData(); - int[] intdata = data; - - int minlength = Math.min(extdata.length, intdata.length); - - for(int i=minlength-1;i>=0;i--) { - intdata[i] ^= extdata[i]; - } - - boolean expanded = false; - for(int i=extdata.length-1;i>=minlength;i--) { - if(extdata[i] != 0) { - if(!expanded) { - intdata = ensureCapacity(extdata.length - 1); - } - intdata[i] = extdata[i]; - } - } - - setNext(); - } - - public void complement(FastSparseSet<E> set) { - - int[] extdata = set.getData(); - int[] intdata = data; - int extlength = extdata.length; - - int pointer = 0; - do { - if(pointer >= extlength) { - break; - } - - intdata[pointer] &= ~extdata[pointer]; - if(intdata[pointer] == 0) { - changeNext(next, pointer, pointer, next[pointer]); - } - - pointer = next[pointer]; - - } while(pointer!=0); - } - - - public boolean equals(Object o) { - if(o == this) return true; - if(o == null || !(o instanceof FastSparseSet)) return false; - - int[] longdata = ((FastSparseSet)o).getData(); - int[] shortdata = data; - - if(data.length > longdata.length) { - shortdata = longdata; - longdata = data; - } - - for(int i=shortdata.length-1;i>=0;i--) { - if(shortdata[i] != longdata[i]) { - return false; - } - } - - for(int i=longdata.length-1;i>=shortdata.length;i--) { - if(longdata[i] != 0) { - return false; - } - } - - return true; - } - - public int getCardinality() { - - boolean found = false; - int[] intdata = data; - - for(int i=intdata.length-1;i>=0;i--) { - int block = intdata[i]; - if(block != 0) { - if(found) { - return 2; - } else { - if ((block & (block-1)) == 0) { - found = true; - } else { - return 2; - } - } - } - } - - return found?1:0; - } - - public boolean isEmpty() { - return data.length == 0 || (next[0] == 0 && data[0] == 0); - } - - public Iterator<E> iterator() { - return new FastSparseSetIterator<E>(this); - } - - public Set<E> toPlainSet() { - HashSet<E> set = new HashSet<E>(); - - int[] intdata = data; - - int size = data.length*32; - if(size > colValuesInternal.size()) { - size = colValuesInternal.size(); - } - - for(int i=size-1;i>=0;i--) { - int[] index = colValuesInternal.get(i); - - if((intdata[index[0]] & index[1]) != 0) { - set.add(colValuesInternal.getKey(i)); - } - } - - return set; - } - - public String toString() { - return toPlainSet().toString(); - } - - public String toBinary() { - - StringBuilder buffer = new StringBuilder(); - int[] intdata = data; - - for(int i=0;i<intdata.length;i++) { - buffer.append(" ").append(Integer.toBinaryString(intdata[i])); - } - - return buffer.toString(); - } - - private int[] getData() { - return data; - } - - private int[] getNext() { - return next; - } - - public int[] getLoad() { - int[] intdata = data; - int notempty = 0; - - for(int i=0;i<intdata.length;i++) { - if(intdata[i] != 0) { - notempty++; - } - } - - return new int[]{intdata.length, notempty}; - } - - public FastSparseSetFactory<E> getFactory() { - return factory; - } - } - - public static class FastSparseSetIterator<E> implements Iterator<E> { - - private VBStyleCollection<int[], E> colValuesInternal; - private int[] data; - private int[] next; - private int size; - - private int pointer = -1; - private int next_pointer = -1; - - private FastSparseSetIterator(FastSparseSet<E> set) { - colValuesInternal = set.getFactory().getInternalValuesCollection(); - data = set.getData(); - next = set.getNext(); - size = colValuesInternal.size(); - } - - private int getNextIndex(int index) { - - index++; - int bindex = index >>> 5; - int dindex = index & 0x1F; - - while(bindex < data.length) { - int block = data[bindex]; - - if(block != 0) { - block >>>= dindex; - while(dindex < 32) { - if((block & 1) != 0) { - return (bindex << 5) + dindex; - } - block >>>= 1; - dindex++; - } - } - - dindex = 0; - bindex = next[bindex]; - - if(bindex == 0) { - break; - } - } - - return -1; - } - - public boolean hasNext() { - next_pointer = getNextIndex(pointer); - return (next_pointer >= 0); - } - - public E next() { - if(next_pointer >= 0) { - pointer = next_pointer; - } else { - pointer = getNextIndex(pointer); - if(pointer == -1) { - pointer = size; - } - } - - next_pointer = -1; - return pointer<size?colValuesInternal.getKey(pointer):null; - } - - public void remove() { - int[] index = colValuesInternal.get(pointer); - data[index[0]] &= ~index[1]; - } - - } - + private VBStyleCollection<int[], E> colValuesInternal = new VBStyleCollection<int[], E>(); + + private int lastBlock; + + private int lastMask; + + public FastSparseSetFactory(Collection<E> set) { + + int block = -1; + int mask = -1; + int index = 0; + + for (E element : set) { + + block = index / 32; + + if (index % 32 == 0) { + mask = 1; + } + else { + mask <<= 1; + } + + colValuesInternal.putWithKey(new int[]{block, mask}, element); + + index++; + } + + lastBlock = block; + lastMask = mask; + } + + private int[] addElement(E element) { + + if (lastMask == -1 || lastMask == 0x80000000) { + lastMask = 1; + lastBlock++; + } + else { + lastMask <<= 1; + } + + int[] pointer = new int[]{lastBlock, lastMask}; + colValuesInternal.putWithKey(pointer, element); + + return pointer; + } + + public FastSparseSet<E> spawnEmptySet() { + return new FastSparseSet<E>(this); + } + + public int getLastBlock() { + return lastBlock; + } + + public int getLastMask() { + return lastMask; + } + + private VBStyleCollection<int[], E> getInternalValuesCollection() { + return colValuesInternal; + } + + + public static class FastSparseSet<E> implements Iterable<E> { + + private FastSparseSetFactory<E> factory; + + private VBStyleCollection<int[], E> colValuesInternal; + + private int[] data; + private int[] next; + + private FastSparseSet(FastSparseSetFactory<E> factory) { + this.factory = factory; + this.colValuesInternal = factory.getInternalValuesCollection(); + + int length = factory.getLastBlock() + 1; + this.data = new int[length]; + this.next = new int[length]; + } + + private FastSparseSet(FastSparseSetFactory<E> factory, int[] data, int[] next) { + this.factory = factory; + this.colValuesInternal = factory.getInternalValuesCollection(); + + this.data = data; + this.next = next; + } + + public FastSparseSet<E> getCopy() { + + int arrlength = data.length; + int[] cpdata = new int[arrlength]; + int[] cpnext = new int[arrlength]; + + System.arraycopy(data, 0, cpdata, 0, arrlength); + System.arraycopy(next, 0, cpnext, 0, arrlength); + + FastSparseSet<E> copy = new FastSparseSet<E>(factory, cpdata, cpnext); + + return copy; + } + + private int[] ensureCapacity(int index) { + + int newlength = data.length; + if (newlength == 0) { + newlength = 1; + } + + while (newlength <= index) { + newlength *= 2; + } + + int[] newdata = new int[newlength]; + System.arraycopy(data, 0, newdata, 0, data.length); + data = newdata; + + int[] newnext = new int[newlength]; + System.arraycopy(next, 0, newnext, 0, next.length); + next = newnext; + + return newdata; + } + + public void add(E element) { + int[] index = colValuesInternal.getWithKey(element); + + if (index == null) { + index = factory.addElement(element); + } + + int block = index[0]; + if (block >= data.length) { + ensureCapacity(block); + } + + data[block] |= index[1]; + + changeNext(next, block, next[block], block); + } + + public void setAllElements() { + + int lastblock = factory.getLastBlock(); + int lastmask = factory.getLastMask(); + + if (lastblock >= data.length) { + ensureCapacity(lastblock); + } + + for (int i = lastblock - 1; i >= 0; i--) { + data[i] = 0xFFFFFFFF; + next[i] = i + 1; + } + + data[lastblock] = lastmask | (lastmask - 1); + next[lastblock] = 0; + } + + public void addAll(Set<E> set) { + for (E element : set) { + add(element); + } + } + + public void remove(E element) { + int[] index = colValuesInternal.getWithKey(element); + + if (index == null) { + index = factory.addElement(element); + } + + int block = index[0]; + if (block < data.length) { + data[block] &= ~index[1]; + + if (data[block] == 0) { + changeNext(next, block, block, next[block]); + } + } + } + + public void removeAll(Set<E> set) { + for (E element : set) { + remove(element); + } + } + + public boolean contains(E element) { + int[] index = colValuesInternal.getWithKey(element); + + if (index == null) { + index = factory.addElement(element); + } + + return index[0] >= data.length ? false : ((data[index[0]] & index[1]) != 0); + } + + public boolean contains(FastSparseSet<E> set) { + int[] extdata = set.getData(); + int[] intdata = data; + + int minlength = Math.min(extdata.length, intdata.length); + + for (int i = minlength - 1; i >= 0; i--) { + if ((extdata[i] & ~intdata[i]) != 0) { + return false; + } + } + + for (int i = extdata.length - 1; i >= minlength; i--) { + if (extdata[i] != 0) { + return false; + } + } + + return true; + } + + private void setNext() { + + int link = 0; + for (int i = data.length - 1; i >= 0; i--) { + next[i] = link; + if (data[i] != 0) { + link = i; + } + } + } + + private 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 void union(FastSparseSet<E> set) { + + int[] extdata = set.getData(); + int[] extnext = set.getNext(); + int[] intdata = data; + int intlength = intdata.length; + + int pointer = 0; + do { + if (pointer >= intlength) { + intdata = ensureCapacity(extdata.length - 1); + } + + boolean nextrec = (intdata[pointer] == 0); + intdata[pointer] |= extdata[pointer]; + + if (nextrec) { + changeNext(next, pointer, next[pointer], pointer); + } + + pointer = extnext[pointer]; + } + while (pointer != 0); + } + + public void intersection(FastSparseSet<E> set) { + int[] extdata = set.getData(); + int[] intdata = data; + + int minlength = Math.min(extdata.length, intdata.length); + + for (int i = minlength - 1; i >= 0; i--) { + intdata[i] &= extdata[i]; + } + + for (int i = intdata.length - 1; i >= minlength; i--) { + intdata[i] = 0; + } + + setNext(); + } + + public void symdiff(FastSparseSet<E> set) { + int[] extdata = set.getData(); + int[] intdata = data; + + int minlength = Math.min(extdata.length, intdata.length); + + for (int i = minlength - 1; i >= 0; i--) { + intdata[i] ^= extdata[i]; + } + + boolean expanded = false; + for (int i = extdata.length - 1; i >= minlength; i--) { + if (extdata[i] != 0) { + if (!expanded) { + intdata = ensureCapacity(extdata.length - 1); + } + intdata[i] = extdata[i]; + } + } + + setNext(); + } + + public void complement(FastSparseSet<E> set) { + + int[] extdata = set.getData(); + int[] intdata = data; + int extlength = extdata.length; + + int pointer = 0; + do { + if (pointer >= extlength) { + break; + } + + intdata[pointer] &= ~extdata[pointer]; + if (intdata[pointer] == 0) { + changeNext(next, pointer, pointer, next[pointer]); + } + + pointer = next[pointer]; + } + while (pointer != 0); + } + + + public boolean equals(Object o) { + if (o == this) return true; + if (o == null || !(o instanceof FastSparseSet)) return false; + + int[] longdata = ((FastSparseSet)o).getData(); + int[] shortdata = data; + + if (data.length > longdata.length) { + shortdata = longdata; + longdata = data; + } + + for (int i = shortdata.length - 1; i >= 0; i--) { + if (shortdata[i] != longdata[i]) { + return false; + } + } + + for (int i = longdata.length - 1; i >= shortdata.length; i--) { + if (longdata[i] != 0) { + return false; + } + } + + return true; + } + + public int getCardinality() { + + boolean found = false; + int[] intdata = data; + + for (int i = intdata.length - 1; i >= 0; i--) { + int block = intdata[i]; + if (block != 0) { + if (found) { + return 2; + } + else { + if ((block & (block - 1)) == 0) { + found = true; + } + else { + return 2; + } + } + } + } + + return found ? 1 : 0; + } + + public boolean isEmpty() { + return data.length == 0 || (next[0] == 0 && data[0] == 0); + } + + public Iterator<E> iterator() { + return new FastSparseSetIterator<E>(this); + } + + public Set<E> toPlainSet() { + HashSet<E> set = new HashSet<E>(); + + int[] intdata = data; + + int size = data.length * 32; + if (size > colValuesInternal.size()) { + size = colValuesInternal.size(); + } + + for (int i = size - 1; i >= 0; i--) { + int[] index = colValuesInternal.get(i); + + if ((intdata[index[0]] & index[1]) != 0) { + set.add(colValuesInternal.getKey(i)); + } + } + + return set; + } + + public String toString() { + return toPlainSet().toString(); + } + + public String toBinary() { + + StringBuilder buffer = new StringBuilder(); + int[] intdata = data; + + for (int i = 0; i < intdata.length; i++) { + buffer.append(" ").append(Integer.toBinaryString(intdata[i])); + } + + return buffer.toString(); + } + + private int[] getData() { + return data; + } + + private int[] getNext() { + return next; + } + + public int[] getLoad() { + int[] intdata = data; + int notempty = 0; + + for (int i = 0; i < intdata.length; i++) { + if (intdata[i] != 0) { + notempty++; + } + } + + return new int[]{intdata.length, notempty}; + } + + public FastSparseSetFactory<E> getFactory() { + return factory; + } + } + + public static class FastSparseSetIterator<E> implements Iterator<E> { + + private VBStyleCollection<int[], E> colValuesInternal; + private int[] data; + private int[] next; + private int size; + + private int pointer = -1; + private int next_pointer = -1; + + private FastSparseSetIterator(FastSparseSet<E> set) { + colValuesInternal = set.getFactory().getInternalValuesCollection(); + data = set.getData(); + next = set.getNext(); + size = colValuesInternal.size(); + } + + private int getNextIndex(int index) { + + index++; + int bindex = index >>> 5; + int dindex = index & 0x1F; + + while (bindex < data.length) { + int block = data[bindex]; + + if (block != 0) { + block >>>= dindex; + while (dindex < 32) { + if ((block & 1) != 0) { + return (bindex << 5) + dindex; + } + block >>>= 1; + dindex++; + } + } + + dindex = 0; + bindex = next[bindex]; + + if (bindex == 0) { + break; + } + } + + return -1; + } + + public boolean hasNext() { + next_pointer = getNextIndex(pointer); + return (next_pointer >= 0); + } + + public E next() { + if (next_pointer >= 0) { + pointer = next_pointer; + } + else { + pointer = getNextIndex(pointer); + if (pointer == -1) { + pointer = size; + } + } + + next_pointer = -1; + return pointer < size ? colValuesInternal.getKey(pointer) : null; + } + + public void remove() { + int[] index = colValuesInternal.get(pointer); + data[index[0]] &= ~index[1]; + } + } } |