aoqi@0: /* aoqi@0: * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved. aoqi@0: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. aoqi@0: * aoqi@0: * This code is free software; you can redistribute it and/or modify it aoqi@0: * under the terms of the GNU General Public License version 2 only, as aoqi@0: * published by the Free Software Foundation. Oracle designates this aoqi@0: * particular file as subject to the "Classpath" exception as provided aoqi@0: * by Oracle in the LICENSE file that accompanied this code. aoqi@0: * aoqi@0: * This code is distributed in the hope that it will be useful, but WITHOUT aoqi@0: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or aoqi@0: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License aoqi@0: * version 2 for more details (a copy is included in the LICENSE file that aoqi@0: * accompanied this code). aoqi@0: * aoqi@0: * You should have received a copy of the GNU General Public License version aoqi@0: * 2 along with this work; if not, write to the Free Software Foundation, aoqi@0: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. aoqi@0: * aoqi@0: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA aoqi@0: * or visit www.oracle.com if you need additional information or have any aoqi@0: * questions. aoqi@0: */ aoqi@0: aoqi@0: package com.sun.xml.internal.bind.v2.util; aoqi@0: import java.util.AbstractSet; aoqi@0: import java.util.Iterator; aoqi@0: import java.util.NoSuchElementException; aoqi@0: import java.util.Set; aoqi@0: import java.util.Map; aoqi@0: import java.util.Collection; aoqi@0: import java.util.HashSet; aoqi@0: aoqi@0: import javax.xml.namespace.QName; aoqi@0: aoqi@0: import com.sun.xml.internal.bind.v2.runtime.Name; aoqi@0: aoqi@0: /** aoqi@0: * Map keyed by {@link QName}. aoqi@0: * aoqi@0: * This specialized map allows a look up operation without constructing aoqi@0: * a new QName instance, for a performance reason. This {@link Map} assumes aoqi@0: * that both namespace URI and local name are {@link String#intern() intern}ed. aoqi@0: * aoqi@0: * @since JAXB 2.0 aoqi@0: */ aoqi@0: public final class QNameMap { aoqi@0: /** aoqi@0: * The default initial capacity - MUST be a power of two. aoqi@0: */ aoqi@0: private static final int DEFAULT_INITIAL_CAPACITY = 16; aoqi@0: aoqi@0: /** aoqi@0: * The maximum capacity, used if a higher value is implicitly specified aoqi@0: * by either of the constructors with arguments. aoqi@0: * MUST be a power of two <= 1<<30. aoqi@0: */ aoqi@0: private static final int MAXIMUM_CAPACITY = 1 << 30; aoqi@0: aoqi@0: /** aoqi@0: * The table, resized as necessary. Length MUST Always be a power of two. aoqi@0: */ aoqi@0: transient Entry[] table = new Entry[DEFAULT_INITIAL_CAPACITY]; aoqi@0: aoqi@0: /** aoqi@0: * The number of key-value mappings contained in this identity hash map. aoqi@0: */ aoqi@0: transient int size; aoqi@0: aoqi@0: /** aoqi@0: * The next size value at which to resize . Taking it as aoqi@0: * MAXIMUM_CAPACITY aoqi@0: * @serial aoqi@0: */ aoqi@0: private int threshold; aoqi@0: aoqi@0: /** aoqi@0: * The load factor used when none specified in constructor. aoqi@0: **/ aoqi@0: private static final float DEFAULT_LOAD_FACTOR = 0.75f; aoqi@0: aoqi@0: aoqi@0: aoqi@0: /** aoqi@0: * Gives an entrySet view of this map aoqi@0: */ aoqi@0: private Set> entrySet = null; aoqi@0: aoqi@0: public QNameMap() { aoqi@0: threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); aoqi@0: table = new Entry[DEFAULT_INITIAL_CAPACITY]; aoqi@0: aoqi@0: } aoqi@0: aoqi@0: /** aoqi@0: * Associates the specified value with the specified keys in this map. aoqi@0: * If the map previously contained a mapping for this key, the old aoqi@0: * value is replaced. aoqi@0: * aoqi@0: * @param namespaceUri First key with which the specified value is to be associated. aoqi@0: * @param localname Second key with which the specified value is to be associated. aoqi@0: * @param value value to be associated with the specified key. aoqi@0: * aoqi@0: */ aoqi@0: public void put(String namespaceUri,String localname, V value ) { aoqi@0: //keys cannot be null aoqi@0: assert localname !=null; aoqi@0: assert namespaceUri !=null; aoqi@0: // keys must be interned aoqi@0: assert localname == localname.intern(); aoqi@0: assert namespaceUri == namespaceUri.intern(); aoqi@0: aoqi@0: int hash = hash(localname); aoqi@0: int i = indexFor(hash, table.length); aoqi@0: aoqi@0: for (Entry e = table[i]; e != null; e = e.next) { aoqi@0: if (e.hash == hash && localname == e.localName && namespaceUri==e.nsUri) { aoqi@0: e.value = value; aoqi@0: return; aoqi@0: } aoqi@0: } aoqi@0: aoqi@0: addEntry(hash, namespaceUri,localname, value, i); aoqi@0: aoqi@0: } aoqi@0: aoqi@0: public void put(QName name, V value ) { aoqi@0: put(name.getNamespaceURI(),name.getLocalPart(),value); aoqi@0: } aoqi@0: aoqi@0: public void put(Name name, V value ) { aoqi@0: put(name.nsUri,name.localName,value); aoqi@0: } aoqi@0: aoqi@0: /** aoqi@0: * Returns the value to which the specified keys are mapped in this QNameMap, aoqi@0: * or null if the map contains no mapping for this key. aoqi@0: * aoqi@0: * @param nsUri the namespaceUri key whose associated value is to be returned. aoqi@0: * @param localPart the localPart key whose associated value is to be returned. aoqi@0: * @return the value to which this map maps the specified set of keya, or aoqi@0: * null if the map contains no mapping for this set of keys. aoqi@0: * @see #put(String,String, Object) aoqi@0: */ aoqi@0: public V get( String nsUri, String localPart ) { aoqi@0: Entry e = getEntry(nsUri,localPart); aoqi@0: if(e==null) return null; aoqi@0: else return e.value; aoqi@0: } aoqi@0: aoqi@0: public V get( QName name ) { aoqi@0: return get(name.getNamespaceURI(),name.getLocalPart()); aoqi@0: } aoqi@0: aoqi@0: /** aoqi@0: * Returns the number of keys-value mappings in this map. aoqi@0: * aoqi@0: * @return the number of keys-value mappings in this map. aoqi@0: */ aoqi@0: public int size() { aoqi@0: return size; aoqi@0: } aoqi@0: aoqi@0: /** aoqi@0: * Copies all of the mappings from the specified map to this map aoqi@0: * These mappings will replace any mappings that aoqi@0: * this map had for any of the keys currently in the specified map. aoqi@0: * aoqi@0: * @param map mappings to be stored in this map. aoqi@0: * aoqi@0: */ aoqi@0: public QNameMap putAll(QNameMap map) { aoqi@0: int numKeysToBeAdded = map.size(); aoqi@0: if (numKeysToBeAdded == 0) aoqi@0: return this; aoqi@0: aoqi@0: aoqi@0: if (numKeysToBeAdded > threshold) { aoqi@0: int targetCapacity = numKeysToBeAdded; aoqi@0: if (targetCapacity > MAXIMUM_CAPACITY) aoqi@0: targetCapacity = MAXIMUM_CAPACITY; aoqi@0: int newCapacity = table.length; aoqi@0: while (newCapacity < targetCapacity) aoqi@0: newCapacity <<= 1; aoqi@0: if (newCapacity > table.length) aoqi@0: resize(newCapacity); aoqi@0: } aoqi@0: aoqi@0: for( Entry e : map.entrySet() ) aoqi@0: put(e.nsUri,e.localName,e.getValue()); aoqi@0: return this; aoqi@0: } aoqi@0: aoqi@0: aoqi@0: /** aoqi@0: * Returns a hash value for the specified object.The hash value is computed aoqi@0: * for the localName. aoqi@0: */ aoqi@0: private static int hash(String x) { aoqi@0: int h = x.hashCode(); aoqi@0: aoqi@0: h += ~(h << 9); aoqi@0: h ^= (h >>> 14); aoqi@0: h += (h << 4); aoqi@0: h ^= (h >>> 10); aoqi@0: return h; aoqi@0: } aoqi@0: aoqi@0: /** aoqi@0: * Returns index for hash code h. aoqi@0: */ aoqi@0: private static int indexFor(int h, int length) { aoqi@0: return h & (length-1); aoqi@0: } aoqi@0: aoqi@0: /** aoqi@0: * Add a new entry with the specified keys, value and hash code to aoqi@0: * the specified bucket. It is the responsibility of this aoqi@0: * method to resize the table if appropriate. aoqi@0: * aoqi@0: */ aoqi@0: private void addEntry(int hash, String nsUri, String localName, V value, int bucketIndex) { aoqi@0: Entry e = table[bucketIndex]; aoqi@0: table[bucketIndex] = new Entry(hash, nsUri, localName, value, e); aoqi@0: if (size++ >= threshold) aoqi@0: resize(2 * table.length); aoqi@0: } aoqi@0: aoqi@0: aoqi@0: /** aoqi@0: * Rehashes the contents of this map into a new array with a aoqi@0: * larger capacity. This method is called automatically when the aoqi@0: * number of keys in this map reaches its threshold. aoqi@0: */ aoqi@0: private void resize(int newCapacity) { aoqi@0: Entry[] oldTable = table; aoqi@0: int oldCapacity = oldTable.length; aoqi@0: if (oldCapacity == MAXIMUM_CAPACITY) { aoqi@0: threshold = Integer.MAX_VALUE; aoqi@0: return; aoqi@0: } aoqi@0: aoqi@0: Entry[] newTable = new Entry[newCapacity]; aoqi@0: transfer(newTable); aoqi@0: table = newTable; aoqi@0: threshold = newCapacity; aoqi@0: } aoqi@0: aoqi@0: /** aoqi@0: * Transfer all entries from current table to newTable. aoqi@0: */ aoqi@0: private void transfer(Entry[] newTable) { aoqi@0: Entry[] src = table; aoqi@0: int newCapacity = newTable.length; aoqi@0: for (int j = 0; j < src.length; j++) { aoqi@0: Entry e = src[j]; aoqi@0: if (e != null) { aoqi@0: src[j] = null; aoqi@0: do { aoqi@0: Entry next = e.next; aoqi@0: int i = indexFor(e.hash, newCapacity); aoqi@0: e.next = newTable[i]; aoqi@0: newTable[i] = e; aoqi@0: e = next; aoqi@0: } while (e != null); aoqi@0: } aoqi@0: } aoqi@0: } aoqi@0: aoqi@0: /** aoqi@0: * Returns one random item in the map. aoqi@0: * If this map is empty, return null. aoqi@0: * aoqi@0: *

aoqi@0: * This method is useful to obtain the value from a map that only contains one element. aoqi@0: */ aoqi@0: public Entry getOne() { aoqi@0: for( Entry e : table ) { aoqi@0: if(e!=null) aoqi@0: return e; aoqi@0: } aoqi@0: return null; aoqi@0: } aoqi@0: aoqi@0: public Collection keySet() { aoqi@0: Set r = new HashSet(); aoqi@0: for (Entry e : entrySet()) { aoqi@0: r.add(e.createQName()); aoqi@0: } aoqi@0: return r; aoqi@0: } aoqi@0: aoqi@0: private abstract class HashIterator implements Iterator { aoqi@0: Entry next; // next entry to return aoqi@0: int index; // current slot aoqi@0: aoqi@0: HashIterator() { aoqi@0: Entry[] t = table; aoqi@0: int i = t.length; aoqi@0: Entry n = null; aoqi@0: if (size != 0) { // advance to first entry aoqi@0: while (i > 0 && (n = t[--i]) == null) {} aoqi@0: } aoqi@0: next = n; aoqi@0: index = i; aoqi@0: } aoqi@0: aoqi@0: public boolean hasNext() { aoqi@0: return next != null; aoqi@0: } aoqi@0: aoqi@0: Entry nextEntry() { aoqi@0: Entry e = next; aoqi@0: if (e == null) aoqi@0: throw new NoSuchElementException(); aoqi@0: aoqi@0: Entry n = e.next; aoqi@0: Entry[] t = table; aoqi@0: int i = index; aoqi@0: while (n == null && i > 0) aoqi@0: n = t[--i]; aoqi@0: index = i; aoqi@0: next = n; aoqi@0: return e; aoqi@0: } aoqi@0: aoqi@0: public void remove() { aoqi@0: throw new UnsupportedOperationException(); aoqi@0: } aoqi@0: } aoqi@0: aoqi@0: public boolean containsKey(String nsUri,String localName) { aoqi@0: return getEntry(nsUri,localName)!=null; aoqi@0: } aoqi@0: aoqi@0: aoqi@0: /** aoqi@0: * Returns true if this map is empty. aoqi@0: */ aoqi@0: public boolean isEmpty() { aoqi@0: return size == 0; aoqi@0: } aoqi@0: aoqi@0: aoqi@0: public static final class Entry { aoqi@0: /** The namespace URI. */ aoqi@0: public final String nsUri; aoqi@0: aoqi@0: /** The localPart. */ aoqi@0: public final String localName; aoqi@0: aoqi@0: V value; aoqi@0: final int hash; aoqi@0: Entry next; aoqi@0: aoqi@0: /** aoqi@0: * Create new entry. aoqi@0: */ aoqi@0: Entry(int h, String nsUri, String localName, V v, Entry n) { aoqi@0: value = v; aoqi@0: next = n; aoqi@0: this.nsUri = nsUri; aoqi@0: this.localName = localName; aoqi@0: hash = h; aoqi@0: } aoqi@0: aoqi@0: /** aoqi@0: * Creates a new QName object from {@link #nsUri} and {@link #localName}. aoqi@0: */ aoqi@0: public QName createQName() { aoqi@0: return new QName(nsUri,localName); aoqi@0: } aoqi@0: aoqi@0: public V getValue() { aoqi@0: return value; aoqi@0: } aoqi@0: aoqi@0: public V setValue(V newValue) { aoqi@0: V oldValue = value; aoqi@0: value = newValue; aoqi@0: return oldValue; aoqi@0: } aoqi@0: aoqi@0: @Override aoqi@0: public boolean equals(Object o) { aoqi@0: if (!(o instanceof Entry)) aoqi@0: return false; aoqi@0: Entry e = (Entry)o; aoqi@0: String k1 = nsUri; aoqi@0: String k2 = e.nsUri; aoqi@0: String k3 = localName; aoqi@0: String k4 = e.localName; aoqi@0: if (k1 == k2 || (k1 != null && k1.equals(k2)) && aoqi@0: (k3 == k4 ||(k3 !=null && k3.equals(k4)))) { aoqi@0: Object v1 = getValue(); aoqi@0: Object v2 = e.getValue(); aoqi@0: if (v1 == v2 || (v1 != null && v1.equals(v2))) aoqi@0: return true; aoqi@0: } aoqi@0: return false; aoqi@0: } aoqi@0: aoqi@0: @Override aoqi@0: public int hashCode() { aoqi@0: return ( localName.hashCode()) ^ aoqi@0: (value==null ? 0 : value.hashCode()); aoqi@0: } aoqi@0: aoqi@0: @Override aoqi@0: public String toString() { aoqi@0: return '"'+nsUri +"\",\"" +localName + "\"=" + getValue(); aoqi@0: } aoqi@0: } aoqi@0: aoqi@0: public Set> entrySet() { aoqi@0: Set> es = entrySet; aoqi@0: return es != null ? es : (entrySet = new EntrySet()); aoqi@0: } aoqi@0: aoqi@0: private Iterator> newEntryIterator() { aoqi@0: return new EntryIterator(); aoqi@0: } aoqi@0: aoqi@0: private class EntryIterator extends HashIterator> { aoqi@0: public Entry next() { aoqi@0: return nextEntry(); aoqi@0: } aoqi@0: } aoqi@0: private class EntrySet extends AbstractSet> { aoqi@0: public Iterator> iterator() { aoqi@0: return newEntryIterator(); aoqi@0: } aoqi@0: @Override aoqi@0: public boolean contains(Object o) { aoqi@0: if (!(o instanceof Entry)) aoqi@0: return false; aoqi@0: Entry e = (Entry) o; aoqi@0: Entry candidate = getEntry(e.nsUri,e.localName); aoqi@0: return candidate != null && candidate.equals(e); aoqi@0: } aoqi@0: @Override aoqi@0: public boolean remove(Object o) { aoqi@0: throw new UnsupportedOperationException(); aoqi@0: } aoqi@0: public int size() { aoqi@0: return size; aoqi@0: } aoqi@0: } aoqi@0: aoqi@0: private Entry getEntry(String nsUri,String localName) { aoqi@0: // strings must be interned aoqi@0: assert nsUri==nsUri.intern(); aoqi@0: assert localName==localName.intern(); aoqi@0: aoqi@0: int hash = hash(localName); aoqi@0: int i = indexFor(hash, table.length); aoqi@0: Entry e = table[i]; aoqi@0: while (e != null && !(localName == e.localName && nsUri == e.nsUri)) aoqi@0: e = e.next; aoqi@0: return e; aoqi@0: } aoqi@0: aoqi@0: @Override aoqi@0: public String toString() { aoqi@0: StringBuilder buf = new StringBuilder(); aoqi@0: buf.append('{'); aoqi@0: aoqi@0: for( Entry e : entrySet() ) { aoqi@0: if(buf.length()>1) aoqi@0: buf.append(','); aoqi@0: buf.append('['); aoqi@0: buf.append(e); aoqi@0: buf.append(']'); aoqi@0: } aoqi@0: aoqi@0: buf.append('}'); aoqi@0: return buf.toString(); aoqi@0: } aoqi@0: }