001: /*
002: * Copyright (c) 1998 - 2005 Versant Corporation
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * Versant Corporation - initial API and implementation
010: */
011: package com.versant.core.ejb.common;
012:
013: import com.versant.core.common.BindingSupportImpl;
014:
015: import java.util.Iterator;
016: import java.util.ConcurrentModificationException;
017: import java.util.NoSuchElementException;
018:
019: /**
020: * This is a Hashed based collection that contain Entry elements.
021: * Equality is key based.
022: */
023: public class EntrySet {
024: /**
025: * The default initial capacity - MUST be a power of two.
026: */
027: static final int DEFAULT_INITIAL_CAPACITY = 16;
028: /**
029: * The load factor used when none specified in constructor.
030: **/
031: static final float DEFAULT_LOAD_FACTOR = 0.75f;
032: /**
033: * The load factor for the hash table.
034: */
035: final float loadFactor;
036: /**
037: * The next size value at which to resize (capacity * load factor).
038: */
039: int threshold;
040: /**
041: * The maximum capacity, used if a higher value is implicitly specified
042: * by either of the constructors with arguments.
043: * MUST be a power of two <= 1<<30.
044: */
045: static final int MAXIMUM_CAPACITY = 1 << 30;
046:
047: /**
048: * Array of value table slots.
049: */
050: private Entry[] m_keyTable;
051:
052: /**
053: * The number of key-value mappings contained in this identity hash map.
054: */
055: transient int size;
056: private int modCount;
057:
058: public EntrySet() {
059: this .loadFactor = DEFAULT_LOAD_FACTOR;
060: threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
061: m_keyTable = new Entry[DEFAULT_INITIAL_CAPACITY];
062: }
063:
064: public EntrySet(int initialCapacity) {
065: this (initialCapacity, DEFAULT_LOAD_FACTOR);
066: }
067:
068: public EntrySet(int initialCapacity, float loadFactor) {
069: if (initialCapacity < 0)
070: throw new IllegalArgumentException(
071: "Illegal initial capacity: " + initialCapacity);
072: if (initialCapacity > MAXIMUM_CAPACITY)
073: initialCapacity = MAXIMUM_CAPACITY;
074: if (loadFactor <= 0 || Float.isNaN(loadFactor))
075: throw new IllegalArgumentException("Illegal load factor: "
076: + loadFactor);
077:
078: // Find a power of 2 >= initialCapacity
079: int capacity = 1;
080: while (capacity < initialCapacity)
081: capacity <<= 1;
082:
083: this .loadFactor = loadFactor;
084: threshold = (int) (capacity * loadFactor);
085: m_keyTable = new Entry[capacity];
086: }
087:
088: /**
089: * Add this entry to the set.
090: * @param ne
091: */
092: public Entry addEntry(Entry ne) {
093: int i = indexFor(ne.hash, m_keyTable.length);
094:
095: for (Entry e = m_keyTable[i]; e != null; e = e.next) {
096: if (e.hash == ne.hash && eq(ne.key, e.key)) {
097: //same instance
098: if (ne == e)
099: return null;
100: else
101: throw new IllegalArgumentException(
102: "Entry with equal key is already in the set");
103:
104: }
105: }
106: modCount++;
107: addEntry(ne, i);
108: return ne;
109: }
110:
111: public boolean add(Object o) {
112: if (!contains(o)) {
113: addEntry(createEntry(o));
114: return true;
115: }
116: return false;
117: }
118:
119: /**
120: * If the instance is present then return the entry, else add it and return the
121: * new entry.
122: * @param o
123: * @return
124: */
125: public Entry addAndReturnEntry(Object o) {
126: Entry e = get(o);
127: if (e == null) {
128: return addEntry(createEntry(o));
129: }
130: return e;
131: }
132:
133: public Entry createEntry(Object key) {
134: return new Entry(key);
135: }
136:
137: private void addEntry(Entry e, int index) {
138: e.next = m_keyTable[index];
139: m_keyTable[index] = e;
140:
141: if (size++ >= threshold) {
142: resize(2 * m_keyTable.length);
143: }
144: }
145:
146: public boolean contains(Object key) {
147: return (get(key) != null);
148: }
149:
150: public Entry get(Object key) {
151: final int hash = key.hashCode();
152: for (Entry e = m_keyTable[indexFor(hash, m_keyTable.length)]; e != null; e = e.next) {
153: if (e.hash == hash && eq(key, e.key)) {
154: return e;
155: }
156: }
157: return null;
158: }
159:
160: public Iterator iterator() {
161: return new EntryIterator();
162: }
163:
164: // Subclass overrides these to alter behavior of views' iterator() method
165: public Iterator newKeyIterator() {
166: return new KeyIterator();
167: }
168:
169: public Iterator newEntryIterator() {
170: return new EntryIterator();
171: }
172:
173: void resize(int newCapacity) {
174: Entry[] oldTable = m_keyTable;
175: int oldCapacity = oldTable.length;
176: if (oldCapacity == MAXIMUM_CAPACITY) {
177: threshold = Integer.MAX_VALUE;
178: return;
179: }
180:
181: Entry[] newTable = new Entry[newCapacity];
182: transfer(newTable);
183: m_keyTable = newTable;
184: threshold = (int) (newCapacity * loadFactor);
185: }
186:
187: /**
188: * Transfer all entries from current table to newTable.
189: */
190: void transfer(Entry[] newTable) {
191: Entry[] src = m_keyTable;
192: int newCapacity = newTable.length;
193: for (int j = 0; j < src.length; j++) {
194: Entry e = src[j];
195: if (e != null) {
196: src[j] = null;
197: do {
198: Entry next = e.next;
199: int i = indexFor(e.hash, newCapacity);
200: e.next = newTable[i];
201: newTable[i] = e;
202: e = next;
203: } while (e != null);
204: }
205: }
206: }
207:
208: /**
209: * Check for equality of non-null reference x and possibly-null y.
210: */
211: static boolean eq(Object x, Object y) {
212: return x == y || x.equals(y);
213: }
214:
215: /**
216: * Returns index for hash code h.
217: */
218: static int indexFor(int h, int length) {
219: return h & (length - 1);
220: }
221:
222: /**
223: * How many keys are in the cache?
224: */
225: public int size() {
226: return size;
227: }
228:
229: /**
230: * Removes all mappings from this map.
231: */
232: public void clear() {
233: modCount++;
234: Entry[] tab = m_keyTable;
235: for (int i = 0; i < tab.length; i++) {
236: tab[i] = null;
237: }
238: size = 0;
239: }
240:
241: public static class Entry {
242: final Object key;
243: private final int hash;
244: private Entry next;
245:
246: public Entry(Object key) {
247: this .key = key;
248: this .hash = key.hashCode();
249: }
250:
251: public Object getKey() {
252: return key;
253: }
254:
255: public boolean equals(Object o) {
256: if (!(o instanceof Entry)) {
257: return false;
258: }
259:
260: Entry e = (Entry) o;
261: Object k1 = getKey();
262: Object k2 = e.getKey();
263: if (k1 == k2 || k1.equals(k2)) {
264: return true;
265: }
266: return false;
267: }
268:
269: public int hashCode() {
270: return hash;
271: }
272: }
273:
274: class Iter implements Iterator {
275: /**
276: * The amount that we have iterated over.
277: */
278: private int iterCount;
279:
280: private Entry lastEntry;
281: private int currentIndex;
282:
283: public Iter() {
284: }
285:
286: public void remove() {
287: throw BindingSupportImpl.getInstance().invalidOperation(
288: "Remove not allowed");
289: }
290:
291: public boolean hasNext() {
292: return (iterCount < size);
293: }
294:
295: private Entry getFirstHeadFrom(int index) {
296: for (int i = index; i < size; i++) {
297: if (m_keyTable[i] != null) {
298: return m_keyTable[i];
299: }
300: }
301: return null;
302: }
303:
304: public Object next() {
305: if (hasNext()) {
306: if (lastEntry != null) {
307: lastEntry = lastEntry.next;
308: if (lastEntry == null) {
309: lastEntry = getFirstHeadFrom(currentIndex++);
310: }
311: } else {
312: lastEntry = getFirstHeadFrom(currentIndex++);
313: }
314: if (lastEntry == null) {
315: throw BindingSupportImpl.getInstance()
316: .noSuchElement("");
317: }
318: iterCount++;
319: return lastEntry;
320: } else {
321: throw BindingSupportImpl.getInstance()
322: .noSuchElement("");
323: }
324: }
325: }
326:
327: private abstract class HashIterator implements Iterator {
328: Entry next; // next entry to return
329: int expectedModCount; // For fast-fail
330: int index; // current slot
331: Entry current; // current entry
332:
333: HashIterator() {
334: expectedModCount = modCount;
335: Entry[] t = m_keyTable;
336: int i = t.length;
337: Entry n = null;
338: if (size != 0) { // advance to first entry
339: while (i > 0 && (n = t[--i]) == null)
340: ;
341: }
342: next = n;
343: index = i;
344: }
345:
346: public boolean hasNext() {
347: return next != null;
348: }
349:
350: Entry nextEntry() {
351: if (modCount != expectedModCount)
352: throw new ConcurrentModificationException();
353: Entry e = next;
354: if (e == null)
355: throw new NoSuchElementException();
356:
357: Entry n = e.next;
358: Entry[] t = m_keyTable;
359: int i = index;
360: while (n == null && i > 0) {
361: n = t[--i];
362: }
363: index = i;
364: next = n;
365: return current = e;
366: }
367:
368: public void remove() {
369: }
370: }
371:
372: private class EntryIterator extends HashIterator {
373: public Object next() {
374: return nextEntry();
375: }
376: }
377:
378: private class KeyIterator extends HashIterator {
379: public Object next() {
380: return nextEntry().getKey();
381: }
382: }
383:
384: }
|