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 @SuppressWarnings("unchecked") 258 public boolean equals(Object ob) { 259 if (ob == this) 260 return true; 261 if (!(ob instanceof Map.Entry)) 262 return false; 263 Map.Entry<String,V> that 264 = (Map.Entry<String,V>)ob; 265 return ((this.getKey() == null 266 ? that.getKey() == null 267 : this.getKey() 268 .equals(that.getKey())) 269 && 270 (this.getValue() == null 271 ? that.getValue() == null 272 : this.getValue() 273 .equals(that.getValue()))); 274 } 275 public V setValue(V v) { 276 throw new UnsupportedOperationException(); 277 } 278 }; 279 } 280 281 public void remove() { 282 throw new UnsupportedOperationException(); 283 } 284 285 }; 286 } 287 }; 288 } 289 290 }