From dc708480b286decd4328d52d742cac000faca3f8 Mon Sep 17 00:00:00 2001
From: "Brian S. O'Neill" <bronee@gmail.com>
Date: Sun, 4 May 2008 17:36:39 +0000
Subject: Merged map repository implementation from map branch.
---
.../java/com/amazon/carbonado/repo/map/Key.java | 273 +++++
.../com/amazon/carbonado/repo/map/MapCursor.java | 173 +++
.../amazon/carbonado/repo/map/MapRepository.java | 125 +++
.../carbonado/repo/map/MapRepositoryBuilder.java | 151 +++
.../com/amazon/carbonado/repo/map/MapStorage.java | 813 ++++++++++++++
.../amazon/carbonado/repo/map/MapTransaction.java | 240 ++++
.../carbonado/repo/map/MapTransactionManager.java | 98 ++
.../amazon/carbonado/repo/map/UpgradableLock.java | 1161 ++++++++++++++++++++
.../amazon/carbonado/repo/map/package-info.java | 24 +
9 files changed, 3058 insertions(+)
create mode 100644 src/main/java/com/amazon/carbonado/repo/map/Key.java
create mode 100644 src/main/java/com/amazon/carbonado/repo/map/MapCursor.java
create mode 100644 src/main/java/com/amazon/carbonado/repo/map/MapRepository.java
create mode 100644 src/main/java/com/amazon/carbonado/repo/map/MapRepositoryBuilder.java
create mode 100644 src/main/java/com/amazon/carbonado/repo/map/MapStorage.java
create mode 100644 src/main/java/com/amazon/carbonado/repo/map/MapTransaction.java
create mode 100644 src/main/java/com/amazon/carbonado/repo/map/MapTransactionManager.java
create mode 100644 src/main/java/com/amazon/carbonado/repo/map/UpgradableLock.java
create mode 100644 src/main/java/com/amazon/carbonado/repo/map/package-info.java
(limited to 'src/main')
diff --git a/src/main/java/com/amazon/carbonado/repo/map/Key.java b/src/main/java/com/amazon/carbonado/repo/map/Key.java
new file mode 100644
index 0000000..5032f66
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/map/Key.java
@@ -0,0 +1,273 @@
+/*
+ * Copyright 2008 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.repo.map;
+
+import java.lang.reflect.UndeclaredThrowableException;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.List;
+import java.util.Map;
+
+import org.cojen.classfile.ClassFile;
+import org.cojen.classfile.CodeBuilder;
+import org.cojen.classfile.Label;
+import org.cojen.classfile.LocalVariable;
+import org.cojen.classfile.MethodInfo;
+import org.cojen.classfile.Modifiers;
+import org.cojen.classfile.TypeDesc;
+
+import org.cojen.util.ClassInjector;
+import org.cojen.util.SoftValuedHashMap;
+
+import com.amazon.carbonado.Storable;
+
+import com.amazon.carbonado.info.OrderedProperty;
+import com.amazon.carbonado.info.StorableInfo;
+import com.amazon.carbonado.info.StorableIntrospector;
+import com.amazon.carbonado.info.StorableProperty;
+
+import com.amazon.carbonado.gen.CodeBuilderUtil;
+
+/**
+ *
+ *
+ * @author Brian S O'Neill
+ */
+class Key<S extends Storable> implements Comparable<Key<S>> {
+ protected final S mStorable;
+ protected final Comparator<S> mComparator;
+
+ Key(S storable, Comparator<S> comparator) {
+ mStorable = storable;
+ mComparator = comparator;
+ }
+
+ @Override
+ public String toString() {
+ return mStorable.toString();
+ }
+
+ public int compareTo(Key<S> other) {
+ int result = mComparator.compare(mStorable, other.mStorable);
+ if (result == 0) {
+ int t1 = tieBreaker();
+ int t2 = other.tieBreaker();
+ if (t1 < t2) {
+ result = -1;
+ } else if (t1 > t2) {
+ result = 1;
+ }
+ }
+ return result;
+ }
+
+ protected int tieBreaker() {
+ return 0;
+ }
+
+ public static interface Assigner<S extends Storable> {
+ void setKeyValues(S storable, Object[] identityValues);
+
+ void setKeyValues(S storable, Object[] identityValues, Object rangeValue);
+ }
+
+ private static final Map<Class, Assigner> mAssigners;
+
+ static {
+ mAssigners = new SoftValuedHashMap();
+ }
+
+ public static synchronized <S extends Storable> Assigner<S> getAssigner(Class<S> clazz) {
+ Assigner<S> assigner = mAssigners.get(clazz);
+ if (assigner == null) {
+ assigner = createAssigner(clazz);
+ mAssigners.put(clazz, assigner);
+ }
+ return assigner;
+ }
+
+ private static <S extends Storable> Assigner<S> createAssigner(Class<S> clazz) {
+ final StorableInfo<S> info = StorableIntrospector.examine(clazz);
+
+ ClassInjector ci = ClassInjector.create(clazz.getName(), clazz.getClassLoader());
+ ClassFile cf = new ClassFile(ci.getClassName());
+ cf.addInterface(Assigner.class);
+ cf.markSynthetic();
+ cf.setSourceFile(Key.class.getName());
+ cf.setTarget("1.5");
+
+ cf.addDefaultConstructor();
+
+ // Define required setKeyValues methods.
+
+ List<OrderedProperty<S>> pk =
+ new ArrayList<OrderedProperty<S>>(info.getPrimaryKey().getProperties());
+
+ TypeDesc storableType = TypeDesc.forClass(Storable.class);
+ TypeDesc storableArrayType = storableType.toArrayType();
+ TypeDesc userStorableType = TypeDesc.forClass(info.getStorableType());
+ TypeDesc objectArrayType = TypeDesc.OBJECT.toArrayType();
+
+ MethodInfo mi = cf.addMethod(Modifiers.PUBLIC, "setKeyValues", null,
+ new TypeDesc[] {storableType, objectArrayType});
+
+ CodeBuilder b = new CodeBuilder(mi);
+
+ LocalVariable userStorableVar = b.createLocalVariable(null, userStorableType);
+ b.loadLocal(b.getParameter(0));
+ b.checkCast(userStorableType);
+ b.storeLocal(userStorableVar);
+
+ // Switch on the number of values supplied.
+
+ /* Switch looks like this for two pk properties:
+
+ switch(identityValues.length) {
+ default:
+ throw new IllegalArgumentException();
+ case 2:
+ storable.setPkProp2(identityValues[1]);
+ case 1:
+ storable.setPkProp1(identityValues[0]);
+ case 0:
+ }
+
+ */
+
+ b.loadLocal(b.getParameter(1));
+ b.arrayLength();
+
+ int[] cases = new int[pk.size() + 1];
+ Label[] labels = new Label[pk.size() + 1];
+
+ for (int i=0; i<labels.length; i++) {
+ cases[i] = pk.size() - i;
+ labels[i] = b.createLabel();
+ }
+
+ Label defaultLabel = b.createLabel();
+
+ b.switchBranch(cases, labels, defaultLabel);
+
+ for (int i=0; i<labels.length; i++) {
+ labels[i].setLocation();
+ int prop = cases[i] - 1;
+ if (prop >= 0) {
+ b.loadLocal(userStorableVar);
+ b.loadLocal(b.getParameter(1));
+ b.loadConstant(prop);
+ b.loadFromArray(storableArrayType);
+ callSetPropertyValue(b, pk.get(prop));
+ }
+ // Fall through to next case.
+ }
+
+ b.returnVoid();
+
+ defaultLabel.setLocation();
+ CodeBuilderUtil.throwException(b, IllegalArgumentException.class, null);
+
+ // The setKeyValues method that takes a range value calls the other
+ // setKeyValues method first, to take care of the identityValues.
+
+ mi = cf.addMethod(Modifiers.PUBLIC, "setKeyValues", null,
+ new TypeDesc[] {storableType, objectArrayType, TypeDesc.OBJECT});
+
+ b = new CodeBuilder(mi);
+
+ b.loadThis();
+ b.loadLocal(b.getParameter(0));
+ b.loadLocal(b.getParameter(1));
+ b.invokeVirtual("setKeyValues", null, new TypeDesc[] {storableType, objectArrayType});
+
+ userStorableVar = b.createLocalVariable(null, userStorableType);
+ b.loadLocal(b.getParameter(0));
+ b.checkCast(userStorableType);
+ b.storeLocal(userStorableVar);
+
+ // Switch on the number of values supplied.
+
+ /* Switch looks like this for two pk properties:
+
+ switch(identityValues.length) {
+ default:
+ throw new IllegalArgumentException();
+ case 0:
+ storable.setPkProp1(rangeValue);
+ return;
+ case 1:
+ storable.setPkProp2(rangeValue);
+ return;
+ }
+
+ */
+
+ b.loadLocal(b.getParameter(1));
+ b.arrayLength();
+
+ cases = new int[pk.size()];
+ labels = new Label[pk.size()];
+
+ for (int i=0; i<labels.length; i++) {
+ cases[i] = i;
+ labels[i] = b.createLabel();
+ }
+
+ defaultLabel = b.createLabel();
+
+ b.switchBranch(cases, labels, defaultLabel);
+
+ for (int i=0; i<labels.length; i++) {
+ labels[i].setLocation();
+ int prop = cases[i];
+ b.loadLocal(userStorableVar);
+ b.loadLocal(b.getParameter(2));
+ callSetPropertyValue(b, pk.get(prop));
+ b.returnVoid();
+ }
+
+ defaultLabel.setLocation();
+ CodeBuilderUtil.throwException(b, IllegalArgumentException.class, null);
+
+ try {
+ return (Assigner<S>) ci.defineClass(cf).newInstance();
+ } catch (IllegalAccessException e) {
+ throw new UndeclaredThrowableException(e);
+ } catch (InstantiationException e) {
+ throw new UndeclaredThrowableException(e);
+ }
+ }
+
+ /**
+ * Creates code to call set method. Assumes Storable and property value
+ * are already on the stack.
+ */
+ private static void callSetPropertyValue(CodeBuilder b, OrderedProperty<?> op) {
+ StorableProperty<?> property = op.getChainedProperty().getLastProperty();
+ TypeDesc propType = TypeDesc.forClass(property.getType());
+ if (propType != TypeDesc.OBJECT) {
+ TypeDesc objectType = propType.toObjectType();
+ b.checkCast(objectType);
+ // Potentially unbox primitive.
+ b.convert(objectType, propType);
+ }
+ b.invoke(property.getWriteMethod());
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/map/MapCursor.java b/src/main/java/com/amazon/carbonado/repo/map/MapCursor.java
new file mode 100644
index 0000000..cd0f7e3
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/map/MapCursor.java
@@ -0,0 +1,173 @@
+/*
+ * Copyright 2008 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.repo.map;
+
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
+
+import com.amazon.carbonado.FetchException;
+import com.amazon.carbonado.IsolationLevel;
+import com.amazon.carbonado.Storable;
+
+import com.amazon.carbonado.cursor.AbstractCursor;
+
+import com.amazon.carbonado.spi.TransactionScope;
+
+/**
+ * Returns copies of Storables that it iterates over.
+ *
+ * @author Brian S O'Neill
+ */
+class MapCursor<S extends Storable> extends AbstractCursor<S> {
+ private static final AtomicReferenceFieldUpdater<MapCursor, Iterator> cIteratorRef =
+ AtomicReferenceFieldUpdater.newUpdater
+ (MapCursor.class, Iterator.class, "mIterator");
+
+ private final MapStorage<S> mStorage;
+ private final TransactionScope<MapTransaction> mScope;
+ private final MapTransaction mTxn;
+ private final boolean mIsForUpdate;
+
+ private volatile Iterator<S> mIterator;
+
+ MapCursor(MapStorage<S> storage,
+ TransactionScope<MapTransaction> scope,
+ Iterable<S> iterable)
+ throws Exception
+ {
+ MapTransaction txn = scope.getTxn();
+
+ mStorage = storage;
+ mScope = scope;
+ mTxn = txn;
+
+ if (txn == null) {
+ mStorage.mLock.lockForRead(scope);
+ mIsForUpdate = false;
+ } else {
+ // Since lock is so coarse, all reads in transaction scope are
+ // upgrade to avoid deadlocks.
+ txn.lockForUpgrade(mStorage.mLock, mIsForUpdate = scope.isForUpdate());
+ }
+
+ scope.register(storage.getStorableType(), this);
+ mIterator = iterable.iterator();
+ }
+
+ public void close() {
+ Iterator<S> it = mIterator;
+ if (it != null) {
+ if (cIteratorRef.compareAndSet(this, it, null)) {
+ UpgradableLock lock = mStorage.mLock;
+ if (mTxn == null) {
+ lock.unlockFromRead(mScope);
+ } else {
+ mTxn.unlockFromUpgrade(lock, mIsForUpdate);
+ }
+ mScope.unregister(mStorage.getStorableType(), this);
+ }
+ }
+ }
+
+ public boolean hasNext() throws FetchException {
+ Iterator<S> it = mIterator;
+ try {
+ if (it != null && it.hasNext()) {
+ return true;
+ } else {
+ close();
+ }
+ return false;
+ } catch (ConcurrentModificationException e) {
+ close();
+ throw new FetchException(e);
+ } catch (Error e) {
+ try {
+ close();
+ } catch (Error e2) {
+ // Ignore.
+ }
+ throw e;
+ }
+ }
+
+ public S next() throws FetchException {
+ Iterator<S> it = mIterator;
+ if (it == null) {
+ close();
+ throw new NoSuchElementException();
+ }
+ try {
+ S next = mStorage.copyAndFireLoadTrigger(it.next());
+ if (!hasNext()) {
+ close();
+ }
+ return next;
+ } catch (ConcurrentModificationException e) {
+ close();
+ throw new FetchException(e);
+ } catch (Error e) {
+ try {
+ close();
+ } catch (Error e2) {
+ // Ignore.
+ }
+ throw e;
+ }
+ }
+
+ @Override
+ public int skipNext(int amount) throws FetchException {
+ if (amount <= 0) {
+ if (amount < 0) {
+ throw new IllegalArgumentException("Cannot skip negative amount: " + amount);
+ }
+ return 0;
+ }
+
+ // Skip over entries without copying them.
+
+ int count = 0;
+ Iterator<S> it = mIterator;
+
+ if (it != null) {
+ try {
+ while (--amount >= 0 && it.hasNext()) {
+ it.next();
+ count++;
+ }
+ } catch (ConcurrentModificationException e) {
+ close();
+ throw new FetchException(e);
+ } catch (Error e) {
+ try {
+ close();
+ } catch (Error e2) {
+ // Ignore.
+ }
+ throw e;
+ }
+ }
+
+ return count;
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/map/MapRepository.java b/src/main/java/com/amazon/carbonado/repo/map/MapRepository.java
new file mode 100644
index 0000000..2e82f89
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/map/MapRepository.java
@@ -0,0 +1,125 @@
+/*
+ * Copyright 2008 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.repo.map;
+
+import java.util.concurrent.atomic.AtomicReference;
+import java.util.concurrent.TimeUnit;
+
+import org.apache.commons.logging.Log;
+
+import com.amazon.carbonado.Repository;
+import com.amazon.carbonado.RepositoryException;
+import com.amazon.carbonado.Storable;
+import com.amazon.carbonado.Storage;
+import com.amazon.carbonado.TriggerFactory;
+
+import com.amazon.carbonado.capability.IndexInfo;
+import com.amazon.carbonado.capability.IndexInfoCapability;
+
+import com.amazon.carbonado.sequence.SequenceValueGenerator;
+import com.amazon.carbonado.sequence.SequenceValueProducer;
+
+import com.amazon.carbonado.qe.RepositoryAccess;
+import com.amazon.carbonado.qe.StorageAccess;
+
+import com.amazon.carbonado.spi.AbstractRepository;
+import com.amazon.carbonado.spi.LobEngine;
+import com.amazon.carbonado.spi.TransactionManager;
+import com.amazon.carbonado.spi.TransactionScope;
+
+/**
+ *
+ *
+ * @author Brian S O'Neill
+ * @see MapRepositoryBuilder
+ */
+class MapRepository extends AbstractRepository<MapTransaction>
+ implements RepositoryAccess, IndexInfoCapability
+{
+ private final AtomicReference<Repository> mRootRef;
+ private final boolean mIsMaster;
+ private final int mLockTimeout;
+ private final TimeUnit mLockTimeoutUnit;
+
+ final Iterable<TriggerFactory> mTriggerFactories;
+ private final MapTransactionManager mTxnManager;
+ private LobEngine mLobEngine;
+
+ MapRepository(AtomicReference<Repository> rootRef, MapRepositoryBuilder builder) {
+ super(builder.getName());
+ mRootRef = rootRef;
+ mIsMaster = builder.isMaster();
+ mLockTimeout = builder.getLockTimeout();
+ mLockTimeoutUnit = builder.getLockTimeoutUnit();
+
+ mTriggerFactories = builder.getTriggerFactories();
+ mTxnManager = new MapTransactionManager(mLockTimeout, mLockTimeoutUnit);
+ }
+
+ public Repository getRootRepository() {
+ return mRootRef.get();
+ }
+
+ public <S extends Storable> StorageAccess<S> storageAccessFor(Class<S> type)
+ throws RepositoryException
+ {
+ return (StorageAccess<S>) storageFor(type);
+ }
+
+ public <S extends Storable> IndexInfo[] getIndexInfo(Class<S> storableType)
+ throws RepositoryException
+ {
+ return ((MapStorage) storageFor(storableType)).getIndexInfo();
+ }
+
+ protected Log getLog() {
+ return null;
+ }
+
+ protected TransactionManager<MapTransaction> transactionManager() {
+ return mTxnManager;
+ }
+
+ protected TransactionScope<MapTransaction> localTransactionScope() {
+ return mTxnManager.localScope();
+ }
+
+ protected <S extends Storable> Storage<S> createStorage(Class<S> type)
+ throws RepositoryException
+ {
+ return new MapStorage<S>(this, type, mLockTimeout, mLockTimeoutUnit);
+ }
+
+ protected SequenceValueProducer createSequenceValueProducer(String name)
+ throws RepositoryException
+ {
+ return new SequenceValueGenerator(this, name);
+ }
+
+ LobEngine getLobEngine() throws RepositoryException {
+ if (mLobEngine == null) {
+ mLobEngine = new LobEngine(this, getRootRepository());
+ }
+ return mLobEngine;
+ }
+
+ boolean isMaster() {
+ return mIsMaster;
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/map/MapRepositoryBuilder.java b/src/main/java/com/amazon/carbonado/repo/map/MapRepositoryBuilder.java
new file mode 100644
index 0000000..8d5d399
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/map/MapRepositoryBuilder.java
@@ -0,0 +1,151 @@
+/*
+ * Copyright 2008 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.repo.map;
+
+import java.util.concurrent.atomic.AtomicReference;
+import java.util.concurrent.TimeUnit;
+
+import com.amazon.carbonado.Repository;
+import com.amazon.carbonado.RepositoryException;
+
+import com.amazon.carbonado.repo.indexed.IndexedRepositoryBuilder;
+
+import com.amazon.carbonado.spi.AbstractRepositoryBuilder;
+
+/**
+ * Volatile repository implementation backed by a concurrent map. Locks used by
+ * repository are coarse, much like <i>table locks</i>. Loads and queries
+ * acquire read locks, and modifications acquire write locks. Within
+ * transactions, loads and queries always acquire upgradable locks, to reduce
+ * the likelihood of deadlock.
+ *
+ * <p>This repository supports transactions, which also may be
+ * nested. Supported isolation levels are read committed and serializable. Read
+ * uncommitted is promoted to read committed, and repeatable read is promoted
+ * to serializable.
+ *
+ * <p>
+ * The following extra capabilities are supported:
+ * <ul>
+ * <li>{@link com.amazon.carbonado.capability.IndexInfoCapability IndexInfoCapability}
+ * <li>{@link com.amazon.carbonado.capability.ShutdownCapability ShutdownCapability}
+ * <li>{@link com.amazon.carbonado.sequence.SequenceCapability SequenceCapability}
+ * </ul>
+ *
+ * <p>Note: This repository uses concurrent navigable map classes, which became
+ * available in JDK1.6.
+ *
+ * @author Brian S O'Neill
+ * @since 1.2
+ */
+public class MapRepositoryBuilder extends AbstractRepositoryBuilder {
+ /**
+ * Convenience method to build a new MapRepository.
+ */
+ public static Repository newRepository() {
+ try {
+ MapRepositoryBuilder builder = new MapRepositoryBuilder();
+ return builder.build();
+ } catch (RepositoryException e) {
+ // Not expected.
+ throw new RuntimeException(e);
+ }
+ }
+
+ private String mName = "";
+ private boolean mIsMaster = true;
+ private boolean mIndexSupport = true;
+ private int mLockTimeout;
+ private TimeUnit mLockTimeoutUnit;
+
+ public MapRepositoryBuilder() {
+ setLockTimeoutMillis(500);
+ }
+
+ public Repository build(AtomicReference<Repository> rootRef) throws RepositoryException {
+ if (mIndexSupport) {
+ // Temporarily set to false to avoid infinite recursion.
+ mIndexSupport = false;
+ try {
+ IndexedRepositoryBuilder ixBuilder = new IndexedRepositoryBuilder();
+ ixBuilder.setWrappedRepository(this);
+ ixBuilder.setMaster(isMaster());
+ ixBuilder.setAllClustered(true);
+ return ixBuilder.build(rootRef);
+ } finally {
+ mIndexSupport = true;
+ }
+ }
+
+ assertReady();
+
+ Repository repo = new MapRepository(rootRef, this);
+
+ rootRef.set(repo);
+ return repo;
+ }
+
+ public String getName() {
+ return mName;
+ }
+
+ public void setName(String name) {
+ mName = name;
+ }
+
+ public boolean isMaster() {
+ return mIsMaster;
+ }
+
+ public void setMaster(boolean b) {
+ mIsMaster = b;
+ }
+
+ /**
+ * Set the lock timeout, in milliseconds. Default value is 500 milliseconds.
+ */
+ public void setLockTimeoutMillis(int timeout) {
+ setLockTimeout(timeout, TimeUnit.MILLISECONDS);
+ }
+
+ /**
+ * Set the lock timeout. Default value is 500 milliseconds.
+ */
+ public void setLockTimeout(int timeout, TimeUnit unit) {
+ if (timeout < 0 || unit == null) {
+ throw new IllegalArgumentException();
+ }
+ mLockTimeout = timeout;
+ mLockTimeoutUnit = unit;
+ }
+
+ /**
+ * Returns the lock timeout. Call getLockTimeoutUnit to get the unit.
+ */
+ public int getLockTimeout() {
+ return mLockTimeout;
+ }
+
+ /**
+ * Returns the lock timeout unit. Call getLockTimeout to get the timeout.
+ */
+ public TimeUnit getLockTimeoutUnit() {
+ return mLockTimeoutUnit;
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/map/MapStorage.java b/src/main/java/com/amazon/carbonado/repo/map/MapStorage.java
new file mode 100644
index 0000000..520d18c
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/map/MapStorage.java
@@ -0,0 +1,813 @@
+/*
+ * Copyright 2008 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.repo.map;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.EnumSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NavigableMap;
+import java.util.Set;
+
+import java.util.concurrent.ConcurrentNavigableMap;
+import java.util.concurrent.ConcurrentSkipListMap;
+import java.util.concurrent.TimeUnit;
+
+import org.cojen.classfile.TypeDesc;
+
+import com.amazon.carbonado.Cursor;
+import com.amazon.carbonado.FetchException;
+import com.amazon.carbonado.FetchInterruptedException;
+import com.amazon.carbonado.FetchTimeoutException;
+import com.amazon.carbonado.IsolationLevel;
+import com.amazon.carbonado.PersistException;
+import com.amazon.carbonado.PersistInterruptedException;
+import com.amazon.carbonado.PersistTimeoutException;
+import com.amazon.carbonado.Query;
+import com.amazon.carbonado.Repository;
+import com.amazon.carbonado.RepositoryException;
+import com.amazon.carbonado.Storable;
+import com.amazon.carbonado.Storage;
+import com.amazon.carbonado.SupportException;
+import com.amazon.carbonado.Trigger;
+
+import com.amazon.carbonado.capability.IndexInfo;
+
+import com.amazon.carbonado.cursor.ArraySortBuffer;
+import com.amazon.carbonado.cursor.EmptyCursor;
+import com.amazon.carbonado.cursor.FilteredCursor;
+import com.amazon.carbonado.cursor.SingletonCursor;
+import com.amazon.carbonado.cursor.SortBuffer;
+import com.amazon.carbonado.cursor.SortedCursor;
+
+import com.amazon.carbonado.filter.Filter;
+import com.amazon.carbonado.filter.FilterValues;
+import com.amazon.carbonado.filter.RelOp;
+
+import com.amazon.carbonado.sequence.SequenceValueProducer;
+
+import com.amazon.carbonado.gen.DelegateStorableGenerator;
+import com.amazon.carbonado.gen.DelegateSupport;
+import com.amazon.carbonado.gen.MasterFeature;
+
+import com.amazon.carbonado.util.QuickConstructorGenerator;
+
+import com.amazon.carbonado.filter.Filter;
+
+import com.amazon.carbonado.info.ChainedProperty;
+import com.amazon.carbonado.info.Direction;
+import com.amazon.carbonado.info.OrderedProperty;
+import com.amazon.carbonado.info.StorableIndex;
+import com.amazon.carbonado.info.StorableInfo;
+import com.amazon.carbonado.info.StorableIntrospector;
+import com.amazon.carbonado.info.StorableProperty;
+
+import com.amazon.carbonado.qe.BoundaryType;
+import com.amazon.carbonado.qe.QueryExecutorFactory;
+import com.amazon.carbonado.qe.QueryEngine;
+import com.amazon.carbonado.qe.StorageAccess;
+
+import com.amazon.carbonado.spi.IndexInfoImpl;
+import com.amazon.carbonado.spi.LobEngine;
+import com.amazon.carbonado.spi.TransactionScope;
+import com.amazon.carbonado.spi.TriggerManager;
+
+/**
+ *
+ *
+ * @author Brian S O'Neill
+ */
+class MapStorage<S extends Storable>
+ implements Storage<S>, DelegateSupport<S>, StorageAccess<S>
+{
+ private static final int DEFAULT_LOB_BLOCK_SIZE = 1000;
+ private static final Object[] NO_VALUES = new Object[0];
+
+ private final MapRepository mRepo;
+ private final StorableInfo<S> mInfo;
+ private final TriggerManager<S> mTriggers;
+ private final InstanceFactory mInstanceFactory;
+ private final StorableIndex<S> mPrimaryKeyIndex;
+ private final QueryEngine<S> mQueryEngine;
+
+ private final int mLockTimeout;
+ private final TimeUnit mLockTimeoutUnit;
+
+ private final ConcurrentNavigableMap<Key<S>, S> mMap;
+ private final Comparator<S> mFullComparator;
+ private final Comparator<S>[] mSearchComparators;
+
+ private final Key.Assigner<S> mKeyAssigner;
+
+ /**
+ * Simple lock which is reentrant for transactions, but auto-commit does not
+ * need to support reentrancy. Read lock requests in transactions can starve
+ * write lock requests, but auto-commit cannot cause starvation. In practice
+ * starvation is not possible since transactions always lock for upgrade.
+ */
+ final UpgradableLock<Object> mLock = new UpgradableLock<Object>() {
+ @Override
+ protected boolean isReadLockHeld(Object locker) {
+ return locker instanceof MapTransaction;
+ }
+ };
+
+ MapStorage(MapRepository repo, Class<S> type, int lockTimeout, TimeUnit lockTimeoutUnit)
+ throws SupportException
+ {
+ mRepo = repo;
+ mInfo = StorableIntrospector.examine(type);
+ mTriggers = new TriggerManager<S>();
+
+ EnumSet<MasterFeature> features;
+ if (repo.isMaster()) {
+ features = EnumSet.of(MasterFeature.INSERT_CHECK_REQUIRED,
+ MasterFeature.VERSIONING,
+ MasterFeature.INSERT_SEQUENCES);
+ } else {
+ features = EnumSet.of(MasterFeature.INSERT_CHECK_REQUIRED);
+ }
+
+ Class<? extends S> delegateStorableClass =
+ DelegateStorableGenerator.getDelegateClass(type, features);
+
+ mInstanceFactory = QuickConstructorGenerator
+ .getInstance(delegateStorableClass, InstanceFactory.class);
+
+ mPrimaryKeyIndex =
+ new StorableIndex<S>(mInfo.getPrimaryKey(), Direction.ASCENDING).clustered(true);
+
+ mQueryEngine = new QueryEngine<S>(type, repo);
+
+ mLockTimeout = lockTimeout;
+ mLockTimeoutUnit = lockTimeoutUnit;
+
+ mMap = new ConcurrentSkipListMap<Key<S>, S>();
+ List<OrderedProperty<S>> propList = createPkPropList();
+ mFullComparator = SortedCursor.createComparator(propList);
+ mSearchComparators = new Comparator[propList.size() + 1];
+ mSearchComparators[propList.size()] = mFullComparator;
+
+ mKeyAssigner = Key.getAssigner(type);
+
+ try {
+ if (LobEngine.hasLobs(type)) {
+ Trigger<S> lobTrigger = repo.getLobEngine()
+ .getSupportTrigger(type, DEFAULT_LOB_BLOCK_SIZE);
+ addTrigger(lobTrigger);
+ }
+
+ // Don't install automatic triggers until we're completely ready.
+ mTriggers.addTriggers(type, repo.mTriggerFactories);
+ } catch (SupportException e) {
+ throw e;
+ } catch (RepositoryException e) {
+ throw new SupportException(e);
+ }
+ }
+
+ public Class<S> getStorableType() {
+ return mInfo.getStorableType();
+ }
+
+ public S prepare() {
+ return (S) mInstanceFactory.instantiate(this);
+ }
+
+ public Query<S> query() throws FetchException {
+ return mQueryEngine.query();
+ }
+
+ public Query<S> query(String filter) throws FetchException {
+ return mQueryEngine.query(filter);
+ }
+
+ public Query<S> query(Filter<S> filter) throws FetchException {
+ return mQueryEngine.query(filter);
+ }
+
+ public void truncate() throws PersistException {
+ try {
+ Object locker = mRepo.localTransactionScope().getTxn();
+ if (locker == null) {
+ locker = Thread.currentThread();
+ }
+ doLockForWrite(locker);
+ try {
+ mMap.clear();
+ } finally {
+ mLock.unlockFromWrite(locker);
+ }
+ } catch (PersistException e) {
+ throw e;
+ } catch (Exception e) {
+ throw new PersistException(e);
+ }
+ }
+
+ public boolean addTrigger(Trigger<? super S> trigger) {
+ return mTriggers.addTrigger(trigger);
+ }
+
+ public boolean removeTrigger(Trigger<? super S> trigger) {
+ return mTriggers.removeTrigger(trigger);
+ }
+
+ public IndexInfo[] getIndexInfo() {
+ StorableIndex<S> pkIndex = mPrimaryKeyIndex;
+
+ if (pkIndex == null) {
+ return new IndexInfo[0];
+ }
+
+ int i = pkIndex.getPropertyCount();
+ String[] propertyNames = new String[i];
+ Direction[] directions = new Direction[i];
+ while (--i >= 0) {
+ propertyNames[i] = pkIndex.getProperty(i).getName();
+ directions[i] = pkIndex.getPropertyDirection(i);
+ }
+
+ return new IndexInfo[] {
+ new IndexInfoImpl(getStorableType().getName(), true, true, propertyNames, directions)
+ };
+ }
+
+ public boolean doTryLoad(S storable) throws FetchException {
+ try {
+ TransactionScope<MapTransaction> scope = mRepo.localTransactionScope();
+ MapTransaction txn = scope.getTxn();
+ if (txn == null) {
+ doLockForRead(scope);
+ try {
+ return doTryLoadNoLock(storable);
+ } finally {
+ mLock.unlockFromRead(scope);
+ }
+ } else {
+ // Since lock is so coarse, all reads in transaction scope are
+ // upgrade to avoid deadlocks.
+ final boolean isForUpdate = scope.isForUpdate();
+ txn.lockForUpgrade(mLock, isForUpdate);
+ try {
+ return doTryLoadNoLock(storable);
+ } finally {
+ txn.unlockFromUpgrade(mLock, isForUpdate);
+ }
+ }
+ } catch (FetchException e) {
+ throw e;
+ } catch (Exception e) {
+ throw new FetchException(e);
+ }
+ }
+
+ // Caller must hold lock.
+ boolean doTryLoadNoLock(S storable) {
+ S existing = mMap.get(new Key<S>(storable, mFullComparator));
+ if (existing == null) {
+ return false;
+ } else {
+ storable.markAllPropertiesDirty();
+ existing.copyAllProperties(storable);
+ storable.markAllPropertiesClean();
+ return true;
+ }
+ }
+
+ public boolean doTryInsert(S storable) throws PersistException {
+ try {
+ TransactionScope<MapTransaction> scope = mRepo.localTransactionScope();
+ MapTransaction txn = scope.getTxn();
+ if (txn == null) {
+ // No need to acquire full write lock since map is concurrent
+ // and existing storable (if any) is not being
+ // modified. Upgrade lock is required because a concurrent
+ // transaction might be in progress, and so insert should wait.
+ doLockForUpgrade(scope);
+ try {
+ return doTryInsertNoLock(storable);
+ } finally {
+ mLock.unlockFromUpgrade(scope);
+ }
+ } else {
+ txn.lockForWrite(mLock);
+ if (doTryInsertNoLock(storable)) {
+ txn.inserted(this, storable);
+ return true;
+ } else {
+ return false;
+ }
+ }
+ } catch (PersistException e) {
+ throw e;
+ } catch (FetchException e) {
+ throw e.toPersistException();
+ } catch (Exception e) {
+ throw new PersistException(e);
+ }
+ }
+
+ // Caller must hold upgrade or write lock.
+ private boolean doTryInsertNoLock(S storable) {
+ Key<S> key = new Key<S>(storable, mFullComparator);
+ S existing = mMap.get(key);
+ if (existing != null) {
+ return false;
+ }
+ // Create a fresh copy to ensure that custom fields are not saved.
+ S copy = (S) storable.prepare();
+ storable.copyAllProperties(copy);
+ copy.markAllPropertiesClean();
+ mMap.put(key, copy);
+ storable.markAllPropertiesClean();
+ return true;
+ }
+
+ public boolean doTryUpdate(S storable) throws PersistException {
+ try {
+ TransactionScope<MapTransaction> scope = mRepo.localTransactionScope();
+ MapTransaction txn = scope.getTxn();
+ if (txn == null) {
+ // Full write lock is required since existing storable is being
+ // modified. Readers cannot be allowed to see modifications
+ // until they are complete. In addtion, a concurrent
+ // transaction might be in progress, and so update should wait.
+ doLockForWrite(scope);
+ try {
+ return doTryUpdateNoLock(storable);
+ } finally {
+ mLock.unlockFromWrite(scope);
+ }
+ } else {
+ txn.lockForWrite(mLock);
+ S existing = mMap.get(new Key<S>(storable, mFullComparator));
+ if (existing == null) {
+ return false;
+ } else {
+ // Copy existing object to undo log.
+ txn.updated(this, (S) existing.copy());
+
+ // Copy altered values to existing object.
+ existing.markAllPropertiesDirty();
+ storable.copyDirtyProperties(existing);
+ existing.markAllPropertiesClean();
+
+ // Copy all values to user object, to simulate a reload.
+ storable.markAllPropertiesDirty();
+ existing.copyAllProperties(storable);
+ storable.markAllPropertiesClean();
+
+ return true;
+ }
+ }
+ } catch (PersistException e) {
+ throw e;
+ } catch (Exception e) {
+ throw new PersistException(e);
+ }
+ }
+
+ // Caller must hold write lock.
+ private boolean doTryUpdateNoLock(S storable) {
+ S existing = mMap.get(new Key<S>(storable, mFullComparator));
+ if (existing == null) {
+ return false;
+ } else {
+ // Copy altered values to existing object.
+ existing.markAllPropertiesDirty();
+ storable.copyDirtyProperties(existing);
+ existing.markAllPropertiesClean();
+
+ // Copy all values to user object, to simulate a reload.
+ storable.markAllPropertiesDirty();
+ existing.copyAllProperties(storable);
+ storable.markAllPropertiesClean();
+
+ return true;
+ }
+ }
+
+ public boolean doTryDelete(S storable) throws PersistException {
+ try {
+ TransactionScope<MapTransaction> scope = mRepo.localTransactionScope();
+ MapTransaction txn = scope.getTxn();
+ if (txn == null) {
+ // No need to acquire full write lock since map is concurrent
+ // and existing storable (if any) is not being
+ // modified. Upgrade lock is required because a concurrent
+ // transaction might be in progress, and so delete should wait.
+ doLockForUpgrade(scope);
+ try {
+ return doTryDeleteNoLock(storable);
+ } finally {
+ mLock.unlockFromUpgrade(scope);
+ }
+ } else {
+ txn.lockForWrite(mLock);
+ S existing = mMap.remove(new Key<S>(storable, mFullComparator));
+ if (existing == null) {
+ return false;
+ } else {
+ txn.deleted(this, existing);
+ return true;
+ }
+ }
+ } catch (PersistException e) {
+ throw e;
+ } catch (FetchException e) {
+ throw e.toPersistException();
+ } catch (Exception e) {
+ throw new PersistException(e);
+ }
+ }
+
+ // Caller must hold upgrade or write lock.
+ private boolean doTryDeleteNoLock(S storable) {
+ return mMap.remove(new Key<S>(storable, mFullComparator)) != null;
+ }
+
+ // Called by MapTransaction, which implicitly holds lock.
+ void mapPut(S storable) {
+ mMap.put(new Key<S>(storable, mFullComparator), storable);
+ }
+
+ // Called by MapTransaction, which implicitly holds lock.
+ void mapRemove(S storable) {
+ mMap.remove(new Key<S>(storable, mFullComparator));
+ }
+
+ private void doLockForRead(Object locker) throws FetchException {
+ try {
+ if (!mLock.tryLockForRead(locker, mLockTimeout, mLockTimeoutUnit)) {
+ throw new FetchTimeoutException("" + mLockTimeout + ' ' +
+ mLockTimeoutUnit.toString().toLowerCase());
+ }
+ } catch (InterruptedException e) {
+ throw new FetchInterruptedException(e);
+ }
+ }
+
+ private void doLockForUpgrade(Object locker) throws FetchException {
+ try {
+ if (!mLock.tryLockForUpgrade(locker, mLockTimeout, mLockTimeoutUnit)) {
+ throw new FetchTimeoutException("" + mLockTimeout + ' ' +
+ mLockTimeoutUnit.toString().toLowerCase());
+ }
+ } catch (InterruptedException e) {
+ throw new FetchInterruptedException(e);
+ }
+ }
+
+ private void doLockForWrite(Object locker) throws PersistException {
+ try {
+ if (!mLock.tryLockForWrite(locker, mLockTimeout, mLockTimeoutUnit)) {
+ throw new PersistTimeoutException("" + mLockTimeout + ' ' +
+ mLockTimeoutUnit.toString().toLowerCase());
+ }
+ } catch (InterruptedException e) {
+ throw new PersistInterruptedException(e);
+ }
+ }
+
+ public Repository getRootRepository() {
+ return mRepo.getRootRepository();
+ }
+
+ public boolean isPropertySupported(String propertyName) {
+ return mInfo.getAllProperties().containsKey(propertyName);
+ }
+
+ public Trigger<? super S> getInsertTrigger() {
+ return mTriggers.getInsertTrigger();
+ }
+
+ public Trigger<? super S> getUpdateTrigger() {
+ return mTriggers.getUpdateTrigger();
+ }
+
+ public Trigger<? super S> getDeleteTrigger() {
+ return mTriggers.getDeleteTrigger();
+ }
+
+ public Trigger<? super S> getLoadTrigger() {
+ return mTriggers.getLoadTrigger();
+ }
+
+ public void locallyDisableLoadTrigger() {
+ mTriggers.locallyDisableLoad();
+ }
+
+ public void locallyEnableLoadTrigger() {
+ mTriggers.locallyEnableLoad();
+ }
+
+ public SequenceValueProducer getSequenceValueProducer(String name) throws PersistException {
+ try {
+ return mRepo.getSequenceValueProducer(name);
+ } catch (RepositoryException e) {
+ throw e.toPersistException();
+ }
+ }
+
+ public QueryExecutorFactory<S> getQueryExecutorFactory() {
+ return mQueryEngine;
+ }
+
+ public Collection<StorableIndex<S>> getAllIndexes() {
+ return Collections.singletonList(mPrimaryKeyIndex);
+ }
+
+ public Storage<S> storageDelegate(StorableIndex<S> index) {
+ // We're the grunt and don't delegate.
+ return null;
+ }
+
+ public long countAll() throws FetchException {
+ try {
+ Object locker = mRepo.localTransactionScope().getTxn();
+ if (locker == null) {
+ locker = Thread.currentThread();
+ }
+ doLockForRead(locker);
+ try {
+ return mMap.size();
+ } finally {
+ mLock.unlockFromRead(locker);
+ }
+ } catch (FetchException e) {
+ throw e;
+ } catch (Exception e) {
+ throw new FetchException(e);
+ }
+ }
+
+ public Cursor<S> fetchAll() throws FetchException {
+ try {
+ return new MapCursor<S>(this, mRepo.localTransactionScope(), mMap.values());
+ } catch (FetchException e) {
+ throw e;
+ } catch (Exception e) {
+ throw new FetchException(e);
+ }
+ }
+
+ public Cursor<S> fetchOne(StorableIndex<S> index, Object[] identityValues)
+ throws FetchException
+ {
+ try {
+ S key = prepare();
+ for (int i=0; i<identityValues.length; i++) {
+ key.setPropertyValue(index.getProperty(i).getName(), identityValues[i]);
+ }
+
+ TransactionScope<MapTransaction> scope = mRepo.localTransactionScope();
+ MapTransaction txn = scope.getTxn();
+ if (txn == null) {
+ doLockForRead(scope);
+ try {
+ S value = mMap.get(new Key<S>(key, mFullComparator));
+ if (value == null) {
+ return EmptyCursor.the();
+ } else {
+ return new SingletonCursor<S>(copyAndFireLoadTrigger(value));
+ }
+ } finally {
+ mLock.unlockFromRead(scope);
+ }
+ } else {
+ // Since lock is so coarse, all reads in transaction scope are
+ // upgrade to avoid deadlocks.
+ final boolean isForUpdate = scope.isForUpdate();
+ txn.lockForUpgrade(mLock, isForUpdate);
+ try {
+ S value = mMap.get(new Key<S>(key, mFullComparator));
+ if (value == null) {
+ return EmptyCursor.the();
+ } else {
+ return new SingletonCursor<S>(copyAndFireLoadTrigger(value));
+ }
+ } finally {
+ txn.unlockFromUpgrade(mLock, isForUpdate);
+ }
+ }
+ } catch (FetchException e) {
+ throw e;
+ } catch (Exception e) {
+ throw new FetchException(e);
+ }
+ }
+
+ S copyAndFireLoadTrigger(S storable) throws FetchException {
+ storable = (S) storable.copy();
+ Trigger<? super S> trigger = getLoadTrigger();
+ if (trigger != null) {
+ trigger.afterLoad(storable);
+ // In case trigger modified the properties, make sure they're still clean.
+ storable.markAllPropertiesClean();
+ }
+ return storable;
+ }
+
+ public Query<?> indexEntryQuery(StorableIndex<S> index) {
+ return null;
+ }
+
+ public Cursor<S> fetchFromIndexEntryQuery(StorableIndex<S> index, Query<?> indexEntryQuery) {
+ return null;
+ }
+
+ public Cursor<S> fetchSubset(StorableIndex<S> index,
+ Object[] identityValues,
+ BoundaryType rangeStartBoundary,
+ Object rangeStartValue,
+ BoundaryType rangeEndBoundary,
+ Object rangeEndValue,
+ boolean reverseRange,
+ boolean reverseOrder)
+ throws FetchException
+ {
+ if (identityValues == null) {
+ identityValues = NO_VALUES;
+ }
+
+ NavigableMap<Key<S>, S> map = mMap;
+
+ int tieBreaker = 1;
+ if (reverseOrder) {
+ map = map.descendingMap();
+ reverseRange = !reverseRange;
+ tieBreaker = -tieBreaker;
+ }
+
+ if (reverseRange) {
+ BoundaryType t1 = rangeStartBoundary;
+ rangeStartBoundary = rangeEndBoundary;
+ rangeEndBoundary = t1;
+ Object t2 = rangeStartValue;
+ rangeStartValue = rangeEndValue;
+ rangeEndValue = t2;
+ }
+
+ tail: {
+ Key<S> startKey;
+ switch (rangeStartBoundary) {
+ case OPEN: default:
+ if (identityValues.length == 0) {
+ break tail;
+ } else {
+ // Tie breaker of -1 puts search key right before first actual
+ // match, thus forming an inclusive start match.
+ startKey = searchKey(-tieBreaker, identityValues);
+ }
+ break;
+ case INCLUSIVE:
+ // Tie breaker of -1 puts search key right before first actual
+ // match, thus forming an inclusive start match.
+ startKey = searchKey(-tieBreaker, identityValues, rangeStartValue);
+ break;
+ case EXCLUSIVE:
+ // Tie breaker of +1 puts search key right after first actual
+ // match, thus forming an exlusive start match.
+ startKey = searchKey(tieBreaker, identityValues, rangeStartValue);
+ break;
+ }
+
+ map = map.tailMap(startKey, true);
+ }
+
+ Cursor<S> cursor;
+ try {
+ cursor = new MapCursor<S>(this, mRepo.localTransactionScope(), map.values());
+ } catch (FetchException e) {
+ throw e;
+ } catch (Exception e) {
+ throw new FetchException(e);
+ }
+
+ // Use filter to stop cursor at desired ending position.
+
+ // FIXME: Let query engine do this so that filter can be
+ // cached. Somehow indicate this at a high level so that query plan
+ // shows a filter.
+ Filter<S> filter;
+ FilterValues<S> filterValues;
+
+ if (rangeEndBoundary == BoundaryType.OPEN) {
+ if (identityValues.length == 0) {
+ filter = null;
+ filterValues = null;
+ } else {
+ filter = Filter.getOpenFilter(getStorableType());
+ for (int i=0; i<identityValues.length; i++) {
+ filter = filter.and(index.getProperty(i).getName(), RelOp.EQ);
+ }
+ filterValues = filter.initialFilterValues();
+ for (int i=0; i<identityValues.length; i++) {
+ filterValues = filterValues.with(identityValues[i]);
+ }
+ }
+ } else {
+ filter = Filter.getOpenFilter(getStorableType());
+ int i = 0;
+ for (; i<identityValues.length; i++) {
+ filter = filter.and(index.getProperty(i).getName(), RelOp.EQ);
+ }
+
+ filter = filter.and(index.getProperty(i).getName(),
+ rangeEndBoundary == BoundaryType.INCLUSIVE ? RelOp.LE : RelOp.LT);
+
+ filterValues = filter.initialFilterValues();
+
+ for (i=0; i<identityValues.length; i++) {
+ filterValues = filterValues.with(identityValues[i]);
+ }
+
+ filterValues = filterValues.with(rangeEndValue);
+ }
+
+ if (filter != null) {
+ cursor = FilteredCursor.applyFilter(filter, filterValues, cursor);
+ }
+
+ return cursor;
+ }
+
+ private List<OrderedProperty<S>> createPkPropList() {
+ return new ArrayList<OrderedProperty<S>>(mInfo.getPrimaryKey().getProperties());
+ }
+
+ private Key<S> searchKey(int tieBreaker, Object[] identityValues) {
+ S storable = prepare();
+ mKeyAssigner.setKeyValues(storable, identityValues);
+ Comparator<S> c = getSearchComparator(identityValues.length);
+ return new SearchKey<S>(tieBreaker, storable, c);
+ }
+
+ private Key<S> searchKey(int tieBreaker, Object[] identityValues, Object rangeValue) {
+ S storable = prepare();
+ mKeyAssigner.setKeyValues(storable, identityValues, rangeValue);
+ Comparator<S> c = getSearchComparator(identityValues.length + 1);
+ return new SearchKey<S>(tieBreaker, storable, c);
+ }
+
+ private Comparator<S> getSearchComparator(int propertyCount) {
+ Comparator<S> comparator = mSearchComparators[propertyCount];
+ if (comparator == null) {
+ List<OrderedProperty<S>> propList = createPkPropList().subList(0, propertyCount);
+ if (propList.size() > 0) {
+ comparator = SortedCursor.createComparator(propList);
+ } else {
+ comparator = SortedCursor.createComparator(getStorableType());
+ }
+ mSearchComparators[propertyCount] = comparator;
+ }
+ return comparator;
+ }
+
+ public SortBuffer<S> createSortBuffer() {
+ return new ArraySortBuffer<S>();
+ }
+
+ public static interface InstanceFactory {
+ Storable instantiate(DelegateSupport support);
+ }
+
+ private static class SearchKey<S extends Storable> extends Key<S> {
+ private final int mTieBreaker;
+
+ SearchKey(int tieBreaker, S storable, Comparator<S> comparator) {
+ super(storable, comparator);
+ mTieBreaker = tieBreaker;
+ }
+
+ @Override
+ protected int tieBreaker() {
+ return mTieBreaker;
+ }
+
+ @Override
+ public String toString() {
+ return super.toString() + ", tieBreaker=" + mTieBreaker;
+ }
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/map/MapTransaction.java b/src/main/java/com/amazon/carbonado/repo/map/MapTransaction.java
new file mode 100644
index 0000000..d2cfe87
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/map/MapTransaction.java
@@ -0,0 +1,240 @@
+/*
+ * Copyright 2008 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.repo.map;
+
+import java.util.concurrent.TimeUnit;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+import com.amazon.carbonado.FetchException;
+import com.amazon.carbonado.FetchInterruptedException;
+import com.amazon.carbonado.FetchTimeoutException;
+import com.amazon.carbonado.IsolationLevel;
+import com.amazon.carbonado.PersistException;
+import com.amazon.carbonado.PersistInterruptedException;
+import com.amazon.carbonado.PersistTimeoutException;
+import com.amazon.carbonado.Storable;
+import com.amazon.carbonado.Storage;
+
+/**
+ *
+ *
+ * @author Brian S O'Neill
+ */
+class MapTransaction {
+ private final MapTransaction mParent;
+ private final IsolationLevel mLevel;
+ private final Object mLocker;
+ private final int mLockTimeout;
+ private final TimeUnit mLockTimeoutUnit;
+
+ private Set<UpgradableLock> mUpgradeLocks;
+ private Set<UpgradableLock> mWriteLocks;
+
+ private List<Undoable> mUndoLog;
+
+ MapTransaction(MapTransaction parent, IsolationLevel level,
+ int lockTimeout, TimeUnit lockTimeoutUnit)
+ {
+ mParent = parent;
+ mLevel = level;
+ mLocker = parent == null ? this : parent.mLocker;
+ mLockTimeout = lockTimeout;
+ mLockTimeoutUnit = lockTimeoutUnit;
+ }
+
+ void lockForUpgrade(UpgradableLock lock, boolean isForUpdate) throws FetchException {
+ if (!isForUpdate && mLevel.isAtMost(IsolationLevel.READ_COMMITTED)) {
+ doLockForUpgrade(lock);
+ } else {
+ Set<UpgradableLock> locks = mUpgradeLocks;
+ if (locks == null) {
+ mUpgradeLocks = locks = new HashSet<UpgradableLock>();
+ doLockForUpgrade(lock);
+ locks.add(lock);
+ } else if (!locks.contains(lock)) {
+ doLockForUpgrade(lock);
+ locks.add(lock);
+ }
+ }
+ }
+
+ private void doLockForUpgrade(UpgradableLock lock) throws FetchException {
+ try {
+ if (!lock.tryLockForUpgrade(mLocker, mLockTimeout, mLockTimeoutUnit)) {
+ throw new FetchTimeoutException("" + mLockTimeout + ' ' +
+ mLockTimeoutUnit.toString().toLowerCase());
+ }
+ } catch (InterruptedException e) {
+ throw new FetchInterruptedException(e);
+ }
+ }
+
+ void unlockFromUpgrade(UpgradableLock lock, boolean isForUpdate) {
+ if (!isForUpdate && mLevel.isAtMost(IsolationLevel.READ_COMMITTED)) {
+ lock.unlockFromUpgrade(mLocker);
+ }
+ }
+
+ void lockForWrite(UpgradableLock lock) throws PersistException {
+ Set<UpgradableLock> locks = mWriteLocks;
+ if (locks == null) {
+ mWriteLocks = locks = new HashSet<UpgradableLock>();
+ doLockForWrite(lock);
+ locks.add(lock);
+ } else if (!locks.contains(lock)) {
+ doLockForWrite(lock);
+ locks.add(lock);
+ }
+ }
+
+ private void doLockForWrite(UpgradableLock lock) throws PersistException {
+ try {
+ if (!lock.tryLockForWrite(mLocker, mLockTimeout, mLockTimeoutUnit)) {
+ throw new PersistTimeoutException("" + mLockTimeout + ' ' +
+ mLockTimeoutUnit.toString().toLowerCase());
+ }
+ } catch (InterruptedException e) {
+ throw new PersistInterruptedException(e);
+ }
+ }
+
+ /**
+ * Add to undo log.
+ */
+ <S extends Storable> void inserted(final MapStorage<S> storage, final S key) {
+ addToUndoLog(new Undoable() {
+ public void undo() {
+ storage.mapRemove(key);
+ }
+ });
+ }
+
+ /**
+ * Add to undo log.
+ */
+ <S extends Storable> void updated(final MapStorage<S> storage, final S old) {
+ addToUndoLog(new Undoable() {
+ public void undo() {
+ storage.mapPut(old);
+ }
+ });
+ }
+
+ /**
+ * Add to undo log.
+ */
+ <S extends Storable> void deleted(final MapStorage<S> storage, final S old) {
+ addToUndoLog(new Undoable() {
+ public void undo() {
+ storage.mapPut(old);
+ }
+ });
+ }
+
+ void commit() {
+ MapTransaction parent = mParent;
+
+ if (parent == null) {
+ releaseLocks();
+ return;
+ }
+
+ // Pass undo log to parent.
+ if (parent.mUndoLog == null) {
+ parent.mUndoLog = mUndoLog;
+ } else if (mUndoLog != null) {
+ parent.mUndoLog.addAll(mUndoLog);
+ }
+ mUndoLog = null;
+
+ // Pass write locks to parent or release if parent already has the lock.
+ {
+ Set<UpgradableLock> locks = mWriteLocks;
+ if (locks != null) {
+ Set<UpgradableLock> parentLocks = parent.mWriteLocks;
+ if (parentLocks == null) {
+ parent.mWriteLocks = locks;
+ } else {
+ for (UpgradableLock lock : locks) {
+ if (!parentLocks.add(lock)) {
+ lock.unlockFromWrite(mLocker);
+ }
+ }
+ }
+ mWriteLocks = null;
+ }
+ }
+
+ // Upgrade locks can simply be released.
+ releaseUpgradeLocks();
+ }
+
+ void abort() {
+ List<Undoable> log = mUndoLog;
+ if (log != null) {
+ for (int i=log.size(); --i>=0; ) {
+ log.get(i).undo();
+ }
+ }
+ mUndoLog = null;
+
+ releaseLocks();
+ }
+
+ private void addToUndoLog(Undoable entry) {
+ List<Undoable> log = mUndoLog;
+ if (log == null) {
+ mUndoLog = log = new ArrayList<Undoable>();
+ }
+ log.add(entry);
+ }
+
+ private void releaseLocks() {
+ releaseWriteLocks();
+ releaseUpgradeLocks();
+ }
+
+ private void releaseWriteLocks() {
+ Set<UpgradableLock> locks = mWriteLocks;
+ if (locks != null) {
+ for (UpgradableLock lock : locks) {
+ lock.unlockFromWrite(mLocker);
+ }
+ mWriteLocks = null;
+ }
+ }
+
+ private void releaseUpgradeLocks() {
+ Set<UpgradableLock> locks = mUpgradeLocks;
+ if (locks != null) {
+ for (UpgradableLock lock : locks) {
+ lock.unlockFromUpgrade(mLocker);
+ }
+ mUpgradeLocks = null;
+ }
+ }
+
+ private static interface Undoable {
+ void undo();
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/map/MapTransactionManager.java b/src/main/java/com/amazon/carbonado/repo/map/MapTransactionManager.java
new file mode 100644
index 0000000..5598353
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/map/MapTransactionManager.java
@@ -0,0 +1,98 @@
+/*
+ * Copyright 2008 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.repo.map;
+
+import java.util.concurrent.TimeUnit;
+
+import com.amazon.carbonado.IsolationLevel;
+import com.amazon.carbonado.PersistException;
+import com.amazon.carbonado.Transaction;
+
+import com.amazon.carbonado.spi.TransactionManager;
+
+/**
+ *
+ *
+ * @author Brian S O'Neill
+ */
+class MapTransactionManager extends TransactionManager<MapTransaction> {
+ private final int mLockTimeout;
+ private final TimeUnit mLockTimeoutUnit;
+
+ MapTransactionManager(int lockTimeout, TimeUnit lockTimeoutUnit) {
+ mLockTimeout = lockTimeout;
+ mLockTimeoutUnit = lockTimeoutUnit;
+ }
+
+ protected IsolationLevel selectIsolationLevel(Transaction parent, IsolationLevel level) {
+ if (level == null) {
+ if (parent == null) {
+ return IsolationLevel.READ_COMMITTED;
+ }
+ return parent.getIsolationLevel();
+ }
+
+ switch (level) {
+ case NONE:
+ return IsolationLevel.NONE;
+ case READ_UNCOMMITTED:
+ case READ_COMMITTED:
+ return IsolationLevel.READ_COMMITTED;
+ case REPEATABLE_READ:
+ case SERIALIZABLE:
+ return IsolationLevel.SERIALIZABLE;
+ default:
+ // Not supported.
+ return null;
+ }
+ }
+
+ protected boolean supportsForUpdate() {
+ return true;
+ }
+
+ protected MapTransaction createTxn(MapTransaction parent, IsolationLevel level)
+ throws Exception
+ {
+ if (level == IsolationLevel.NONE) {
+ return null;
+ }
+ return new MapTransaction(parent, level, mLockTimeout, mLockTimeoutUnit);
+ }
+
+ @Override
+ protected MapTransaction createTxn(MapTransaction parent, IsolationLevel level,
+ int timeout, TimeUnit unit)
+ throws Exception
+ {
+ if (level == IsolationLevel.NONE) {
+ return null;
+ }
+ return new MapTransaction(parent, level, timeout, unit);
+ }
+
+ protected boolean commitTxn(MapTransaction txn) throws PersistException {
+ txn.commit();
+ return false;
+ }
+
+ protected void abortTxn(MapTransaction txn) throws PersistException {
+ txn.abort();
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/map/UpgradableLock.java b/src/main/java/com/amazon/carbonado/repo/map/UpgradableLock.java
new file mode 100644
index 0000000..9862791
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/map/UpgradableLock.java
@@ -0,0 +1,1161 @@
+/*
+ * Copyright 2007 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.repo.map;
+
+import java.util.concurrent.TimeUnit;
+
+import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
+
+import java.util.concurrent.locks.LockSupport;
+
+/**
+ * Partially reentrant, upgradable read/write lock. Up to 1,073,741,824 read
+ * locks can be held. Upgraders and writers may re-enter the lock up to
+ * 2,147,483,648 times. Attempts by readers to re-enter the lock is not
+ * detected and is deadlock prone, unless locker already holds an upgrade or
+ * write lock. Subclasses can support full reentrancy by overriding the
+ * protected read lock adjust and hold check methods.
+ *
+ * <p>This lock implementation differs from the usual Java lock with respect to
+ * lock ownership. Locks are not owned by threads, but by arbitrary locker
+ * objects. A thread which attempts to acquire an upgrade or write lock twice
+ * with different locker objects will deadlock on the second attempt.
+ *
+ * <p>As is typical of read/write lock implementations, a read lock blocks
+ * waiting writers, but it doesn't block other readers. A write lock is
+ * exclusive and can be held by at most one locker. Attempting to acquire a
+ * write lock while a read lock is held by the same locker is inherently
+ * deadlock prone, and some read/write lock implementations will always
+ * deadlock.
+ *
+ * <p>An upgrade lock allows a read lock to be safely upgraded to a write
+ * lock. Instead of acquiring a read lock, an upgrade lock is acquired. This
+ * acts like a shared read lock in that readers are not blocked, but it also
+ * acts like an exclusive write lock -- writers and upgraders are blocked. With
+ * an upgrade lock held, the locker may acquire a write lock without deadlock.
+ *
+ * <pre>
+ * Locks held Locks safely Locks acquirable
+ * by owner acquirable by owner by other lockers
+ * --------------------------------------------------
+ * - - - R U W R U W
+ * R - - - - - R U -
+ * R U - - U - R - -
+ * - U - R U W R - -
+ * - U W R U W - - -
+ * R U W R U W - - -
+ * R - W R U W - - -
+ * - - W R U W - - -
+ * </pre>
+ *
+ * @author Brian S O'Neill
+ * @param <L> Locker type
+ */
+class UpgradableLock<L> {
+ // Design note: This class borrows heavily from AbstractQueuedSynchronizer.
+ // Consult that class for understanding the locking mechanics.
+
+ private static enum Result {
+ /** Lock acquisition failed */
+ FAILED,
+ /** Lock has just been acquired by locker and can be safely released later */
+ ACQUIRED,
+ /** Lock is already owned by locker and should not be released more than once */
+ OWNED
+ }
+
+ private static final AtomicReferenceFieldUpdater<UpgradableLock, Node> cRWHeadRef =
+ AtomicReferenceFieldUpdater.newUpdater
+ (UpgradableLock.class, Node.class, "mRWHead");
+
+ private static final AtomicReferenceFieldUpdater<UpgradableLock, Node> cRWTailRef =
+ AtomicReferenceFieldUpdater.newUpdater
+ (UpgradableLock.class, Node.class, "mRWTail");
+
+ private static final AtomicReferenceFieldUpdater<UpgradableLock, Node> cUHeadRef =
+ AtomicReferenceFieldUpdater.newUpdater
+ (UpgradableLock.class, Node.class, "mUHead");
+
+ private static final AtomicReferenceFieldUpdater<UpgradableLock, Node> cUTailRef =
+ AtomicReferenceFieldUpdater.newUpdater
+ (UpgradableLock.class, Node.class, "mUTail");
+
+ private static final AtomicIntegerFieldUpdater<UpgradableLock> cStateRef =
+ AtomicIntegerFieldUpdater.newUpdater
+ (UpgradableLock.class, "mState");
+
+ // State mask bits for held locks. Read lock count is stored in lower 30 bits of state.
+ private static final int LOCK_STATE_UPGRADE = 0x40000000;
+ // Write state must be this value in order for quick sign check to work.
+ private static final int LOCK_STATE_WRITE = 0x80000000;
+
+ private static final int LOCK_STATE_MASK = LOCK_STATE_UPGRADE | LOCK_STATE_WRITE;
+
+ /**
+ * The number of nanoseconds for which it is faster to spin
+ * rather than to use timed park. A rough estimate suffices
+ * to improve responsiveness with very short timeouts.
+ */
+ private static final long SPIN_FOR_TIMEOUT_THRESHOLD = 1000L;
+
+ // Head of read-write queue.
+ private transient volatile Node mRWHead;
+
+ // Tail of read-write queue.
+ private transient volatile Node mRWTail;
+
+ // Head of write upgrade queue.
+ private transient volatile Node mUHead;
+
+ // Tail of write upgrade queue.
+ private transient volatile Node mUTail;
+
+ private transient volatile int mState;
+
+ // Owner holds an upgradable lock and possibly a write lock too.
+ private transient L mOwner;
+
+ // Counts number of times that owner has entered an upgradable or write lock.
+ private transient int mUpgradeCount;
+ private transient int mWriteCount;
+
+ public UpgradableLock() {
+ }
+
+ /**
+ * Acquire a shared read lock, possibly blocking indefinitely.
+ *
+ * @param locker object which might be write or upgrade lock owner
+ */
+ public final void lockForRead(L locker) {
+ if (!tryLockForRead(locker)) {
+ lockForReadQueued(locker, addReadWaiter());
+ }
+ }
+
+ /**
+ * Acquire a shared read lock, possibly blocking until interrupted.
+ *
+ * @param locker object which might be write or upgrade lock owner
+ */
+ public final void lockForReadInterruptibly(L locker) throws InterruptedException {
+ if (Thread.interrupted()) {
+ throw new InterruptedException();
+ }
+ if (!tryLockForRead(locker)) {
+ lockForReadQueuedInterruptibly(locker, addReadWaiter());
+ }
+ }
+
+ /**
+ * Attempt to immediately acquire a shared read lock.
+ *
+ * @param locker object which might be write or upgrade lock owner
+ * @return true if acquired
+ */
+ public final boolean tryLockForRead(L locker) {
+ int state = mState;
+ if (state >= 0) { // no write lock is held
+ if (isReadWriteFirst() || isReadLockHeld(locker)) {
+ do {
+ if (incrementReadLocks(state)) {
+ adjustReadLockCount(locker, 1);
+ return true;
+ }
+ // keep looping on CAS failure if a reader or upgrader mucked with the state
+ } while ((state = mState) >= 0);
+ }
+ } else if (mOwner == locker) {
+ // keep looping on CAS failure if a reader or upgrader mucked with the state
+ while (!incrementReadLocks(state)) {
+ state = mState;
+ }
+ adjustReadLockCount(locker, 1);
+ return true;
+ }
+ return false;
+ }
+
+ /**
+ * Attempt to acquire a shared read lock, waiting a maximum amount of
+ * time.
+ *
+ * @param locker object which might be write or upgrade lock owner
+ * @return true if acquired
+ */
+ public final boolean tryLockForRead(L locker, long timeout, TimeUnit unit)
+ throws InterruptedException
+ {
+ if (Thread.interrupted()) {
+ throw new InterruptedException();
+ }
+ if (!tryLockForRead(locker)) {
+ return lockForReadQueuedInterruptibly(locker, addReadWaiter(), unit.toNanos(timeout));
+ }
+ return true;
+ }
+
+ /**
+ * Release a previously acquired read lock.
+ */
+ public final void unlockFromRead(L locker) {
+ adjustReadLockCount(locker, -1);
+
+ int readLocks;
+ while ((readLocks = decrementReadLocks(mState)) < 0) {}
+
+ if (readLocks == 0) {
+ Node h = mRWHead;
+ if (h != null && h.mWaitStatus != 0) {
+ unparkReadWriteSuccessor(h);
+ }
+ }
+ }
+
+ /**
+ * Acquire an upgrade lock, possibly blocking indefinitely.
+ *
+ * @param locker object trying to become lock owner
+ * @return true if acquired
+ */
+ public final boolean lockForUpgrade(L locker) {
+ return lockForUpgrade_(locker) != Result.FAILED;
+ }
+
+ /**
+ * Acquire an upgrade lock, possibly blocking indefinitely.
+ *
+ * @param locker object trying to become lock owner
+ * @return ACQUIRED or OWNED
+ */
+ private final Result lockForUpgrade_(L locker) {
+ Result result;
+ if ((result = tryLockForUpgrade_(locker)) == Result.FAILED) {
+ result = lockForUpgradeQueued(locker, addUpgradeWaiter());
+ }
+ return result;
+ }
+
+ /**
+ * Acquire an upgrade lock, possibly blocking until interrupted.
+ *
+ * @param locker object trying to become lock owner
+ * @return true if acquired
+ */
+ public final boolean lockForUpgradeInterruptibly(L locker) throws InterruptedException {
+ return lockForUpgradeInterruptibly_(locker) != Result.FAILED;
+ }
+
+ /**
+ * Acquire an upgrade lock, possibly blocking until interrupted.
+ *
+ * @param locker object trying to become lock owner
+ * @return ACQUIRED or OWNED
+ */
+ private final Result lockForUpgradeInterruptibly_(L locker) throws InterruptedException {
+ if (Thread.interrupted()) {
+ throw new InterruptedException();
+ }
+ Result result;
+ if ((result = tryLockForUpgrade_(locker)) == Result.FAILED) {
+ result = lockForUpgradeQueuedInterruptibly(locker, addUpgradeWaiter());
+ }
+ return result;
+ }
+
+ /**
+ * Attempt to immediately acquire an upgrade lock.
+ *
+ * @param locker object trying to become lock owner
+ * @return true if acquired
+ */
+ public final boolean tryLockForUpgrade(L locker) {
+ return tryLockForUpgrade_(locker) != Result.FAILED;
+ }
+
+ /**
+ * Attempt to immediately acquire an upgrade lock.
+ *
+ * @param locker object trying to become lock owner
+ * @return FAILED, ACQUIRED or OWNED
+ */
+ private final Result tryLockForUpgrade_(L locker) {
+ int state = mState;
+ if ((state & LOCK_STATE_MASK) == 0) { // no write or upgrade lock is held
+ if (isUpgradeFirst()) {
+ do {
+ if (setUpgradeLock(state)) {
+ mOwner = locker;
+ incrementUpgradeCount();
+ return Result.ACQUIRED;
+ }
+ // keep looping on CAS failure if a reader mucked with the state
+ } while (((state = mState) & LOCK_STATE_MASK) == 0);
+ }
+ } else if (mOwner == locker) {
+ incrementUpgradeCount();
+ return Result.OWNED;
+ }
+ return Result.FAILED;
+ }
+
+ /**
+ * Attempt to acquire an upgrade lock, waiting a maximum amount of time.
+ *
+ * @param locker object trying to become lock owner
+ * @return true if acquired
+ */
+ public final boolean tryLockForUpgrade(L locker, long timeout, TimeUnit unit)
+ throws InterruptedException
+ {
+ return tryLockForUpgrade_(locker, timeout, unit) != Result.FAILED;
+ }
+
+ /**
+ * Attempt to acquire an upgrade lock, waiting a maximum amount of time.
+ *
+ * @param locker object trying to become lock owner
+ * @return FAILED, ACQUIRED or OWNED
+ */
+ private final Result tryLockForUpgrade_(L locker, long timeout, TimeUnit unit)
+ throws InterruptedException
+ {
+ if (Thread.interrupted()) {
+ throw new InterruptedException();
+ }
+ Result result;
+ if ((result = tryLockForUpgrade_(locker)) == Result.FAILED) {
+ result = lockForUpgradeQueuedInterruptibly(locker, addUpgradeWaiter(),
+ unit.toNanos(timeout));
+ }
+ return result;
+ }
+
+ /**
+ * Release a previously acquired upgrade lock.
+ */
+ public final void unlockFromUpgrade(L locker) {
+ int upgradeCount = mUpgradeCount - 1;
+ if (upgradeCount < 0) {
+ throw new IllegalMonitorStateException("Too many upgrade locks released");
+ }
+ if (upgradeCount == 0 && mWriteCount > 0) {
+ // Don't release last upgrade lock and switch write lock to
+ // automatic upgrade mode.
+ clearUpgradeLock(mState);
+ return;
+ }
+ mUpgradeCount = upgradeCount;
+ if (upgradeCount > 0) {
+ return;
+ }
+
+ mOwner = null;
+
+ // keep looping on CAS failure if reader mucked with state
+ while (!clearUpgradeLock(mState)) {}
+
+ Node h = mUHead;
+ if (h != null && h.mWaitStatus != 0) {
+ unparkUpgradeSuccessor(h);
+ }
+ }
+
+ /**
+ * Acquire an exclusive write lock, possibly blocking indefinitely.
+ *
+ * @param locker object trying to become lock owner
+ */
+ public final void lockForWrite(L locker) {
+ Result writeResult;
+ if (!tryLockForWrite(locker)) {
+ Result upgradeResult = lockForUpgrade_(locker);
+ if (!tryLockForWrite(locker)) {
+ lockForWriteQueued(locker, addWriteWaiter());
+ }
+ if (upgradeResult == Result.ACQUIRED) {
+ // clear upgrade state bit to indicate automatic upgrade
+ while (!clearUpgradeLock(mState)) {}
+ } else {
+ // undo automatic upgrade count increment
+ mUpgradeCount--;
+ }
+ }
+ }
+
+ /**
+ * Acquire an exclusive write lock, possibly blocking until interrupted.
+ *
+ * @param locker object trying to become lock owner
+ */
+ public final void lockForWriteInterruptibly(L locker) throws InterruptedException {
+ if (Thread.interrupted()) {
+ throw new InterruptedException();
+ }
+ if (!tryLockForWrite(locker)) {
+ Result upgradeResult = lockForUpgradeInterruptibly_(locker);
+ if (!tryLockForWrite(locker)) {
+ lockForWriteQueuedInterruptibly(locker, addWriteWaiter());
+ }
+ if (upgradeResult == Result.ACQUIRED) {
+ // clear upgrade state bit to indicate automatic upgrade
+ while (!clearUpgradeLock(mState)) {}
+ } else {
+ // undo automatic upgrade count increment
+ mUpgradeCount--;
+ }
+ }
+ }
+
+ /**
+ * Attempt to immediately acquire an exclusive lock.
+ *
+ * @param locker object trying to become lock owner
+ * @return true if acquired
+ */
+ public final boolean tryLockForWrite(L locker) {
+ int state = mState;
+ if (state == 0) {
+ // no locks are held
+ if (isUpgradeOrReadWriteFirst() && setWriteLock(state)) {
+ // keep upgrade state bit clear to indicate automatic upgrade
+ mOwner = locker;
+ incrementUpgradeCount();
+ incrementWriteCount();
+ return true;
+ }
+ } else if (state == LOCK_STATE_UPGRADE) {
+ // only upgrade lock is held; upgrade to full write lock
+ if (mOwner == locker && setWriteLock(state)) {
+ incrementWriteCount();
+ return true;
+ }
+ } else if (state < 0) {
+ // write lock is held, and upgrade lock might be held too
+ if (mOwner == locker) {
+ incrementWriteCount();
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Attempt to acquire an exclusive lock, waiting a maximum amount of time.
+ *
+ * @param locker object trying to become lock owner
+ * @return true if acquired
+ */
+ public final boolean tryLockForWrite(L locker, long timeout, TimeUnit unit)
+ throws InterruptedException
+ {
+ if (Thread.interrupted()) {
+ throw new InterruptedException();
+ }
+ if (!tryLockForWrite(locker)) {
+ return lockForWriteQueuedInterruptibly(locker, addWriteWaiter(),
+ unit.toNanos(timeout));
+ }
+ return true;
+ }
+
+ /**
+ * Release a previously acquired write lock.
+ */
+ public final void unlockFromWrite(L locker) {
+ int writeCount = mWriteCount - 1;
+ if (writeCount < 0) {
+ throw new IllegalMonitorStateException("Too many write locks released");
+ }
+ mWriteCount = writeCount;
+ if (writeCount > 0) {
+ return;
+ }
+
+ // copy original state to check if upgrade lock was automatic
+ final int state = mState;
+
+ // make sure upgrade lock is still held after releasing write lock
+ mState = LOCK_STATE_UPGRADE;
+
+ Node h = mRWHead;
+ if (h != null && h.mWaitStatus != 0) {
+ unparkReadWriteSuccessor(h);
+ }
+
+ if (state == LOCK_STATE_WRITE) {
+ // upgrade owner was automatically set, so automatically clear it
+ unlockFromUpgrade(locker);
+ }
+ }
+
+ public String toString() {
+ int state = mState;
+ int readLocks = state & ~LOCK_STATE_MASK;
+ int upgradeLocks = mUpgradeCount;
+ int writeLocks = mWriteCount;
+
+ return super.toString()
+ + "[Read locks = " + readLocks
+ + ", Upgrade locks = " + upgradeLocks
+ + ", Write locks = " + writeLocks
+ + ", Owner = " + mOwner
+ + ']';
+ }
+
+ /**
+ * Add or subtract to the count of read locks held for the given
+ * locker. Default implementation does nothing, and so read locks are not
+ * reentrant.
+ *
+ * @throws IllegalMonitorStateException if count overflows or underflows
+ */
+ protected void adjustReadLockCount(L locker, int amount) {
+ }
+
+ /**
+ * Default implementation does nothing and always returns false, and so
+ * read locks are not reentrant. Overridden implementation may choose to
+ * always returns true, in which case read lock requests can starve upgrade
+ * and write lock requests.
+ */
+ protected boolean isReadLockHeld(L locker) {
+ return false;
+ }
+
+ private Node enqForReadWrite(final Node node) {
+ for (;;) {
+ Node t = mRWTail;
+ if (t == null) { // Must initialize
+ Node h = new Node(); // Dummy header
+ h.mNext = node;
+ node.mPrev = h;
+ if (cRWHeadRef.compareAndSet(this, null, h)) {
+ mRWTail = node;
+ return h;
+ }
+ } else {
+ node.mPrev = t;
+ if (cRWTailRef.compareAndSet(this, t, node)) {
+ t.mNext = node;
+ return t;
+ }
+ }
+ }
+ }
+
+ private Node enqForUpgrade(final Node node) {
+ for (;;) {
+ Node t = mUTail;
+ if (t == null) { // Must initialize
+ Node h = new Node(); // Dummy header
+ h.mNext = node;
+ node.mPrev = h;
+ if (cUHeadRef.compareAndSet(this, null, h)) {
+ mUTail = node;
+ return h;
+ }
+ } else {
+ node.mPrev = t;
+ if (cUTailRef.compareAndSet(this, t, node)) {
+ t.mNext = node;
+ return t;
+ }
+ }
+ }
+ }
+
+ private Node addReadWaiter() {
+ return addReadWriteWaiter(true);
+ }
+
+ private Node addWriteWaiter() {
+ return addReadWriteWaiter(false);
+ }
+
+ private Node addReadWriteWaiter(boolean shared) {
+ Node node = new Node(Thread.currentThread(), shared);
+ // Try the fast path of enq; backup to full enq on failure
+ Node pred = mRWTail;
+ if (pred != null) {
+ node.mPrev = pred;
+ if (cRWTailRef.compareAndSet(this, pred, node)) {
+ pred.mNext = node;
+ return node;
+ }
+ }
+ enqForReadWrite(node);
+ return node;
+ }
+
+ private Node addUpgradeWaiter() {
+ Node node = new Node(Thread.currentThread(), false);
+ // Try the fast path of enq; backup to full enq on failure
+ Node pred = mUTail;
+ if (pred != null) {
+ node.mPrev = pred;
+ if (cUTailRef.compareAndSet(this, pred, node)) {
+ pred.mNext = node;
+ return node;
+ }
+ }
+ enqForUpgrade(node);
+ return node;
+ }
+
+ private void setReadWriteHead(Node node) {
+ mRWHead = node;
+ node.mThread = null;
+ node.mPrev = null;
+ }
+
+ private void setUpgradeHead(Node node) {
+ mUHead = node;
+ node.mThread = null;
+ node.mPrev = null;
+ }
+
+ private void unparkReadWriteSuccessor(Node node) {
+ Node.cWaitStatusRef.compareAndSet(node, Node.SIGNAL, 0);
+
+ Node s = node.mNext;
+ if (s == null || s.mWaitStatus > 0) {
+ s = null;
+ for (Node t = mRWTail; t != null && t != node; t = t.mPrev) {
+ if (t.mWaitStatus <= 0) {
+ s = t;
+ }
+ }
+ }
+ if (s != null) {
+ LockSupport.unpark(s.mThread);
+ }
+ }
+
+ private void unparkUpgradeSuccessor(Node node) {
+ Node.cWaitStatusRef.compareAndSet(node, Node.SIGNAL, 0);
+
+ Node s = node.mNext;
+ if (s == null || s.mWaitStatus > 0) {
+ s = null;
+ for (Node t = mUTail; t != null && t != node; t = t.mPrev) {
+ if (t.mWaitStatus <= 0) {
+ s = t;
+ }
+ }
+ }
+ if (s != null) {
+ LockSupport.unpark(s.mThread);
+ }
+ }
+
+ private void setReadWriteHeadAndPropagate(Node node) {
+ setReadWriteHead(node);
+ if (node.mWaitStatus != 0) {
+ Node s = node.mNext;
+ if (s == null || s.mShared) {
+ unparkReadWriteSuccessor(node);
+ }
+ }
+ }
+
+ private void cancelAcquireReadWrite(Node node) {
+ if (node != null) {
+ node.mThread = null;
+ node.mWaitStatus = Node.CANCELLED;
+ unparkReadWriteSuccessor(node);
+ }
+ }
+
+ private void cancelAcquireUpgrade(Node node) {
+ if (node != null) {
+ node.mThread = null;
+ node.mWaitStatus = Node.CANCELLED;
+ unparkUpgradeSuccessor(node);
+ }
+ }
+
+ private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
+ int s = pred.mWaitStatus;
+ if (s < 0) {
+ return true;
+ }
+ if (s > 0) {
+ node.mPrev = pred.mPrev;
+ } else {
+ Node.cWaitStatusRef.compareAndSet(pred, 0, Node.SIGNAL);
+ }
+ return false;
+ }
+
+ private static void selfInterrupt() {
+ Thread.currentThread().interrupt();
+ }
+
+ private final boolean parkAndCheckInterrupt() {
+ LockSupport.park(this);
+ return Thread.interrupted();
+ }
+
+ /**
+ * @return ACQUIRED or OWNED
+ */
+ private final Result lockForUpgradeQueued(L locker, final Node node) {
+ try {
+ boolean interrupted = false;
+ for (;;) {
+ final Node p = node.predecessor();
+ Result result;
+ if (p == mUHead && (result = tryLockForUpgrade_(locker)) != Result.FAILED) {
+ setUpgradeHead(node);
+ p.mNext = null; // help GC
+ if (interrupted) {
+ selfInterrupt();
+ }
+ return result;
+ }
+ if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) {
+ interrupted = true;
+ }
+ }
+ } catch (RuntimeException e) {
+ cancelAcquireUpgrade(node);
+ throw e;
+ }
+ }
+
+ /**
+ * @return ACQUIRED or OWNED
+ */
+ private final Result lockForUpgradeQueuedInterruptibly(L locker, final Node node)
+ throws InterruptedException
+ {
+ try {
+ for (;;) {
+ final Node p = node.predecessor();
+ Result result;
+ if (p == mUHead && (result = tryLockForUpgrade_(locker)) != Result.FAILED) {
+ setUpgradeHead(node);
+ p.mNext = null; // help GC
+ return result;
+ }
+ if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) {
+ break;
+ }
+ }
+ } catch (RuntimeException e) {
+ cancelAcquireUpgrade(node);
+ throw e;
+ }
+ // Arrive here only if interrupted
+ cancelAcquireUpgrade(node);
+ throw new InterruptedException();
+ }
+
+ /**
+ * @return FAILED, ACQUIRED or OWNED
+ */
+ private final Result lockForUpgradeQueuedInterruptibly(L locker, final Node node,
+ long nanosTimeout)
+ throws InterruptedException
+ {
+ long lastTime = System.nanoTime();
+ try {
+ for (;;) {
+ final Node p = node.predecessor();
+ Result result;
+ if (p == mUHead && (result = tryLockForUpgrade_(locker)) != Result.FAILED) {
+ setUpgradeHead(node);
+ p.mNext = null; // help GC
+ return result;
+ }
+ if (nanosTimeout <= 0) {
+ cancelAcquireUpgrade(node);
+ return Result.FAILED;
+ }
+ if (nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD
+ && shouldParkAfterFailedAcquire(p, node))
+ {
+ LockSupport.parkNanos(this, nanosTimeout);
+ }
+ long now = System.nanoTime();
+ nanosTimeout -= now - lastTime;
+ lastTime = now;
+ if (Thread.interrupted()) {
+ break;
+ }
+ }
+ } catch (RuntimeException e) {
+ cancelAcquireUpgrade(node);
+ throw e;
+ }
+ // Arrive here only if interrupted
+ cancelAcquireUpgrade(node);
+ throw new InterruptedException();
+ }
+
+ private final void lockForReadQueued(L locker, final Node node) {
+ try {
+ boolean interrupted = false;
+ for (;;) {
+ final Node p = node.predecessor();
+ if (p == mRWHead && tryLockForRead(locker)) {
+ setReadWriteHeadAndPropagate(node);
+ p.mNext = null; // help GC
+ if (interrupted) {
+ selfInterrupt();
+ }
+ return;
+ }
+ if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) {
+ interrupted = true;
+ }
+ }
+ } catch (RuntimeException e) {
+ cancelAcquireReadWrite(node);
+ throw e;
+ }
+ }
+
+ private final void lockForReadQueuedInterruptibly(L locker, final Node node)
+ throws InterruptedException
+ {
+ try {
+ for (;;) {
+ final Node p = node.predecessor();
+ if (p == mRWHead && tryLockForRead(locker)) {
+ setReadWriteHeadAndPropagate(node);
+ p.mNext = null; // help GC
+ return;
+ }
+ if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) {
+ break;
+ }
+ }
+ } catch (RuntimeException e) {
+ cancelAcquireReadWrite(node);
+ throw e;
+ }
+ // Arrive here only if interrupted
+ cancelAcquireReadWrite(node);
+ throw new InterruptedException();
+ }
+
+ /**
+ * @return true if acquired
+ */
+ private final boolean lockForReadQueuedInterruptibly(L locker, final Node node,
+ long nanosTimeout)
+ throws InterruptedException
+ {
+ long lastTime = System.nanoTime();
+ try {
+ for (;;) {
+ final Node p = node.predecessor();
+ if (p == mRWHead && tryLockForRead(locker)) {
+ setReadWriteHeadAndPropagate(node);
+ p.mNext = null; // help GC
+ return true;
+ }
+ if (nanosTimeout <= 0) {
+ cancelAcquireReadWrite(node);
+ return false;
+ }
+ if (nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD
+ && shouldParkAfterFailedAcquire(p, node))
+ {
+ LockSupport.parkNanos(this, nanosTimeout);
+ }
+ long now = System.nanoTime();
+ nanosTimeout -= now - lastTime;
+ lastTime = now;
+ if (Thread.interrupted()) {
+ break;
+ }
+ }
+ } catch (RuntimeException e) {
+ cancelAcquireReadWrite(node);
+ throw e;
+ }
+ // Arrive here only if interrupted
+ cancelAcquireReadWrite(node);
+ throw new InterruptedException();
+ }
+
+ private final void lockForWriteQueued(L locker, final Node node) {
+ try {
+ boolean interrupted = false;
+ for (;;) {
+ final Node p = node.predecessor();
+ if (p == mRWHead && tryLockForWrite(locker)) {
+ setReadWriteHead(node);
+ p.mNext = null; // help GC
+ if (interrupted) {
+ selfInterrupt();
+ }
+ return;
+ }
+ if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) {
+ interrupted = true;
+ }
+ }
+ } catch (RuntimeException e) {
+ cancelAcquireReadWrite(node);
+ throw e;
+ }
+ }
+
+ private final void lockForWriteQueuedInterruptibly(L locker, final Node node)
+ throws InterruptedException
+ {
+ try {
+ for (;;) {
+ final Node p = node.predecessor();
+ if (p == mRWHead && tryLockForWrite(locker)) {
+ setReadWriteHead(node);
+ p.mNext = null; // help GC
+ return;
+ }
+ if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) {
+ break;
+ }
+ }
+ } catch (RuntimeException e) {
+ cancelAcquireReadWrite(node);
+ throw e;
+ }
+ // Arrive here only if interrupted
+ cancelAcquireReadWrite(node);
+ throw new InterruptedException();
+ }
+
+ /**
+ * @return true if acquired
+ */
+ private final boolean lockForWriteQueuedInterruptibly(L locker, final Node node,
+ long nanosTimeout)
+ throws InterruptedException
+ {
+ long lastTime = System.nanoTime();
+ try {
+ for (;;) {
+ final Node p = node.predecessor();
+ if (p == mRWHead && tryLockForWrite(locker)) {
+ setReadWriteHead(node);
+ p.mNext = null; // help GC
+ return true;
+ }
+ if (nanosTimeout <= 0) {
+ cancelAcquireReadWrite(node);
+ return false;
+ }
+ if (nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD
+ && shouldParkAfterFailedAcquire(p, node))
+ {
+ LockSupport.parkNanos(this, nanosTimeout);
+ }
+ long now = System.nanoTime();
+ nanosTimeout -= now - lastTime;
+ lastTime = now;
+ if (Thread.interrupted()) {
+ break;
+ }
+ }
+ } catch (RuntimeException e) {
+ cancelAcquireReadWrite(node);
+ throw e;
+ }
+ // Arrive here only if interrupted
+ cancelAcquireReadWrite(node);
+ throw new InterruptedException();
+ }
+
+ private final boolean isReadWriteFirst() {
+ Node h;
+ if ((h = mRWHead) == null) {
+ return true;
+ }
+ Thread current = Thread.currentThread();
+ Node s;
+ return ((s = h.mNext) != null && s.mThread == current) || fullIsReadWriteFirst(current);
+ }
+
+ private final boolean fullIsReadWriteFirst(Thread current) {
+ Node h, s;
+ Thread firstThread = null;
+ if (((h = mRWHead) != null && (s = h.mNext) != null &&
+ s.mPrev == mRWHead && (firstThread = s.mThread) != null))
+ {
+ return firstThread == current;
+ }
+ Node t = mRWTail;
+ while (t != null && t != mRWHead) {
+ Thread tt = t.mThread;
+ if (tt != null) {
+ firstThread = tt;
+ }
+ t = t.mPrev;
+ }
+ return firstThread == current || firstThread == null;
+ }
+
+ private final boolean isUpgradeFirst() {
+ Node h;
+ if ((h = mUHead) == null) {
+ return true;
+ }
+ Thread current = Thread.currentThread();
+ Node s;
+ return ((s = h.mNext) != null && s.mThread == current) || fullIsUpgradeFirst(current);
+ }
+
+ private final boolean fullIsUpgradeFirst(Thread current) {
+ Node h, s;
+ Thread firstThread = null;
+ if (((h = mUHead) != null && (s = h.mNext) != null &&
+ s.mPrev == mUHead && (firstThread = s.mThread) != null))
+ {
+ return firstThread == current;
+ }
+ Node t = mUTail;
+ while (t != null && t != mUHead) {
+ Thread tt = t.mThread;
+ if (tt != null) {
+ firstThread = tt;
+ }
+ t = t.mPrev;
+ }
+ return firstThread == current || firstThread == null;
+ }
+
+ private final boolean isUpgradeOrReadWriteFirst() {
+ Node uh, rwh;
+ if ((uh = mUHead) == null || (rwh = mRWHead) == null) {
+ return true;
+ }
+ Thread current = Thread.currentThread();
+ Node us, rws;
+ return ((us = uh.mNext) != null && us.mThread == current)
+ || ((rws = rwh.mNext) != null && rws.mThread == current)
+ || fullIsUpgradeFirst(current)
+ || fullIsReadWriteFirst(current);
+ }
+
+ /**
+ * @return false if state changed
+ */
+ private boolean incrementReadLocks(int state) {
+ int readLocks = (state & ~LOCK_STATE_MASK) + 1;
+ if (readLocks == LOCK_STATE_MASK) {
+ throw new IllegalMonitorStateException("Maximum read lock count exceeded");
+ }
+ return cStateRef.compareAndSet(this, state, state & LOCK_STATE_MASK | readLocks);
+ }
+
+ /**
+ * @return number of remaining read locks or negative if concurrent
+ * modification prevented operation
+ */
+ private int decrementReadLocks(int state) {
+ int readLocks = (state & ~LOCK_STATE_MASK) - 1;
+ if (readLocks < 0) {
+ throw new IllegalMonitorStateException("Too many read locks released");
+ }
+ if (cStateRef.compareAndSet(this, state, state & LOCK_STATE_MASK | readLocks)) {
+ return readLocks;
+ }
+ return -1;
+ }
+
+ /**
+ * @return false if concurrent modification prevented operation
+ */
+ private boolean setUpgradeLock(int state) {
+ return cStateRef.compareAndSet(this, state, state | LOCK_STATE_UPGRADE);
+ }
+
+ /**
+ * @return false if concurrent modification prevented operation
+ */
+ private boolean clearUpgradeLock(int state) {
+ return cStateRef.compareAndSet(this, state, state & ~LOCK_STATE_UPGRADE);
+ }
+
+ private void incrementUpgradeCount() {
+ int upgradeCount = mUpgradeCount + 1;
+ if (upgradeCount < 0) {
+ throw new IllegalMonitorStateException("Maximum upgrade lock count exceeded");
+ }
+ mUpgradeCount = upgradeCount;
+ }
+
+ /**
+ * @return false if concurrent modification prevented operation
+ */
+ private boolean setWriteLock(int state) {
+ return cStateRef.compareAndSet(this, state, state | LOCK_STATE_WRITE);
+ }
+
+ private void incrementWriteCount() {
+ int writeCount = mWriteCount + 1;
+ if (writeCount < 0) {
+ throw new IllegalMonitorStateException("Maximum write lock count exceeded");
+ }
+ mWriteCount = writeCount;
+ }
+
+ /**
+ * Node class ripped off from AbstractQueuedSynchronizer and modified
+ * slightly. Read the comments in that class for better understanding.
+ */
+ static final class Node {
+ static final AtomicIntegerFieldUpdater<Node> cWaitStatusRef =
+ AtomicIntegerFieldUpdater.newUpdater(Node.class, "mWaitStatus");
+
+ static final int CANCELLED = 1;
+ static final int SIGNAL = -1;
+
+ volatile int mWaitStatus;
+ volatile Node mPrev;
+ volatile Node mNext;
+ volatile Thread mThread;
+
+ final boolean mShared;
+
+ // Used to establish initial head
+ Node() {
+ mShared = false;
+ }
+
+ Node(Thread thread, boolean shared) {
+ mThread = thread;
+ mShared = shared;
+ }
+
+ final Node predecessor() throws NullPointerException {
+ Node p = mPrev;
+ if (p == null) {
+ throw new NullPointerException();
+ } else {
+ return p;
+ }
+ }
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/map/package-info.java b/src/main/java/com/amazon/carbonado/repo/map/package-info.java
new file mode 100644
index 0000000..b386251
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/map/package-info.java
@@ -0,0 +1,24 @@
+/*
+ * Copyright 2008 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/**
+ * Volatile repository implementation backed by a concurrent map.
+ *
+ * @see com.amazon.carbonado.repo.map.MapRepositoryBuilder
+ */
+package com.amazon.carbonado.repo.map;
--
cgit v1.2.3