1 /*
2 * Copyright (c) 2004, 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<String,V> that
263 = (Map.Entry<String,V>)ob;
264 return ((this.getKey() == null
265 ? that.getKey() == null
266 : this.getKey()
267 .equals(that.getKey()))
268 &&
269 (this.getValue() == null
270 ? that.getValue() == null
271 : this.getValue()
272 .equals(that.getValue())));
273 }
274 public V setValue(V v) {
275 throw new UnsupportedOperationException();
276 }
277 };
278 }
279
280 public void remove() {
281 throw new UnsupportedOperationException();
282 }
283
284 };
285 }
286 };
287 }
288
289 }