- this(newRootNode(), equiv, false);
- }
-
- public TrieMap() {
- this(Equivalence.equals());
- }
-
- /* internal methods */
-
- final Equivalence<? super K> equiv() {
- return equiv;
- }
-
- private static <K,V> INode<K, V> newRootNode() {
- final Gen gen = new Gen();
- return new INode<>(gen, new CNode<>(gen));
- }
-
- private boolean CAS_ROOT(final Object ov, final Object nv) {
- checkState(!readOnly, "Attempted to modify a read-only snapshot");
- return ROOT_UPDATER.compareAndSet(this, ov, nv);
- }
-
- final INode<K, V> readRoot() {
- return RDCSS_READ_ROOT(false);
- }
-
- // FIXME: abort = false by default
- final INode<K, V> readRoot(final boolean abort) {
- return RDCSS_READ_ROOT(abort);
- }
-
- private final INode<K, V> RDCSS_READ_ROOT() {
- return RDCSS_READ_ROOT(false);
- }
-
- private final INode<K, V> RDCSS_READ_ROOT(final boolean abort) {
- final Object r = /* READ */ root;
- if (r instanceof INode) {
- return (INode<K, V>) r;
- }
-
- checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r);
- return RDCSS_Complete(abort);
- }
-
- private INode<K, V> RDCSS_Complete(final boolean abort) {
- while (true) {
- final Object r = /* READ */ root;
- if (r instanceof INode) {
- return (INode<K, V>) r;
- }
-
- checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r);
- @SuppressWarnings("unchecked")
- final RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) r;
- final INode<K, V> ov = desc.old;
- final MainNode<K, V> exp = desc.expectedmain;
- final INode<K, V> nv = desc.nv;
-
- if (abort) {
- if (CAS_ROOT(desc, ov)) {
- return ov;
- }
-
- // Tail recursion: return RDCSS_Complete(abort);
- continue;
- }
-
- final MainNode<K, V> oldmain = ov.gcasRead(this);
- if (oldmain == exp) {
- if (CAS_ROOT(desc, nv)) {
- desc.committed = true;
- return nv;
- }
-
- // Tail recursion: return RDCSS_Complete(abort);
- continue;
- }
-
- if (CAS_ROOT(desc, ov)) {
- return ov;
- }
-
- // Tail recursion: return RDCSS_Complete(abort);
- }
- }
-
- private boolean RDCSS_ROOT(final INode<K, V> ov, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
- final RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<> (ov, expectedmain, nv);
- if (CAS_ROOT(ov, desc)) {
- RDCSS_Complete(false);
- return /* READ */desc.committed;
- }
-
- return false;
- }
-
- private void inserthc(final K k, final int hc, final V v) {
- // TODO: this is called from serialization only, which means we should not be observing any races,
- // hence we should not need to pass down the entire tree, just equality (I think).
- final boolean success = RDCSS_READ_ROOT().rec_insert(k, v, hc, 0, null, this);
- Verify.verify(success, "Concurrent modification during serialization of map %s", this);
- }
-
- void add(final K key, final V value) {
- final K k = checkNotNull(key);
- inserthc(k, computeHash(k), checkNotNull(value));
- }
-
- private Optional<V> insertifhc(final K k, final int hc, final V v, final Object cond) {
- Optional<V> res;
- do {
- // Keep looping as long as we do not get a reply
- res = RDCSS_READ_ROOT().rec_insertif(k, v, hc, cond, 0, null, this);
- } while (res == null);
-
- return res;
- }
-
- @SuppressWarnings("unchecked")
- private V lookuphc(final K k, final int hc) {
- Object res;
- do {
- // Keep looping as long as RESTART is being indicated
- res = RDCSS_READ_ROOT().rec_lookup(k, hc, 0, null, this);
- } while (res == RESTART);
-
- return (V) res;
- }
-
- private Optional<V> removehc(final K k, final Object cond, final int hc) {
- Optional<V> res;
- do {
- // Keep looping as long as we do not get a reply
- res = RDCSS_READ_ROOT().rec_remove(k, cond, hc, 0, null, this);
- } while (res == null);
-
- return res;
- }
-
- /**
- * Ensure this instance is read-write, throw UnsupportedOperationException
- * otherwise. Used by Map-type methods for quick check.
- */
- private void ensureReadWrite() {
- if (readOnly) {
- throw new UnsupportedOperationException("Attempted to modify a read-only view");
- }