1 /* 2 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package com.sun.xml.internal.ws.util; 27 28 import com.sun.istack.internal.NotNull; 29 30 import javax.xml.namespace.QName; 31 import java.util.AbstractSet; 32 import java.util.Collection; 33 import java.util.HashSet; 34 import java.util.Iterator; 35 import java.util.Map; 36 import java.util.NoSuchElementException; 37 import java.util.Set; 38 39 /** 40 * Map keyed by {@link QName}. 41 * 42 * This specialized map allows a look up operation without constructing 43 * a new QName instance, for a performance reason. This {@link Map} assumes 44 * that both namespace URI and local name are {@link String#intern() intern}ed. 45 * 46 * @since JAXB 2.0 47 */ 48 public final class QNameMap<V> { 49 /** 50 * The default initial capacity - MUST be a power of two. 51 */ 52 private static final int DEFAULT_INITIAL_CAPACITY = 16; 53 54 /** 55 * The maximum capacity, used if a higher value is implicitly specified 56 * by either of the constructors with arguments. 57 * MUST be a power of two <= 1<<30. 58 */ 59 private static final int MAXIMUM_CAPACITY = 1 << 30; 60 61 /** 62 * The table, resized as necessary. Length MUST Always be a power of two. 63 */ 64 transient Entry<V>[] table = new Entry[DEFAULT_INITIAL_CAPACITY]; 65 66 /** 67 * The number of key-value mappings contained in this identity hash map. 68 */ 69 transient int size; 70 71 /** 72 * The next size value at which to resize . Taking it as 73 * MAXIMUM_CAPACITY 74 * @serial 75 */ 76 private int threshold; 77 78 /** 79 * The load factor used when none specified in constructor. 80 **/ 81 private static final float DEFAULT_LOAD_FACTOR = 0.75f; 82 83 84 85 /** 86 * Gives an entrySet view of this map 87 */ 88 private Set<Entry<V>> entrySet = null; 89 90 public QNameMap() { 91 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); 92 table = new Entry[DEFAULT_INITIAL_CAPACITY]; 93 94 } 95 96 /** 97 * Associates the specified value with the specified keys in this map. 98 * If the map previously contained a mapping for this key, the old 99 * value is replaced. 100 * 101 * @param namespaceUri First key with which the specified value is to be associated. 102 * @param localname Second key with which the specified value is to be associated. 103 * @param value value to be associated with the specified key. 104 * 105 */ 106 public void put(String namespaceUri,String localname, V value ) { 107 //keys cannot be null 108 assert localname !=null; 109 assert namespaceUri !=null; 110 111 int hash = hash(localname); 112 int i = indexFor(hash, table.length); 113 114 for (Entry<V> e = table[i]; e != null; e = e.next) { 115 if (e.hash == hash && localname.equals(e.localName) && namespaceUri.equals(e.nsUri)) { 116 e.value = value; 117 return; 118 } 119 } 120 121 addEntry(hash, namespaceUri,localname, value, i); 122 123 } 124 125 public void put(QName name, V value ) { 126 put(name.getNamespaceURI(),name.getLocalPart(),value); 127 } 128 129 /** 130 * Returns the value to which the specified keys are mapped in this QNameMap, 131 * or {@code null} if the map contains no mapping for this key. 132 * 133 * @param nsUri the namespaceUri key whose associated value is to be returned. 134 * @param localPart the localPart key whose associated value is to be returned. 135 * @return the value to which this map maps the specified set of keya, or 136 * {@code null} if the map contains no mapping for this set of keys. 137 * @see #put(String,String, Object) 138 */ 139 public V get( @NotNull String nsUri, String localPart ) { 140 Entry<V> e = getEntry(nsUri,localPart); 141 if(e==null) return null; 142 else return e.value; 143 } 144 145 public V get( QName name ) { 146 return get(name.getNamespaceURI(),name.getLocalPart()); 147 } 148 149 /** 150 * Returns the number of keys-value mappings in this map. 151 * 152 * @return the number of keys-value mappings in this map. 153 */ 154 public int size() { 155 return size; 156 } 157 158 /** 159 * Copies all of the mappings from the specified map to this map 160 * These mappings will replace any mappings that 161 * this map had for any of the keys currently in the specified map. 162 * 163 * @param map mappings to be stored in this map. 164 * 165 */ 166 public QNameMap<V> putAll(QNameMap<? extends V> map) { 167 int numKeysToBeAdded = map.size(); 168 if (numKeysToBeAdded == 0) 169 return this; 170 171 172 if (numKeysToBeAdded > threshold) { 173 int targetCapacity = numKeysToBeAdded; 174 if (targetCapacity > MAXIMUM_CAPACITY) 175 targetCapacity = MAXIMUM_CAPACITY; 176 int newCapacity = table.length; 177 while (newCapacity < targetCapacity) 178 newCapacity <<= 1; 179 if (newCapacity > table.length) 180 resize(newCapacity); 181 } 182 183 for( Entry<? extends V> e : map.entrySet() ) 184 put(e.nsUri,e.localName,e.getValue()); 185 return this; 186 } 187 188 public QNameMap<V> putAll(Map<QName,? extends V> map) { 189 for (Map.Entry<QName, ? extends V> e : map.entrySet()) { 190 QName qn = e.getKey(); 191 put(qn.getNamespaceURI(),qn.getLocalPart(),e.getValue()); 192 } 193 return this; 194 } 195 196 197 /** 198 * Returns a hash value for the specified object.The hash value is computed 199 * for the localName. 200 */ 201 private static int hash(String x) { 202 int h = x.hashCode(); 203 204 h += ~(h << 9); 205 h ^= (h >>> 14); 206 h += (h << 4); 207 h ^= (h >>> 10); 208 return h; 209 } 210 211 /** 212 * Returns index for hash code h. 213 */ 214 private static int indexFor(int h, int length) { 215 return h & (length-1); 216 } 217 218 /** 219 * Add a new entry with the specified keys, value and hash code to 220 * the specified bucket. It is the responsibility of this 221 * method to resize the table if appropriate. 222 * 223 */ 224 private void addEntry(int hash, String nsUri, String localName, V value, int bucketIndex) { 225 Entry<V> e = table[bucketIndex]; 226 table[bucketIndex] = new Entry<V>(hash, nsUri, localName, value, e); 227 if (size++ >= threshold) 228 resize(2 * table.length); 229 } 230 231 232 /** 233 * Rehashes the contents of this map into a new array with a 234 * larger capacity. This method is called automatically when the 235 * number of keys in this map reaches its threshold. 236 */ 237 private void resize(int newCapacity) { 238 Entry[] oldTable = table; 239 int oldCapacity = oldTable.length; 240 if (oldCapacity == MAXIMUM_CAPACITY) { 241 threshold = Integer.MAX_VALUE; 242 return; 243 } 244 245 Entry[] newTable = new Entry[newCapacity]; 246 transfer(newTable); 247 table = newTable; 248 threshold = newCapacity; 249 } 250 251 /** 252 * Transfer all entries from current table to newTable. 253 */ 254 private void transfer(Entry<V>[] newTable) { 255 Entry<V>[] src = table; 256 int newCapacity = newTable.length; 257 for (int j = 0; j < src.length; j++) { 258 Entry<V> e = src[j]; 259 if (e != null) { 260 src[j] = null; 261 do { 262 Entry<V> next = e.next; 263 int i = indexFor(e.hash, newCapacity); 264 e.next = newTable[i]; 265 newTable[i] = e; 266 e = next; 267 } while (e != null); 268 } 269 } 270 } 271 272 /** 273 * Returns one random item in the map. 274 * If this map is empty, return null. 275 * 276 * <p> 277 * This method is useful to obtain the value from a map that only contains one element. 278 */ 279 public Entry<V> getOne() { 280 for( Entry<V> e : table ) { 281 if(e!=null) 282 return e; 283 } 284 return null; 285 } 286 287 public Collection<QName> keySet() { 288 Set<QName> r = new HashSet<QName>(); 289 for (Entry<V> e : entrySet()) { 290 r.add(e.createQName()); 291 } 292 return r; 293 } 294 295 public Iterable<V> values() { 296 return views; 297 } 298 299 private transient Iterable<V> views = new Iterable<V>() { 300 public Iterator<V> iterator() { 301 return new ValueIterator(); 302 } 303 }; 304 305 private abstract class HashIterator<E> implements Iterator<E> { 306 Entry<V> next; // next entry to return 307 int index; // current slot 308 309 HashIterator() { 310 Entry<V>[] t = table; 311 int i = t.length; 312 Entry<V> n = null; 313 if (size != 0) { // advance to first entry 314 while (i > 0 && (n = t[--i]) == null) 315 ; 316 } 317 next = n; 318 index = i; 319 } 320 321 public boolean hasNext() { 322 return next != null; 323 } 324 325 Entry<V> nextEntry() { 326 Entry<V> e = next; 327 if (e == null) 328 throw new NoSuchElementException(); 329 330 Entry<V> n = e.next; 331 Entry<V>[] t = table; 332 int i = index; 333 while (n == null && i > 0) 334 n = t[--i]; 335 index = i; 336 next = n; 337 return e; 338 } 339 340 public void remove() { 341 throw new UnsupportedOperationException(); 342 } 343 } 344 345 private class ValueIterator extends HashIterator<V> { 346 public V next() { 347 return nextEntry().value; 348 } 349 } 350 351 public boolean containsKey(@NotNull String nsUri,String localName) { 352 return getEntry(nsUri,localName)!=null; 353 } 354 355 356 /** 357 * Returns true if this map is empty. 358 */ 359 public boolean isEmpty() { 360 return size == 0; 361 } 362 363 364 public static final class Entry<V> { 365 /** The namespace URI. */ 366 public final String nsUri; 367 368 /** The localPart. */ 369 public final String localName; 370 371 V value; 372 final int hash; 373 Entry<V> next; 374 375 /** 376 * Create new entry. 377 */ 378 Entry(int h, String nsUri, String localName, V v, Entry<V> n) { 379 value = v; 380 next = n; 381 this.nsUri = nsUri; 382 this.localName = localName; 383 hash = h; 384 } 385 386 /** 387 * Creates a new QName object from {@link #nsUri} and {@link #localName}. 388 */ 389 public QName createQName() { 390 return new QName(nsUri,localName); 391 } 392 393 public V getValue() { 394 return value; 395 } 396 397 public V setValue(V newValue) { 398 V oldValue = value; 399 value = newValue; 400 return oldValue; 401 } 402 403 public boolean equals(Object o) { 404 if (!(o instanceof Entry)) 405 return false; 406 Entry e = (Entry)o; 407 String k1 = nsUri; 408 String k2 = e.nsUri; 409 String k3 = localName; 410 String k4 = e.localName; 411 if (k1.equals(k2) && k3.equals(k4)) { 412 Object v1 = getValue(); 413 Object v2 = e.getValue(); 414 if (v1 == v2 || (v1 != null && v1.equals(v2))) 415 return true; 416 } 417 return false; 418 } 419 420 public int hashCode() { 421 return ( localName.hashCode()) ^ 422 (value==null ? 0 : value.hashCode()); 423 } 424 425 public String toString() { 426 return '"'+nsUri +"\",\"" +localName + "\"=" + getValue(); 427 } 428 } 429 430 public Set<Entry<V>> entrySet() { 431 Set<Entry<V>> es = entrySet; 432 return es != null ? es : (entrySet = new EntrySet()); 433 } 434 435 private Iterator<Entry<V>> newEntryIterator() { 436 return new EntryIterator(); 437 } 438 439 private class EntryIterator extends HashIterator<Entry<V>> { 440 public Entry<V> next() { 441 return nextEntry(); 442 } 443 } 444 private class EntrySet extends AbstractSet<Entry<V>> { 445 public Iterator<Entry<V>> iterator() { 446 return newEntryIterator(); 447 } 448 public boolean contains(Object o) { 449 if (!(o instanceof Entry)) 450 return false; 451 Entry<V> e = (Entry<V>) o; 452 Entry<V> candidate = getEntry(e.nsUri,e.localName); 453 return candidate != null && candidate.equals(e); 454 } 455 public boolean remove(Object o) { 456 throw new UnsupportedOperationException(); 457 } 458 public int size() { 459 return size; 460 } 461 } 462 463 private Entry<V> getEntry(@NotNull String nsUri,String localName) { 464 int hash = hash(localName); 465 int i = indexFor(hash, table.length); 466 Entry<V> e = table[i]; 467 while (e != null && !(localName.equals(e.localName) && nsUri.equals(e.nsUri))) 468 e = e.next; 469 return e; 470 } 471 472 public String toString() { 473 StringBuilder buf = new StringBuilder(); 474 buf.append('{'); 475 476 for( Entry<V> e : entrySet() ) { 477 if(buf.length()>1) 478 buf.append(','); 479 buf.append('['); 480 buf.append(e); 481 buf.append(']'); 482 } 483 484 buf.append('}'); 485 return buf.toString(); 486 } 487 }