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