1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/share/jaxws_classes/com/sun/xml/internal/bind/v2/util/QNameMap.java Tue Mar 06 16:09:35 2012 -0800 1.3 @@ -0,0 +1,480 @@ 1.4 +/* 1.5 + * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved. 1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1.7 + * 1.8 + * This code is free software; you can redistribute it and/or modify it 1.9 + * under the terms of the GNU General Public License version 2 only, as 1.10 + * published by the Free Software Foundation. Oracle designates this 1.11 + * particular file as subject to the "Classpath" exception as provided 1.12 + * by Oracle in the LICENSE file that accompanied this code. 1.13 + * 1.14 + * This code is distributed in the hope that it will be useful, but WITHOUT 1.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1.17 + * version 2 for more details (a copy is included in the LICENSE file that 1.18 + * accompanied this code). 1.19 + * 1.20 + * You should have received a copy of the GNU General Public License version 1.21 + * 2 along with this work; if not, write to the Free Software Foundation, 1.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1.23 + * 1.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 1.25 + * or visit www.oracle.com if you need additional information or have any 1.26 + * questions. 1.27 + */ 1.28 + 1.29 +package com.sun.xml.internal.bind.v2.util; 1.30 +import java.util.AbstractSet; 1.31 +import java.util.Iterator; 1.32 +import java.util.NoSuchElementException; 1.33 +import java.util.Set; 1.34 +import java.util.Map; 1.35 +import java.util.Collection; 1.36 +import java.util.HashSet; 1.37 + 1.38 +import javax.xml.namespace.QName; 1.39 + 1.40 +import com.sun.xml.internal.bind.v2.runtime.Name; 1.41 + 1.42 +/** 1.43 + * Map keyed by {@link QName}. 1.44 + * 1.45 + * This specialized map allows a look up operation without constructing 1.46 + * a new QName instance, for a performance reason. This {@link Map} assumes 1.47 + * that both namespace URI and local name are {@link String#intern() intern}ed. 1.48 + * 1.49 + * @since JAXB 2.0 1.50 + */ 1.51 +public final class QNameMap<V> { 1.52 + /** 1.53 + * The default initial capacity - MUST be a power of two. 1.54 + */ 1.55 + private static final int DEFAULT_INITIAL_CAPACITY = 16; 1.56 + 1.57 + /** 1.58 + * The maximum capacity, used if a higher value is implicitly specified 1.59 + * by either of the constructors with arguments. 1.60 + * MUST be a power of two <= 1<<30. 1.61 + */ 1.62 + private static final int MAXIMUM_CAPACITY = 1 << 30; 1.63 + 1.64 + /** 1.65 + * The table, resized as necessary. Length MUST Always be a power of two. 1.66 + */ 1.67 + transient Entry<V>[] table = new Entry[DEFAULT_INITIAL_CAPACITY]; 1.68 + 1.69 + /** 1.70 + * The number of key-value mappings contained in this identity hash map. 1.71 + */ 1.72 + transient int size; 1.73 + 1.74 + /** 1.75 + * The next size value at which to resize . Taking it as 1.76 + * MAXIMUM_CAPACITY 1.77 + * @serial 1.78 + */ 1.79 + private int threshold; 1.80 + 1.81 + /** 1.82 + * The load factor used when none specified in constructor. 1.83 + **/ 1.84 + private static final float DEFAULT_LOAD_FACTOR = 0.75f; 1.85 + 1.86 + 1.87 + 1.88 + /** 1.89 + * Gives an entrySet view of this map 1.90 + */ 1.91 + private Set<Entry<V>> entrySet = null; 1.92 + 1.93 + public QNameMap() { 1.94 + threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); 1.95 + table = new Entry[DEFAULT_INITIAL_CAPACITY]; 1.96 + 1.97 + } 1.98 + 1.99 + /** 1.100 + * Associates the specified value with the specified keys in this map. 1.101 + * If the map previously contained a mapping for this key, the old 1.102 + * value is replaced. 1.103 + * 1.104 + * @param namespaceUri First key with which the specified value is to be associated. 1.105 + * @param localname Second key with which the specified value is to be associated. 1.106 + * @param value value to be associated with the specified key. 1.107 + * 1.108 + */ 1.109 + public void put(String namespaceUri,String localname, V value ) { 1.110 + //keys cannot be null 1.111 + assert localname !=null; 1.112 + assert namespaceUri !=null; 1.113 + // keys must be interned 1.114 + assert localname == localname.intern(); 1.115 + assert namespaceUri == namespaceUri.intern(); 1.116 + 1.117 + int hash = hash(localname); 1.118 + int i = indexFor(hash, table.length); 1.119 + 1.120 + for (Entry<V> e = table[i]; e != null; e = e.next) { 1.121 + if (e.hash == hash && localname == e.localName && namespaceUri==e.nsUri) { 1.122 + e.value = value; 1.123 + return; 1.124 + } 1.125 + } 1.126 + 1.127 + addEntry(hash, namespaceUri,localname, value, i); 1.128 + 1.129 + } 1.130 + 1.131 + public void put(QName name, V value ) { 1.132 + put(name.getNamespaceURI(),name.getLocalPart(),value); 1.133 + } 1.134 + 1.135 + public void put(Name name, V value ) { 1.136 + put(name.nsUri,name.localName,value); 1.137 + } 1.138 + 1.139 + /** 1.140 + * Returns the value to which the specified keys are mapped in this QNameMap, 1.141 + * or <tt>null</tt> if the map contains no mapping for this key. 1.142 + * 1.143 + * @param nsUri the namespaceUri key whose associated value is to be returned. 1.144 + * @param localPart the localPart key whose associated value is to be returned. 1.145 + * @return the value to which this map maps the specified set of keya, or 1.146 + * <tt>null</tt> if the map contains no mapping for this set of keys. 1.147 + * @see #put(String,String, Object) 1.148 + */ 1.149 + public V get( String nsUri, String localPart ) { 1.150 + Entry<V> e = getEntry(nsUri,localPart); 1.151 + if(e==null) return null; 1.152 + else return e.value; 1.153 + } 1.154 + 1.155 + public V get( QName name ) { 1.156 + return get(name.getNamespaceURI(),name.getLocalPart()); 1.157 + } 1.158 + 1.159 + /** 1.160 + * Returns the number of keys-value mappings in this map. 1.161 + * 1.162 + * @return the number of keys-value mappings in this map. 1.163 + */ 1.164 + public int size() { 1.165 + return size; 1.166 + } 1.167 + 1.168 + /** 1.169 + * Copies all of the mappings from the specified map to this map 1.170 + * These mappings will replace any mappings that 1.171 + * this map had for any of the keys currently in the specified map. 1.172 + * 1.173 + * @param map mappings to be stored in this map. 1.174 + * 1.175 + */ 1.176 + public QNameMap<V> putAll(QNameMap<? extends V> map) { 1.177 + int numKeysToBeAdded = map.size(); 1.178 + if (numKeysToBeAdded == 0) 1.179 + return this; 1.180 + 1.181 + 1.182 + if (numKeysToBeAdded > threshold) { 1.183 + int targetCapacity = numKeysToBeAdded; 1.184 + if (targetCapacity > MAXIMUM_CAPACITY) 1.185 + targetCapacity = MAXIMUM_CAPACITY; 1.186 + int newCapacity = table.length; 1.187 + while (newCapacity < targetCapacity) 1.188 + newCapacity <<= 1; 1.189 + if (newCapacity > table.length) 1.190 + resize(newCapacity); 1.191 + } 1.192 + 1.193 + for( Entry<? extends V> e : map.entrySet() ) 1.194 + put(e.nsUri,e.localName,e.getValue()); 1.195 + return this; 1.196 + } 1.197 + 1.198 + 1.199 + /** 1.200 + * Returns a hash value for the specified object.The hash value is computed 1.201 + * for the localName. 1.202 + */ 1.203 + private static int hash(String x) { 1.204 + int h = x.hashCode(); 1.205 + 1.206 + h += ~(h << 9); 1.207 + h ^= (h >>> 14); 1.208 + h += (h << 4); 1.209 + h ^= (h >>> 10); 1.210 + return h; 1.211 + } 1.212 + 1.213 + /** 1.214 + * Returns index for hash code h. 1.215 + */ 1.216 + private static int indexFor(int h, int length) { 1.217 + return h & (length-1); 1.218 + } 1.219 + 1.220 + /** 1.221 + * Add a new entry with the specified keys, value and hash code to 1.222 + * the specified bucket. It is the responsibility of this 1.223 + * method to resize the table if appropriate. 1.224 + * 1.225 + */ 1.226 + private void addEntry(int hash, String nsUri, String localName, V value, int bucketIndex) { 1.227 + Entry<V> e = table[bucketIndex]; 1.228 + table[bucketIndex] = new Entry<V>(hash, nsUri, localName, value, e); 1.229 + if (size++ >= threshold) 1.230 + resize(2 * table.length); 1.231 + } 1.232 + 1.233 + 1.234 + /** 1.235 + * Rehashes the contents of this map into a new array with a 1.236 + * larger capacity. This method is called automatically when the 1.237 + * number of keys in this map reaches its threshold. 1.238 + */ 1.239 + private void resize(int newCapacity) { 1.240 + Entry[] oldTable = table; 1.241 + int oldCapacity = oldTable.length; 1.242 + if (oldCapacity == MAXIMUM_CAPACITY) { 1.243 + threshold = Integer.MAX_VALUE; 1.244 + return; 1.245 + } 1.246 + 1.247 + Entry[] newTable = new Entry[newCapacity]; 1.248 + transfer(newTable); 1.249 + table = newTable; 1.250 + threshold = newCapacity; 1.251 + } 1.252 + 1.253 + /** 1.254 + * Transfer all entries from current table to newTable. 1.255 + */ 1.256 + private void transfer(Entry<V>[] newTable) { 1.257 + Entry<V>[] src = table; 1.258 + int newCapacity = newTable.length; 1.259 + for (int j = 0; j < src.length; j++) { 1.260 + Entry<V> e = src[j]; 1.261 + if (e != null) { 1.262 + src[j] = null; 1.263 + do { 1.264 + Entry<V> next = e.next; 1.265 + int i = indexFor(e.hash, newCapacity); 1.266 + e.next = newTable[i]; 1.267 + newTable[i] = e; 1.268 + e = next; 1.269 + } while (e != null); 1.270 + } 1.271 + } 1.272 + } 1.273 + 1.274 + /** 1.275 + * Returns one random item in the map. 1.276 + * If this map is empty, return null. 1.277 + * 1.278 + * <p> 1.279 + * This method is useful to obtain the value from a map that only contains one element. 1.280 + */ 1.281 + public Entry<V> getOne() { 1.282 + for( Entry<V> e : table ) { 1.283 + if(e!=null) 1.284 + return e; 1.285 + } 1.286 + return null; 1.287 + } 1.288 + 1.289 + public Collection<QName> keySet() { 1.290 + Set<QName> r = new HashSet<QName>(); 1.291 + for (Entry<V> e : entrySet()) { 1.292 + r.add(e.createQName()); 1.293 + } 1.294 + return r; 1.295 + } 1.296 + 1.297 + private abstract class HashIterator<E> implements Iterator<E> { 1.298 + Entry<V> next; // next entry to return 1.299 + int index; // current slot 1.300 + 1.301 + HashIterator() { 1.302 + Entry<V>[] t = table; 1.303 + int i = t.length; 1.304 + Entry<V> n = null; 1.305 + if (size != 0) { // advance to first entry 1.306 + while (i > 0 && (n = t[--i]) == null) {} 1.307 + } 1.308 + next = n; 1.309 + index = i; 1.310 + } 1.311 + 1.312 + public boolean hasNext() { 1.313 + return next != null; 1.314 + } 1.315 + 1.316 + Entry<V> nextEntry() { 1.317 + Entry<V> e = next; 1.318 + if (e == null) 1.319 + throw new NoSuchElementException(); 1.320 + 1.321 + Entry<V> n = e.next; 1.322 + Entry<V>[] t = table; 1.323 + int i = index; 1.324 + while (n == null && i > 0) 1.325 + n = t[--i]; 1.326 + index = i; 1.327 + next = n; 1.328 + return e; 1.329 + } 1.330 + 1.331 + public void remove() { 1.332 + throw new UnsupportedOperationException(); 1.333 + } 1.334 + } 1.335 + 1.336 + public boolean containsKey(String nsUri,String localName) { 1.337 + return getEntry(nsUri,localName)!=null; 1.338 + } 1.339 + 1.340 + 1.341 + /** 1.342 + * Returns true if this map is empty. 1.343 + */ 1.344 + public boolean isEmpty() { 1.345 + return size == 0; 1.346 + } 1.347 + 1.348 + 1.349 + public static final class Entry<V> { 1.350 + /** The namespace URI. */ 1.351 + public final String nsUri; 1.352 + 1.353 + /** The localPart. */ 1.354 + public final String localName; 1.355 + 1.356 + V value; 1.357 + final int hash; 1.358 + Entry<V> next; 1.359 + 1.360 + /** 1.361 + * Create new entry. 1.362 + */ 1.363 + Entry(int h, String nsUri, String localName, V v, Entry<V> n) { 1.364 + value = v; 1.365 + next = n; 1.366 + this.nsUri = nsUri; 1.367 + this.localName = localName; 1.368 + hash = h; 1.369 + } 1.370 + 1.371 + /** 1.372 + * Creates a new QName object from {@link #nsUri} and {@link #localName}. 1.373 + */ 1.374 + public QName createQName() { 1.375 + return new QName(nsUri,localName); 1.376 + } 1.377 + 1.378 + public V getValue() { 1.379 + return value; 1.380 + } 1.381 + 1.382 + public V setValue(V newValue) { 1.383 + V oldValue = value; 1.384 + value = newValue; 1.385 + return oldValue; 1.386 + } 1.387 + 1.388 + @Override 1.389 + public boolean equals(Object o) { 1.390 + if (!(o instanceof Entry)) 1.391 + return false; 1.392 + Entry e = (Entry)o; 1.393 + String k1 = nsUri; 1.394 + String k2 = e.nsUri; 1.395 + String k3 = localName; 1.396 + String k4 = e.localName; 1.397 + if (k1 == k2 || (k1 != null && k1.equals(k2)) && 1.398 + (k3 == k4 ||(k3 !=null && k3.equals(k4)))) { 1.399 + Object v1 = getValue(); 1.400 + Object v2 = e.getValue(); 1.401 + if (v1 == v2 || (v1 != null && v1.equals(v2))) 1.402 + return true; 1.403 + } 1.404 + return false; 1.405 + } 1.406 + 1.407 + @Override 1.408 + public int hashCode() { 1.409 + return ( localName.hashCode()) ^ 1.410 + (value==null ? 0 : value.hashCode()); 1.411 + } 1.412 + 1.413 + @Override 1.414 + public String toString() { 1.415 + return '"'+nsUri +"\",\"" +localName + "\"=" + getValue(); 1.416 + } 1.417 + } 1.418 + 1.419 + public Set<Entry<V>> entrySet() { 1.420 + Set<Entry<V>> es = entrySet; 1.421 + return es != null ? es : (entrySet = new EntrySet()); 1.422 + } 1.423 + 1.424 + private Iterator<Entry<V>> newEntryIterator() { 1.425 + return new EntryIterator(); 1.426 + } 1.427 + 1.428 + private class EntryIterator extends HashIterator<Entry<V>> { 1.429 + public Entry<V> next() { 1.430 + return nextEntry(); 1.431 + } 1.432 + } 1.433 + private class EntrySet extends AbstractSet<Entry<V>> { 1.434 + public Iterator<Entry<V>> iterator() { 1.435 + return newEntryIterator(); 1.436 + } 1.437 + @Override 1.438 + public boolean contains(Object o) { 1.439 + if (!(o instanceof Entry)) 1.440 + return false; 1.441 + Entry<V> e = (Entry<V>) o; 1.442 + Entry<V> candidate = getEntry(e.nsUri,e.localName); 1.443 + return candidate != null && candidate.equals(e); 1.444 + } 1.445 + @Override 1.446 + public boolean remove(Object o) { 1.447 + throw new UnsupportedOperationException(); 1.448 + } 1.449 + public int size() { 1.450 + return size; 1.451 + } 1.452 + } 1.453 + 1.454 + private Entry<V> getEntry(String nsUri,String localName) { 1.455 + // strings must be interned 1.456 + assert nsUri==nsUri.intern(); 1.457 + assert localName==localName.intern(); 1.458 + 1.459 + int hash = hash(localName); 1.460 + int i = indexFor(hash, table.length); 1.461 + Entry<V> e = table[i]; 1.462 + while (e != null && !(localName == e.localName && nsUri == e.nsUri)) 1.463 + e = e.next; 1.464 + return e; 1.465 + } 1.466 + 1.467 + @Override 1.468 + public String toString() { 1.469 + StringBuilder buf = new StringBuilder(); 1.470 + buf.append('{'); 1.471 + 1.472 + for( Entry<V> e : entrySet() ) { 1.473 + if(buf.length()>1) 1.474 + buf.append(','); 1.475 + buf.append('['); 1.476 + buf.append(e); 1.477 + buf.append(']'); 1.478 + } 1.479 + 1.480 + buf.append('}'); 1.481 + return buf.toString(); 1.482 + } 1.483 +}