Repository: groovy Updated Branches: refs/heads/master 582ecf4e1 -> b88379785
Add `computeIfAbsent` to `ConcurrentLinkedHashMap` Project: http://git-wip-us.apache.org/repos/asf/groovy/repo Commit: http://git-wip-us.apache.org/repos/asf/groovy/commit/b8837978 Tree: http://git-wip-us.apache.org/repos/asf/groovy/tree/b8837978 Diff: http://git-wip-us.apache.org/repos/asf/groovy/diff/b8837978 Branch: refs/heads/master Commit: b883797852e0a66c500571512486b16006dbfbcd Parents: 582ecf4 Author: sunlan <[email protected]> Authored: Mon Jan 8 13:16:41 2018 +0800 Committer: sunlan <[email protected]> Committed: Mon Jan 8 13:16:41 2018 +0800 ---------------------------------------------------------------------- .../ConcurrentLinkedHashMap.java | 90 ++++++++++++++++++++ .../ConcurrentLinkedHashMapTest.java | 49 +++++++++++ 2 files changed, 139 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/groovy/blob/b8837978/src/main/java/org/apache/groovy/util/concurrentlinkedhashmap/ConcurrentLinkedHashMap.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/groovy/util/concurrentlinkedhashmap/ConcurrentLinkedHashMap.java b/src/main/java/org/apache/groovy/util/concurrentlinkedhashmap/ConcurrentLinkedHashMap.java index 938ef63..0828e9b 100644 --- a/src/main/java/org/apache/groovy/util/concurrentlinkedhashmap/ConcurrentLinkedHashMap.java +++ b/src/main/java/org/apache/groovy/util/concurrentlinkedhashmap/ConcurrentLinkedHashMap.java @@ -40,6 +40,7 @@ import java.util.concurrent.atomic.AtomicLong; import java.util.concurrent.atomic.AtomicReference; import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReentrantLock; +import java.util.function.Function; import static java.util.Collections.emptyList; import static java.util.Collections.unmodifiableMap; @@ -749,6 +750,89 @@ public final class ConcurrentLinkedHashMap<K, V> extends AbstractMap<K, V> } @Override + public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { + return compute(key, mappingFunction, true); + } + + V compute(final K key, final Function<? super K, ? extends V> mappingFunction, boolean onlyIfAbsent) { + checkNotNull(key); + + final NodeHolder<K, V> nh = new NodeHolder<K, V>(); + + for (;;) { + Function<K, Node<K, V>> f = k -> { + final V value = mappingFunction.apply(key); + + checkNotNull(value); + + final int weight = weigher.weightOf(key, value); + final WeightedValue<V> weightedValue = new WeightedValue<V>(value, weight); + final Node<K, V> node = new Node<K, V>(key, weightedValue); + + nh.setNode(node); + + return node; + }; + Node<K, V> prior = data.computeIfAbsent(key, f); + + Node<K, V> node = nh.getNode(); + if (null == node) { + f.apply(key); + node = nh.getNode(); + } else { + // the return value of `computeIfAbsent` is different from the one of `putIfAbsent`. + // if the key is absent in map, the return value of `computeIfAbsent` is the newly computed value, but `putIfAbsent` return null. + // prior should keep the value with the same meaning of the return value of `putIfAbsent`, so reset it as null here. + prior = null; + } + final WeightedValue<V> weightedValue = node.weightedValue; + final int weight = weightedValue.weight; + + if (prior == null) { + afterWrite(new AddTask(node, weight)); + return weightedValue.value; + } else if (onlyIfAbsent) { + afterRead(prior); + return prior.getValue(); + } + for (;;) { + final WeightedValue<V> oldWeightedValue = prior.get(); + if (!oldWeightedValue.isAlive()) { + break; + } + + if (prior.compareAndSet(oldWeightedValue, weightedValue)) { + final int weightedDifference = weight - oldWeightedValue.weight; + if (weightedDifference == 0) { + afterRead(prior); + } else { + afterWrite(new UpdateTask(prior, weightedDifference)); + } + return oldWeightedValue.value; + } + } + } + } + + private static class NodeHolder<K, V> { + private Node<K, V> node; + + public NodeHolder() {} + + public NodeHolder(Node<K, V> node) { + this.node = node; + } + + public Node<K, V> getNode() { + return node; + } + + public void setNode(Node<K, V> node) { + this.node = node; + } + } + + @Override public V remove(Object key) { final Node<K, V> node = data.remove(key); if (node == null) { @@ -1142,11 +1226,13 @@ public final class ConcurrentLinkedHashMap<K, V> extends AbstractMap<K, V> Node<K, V> prev; @GuardedBy("evictionLock") Node<K, V> next; + WeightedValue<V> weightedValue; /** Creates a new, unlinked node. */ Node(K key, WeightedValue<V> weightedValue) { super(weightedValue); this.key = key; + this.weightedValue = weightedValue; } @Override @@ -1177,6 +1263,10 @@ public final class ConcurrentLinkedHashMap<K, V> extends AbstractMap<K, V> V getValue() { return get().value; } + + WeightedValue<V> getWeightedValue() { + return this.weightedValue; + } } /** An adapter to safely externalize the keys. */ http://git-wip-us.apache.org/repos/asf/groovy/blob/b8837978/src/test/java/org/apache/groovy/util/concurrentlinkedhashmap/ConcurrentLinkedHashMapTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/groovy/util/concurrentlinkedhashmap/ConcurrentLinkedHashMapTest.java b/src/test/java/org/apache/groovy/util/concurrentlinkedhashmap/ConcurrentLinkedHashMapTest.java new file mode 100644 index 0000000..465d071 --- /dev/null +++ b/src/test/java/org/apache/groovy/util/concurrentlinkedhashmap/ConcurrentLinkedHashMapTest.java @@ -0,0 +1,49 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you 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 org.apache.groovy.util.concurrentlinkedhashmap; + +import org.junit.Test; + +import static org.junit.Assert.assertArrayEquals; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertNull; + +public class ConcurrentLinkedHashMapTest { + @Test + public void computeIfAbsent() { + ConcurrentLinkedHashMap m = new ConcurrentLinkedHashMap.Builder<>() + .maximumWeightedCapacity(3) + .build(); + + assertEquals(1, m.computeIfAbsent("a", k -> 1)); + assertEquals(1, m.computeIfAbsent("a", k -> 2)); + + assertEquals(1, m.get("a")); + + assertEquals(3, m.computeIfAbsent("b", k -> 3)); + assertEquals(4, m.computeIfAbsent("c", k -> 4)); + assertEquals(5, m.computeIfAbsent("d", k -> 5)); + assertEquals(5, m.computeIfAbsent("d", k -> 6)); + + assertArrayEquals(new String[] {"b", "c", "d"}, m.keySet().toArray(new String[0])); + assertArrayEquals(new Integer[] {3, 4, 5}, m.values().toArray(new Integer[0])); + } + +} \ No newline at end of file
