001: /*
002: * Copyright 2006 Sun Microsystems, Inc. All Rights Reserved.
003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004: *
005: * This code is free software; you can redistribute it and/or modify it
006: * under the terms of the GNU General Public License version 2 only, as
007: * published by the Free Software Foundation. Sun designates this
008: * particular file as subject to the "Classpath" exception as provided
009: * by Sun in the LICENSE file that accompanied this code.
010: *
011: * This code is distributed in the hope that it will be useful, but WITHOUT
012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014: * version 2 for more details (a copy is included in the LICENSE file that
015: * accompanied this code).
016: *
017: * You should have received a copy of the GNU General Public License version
018: * 2 along with this work; if not, write to the Free Software Foundation,
019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022: * CA 95054 USA or visit www.sun.com if you need additional information or
023: * have any questions.
024: */
025:
026: package com.sun.xml.internal.bind.v2.util;
027:
028: import java.util.AbstractSet;
029: import java.util.Iterator;
030: import java.util.NoSuchElementException;
031: import java.util.Set;
032: import java.util.Map;
033: import java.util.Collection;
034: import java.util.HashSet;
035:
036: import javax.xml.namespace.QName;
037:
038: import com.sun.xml.internal.bind.v2.runtime.Name;
039:
040: /**
041: * Map keyed by {@link QName}.
042: *
043: * This specialized map allows a look up operation without constructing
044: * a new QName instance, for a performance reason. This {@link Map} assumes
045: * that both namespace URI and local name are {@link String#intern() intern}ed.
046: *
047: * @since JAXB 2.0
048: */
049: public final class QNameMap<V> {
050: /**
051: * The default initial capacity - MUST be a power of two.
052: */
053: private static final int DEFAULT_INITIAL_CAPACITY = 16;
054:
055: /**
056: * The maximum capacity, used if a higher value is implicitly specified
057: * by either of the constructors with arguments.
058: * MUST be a power of two <= 1<<30.
059: */
060: private static final int MAXIMUM_CAPACITY = 1 << 30;
061:
062: /**
063: * The table, resized as necessary. Length MUST Always be a power of two.
064: */
065: transient Entry<V>[] table = new Entry[DEFAULT_INITIAL_CAPACITY];
066:
067: /**
068: * The number of key-value mappings contained in this identity hash map.
069: */
070: transient int size;
071:
072: /**
073: * The next size value at which to resize . Taking it as
074: * MAXIMUM_CAPACITY
075: * @serial
076: */
077: private int threshold;
078:
079: /**
080: * The load factor used when none specified in constructor.
081: **/
082: private static final float DEFAULT_LOAD_FACTOR = 0.75f;
083:
084: /**
085: * Gives an entrySet view of this map
086: */
087: private Set<Entry<V>> entrySet = null;
088:
089: public QNameMap() {
090: threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
091: table = new Entry[DEFAULT_INITIAL_CAPACITY];
092:
093: }
094:
095: /**
096: * Associates the specified value with the specified keys in this map.
097: * If the map previously contained a mapping for this key, the old
098: * value is replaced.
099: *
100: * @param namespaceUri First key with which the specified value is to be associated.
101: * @param localname Second key with which the specified value is to be associated.
102: * @param value value to be associated with the specified key.
103: *
104: */
105: public void put(String namespaceUri, String localname, V value) {
106: //keys cannot be null
107: assert localname != null;
108: assert namespaceUri != null;
109: // keys must be interned
110: assert localname == localname.intern();
111: assert namespaceUri == namespaceUri.intern();
112:
113: int hash = hash(localname);
114: int i = indexFor(hash, table.length);
115:
116: for (Entry<V> e = table[i]; e != null; e = e.next) {
117: if (e.hash == hash && localname == e.localName
118: && 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)
149: return null;
150: else
151: return e.value;
152: }
153:
154: public V get(QName name) {
155: return get(name.getNamespaceURI(), name.getLocalPart());
156: }
157:
158: /**
159: * Returns the number of keys-value mappings in this map.
160: *
161: * @return the number of keys-value mappings in this map.
162: */
163: public int size() {
164: return size;
165: }
166:
167: /**
168: * Copies all of the mappings from the specified map to this map
169: * These mappings will replace any mappings that
170: * this map had for any of the keys currently in the specified map.
171: *
172: * @param map mappings to be stored in this map.
173: *
174: */
175: public QNameMap<V> putAll(QNameMap<? extends V> map) {
176: int numKeysToBeAdded = map.size();
177: if (numKeysToBeAdded == 0)
178: return this ;
179:
180: if (numKeysToBeAdded > threshold) {
181: int targetCapacity = numKeysToBeAdded;
182: if (targetCapacity > MAXIMUM_CAPACITY)
183: targetCapacity = MAXIMUM_CAPACITY;
184: int newCapacity = table.length;
185: while (newCapacity < targetCapacity)
186: newCapacity <<= 1;
187: if (newCapacity > table.length)
188: resize(newCapacity);
189: }
190:
191: for (Entry<? extends V> e : map.entrySet())
192: put(e.nsUri, e.localName, e.getValue());
193: return this ;
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,
224: V value, int bucketIndex) {
225: Entry<V> e = table[bucketIndex];
226: table[bucketIndex] = new Entry<V>(hash, nsUri, localName,
227: value, e);
228: if (size++ >= threshold)
229: resize(2 * table.length);
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: private abstract class HashIterator<E> implements Iterator<E> {
296: Entry<V> next; // next entry to return
297: int index; // current slot
298:
299: HashIterator() {
300: Entry<V>[] t = table;
301: int i = t.length;
302: Entry<V> n = null;
303: if (size != 0) { // advance to first entry
304: while (i > 0 && (n = t[--i]) == null)
305: ;
306: }
307: next = n;
308: index = i;
309: }
310:
311: public boolean hasNext() {
312: return next != null;
313: }
314:
315: Entry<V> nextEntry() {
316: Entry<V> e = next;
317: if (e == null)
318: throw new NoSuchElementException();
319:
320: Entry<V> n = e.next;
321: Entry<V>[] t = table;
322: int i = index;
323: while (n == null && i > 0)
324: n = t[--i];
325: index = i;
326: next = n;
327: return e;
328: }
329:
330: public void remove() {
331: throw new UnsupportedOperationException();
332: }
333: }
334:
335: public boolean containsKey(String nsUri, String localName) {
336: return getEntry(nsUri, localName) != null;
337: }
338:
339: /**
340: * Returns true if this map is empty.
341: */
342: public boolean isEmpty() {
343: return size == 0;
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: public boolean equals(Object o) {
386: if (!(o instanceof Entry))
387: return false;
388: Entry e = (Entry) o;
389: String k1 = nsUri;
390: String k2 = e.nsUri;
391: String k3 = localName;
392: String k4 = e.localName;
393: if (k1 == k2 || (k1 != null && k1.equals(k2))
394: && (k3 == k4 || (k3 != null && k3.equals(k4)))) {
395: Object v1 = getValue();
396: Object v2 = e.getValue();
397: if (v1 == v2 || (v1 != null && v1.equals(v2)))
398: return true;
399: }
400: return false;
401: }
402:
403: public int hashCode() {
404: return (localName.hashCode())
405: ^ (value == null ? 0 : value.hashCode());
406: }
407:
408: public String toString() {
409: return '"' + nsUri + "\",\"" + localName + "\"="
410: + getValue();
411: }
412: }
413:
414: public Set<Entry<V>> entrySet() {
415: Set<Entry<V>> es = entrySet;
416: return es != null ? es : (entrySet = new EntrySet());
417: }
418:
419: private Iterator<Entry<V>> newEntryIterator() {
420: return new EntryIterator();
421: }
422:
423: private class EntryIterator extends HashIterator<Entry<V>> {
424: public Entry<V> next() {
425: return nextEntry();
426: }
427: }
428:
429: private class EntrySet extends AbstractSet<Entry<V>> {
430: public Iterator<Entry<V>> iterator() {
431: return newEntryIterator();
432: }
433:
434: public boolean contains(Object o) {
435: if (!(o instanceof Entry))
436: return false;
437: Entry<V> e = (Entry<V>) o;
438: Entry<V> candidate = getEntry(e.nsUri, e.localName);
439: return candidate != null && candidate.equals(e);
440: }
441:
442: public boolean remove(Object o) {
443: throw new UnsupportedOperationException();
444: }
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
460: && !(localName == e.localName && nsUri == e.nsUri))
461: e = e.next;
462: return e;
463: }
464:
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: }
|