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