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