001: /*
002: * Copyright 2001-2005 Stephen Colebourne
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.joda.time.convert;
017:
018: /**
019: * A set of converters, which allows exact converters to be quickly
020: * selected. This class is threadsafe because it is (essentially) immutable.
021: *
022: * @author Brian S O'Neill
023: * @since 1.0
024: */
025: class ConverterSet {
026: private final Converter[] iConverters;
027:
028: // A simple immutable hashtable: closed hashing, linear probing, sized
029: // power of 2, at least one null slot.
030: private Entry[] iSelectEntries;
031:
032: ConverterSet(Converter[] converters) {
033: // Since this is a package private constructor, we trust ourselves not
034: // to alter the array outside this class.
035: iConverters = converters;
036: iSelectEntries = new Entry[1 << 4]; // 16
037: }
038:
039: /**
040: * Returns the closest matching converter for the given type, or null if
041: * none found.
042: *
043: * @param type type to select, which may be null
044: * @throws IllegalStateException if multiple converters match the type
045: * equally well
046: */
047: Converter select(Class type) throws IllegalStateException {
048: // Check the hashtable first.
049: Entry[] entries = iSelectEntries;
050: int length = entries.length;
051: int index = type == null ? 0 : type.hashCode() & (length - 1);
052:
053: Entry e;
054: // This loop depends on there being at least one null slot.
055: while ((e = entries[index]) != null) {
056: if (e.iType == type) {
057: return e.iConverter;
058: }
059: if (++index >= length) {
060: index = 0;
061: }
062: }
063:
064: // Not found in the hashtable, so do actual work.
065:
066: Converter converter = selectSlow(this , type);
067: e = new Entry(type, converter);
068:
069: // Save the entry for future selects. This class must be threadsafe,
070: // but there is no synchronization. Since the hashtable is being used
071: // as a cache, it is okay to destroy existing entries. This isn't
072: // likely to occur unless there is a high amount of concurrency. As
073: // time goes on, cache updates will occur less often, and the cache
074: // will fill with all the necessary entries.
075:
076: // Do all updates on a copy: slots in iSelectEntries must not be
077: // updated by multiple threads as this can allow all null slots to be
078: // consumed.
079: entries = (Entry[]) entries.clone();
080:
081: // Add new entry.
082: entries[index] = e;
083:
084: // Verify that at least one null slot exists!
085: for (int i = 0; i < length; i++) {
086: if (entries[i] == null) {
087: // Found a null slot, swap in new hashtable.
088: iSelectEntries = entries;
089: return converter;
090: }
091: }
092:
093: // Double capacity and re-hash.
094:
095: int newLength = length << 1;
096: Entry[] newEntries = new Entry[newLength];
097: for (int i = 0; i < length; i++) {
098: e = entries[i];
099: type = e.iType;
100: index = type == null ? 0 : type.hashCode()
101: & (newLength - 1);
102: while (newEntries[index] != null) {
103: if (++index >= newLength) {
104: index = 0;
105: }
106: }
107: newEntries[index] = e;
108: }
109:
110: // Swap in new hashtable.
111: iSelectEntries = newEntries;
112: return converter;
113: }
114:
115: /**
116: * Returns the amount of converters in the set.
117: */
118: int size() {
119: return iConverters.length;
120: }
121:
122: /**
123: * Copies all the converters in the set to the given array.
124: */
125: void copyInto(Converter[] converters) {
126: System.arraycopy(iConverters, 0, converters, 0,
127: iConverters.length);
128: }
129:
130: /**
131: * Returns a copy of this set, with the given converter added. If a
132: * matching converter is already in the set, the given converter replaces
133: * it. If the converter is exactly the same as one already in the set, the
134: * original set is returned.
135: *
136: * @param converter converter to add, must not be null
137: * @param removed if not null, element 0 is set to the removed converter
138: * @throws NullPointerException if converter is null
139: */
140: ConverterSet add(Converter converter, Converter[] removed) {
141: Converter[] converters = iConverters;
142: int length = converters.length;
143:
144: for (int i = 0; i < length; i++) {
145: Converter existing = converters[i];
146: if (converter.equals(existing)) {
147: // Already in the set.
148: if (removed != null) {
149: removed[0] = null;
150: }
151: return this ;
152: }
153:
154: if (converter.getSupportedType() == existing
155: .getSupportedType()) {
156: // Replace the converter.
157: Converter[] copy = new Converter[length];
158:
159: for (int j = 0; j < length; j++) {
160: if (j != i) {
161: copy[j] = converters[j];
162: } else {
163: copy[j] = converter;
164: }
165: }
166:
167: if (removed != null) {
168: removed[0] = existing;
169: }
170: return new ConverterSet(copy);
171: }
172: }
173:
174: // Not found, so add it.
175: Converter[] copy = new Converter[length + 1];
176: System.arraycopy(converters, 0, copy, 0, length);
177: copy[length] = converter;
178:
179: if (removed != null) {
180: removed[0] = null;
181: }
182: return new ConverterSet(copy);
183: }
184:
185: /**
186: * Returns a copy of this set, with the given converter removed. If the
187: * converter was not in the set, the original set is returned.
188: *
189: * @param converter converter to remove, must not be null
190: * @param removed if not null, element 0 is set to the removed converter
191: * @throws NullPointerException if converter is null
192: */
193: ConverterSet remove(Converter converter, Converter[] removed) {
194: Converter[] converters = iConverters;
195: int length = converters.length;
196:
197: for (int i = 0; i < length; i++) {
198: if (converter.equals(converters[i])) {
199: return remove(i, removed);
200: }
201: }
202:
203: // Not found.
204: if (removed != null) {
205: removed[0] = null;
206: }
207: return this ;
208: }
209:
210: /**
211: * Returns a copy of this set, with the converter at the given index
212: * removed.
213: *
214: * @param index index of converter to remove
215: * @param removed if not null, element 0 is set to the removed converter
216: * @throws IndexOutOfBoundsException if the index is invalid
217: */
218: ConverterSet remove(final int index, Converter[] removed) {
219: Converter[] converters = iConverters;
220: int length = converters.length;
221: if (index >= length) {
222: throw new IndexOutOfBoundsException();
223: }
224:
225: if (removed != null) {
226: removed[0] = converters[index];
227: }
228:
229: Converter[] copy = new Converter[length - 1];
230:
231: int j = 0;
232: for (int i = 0; i < length; i++) {
233: if (i != index) {
234: copy[j++] = converters[i];
235: }
236: }
237:
238: return new ConverterSet(copy);
239: }
240:
241: /**
242: * Returns the closest matching converter for the given type, but not very
243: * efficiently.
244: */
245: private static Converter selectSlow(ConverterSet set, Class type) {
246: Converter[] converters = set.iConverters;
247: int length = converters.length;
248: Converter converter;
249:
250: for (int i = length; --i >= 0;) {
251: converter = converters[i];
252: Class supportedType = converter.getSupportedType();
253:
254: if (supportedType == type) {
255: // Exact match.
256: return converter;
257: }
258:
259: if (supportedType == null
260: || (type != null && !supportedType
261: .isAssignableFrom(type))) {
262: // Eliminate the impossible.
263: set = set.remove(i, null);
264: converters = set.iConverters;
265: length = converters.length;
266: }
267: }
268:
269: // Haven't found exact match, so check what remains in the set.
270:
271: if (type == null || length == 0) {
272: return null;
273: }
274: if (length == 1) {
275: // Found the one best match.
276: return converters[0];
277: }
278:
279: // At this point, there exist multiple potential converters.
280:
281: // Eliminate supertypes.
282: for (int i = length; --i >= 0;) {
283: converter = converters[i];
284: Class supportedType = converter.getSupportedType();
285: for (int j = length; --j >= 0;) {
286: if (j != i
287: && converters[j].getSupportedType()
288: .isAssignableFrom(supportedType)) {
289: // Eliminate supertype.
290: set = set.remove(j, null);
291: converters = set.iConverters;
292: length = converters.length;
293: i = length - 1;
294: }
295: }
296: }
297:
298: // Check what remains in the set.
299:
300: if (length == 1) {
301: // Found the one best match.
302: return converters[0];
303: }
304:
305: // Class c implements a, b {}
306: // Converters exist only for a and b. Which is better? Neither.
307:
308: StringBuffer msg = new StringBuffer();
309: msg.append("Unable to find best converter for type \"");
310: msg.append(type.getName());
311: msg.append("\" from remaining set: ");
312: for (int i = 0; i < length; i++) {
313: converter = converters[i];
314: Class supportedType = converter.getSupportedType();
315:
316: msg.append(converter.getClass().getName());
317: msg.append('[');
318: msg.append(supportedType == null ? null : supportedType
319: .getName());
320: msg.append("], ");
321: }
322:
323: throw new IllegalStateException(msg.toString());
324: }
325:
326: static class Entry {
327: final Class iType;
328: final Converter iConverter;
329:
330: Entry(Class type, Converter converter) {
331: iType = type;
332: iConverter = converter;
333: }
334: }
335:
336: }
|