diff options
author | Paul Duffin <paulduffin@google.com> | 2015-01-19 12:46:40 +0000 |
---|---|---|
committer | Android Git Automerger <android-git-automerger@android.com> | 2015-01-19 12:46:40 +0000 |
commit | aab56800fcb95e9b1a2d653588b14158080cc6b4 (patch) | |
tree | 7365392c3ea77742021cf187acfd465f9bb774ab /guava/src/com/google/common/base/SmallCharMatcher.java | |
parent | 6fa98dbaae182b511fbeb331e08f5fb827715ea8 (diff) | |
parent | 84fb43aa6a1e752487f2624055ff26b1b6b7c043 (diff) | |
download | android_external_guava-aab56800fcb95e9b1a2d653588b14158080cc6b4.tar.gz android_external_guava-aab56800fcb95e9b1a2d653588b14158080cc6b4.tar.bz2 android_external_guava-aab56800fcb95e9b1a2d653588b14158080cc6b4.zip |
am 84fb43aa: Merge "Revert "Upgraded Guava to unmodified v14.0.1""
* commit '84fb43aa6a1e752487f2624055ff26b1b6b7c043':
Revert "Upgraded Guava to unmodified v14.0.1"
Diffstat (limited to 'guava/src/com/google/common/base/SmallCharMatcher.java')
-rw-r--r-- | guava/src/com/google/common/base/SmallCharMatcher.java | 155 |
1 files changed, 0 insertions, 155 deletions
diff --git a/guava/src/com/google/common/base/SmallCharMatcher.java b/guava/src/com/google/common/base/SmallCharMatcher.java deleted file mode 100644 index 10234c5..0000000 --- a/guava/src/com/google/common/base/SmallCharMatcher.java +++ /dev/null @@ -1,155 +0,0 @@ -/* - * Copyright (C) 2012 The Guava Authors - * - * 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 com.google.common.base; - -import com.google.common.annotations.GwtIncompatible; -import com.google.common.annotations.VisibleForTesting; -import com.google.common.base.CharMatcher.FastMatcher; - -import java.util.BitSet; - -/** - * An immutable version of CharMatcher for smallish sets of characters that uses a hash table - * with linear probing to check for matches. - * - * @author Christopher Swenson - */ -@GwtIncompatible("no precomputation is done in GWT") -final class SmallCharMatcher extends FastMatcher { - static final int MAX_SIZE = 1023; - private final char[] table; - private final boolean containsZero; - private final long filter; - - private SmallCharMatcher(char[] table, long filter, boolean containsZero, - String description) { - super(description); - this.table = table; - this.filter = filter; - this.containsZero = containsZero; - } - - private static final int C1 = 0xcc9e2d51; - private static final int C2 = 0x1b873593; - - /* - * This method was rewritten in Java from an intermediate step of the Murmur hash function in - * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp, which contained the - * following header: - * - * MurmurHash3 was written by Austin Appleby, and is placed in the public domain. The author - * hereby disclaims copyright to this source code. - */ - static int smear(int hashCode) { - return C2 * Integer.rotateLeft(hashCode * C1, 15); - } - - private boolean checkFilter(int c) { - return 1 == (1 & (filter >> c)); - } - - // This is all essentially copied from ImmutableSet, but we have to duplicate because - // of dependencies. - - // Represents how tightly we can pack things, as a maximum. - private static final double DESIRED_LOAD_FACTOR = 0.5; - - /** - * Returns an array size suitable for the backing array of a hash table that - * uses open addressing with linear probing in its implementation. The - * returned size is the smallest power of two that can hold setSize elements - * with the desired load factor. - */ - @VisibleForTesting static int chooseTableSize(int setSize) { - if (setSize == 1) { - return 2; - } - // Correct the size for open addressing to match desired load factor. - // Round up to the next highest power of 2. - int tableSize = Integer.highestOneBit(setSize - 1) << 1; - while (tableSize * DESIRED_LOAD_FACTOR < setSize) { - tableSize <<= 1; - } - return tableSize; - } - - @GwtIncompatible("java.util.BitSet") - static CharMatcher from(BitSet chars, String description) { - // Compute the filter. - long filter = 0; - int size = chars.cardinality(); - boolean containsZero = chars.get(0); - // Compute the hash table. - char[] table = new char[chooseTableSize(size)]; - int mask = table.length - 1; - for (int c = chars.nextSetBit(0); c != -1; c = chars.nextSetBit(c + 1)) { - // Compute the filter at the same time. - filter |= 1L << c; - int index = smear(c) & mask; - while (true) { - // Check for empty. - if (table[index] == 0) { - table[index] = (char) c; - break; - } - // Linear probing. - index = (index + 1) & mask; - } - } - return new SmallCharMatcher(table, filter, containsZero, description); - } - - @Override - public boolean matches(char c) { - if (c == 0) { - return containsZero; - } - if (!checkFilter(c)) { - return false; - } - int mask = table.length - 1; - int startingIndex = smear(c) & mask; - int index = startingIndex; - do { - // Check for empty. - if (table[index] == 0) { - return false; - // Check for match. - } else if (table[index] == c) { - return true; - } else { - // Linear probing. - index = (index + 1) & mask; - } - // Check to see if we wrapped around the whole table. - } while (index != startingIndex); - return false; - } - - @GwtIncompatible("java.util.BitSet") - @Override - void setBits(BitSet table) { - if (containsZero) { - table.set(0); - } - for (char c : this.table) { - if (c != 0) { - table.set(c); - } - } - } -} |