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 ht The row array to be initialized 125 */ 126 protected abstract void init(Object[] ht); 127 128 @SuppressWarnings("unchecked") 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() { 168 return new AbstractSet<> () { 169 170 public int size() { 171 return size; 172 } 173 174 public Iterator<String> iterator() { 175 return new Iterator<>() { 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; 261 Map.Entry<?,?> that = (Map.Entry<?,?>)ob; 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 }