You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@groovy.apache.org by su...@apache.org on 2020/07/10 05:28:40 UTC
[groovy] branch GROOVY-9631 updated: Add `AbstractConcurrentMap`
and `AbstractConcurrentMapBase` back for binary compatibility
This is an automated email from the ASF dual-hosted git repository.
sunlan pushed a commit to branch GROOVY-9631
in repository https://gitbox.apache.org/repos/asf/groovy.git
The following commit(s) were added to refs/heads/GROOVY-9631 by this push:
new 20da422 Add `AbstractConcurrentMap` and `AbstractConcurrentMapBase` back for binary compatibility
20da422 is described below
commit 20da422a41fd532f135fd6c5e5c5c89f586dfaa7
Author: Daniel Sun <su...@apache.org>
AuthorDate: Fri Jul 10 13:26:49 2020 +0800
Add `AbstractConcurrentMap` and `AbstractConcurrentMapBase` back for binary compatibility
---
.../groovy/util/AbstractConcurrentMap.java | 208 +++++++++++++
.../groovy/util/AbstractConcurrentMapBase.java | 337 +++++++++++++++++++++
.../util/AbstractConcurrentMapSegmentTest.groovy | 194 ++++++++++++
3 files changed, 739 insertions(+)
diff --git a/src/main/java/org/codehaus/groovy/util/AbstractConcurrentMap.java b/src/main/java/org/codehaus/groovy/util/AbstractConcurrentMap.java
new file mode 100644
index 0000000..d67fd88
--- /dev/null
+++ b/src/main/java/org/codehaus/groovy/util/AbstractConcurrentMap.java
@@ -0,0 +1,208 @@
+/*
+ * 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.codehaus.groovy.util;
+
+@Deprecated
+public abstract class AbstractConcurrentMap<K, V> extends AbstractConcurrentMapBase {
+
+ public AbstractConcurrentMap(Object segmentInfo) {
+ super(segmentInfo);
+ }
+
+ public Segment segmentFor (int hash) {
+ return (Segment) super.segmentFor(hash);
+ }
+
+ public V get(K key) {
+ int hash = hash(key);
+ return (V) segmentFor(hash).get(key, hash);
+ }
+
+ public Entry<K,V> getOrPut(K key, V value) {
+ int hash = hash(key);
+ return segmentFor(hash).getOrPut(key, hash, value);
+ }
+
+ public void put(K key, V value) {
+ int hash = hash(key);
+ segmentFor(hash).put(key, hash, value);
+ }
+
+ public void remove(K key) {
+ int hash = hash(key);
+ segmentFor(hash).remove(key, hash);
+ }
+
+ public abstract static class Segment<K,V> extends AbstractConcurrentMapBase.Segment {
+
+ private static final long serialVersionUID = -2392526467736920612L;
+
+ protected Segment(int initialCapacity) {
+ super(initialCapacity);
+ }
+
+ public final V get(K key, int hash) {
+ Object[] tab = table;
+ Object o = tab[hash & (tab.length - 1)];
+ if (o != null) {
+ if (o instanceof Entry) {
+ Entry<K,V> e = (Entry) o;
+ if (e.isEqual(key, hash)) {
+ return e.getValue();
+ }
+ }
+ else {
+ Object[] arr = (Object[]) o;
+ for (Object value : arr) {
+ Entry<K, V> e = (Entry<K, V>) value;
+ if (e != null && e.isEqual(key, hash)) {
+ return e.getValue();
+ }
+ }
+ }
+ }
+ return null;
+ }
+
+ public final Entry<K,V> getOrPut(K key, int hash, V value) {
+ Object[] tab = table;
+ Object o = tab[hash & (tab.length - 1)];
+ if (o != null) {
+ if (o instanceof Entry) {
+ Entry<K,V> e = (Entry) o;
+ if (e.isEqual(key, hash)) {
+ return e;
+ }
+ }
+ else {
+ Object[] arr = (Object[]) o;
+ for (Object item : arr) {
+ Entry<K, V> e = (Entry<K, V>) item;
+ if (e != null && e.isEqual(key, hash)) {
+ return e;
+ }
+ }
+ }
+ }
+ return put(key, hash, value);
+ }
+
+ public final Entry put(K key, int hash, V value) {
+ lock();
+ try {
+ rehashIfThresholdExceeded();
+
+ Object[] tab = table;
+ int index = hash & (tab.length - 1);
+ Object o = tab[index];
+ if (o != null) {
+ if (o instanceof Entry) {
+ Entry e = (Entry) o;
+ if (e.isEqual(key, hash)) {
+ e.setValue(value);
+ return e;
+ }
+ else {
+ Object[] arr = new Object [2];
+ final Entry ee = createEntry(key, hash, value);
+ arr [0] = ee;
+ arr [1] = e;
+ tab[index] = arr;
+ count++;
+ return ee;
+ }
+ }
+ else {
+ Object[] arr = (Object[]) o;
+ for (Object item : arr) {
+ Entry e = (Entry) item;
+ if (e != null && e.isEqual(key, hash)) {
+ e.setValue(value);
+ return e;
+ }
+ }
+
+ final Entry ee = createEntry(key, hash, value);
+ for (int i = 0; i < arr.length; i++) {
+ Entry e = (Entry) arr[i];
+ if (e == null) {
+ arr [i] = ee;
+ count++;
+ return ee;
+ }
+ }
+
+ Object[] newArr = new Object[arr.length+1];
+ newArr [0] = ee;
+ System.arraycopy(arr, 0, newArr, 1, arr.length);
+ tab [index] = newArr;
+ count++;
+ return ee;
+ }
+ }
+
+ Entry e = createEntry(key, hash, value);
+ tab[index] = e;
+ count++; // write-volatile
+ return e;
+ } finally {
+ unlock();
+ }
+ }
+
+ public void remove(K key, int hash) {
+ lock();
+ try {
+ int c = count-1;
+ final Object[] tab = table;
+ final int index = hash & (tab.length - 1);
+ Object o = tab[index];
+
+ if (o != null) {
+ if (o instanceof Entry) {
+ if (((Entry<K,V>)o).isEqual(key, hash)) {
+ tab[index] = null;
+ count = c;
+ }
+ }
+ else {
+ Object[] arr = (Object[]) o;
+ for (int i = 0; i < arr.length; i++) {
+ Entry<K,V> e = (Entry<K,V>) arr[i];
+ if (e != null && e.isEqual(key, hash)) {
+ arr [i] = null;
+ count = c;
+ break;
+ }
+ }
+ }
+ }
+ }
+ finally {
+ unlock();
+ }
+ }
+
+ protected abstract Entry<K,V> createEntry(K key, int hash, V value);
+ }
+
+ public interface Entry<K, V> extends AbstractConcurrentMapBase.Entry<V>{
+ boolean isEqual(K key, int hash);
+ }
+}
diff --git a/src/main/java/org/codehaus/groovy/util/AbstractConcurrentMapBase.java b/src/main/java/org/codehaus/groovy/util/AbstractConcurrentMapBase.java
new file mode 100644
index 0000000..57ac68e
--- /dev/null
+++ b/src/main/java/org/codehaus/groovy/util/AbstractConcurrentMapBase.java
@@ -0,0 +1,337 @@
+/*
+ * 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.codehaus.groovy.util;
+
+import java.util.Collection;
+import java.util.LinkedList;
+
+@Deprecated
+public abstract class AbstractConcurrentMapBase {
+ protected static final int MAXIMUM_CAPACITY = 1 << 30;
+ static final int MAX_SEGMENTS = 1 << 16;
+ static final int RETRIES_BEFORE_LOCK = 2;
+ final int segmentMask;
+ final int segmentShift;
+ protected final Segment[] segments;
+
+ public AbstractConcurrentMapBase(Object segmentInfo) {
+ int sshift = 0;
+ int ssize = 1;
+ while (ssize < 16) {
+ ++sshift;
+ ssize <<= 1;
+ }
+ segmentShift = 32 - sshift;
+ segmentMask = ssize - 1;
+ this.segments = new Segment[ssize];
+
+ int c = 512 / ssize;
+ if (c * ssize < 512)
+ ++c;
+ int cap = 1;
+ while (cap < c)
+ cap <<= 1;
+
+ for (int i = 0; i < this.segments.length; ++i)
+ this.segments[i] = createSegment(segmentInfo, cap);
+ }
+
+ protected abstract Segment createSegment(Object segmentInfo, int cap);
+
+ protected static <K> int hash(K key) {
+ int h = System.identityHashCode(key);
+ h += ~(h << 9);
+ h ^= (h >>> 14);
+ h += (h << 4);
+ h ^= (h >>> 10);
+ return h;
+ }
+
+ public Segment segmentFor(int hash) {
+ return segments[(hash >>> segmentShift) & segmentMask];
+ }
+
+ public int fullSize() {
+ int count = 0;
+ for (Segment segment : segments) {
+ segment.lock();
+ try {
+ for (int j = 0; j < segment.table.length; j++) {
+ Object o = segment.table[j];
+ if (o != null) {
+ if (o instanceof Entry) {
+ count++;
+ } else {
+ Object[] arr = (Object[]) o;
+ count += arr.length;
+ }
+ }
+ }
+ } finally {
+ segment.unlock();
+ }
+ }
+ return count;
+ }
+
+ public int size() {
+ int count = 0;
+ for (Segment segment : segments) {
+ segment.lock();
+ try {
+ for (int j = 0; j < segment.table.length; j++) {
+ Object o = segment.table[j];
+ if (o != null) {
+ if (o instanceof Entry) {
+ Entry e = (Entry) o;
+ if (e.isValid())
+ count++;
+ } else {
+ Object[] arr = (Object[]) o;
+ for (Object value : arr) {
+ Entry info = (Entry) value;
+ if (info != null && info.isValid())
+ count++;
+ }
+ }
+ }
+ }
+ } finally {
+ segment.unlock();
+ }
+ }
+ return count;
+ }
+
+ public Collection values() {
+ Collection result = new LinkedList();
+ for (Segment segment : segments) {
+ segment.lock();
+ try {
+ for (int j = 0; j < segment.table.length; j++) {
+ Object o = segment.table[j];
+ if (o != null) {
+ if (o instanceof Entry) {
+ Entry e = (Entry) o;
+ if (e.isValid())
+ result.add(e);
+ } else {
+ Object[] arr = (Object[]) o;
+ for (Object value : arr) {
+ Entry info = (Entry) value;
+ if (info != null && info.isValid())
+ result.add(info);
+ }
+ }
+ }
+ }
+ } finally {
+ segment.unlock();
+ }
+ }
+ return result;
+ }
+
+ public static class Segment extends LockableObject {
+ private static final long serialVersionUID = -4128828550135386431L;
+ volatile int count;
+
+ int threshold;
+
+ protected volatile Object[] table;
+
+ protected Segment(int initialCapacity) {
+ setTable(new Object[initialCapacity]);
+ }
+
+ void setTable(Object[] newTable) {
+ threshold = (int) (newTable.length * 0.75f);
+ table = newTable;
+ }
+
+ void removeEntry (Entry e) {
+ lock ();
+ int newCount = count;
+ try {
+ Object [] tab = table;
+ int index = e.getHash() & (tab.length-1);
+ Object o = tab[index];
+ if (o != null) {
+ if (o instanceof Entry) {
+ if (o == e) {
+ tab [index] = null;
+ newCount--;
+ }
+ }
+ else {
+ Object[] arr = (Object[]) o;
+ Object res = null;
+ for (Object value : arr) {
+ Entry info = (Entry) value;
+ if (info != null) {
+ if (info != e) {
+ if (info.isValid()) {
+ res = put(info, res);
+ } else {
+ newCount--;
+ }
+ } else {
+ newCount--;
+ }
+ }
+ }
+ tab [index] = res;
+ }
+ count = newCount;
+ }
+ }
+ finally {
+ unlock();
+ }
+ }
+
+ void rehashIfThresholdExceeded() {
+ if(count > threshold) {
+ rehash();
+ }
+ }
+
+ void rehash() {
+ Object[] oldTable = table;
+ int oldCapacity = oldTable.length;
+ if (oldCapacity >= MAXIMUM_CAPACITY)
+ return;
+
+ int newCount = 0;
+ for (int i = 0; i < oldCapacity ; i++) {
+ Object o = oldTable [i];
+ if (o != null) {
+ if (o instanceof Entry) {
+ Entry e = (Entry) o;
+ if (e.isValid()) {
+ newCount++;
+ }
+ else {
+ oldTable[i] = null;
+ }
+ }
+ else {
+ Object[] arr = (Object[]) o;
+ int localCount = 0;
+ for (int index = 0; index < arr.length; index++) {
+ Entry e = (Entry) arr[index];
+ if (e != null && e.isValid()) {
+ localCount++;
+ }
+ else {
+ arr [index] = null;
+ }
+ }
+ if (localCount == 0)
+ oldTable[i] = null;
+ else
+ newCount += localCount;
+ }
+ }
+ }
+
+ Object[] newTable = new Object[newCount+1 < threshold ? oldCapacity : oldCapacity << 1];
+ int sizeMask = newTable.length - 1;
+ newCount = 0;
+ for (Object o : oldTable) {
+ if (o != null) {
+ if (o instanceof Entry) {
+ Entry e = (Entry) o;
+ if (e.isValid()) {
+ int index = e.getHash() & sizeMask;
+ put(e, index, newTable);
+ newCount++;
+ }
+ } else {
+ Object[] arr = (Object[]) o;
+ for (Object value : arr) {
+ Entry e = (Entry) value;
+ if (e != null && e.isValid()) {
+ int index = e.getHash() & sizeMask;
+ put(e, index, newTable);
+ newCount++;
+ }
+ }
+ }
+ }
+ }
+
+ threshold = (int)(newTable.length * 0.75f);
+
+ table = newTable;
+ count = newCount;
+ }
+
+ private static void put(Entry ee, int index, Object[] tab) {
+ Object o = tab[index];
+ if (o != null) {
+ if (o instanceof Entry) {
+ Object[] arr = new Object [2];
+ arr [0] = ee;
+ arr [1] = o;
+ tab[index] = arr;
+ return;
+ }
+ else {
+ Object[] arr = (Object[]) o;
+ Object[] newArr = new Object[arr.length+1];
+ newArr [0] = ee;
+ System.arraycopy(arr, 0, newArr, 1, arr.length);
+ tab [index] = newArr;
+ return;
+ }
+ }
+ tab[index] = ee;
+ }
+
+ private static Object put(Entry ee, Object o) {
+ if (o != null) {
+ if (o instanceof Entry) {
+ Object[] arr = new Object [2];
+ arr [0] = ee;
+ arr [1] = o;
+ return arr;
+ }
+ else {
+ Object[] arr = (Object[]) o;
+ Object[] newArr = new Object[arr.length+1];
+ newArr [0] = ee;
+ System.arraycopy(arr, 0, newArr, 1, arr.length);
+ return newArr;
+ }
+ }
+ return ee;
+ }
+ }
+
+ public interface Entry<V> {
+ V getValue();
+
+ void setValue(V value);
+
+ int getHash();
+
+ boolean isValid();
+ }
+}
diff --git a/src/test/org/codehaus/groovy/util/AbstractConcurrentMapSegmentTest.groovy b/src/test/org/codehaus/groovy/util/AbstractConcurrentMapSegmentTest.groovy
new file mode 100644
index 0000000..1706715
--- /dev/null
+++ b/src/test/org/codehaus/groovy/util/AbstractConcurrentMapSegmentTest.groovy
@@ -0,0 +1,194 @@
+/*
+ * 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.codehaus.groovy.util
+
+import org.junit.Before
+import org.junit.Test
+
+@Deprecated
+class AbstractConcurrentMapSegmentTest {
+ private static final Integer INITIAL_SEGMENT_SIZE = 100
+ private static final Integer SEGMENT_THRESHOLD = 0.75f * INITIAL_SEGMENT_SIZE
+
+ // Incrementing counter used to generate unique key names for TestEntry objects
+ // across all test methods in this class
+ private static int keyId
+
+ TestSegment segment
+ List<TestEntry> entries = []
+ int rehashCount = 0
+
+ @Before
+ public void setUp() throws Exception {
+ segment = new TestSegment(INITIAL_SEGMENT_SIZE)
+ }
+
+ @Test
+ public void testSegmentWillNotRehash() {
+ whenIAddElements(50)
+ thenRehashHappenedTimes(0)
+ thenSegmentExpands(false)
+ }
+
+ @Test
+ public void testSegmentWillNotRehashEdgeCase() {
+ whenIAddElements(SEGMENT_THRESHOLD + 1)
+ thenRehashHappenedTimes(0)
+ thenSegmentExpands(false)
+ }
+
+ @Test
+ public void testSegmentWillRehashAndExpand() {
+ whenIAddElements(SEGMENT_THRESHOLD + 2)
+ thenRehashHappenedTimes(1)
+ thenSegmentExpands(true)
+ }
+
+ @Test
+ public void testSegmentWillRehashAndExpandManyTimes() {
+ int elementCount = (SEGMENT_THRESHOLD + 1 ) * 6
+ whenIAddElements(elementCount)
+ //456 elements fit into segment of size 800, which is 100 * 2 * 2 * 2
+ thenSegmentSizeIs(INITIAL_SEGMENT_SIZE * 2 * 2 * 2)
+ thenRehashHappenedTimes(3)
+ }
+
+ @Test
+ public void testSegmentWillRehashWithNoExpansion() {
+ whenIAddElements(SEGMENT_THRESHOLD)
+ whenISetElementsAsInvalid(50)
+ whenIAddElements(50)
+ thenRehashHappenedTimes(1)
+ thenSegmentExpands(false)
+ }
+
+ @Test
+ public void testSegmentWillRehashAndEventuallyExpand() {
+ whenIAddElements(SEGMENT_THRESHOLD)
+
+ // 1-st rehash
+ whenISetElementsAsInvalid(50)
+ whenIAddElements(50)
+ thenSegmentExpands(false)
+
+ // 2-nd rehash
+ whenISetElementsAsInvalid(30)
+ whenIAddElements(30)
+ thenSegmentExpands(false)
+
+ // 3-nd rehash
+ whenISetElementsAsInvalid(20)
+ whenIAddElements(20)
+ thenSegmentExpands(false)
+
+ // 4-th rehash with none invalid => expansion: segment * 2
+ whenIAddElements(SEGMENT_THRESHOLD)
+
+ thenRehashHappenedTimes(4)
+ thenSegmentSizeIs(INITIAL_SEGMENT_SIZE * 2)
+ }
+
+ private void whenIAddElements(int count) {
+ count.times {
+ String key = "k:${++keyId}-${it}"
+ segment.put(key, key.hashCode(), "v${it}")
+ }
+ }
+
+ private void whenISetElementsAsInvalid(int count) {
+ List<TestEntry> validEntires = entries.findAll { it.isValid() }
+ count.times {
+ validEntires.get(it).setValid(false)
+ }
+ }
+
+ private void thenRehashHappenedTimes(int expectedRehashCount) {
+ assert rehashCount == expectedRehashCount
+ }
+
+ private void thenSegmentSizeIs(int expectedSize) {
+ assert segment.table.length == expectedSize
+ }
+
+ private void thenSegmentExpands(boolean truth) {
+ assert segment.table.length > INITIAL_SEGMENT_SIZE == truth
+ }
+
+ class TestSegment extends org.codehaus.groovy.util.AbstractConcurrentMap.Segment {
+
+ protected TestSegment(int initialCapacity) {
+ super(initialCapacity)
+ }
+
+ @Override
+ protected org.codehaus.groovy.util.AbstractConcurrentMap.Entry createEntry(Object key, int hash, Object value) {
+ TestEntry entry = new TestEntry(key, hash, value)
+ entries.add(entry)
+ return entry
+ }
+
+ @Override
+ void rehash() {
+ rehashCount++
+ super.rehash()
+ }
+ }
+}
+
+class TestEntry implements org.codehaus.groovy.util.AbstractConcurrentMap.Entry {
+ Object key
+ Object value
+ int hash
+ boolean valid = true;
+
+ public TestEntry(Object key, int hash, Object value) {
+ this.key = key
+ this.hash = hash
+ this.value = value
+ }
+
+ @Override
+ boolean isEqual(Object key, int hash) {
+ return hash == this.hash && key.equals(this.key)
+ }
+
+ @Override
+ Object getValue() {
+ return value
+ }
+
+ @Override
+ void setValue(Object value) {
+ this.value = value
+ }
+
+ @Override
+ int getHash() {
+ return hash
+ }
+
+ @Override
+ boolean isValid() {
+ return valid
+ }
+
+ public void setValid(boolean valid) {
+ this.valid = valid
+ }
+}