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