1 /*
2 * Copyright (c) 1997, 2012, 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.bind.v2.util;
27 import java.util.AbstractSet;
28 import java.util.Iterator;
29 import java.util.NoSuchElementException;
30 import java.util.Set;
31 import java.util.Map;
32 import java.util.Collection;
33 import java.util.HashSet;
34
35 import javax.xml.namespace.QName;
36
37 import com.sun.xml.internal.bind.v2.runtime.Name;
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 // keys must be interned
111 assert localname == localname.intern();
112 assert namespaceUri == namespaceUri.intern();
113
114 int hash = hash(localname);
115 int i = indexFor(hash, table.length);
116
117 for (Entry<V> e = table[i]; e != null; e = e.next) {
118 if (e.hash == hash && localname == e.localName && namespaceUri==e.nsUri) {
119 e.value = value;
120 return;
121 }
122 }
123
124 addEntry(hash, namespaceUri,localname, value, i);
125
126 }
127
128 public void put(QName name, V value ) {
129 put(name.getNamespaceURI(),name.getLocalPart(),value);
130 }
131
132 public void put(Name name, V value ) {
133 put(name.nsUri,name.localName,value);
134 }
135
136 /**
137 * Returns the value to which the specified keys are mapped in this QNameMap,
138 * or <tt>null</tt> if the map contains no mapping for this key.
139 *
140 * @param nsUri the namespaceUri key whose associated value is to be returned.
141 * @param localPart the localPart key whose associated value is to be returned.
142 * @return the value to which this map maps the specified set of keya, or
143 * <tt>null</tt> if the map contains no mapping for this set of keys.
144 * @see #put(String,String, Object)
145 */
146 public V get( String nsUri, String localPart ) {
147 Entry<V> e = getEntry(nsUri,localPart);
148 if(e==null) return null;
149 else return e.value;
150 }
151
152 public V get( QName name ) {
153 return get(name.getNamespaceURI(),name.getLocalPart());
154 }
155
156 /**
157 * Returns the number of keys-value mappings in this map.
158 *
159 * @return the number of keys-value mappings in this map.
160 */
161 public int size() {
162 return size;
163 }
164
165 /**
166 * Copies all of the mappings from the specified map to this map
167 * These mappings will replace any mappings that
168 * this map had for any of the keys currently in the specified map.
169 *
170 * @param map mappings to be stored in this map.
171 *
172 */
173 public QNameMap<V> putAll(QNameMap<? extends V> map) {
174 int numKeysToBeAdded = map.size();
175 if (numKeysToBeAdded == 0)
176 return this;
177
178
179 if (numKeysToBeAdded > threshold) {
180 int targetCapacity = numKeysToBeAdded;
181 if (targetCapacity > MAXIMUM_CAPACITY)
182 targetCapacity = MAXIMUM_CAPACITY;
183 int newCapacity = table.length;
184 while (newCapacity < targetCapacity)
185 newCapacity <<= 1;
186 if (newCapacity > table.length)
187 resize(newCapacity);
188 }
189
190 for( Entry<? extends V> e : map.entrySet() )
191 put(e.nsUri,e.localName,e.getValue());
192 return this;
193 }
194
195
196 /**
197 * Returns a hash value for the specified object.The hash value is computed
198 * for the localName.
199 */
200 private static int hash(String x) {
201 int h = x.hashCode();
202
203 h += ~(h << 9);
204 h ^= (h >>> 14);
205 h += (h << 4);
206 h ^= (h >>> 10);
207 return h;
208 }
209
210 /**
211 * Returns index for hash code h.
212 */
213 private static int indexFor(int h, int length) {
214 return h & (length-1);
215 }
216
217 /**
218 * Add a new entry with the specified keys, value and hash code to
219 * the specified bucket. It is the responsibility of this
220 * method to resize the table if appropriate.
221 *
222 */
223 private void addEntry(int hash, String nsUri, String localName, V value, int bucketIndex) {
224 Entry<V> e = table[bucketIndex];
225 table[bucketIndex] = new Entry<V>(hash, nsUri, localName, value, e);
226 if (size++ >= threshold)
227 resize(2 * table.length);
228 }
229
230
231 /**
232 * Rehashes the contents of this map into a new array with a
233 * larger capacity. This method is called automatically when the
234 * number of keys in this map reaches its threshold.
235 */
236 private void resize(int newCapacity) {
237 Entry[] oldTable = table;
238 int oldCapacity = oldTable.length;
239 if (oldCapacity == MAXIMUM_CAPACITY) {
240 threshold = Integer.MAX_VALUE;
241 return;
242 }
243
244 Entry[] newTable = new Entry[newCapacity];
245 transfer(newTable);
246 table = newTable;
247 threshold = newCapacity;
248 }
249
250 /**
251 * Transfer all entries from current table to newTable.
252 */
253 private void transfer(Entry<V>[] newTable) {
254 Entry<V>[] src = table;
255 int newCapacity = newTable.length;
256 for (int j = 0; j < src.length; j++) {
257 Entry<V> e = src[j];
258 if (e != null) {
259 src[j] = null;
260 do {
261 Entry<V> next = e.next;
262 int i = indexFor(e.hash, newCapacity);
263 e.next = newTable[i];
264 newTable[i] = e;
265 e = next;
266 } while (e != null);
267 }
268 }
269 }
270
271 /**
272 * Returns one random item in the map.
273 * If this map is empty, return null.
274 *
275 * <p>
276 * This method is useful to obtain the value from a map that only contains one element.
277 */
278 public Entry<V> getOne() {
279 for( Entry<V> e : table ) {
280 if(e!=null)
281 return e;
282 }
283 return null;
284 }
285
286 public Collection<QName> keySet() {
287 Set<QName> r = new HashSet<QName>();
288 for (Entry<V> e : entrySet()) {
289 r.add(e.createQName());
290 }
291 return r;
292 }
293
294 private abstract class HashIterator<E> implements Iterator<E> {
295 Entry<V> next; // next entry to return
296 int index; // current slot
297
298 HashIterator() {
299 Entry<V>[] t = table;
300 int i = t.length;
301 Entry<V> n = null;
302 if (size != 0) { // advance to first entry
303 while (i > 0 && (n = t[--i]) == null) {}
304 }
305 next = n;
306 index = i;
307 }
308
309 public boolean hasNext() {
310 return next != null;
311 }
312
313 Entry<V> nextEntry() {
314 Entry<V> e = next;
315 if (e == null)
316 throw new NoSuchElementException();
317
318 Entry<V> n = e.next;
319 Entry<V>[] t = table;
320 int i = index;
321 while (n == null && i > 0)
322 n = t[--i];
323 index = i;
324 next = n;
325 return e;
326 }
327
328 public void remove() {
329 throw new UnsupportedOperationException();
330 }
331 }
332
333 public boolean containsKey(String nsUri,String localName) {
334 return getEntry(nsUri,localName)!=null;
335 }
336
337
338 /**
339 * Returns true if this map is empty.
340 */
341 public boolean isEmpty() {
342 return size == 0;
343 }
344
345
346 public static final class Entry<V> {
347 /** The namespace URI. */
348 public final String nsUri;
349
350 /** The localPart. */
351 public final String localName;
352
353 V value;
354 final int hash;
355 Entry<V> next;
356
357 /**
358 * Create new entry.
359 */
360 Entry(int h, String nsUri, String localName, V v, Entry<V> n) {
361 value = v;
362 next = n;
363 this.nsUri = nsUri;
364 this.localName = localName;
365 hash = h;
366 }
367
368 /**
369 * Creates a new QName object from {@link #nsUri} and {@link #localName}.
370 */
371 public QName createQName() {
372 return new QName(nsUri,localName);
373 }
374
375 public V getValue() {
376 return value;
377 }
378
379 public V setValue(V newValue) {
380 V oldValue = value;
381 value = newValue;
382 return oldValue;
383 }
384
385 @Override
386 public boolean equals(Object o) {
387 if (!(o instanceof Entry))
388 return false;
389 Entry e = (Entry)o;
390 String k1 = nsUri;
391 String k2 = e.nsUri;
392 String k3 = localName;
393 String k4 = e.localName;
394 if (k1 == k2 || (k1 != null && k1.equals(k2)) &&
395 (k3 == k4 ||(k3 !=null && k3.equals(k4)))) {
396 Object v1 = getValue();
397 Object v2 = e.getValue();
398 if (v1 == v2 || (v1 != null && v1.equals(v2)))
399 return true;
400 }
401 return false;
402 }
403
404 @Override
405 public int hashCode() {
406 return ( localName.hashCode()) ^
407 (value==null ? 0 : value.hashCode());
408 }
409
410 @Override
411 public String toString() {
412 return '"'+nsUri +"\",\"" +localName + "\"=" + getValue();
413 }
414 }
415
416 public Set<Entry<V>> entrySet() {
417 Set<Entry<V>> es = entrySet;
418 return es != null ? es : (entrySet = new EntrySet());
419 }
420
421 private Iterator<Entry<V>> newEntryIterator() {
422 return new EntryIterator();
423 }
424
425 private class EntryIterator extends HashIterator<Entry<V>> {
426 public Entry<V> next() {
427 return nextEntry();
428 }
429 }
430 private class EntrySet extends AbstractSet<Entry<V>> {
431 public Iterator<Entry<V>> iterator() {
432 return newEntryIterator();
433 }
434 @Override
435 public boolean contains(Object o) {
436 if (!(o instanceof Entry))
437 return false;
438 Entry<V> e = (Entry<V>) o;
439 Entry<V> candidate = getEntry(e.nsUri,e.localName);
440 return candidate != null && candidate.equals(e);
441 }
442 @Override
443 public boolean remove(Object o) {
444 throw new UnsupportedOperationException();
445 }
446 public int size() {
447 return size;
448 }
449 }
450
451 private Entry<V> getEntry(String nsUri,String localName) {
452 // strings must be interned
453 assert nsUri==nsUri.intern();
454 assert localName==localName.intern();
455
456 int hash = hash(localName);
457 int i = indexFor(hash, table.length);
458 Entry<V> e = table[i];
459 while (e != null && !(localName == e.localName && nsUri == e.nsUri))
460 e = e.next;
461 return e;
462 }
463
464 @Override
465 public String toString() {
466 StringBuilder buf = new StringBuilder();
467 buf.append('{');
468
469 for( Entry<V> e : entrySet() ) {
470 if(buf.length()>1)
471 buf.append(',');
472 buf.append('[');
473 buf.append(e);
474 buf.append(']');
475 }
476
477 buf.append('}');
478 return buf.toString();
479 }
480 }