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
|
/*
* 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.GwtCompatible;
import com.google.common.annotations.VisibleForTesting;
/**
* An immutable version of CharMatcher for medium-sized sets of characters that uses a hash table
* with linear probing to check for matches.
*
* @author Christopher Swenson
*/
@GwtCompatible
final class MediumCharMatcher extends CharMatcher {
static final int MAX_SIZE = 1023;
private final char[] table;
private final boolean containsZero;
private final long filter;
private MediumCharMatcher(char[] table, long filter, boolean containsZero,
String description) {
super(description);
this.table = table;
this.filter = filter;
this.containsZero = containsZero;
}
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;
}
// This method is thread-safe, since if any two threads execute it simultaneously, all
// that will happen is that they compute the same data structure twice, but nothing will ever
// be incorrect.
@Override
public CharMatcher precomputed() {
return this;
}
static CharMatcher from(char[] chars, String description) {
// Compute the filter.
long filter = 0;
int size = chars.length;
boolean containsZero = (chars[0] == 0);
// Compute the filter.
for (char c : chars) {
filter |= 1L << c;
}
// Compute the hash table.
char[] table = new char[chooseTableSize(size)];
int mask = table.length - 1;
for (char c : chars) {
int index = c & mask;
while (true) {
// Check for empty.
if (table[index] == 0) {
table[index] = c;
break;
}
// Linear probing.
index = (index + 1) & mask;
}
}
return new MediumCharMatcher(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 = 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;
}
}
|
