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&lt;String&gt;
  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 }
--- EOF ---