Coverage Summary for Class: SmallCharMatcher (com.google.common.base)

1 /*
2  * Copyright (C) 2012 The Guava Authors
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5  * in compliance with the License. You may obtain a copy of the License at
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software distributed under the License
10  * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11  * or implied. See the License for the specific language governing permissions and limitations under
12  * the License.
13  */
14 
15 package com.google.common.base;
16 
17 import com.google.common.annotations.GwtIncompatible;
18 import com.google.common.annotations.VisibleForTesting;
19 import com.google.common.base.CharMatcher.NamedFastMatcher;
20 import java.util.BitSet;
21 
22 /**
23  * An immutable version of CharMatcher for smallish sets of characters that uses a hash table with
24  * linear probing to check for matches.
25  *
26  * @author Christopher Swenson
27  */
28 @GwtIncompatible // no precomputation is done in GWT
29 @ElementTypesAreNonnullByDefault
30 final class SmallCharMatcher extends NamedFastMatcher {
31   static final int MAX_SIZE = 1023;
32   private final char[] table;
33   private final boolean containsZero;
34   private final long filter;
35 
36   private SmallCharMatcher(char[] table, long filter, boolean containsZero, String description) {
37     super(description);
38     this.table = table;
39     this.filter = filter;
40     this.containsZero = containsZero;
41   }
42 
43   private static final int C1 = 0xcc9e2d51;
44   private static final int C2 = 0x1b873593;
45 
46   /*
47    * This method was rewritten in Java from an intermediate step of the Murmur hash function in
48    * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp, which contained the
49    * following header:
50    *
51    * MurmurHash3 was written by Austin Appleby, and is placed in the public domain. The author
52    * hereby disclaims copyright to this source code.
53    */
54   static int smear(int hashCode) {
55     return C2 * Integer.rotateLeft(hashCode * C1, 15);
56   }
57 
58   private boolean checkFilter(int c) {
59     return 1 == (1 & (filter >> c));
60   }
61 
62   // This is all essentially copied from ImmutableSet, but we have to duplicate because
63   // of dependencies.
64 
65   // Represents how tightly we can pack things, as a maximum.
66   private static final double DESIRED_LOAD_FACTOR = 0.5;
67 
68   /**
69    * Returns an array size suitable for the backing array of a hash table that uses open addressing
70    * with linear probing in its implementation. The returned size is the smallest power of two that
71    * can hold setSize elements with the desired load factor.
72    */
73   @VisibleForTesting
74   static int chooseTableSize(int setSize) {
75     if (setSize == 1) {
76       return 2;
77     }
78     // Correct the size for open addressing to match desired load factor.
79     // Round up to the next highest power of 2.
80     int tableSize = Integer.highestOneBit(setSize - 1) << 1;
81     while (tableSize * DESIRED_LOAD_FACTOR < setSize) {
82       tableSize <<= 1;
83     }
84     return tableSize;
85   }
86 
87   static CharMatcher from(BitSet chars, String description) {
88     // Compute the filter.
89     long filter = 0;
90     int size = chars.cardinality();
91     boolean containsZero = chars.get(0);
92     // Compute the hash table.
93     char[] table = new char[chooseTableSize(size)];
94     int mask = table.length - 1;
95     for (int c = chars.nextSetBit(0); c != -1; c = chars.nextSetBit(c + 1)) {
96       // Compute the filter at the same time.
97       filter |= 1L << c;
98       int index = smear(c) & mask;
99       while (true) {
100         // Check for empty.
101         if (table[index] == 0) {
102           table[index] = (char) c;
103           break;
104         }
105         // Linear probing.
106         index = (index + 1) & mask;
107       }
108     }
109     return new SmallCharMatcher(table, filter, containsZero, description);
110   }
111 
112   @Override
113   public boolean matches(char c) {
114     if (c == 0) {
115       return containsZero;
116     }
117     if (!checkFilter(c)) {
118       return false;
119     }
120     int mask = table.length - 1;
121     int startingIndex = smear(c) & mask;
122     int index = startingIndex;
123     do {
124       if (table[index] == 0) { // Check for empty.
125         return false;
126       } else if (table[index] == c) { // Check for match.
127         return true;
128       } else { // Linear probing.
129         index = (index + 1) & mask;
130       }
131       // Check to see if we wrapped around the whole table.
132     } while (index != startingIndex);
133     return false;
134   }
135 
136   @Override
137   void setBits(BitSet table) {
138     if (containsZero) {
139       table.set(0);
140     }
141     for (char c : this.table) {
142       if (c != 0) {
143         table.set(c);
144       }
145     }
146   }
147 }