author | michaelm |
Thu, 14 Nov 2019 15:01:49 +0000 | |
branch | unixdomainchannels |
changeset 59082 | 5e250ee9259e |
parent 47216 | 71c04702a3d5 |
permissions | -rw-r--r-- |
2 | 1 |
/* |
14342
8435a30053c1
7197491: update copyright year to match last edit in jdk8 jdk repository
alanb
parents:
13795
diff
changeset
|
2 |
* Copyright (c) 2004, 2012, Oracle and/or its affiliates. All rights reserved. |
2 | 3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 |
* |
|
5 |
* This code is free software; you can redistribute it and/or modify it |
|
6 |
* under the terms of the GNU General Public License version 2 only, as |
|
5506 | 7 |
* published by the Free Software Foundation. Oracle designates this |
2 | 8 |
* particular file as subject to the "Classpath" exception as provided |
5506 | 9 |
* by Oracle in the LICENSE file that accompanied this code. |
2 | 10 |
* |
11 |
* This code is distributed in the hope that it will be useful, but WITHOUT |
|
12 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
13 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
14 |
* version 2 for more details (a copy is included in the LICENSE file that |
|
15 |
* accompanied this code). |
|
16 |
* |
|
17 |
* You should have received a copy of the GNU General Public License version |
|
18 |
* 2 along with this work; if not, write to the Free Software Foundation, |
|
19 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
|
20 |
* |
|
5506 | 21 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
22 |
* or visit www.oracle.com if you need additional information or have any |
|
23 |
* questions. |
|
2 | 24 |
*/ |
25 |
||
26 |
package sun.util; |
|
27 |
||
28 |
import java.util.Iterator; |
|
29 |
import java.util.Map; |
|
30 |
import java.util.Set; |
|
31 |
import java.util.AbstractMap; |
|
32 |
import java.util.AbstractSet; |
|
33 |
import java.util.NoSuchElementException; |
|
34 |
||
35 |
||
36 |
/** |
|
37 |
* A precomputed hash map. |
|
38 |
* |
|
39 |
* <p> Subclasses of this class are of the following form: |
|
40 |
* |
|
41 |
* <blockquote><pre> |
|
42 |
* class FooMap |
|
43 |
* extends sun.util.PreHashedMap<String> |
|
44 |
* { |
|
45 |
* |
|
46 |
* private FooMap() { |
|
47 |
* super(ROWS, SIZE, SHIFT, MASK); |
|
48 |
* } |
|
49 |
* |
|
50 |
* protected void init(Object[] ht) { |
|
51 |
* ht[0] = new Object[] { "key-1", value_1 }; |
|
52 |
* ht[1] = new Object[] { "key-2", value_2, |
|
53 |
* new Object { "key-3", value_3 } }; |
|
54 |
* ... |
|
55 |
* } |
|
56 |
* |
|
57 |
* }</pre></blockquote> |
|
58 |
* |
|
32210
958d823579c3
8133480: replace some <tt> tags (obsolete in html5) in core-libs docs
avstepan
parents:
31061
diff
changeset
|
59 |
* <p> The {@code init} method is invoked by the {@code PreHashedMap} |
2 | 60 |
* constructor with an object array long enough for the map's rows. The method |
61 |
* must construct the hash chain for each row and store it in the appropriate |
|
62 |
* element of the array. |
|
63 |
* |
|
64 |
* <p> Each entry in the map is represented by a unique hash-chain node. The |
|
65 |
* final node of a hash chain is a two-element object array whose first element |
|
66 |
* is the entry's key and whose second element is the entry's value. A |
|
67 |
* non-final node of a hash chain is a three-element object array whose first |
|
68 |
* two elements are the entry's key and value and whose third element is the |
|
69 |
* next node in the chain. |
|
70 |
* |
|
71 |
* <p> Instances of this class are mutable and are not safe for concurrent |
|
72 |
* access. They may be made immutable and thread-safe via the appropriate |
|
73 |
* methods in the {@link java.util.Collections} utility class. |
|
74 |
* |
|
75 |
* <p> In the JDK build, subclasses of this class are typically created via the |
|
32210
958d823579c3
8133480: replace some <tt> tags (obsolete in html5) in core-libs docs
avstepan
parents:
31061
diff
changeset
|
76 |
* {@code Hasher} program in the {@code make/tools/Hasher} directory. |
2 | 77 |
* |
78 |
* @author Mark Reinhold |
|
79 |
* @since 1.5 |
|
80 |
* |
|
81 |
* @see java.util.AbstractMap |
|
82 |
*/ |
|
83 |
||
84 |
public abstract class PreHashedMap<V> |
|
85 |
extends AbstractMap<String,V> |
|
86 |
{ |
|
87 |
||
88 |
private final int rows; |
|
89 |
private final int size; |
|
90 |
private final int shift; |
|
91 |
private final int mask; |
|
92 |
private final Object[] ht; |
|
93 |
||
94 |
/** |
|
95 |
* Creates a new map. |
|
96 |
* |
|
97 |
* <p> This constructor invokes the {@link #init init} method, passing it a |
|
32210
958d823579c3
8133480: replace some <tt> tags (obsolete in html5) in core-libs docs
avstepan
parents:
31061
diff
changeset
|
98 |
* newly-constructed row array that is {@code rows} elements long. |
2 | 99 |
* |
100 |
* @param rows |
|
101 |
* The number of rows in the map |
|
102 |
* @param size |
|
103 |
* The number of entries in the map |
|
104 |
* @param shift |
|
105 |
* The value by which hash codes are right-shifted |
|
106 |
* @param mask |
|
107 |
* The value with which hash codes are masked after being shifted |
|
108 |
*/ |
|
109 |
protected PreHashedMap(int rows, int size, int shift, int mask) { |
|
110 |
this.rows = rows; |
|
111 |
this.size = size; |
|
112 |
this.shift = shift; |
|
113 |
this.mask = mask; |
|
114 |
this.ht = new Object[rows]; |
|
115 |
init(ht); |
|
116 |
} |
|
117 |
||
118 |
/** |
|
119 |
* Initializes this map. |
|
120 |
* |
|
121 |
* <p> This method must construct the map's hash chains and store them into |
|
122 |
* the appropriate elements of the given hash-table row array. |
|
123 |
* |
|
31061 | 124 |
* @param ht The row array to be initialized |
2 | 125 |
*/ |
126 |
protected abstract void init(Object[] ht); |
|
127 |
||
13795
73850c397272
7193406: Clean-up JDK Build Warnings in java.util, java.io
dxu
parents:
5506
diff
changeset
|
128 |
@SuppressWarnings("unchecked") |
2 | 129 |
private V toV(Object x) { |
130 |
return (V)x; |
|
131 |
} |
|
132 |
||
133 |
public V get(Object k) { |
|
134 |
int h = (k.hashCode() >> shift) & mask; |
|
135 |
Object[] a = (Object[])ht[h]; |
|
136 |
if (a == null) return null; |
|
137 |
for (;;) { |
|
138 |
if (a[0].equals(k)) |
|
139 |
return toV(a[1]); |
|
140 |
if (a.length < 3) |
|
141 |
return null; |
|
142 |
a = (Object[])a[2]; |
|
143 |
} |
|
144 |
} |
|
145 |
||
146 |
/** |
|
147 |
* @throws UnsupportedOperationException |
|
148 |
* If the given key is not part of this map's initial key set |
|
149 |
*/ |
|
150 |
public V put(String k, V v) { |
|
151 |
int h = (k.hashCode() >> shift) & mask; |
|
152 |
Object[] a = (Object[])ht[h]; |
|
153 |
if (a == null) |
|
154 |
throw new UnsupportedOperationException(k); |
|
155 |
for (;;) { |
|
156 |
if (a[0].equals(k)) { |
|
157 |
V ov = toV(a[1]); |
|
158 |
a[1] = v; |
|
159 |
return ov; |
|
160 |
} |
|
161 |
if (a.length < 3) |
|
162 |
throw new UnsupportedOperationException(k); |
|
163 |
a = (Object[])a[2]; |
|
164 |
} |
|
165 |
} |
|
166 |
||
167 |
public Set<String> keySet() { |
|
29986
97167d851fc4
8078467: Update core libraries to use diamond with anonymous classes
darcy
parents:
25859
diff
changeset
|
168 |
return new AbstractSet<> () { |
2 | 169 |
|
170 |
public int size() { |
|
171 |
return size; |
|
172 |
} |
|
173 |
||
174 |
public Iterator<String> iterator() { |
|
29986
97167d851fc4
8078467: Update core libraries to use diamond with anonymous classes
darcy
parents:
25859
diff
changeset
|
175 |
return new Iterator<>() { |
2 | 176 |
private int i = -1; |
177 |
Object[] a = null; |
|
178 |
String cur = null; |
|
179 |
||
180 |
private boolean findNext() { |
|
181 |
if (a != null) { |
|
182 |
if (a.length == 3) { |
|
183 |
a = (Object[])a[2]; |
|
184 |
cur = (String)a[0]; |
|
185 |
return true; |
|
186 |
} |
|
187 |
i++; |
|
188 |
a = null; |
|
189 |
} |
|
190 |
cur = null; |
|
191 |
if (i >= rows) |
|
192 |
return false; |
|
193 |
if (i < 0 || ht[i] == null) { |
|
194 |
do { |
|
195 |
if (++i >= rows) |
|
196 |
return false; |
|
197 |
} while (ht[i] == null); |
|
198 |
} |
|
199 |
a = (Object[])ht[i]; |
|
200 |
cur = (String)a[0]; |
|
201 |
return true; |
|
202 |
} |
|
203 |
||
204 |
public boolean hasNext() { |
|
205 |
if (cur != null) |
|
206 |
return true; |
|
207 |
return findNext(); |
|
208 |
} |
|
209 |
||
210 |
public String next() { |
|
211 |
if (cur == null) { |
|
212 |
if (!findNext()) |
|
213 |
throw new NoSuchElementException(); |
|
214 |
} |
|
215 |
String s = cur; |
|
216 |
cur = null; |
|
217 |
return s; |
|
218 |
} |
|
219 |
||
220 |
public void remove() { |
|
221 |
throw new UnsupportedOperationException(); |
|
222 |
} |
|
223 |
||
224 |
}; |
|
225 |
} |
|
226 |
}; |
|
227 |
} |
|
228 |
||
229 |
public Set<Map.Entry<String,V>> entrySet() { |
|
230 |
return new AbstractSet<Map.Entry<String,V>> () { |
|
231 |
||
232 |
public int size() { |
|
233 |
return size; |
|
234 |
} |
|
235 |
||
236 |
public Iterator<Map.Entry<String,V>> iterator() { |
|
237 |
return new Iterator<Map.Entry<String,V>>() { |
|
238 |
final Iterator<String> i = keySet().iterator(); |
|
239 |
||
240 |
public boolean hasNext() { |
|
241 |
return i.hasNext(); |
|
242 |
} |
|
243 |
||
244 |
public Map.Entry<String,V> next() { |
|
245 |
return new Map.Entry<String,V>() { |
|
246 |
String k = i.next(); |
|
247 |
public String getKey() { return k; } |
|
248 |
public V getValue() { return get(k); } |
|
249 |
public int hashCode() { |
|
250 |
V v = get(k); |
|
251 |
return (k.hashCode() |
|
252 |
+ (v == null |
|
253 |
? 0 |
|
254 |
: v.hashCode())); |
|
255 |
} |
|
256 |
public boolean equals(Object ob) { |
|
257 |
if (ob == this) |
|
258 |
return true; |
|
259 |
if (!(ob instanceof Map.Entry)) |
|
260 |
return false; |
|
13795
73850c397272
7193406: Clean-up JDK Build Warnings in java.util, java.io
dxu
parents:
5506
diff
changeset
|
261 |
Map.Entry<?,?> that = (Map.Entry<?,?>)ob; |
2 | 262 |
return ((this.getKey() == null |
263 |
? that.getKey() == null |
|
264 |
: this.getKey() |
|
265 |
.equals(that.getKey())) |
|
266 |
&& |
|
267 |
(this.getValue() == null |
|
268 |
? that.getValue() == null |
|
269 |
: this.getValue() |
|
270 |
.equals(that.getValue()))); |
|
271 |
} |
|
272 |
public V setValue(V v) { |
|
273 |
throw new UnsupportedOperationException(); |
|
274 |
} |
|
275 |
}; |
|
276 |
} |
|
277 |
||
278 |
public void remove() { |
|
279 |
throw new UnsupportedOperationException(); |
|
280 |
} |
|
281 |
||
282 |
}; |
|
283 |
} |
|
284 |
}; |
|
285 |
} |
|
286 |
||
287 |
} |