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.jdo;
012:
013: import com.versant.core.common.*;
014:
015: import java.lang.ref.ReferenceQueue;
016: import java.util.Set;
017: import java.util.Iterator;
018:
019: /**
020: * This is an implementation PM managed cache that uses a linked list to
021: * reference the colisions in the collection.
022: */
023: public final class LocalPMCache {
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: * Reference queue for cleared WeakKeys
049: */
050: public ReferenceQueue queue = new ReferenceQueue();
051: private VersantPersistenceManagerImp pm;
052: private final TransactionalList processList = new TransactionalList();
053: private boolean overWriteMode;
054:
055: private int currentRefType = VersantPersistenceManager.PM_CACHE_REF_TYPE_SOFT;
056:
057: /**
058: * Array of value table slots.
059: */
060: private PMCacheEntry[] m_keyTable;
061:
062: /**
063: * The number of key-value mappings contained in this identity hash map.
064: */
065: transient int size;
066:
067: private final int createdSize;
068:
069: public LocalPMCache() {
070: this .loadFactor = DEFAULT_LOAD_FACTOR;
071: threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
072: m_keyTable = new PMCacheEntry[DEFAULT_INITIAL_CAPACITY];
073: createdSize = DEFAULT_INITIAL_CAPACITY;
074: }
075:
076: public LocalPMCache(int initialCapacity) {
077: this (initialCapacity, DEFAULT_LOAD_FACTOR);
078: }
079:
080: public LocalPMCache(int initialCapacity, float loadFactor) {
081: if (initialCapacity < 0)
082: throw new IllegalArgumentException(
083: "Illegal initial capacity: " + initialCapacity);
084: if (initialCapacity > MAXIMUM_CAPACITY)
085: initialCapacity = MAXIMUM_CAPACITY;
086: if (loadFactor <= 0 || Float.isNaN(loadFactor))
087: throw new IllegalArgumentException("Illegal load factor: "
088: + loadFactor);
089:
090: // Find a power of 2 >= initialCapacity
091: int capacity = 1;
092: while (capacity < initialCapacity)
093: capacity <<= 1;
094:
095: this .loadFactor = loadFactor;
096: threshold = (int) (capacity * loadFactor);
097: m_keyTable = new PMCacheEntry[capacity];
098: createdSize = initialCapacity;
099: }
100:
101: public int getCurrentRefType() {
102: return currentRefType;
103: }
104:
105: public void setCurrentRefType(int currentRefType) {
106: checkRefType(currentRefType);
107: this .currentRefType = currentRefType;
108: }
109:
110: public static void checkRefType(int currentRefType) {
111: if (currentRefType != VersantPersistenceManager.PM_CACHE_REF_TYPE_WEAK
112: && currentRefType != VersantPersistenceManager.PM_CACHE_REF_TYPE_SOFT
113: && currentRefType != VersantPersistenceManager.PM_CACHE_REF_TYPE_STRONG) {
114: throw BindingSupportImpl
115: .getInstance()
116: .invalidOperation(
117: "The option '"
118: + currentRefType
119: + "' is not a valid choice for a PMCacheRefType.");
120: }
121: }
122:
123: public boolean isOverWriteMode() {
124: return overWriteMode;
125: }
126:
127: public void setOverWriteMode(boolean overWriteMode) {
128: this .overWriteMode = overWriteMode;
129: }
130:
131: public void setPm(VersantPersistenceManagerImp pm) {
132: this .pm = pm;
133: }
134:
135: /**
136: * Add a newly created sm to the managed cache.
137: */
138: public PCStateMan add(PCStateMan sm) {
139: //this will create a realOID if needed
140: sm.getRealOIDIfAppId();
141: addSm(sm.oid.getAvailableOID(), sm);
142: addForProcessing(sm);
143: if (sm.isTx())
144: pm.addTxStateObject(sm);
145: return sm;
146: }
147:
148: public PCStateMan add(OID oid, State state, PCStateMan[] sms) {
149: return addState(oid, state, true, sms);
150: }
151:
152: /**
153: * Provide the oid-state pair to local cache. This will not result in a PCStateman
154: * being created.
155: */
156: public void addStateOnly(OID oid, State state) {
157: addState(oid, state, false, null);
158: }
159:
160: /**
161: * This must create a CacheEntryBase for the sm.
162: */
163: public PMCacheEntry createCacheKey(PCStateMan sm) {
164: if (sm.cacheEntry != null) {
165: throw BindingSupportImpl.getInstance().internal(
166: "StateManager already has a PMCacheEntry");
167: }
168: return sm.cacheEntry = new PMCacheEntry(currentRefType, sm,
169: queue);
170: }
171:
172: /**
173: * This must create a CacheEntryBase for the sm.
174: */
175: public PMCacheEntry createCacheKey(OID oid, State state) {
176: return new PMCacheEntry(currentRefType, oid, state, queue);
177: }
178:
179: /**
180: * Add to the head of the processList.
181: */
182: public PCStateMan addForProcessing(PCStateMan sm) {
183: if (!pm.isActive())
184: return sm;
185: processList.add(sm);
186: return sm;
187: }
188:
189: PCStateMan updateSm(State value, PCStateMan sm, OID key) {
190: if (value == NULLState.NULL_STATE) {
191: /**
192: * Must throw exception as the instance was deleted from under us
193: */
194: throw BindingSupportImpl.getInstance().objectNotFound(
195: "No row for " + sm.getClassMetaData().storeClass
196: + " " + key.toSString());
197: }
198:
199: if (sm != null) {
200: sm.updateWith(value, pm, overWriteMode);
201: addForProcessing(sm);
202: }
203: return sm;
204: }
205:
206: /**
207: * Process the ReferenceQueue holding keys for GCed values.
208: */
209: public void processReferenceQueue() {
210: processReferenceQueueImp();
211: }
212:
213: /**
214: * Remove all invalidated entries from the map, that is, remove all entries
215: * whose keys have been discarded. This method should be invoked once by
216: * each public mutator in this class. We don't invoke this method in
217: * public accessors because that can lead to surprising
218: * ConcurrentModificationExceptions.
219: */
220: private void processReferenceQueueImp() {
221: PMCacheEntryOwnerRef ref;
222: while ((ref = (PMCacheEntryOwnerRef) queue.poll()) != null) {
223: PMCacheEntry ce = ref.getOwner();
224: if (!ce.hasReference(ref))
225: // the ref of the PMCacheEntry might have changed,
226: // due to PMCacheEntry.upgradeToSm(). In this case,
227: // we must not remove the entry.
228:
229: continue;
230: removeImp(ce, m_keyTable, indexFor(ce.mappedOID.hashCode(),
231: m_keyTable.length));
232: }
233: }
234:
235: public void doCommit(boolean retainValues) {
236: processReferenceQueueImp();
237: //only do processList
238: Iterator iter = processList.iterator();
239: while (iter.hasNext()) {
240: PMCacheEntry ce = (PMCacheEntry) iter.next();
241: PCStateMan sm = (PCStateMan) ce.get();
242: if (sm != null) {
243: sm.commit(pm);
244: }
245: }
246: processList.clear();
247: }
248:
249: public void doRollback(boolean retainValues) {
250: processReferenceQueueImp();
251: Iterator iter = processList.iterator();
252: while (iter.hasNext()) {
253: PMCacheEntry ce = (PMCacheEntry) iter.next();
254: PCStateMan sm = (PCStateMan) ce.get();
255: if (sm != null) {
256: sm.rollback();
257: }
258: }
259: processList.clear();
260: }
261:
262: public void doRefresh(boolean strict) {
263: Iterator iter = processList.iterator();
264: while (iter.hasNext()) {
265: PMCacheEntry ce = (PMCacheEntry) iter.next();
266: PCStateMan sm = (PCStateMan) ce.get();
267: if (sm != null) {
268: sm.refresh();
269: }
270: }
271: }
272:
273: /**
274: * This add the real oid of the NewOID to the mapping.
275: */
276: public void addRealOID(PCStateMan sm) {
277: reMapWithRealOID(sm);
278: }
279:
280: private void reMapWithRealOID(PCStateMan sm) {
281: if (Debug.DEBUG) {
282: validate();
283: if (!sm.oid.isNew()) {
284: throw BindingSupportImpl.getInstance().internal(
285: "The instance is not new");
286: }
287: if (sm.cacheEntry.mappedOID != sm.oid) {
288: throw BindingSupportImpl.getInstance().internal(
289: "The instance is not mapped with its newOID");
290: }
291: if (sm.oid.getRealOID() == null) {
292: throw BindingSupportImpl.getInstance().internal(
293: "The realOID may not be null: " + sm.oid);
294: }
295: }
296:
297: if (sm.cacheEntry.mappedOID == sm.oid.getRealOID())
298: return;
299: final int currentIndex = indexFor(sm.cacheEntry.hash,
300: m_keyTable.length);
301: final int newIndex = indexFor(sm.oid.getRealOID().hashCode(),
302: m_keyTable.length);
303:
304: if (currentIndex == newIndex) {
305: OID realOID = sm.oid.getRealOID();
306: sm.cacheEntry.reHash(realOID);
307: realOID.resolve(sm.state);
308: return;
309: }
310: //remove from current pos
311: if (sm.cacheEntry.prev == null) {
312: m_keyTable[currentIndex] = sm.cacheEntry.next;
313: }
314: sm.cacheEntry.unlinkNextList();
315:
316: OID realOID = sm.oid.getRealOID();
317: sm.cacheEntry.reHash(realOID);
318: realOID.resolve(sm.state);
319:
320: sm.cacheEntry.setNext(m_keyTable[newIndex]);
321: m_keyTable[newIndex] = sm.cacheEntry;
322: }
323:
324: public void checkModelConsistency() {
325: processReferenceQueueImp();
326: PMCacheEntry[] src = m_keyTable;
327: for (int j = 0; j < src.length; j++) {
328: PMCacheEntry e = src[j];
329: if (e != null) {
330: Object val = e.get();
331: if (val != null && (val instanceof PCStateMan)) {
332: ((PCStateMan) val).checkModelConsistency();
333: }
334: e = e.next;
335: }
336: }
337: }
338:
339: /**
340: * If the instance for this oid is already managed then it will be updated
341: * with the state information.
342: * Else the instance will be managed with this state.
343: */
344: protected PCStateMan addState(OID key, State value, boolean manage,
345: PCStateMan[] addSm) {
346: if (Debug.DEBUG)
347: validate();
348: final PMCacheEntry[] m_keyTable = this .m_keyTable;
349: final int hash = key.hashCode();
350: final int i = indexFor(hash, m_keyTable.length);
351:
352: for (PMCacheEntry e = m_keyTable[i]; e != null; e = e.next) {
353: if (e.hashCode() == hash && eq(key, e.mappedOID)) {
354: Object o = e.get();
355: if (o == null) {
356: removeImp(e, m_keyTable, i);
357: break;
358: }
359: if (o instanceof PCStateMan) {
360: return updateSm(value, (PCStateMan) o, key);
361: } else {
362: State currentState = (State) o;
363: if (value == NULLState.NULL_STATE) {
364: removeImp(e, m_keyTable, i);
365: return null;
366: } else {
367: if (overWriteMode) {
368: currentState.clear();
369: }
370: if (currentState != null) {
371: value.updateNonFilled(currentState);
372: if (manage) {
373: return e.upgradeToSm(addSm[0] = pm
374: .reManage(key, value), queue);
375: } else {
376: currentState.updateNonFilled(value);
377: return null;
378: }
379: }
380: }
381: }
382: }
383: }
384: if (Debug.DEBUG)
385: validate();
386: if (value == NULLState.NULL_STATE) {
387: //ignore
388: return null;
389: }
390: //add new entry
391: PMCacheEntry ce;
392: PCStateMan sm = null;
393: if (manage) {
394: //create sm and add
395: ce = createCacheKey(sm = addSm[0] = pm.reManage(key, value));
396: } else {
397: //just add the oid-state pair
398: ce = createCacheKey(key, value);
399: }
400: ce.setNext(m_keyTable[i]);
401: m_keyTable[i] = ce;
402: if (size++ >= threshold)
403: resize(2 * m_keyTable.length);
404: if (Debug.DEBUG)
405: validate();
406: return sm;
407: }
408:
409: /**
410: * Remove the entry. Note that this is a NOP if it is not in the cache.
411: */
412: private void removeImp(PMCacheEntry e,
413: final PMCacheEntry[] m_keyTable, final int i) {
414: if (Debug.DEBUG)
415: validate();
416: if (m_keyTable[i] == null)
417: return;
418: if (m_keyTable[i] == e) {
419: m_keyTable[i] = e.next;
420: clearCE(e);
421: } else {
422: for (PMCacheEntry ce = m_keyTable[i].next; ce != null; ce = ce.next) {
423: if (ce == e) {
424: clearCE(e);
425: break;
426: }
427: }
428:
429: }
430: if (Debug.DEBUG)
431: validate();
432: }
433:
434: private void clearCE(PMCacheEntry e) {
435: e.unlinkNextList();
436: e.clear();
437: size--;
438: }
439:
440: /**
441: * This method does not replace the {@link PCStateMan} if the {@link OID} is present.
442: * If the mapping exist it will be verified.
443: * If the mapping does not exist it will be created.
444: */
445: public PCStateMan addSm(OID key, PCStateMan value) {
446: key = key.getAvailableOID();
447: final PMCacheEntry[] m_keyTable = this .m_keyTable;
448: final int hash = key.hashCode();
449: final int i = indexFor(hash, m_keyTable.length);
450:
451: for (PMCacheEntry e = m_keyTable[i]; e != null; e = e.next) {
452: if (e.hash == hash && eq(key, e.mappedOID)) {
453: Object o = e.get();
454: if (o != null) {
455: if (o != null && o != value) {
456: throw BindingSupportImpl.getInstance()
457: .internal(
458: "Inconsistent mapping for id '"
459: + key.toPkString()
460: + "'");
461: }
462: return value;
463: }
464: remove(e);
465: break;
466: }
467: }
468: //add new entry
469: PMCacheEntry ce = value.cacheEntry;
470: if (ce == null) {
471: ce = createCacheKey(value);
472: }
473:
474: ce.setNext(m_keyTable[i]);
475: m_keyTable[i] = ce;
476: if (size++ >= threshold)
477: resize(2 * m_keyTable.length);
478:
479: if (Debug.DEBUG)
480: validate();
481: return value;
482: }
483:
484: public void setInterceptDfgFieldAccess(boolean on) {
485: processReferenceQueueImp();
486:
487: PMCacheEntry[] src = m_keyTable;
488: for (int j = 0; j < src.length; j++) {
489: PMCacheEntry e = src[j];
490: while (e != null) {
491: Object o = e.get();
492: if (o != null && (o instanceof PCStateMan)) {
493: ((PCStateMan) o).setInterceptDfgFieldAccess(on);
494: }
495: e = e.next;
496: }
497: }
498: }
499:
500: public void evict() {
501: PMCacheEntry[] src = m_keyTable;
502: for (int j = 0; j < src.length; j++) {
503: PMCacheEntry e = src[j];
504: while (e != null) {
505: Object o = e.get();
506: if (o != null && (o instanceof PCStateMan)) {
507: ((PCStateMan) o).evict();
508: }
509: e = e.next;
510: }
511: }
512: processReferenceQueueImp();
513: }
514:
515: /**
516: * Return the state if present. This will not result in the PCStateMan being
517: * created if not currently managed.
518: */
519: public State getStateByOID(OID oid) {
520: Object value = getValueByOid(oid);
521: if (value == null)
522: return null;
523: if (value instanceof PCStateMan) {
524: return ((PCStateMan) value).state;
525: } else {
526: return (State) value;
527: }
528: }
529:
530: /**
531: * Do we have a State or PCStateMan for the oid? Note the data may be
532: * evicted at any time depending on the reference type.
533: */
534: public boolean contains(OID oid) {
535: return (getValueByOid(oid) != null);
536: }
537:
538: /**
539: * If the sm is already managed then return it. If the oid and state is present
540: * then manage it and return it. Else return null.
541: */
542: public PCStateMan getByOID(OID oid, boolean manage) {
543: PMCacheEntry ce = getByOID(oid.getAvailableOID());
544: if (ce == null)
545: return null;
546: Object value = ce.get();
547: if (value == null) {
548: remove(ce);
549: return null;
550: }
551: if (value instanceof PCStateMan) {
552: return (PCStateMan) value;
553: }
554: if (!manage)
555: return null;
556: return ce.upgradeToSm(pm.reManage(oid, (State) value), queue);
557: }
558:
559: /**
560: * If the sm is already managed then return it. If the oid and state is present
561: * then manage it and return it. Else return null. This looks up using the
562: * oid as is and does not assume that realOID has been set.
563: */
564: public PCStateMan getByNewObjectOID(NewObjectOID oid) {
565: PMCacheEntry ce = getByOID(oid);
566: if (ce == null)
567: return null;
568: Object value = ce.get();
569: if (value == null) {
570: remove(ce);
571: return null;
572: }
573: if (value instanceof PCStateMan) {
574: return (PCStateMan) value;
575: }
576: return ce.upgradeToSm(pm.reManage(oid, (State) value), queue);
577: }
578:
579: private Object getValueByOid(OID oid) {
580: PMCacheEntry ce = getByOID(oid.getAvailableOID());
581: if (ce == null)
582: return null;
583: Object value = ce.get();
584: if (value == null) {
585: remove(ce);
586: return null;
587: }
588: return value;
589: }
590:
591: private PMCacheEntry getByOID(OID oid) {
592: final int hash = oid.hashCode();
593: for (PMCacheEntry e = m_keyTable[indexFor(hash,
594: m_keyTable.length)]; e != null; e = e.next) {
595: if (e.hash == hash && eq(oid, e.mappedOID)) {
596: return e;
597: }
598: }
599: return null;
600: }
601:
602: public void clear() {
603: PMCacheEntry[] src = m_keyTable;
604: for (int j = 0; j < src.length; j++) {
605: PMCacheEntry e = src[j];
606: PMCacheEntry next;
607: while (e != null) {
608: next = e.next;
609: e.reset();
610: e.next = null;
611: e.prev = null;
612: e = next;
613: }
614: }
615: processList.clear();
616: size = 0;
617: m_keyTable = new PMCacheEntry[createdSize];
618: }
619:
620: public boolean inProcessList(PCStateMan sm) {
621: return processList.contains(sm.cacheEntry);
622: }
623:
624: public void remove(PCStateMan sm) {
625: remove(sm.cacheEntry);
626: }
627:
628: /**
629: * Remove entry from collection. This must also ensure that the entry
630: * is removed from the processList.
631: */
632: private void remove(PMCacheEntry ce) {
633: if (Debug.DEBUG)
634: validate();
635: int hash = ce.mappedOID.hashCode();
636: int i = indexFor(hash, m_keyTable.length);
637: PMCacheEntry e = m_keyTable[i];
638: for (; e != null; e = e.next) {
639: if (e.hash == hash && eq(ce.mappedOID, e.mappedOID)) {
640: removeImp(e, m_keyTable, i);
641: }
642: }
643: if (Debug.DEBUG)
644: validate();
645: }
646:
647: /**
648: * This will validate the consistency of the cache. Only for debugging
649: */
650: private Set[] validate() {
651: int count = 0;
652: // ObjectHashSet[] sets = {new ObjectHashSet(size, ObjectHashSet.IDENTITY_COMP), new ObjectHashSet(size, ObjectHashSet.IDENTITY_COMP)};
653: PMCacheEntry[] src = m_keyTable;
654: for (int j = 0; j < src.length; j++) {
655: PMCacheEntry e = src[j];
656: while (e != null) {
657: int index = indexFor(e.mappedOID.hashCode(),
658: m_keyTable.length);
659: if (index != j) {
660: throw BindingSupportImpl.getInstance().internal(
661: "The entry is not at the correct pos");
662: }
663: // Object val = e.get();
664: // if (!sets[0].add(e)) {
665: // throw BindingSupportImpl.getInstance().internal("The entry "
666: // + e + " is more than once in the cache");
667: // }
668: // if (val != null) {
669: // if (!sets[1].add(val)) {
670: // throw BindingSupportImpl.getInstance().internal("The value " + val + " is in the cache more than once");
671: // }
672: // }
673: count++;
674: e = e.next;
675: }
676: }
677:
678: if (count != size) {
679: throw BindingSupportImpl.getInstance().internal(
680: "The counted size == " + count + " but size is "
681: + size);
682: }
683: // return sets;
684: return null;
685: }
686:
687: public void dump() {
688: System.out.println("\n\n\nLocalPMCache.dump: START");
689: PMCacheEntry[] src = m_keyTable;
690: for (int j = 0; j < src.length; j++) {
691: PMCacheEntry e = src[j];
692: boolean first = true;
693: while (e != null) {
694: if (first) {
695: System.out.println("j = " + j);
696: first = false;
697: }
698: System.out.println("e = " + e);
699: e = e.next;
700: }
701: }
702: System.out.println("LocalPMCache.dump: END \n\n\n");
703: }
704:
705: private void resize(int newCapacity) {
706: if (Debug.DEBUG)
707: validate();
708: PMCacheEntry[] oldTable = m_keyTable;
709: int oldCapacity = oldTable.length;
710: if (oldCapacity == MAXIMUM_CAPACITY) {
711: threshold = Integer.MAX_VALUE;
712: return;
713: }
714:
715: PMCacheEntry[] newTable = new PMCacheEntry[newCapacity];
716: transfer(newTable);
717: m_keyTable = newTable;
718: threshold = (int) (newCapacity * loadFactor);
719: if (Debug.DEBUG)
720: validate();
721: }
722:
723: /**
724: * Transfer all entries from current table to newTable.
725: */
726: private void transfer(PMCacheEntry[] newTable) {
727: PMCacheEntry[] src = m_keyTable;
728: int newCapacity = newTable.length;
729: size = 0;
730: for (int j = 0; j < src.length; j++) {
731: PMCacheEntry e = src[j];
732: if (e != null) {
733: //skip entries with gc'd refs
734: for (;;) {
735: if (e == null)
736: break;
737: if (e.get() == null) {
738: e.clear();
739: e = e.next;
740: } else {
741: break;
742: }
743: }
744: if (e == null)
745: continue;
746: src[j] = null;
747:
748: do {
749: size++;
750: PMCacheEntry next = e.next;
751: int i = indexFor(e.hash, newCapacity);
752: e.unlinkNextList();
753: e.setNext(newTable[i]);
754: newTable[i] = e;
755: e = next;
756: } while (e != null);
757: }
758: }
759: }
760:
761: /**
762: * Check for equality of non-null reference x and possibly-null y.
763: */
764: static boolean eq(OID x, OID y) {
765: return x == y || x.equals(y);
766: }
767:
768: /**
769: * Returns index for hash code h.
770: */
771: static int indexFor(int h, int length) {
772: return h & (length - 1);
773: }
774:
775: /**
776: * How many keys are in the cache?
777: */
778: public int size() {
779: return size;
780: }
781:
782: }
|