001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common Development
008: * and Distribution License("CDDL") (collectively, the "License"). You
009: * may not use this file except in compliance with the License. You can obtain
010: * a copy of the License at https://glassfish.dev.java.net/public/CDDL+GPL.html
011: * or glassfish/bootstrap/legal/LICENSE.txt. See the License for the specific
012: * language governing permissions and limitations under the License.
013: *
014: * When distributing the software, include this License Header Notice in each
015: * file and include the License file at glassfish/bootstrap/legal/LICENSE.txt.
016: * Sun designates this particular file as subject to the "Classpath" exception
017: * as provided by Sun in the GPL Version 2 section of the License file that
018: * accompanied this code. If applicable, add the following below the License
019: * Header, with the fields enclosed by brackets [] replaced by your own
020: * identifying information: "Portions Copyrighted [year]
021: * [name of copyright owner]"
022: *
023: * Contributor(s):
024: *
025: * If you wish your version of this file to be governed by only the CDDL or
026: * only the GPL Version 2, indicate your decision by adding "[Contributor]
027: * elects to include this software in this distribution under the [CDDL or GPL
028: * Version 2] license." If you don't indicate a single choice of license, a
029: * recipient has the option to distribute your version of this file under
030: * either the CDDL, the GPL Version 2 or to extend the choice of license to
031: * its licensees as provided above. However, if you add GPL Version 2 code
032: * and therefore, elected the GPL Version 2 license, then the option applies
033: * only if the new code is made subject to such option by the copyright
034: * holder.
035: */
036:
037: package com.sun.xml.bind.v2.util;
038:
039: import java.util.AbstractSet;
040: import java.util.Iterator;
041: import java.util.NoSuchElementException;
042: import java.util.Set;
043: import java.util.Map;
044: import java.util.Collection;
045: import java.util.HashSet;
046:
047: import javax.xml.namespace.QName;
048:
049: import com.sun.xml.bind.v2.runtime.Name;
050:
051: /**
052: * Map keyed by {@link QName}.
053: *
054: * This specialized map allows a look up operation without constructing
055: * a new QName instance, for a performance reason. This {@link Map} assumes
056: * that both namespace URI and local name are {@link String#intern() intern}ed.
057: *
058: * @since JAXB 2.0
059: */
060: public final class QNameMap<V> {
061: /**
062: * The default initial capacity - MUST be a power of two.
063: */
064: private static final int DEFAULT_INITIAL_CAPACITY = 16;
065:
066: /**
067: * The maximum capacity, used if a higher value is implicitly specified
068: * by either of the constructors with arguments.
069: * MUST be a power of two <= 1<<30.
070: */
071: private static final int MAXIMUM_CAPACITY = 1 << 30;
072:
073: /**
074: * The table, resized as necessary. Length MUST Always be a power of two.
075: */
076: transient Entry<V>[] table = new Entry[DEFAULT_INITIAL_CAPACITY];
077:
078: /**
079: * The number of key-value mappings contained in this identity hash map.
080: */
081: transient int size;
082:
083: /**
084: * The next size value at which to resize . Taking it as
085: * MAXIMUM_CAPACITY
086: * @serial
087: */
088: private int threshold;
089:
090: /**
091: * The load factor used when none specified in constructor.
092: **/
093: private static final float DEFAULT_LOAD_FACTOR = 0.75f;
094:
095: /**
096: * Gives an entrySet view of this map
097: */
098: private Set<Entry<V>> entrySet = null;
099:
100: public QNameMap() {
101: threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
102: table = new Entry[DEFAULT_INITIAL_CAPACITY];
103:
104: }
105:
106: /**
107: * Associates the specified value with the specified keys in this map.
108: * If the map previously contained a mapping for this key, the old
109: * value is replaced.
110: *
111: * @param namespaceUri First key with which the specified value is to be associated.
112: * @param localname Second key with which the specified value is to be associated.
113: * @param value value to be associated with the specified key.
114: *
115: */
116: public void put(String namespaceUri, String localname, V value) {
117: //keys cannot be null
118: assert localname != null;
119: assert namespaceUri != null;
120: // keys must be interned
121: assert localname == localname.intern();
122: assert namespaceUri == namespaceUri.intern();
123:
124: int hash = hash(localname);
125: int i = indexFor(hash, table.length);
126:
127: for (Entry<V> e = table[i]; e != null; e = e.next) {
128: if (e.hash == hash && localname == e.localName
129: && namespaceUri == e.nsUri) {
130: e.value = value;
131: return;
132: }
133: }
134:
135: addEntry(hash, namespaceUri, localname, value, i);
136:
137: }
138:
139: public void put(QName name, V value) {
140: put(name.getNamespaceURI(), name.getLocalPart(), value);
141: }
142:
143: public void put(Name name, V value) {
144: put(name.nsUri, name.localName, value);
145: }
146:
147: /**
148: * Returns the value to which the specified keys are mapped in this QNameMap,
149: * or <tt>null</tt> if the map contains no mapping for this key.
150: *
151: * @param nsUri the namespaceUri key whose associated value is to be returned.
152: * @param localPart the localPart key whose associated value is to be returned.
153: * @return the value to which this map maps the specified set of keya, or
154: * <tt>null</tt> if the map contains no mapping for this set of keys.
155: * @see #put(String,String, Object)
156: */
157: public V get(String nsUri, String localPart) {
158: Entry<V> e = getEntry(nsUri, localPart);
159: if (e == null)
160: return null;
161: else
162: return e.value;
163: }
164:
165: public V get(QName name) {
166: return get(name.getNamespaceURI(), name.getLocalPart());
167: }
168:
169: /**
170: * Returns the number of keys-value mappings in this map.
171: *
172: * @return the number of keys-value mappings in this map.
173: */
174: public int size() {
175: return size;
176: }
177:
178: /**
179: * Copies all of the mappings from the specified map to this map
180: * These mappings will replace any mappings that
181: * this map had for any of the keys currently in the specified map.
182: *
183: * @param map mappings to be stored in this map.
184: *
185: */
186: public QNameMap<V> putAll(QNameMap<? extends V> map) {
187: int numKeysToBeAdded = map.size();
188: if (numKeysToBeAdded == 0)
189: return this ;
190:
191: if (numKeysToBeAdded > threshold) {
192: int targetCapacity = numKeysToBeAdded;
193: if (targetCapacity > MAXIMUM_CAPACITY)
194: targetCapacity = MAXIMUM_CAPACITY;
195: int newCapacity = table.length;
196: while (newCapacity < targetCapacity)
197: newCapacity <<= 1;
198: if (newCapacity > table.length)
199: resize(newCapacity);
200: }
201:
202: for (Entry<? extends V> e : map.entrySet())
203: put(e.nsUri, e.localName, e.getValue());
204: return this ;
205: }
206:
207: /**
208: * Returns a hash value for the specified object.The hash value is computed
209: * for the localName.
210: */
211: private static int hash(String x) {
212: int h = x.hashCode();
213:
214: h += ~(h << 9);
215: h ^= (h >>> 14);
216: h += (h << 4);
217: h ^= (h >>> 10);
218: return h;
219: }
220:
221: /**
222: * Returns index for hash code h.
223: */
224: private static int indexFor(int h, int length) {
225: return h & (length - 1);
226: }
227:
228: /**
229: * Add a new entry with the specified keys, value and hash code to
230: * the specified bucket. It is the responsibility of this
231: * method to resize the table if appropriate.
232: *
233: */
234: private void addEntry(int hash, String nsUri, String localName,
235: V value, int bucketIndex) {
236: Entry<V> e = table[bucketIndex];
237: table[bucketIndex] = new Entry<V>(hash, nsUri, localName,
238: value, e);
239: if (size++ >= threshold)
240: resize(2 * table.length);
241: }
242:
243: /**
244: * Rehashes the contents of this map into a new array with a
245: * larger capacity. This method is called automatically when the
246: * number of keys in this map reaches its threshold.
247: */
248: private void resize(int newCapacity) {
249: Entry[] oldTable = table;
250: int oldCapacity = oldTable.length;
251: if (oldCapacity == MAXIMUM_CAPACITY) {
252: threshold = Integer.MAX_VALUE;
253: return;
254: }
255:
256: Entry[] newTable = new Entry[newCapacity];
257: transfer(newTable);
258: table = newTable;
259: threshold = newCapacity;
260: }
261:
262: /**
263: * Transfer all entries from current table to newTable.
264: */
265: private void transfer(Entry<V>[] newTable) {
266: Entry<V>[] src = table;
267: int newCapacity = newTable.length;
268: for (int j = 0; j < src.length; j++) {
269: Entry<V> e = src[j];
270: if (e != null) {
271: src[j] = null;
272: do {
273: Entry<V> next = e.next;
274: int i = indexFor(e.hash, newCapacity);
275: e.next = newTable[i];
276: newTable[i] = e;
277: e = next;
278: } while (e != null);
279: }
280: }
281: }
282:
283: /**
284: * Returns one random item in the map.
285: * If this map is empty, return null.
286: *
287: * <p>
288: * This method is useful to obtain the value from a map that only contains one element.
289: */
290: public Entry<V> getOne() {
291: for (Entry<V> e : table) {
292: if (e != null)
293: return e;
294: }
295: return null;
296: }
297:
298: public Collection<QName> keySet() {
299: Set<QName> r = new HashSet<QName>();
300: for (Entry<V> e : entrySet()) {
301: r.add(e.createQName());
302: }
303: return r;
304: }
305:
306: private abstract class HashIterator<E> implements Iterator<E> {
307: Entry<V> next; // next entry to return
308: int index; // current slot
309:
310: HashIterator() {
311: Entry<V>[] t = table;
312: int i = t.length;
313: Entry<V> n = null;
314: if (size != 0) { // advance to first entry
315: while (i > 0 && (n = t[--i]) == null)
316: ;
317: }
318: next = n;
319: index = i;
320: }
321:
322: public boolean hasNext() {
323: return next != null;
324: }
325:
326: Entry<V> nextEntry() {
327: Entry<V> e = next;
328: if (e == null)
329: throw new NoSuchElementException();
330:
331: Entry<V> n = e.next;
332: Entry<V>[] t = table;
333: int i = index;
334: while (n == null && i > 0)
335: n = t[--i];
336: index = i;
337: next = n;
338: return e;
339: }
340:
341: public void remove() {
342: throw new UnsupportedOperationException();
343: }
344: }
345:
346: public boolean containsKey(String nsUri, String localName) {
347: return getEntry(nsUri, localName) != null;
348: }
349:
350: /**
351: * Returns true if this map is empty.
352: */
353: public boolean isEmpty() {
354: return size == 0;
355: }
356:
357: public static final class Entry<V> {
358: /** The namespace URI. */
359: public final String nsUri;
360:
361: /** The localPart. */
362: public final String localName;
363:
364: V value;
365: final int hash;
366: Entry<V> next;
367:
368: /**
369: * Create new entry.
370: */
371: Entry(int h, String nsUri, String localName, V v, Entry<V> n) {
372: value = v;
373: next = n;
374: this .nsUri = nsUri;
375: this .localName = localName;
376: hash = h;
377: }
378:
379: /**
380: * Creates a new QName object from {@link #nsUri} and {@link #localName}.
381: */
382: public QName createQName() {
383: return new QName(nsUri, localName);
384: }
385:
386: public V getValue() {
387: return value;
388: }
389:
390: public V setValue(V newValue) {
391: V oldValue = value;
392: value = newValue;
393: return oldValue;
394: }
395:
396: public boolean equals(Object o) {
397: if (!(o instanceof Entry))
398: return false;
399: Entry e = (Entry) o;
400: String k1 = nsUri;
401: String k2 = e.nsUri;
402: String k3 = localName;
403: String k4 = e.localName;
404: if (k1 == k2 || (k1 != null && k1.equals(k2))
405: && (k3 == k4 || (k3 != null && k3.equals(k4)))) {
406: Object v1 = getValue();
407: Object v2 = e.getValue();
408: if (v1 == v2 || (v1 != null && v1.equals(v2)))
409: return true;
410: }
411: return false;
412: }
413:
414: public int hashCode() {
415: return (localName.hashCode())
416: ^ (value == null ? 0 : value.hashCode());
417: }
418:
419: public String toString() {
420: return '"' + nsUri + "\",\"" + localName + "\"="
421: + getValue();
422: }
423: }
424:
425: public Set<Entry<V>> entrySet() {
426: Set<Entry<V>> es = entrySet;
427: return es != null ? es : (entrySet = new EntrySet());
428: }
429:
430: private Iterator<Entry<V>> newEntryIterator() {
431: return new EntryIterator();
432: }
433:
434: private class EntryIterator extends HashIterator<Entry<V>> {
435: public Entry<V> next() {
436: return nextEntry();
437: }
438: }
439:
440: private class EntrySet extends AbstractSet<Entry<V>> {
441: public Iterator<Entry<V>> iterator() {
442: return newEntryIterator();
443: }
444:
445: public boolean contains(Object o) {
446: if (!(o instanceof Entry))
447: return false;
448: Entry<V> e = (Entry<V>) o;
449: Entry<V> candidate = getEntry(e.nsUri, e.localName);
450: return candidate != null && candidate.equals(e);
451: }
452:
453: public boolean remove(Object o) {
454: throw new UnsupportedOperationException();
455: }
456:
457: public int size() {
458: return size;
459: }
460: }
461:
462: private Entry<V> getEntry(String nsUri, String localName) {
463: // strings must be interned
464: assert nsUri == nsUri.intern();
465: assert localName == localName.intern();
466:
467: int hash = hash(localName);
468: int i = indexFor(hash, table.length);
469: Entry<V> e = table[i];
470: while (e != null
471: && !(localName == e.localName && nsUri == e.nsUri))
472: e = e.next;
473: return e;
474: }
475:
476: public String toString() {
477: StringBuilder buf = new StringBuilder();
478: buf.append('{');
479:
480: for (Entry<V> e : entrySet()) {
481: if (buf.length() > 1)
482: buf.append(',');
483: buf.append('[');
484: buf.append(e);
485: buf.append(']');
486: }
487:
488: buf.append('}');
489: return buf.toString();
490: }
491: }
|