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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
|
/*
* Copyright (C) 2002-2024 Sebastiano Vigna
*
* 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 PACKAGE;
import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
import java.io.Serializable;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock.ReadLock;
import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock;
/** A concurrent counting map. The map is made by a number of <em>stripes</em> (instances of {@link Object2IntOpenHashMap})
* which are accessed independently
* using a {@link ReentrantReadWriteLock}. Only one thread can write in a stripe at a time, but different stripes
* can be modified independently and read access can happen concurrently on each stripe.
*
* <p>The collection view methods ({@link #entrySet()} and similar} are currently not supported, and will throw
* {@link UnsupportedOperationException}
*
* @param <K> the type of keys.
*/
public class STRIPED_OPEN_HASH_MAP KEY_VALUE_GENERIC extends ABSTRACT_MAP KEY_VALUE_GENERIC implements java.io.Serializable, Cloneable {
private static final long serialVersionUID = 1L;
/** The stripes. Keys are distributed among them using the lower bits of their {@link Object#hashCode()}. */
private final OPEN_HASH_MAP KEY_VALUE_GENERIC[] map;
/** An array of locks parallel to {@link #map}, protecting each stripe. */
private final transient ReentrantReadWriteLock[] lock;
/** {@link #map map.length} − 1, cached. */
private final int mask;
/** Creates a new concurrent counting map with concurrency level equal to {@link Runtime#availableProcessors()}. */
public STRIPED_OPEN_HASH_MAP() {
this(Runtime.getRuntime().availableProcessors());
}
/** Creates a new concurrent counting map.
*
* @param concurrencyLevel the number of stripes (it will be {@linkplain Integer#highestOneBit(int) forced to be a power of two}); ideally, as large as the number of threads that will ever access
* this map, but higher values require more space.
*/
SUPPRESS_WARNINGS_KEY_UNCHECKED
public STRIPED_OPEN_HASH_MAP(final int concurrencyLevel) {
map = new OPEN_HASH_MAP[Integer.highestOneBit(concurrencyLevel)];
lock = new ReentrantReadWriteLock[map.length];
for(int i = map.length; i-- != 0;) {
map[i] = new OPEN_HASH_MAP KEY_VALUE_GENERIC_DIAMOND();
lock[i] = new ReentrantReadWriteLock();
}
mask = map.length - 1;
}
#if KEYS_PRIMITIVE
public VALUE_GENERIC_CLASS get(final KEY_CLASS k) {
final int stripe = KEY2INTHASH(k) & mask;
final ReadLock readLock = lock[stripe].readLock();
try {
readLock.lock();
return map[stripe].get(k);
}
finally {
readLock.unlock();
}
}
#endif
SUPPRESS_WARNINGS_KEY_UNCHECKED
public VALUE_GENERIC_TYPE GET_VALUE(final KEY_TYPE k) {
final int stripe = KEY2INTHASH(k) & mask;
final ReadLock readLock = lock[stripe].readLock();
try {
readLock.lock();
return map[stripe].GET_VALUE(k);
}
finally {
readLock.unlock();
}
}
public VALUE_GENERIC_TYPE put(final KEY_GENERIC_TYPE k, final VALUE_GENERIC_TYPE v) {
final int stripe = KEY2INTHASH(k) & mask;
final WriteLock writeLock = lock[stripe].writeLock();
try {
writeLock.lock();
return map[stripe].put(k, v);
}
finally {
writeLock.unlock();
}
}
public VALUE_GENERIC_TYPE putIfAbsent(final KEY_GENERIC_TYPE k, final VALUE_GENERIC_TYPE v) {
final int stripe = KEY2INTHASH(k) & mask;
final WriteLock writeLock = lock[stripe].writeLock();
try {
writeLock.lock();
if (map[stripe].containsKey(k)) return map[stripe].get(k);
return map[stripe].put(k, v);
}
finally {
writeLock.unlock();
}
}
#if VALUES_PRIMITIVE || KEYS_PRIMITIVE
public VALUE_GENERIC_CLASS put(final KEY_GENERIC_CLASS ok, final VALUE_GENERIC_CLASS ov) {
final int stripe = KEY2INTHASH(ok) & mask;
final WriteLock writeLock = lock[stripe].writeLock();
try {
writeLock.lock();
return map[stripe].put(ok, ov);
}
finally {
writeLock.unlock();
}
}
public VALUE_GENERIC_CLASS putIfAbsent(final KEY_GENERIC_CLASS ok, final VALUE_GENERIC_CLASS ov) {
final int stripe = KEY2INTHASH(ok) & mask;
final WriteLock writeLock = lock[stripe].writeLock();
try {
writeLock.lock();
if (map[stripe].containsKey(ok)) return map[stripe].get(ok);
return map[stripe].put(ok, ov);
}
finally {
writeLock.unlock();
}
}
#endif
public int size() {
final ReentrantReadWriteLock[] lock = this.lock;
int size = 0;
for(int stripe = lock.length; stripe-- != 0;) {
final ReadLock readLock = lock[stripe].readLock();
try {
readLock.lock();
size += map[stripe].size();
}
finally {
readLock.unlock();
}
}
return size;
}
public FastEntrySet KEY_VALUE_GENERIC ENTRYSET() {
throw new UnsupportedOperationException();
}
}
|
