1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
/*
* 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);
}
}
}
}
|
