0N/A/*
2362N/A * Copyright (c) 2004, Oracle and/or its affiliates. All rights reserved.
0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0N/A *
0N/A * This code is free software; you can redistribute it and/or modify it
0N/A * under the terms of the GNU General Public License version 2 only, as
2362N/A * published by the Free Software Foundation. Oracle designates this
0N/A * particular file as subject to the "Classpath" exception as provided
2362N/A * by Oracle in the LICENSE file that accompanied this code.
0N/A *
0N/A * This code is distributed in the hope that it will be useful, but WITHOUT
0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0N/A * version 2 for more details (a copy is included in the LICENSE file that
0N/A * accompanied this code).
0N/A *
0N/A * You should have received a copy of the GNU General Public License version
0N/A * 2 along with this work; if not, write to the Free Software Foundation,
0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0N/A *
2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
2362N/A * or visit www.oracle.com if you need additional information or have any
2362N/A * questions.
0N/A */
0N/A
0N/Apackage sun.util;
0N/A
0N/Aimport java.util.Iterator;
0N/Aimport java.util.Map;
0N/Aimport java.util.Set;
0N/Aimport java.util.AbstractMap;
0N/Aimport java.util.AbstractSet;
0N/Aimport java.util.NoSuchElementException;
0N/A
0N/A
0N/A/**
0N/A * A precomputed hash map.
0N/A *
0N/A * <p> Subclasses of this class are of the following form:
0N/A *
0N/A * <blockquote><pre>
0N/A * class FooMap
0N/A * extends sun.util.PreHashedMap&lt;String&gt;
0N/A * {
0N/A *
0N/A * private FooMap() {
0N/A * super(ROWS, SIZE, SHIFT, MASK);
0N/A * }
0N/A *
0N/A * protected void init(Object[] ht) {
0N/A * ht[0] = new Object[] { "key-1", value_1 };
0N/A * ht[1] = new Object[] { "key-2", value_2,
0N/A * new Object { "key-3", value_3 } };
0N/A * ...
0N/A * }
0N/A *
0N/A * }</pre></blockquote>
0N/A *
0N/A * <p> The <tt>init</tt> method is invoked by the <tt>PreHashedMap</tt>
0N/A * constructor with an object array long enough for the map's rows. The method
0N/A * must construct the hash chain for each row and store it in the appropriate
0N/A * element of the array.
0N/A *
0N/A * <p> Each entry in the map is represented by a unique hash-chain node. The
0N/A * final node of a hash chain is a two-element object array whose first element
0N/A * is the entry's key and whose second element is the entry's value. A
0N/A * non-final node of a hash chain is a three-element object array whose first
0N/A * two elements are the entry's key and value and whose third element is the
0N/A * next node in the chain.
0N/A *
0N/A * <p> Instances of this class are mutable and are not safe for concurrent
0N/A * access. They may be made immutable and thread-safe via the appropriate
0N/A * methods in the {@link java.util.Collections} utility class.
0N/A *
0N/A * <p> In the JDK build, subclasses of this class are typically created via the
0N/A * <tt>Hasher</tt> program in the <tt>make/tools/Hasher</tt> directory.
0N/A *
0N/A * @author Mark Reinhold
0N/A * @since 1.5
0N/A *
0N/A * @see java.util.AbstractMap
0N/A */
0N/A
0N/Apublic abstract class PreHashedMap<V>
0N/A extends AbstractMap<String,V>
0N/A{
0N/A
0N/A private final int rows;
0N/A private final int size;
0N/A private final int shift;
0N/A private final int mask;
0N/A private final Object[] ht;
0N/A
0N/A /**
0N/A * Creates a new map.
0N/A *
0N/A * <p> This constructor invokes the {@link #init init} method, passing it a
0N/A * newly-constructed row array that is <tt>rows</tt> elements long.
0N/A *
0N/A * @param rows
0N/A * The number of rows in the map
0N/A * @param size
0N/A * The number of entries in the map
0N/A * @param shift
0N/A * The value by which hash codes are right-shifted
0N/A * @param mask
0N/A * The value with which hash codes are masked after being shifted
0N/A */
0N/A protected PreHashedMap(int rows, int size, int shift, int mask) {
0N/A this.rows = rows;
0N/A this.size = size;
0N/A this.shift = shift;
0N/A this.mask = mask;
0N/A this.ht = new Object[rows];
0N/A init(ht);
0N/A }
0N/A
0N/A /**
0N/A * Initializes this map.
0N/A *
0N/A * <p> This method must construct the map's hash chains and store them into
0N/A * the appropriate elements of the given hash-table row array.
0N/A *
0N/A * @param rows
0N/A * The row array to be initialized
0N/A */
0N/A protected abstract void init(Object[] ht);
0N/A
5047N/A @SuppressWarnings("unchecked")
0N/A private V toV(Object x) {
0N/A return (V)x;
0N/A }
0N/A
0N/A public V get(Object k) {
0N/A int h = (k.hashCode() >> shift) & mask;
0N/A Object[] a = (Object[])ht[h];
0N/A if (a == null) return null;
0N/A for (;;) {
0N/A if (a[0].equals(k))
0N/A return toV(a[1]);
0N/A if (a.length < 3)
0N/A return null;
0N/A a = (Object[])a[2];
0N/A }
0N/A }
0N/A
0N/A /**
0N/A * @throws UnsupportedOperationException
0N/A * If the given key is not part of this map's initial key set
0N/A */
0N/A public V put(String k, V v) {
0N/A int h = (k.hashCode() >> shift) & mask;
0N/A Object[] a = (Object[])ht[h];
0N/A if (a == null)
0N/A throw new UnsupportedOperationException(k);
0N/A for (;;) {
0N/A if (a[0].equals(k)) {
0N/A V ov = toV(a[1]);
0N/A a[1] = v;
0N/A return ov;
0N/A }
0N/A if (a.length < 3)
0N/A throw new UnsupportedOperationException(k);
0N/A a = (Object[])a[2];
0N/A }
0N/A }
0N/A
0N/A public Set<String> keySet() {
0N/A return new AbstractSet<String> () {
0N/A
0N/A public int size() {
0N/A return size;
0N/A }
0N/A
0N/A public Iterator<String> iterator() {
0N/A return new Iterator<String>() {
0N/A private int i = -1;
0N/A Object[] a = null;
0N/A String cur = null;
0N/A
0N/A private boolean findNext() {
0N/A if (a != null) {
0N/A if (a.length == 3) {
0N/A a = (Object[])a[2];
0N/A cur = (String)a[0];
0N/A return true;
0N/A }
0N/A i++;
0N/A a = null;
0N/A }
0N/A cur = null;
0N/A if (i >= rows)
0N/A return false;
0N/A if (i < 0 || ht[i] == null) {
0N/A do {
0N/A if (++i >= rows)
0N/A return false;
0N/A } while (ht[i] == null);
0N/A }
0N/A a = (Object[])ht[i];
0N/A cur = (String)a[0];
0N/A return true;
0N/A }
0N/A
0N/A public boolean hasNext() {
0N/A if (cur != null)
0N/A return true;
0N/A return findNext();
0N/A }
0N/A
0N/A public String next() {
0N/A if (cur == null) {
0N/A if (!findNext())
0N/A throw new NoSuchElementException();
0N/A }
0N/A String s = cur;
0N/A cur = null;
0N/A return s;
0N/A }
0N/A
0N/A public void remove() {
0N/A throw new UnsupportedOperationException();
0N/A }
0N/A
0N/A };
0N/A }
0N/A };
0N/A }
0N/A
0N/A public Set<Map.Entry<String,V>> entrySet() {
0N/A return new AbstractSet<Map.Entry<String,V>> () {
0N/A
0N/A public int size() {
0N/A return size;
0N/A }
0N/A
0N/A public Iterator<Map.Entry<String,V>> iterator() {
0N/A return new Iterator<Map.Entry<String,V>>() {
0N/A final Iterator<String> i = keySet().iterator();
0N/A
0N/A public boolean hasNext() {
0N/A return i.hasNext();
0N/A }
0N/A
0N/A public Map.Entry<String,V> next() {
0N/A return new Map.Entry<String,V>() {
0N/A String k = i.next();
0N/A public String getKey() { return k; }
0N/A public V getValue() { return get(k); }
0N/A public int hashCode() {
0N/A V v = get(k);
0N/A return (k.hashCode()
0N/A + (v == null
0N/A ? 0
0N/A : v.hashCode()));
0N/A }
5047N/A @SuppressWarnings("unchecked")
0N/A public boolean equals(Object ob) {
0N/A if (ob == this)
0N/A return true;
0N/A if (!(ob instanceof Map.Entry))
0N/A return false;
0N/A Map.Entry<String,V> that
0N/A = (Map.Entry<String,V>)ob;
0N/A return ((this.getKey() == null
0N/A ? that.getKey() == null
0N/A : this.getKey()
0N/A .equals(that.getKey()))
0N/A &&
0N/A (this.getValue() == null
0N/A ? that.getValue() == null
0N/A : this.getValue()
0N/A .equals(that.getValue())));
0N/A }
0N/A public V setValue(V v) {
0N/A throw new UnsupportedOperationException();
0N/A }
0N/A };
0N/A }
0N/A
0N/A public void remove() {
0N/A throw new UnsupportedOperationException();
0N/A }
0N/A
0N/A };
0N/A }
0N/A };
0N/A }
0N/A
0N/A}