|
1 /* |
|
2 * Copyright (c) 2004, 2012, Oracle and/or its affiliates. All rights reserved. |
|
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 |
|
7 * published by the Free Software Foundation. Oracle designates this |
|
8 * particular file as subject to the "Classpath" exception as provided |
|
9 * by Oracle in the LICENSE file that accompanied this code. |
|
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 * |
|
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. |
|
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 * |
|
59 * <p> The <tt>init</tt> method is invoked by the <tt>PreHashedMap</tt> |
|
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 |
|
76 * <tt>Hasher</tt> program in the <tt>make/tools/Hasher</tt> directory. |
|
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 |
|
98 * newly-constructed row array that is <tt>rows</tt> elements long. |
|
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 * |
|
124 * @param rows |
|
125 * The row array to be initialized |
|
126 */ |
|
127 protected abstract void init(Object[] ht); |
|
128 |
|
129 @SuppressWarnings("unchecked") |
|
130 private V toV(Object x) { |
|
131 return (V)x; |
|
132 } |
|
133 |
|
134 public V get(Object k) { |
|
135 int h = (k.hashCode() >> shift) & mask; |
|
136 Object[] a = (Object[])ht[h]; |
|
137 if (a == null) return null; |
|
138 for (;;) { |
|
139 if (a[0].equals(k)) |
|
140 return toV(a[1]); |
|
141 if (a.length < 3) |
|
142 return null; |
|
143 a = (Object[])a[2]; |
|
144 } |
|
145 } |
|
146 |
|
147 /** |
|
148 * @throws UnsupportedOperationException |
|
149 * If the given key is not part of this map's initial key set |
|
150 */ |
|
151 public V put(String k, V v) { |
|
152 int h = (k.hashCode() >> shift) & mask; |
|
153 Object[] a = (Object[])ht[h]; |
|
154 if (a == null) |
|
155 throw new UnsupportedOperationException(k); |
|
156 for (;;) { |
|
157 if (a[0].equals(k)) { |
|
158 V ov = toV(a[1]); |
|
159 a[1] = v; |
|
160 return ov; |
|
161 } |
|
162 if (a.length < 3) |
|
163 throw new UnsupportedOperationException(k); |
|
164 a = (Object[])a[2]; |
|
165 } |
|
166 } |
|
167 |
|
168 public Set<String> keySet() { |
|
169 return new AbstractSet<String> () { |
|
170 |
|
171 public int size() { |
|
172 return size; |
|
173 } |
|
174 |
|
175 public Iterator<String> iterator() { |
|
176 return new Iterator<String>() { |
|
177 private int i = -1; |
|
178 Object[] a = null; |
|
179 String cur = null; |
|
180 |
|
181 private boolean findNext() { |
|
182 if (a != null) { |
|
183 if (a.length == 3) { |
|
184 a = (Object[])a[2]; |
|
185 cur = (String)a[0]; |
|
186 return true; |
|
187 } |
|
188 i++; |
|
189 a = null; |
|
190 } |
|
191 cur = null; |
|
192 if (i >= rows) |
|
193 return false; |
|
194 if (i < 0 || ht[i] == null) { |
|
195 do { |
|
196 if (++i >= rows) |
|
197 return false; |
|
198 } while (ht[i] == null); |
|
199 } |
|
200 a = (Object[])ht[i]; |
|
201 cur = (String)a[0]; |
|
202 return true; |
|
203 } |
|
204 |
|
205 public boolean hasNext() { |
|
206 if (cur != null) |
|
207 return true; |
|
208 return findNext(); |
|
209 } |
|
210 |
|
211 public String next() { |
|
212 if (cur == null) { |
|
213 if (!findNext()) |
|
214 throw new NoSuchElementException(); |
|
215 } |
|
216 String s = cur; |
|
217 cur = null; |
|
218 return s; |
|
219 } |
|
220 |
|
221 public void remove() { |
|
222 throw new UnsupportedOperationException(); |
|
223 } |
|
224 |
|
225 }; |
|
226 } |
|
227 }; |
|
228 } |
|
229 |
|
230 public Set<Map.Entry<String,V>> entrySet() { |
|
231 return new AbstractSet<Map.Entry<String,V>> () { |
|
232 |
|
233 public int size() { |
|
234 return size; |
|
235 } |
|
236 |
|
237 public Iterator<Map.Entry<String,V>> iterator() { |
|
238 return new Iterator<Map.Entry<String,V>>() { |
|
239 final Iterator<String> i = keySet().iterator(); |
|
240 |
|
241 public boolean hasNext() { |
|
242 return i.hasNext(); |
|
243 } |
|
244 |
|
245 public Map.Entry<String,V> next() { |
|
246 return new Map.Entry<String,V>() { |
|
247 String k = i.next(); |
|
248 public String getKey() { return k; } |
|
249 public V getValue() { return get(k); } |
|
250 public int hashCode() { |
|
251 V v = get(k); |
|
252 return (k.hashCode() |
|
253 + (v == null |
|
254 ? 0 |
|
255 : v.hashCode())); |
|
256 } |
|
257 public boolean equals(Object ob) { |
|
258 if (ob == this) |
|
259 return true; |
|
260 if (!(ob instanceof Map.Entry)) |
|
261 return false; |
|
262 Map.Entry<?,?> that = (Map.Entry<?,?>)ob; |
|
263 return ((this.getKey() == null |
|
264 ? that.getKey() == null |
|
265 : this.getKey() |
|
266 .equals(that.getKey())) |
|
267 && |
|
268 (this.getValue() == null |
|
269 ? that.getValue() == null |
|
270 : this.getValue() |
|
271 .equals(that.getValue()))); |
|
272 } |
|
273 public V setValue(V v) { |
|
274 throw new UnsupportedOperationException(); |
|
275 } |
|
276 }; |
|
277 } |
|
278 |
|
279 public void remove() { |
|
280 throw new UnsupportedOperationException(); |
|
281 } |
|
282 |
|
283 }; |
|
284 } |
|
285 }; |
|
286 } |
|
287 |
|
288 } |