You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@hugegraph.apache.org by "conghuhu (via GitHub)" <gi...@apache.org> on 2023/12/05 06:59:46 UTC
[PR] feat: add IntMapByDynamicHash [incubator-hugegraph]
conghuhu opened a new pull request, #2377:
URL: https://github.com/apache/incubator-hugegraph/pull/2377
<!--
Thank you very much for contributing to Apache HugeGraph, we are happy that you want to help us improve it!
Here are some tips for you:
1. If this is your first time, please read the [contributing guidelines](https://github.com/apache/hugegraph/blob/master/CONTRIBUTING.md)
2. If a PR fix/close an issue, type the message "close xxx" (xxx is the link of related
issue) in the content, GitHub will auto link it (Required)
3. Name the PR title in "Google Commit Format", start with "feat | fix | perf | refactor | doc | chore",
such like: "feat(core): support the PageRank algorithm" or "fix: wrong break in the compute loop" (module is optional)
skip it if you are unsure about which is the best component.
4. One PR address one issue, better not to mix up multiple issues.
5. Put an `x` in the `[ ]` to mark the item as CHECKED. `[x]` (or click it directly after
published)
-->
## Purpose of the PR
Add IntMapByDynamicHash for high performance, lockless, concurrency secure hashmap.
<!--
Please explain more context in this section, clarify why the changes are needed.
e.g:
- If you propose a new API, clarify the use case for a new API.
- If you fix a bug, you can clarify why it is a bug, and should be associated with an issue.
-->
## Main Changes
<!-- Please clarify what changes you are proposing. The purpose of this section is to outline the changes and how this PR fixes the issue. These change logs are helpful for better ant faster reviews.)
For example:
- If you introduce a new feature, please show detailed design here or add the link of design documentation.
- If you refactor some codes with changing classes, showing the class hierarchy will help reviewers.
- If there is a discussion in the mailing list, please add the link. -->
## Verifying these changes
### Dynamic Capcitity

### With Init Capcitity

- [ ] Trivial rework / code cleanup without any test coverage. (No Need)
- [ ] Already covered by existing tests, such as *(please modify tests here)*.
- [ ] Need tests and can be verified as follows:
- xxx
## Does this PR potentially affect the following parts?
<!-- DO NOT REMOVE THIS SECTION. CHECK THE PROPER BOX ONLY. -->
- [ ] Nope
- [ ] Dependencies (add/update license info) <!-- Don't forget to add/update the info in "LICENSE" & "NOTICE" files (both in root & dist module) -->
- [ ] Modify configurations
- [ ] The public API
- [ ] Other affects (typed here)
## Documentation Status
<!-- DO NOT REMOVE THIS SECTION. CHECK THE PROPER BOX ONLY. -->
- [ ] `Doc - TODO` <!-- Your PR changes impact docs and you will update later -->
- [ ] `Doc - Done` <!-- Related docs have been already added or updated -->
- [ ] `Doc - No Need` <!-- Your PR changes don't impact/need docs -->
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@hugegraph.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@hugegraph.apache.org
For additional commands, e-mail: issues-help@hugegraph.apache.org
Re: [PR] feat: add IntMapByDynamicHash [incubator-hugegraph]
Posted by "imbajin (via GitHub)" <gi...@apache.org>.
imbajin commented on PR #2377:
URL: https://github.com/apache/incubator-hugegraph/pull/2377#issuecomment-1842176886
From line L735 ~ L972, some suggestions from Copilot:
1. **Handling InterruptedException:** In the `waitForAllResizers` method of the `ResizeContainer` class, the InterruptedException is caught but completely ignored. This could potentially cause issues with thread interruption. In most cases, InterruptedException should either some operation in the catch block or propagate it further.
2. **Endless loop:** Depending on the IntMapByDynamicHash.tableAt(currentArray, index) != RESIZED condition in the helpWithResizeWhileCurrentIndex method, Java could get stuck in an endless while loop. The condition that ends the while loop (change of IntMapByDynamicHash.tableAt(currentArray, index)) does not seem to be reachable and changeable within the loop.
3. **Concurrency:** This code has complex concurrent operations and synchronizations, which are often a source of hard-to-detect bugs. Please ensure that your multithreading logic is correct and you are properly handling thread synchronization.
4. **Thread.yield() usage:** The usage of Thread.yield() is generally not recommended since its behavior can be unpredictable and could vary with different JVMs. You would also want to avoid it for real-time systems.
5. **Null Entry objects:** In the HashIterator's findNext method, null Entry objects are omitted. This would cause hasNext and next methods to not properly reflect the presence of these null entries.
6. **Mutation of shared resources:** Since the array being operated on is not final nor encapsulated, external threads could affect the same array. This could cause unexpected behaviors if not properly handled.
7. **Potential multithreading issues:** This code contains various multithreaded operations (e.g., asynchronous resizers updating in the ResizeContainer class), which can create complex interactions. Without proper synchronization controls, this may result in data inconsistencies.
8. **Method reverseTransfer is not in the code you provided:** There's method reverseTransfer is called in helpWithResize method. However, the code for reverseTransfer is not provided and thus, can't be validated.
Please note that these are potential issues that could lead to bugs based on the provided code snippet. Whether they could actually pose problems depends on the exact workflow and environment in which this code is used. It would also benefit from unit-tests to assure that functionality is as expected.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@hugegraph.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@hugegraph.apache.org
For additional commands, e-mail: issues-help@hugegraph.apache.org
Re: [PR] feat: add IntMapByDynamicHash [incubator-hugegraph]
Posted by "javeme (via GitHub)" <gi...@apache.org>.
javeme commented on code in PR #2377:
URL: https://github.com/apache/incubator-hugegraph/pull/2377#discussion_r1415652340
##########
hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/util/collection/IntMapByDynamicHash.java:
##########
@@ -0,0 +1,899 @@
+/*
+ * 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.hugegraph.util.collection;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
+
+import sun.misc.Unsafe;
+
+public class IntMapByDynamicHash implements IntMap {
+
+ private static final int DEFAULT_INITIAL_CAPACITY = 16;
+
+ /**
+ * The maximum capacity, used if a higher value is implicitly specified
+ * by either of the constructors with arguments.
+ * MUST be a power of two <= 1<<30.
+ */
+ private static final int MAXIMUM_CAPACITY = 1 << 30;
+
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private static final int PARTITIONED_SIZE_THRESHOLD = 4096;
+
+ private static final int NULL_VALUE = Integer.MIN_VALUE;
+
+ private static final AtomicReferenceFieldUpdater<IntMapByDynamicHash, Entry[]>
+ TABLE_UPDATER =
+ AtomicReferenceFieldUpdater.newUpdater(IntMapByDynamicHash.class, Entry[].class,
+ "table");
+
+ private volatile Entry[] table;
+
+ /**
+ * Partition counting to improve the concurrency performance of addToSize()
+ */
+ private int[] partitionedSize;
+
+ private static final Entry RESIZING = new Entry(NULL_VALUE, NULL_VALUE, 1);
+ private static final Entry RESIZED = new Entry(NULL_VALUE, NULL_VALUE, 2);
+
+ private static final Entry RESIZE_SENTINEL = new Entry(NULL_VALUE, NULL_VALUE, 3);
+
+ /**
+ * must be 2^n - 1
+ */
+ private static final int SIZE_BUCKETS = 7;
+
+
+ /* ---------------- Table element access -------------- */
+ private static Object tableAt(Object[] array, int index) {
+ return UNSAFE.getObjectVolatile(array,
+ ((long) index << ENTRY_ARRAY_SHIFT) +
+ ENTRY_ARRAY_BASE);
+ }
+
+ private static boolean casTableAt(Object[] array, int index, Object expected, Object newValue) {
+ return UNSAFE.compareAndSwapObject(
+ array,
+ ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ expected,
+ newValue);
+ }
+
+ private static void setTableAt(Object[] array, int index, Object newValue) {
+ UNSAFE.putObjectVolatile(array, ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ newValue);
+ }
+
+ private static int tableSizeFor(int c) {
+ int n = c - 1;
+ n |= n >>> 1;
+ n |= n >>> 2;
+ n |= n >>> 4;
+ n |= n >>> 8;
+ n |= n >>> 16;
+ return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
+ }
+
+ /**
+ * updated via atomic field updater
+ */
+ @SuppressWarnings("UnusedDeclaration")
+ private volatile int size;
Review Comment:
prefer to move to line 56
##########
hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/util/collection/IntMapByDynamicHash.java:
##########
@@ -0,0 +1,899 @@
+/*
+ * 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.hugegraph.util.collection;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
+
+import sun.misc.Unsafe;
+
+public class IntMapByDynamicHash implements IntMap {
+
+ private static final int DEFAULT_INITIAL_CAPACITY = 16;
+
+ /**
+ * The maximum capacity, used if a higher value is implicitly specified
+ * by either of the constructors with arguments.
+ * MUST be a power of two <= 1<<30.
+ */
+ private static final int MAXIMUM_CAPACITY = 1 << 30;
+
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private static final int PARTITIONED_SIZE_THRESHOLD = 4096;
+
+ private static final int NULL_VALUE = Integer.MIN_VALUE;
+
+ private static final AtomicReferenceFieldUpdater<IntMapByDynamicHash, Entry[]>
+ TABLE_UPDATER =
+ AtomicReferenceFieldUpdater.newUpdater(IntMapByDynamicHash.class, Entry[].class,
+ "table");
+
+ private volatile Entry[] table;
+
+ /**
+ * Partition counting to improve the concurrency performance of addToSize()
+ */
+ private int[] partitionedSize;
+
+ private static final Entry RESIZING = new Entry(NULL_VALUE, NULL_VALUE, 1);
+ private static final Entry RESIZED = new Entry(NULL_VALUE, NULL_VALUE, 2);
+
+ private static final Entry RESIZE_SENTINEL = new Entry(NULL_VALUE, NULL_VALUE, 3);
+
+ /**
+ * must be 2^n - 1
+ */
+ private static final int SIZE_BUCKETS = 7;
+
+
+ /* ---------------- Table element access -------------- */
+ private static Object tableAt(Object[] array, int index) {
+ return UNSAFE.getObjectVolatile(array,
+ ((long) index << ENTRY_ARRAY_SHIFT) +
+ ENTRY_ARRAY_BASE);
+ }
+
+ private static boolean casTableAt(Object[] array, int index, Object expected, Object newValue) {
+ return UNSAFE.compareAndSwapObject(
+ array,
+ ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ expected,
+ newValue);
+ }
+
+ private static void setTableAt(Object[] array, int index, Object newValue) {
+ UNSAFE.putObjectVolatile(array, ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ newValue);
+ }
+
+ private static int tableSizeFor(int c) {
+ int n = c - 1;
+ n |= n >>> 1;
+ n |= n >>> 2;
+ n |= n >>> 4;
+ n |= n >>> 8;
+ n |= n >>> 16;
+ return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
+ }
+
+ /**
+ * updated via atomic field updater
+ */
+ @SuppressWarnings("UnusedDeclaration")
+ private volatile int size;
+
+ public IntMapByDynamicHash() {
+ this(DEFAULT_INITIAL_CAPACITY);
+ }
+
+ public IntMapByDynamicHash(int initialCapacity) {
+ if (initialCapacity < 0) {
+ throw new IllegalArgumentException("Illegal Initial Capacity: " + initialCapacity);
+ }
+ if (initialCapacity > MAXIMUM_CAPACITY) {
+ initialCapacity = MAXIMUM_CAPACITY;
+ }
+ long size = (long) (1.0 + (long) initialCapacity / LOAD_FACTOR);
+ int cap = (size >= (long) MAXIMUM_CAPACITY) ?
+ MAXIMUM_CAPACITY : tableSizeFor((int) size);
+ if (cap >= PARTITIONED_SIZE_THRESHOLD) {
+ // we want 7 extra slots and 64 bytes for each
+ // slot. int is 4 bytes, so 64 bytes is 16 ints.
+ this.partitionedSize =
+ new int[SIZE_BUCKETS * 16];
+ }
+ // The end index is for resizeContainer
+ this.table = new Entry[cap + 1];
+ }
+
+ @Override
+ public boolean put(int key, int value) {
+ int hash = this.hash(key);
+ Entry[] currentArray = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == null) {
+ Entry newEntry = new Entry(key, value);
+ this.addToSize(1);
+ if (IntMapByDynamicHash.casTableAt(currentArray, hash, null, newEntry)) {
+ return true;
+ }
+ this.addToSize(-1);
+ }
+
+ this.slowPut(key, value, currentArray);
+ return true;
+ }
+
+ private int slowPut(int key, int value, Entry[] currentTable) {
+ int length;
+ int index;
+ Entry o;
+
+ while (true) {
+ length = currentTable.length;
+ index = this.hash(key, length);
+ o = (Entry) IntMapByDynamicHash.tableAt(currentTable, index);
+
+ if (o == RESIZED || o == RESIZING) {
+ currentTable = this.helpWithResizeWhileCurrentIndex(currentTable, index);
+ } else {
+ Entry e = o;
+ boolean found = false;
+
+ // Search for the key in the chain
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ found = true;
+ break;
+ }
+ e = e.getNext();
+ }
+
+ if (found) {
+ int oldVal = e.getValue();
+ // Key found, replace the entry
+ Entry newEntry =
+ new Entry(key, value, this.createReplacementChainForRemoval(o, e));
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, newEntry)) {
+ return oldVal;
+ }
+ } else {
+ // Key not found, add a new entry
+ Entry newEntry = new Entry(key, value, o);
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, newEntry)) {
+ this.incrementSizeAndPossiblyResize(currentTable, length, o);
+ return NULL_VALUE;
+ }
+ }
+ }
+ }
+ }
+
+ @Override
+ public int get(int key) {
+ int hash = this.hash(key);
+ Entry[] currentArray = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == RESIZED || o == RESIZING) {
+ return this.slowGet(key, currentArray);
+ }
+ for (Entry e = o; e != null; e = e.getNext()) {
+ int k;
+ if ((k = e.getKey()) == key || key == k) {
+ return e.value;
+ }
+ }
+ return NULL_VALUE;
+ }
+
+ private int slowGet(int key, Entry[] currentArray) {
+ while (true) {
+ int length = currentArray.length;
+ int hash = this.hash(key, length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = this.helpWithResizeWhileCurrentIndex(currentArray, hash);
+ } else {
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ return e.getValue();
+ }
+ e = e.getNext();
+ }
+ return NULL_VALUE;
+ }
+ }
+ }
+
+ @Override
+ public boolean remove(int key) {
+ int hash = this.hash(key);
+ Entry[] currentTable = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentTable, hash);
+ if (o == RESIZED || o == RESIZING) {
+ return this.slowRemove(key, currentTable) != null;
+ }
+
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ Entry replacement = this.createReplacementChainForRemoval(o, e);
+ if (IntMapByDynamicHash.casTableAt(currentTable, hash, o, replacement)) {
+ this.addToSize(-1);
+ return true;
+ }
+ return this.slowRemove(key, currentTable) != null;
+ }
+ e = e.getNext();
+ }
+ return false;
+ }
+
+ private Entry slowRemove(int key, Entry[] currentTable) {
+ int length;
+ int index;
+ Entry o;
+
+ while (true) {
+ length = currentTable.length;
+ index = this.hash(key, length);
+ o = (Entry) IntMapByDynamicHash.tableAt(currentTable, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentTable = this.helpWithResizeWhileCurrentIndex(currentTable, index);
+ } else {
+ Entry e = o;
+ Entry prev = null;
+
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ Entry replacement = this.createReplacementChainForRemoval(o, e);
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, replacement)) {
+ this.addToSize(-1);
+ return e;
+ }
+ // Key found, but CAS failed, restart the loop
+ break;
+ }
+ prev = e;
+ e = e.getNext();
+ }
+
+ if (prev != null) {
+ // Key not found
+ return null;
+ }
+ }
+ }
+ }
+
+ @Override
+ public boolean containsKey(int key) {
+ return this.getEntry(key) != null;
+ }
+
+ @Override
+ public IntIterator keys() {
+ return new KeyIterator();
+ }
+
+ @Override
+ public IntIterator values() {
+ return new ValueIterator();
+ }
+
+ @Override
+ public void clear() {
+ Entry[] currentArray = this.table;
+ ResizeContainer resizeContainer;
+ do {
+ resizeContainer = null;
+ for (int i = 0; i < currentArray.length - 1; i++) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, i);
+ if (o == RESIZED || o == RESIZING) {
+ resizeContainer = (ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ currentArray.length -
+ 1);
+ } else if (o != null) {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(currentArray, i, o, null)) {
+ int removedEntries = 0;
+ while (e != null) {
+ removedEntries++;
+ e = e.getNext();
+ }
+ this.addToSize(-removedEntries);
+ }
+ }
+ }
+ if (resizeContainer != null) {
+ if (resizeContainer.isNotDone()) {
+ this.helpWithResize(currentArray);
+ resizeContainer.waitForAllResizers();
+ }
+ currentArray = resizeContainer.nextArray;
+ }
+ } while (resizeContainer != null);
+ }
+
+ @Override
+ public int size() {
+ int localSize = this.size;
+ if (this.partitionedSize != null) {
+ for (int i = 0; i < SIZE_BUCKETS; i++) {
+ localSize += this.partitionedSize[i << 4];
+ }
+ }
+ return localSize;
+ }
+
+ @Override
+ public boolean concurrent() {
+ return true;
+ }
+
+ private int hash(int key) {
+ return key & (table.length - 2);
+ }
+
+ private int hash(int key, int length) {
+ return key & (length - 2);
+ }
+
+ private Entry getEntry(int key) {
+ Entry[] currentArray = this.table;
+ while (true) {
+ int length = currentArray.length;
+ int index = this.hash(key, length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = this.helpWithResizeWhileCurrentIndex(currentArray, index);
+ } else {
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ return e;
+ }
+ e = e.getNext();
+ }
+ return null;
+ }
+ }
+ }
+
+ private void addToSize(int value) {
+ if (this.partitionedSize != null) {
+ if (this.incrementPartitionedSize(value)) {
+ return;
+ }
+ }
+ this.incrementLocalSize(value);
+ }
+
+ private boolean incrementPartitionedSize(int value) {
+ int h = (int) Thread.currentThread().getId();
+ h ^= (h >>> 18) ^ (h >>> 12);
+ h = (h ^ (h >>> 10)) & SIZE_BUCKETS;
+ if (h != 0) {
+ h = (h - 1) << 4;
+ long address = ((long) h << INT_ARRAY_SHIFT) + INT_ARRAY_BASE;
+ while (true) {
+ int localSize = UNSAFE.getIntVolatile(this.partitionedSize, address);
+ if (UNSAFE.compareAndSwapInt(this.partitionedSize, address, localSize,
+ localSize + value)) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ private void incrementLocalSize(int value) {
+ while (true) {
+ int localSize = this.size;
+ if (UNSAFE.compareAndSwapInt(this, SIZE_OFFSET, localSize, localSize + value)) {
+ break;
+ }
+ }
+ }
+
+ private Entry createReplacementChainForRemoval(Entry original,
+ Entry toRemove) {
+ if (original == toRemove) {
+ return original.getNext();
+ }
+ Entry replacement = null;
+ Entry e = original;
+ while (e != null) {
+ if (e != toRemove) {
+ replacement = new Entry(e.getKey(), e.getValue(), replacement);
+ }
+ e = e.getNext();
+ }
+ return replacement;
+ }
+
+ private void incrementSizeAndPossiblyResize(Entry[] currentArray, int length, Entry prev) {
+ this.addToSize(1);
+ if (prev != null) {
+ int localSize = this.size();
+ int threshold = (int) (length * LOAD_FACTOR); // threshold = length * 0.75
+ if (localSize + 1 > threshold) {
+ this.resize(currentArray);
+ }
+ }
+ }
+
+ private Entry[] helpWithResizeWhileCurrentIndex(Entry[] currentArray, int index) {
+ Entry[] newArray = this.helpWithResize(currentArray);
+ int helpCount = 0;
+ while (IntMapByDynamicHash.tableAt(currentArray, index) != RESIZED) {
+ helpCount++;
+ newArray = this.helpWithResize(currentArray);
+ if ((helpCount & 7) == 0) {
+ Thread.yield();
+ }
+ }
+ return newArray;
+ }
+
+ private void resize(Entry[] oldTable) {
+ this.resize(oldTable, (oldTable.length - 1 << 1) + 1);
+ }
+
+ // newSize must be a power of 2 + 1
+ @SuppressWarnings("JLM_JSR166_UTILCONCURRENT_MONITORENTER")
+ private void resize(Entry[] oldTable, int newSize) {
+ int oldCapacity = oldTable.length;
+ int end = oldCapacity - 1;
+ Entry last = (Entry) IntMapByDynamicHash.tableAt(oldTable, end);
+ if (this.size() < end && last == RESIZE_SENTINEL) {
+ return;
+ }
+ if (oldCapacity >= MAXIMUM_CAPACITY) {
+ throw new RuntimeException("max capacity of map exceeded");
+ }
+ ResizeContainer resizeContainer = null;
+ // This ownResize records whether current thread need to perform the expansion operation of
+ // the map by itself
+ boolean ownResize = false;
+ if (last == null || last == RESIZE_SENTINEL) {
+ // allocating a new array is too expensive to make this an atomic operation
+ synchronized (oldTable) {
+ if (IntMapByDynamicHash.tableAt(oldTable, end) == null) {
+ IntMapByDynamicHash.setTableAt(oldTable, end, RESIZE_SENTINEL);
+ if (this.partitionedSize == null && newSize >= PARTITIONED_SIZE_THRESHOLD) {
+ this.partitionedSize = new int[SIZE_BUCKETS * 16];
+ }
+ resizeContainer = new ResizeContainer(new Entry[newSize], oldTable.length - 1);
+ IntMapByDynamicHash.setTableAt(oldTable, end, resizeContainer);
+ ownResize = true;
+ }
+ }
+ }
+ if (ownResize) {
+ this.transfer(oldTable, resizeContainer);
+
+ Entry[] src = this.table;
+ while (!TABLE_UPDATER.compareAndSet(this, oldTable, resizeContainer.nextArray)) {
+ /*
+ we're in a double resize situation; we'll have to go help until it's our turn
+ to set the table
+ */
+ if (src != oldTable) {
+ this.helpWithResize(src);
+ }
+ }
+ } else {
+ this.helpWithResize(oldTable);
+ }
+ }
+
+ /**
+ * Transfer all entries from src to dest tables
+ */
+ private void transfer(Entry[] src, ResizeContainer resizeContainer) {
+ Entry[] dest = resizeContainer.nextArray;
+
+ for (int j = 0; j < src.length - 1; ) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(src, j);
+ if (o == null) {
+ if (IntMapByDynamicHash.casTableAt(src, j, null, RESIZED)) {
+ j++;
+ }
+ } else if (o == RESIZED || o == RESIZING) {
+ /*
+ During the expansion process, other threads have already migrated the elements at
+ this location to the new array. This means that the elements in the current
+ position have already been processed and do not need to be migrated again.
+ */
+ j = (j & ~(ResizeContainer.QUEUE_INCREMENT - 1)) + ResizeContainer.QUEUE_INCREMENT;
+ /*
+ When there is only one thread for expansion, there is no concurrency issue
+ and there is no need to wait.
+ */
+ if (resizeContainer.resizers.get() == 1) {
+ break;
+ }
+ } else {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(src, j, o, RESIZING)) {
+ while (e != null) {
+ this.unconditionalCopy(dest, e);
+ e = e.getNext();
+ }
+ IntMapByDynamicHash.setTableAt(src, j, RESIZED);
+ j++;
+ }
+ }
+ }
+ resizeContainer.decrementResizerAndNotify();
+ resizeContainer.waitForAllResizers();
+ }
+
+ /**
+ * Enable the current thread to participate in the expansion
+ */
+ private Entry[] helpWithResize(Entry[] currentArray) {
+ ResizeContainer resizeContainer =
+ (ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ currentArray.length - 1);
+ Entry[] newTable = resizeContainer.nextArray;
+ if (resizeContainer.getQueuePosition() > ResizeContainer.QUEUE_INCREMENT) {
+ resizeContainer.incrementResizer();
+ this.reverseTransfer(currentArray, resizeContainer);
+ resizeContainer.decrementResizerAndNotify();
+ }
+ return newTable;
+ }
+
+ private void reverseTransfer(Entry[] src, ResizeContainer resizeContainer) {
+ Entry[] dest = resizeContainer.nextArray;
+ while (resizeContainer.getQueuePosition() > 0) {
+ int start = resizeContainer.subtractAndGetQueuePosition();
+ int end = start + ResizeContainer.QUEUE_INCREMENT;
+ if (end > 0) {
+ if (start < 0) {
+ start = 0;
+ }
+ for (int j = end - 1; j >= start; ) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(src, j);
+ if (o == null) {
+ if (IntMapByDynamicHash.casTableAt(src, j, null, RESIZED)) {
+ j--;
+ }
+ } else if (o == RESIZED || o == RESIZING) {
+ resizeContainer.zeroOutQueuePosition();
+ return;
+ } else {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(src, j, o, RESIZING)) {
+ while (e != null) {
+ this.unconditionalCopy(dest, e);
+ e = e.getNext();
+ }
+ IntMapByDynamicHash.setTableAt(src, j, RESIZED);
+ j--;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ private void unconditionalCopy(Entry[] dest, Entry toCopyEntry) {
+ Entry[] currentArray = dest;
+ while (true) {
+ int length = currentArray.length;
+ int index = this.hash(toCopyEntry.getKey(), length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = ((ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ length -
+ 1)).nextArray;
+ } else {
+ Entry newEntry;
+ if (o == null) {
+ if (toCopyEntry.getNext() == null) {
+ newEntry = toCopyEntry; // no need to duplicate
+ } else {
+ newEntry = new Entry(toCopyEntry.getKey(), toCopyEntry.getValue());
+ }
+ } else {
+ newEntry =
+ new Entry(toCopyEntry.getKey(), toCopyEntry.getValue(), o);
+ }
+ if (IntMapByDynamicHash.casTableAt(currentArray, index, o, newEntry)) {
+ return;
+ }
+ }
+ }
+ }
+
+ private static final class ResizeContainer extends Entry {
+ private static final int QUEUE_INCREMENT =
+ Math.min(1 << 10,
+ Integer.highestOneBit(Runtime.getRuntime().availableProcessors()) << 4);
Review Comment:
we have defined a const CPUS, let's just use it
##########
hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/util/collection/IntMapByDynamicHash.java:
##########
@@ -0,0 +1,899 @@
+/*
+ * 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.hugegraph.util.collection;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
+
+import sun.misc.Unsafe;
+
+public class IntMapByDynamicHash implements IntMap {
+
+ private static final int DEFAULT_INITIAL_CAPACITY = 16;
+
+ /**
+ * The maximum capacity, used if a higher value is implicitly specified
+ * by either of the constructors with arguments.
+ * MUST be a power of two <= 1<<30.
+ */
+ private static final int MAXIMUM_CAPACITY = 1 << 30;
+
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private static final int PARTITIONED_SIZE_THRESHOLD = 4096;
+
+ private static final int NULL_VALUE = Integer.MIN_VALUE;
+
+ private static final AtomicReferenceFieldUpdater<IntMapByDynamicHash, Entry[]>
+ TABLE_UPDATER =
+ AtomicReferenceFieldUpdater.newUpdater(IntMapByDynamicHash.class, Entry[].class,
+ "table");
+
+ private volatile Entry[] table;
+
+ /**
+ * Partition counting to improve the concurrency performance of addToSize()
+ */
+ private int[] partitionedSize;
+
+ private static final Entry RESIZING = new Entry(NULL_VALUE, NULL_VALUE, 1);
+ private static final Entry RESIZED = new Entry(NULL_VALUE, NULL_VALUE, 2);
+
+ private static final Entry RESIZE_SENTINEL = new Entry(NULL_VALUE, NULL_VALUE, 3);
+
+ /**
+ * must be 2^n - 1
+ */
+ private static final int SIZE_BUCKETS = 7;
+
+
+ /* ---------------- Table element access -------------- */
+ private static Object tableAt(Object[] array, int index) {
+ return UNSAFE.getObjectVolatile(array,
+ ((long) index << ENTRY_ARRAY_SHIFT) +
+ ENTRY_ARRAY_BASE);
+ }
+
+ private static boolean casTableAt(Object[] array, int index, Object expected, Object newValue) {
+ return UNSAFE.compareAndSwapObject(
+ array,
+ ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ expected,
+ newValue);
+ }
+
+ private static void setTableAt(Object[] array, int index, Object newValue) {
+ UNSAFE.putObjectVolatile(array, ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ newValue);
+ }
+
+ private static int tableSizeFor(int c) {
+ int n = c - 1;
+ n |= n >>> 1;
+ n |= n >>> 2;
+ n |= n >>> 4;
+ n |= n >>> 8;
+ n |= n >>> 16;
+ return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
+ }
+
+ /**
+ * updated via atomic field updater
+ */
+ @SuppressWarnings("UnusedDeclaration")
+ private volatile int size;
+
+ public IntMapByDynamicHash() {
+ this(DEFAULT_INITIAL_CAPACITY);
+ }
+
+ public IntMapByDynamicHash(int initialCapacity) {
+ if (initialCapacity < 0) {
+ throw new IllegalArgumentException("Illegal Initial Capacity: " + initialCapacity);
+ }
+ if (initialCapacity > MAXIMUM_CAPACITY) {
+ initialCapacity = MAXIMUM_CAPACITY;
+ }
+ long size = (long) (1.0 + (long) initialCapacity / LOAD_FACTOR);
+ int cap = (size >= (long) MAXIMUM_CAPACITY) ?
+ MAXIMUM_CAPACITY : tableSizeFor((int) size);
+ if (cap >= PARTITIONED_SIZE_THRESHOLD) {
+ // we want 7 extra slots and 64 bytes for each
+ // slot. int is 4 bytes, so 64 bytes is 16 ints.
+ this.partitionedSize =
+ new int[SIZE_BUCKETS * 16];
+ }
+ // The end index is for resizeContainer
+ this.table = new Entry[cap + 1];
+ }
+
+ @Override
+ public boolean put(int key, int value) {
+ int hash = this.hash(key);
+ Entry[] currentArray = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == null) {
+ Entry newEntry = new Entry(key, value);
+ this.addToSize(1);
+ if (IntMapByDynamicHash.casTableAt(currentArray, hash, null, newEntry)) {
+ return true;
+ }
+ this.addToSize(-1);
+ }
+
+ this.slowPut(key, value, currentArray);
+ return true;
+ }
+
+ private int slowPut(int key, int value, Entry[] currentTable) {
+ int length;
+ int index;
+ Entry o;
+
+ while (true) {
+ length = currentTable.length;
+ index = this.hash(key, length);
+ o = (Entry) IntMapByDynamicHash.tableAt(currentTable, index);
+
+ if (o == RESIZED || o == RESIZING) {
+ currentTable = this.helpWithResizeWhileCurrentIndex(currentTable, index);
+ } else {
+ Entry e = o;
+ boolean found = false;
+
+ // Search for the key in the chain
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ found = true;
+ break;
+ }
+ e = e.getNext();
+ }
+
+ if (found) {
+ int oldVal = e.getValue();
+ // Key found, replace the entry
+ Entry newEntry =
+ new Entry(key, value, this.createReplacementChainForRemoval(o, e));
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, newEntry)) {
+ return oldVal;
+ }
+ } else {
+ // Key not found, add a new entry
+ Entry newEntry = new Entry(key, value, o);
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, newEntry)) {
+ this.incrementSizeAndPossiblyResize(currentTable, length, o);
+ return NULL_VALUE;
+ }
+ }
+ }
+ }
+ }
+
+ @Override
+ public int get(int key) {
+ int hash = this.hash(key);
+ Entry[] currentArray = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == RESIZED || o == RESIZING) {
+ return this.slowGet(key, currentArray);
+ }
+ for (Entry e = o; e != null; e = e.getNext()) {
+ int k;
+ if ((k = e.getKey()) == key || key == k) {
+ return e.value;
+ }
+ }
+ return NULL_VALUE;
+ }
+
+ private int slowGet(int key, Entry[] currentArray) {
+ while (true) {
+ int length = currentArray.length;
+ int hash = this.hash(key, length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = this.helpWithResizeWhileCurrentIndex(currentArray, hash);
+ } else {
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ return e.getValue();
+ }
+ e = e.getNext();
+ }
+ return NULL_VALUE;
+ }
+ }
+ }
+
+ @Override
+ public boolean remove(int key) {
+ int hash = this.hash(key);
+ Entry[] currentTable = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentTable, hash);
+ if (o == RESIZED || o == RESIZING) {
+ return this.slowRemove(key, currentTable) != null;
+ }
+
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ Entry replacement = this.createReplacementChainForRemoval(o, e);
+ if (IntMapByDynamicHash.casTableAt(currentTable, hash, o, replacement)) {
+ this.addToSize(-1);
+ return true;
+ }
+ return this.slowRemove(key, currentTable) != null;
+ }
+ e = e.getNext();
+ }
+ return false;
+ }
+
+ private Entry slowRemove(int key, Entry[] currentTable) {
+ int length;
+ int index;
+ Entry o;
+
+ while (true) {
+ length = currentTable.length;
+ index = this.hash(key, length);
+ o = (Entry) IntMapByDynamicHash.tableAt(currentTable, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentTable = this.helpWithResizeWhileCurrentIndex(currentTable, index);
+ } else {
+ Entry e = o;
+ Entry prev = null;
+
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ Entry replacement = this.createReplacementChainForRemoval(o, e);
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, replacement)) {
+ this.addToSize(-1);
+ return e;
+ }
+ // Key found, but CAS failed, restart the loop
+ break;
+ }
+ prev = e;
+ e = e.getNext();
+ }
+
+ if (prev != null) {
+ // Key not found
+ return null;
+ }
+ }
+ }
+ }
+
+ @Override
+ public boolean containsKey(int key) {
+ return this.getEntry(key) != null;
+ }
+
+ @Override
+ public IntIterator keys() {
+ return new KeyIterator();
+ }
+
+ @Override
+ public IntIterator values() {
+ return new ValueIterator();
+ }
+
+ @Override
+ public void clear() {
+ Entry[] currentArray = this.table;
+ ResizeContainer resizeContainer;
+ do {
+ resizeContainer = null;
+ for (int i = 0; i < currentArray.length - 1; i++) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, i);
+ if (o == RESIZED || o == RESIZING) {
+ resizeContainer = (ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ currentArray.length -
+ 1);
+ } else if (o != null) {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(currentArray, i, o, null)) {
+ int removedEntries = 0;
+ while (e != null) {
+ removedEntries++;
+ e = e.getNext();
+ }
+ this.addToSize(-removedEntries);
+ }
+ }
+ }
+ if (resizeContainer != null) {
+ if (resizeContainer.isNotDone()) {
+ this.helpWithResize(currentArray);
+ resizeContainer.waitForAllResizers();
+ }
+ currentArray = resizeContainer.nextArray;
+ }
+ } while (resizeContainer != null);
+ }
+
+ @Override
+ public int size() {
+ int localSize = this.size;
+ if (this.partitionedSize != null) {
+ for (int i = 0; i < SIZE_BUCKETS; i++) {
+ localSize += this.partitionedSize[i << 4];
+ }
+ }
+ return localSize;
+ }
+
+ @Override
+ public boolean concurrent() {
+ return true;
+ }
+
+ private int hash(int key) {
+ return key & (table.length - 2);
+ }
+
+ private int hash(int key, int length) {
+ return key & (length - 2);
+ }
+
+ private Entry getEntry(int key) {
+ Entry[] currentArray = this.table;
+ while (true) {
+ int length = currentArray.length;
+ int index = this.hash(key, length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = this.helpWithResizeWhileCurrentIndex(currentArray, index);
+ } else {
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ return e;
+ }
+ e = e.getNext();
+ }
+ return null;
+ }
+ }
+ }
+
+ private void addToSize(int value) {
+ if (this.partitionedSize != null) {
+ if (this.incrementPartitionedSize(value)) {
+ return;
+ }
+ }
+ this.incrementLocalSize(value);
+ }
+
+ private boolean incrementPartitionedSize(int value) {
+ int h = (int) Thread.currentThread().getId();
+ h ^= (h >>> 18) ^ (h >>> 12);
+ h = (h ^ (h >>> 10)) & SIZE_BUCKETS;
+ if (h != 0) {
+ h = (h - 1) << 4;
+ long address = ((long) h << INT_ARRAY_SHIFT) + INT_ARRAY_BASE;
+ while (true) {
+ int localSize = UNSAFE.getIntVolatile(this.partitionedSize, address);
+ if (UNSAFE.compareAndSwapInt(this.partitionedSize, address, localSize,
+ localSize + value)) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ private void incrementLocalSize(int value) {
+ while (true) {
+ int localSize = this.size;
+ if (UNSAFE.compareAndSwapInt(this, SIZE_OFFSET, localSize, localSize + value)) {
+ break;
+ }
+ }
+ }
+
+ private Entry createReplacementChainForRemoval(Entry original,
+ Entry toRemove) {
+ if (original == toRemove) {
+ return original.getNext();
+ }
+ Entry replacement = null;
+ Entry e = original;
+ while (e != null) {
+ if (e != toRemove) {
+ replacement = new Entry(e.getKey(), e.getValue(), replacement);
+ }
+ e = e.getNext();
+ }
+ return replacement;
+ }
+
+ private void incrementSizeAndPossiblyResize(Entry[] currentArray, int length, Entry prev) {
+ this.addToSize(1);
+ if (prev != null) {
+ int localSize = this.size();
+ int threshold = (int) (length * LOAD_FACTOR); // threshold = length * 0.75
+ if (localSize + 1 > threshold) {
+ this.resize(currentArray);
+ }
+ }
+ }
+
+ private Entry[] helpWithResizeWhileCurrentIndex(Entry[] currentArray, int index) {
+ Entry[] newArray = this.helpWithResize(currentArray);
+ int helpCount = 0;
+ while (IntMapByDynamicHash.tableAt(currentArray, index) != RESIZED) {
+ helpCount++;
+ newArray = this.helpWithResize(currentArray);
+ if ((helpCount & 7) == 0) {
+ Thread.yield();
+ }
+ }
+ return newArray;
+ }
+
+ private void resize(Entry[] oldTable) {
+ this.resize(oldTable, (oldTable.length - 1 << 1) + 1);
+ }
+
+ // newSize must be a power of 2 + 1
+ @SuppressWarnings("JLM_JSR166_UTILCONCURRENT_MONITORENTER")
+ private void resize(Entry[] oldTable, int newSize) {
+ int oldCapacity = oldTable.length;
+ int end = oldCapacity - 1;
+ Entry last = (Entry) IntMapByDynamicHash.tableAt(oldTable, end);
+ if (this.size() < end && last == RESIZE_SENTINEL) {
+ return;
+ }
+ if (oldCapacity >= MAXIMUM_CAPACITY) {
+ throw new RuntimeException("max capacity of map exceeded");
+ }
+ ResizeContainer resizeContainer = null;
+ // This ownResize records whether current thread need to perform the expansion operation of
+ // the map by itself
+ boolean ownResize = false;
+ if (last == null || last == RESIZE_SENTINEL) {
+ // allocating a new array is too expensive to make this an atomic operation
+ synchronized (oldTable) {
+ if (IntMapByDynamicHash.tableAt(oldTable, end) == null) {
+ IntMapByDynamicHash.setTableAt(oldTable, end, RESIZE_SENTINEL);
+ if (this.partitionedSize == null && newSize >= PARTITIONED_SIZE_THRESHOLD) {
+ this.partitionedSize = new int[SIZE_BUCKETS * 16];
+ }
+ resizeContainer = new ResizeContainer(new Entry[newSize], oldTable.length - 1);
+ IntMapByDynamicHash.setTableAt(oldTable, end, resizeContainer);
+ ownResize = true;
+ }
+ }
+ }
+ if (ownResize) {
+ this.transfer(oldTable, resizeContainer);
+
+ Entry[] src = this.table;
+ while (!TABLE_UPDATER.compareAndSet(this, oldTable, resizeContainer.nextArray)) {
+ /*
+ we're in a double resize situation; we'll have to go help until it's our turn
+ to set the table
+ */
+ if (src != oldTable) {
+ this.helpWithResize(src);
+ }
+ }
+ } else {
+ this.helpWithResize(oldTable);
+ }
+ }
+
+ /**
+ * Transfer all entries from src to dest tables
+ */
+ private void transfer(Entry[] src, ResizeContainer resizeContainer) {
+ Entry[] dest = resizeContainer.nextArray;
+
+ for (int j = 0; j < src.length - 1; ) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(src, j);
+ if (o == null) {
+ if (IntMapByDynamicHash.casTableAt(src, j, null, RESIZED)) {
+ j++;
+ }
+ } else if (o == RESIZED || o == RESIZING) {
+ /*
+ During the expansion process, other threads have already migrated the elements at
+ this location to the new array. This means that the elements in the current
+ position have already been processed and do not need to be migrated again.
+ */
+ j = (j & ~(ResizeContainer.QUEUE_INCREMENT - 1)) + ResizeContainer.QUEUE_INCREMENT;
+ /*
+ When there is only one thread for expansion, there is no concurrency issue
+ and there is no need to wait.
+ */
+ if (resizeContainer.resizers.get() == 1) {
+ break;
+ }
+ } else {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(src, j, o, RESIZING)) {
+ while (e != null) {
+ this.unconditionalCopy(dest, e);
+ e = e.getNext();
+ }
+ IntMapByDynamicHash.setTableAt(src, j, RESIZED);
+ j++;
+ }
+ }
+ }
+ resizeContainer.decrementResizerAndNotify();
+ resizeContainer.waitForAllResizers();
+ }
+
+ /**
+ * Enable the current thread to participate in the expansion
+ */
+ private Entry[] helpWithResize(Entry[] currentArray) {
+ ResizeContainer resizeContainer =
+ (ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ currentArray.length - 1);
+ Entry[] newTable = resizeContainer.nextArray;
+ if (resizeContainer.getQueuePosition() > ResizeContainer.QUEUE_INCREMENT) {
+ resizeContainer.incrementResizer();
+ this.reverseTransfer(currentArray, resizeContainer);
+ resizeContainer.decrementResizerAndNotify();
+ }
+ return newTable;
+ }
+
+ private void reverseTransfer(Entry[] src, ResizeContainer resizeContainer) {
+ Entry[] dest = resizeContainer.nextArray;
+ while (resizeContainer.getQueuePosition() > 0) {
+ int start = resizeContainer.subtractAndGetQueuePosition();
+ int end = start + ResizeContainer.QUEUE_INCREMENT;
+ if (end > 0) {
+ if (start < 0) {
+ start = 0;
+ }
+ for (int j = end - 1; j >= start; ) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(src, j);
+ if (o == null) {
+ if (IntMapByDynamicHash.casTableAt(src, j, null, RESIZED)) {
+ j--;
+ }
+ } else if (o == RESIZED || o == RESIZING) {
+ resizeContainer.zeroOutQueuePosition();
+ return;
+ } else {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(src, j, o, RESIZING)) {
+ while (e != null) {
+ this.unconditionalCopy(dest, e);
+ e = e.getNext();
+ }
+ IntMapByDynamicHash.setTableAt(src, j, RESIZED);
+ j--;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ private void unconditionalCopy(Entry[] dest, Entry toCopyEntry) {
+ Entry[] currentArray = dest;
+ while (true) {
+ int length = currentArray.length;
+ int index = this.hash(toCopyEntry.getKey(), length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = ((ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ length -
+ 1)).nextArray;
+ } else {
+ Entry newEntry;
+ if (o == null) {
+ if (toCopyEntry.getNext() == null) {
+ newEntry = toCopyEntry; // no need to duplicate
+ } else {
+ newEntry = new Entry(toCopyEntry.getKey(), toCopyEntry.getValue());
+ }
+ } else {
+ newEntry =
+ new Entry(toCopyEntry.getKey(), toCopyEntry.getValue(), o);
+ }
+ if (IntMapByDynamicHash.casTableAt(currentArray, index, o, newEntry)) {
+ return;
+ }
+ }
+ }
+ }
+
+ private static final class ResizeContainer extends Entry {
+ private static final int QUEUE_INCREMENT =
+ Math.min(1 << 10,
+ Integer.highestOneBit(Runtime.getRuntime().availableProcessors()) << 4);
+ private final AtomicInteger resizers = new AtomicInteger(1);
+ private final Entry[] nextArray;
+ private final AtomicInteger queuePosition;
+
+ private ResizeContainer(Entry[] nextArray, int oldSize) {
+ super(NULL_VALUE, NULL_VALUE, 4);
+ this.nextArray = nextArray;
+ this.queuePosition = new AtomicInteger(oldSize);
+ }
+
+ public void incrementResizer() {
+ this.resizers.incrementAndGet();
+ }
+
+ public void decrementResizerAndNotify() {
+ int remaining = this.resizers.decrementAndGet();
+ if (remaining == 0) {
+ synchronized (this) {
+ this.notifyAll();
+ }
+ }
+ }
+
+ public int getQueuePosition() {
+ return this.queuePosition.get();
+ }
+
+ public int subtractAndGetQueuePosition() {
+ return this.queuePosition.addAndGet(-QUEUE_INCREMENT);
+ }
+
+ public void waitForAllResizers() {
+ if (this.resizers.get() > 0) {
+ for (int i = 0; i < 16; i++) {
+ if (this.resizers.get() == 0) {
+ break;
+ }
+ }
+ for (int i = 0; i < 16; i++) {
+ if (this.resizers.get() == 0) {
+ break;
+ }
+ Thread.yield();
+ }
+ }
+ if (this.resizers.get() > 0) {
+ synchronized (this) {
+ while (this.resizers.get() > 0) {
+ try {
+ this.wait();
+ } catch (InterruptedException e) {
+ //ginore
+ }
+ }
+ }
+ }
+ }
+
+ public boolean isNotDone() {
+ return this.resizers.get() > 0;
+ }
+
+ public void zeroOutQueuePosition() {
+ this.queuePosition.set(0);
+ }
+ }
+
+ private static class Entry {
+ final int key;
+ volatile int value;
+ volatile Entry next;
+
+ /**
+ * 0 NORMAL
+ * 1 RESIZING
+ * 2 RESIZED
+ * 3 RESIZE_SENTINEL
+ * 4 ResizeContainer
+ */
+ final int state;
+
+ public Entry(int key, int value, int state) {
+ this.key = key;
+ this.value = value;
+ this.state = state;
+ }
+
+ public Entry(int key, int value) {
+ this.key = key;
+ this.value = value;
+ this.next = null;
+ this.state = 0;
+ }
+
+ public Entry(int key, int value, Entry next) {
+ this.key = key;
+ this.value = value;
+ this.next = next;
+ this.state = 0;
+ }
+
+ public int getKey() {
+ return key;
+ }
+
+ public int getValue() {
+ return value;
+ }
+
+ public Entry getNext() {
+ return next;
+ }
+
+ @Override
+ public String toString() {
+ return this.key + "=" + this.value;
+ }
+ }
+
+ /* ---------------- Iterator -------------- */
+
+ private static final class IteratorState {
Review Comment:
ditto
##########
hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/util/collection/IntMapByDynamicHash.java:
##########
@@ -0,0 +1,899 @@
+/*
+ * 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.hugegraph.util.collection;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
+
+import sun.misc.Unsafe;
+
+public class IntMapByDynamicHash implements IntMap {
+
+ private static final int DEFAULT_INITIAL_CAPACITY = 16;
+
+ /**
+ * The maximum capacity, used if a higher value is implicitly specified
+ * by either of the constructors with arguments.
+ * MUST be a power of two <= 1<<30.
+ */
+ private static final int MAXIMUM_CAPACITY = 1 << 30;
+
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private static final int PARTITIONED_SIZE_THRESHOLD = 4096;
+
+ private static final int NULL_VALUE = Integer.MIN_VALUE;
+
+ private static final AtomicReferenceFieldUpdater<IntMapByDynamicHash, Entry[]>
+ TABLE_UPDATER =
+ AtomicReferenceFieldUpdater.newUpdater(IntMapByDynamicHash.class, Entry[].class,
+ "table");
+
+ private volatile Entry[] table;
+
+ /**
+ * Partition counting to improve the concurrency performance of addToSize()
+ */
+ private int[] partitionedSize;
+
+ private static final Entry RESIZING = new Entry(NULL_VALUE, NULL_VALUE, 1);
+ private static final Entry RESIZED = new Entry(NULL_VALUE, NULL_VALUE, 2);
+
+ private static final Entry RESIZE_SENTINEL = new Entry(NULL_VALUE, NULL_VALUE, 3);
+
+ /**
+ * must be 2^n - 1
+ */
+ private static final int SIZE_BUCKETS = 7;
+
+
+ /* ---------------- Table element access -------------- */
+ private static Object tableAt(Object[] array, int index) {
+ return UNSAFE.getObjectVolatile(array,
+ ((long) index << ENTRY_ARRAY_SHIFT) +
+ ENTRY_ARRAY_BASE);
+ }
+
+ private static boolean casTableAt(Object[] array, int index, Object expected, Object newValue) {
+ return UNSAFE.compareAndSwapObject(
+ array,
+ ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ expected,
+ newValue);
+ }
+
+ private static void setTableAt(Object[] array, int index, Object newValue) {
+ UNSAFE.putObjectVolatile(array, ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ newValue);
+ }
+
+ private static int tableSizeFor(int c) {
+ int n = c - 1;
+ n |= n >>> 1;
+ n |= n >>> 2;
+ n |= n >>> 4;
+ n |= n >>> 8;
+ n |= n >>> 16;
+ return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
+ }
+
+ /**
+ * updated via atomic field updater
+ */
+ @SuppressWarnings("UnusedDeclaration")
+ private volatile int size;
+
+ public IntMapByDynamicHash() {
+ this(DEFAULT_INITIAL_CAPACITY);
+ }
+
+ public IntMapByDynamicHash(int initialCapacity) {
+ if (initialCapacity < 0) {
+ throw new IllegalArgumentException("Illegal Initial Capacity: " + initialCapacity);
+ }
+ if (initialCapacity > MAXIMUM_CAPACITY) {
+ initialCapacity = MAXIMUM_CAPACITY;
+ }
+ long size = (long) (1.0 + (long) initialCapacity / LOAD_FACTOR);
+ int cap = (size >= (long) MAXIMUM_CAPACITY) ?
+ MAXIMUM_CAPACITY : tableSizeFor((int) size);
+ if (cap >= PARTITIONED_SIZE_THRESHOLD) {
+ // we want 7 extra slots and 64 bytes for each
+ // slot. int is 4 bytes, so 64 bytes is 16 ints.
+ this.partitionedSize =
+ new int[SIZE_BUCKETS * 16];
+ }
+ // The end index is for resizeContainer
+ this.table = new Entry[cap + 1];
+ }
+
+ @Override
+ public boolean put(int key, int value) {
+ int hash = this.hash(key);
+ Entry[] currentArray = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == null) {
+ Entry newEntry = new Entry(key, value);
+ this.addToSize(1);
+ if (IntMapByDynamicHash.casTableAt(currentArray, hash, null, newEntry)) {
+ return true;
+ }
+ this.addToSize(-1);
+ }
+
+ this.slowPut(key, value, currentArray);
+ return true;
+ }
+
+ private int slowPut(int key, int value, Entry[] currentTable) {
+ int length;
+ int index;
+ Entry o;
+
+ while (true) {
+ length = currentTable.length;
+ index = this.hash(key, length);
+ o = (Entry) IntMapByDynamicHash.tableAt(currentTable, index);
+
+ if (o == RESIZED || o == RESIZING) {
+ currentTable = this.helpWithResizeWhileCurrentIndex(currentTable, index);
+ } else {
+ Entry e = o;
+ boolean found = false;
+
+ // Search for the key in the chain
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ found = true;
+ break;
+ }
+ e = e.getNext();
+ }
+
+ if (found) {
+ int oldVal = e.getValue();
+ // Key found, replace the entry
+ Entry newEntry =
+ new Entry(key, value, this.createReplacementChainForRemoval(o, e));
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, newEntry)) {
+ return oldVal;
+ }
+ } else {
+ // Key not found, add a new entry
+ Entry newEntry = new Entry(key, value, o);
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, newEntry)) {
+ this.incrementSizeAndPossiblyResize(currentTable, length, o);
+ return NULL_VALUE;
+ }
+ }
+ }
+ }
+ }
+
+ @Override
+ public int get(int key) {
+ int hash = this.hash(key);
+ Entry[] currentArray = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == RESIZED || o == RESIZING) {
+ return this.slowGet(key, currentArray);
+ }
+ for (Entry e = o; e != null; e = e.getNext()) {
+ int k;
+ if ((k = e.getKey()) == key || key == k) {
+ return e.value;
+ }
+ }
+ return NULL_VALUE;
+ }
+
+ private int slowGet(int key, Entry[] currentArray) {
+ while (true) {
+ int length = currentArray.length;
+ int hash = this.hash(key, length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = this.helpWithResizeWhileCurrentIndex(currentArray, hash);
+ } else {
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ return e.getValue();
+ }
+ e = e.getNext();
+ }
+ return NULL_VALUE;
+ }
+ }
+ }
+
+ @Override
+ public boolean remove(int key) {
+ int hash = this.hash(key);
+ Entry[] currentTable = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentTable, hash);
+ if (o == RESIZED || o == RESIZING) {
+ return this.slowRemove(key, currentTable) != null;
+ }
+
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ Entry replacement = this.createReplacementChainForRemoval(o, e);
+ if (IntMapByDynamicHash.casTableAt(currentTable, hash, o, replacement)) {
+ this.addToSize(-1);
+ return true;
+ }
+ return this.slowRemove(key, currentTable) != null;
+ }
+ e = e.getNext();
+ }
+ return false;
+ }
+
+ private Entry slowRemove(int key, Entry[] currentTable) {
+ int length;
+ int index;
+ Entry o;
+
+ while (true) {
+ length = currentTable.length;
+ index = this.hash(key, length);
+ o = (Entry) IntMapByDynamicHash.tableAt(currentTable, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentTable = this.helpWithResizeWhileCurrentIndex(currentTable, index);
+ } else {
+ Entry e = o;
+ Entry prev = null;
+
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ Entry replacement = this.createReplacementChainForRemoval(o, e);
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, replacement)) {
+ this.addToSize(-1);
+ return e;
+ }
+ // Key found, but CAS failed, restart the loop
+ break;
+ }
+ prev = e;
+ e = e.getNext();
+ }
+
+ if (prev != null) {
+ // Key not found
+ return null;
+ }
+ }
+ }
+ }
+
+ @Override
+ public boolean containsKey(int key) {
+ return this.getEntry(key) != null;
+ }
+
+ @Override
+ public IntIterator keys() {
+ return new KeyIterator();
+ }
+
+ @Override
+ public IntIterator values() {
+ return new ValueIterator();
+ }
+
+ @Override
+ public void clear() {
+ Entry[] currentArray = this.table;
+ ResizeContainer resizeContainer;
+ do {
+ resizeContainer = null;
+ for (int i = 0; i < currentArray.length - 1; i++) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, i);
+ if (o == RESIZED || o == RESIZING) {
+ resizeContainer = (ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ currentArray.length -
+ 1);
+ } else if (o != null) {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(currentArray, i, o, null)) {
+ int removedEntries = 0;
+ while (e != null) {
+ removedEntries++;
+ e = e.getNext();
+ }
+ this.addToSize(-removedEntries);
+ }
+ }
+ }
+ if (resizeContainer != null) {
+ if (resizeContainer.isNotDone()) {
+ this.helpWithResize(currentArray);
+ resizeContainer.waitForAllResizers();
+ }
+ currentArray = resizeContainer.nextArray;
+ }
+ } while (resizeContainer != null);
+ }
+
+ @Override
+ public int size() {
+ int localSize = this.size;
+ if (this.partitionedSize != null) {
+ for (int i = 0; i < SIZE_BUCKETS; i++) {
+ localSize += this.partitionedSize[i << 4];
+ }
+ }
+ return localSize;
+ }
+
+ @Override
+ public boolean concurrent() {
+ return true;
+ }
+
+ private int hash(int key) {
+ return key & (table.length - 2);
+ }
+
+ private int hash(int key, int length) {
+ return key & (length - 2);
+ }
+
+ private Entry getEntry(int key) {
+ Entry[] currentArray = this.table;
+ while (true) {
+ int length = currentArray.length;
+ int index = this.hash(key, length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = this.helpWithResizeWhileCurrentIndex(currentArray, index);
+ } else {
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ return e;
+ }
+ e = e.getNext();
+ }
+ return null;
+ }
+ }
+ }
+
+ private void addToSize(int value) {
+ if (this.partitionedSize != null) {
+ if (this.incrementPartitionedSize(value)) {
+ return;
+ }
+ }
+ this.incrementLocalSize(value);
+ }
+
+ private boolean incrementPartitionedSize(int value) {
+ int h = (int) Thread.currentThread().getId();
+ h ^= (h >>> 18) ^ (h >>> 12);
+ h = (h ^ (h >>> 10)) & SIZE_BUCKETS;
+ if (h != 0) {
+ h = (h - 1) << 4;
+ long address = ((long) h << INT_ARRAY_SHIFT) + INT_ARRAY_BASE;
+ while (true) {
+ int localSize = UNSAFE.getIntVolatile(this.partitionedSize, address);
+ if (UNSAFE.compareAndSwapInt(this.partitionedSize, address, localSize,
+ localSize + value)) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ private void incrementLocalSize(int value) {
+ while (true) {
+ int localSize = this.size;
+ if (UNSAFE.compareAndSwapInt(this, SIZE_OFFSET, localSize, localSize + value)) {
+ break;
+ }
+ }
+ }
+
+ private Entry createReplacementChainForRemoval(Entry original,
+ Entry toRemove) {
+ if (original == toRemove) {
+ return original.getNext();
+ }
+ Entry replacement = null;
+ Entry e = original;
+ while (e != null) {
+ if (e != toRemove) {
+ replacement = new Entry(e.getKey(), e.getValue(), replacement);
+ }
+ e = e.getNext();
+ }
+ return replacement;
+ }
+
+ private void incrementSizeAndPossiblyResize(Entry[] currentArray, int length, Entry prev) {
+ this.addToSize(1);
+ if (prev != null) {
+ int localSize = this.size();
+ int threshold = (int) (length * LOAD_FACTOR); // threshold = length * 0.75
+ if (localSize + 1 > threshold) {
+ this.resize(currentArray);
+ }
+ }
+ }
+
+ private Entry[] helpWithResizeWhileCurrentIndex(Entry[] currentArray, int index) {
+ Entry[] newArray = this.helpWithResize(currentArray);
+ int helpCount = 0;
+ while (IntMapByDynamicHash.tableAt(currentArray, index) != RESIZED) {
+ helpCount++;
+ newArray = this.helpWithResize(currentArray);
+ if ((helpCount & 7) == 0) {
+ Thread.yield();
+ }
+ }
+ return newArray;
+ }
+
+ private void resize(Entry[] oldTable) {
+ this.resize(oldTable, (oldTable.length - 1 << 1) + 1);
+ }
+
+ // newSize must be a power of 2 + 1
+ @SuppressWarnings("JLM_JSR166_UTILCONCURRENT_MONITORENTER")
+ private void resize(Entry[] oldTable, int newSize) {
+ int oldCapacity = oldTable.length;
+ int end = oldCapacity - 1;
+ Entry last = (Entry) IntMapByDynamicHash.tableAt(oldTable, end);
+ if (this.size() < end && last == RESIZE_SENTINEL) {
+ return;
+ }
+ if (oldCapacity >= MAXIMUM_CAPACITY) {
+ throw new RuntimeException("max capacity of map exceeded");
+ }
+ ResizeContainer resizeContainer = null;
+ // This ownResize records whether current thread need to perform the expansion operation of
+ // the map by itself
+ boolean ownResize = false;
+ if (last == null || last == RESIZE_SENTINEL) {
+ // allocating a new array is too expensive to make this an atomic operation
+ synchronized (oldTable) {
+ if (IntMapByDynamicHash.tableAt(oldTable, end) == null) {
+ IntMapByDynamicHash.setTableAt(oldTable, end, RESIZE_SENTINEL);
+ if (this.partitionedSize == null && newSize >= PARTITIONED_SIZE_THRESHOLD) {
+ this.partitionedSize = new int[SIZE_BUCKETS * 16];
+ }
+ resizeContainer = new ResizeContainer(new Entry[newSize], oldTable.length - 1);
+ IntMapByDynamicHash.setTableAt(oldTable, end, resizeContainer);
+ ownResize = true;
+ }
+ }
+ }
+ if (ownResize) {
+ this.transfer(oldTable, resizeContainer);
+
+ Entry[] src = this.table;
+ while (!TABLE_UPDATER.compareAndSet(this, oldTable, resizeContainer.nextArray)) {
+ /*
+ we're in a double resize situation; we'll have to go help until it's our turn
+ to set the table
+ */
+ if (src != oldTable) {
+ this.helpWithResize(src);
+ }
+ }
+ } else {
+ this.helpWithResize(oldTable);
+ }
+ }
+
+ /**
+ * Transfer all entries from src to dest tables
+ */
+ private void transfer(Entry[] src, ResizeContainer resizeContainer) {
+ Entry[] dest = resizeContainer.nextArray;
+
+ for (int j = 0; j < src.length - 1; ) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(src, j);
+ if (o == null) {
+ if (IntMapByDynamicHash.casTableAt(src, j, null, RESIZED)) {
+ j++;
+ }
+ } else if (o == RESIZED || o == RESIZING) {
+ /*
+ During the expansion process, other threads have already migrated the elements at
+ this location to the new array. This means that the elements in the current
+ position have already been processed and do not need to be migrated again.
+ */
+ j = (j & ~(ResizeContainer.QUEUE_INCREMENT - 1)) + ResizeContainer.QUEUE_INCREMENT;
+ /*
+ When there is only one thread for expansion, there is no concurrency issue
+ and there is no need to wait.
+ */
+ if (resizeContainer.resizers.get() == 1) {
+ break;
+ }
+ } else {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(src, j, o, RESIZING)) {
+ while (e != null) {
+ this.unconditionalCopy(dest, e);
+ e = e.getNext();
+ }
+ IntMapByDynamicHash.setTableAt(src, j, RESIZED);
+ j++;
+ }
+ }
+ }
+ resizeContainer.decrementResizerAndNotify();
+ resizeContainer.waitForAllResizers();
+ }
+
+ /**
+ * Enable the current thread to participate in the expansion
+ */
+ private Entry[] helpWithResize(Entry[] currentArray) {
+ ResizeContainer resizeContainer =
+ (ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ currentArray.length - 1);
+ Entry[] newTable = resizeContainer.nextArray;
+ if (resizeContainer.getQueuePosition() > ResizeContainer.QUEUE_INCREMENT) {
+ resizeContainer.incrementResizer();
+ this.reverseTransfer(currentArray, resizeContainer);
+ resizeContainer.decrementResizerAndNotify();
+ }
+ return newTable;
+ }
+
+ private void reverseTransfer(Entry[] src, ResizeContainer resizeContainer) {
+ Entry[] dest = resizeContainer.nextArray;
+ while (resizeContainer.getQueuePosition() > 0) {
+ int start = resizeContainer.subtractAndGetQueuePosition();
+ int end = start + ResizeContainer.QUEUE_INCREMENT;
+ if (end > 0) {
+ if (start < 0) {
+ start = 0;
+ }
+ for (int j = end - 1; j >= start; ) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(src, j);
+ if (o == null) {
+ if (IntMapByDynamicHash.casTableAt(src, j, null, RESIZED)) {
+ j--;
+ }
+ } else if (o == RESIZED || o == RESIZING) {
+ resizeContainer.zeroOutQueuePosition();
+ return;
+ } else {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(src, j, o, RESIZING)) {
+ while (e != null) {
+ this.unconditionalCopy(dest, e);
+ e = e.getNext();
+ }
+ IntMapByDynamicHash.setTableAt(src, j, RESIZED);
+ j--;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ private void unconditionalCopy(Entry[] dest, Entry toCopyEntry) {
+ Entry[] currentArray = dest;
+ while (true) {
+ int length = currentArray.length;
+ int index = this.hash(toCopyEntry.getKey(), length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = ((ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ length -
+ 1)).nextArray;
+ } else {
+ Entry newEntry;
+ if (o == null) {
+ if (toCopyEntry.getNext() == null) {
+ newEntry = toCopyEntry; // no need to duplicate
+ } else {
+ newEntry = new Entry(toCopyEntry.getKey(), toCopyEntry.getValue());
+ }
+ } else {
+ newEntry =
+ new Entry(toCopyEntry.getKey(), toCopyEntry.getValue(), o);
+ }
+ if (IntMapByDynamicHash.casTableAt(currentArray, index, o, newEntry)) {
+ return;
+ }
+ }
+ }
+ }
+
+ private static final class ResizeContainer extends Entry {
+ private static final int QUEUE_INCREMENT =
+ Math.min(1 << 10,
+ Integer.highestOneBit(Runtime.getRuntime().availableProcessors()) << 4);
+ private final AtomicInteger resizers = new AtomicInteger(1);
+ private final Entry[] nextArray;
+ private final AtomicInteger queuePosition;
+
+ private ResizeContainer(Entry[] nextArray, int oldSize) {
+ super(NULL_VALUE, NULL_VALUE, 4);
+ this.nextArray = nextArray;
+ this.queuePosition = new AtomicInteger(oldSize);
+ }
+
+ public void incrementResizer() {
+ this.resizers.incrementAndGet();
+ }
+
+ public void decrementResizerAndNotify() {
+ int remaining = this.resizers.decrementAndGet();
+ if (remaining == 0) {
+ synchronized (this) {
+ this.notifyAll();
+ }
+ }
+ }
+
+ public int getQueuePosition() {
+ return this.queuePosition.get();
+ }
+
+ public int subtractAndGetQueuePosition() {
+ return this.queuePosition.addAndGet(-QUEUE_INCREMENT);
+ }
+
+ public void waitForAllResizers() {
+ if (this.resizers.get() > 0) {
+ for (int i = 0; i < 16; i++) {
+ if (this.resizers.get() == 0) {
+ break;
+ }
+ }
+ for (int i = 0; i < 16; i++) {
+ if (this.resizers.get() == 0) {
+ break;
+ }
+ Thread.yield();
+ }
+ }
+ if (this.resizers.get() > 0) {
+ synchronized (this) {
+ while (this.resizers.get() > 0) {
+ try {
+ this.wait();
+ } catch (InterruptedException e) {
+ //ginore
+ }
+ }
+ }
+ }
+ }
+
+ public boolean isNotDone() {
+ return this.resizers.get() > 0;
+ }
+
+ public void zeroOutQueuePosition() {
+ this.queuePosition.set(0);
+ }
+ }
+
+ private static class Entry {
+ final int key;
+ volatile int value;
+ volatile Entry next;
+
+ /**
+ * 0 NORMAL
+ * 1 RESIZING
+ * 2 RESIZED
+ * 3 RESIZE_SENTINEL
+ * 4 ResizeContainer
Review Comment:
please also keep capital style
##########
hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/util/collection/IntMapByDynamicHash.java:
##########
@@ -0,0 +1,899 @@
+/*
+ * 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.hugegraph.util.collection;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
+
+import sun.misc.Unsafe;
+
+public class IntMapByDynamicHash implements IntMap {
+
+ private static final int DEFAULT_INITIAL_CAPACITY = 16;
+
+ /**
+ * The maximum capacity, used if a higher value is implicitly specified
+ * by either of the constructors with arguments.
+ * MUST be a power of two <= 1<<30.
+ */
+ private static final int MAXIMUM_CAPACITY = 1 << 30;
+
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private static final int PARTITIONED_SIZE_THRESHOLD = 4096;
+
+ private static final int NULL_VALUE = Integer.MIN_VALUE;
+
+ private static final AtomicReferenceFieldUpdater<IntMapByDynamicHash, Entry[]>
+ TABLE_UPDATER =
+ AtomicReferenceFieldUpdater.newUpdater(IntMapByDynamicHash.class, Entry[].class,
+ "table");
+
+ private volatile Entry[] table;
+
+ /**
+ * Partition counting to improve the concurrency performance of addToSize()
+ */
+ private int[] partitionedSize;
+
+ private static final Entry RESIZING = new Entry(NULL_VALUE, NULL_VALUE, 1);
+ private static final Entry RESIZED = new Entry(NULL_VALUE, NULL_VALUE, 2);
+
+ private static final Entry RESIZE_SENTINEL = new Entry(NULL_VALUE, NULL_VALUE, 3);
+
+ /**
+ * must be 2^n - 1
+ */
+ private static final int SIZE_BUCKETS = 7;
+
+
+ /* ---------------- Table element access -------------- */
+ private static Object tableAt(Object[] array, int index) {
+ return UNSAFE.getObjectVolatile(array,
+ ((long) index << ENTRY_ARRAY_SHIFT) +
+ ENTRY_ARRAY_BASE);
+ }
+
+ private static boolean casTableAt(Object[] array, int index, Object expected, Object newValue) {
+ return UNSAFE.compareAndSwapObject(
+ array,
+ ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ expected,
+ newValue);
+ }
+
+ private static void setTableAt(Object[] array, int index, Object newValue) {
+ UNSAFE.putObjectVolatile(array, ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ newValue);
+ }
+
+ private static int tableSizeFor(int c) {
+ int n = c - 1;
+ n |= n >>> 1;
+ n |= n >>> 2;
+ n |= n >>> 4;
+ n |= n >>> 8;
+ n |= n >>> 16;
+ return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
+ }
+
+ /**
+ * updated via atomic field updater
+ */
+ @SuppressWarnings("UnusedDeclaration")
+ private volatile int size;
+
+ public IntMapByDynamicHash() {
+ this(DEFAULT_INITIAL_CAPACITY);
+ }
+
+ public IntMapByDynamicHash(int initialCapacity) {
+ if (initialCapacity < 0) {
+ throw new IllegalArgumentException("Illegal Initial Capacity: " + initialCapacity);
+ }
+ if (initialCapacity > MAXIMUM_CAPACITY) {
+ initialCapacity = MAXIMUM_CAPACITY;
+ }
+ long size = (long) (1.0 + (long) initialCapacity / LOAD_FACTOR);
+ int cap = (size >= (long) MAXIMUM_CAPACITY) ?
+ MAXIMUM_CAPACITY : tableSizeFor((int) size);
+ if (cap >= PARTITIONED_SIZE_THRESHOLD) {
+ // we want 7 extra slots and 64 bytes for each
+ // slot. int is 4 bytes, so 64 bytes is 16 ints.
+ this.partitionedSize =
+ new int[SIZE_BUCKETS * 16];
+ }
+ // The end index is for resizeContainer
+ this.table = new Entry[cap + 1];
+ }
+
+ @Override
+ public boolean put(int key, int value) {
+ int hash = this.hash(key);
+ Entry[] currentArray = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == null) {
+ Entry newEntry = new Entry(key, value);
+ this.addToSize(1);
+ if (IntMapByDynamicHash.casTableAt(currentArray, hash, null, newEntry)) {
+ return true;
+ }
+ this.addToSize(-1);
+ }
+
+ this.slowPut(key, value, currentArray);
+ return true;
+ }
+
+ private int slowPut(int key, int value, Entry[] currentTable) {
+ int length;
+ int index;
+ Entry o;
+
+ while (true) {
+ length = currentTable.length;
+ index = this.hash(key, length);
+ o = (Entry) IntMapByDynamicHash.tableAt(currentTable, index);
+
+ if (o == RESIZED || o == RESIZING) {
+ currentTable = this.helpWithResizeWhileCurrentIndex(currentTable, index);
+ } else {
+ Entry e = o;
+ boolean found = false;
+
+ // Search for the key in the chain
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ found = true;
+ break;
+ }
+ e = e.getNext();
+ }
+
+ if (found) {
+ int oldVal = e.getValue();
+ // Key found, replace the entry
+ Entry newEntry =
+ new Entry(key, value, this.createReplacementChainForRemoval(o, e));
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, newEntry)) {
+ return oldVal;
+ }
+ } else {
+ // Key not found, add a new entry
+ Entry newEntry = new Entry(key, value, o);
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, newEntry)) {
+ this.incrementSizeAndPossiblyResize(currentTable, length, o);
+ return NULL_VALUE;
+ }
+ }
+ }
+ }
+ }
+
+ @Override
+ public int get(int key) {
+ int hash = this.hash(key);
+ Entry[] currentArray = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == RESIZED || o == RESIZING) {
+ return this.slowGet(key, currentArray);
+ }
+ for (Entry e = o; e != null; e = e.getNext()) {
+ int k;
+ if ((k = e.getKey()) == key || key == k) {
+ return e.value;
+ }
+ }
+ return NULL_VALUE;
+ }
+
+ private int slowGet(int key, Entry[] currentArray) {
+ while (true) {
+ int length = currentArray.length;
+ int hash = this.hash(key, length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = this.helpWithResizeWhileCurrentIndex(currentArray, hash);
+ } else {
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ return e.getValue();
+ }
+ e = e.getNext();
+ }
+ return NULL_VALUE;
+ }
+ }
+ }
+
+ @Override
+ public boolean remove(int key) {
+ int hash = this.hash(key);
+ Entry[] currentTable = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentTable, hash);
+ if (o == RESIZED || o == RESIZING) {
+ return this.slowRemove(key, currentTable) != null;
+ }
+
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ Entry replacement = this.createReplacementChainForRemoval(o, e);
+ if (IntMapByDynamicHash.casTableAt(currentTable, hash, o, replacement)) {
+ this.addToSize(-1);
+ return true;
+ }
+ return this.slowRemove(key, currentTable) != null;
+ }
+ e = e.getNext();
+ }
+ return false;
+ }
+
+ private Entry slowRemove(int key, Entry[] currentTable) {
+ int length;
+ int index;
+ Entry o;
+
+ while (true) {
+ length = currentTable.length;
+ index = this.hash(key, length);
+ o = (Entry) IntMapByDynamicHash.tableAt(currentTable, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentTable = this.helpWithResizeWhileCurrentIndex(currentTable, index);
+ } else {
+ Entry e = o;
+ Entry prev = null;
+
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ Entry replacement = this.createReplacementChainForRemoval(o, e);
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, replacement)) {
+ this.addToSize(-1);
+ return e;
+ }
+ // Key found, but CAS failed, restart the loop
+ break;
+ }
+ prev = e;
+ e = e.getNext();
+ }
+
+ if (prev != null) {
+ // Key not found
+ return null;
+ }
+ }
+ }
+ }
+
+ @Override
+ public boolean containsKey(int key) {
+ return this.getEntry(key) != null;
+ }
+
+ @Override
+ public IntIterator keys() {
+ return new KeyIterator();
+ }
+
+ @Override
+ public IntIterator values() {
+ return new ValueIterator();
+ }
+
+ @Override
+ public void clear() {
+ Entry[] currentArray = this.table;
+ ResizeContainer resizeContainer;
+ do {
+ resizeContainer = null;
+ for (int i = 0; i < currentArray.length - 1; i++) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, i);
+ if (o == RESIZED || o == RESIZING) {
+ resizeContainer = (ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ currentArray.length -
+ 1);
+ } else if (o != null) {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(currentArray, i, o, null)) {
+ int removedEntries = 0;
+ while (e != null) {
+ removedEntries++;
+ e = e.getNext();
+ }
+ this.addToSize(-removedEntries);
+ }
+ }
+ }
+ if (resizeContainer != null) {
+ if (resizeContainer.isNotDone()) {
+ this.helpWithResize(currentArray);
+ resizeContainer.waitForAllResizers();
+ }
+ currentArray = resizeContainer.nextArray;
+ }
+ } while (resizeContainer != null);
+ }
+
+ @Override
+ public int size() {
+ int localSize = this.size;
+ if (this.partitionedSize != null) {
+ for (int i = 0; i < SIZE_BUCKETS; i++) {
+ localSize += this.partitionedSize[i << 4];
+ }
+ }
+ return localSize;
+ }
+
+ @Override
+ public boolean concurrent() {
+ return true;
+ }
+
+ private int hash(int key) {
+ return key & (table.length - 2);
+ }
+
+ private int hash(int key, int length) {
+ return key & (length - 2);
+ }
+
+ private Entry getEntry(int key) {
+ Entry[] currentArray = this.table;
+ while (true) {
+ int length = currentArray.length;
+ int index = this.hash(key, length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = this.helpWithResizeWhileCurrentIndex(currentArray, index);
+ } else {
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ return e;
+ }
+ e = e.getNext();
+ }
+ return null;
+ }
+ }
+ }
+
+ private void addToSize(int value) {
+ if (this.partitionedSize != null) {
+ if (this.incrementPartitionedSize(value)) {
+ return;
+ }
+ }
+ this.incrementLocalSize(value);
+ }
+
+ private boolean incrementPartitionedSize(int value) {
+ int h = (int) Thread.currentThread().getId();
+ h ^= (h >>> 18) ^ (h >>> 12);
+ h = (h ^ (h >>> 10)) & SIZE_BUCKETS;
+ if (h != 0) {
+ h = (h - 1) << 4;
+ long address = ((long) h << INT_ARRAY_SHIFT) + INT_ARRAY_BASE;
+ while (true) {
+ int localSize = UNSAFE.getIntVolatile(this.partitionedSize, address);
+ if (UNSAFE.compareAndSwapInt(this.partitionedSize, address, localSize,
+ localSize + value)) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ private void incrementLocalSize(int value) {
+ while (true) {
+ int localSize = this.size;
+ if (UNSAFE.compareAndSwapInt(this, SIZE_OFFSET, localSize, localSize + value)) {
+ break;
+ }
+ }
+ }
+
+ private Entry createReplacementChainForRemoval(Entry original,
+ Entry toRemove) {
+ if (original == toRemove) {
+ return original.getNext();
+ }
+ Entry replacement = null;
+ Entry e = original;
+ while (e != null) {
+ if (e != toRemove) {
+ replacement = new Entry(e.getKey(), e.getValue(), replacement);
+ }
+ e = e.getNext();
+ }
+ return replacement;
+ }
+
+ private void incrementSizeAndPossiblyResize(Entry[] currentArray, int length, Entry prev) {
+ this.addToSize(1);
+ if (prev != null) {
+ int localSize = this.size();
+ int threshold = (int) (length * LOAD_FACTOR); // threshold = length * 0.75
+ if (localSize + 1 > threshold) {
+ this.resize(currentArray);
+ }
+ }
+ }
+
+ private Entry[] helpWithResizeWhileCurrentIndex(Entry[] currentArray, int index) {
+ Entry[] newArray = this.helpWithResize(currentArray);
+ int helpCount = 0;
+ while (IntMapByDynamicHash.tableAt(currentArray, index) != RESIZED) {
+ helpCount++;
+ newArray = this.helpWithResize(currentArray);
+ if ((helpCount & 7) == 0) {
+ Thread.yield();
+ }
+ }
+ return newArray;
+ }
+
+ private void resize(Entry[] oldTable) {
+ this.resize(oldTable, (oldTable.length - 1 << 1) + 1);
+ }
+
+ // newSize must be a power of 2 + 1
+ @SuppressWarnings("JLM_JSR166_UTILCONCURRENT_MONITORENTER")
+ private void resize(Entry[] oldTable, int newSize) {
+ int oldCapacity = oldTable.length;
+ int end = oldCapacity - 1;
+ Entry last = (Entry) IntMapByDynamicHash.tableAt(oldTable, end);
+ if (this.size() < end && last == RESIZE_SENTINEL) {
+ return;
+ }
+ if (oldCapacity >= MAXIMUM_CAPACITY) {
+ throw new RuntimeException("max capacity of map exceeded");
+ }
+ ResizeContainer resizeContainer = null;
+ // This ownResize records whether current thread need to perform the expansion operation of
+ // the map by itself
+ boolean ownResize = false;
+ if (last == null || last == RESIZE_SENTINEL) {
+ // allocating a new array is too expensive to make this an atomic operation
+ synchronized (oldTable) {
+ if (IntMapByDynamicHash.tableAt(oldTable, end) == null) {
+ IntMapByDynamicHash.setTableAt(oldTable, end, RESIZE_SENTINEL);
+ if (this.partitionedSize == null && newSize >= PARTITIONED_SIZE_THRESHOLD) {
+ this.partitionedSize = new int[SIZE_BUCKETS * 16];
+ }
+ resizeContainer = new ResizeContainer(new Entry[newSize], oldTable.length - 1);
+ IntMapByDynamicHash.setTableAt(oldTable, end, resizeContainer);
+ ownResize = true;
+ }
+ }
+ }
+ if (ownResize) {
+ this.transfer(oldTable, resizeContainer);
+
+ Entry[] src = this.table;
+ while (!TABLE_UPDATER.compareAndSet(this, oldTable, resizeContainer.nextArray)) {
+ /*
+ we're in a double resize situation; we'll have to go help until it's our turn
+ to set the table
+ */
+ if (src != oldTable) {
+ this.helpWithResize(src);
+ }
+ }
+ } else {
+ this.helpWithResize(oldTable);
+ }
+ }
+
+ /**
+ * Transfer all entries from src to dest tables
+ */
+ private void transfer(Entry[] src, ResizeContainer resizeContainer) {
+ Entry[] dest = resizeContainer.nextArray;
+
+ for (int j = 0; j < src.length - 1; ) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(src, j);
+ if (o == null) {
+ if (IntMapByDynamicHash.casTableAt(src, j, null, RESIZED)) {
+ j++;
+ }
+ } else if (o == RESIZED || o == RESIZING) {
+ /*
+ During the expansion process, other threads have already migrated the elements at
+ this location to the new array. This means that the elements in the current
+ position have already been processed and do not need to be migrated again.
+ */
+ j = (j & ~(ResizeContainer.QUEUE_INCREMENT - 1)) + ResizeContainer.QUEUE_INCREMENT;
+ /*
+ When there is only one thread for expansion, there is no concurrency issue
+ and there is no need to wait.
+ */
+ if (resizeContainer.resizers.get() == 1) {
+ break;
+ }
+ } else {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(src, j, o, RESIZING)) {
+ while (e != null) {
+ this.unconditionalCopy(dest, e);
+ e = e.getNext();
+ }
+ IntMapByDynamicHash.setTableAt(src, j, RESIZED);
+ j++;
+ }
+ }
+ }
+ resizeContainer.decrementResizerAndNotify();
+ resizeContainer.waitForAllResizers();
+ }
+
+ /**
+ * Enable the current thread to participate in the expansion
+ */
+ private Entry[] helpWithResize(Entry[] currentArray) {
+ ResizeContainer resizeContainer =
+ (ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ currentArray.length - 1);
+ Entry[] newTable = resizeContainer.nextArray;
+ if (resizeContainer.getQueuePosition() > ResizeContainer.QUEUE_INCREMENT) {
+ resizeContainer.incrementResizer();
+ this.reverseTransfer(currentArray, resizeContainer);
+ resizeContainer.decrementResizerAndNotify();
+ }
+ return newTable;
+ }
+
+ private void reverseTransfer(Entry[] src, ResizeContainer resizeContainer) {
+ Entry[] dest = resizeContainer.nextArray;
+ while (resizeContainer.getQueuePosition() > 0) {
+ int start = resizeContainer.subtractAndGetQueuePosition();
+ int end = start + ResizeContainer.QUEUE_INCREMENT;
+ if (end > 0) {
+ if (start < 0) {
+ start = 0;
+ }
+ for (int j = end - 1; j >= start; ) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(src, j);
+ if (o == null) {
+ if (IntMapByDynamicHash.casTableAt(src, j, null, RESIZED)) {
+ j--;
+ }
+ } else if (o == RESIZED || o == RESIZING) {
+ resizeContainer.zeroOutQueuePosition();
+ return;
+ } else {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(src, j, o, RESIZING)) {
+ while (e != null) {
+ this.unconditionalCopy(dest, e);
+ e = e.getNext();
+ }
+ IntMapByDynamicHash.setTableAt(src, j, RESIZED);
+ j--;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ private void unconditionalCopy(Entry[] dest, Entry toCopyEntry) {
+ Entry[] currentArray = dest;
+ while (true) {
+ int length = currentArray.length;
+ int index = this.hash(toCopyEntry.getKey(), length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = ((ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ length -
+ 1)).nextArray;
+ } else {
+ Entry newEntry;
+ if (o == null) {
+ if (toCopyEntry.getNext() == null) {
+ newEntry = toCopyEntry; // no need to duplicate
+ } else {
+ newEntry = new Entry(toCopyEntry.getKey(), toCopyEntry.getValue());
+ }
+ } else {
+ newEntry =
+ new Entry(toCopyEntry.getKey(), toCopyEntry.getValue(), o);
+ }
+ if (IntMapByDynamicHash.casTableAt(currentArray, index, o, newEntry)) {
+ return;
+ }
+ }
+ }
+ }
+
+ private static final class ResizeContainer extends Entry {
+ private static final int QUEUE_INCREMENT =
+ Math.min(1 << 10,
+ Integer.highestOneBit(Runtime.getRuntime().availableProcessors()) << 4);
+ private final AtomicInteger resizers = new AtomicInteger(1);
+ private final Entry[] nextArray;
+ private final AtomicInteger queuePosition;
+
+ private ResizeContainer(Entry[] nextArray, int oldSize) {
+ super(NULL_VALUE, NULL_VALUE, 4);
+ this.nextArray = nextArray;
+ this.queuePosition = new AtomicInteger(oldSize);
+ }
+
+ public void incrementResizer() {
+ this.resizers.incrementAndGet();
+ }
+
+ public void decrementResizerAndNotify() {
+ int remaining = this.resizers.decrementAndGet();
+ if (remaining == 0) {
+ synchronized (this) {
+ this.notifyAll();
+ }
+ }
+ }
+
+ public int getQueuePosition() {
+ return this.queuePosition.get();
+ }
+
+ public int subtractAndGetQueuePosition() {
+ return this.queuePosition.addAndGet(-QUEUE_INCREMENT);
+ }
+
+ public void waitForAllResizers() {
+ if (this.resizers.get() > 0) {
+ for (int i = 0; i < 16; i++) {
+ if (this.resizers.get() == 0) {
+ break;
+ }
+ }
+ for (int i = 0; i < 16; i++) {
+ if (this.resizers.get() == 0) {
+ break;
+ }
+ Thread.yield();
+ }
+ }
+ if (this.resizers.get() > 0) {
+ synchronized (this) {
+ while (this.resizers.get() > 0) {
+ try {
+ this.wait();
+ } catch (InterruptedException e) {
+ //ginore
+ }
+ }
+ }
+ }
+ }
+
+ public boolean isNotDone() {
+ return this.resizers.get() > 0;
+ }
+
+ public void zeroOutQueuePosition() {
+ this.queuePosition.set(0);
+ }
+ }
+
+ private static class Entry {
Review Comment:
expect a blank line
##########
hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/util/collection/IntMapByDynamicHash.java:
##########
@@ -0,0 +1,899 @@
+/*
+ * 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.hugegraph.util.collection;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
+
+import sun.misc.Unsafe;
+
+public class IntMapByDynamicHash implements IntMap {
+
+ private static final int DEFAULT_INITIAL_CAPACITY = 16;
+
+ /**
+ * The maximum capacity, used if a higher value is implicitly specified
+ * by either of the constructors with arguments.
+ * MUST be a power of two <= 1<<30.
+ */
+ private static final int MAXIMUM_CAPACITY = 1 << 30;
+
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private static final int PARTITIONED_SIZE_THRESHOLD = 4096;
+
+ private static final int NULL_VALUE = Integer.MIN_VALUE;
+
+ private static final AtomicReferenceFieldUpdater<IntMapByDynamicHash, Entry[]>
+ TABLE_UPDATER =
+ AtomicReferenceFieldUpdater.newUpdater(IntMapByDynamicHash.class, Entry[].class,
+ "table");
+
+ private volatile Entry[] table;
+
+ /**
+ * Partition counting to improve the concurrency performance of addToSize()
+ */
+ private int[] partitionedSize;
+
+ private static final Entry RESIZING = new Entry(NULL_VALUE, NULL_VALUE, 1);
+ private static final Entry RESIZED = new Entry(NULL_VALUE, NULL_VALUE, 2);
+
+ private static final Entry RESIZE_SENTINEL = new Entry(NULL_VALUE, NULL_VALUE, 3);
+
+ /**
+ * must be 2^n - 1
+ */
+ private static final int SIZE_BUCKETS = 7;
+
+
+ /* ---------------- Table element access -------------- */
+ private static Object tableAt(Object[] array, int index) {
+ return UNSAFE.getObjectVolatile(array,
+ ((long) index << ENTRY_ARRAY_SHIFT) +
+ ENTRY_ARRAY_BASE);
+ }
+
+ private static boolean casTableAt(Object[] array, int index, Object expected, Object newValue) {
+ return UNSAFE.compareAndSwapObject(
+ array,
+ ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ expected,
+ newValue);
+ }
+
+ private static void setTableAt(Object[] array, int index, Object newValue) {
+ UNSAFE.putObjectVolatile(array, ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ newValue);
+ }
+
+ private static int tableSizeFor(int c) {
+ int n = c - 1;
+ n |= n >>> 1;
+ n |= n >>> 2;
+ n |= n >>> 4;
+ n |= n >>> 8;
+ n |= n >>> 16;
+ return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
+ }
+
+ /**
+ * updated via atomic field updater
+ */
+ @SuppressWarnings("UnusedDeclaration")
+ private volatile int size;
+
+ public IntMapByDynamicHash() {
+ this(DEFAULT_INITIAL_CAPACITY);
+ }
+
+ public IntMapByDynamicHash(int initialCapacity) {
+ if (initialCapacity < 0) {
+ throw new IllegalArgumentException("Illegal Initial Capacity: " + initialCapacity);
+ }
+ if (initialCapacity > MAXIMUM_CAPACITY) {
+ initialCapacity = MAXIMUM_CAPACITY;
+ }
+ long size = (long) (1.0 + (long) initialCapacity / LOAD_FACTOR);
+ int cap = (size >= (long) MAXIMUM_CAPACITY) ?
+ MAXIMUM_CAPACITY : tableSizeFor((int) size);
+ if (cap >= PARTITIONED_SIZE_THRESHOLD) {
+ // we want 7 extra slots and 64 bytes for each
+ // slot. int is 4 bytes, so 64 bytes is 16 ints.
+ this.partitionedSize =
+ new int[SIZE_BUCKETS * 16];
+ }
+ // The end index is for resizeContainer
+ this.table = new Entry[cap + 1];
+ }
+
+ @Override
+ public boolean put(int key, int value) {
+ int hash = this.hash(key);
+ Entry[] currentArray = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == null) {
+ Entry newEntry = new Entry(key, value);
+ this.addToSize(1);
+ if (IntMapByDynamicHash.casTableAt(currentArray, hash, null, newEntry)) {
+ return true;
+ }
+ this.addToSize(-1);
+ }
+
+ this.slowPut(key, value, currentArray);
+ return true;
+ }
+
+ private int slowPut(int key, int value, Entry[] currentTable) {
+ int length;
+ int index;
+ Entry o;
+
+ while (true) {
+ length = currentTable.length;
+ index = this.hash(key, length);
+ o = (Entry) IntMapByDynamicHash.tableAt(currentTable, index);
+
+ if (o == RESIZED || o == RESIZING) {
+ currentTable = this.helpWithResizeWhileCurrentIndex(currentTable, index);
+ } else {
+ Entry e = o;
+ boolean found = false;
+
+ // Search for the key in the chain
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ found = true;
+ break;
+ }
+ e = e.getNext();
+ }
+
+ if (found) {
+ int oldVal = e.getValue();
+ // Key found, replace the entry
+ Entry newEntry =
+ new Entry(key, value, this.createReplacementChainForRemoval(o, e));
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, newEntry)) {
+ return oldVal;
+ }
+ } else {
+ // Key not found, add a new entry
+ Entry newEntry = new Entry(key, value, o);
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, newEntry)) {
+ this.incrementSizeAndPossiblyResize(currentTable, length, o);
+ return NULL_VALUE;
+ }
+ }
+ }
+ }
+ }
+
+ @Override
+ public int get(int key) {
+ int hash = this.hash(key);
+ Entry[] currentArray = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == RESIZED || o == RESIZING) {
+ return this.slowGet(key, currentArray);
+ }
+ for (Entry e = o; e != null; e = e.getNext()) {
+ int k;
+ if ((k = e.getKey()) == key || key == k) {
+ return e.value;
+ }
+ }
+ return NULL_VALUE;
+ }
+
+ private int slowGet(int key, Entry[] currentArray) {
+ while (true) {
+ int length = currentArray.length;
+ int hash = this.hash(key, length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = this.helpWithResizeWhileCurrentIndex(currentArray, hash);
+ } else {
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ return e.getValue();
+ }
+ e = e.getNext();
+ }
+ return NULL_VALUE;
+ }
+ }
+ }
+
+ @Override
+ public boolean remove(int key) {
+ int hash = this.hash(key);
+ Entry[] currentTable = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentTable, hash);
+ if (o == RESIZED || o == RESIZING) {
+ return this.slowRemove(key, currentTable) != null;
+ }
+
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ Entry replacement = this.createReplacementChainForRemoval(o, e);
+ if (IntMapByDynamicHash.casTableAt(currentTable, hash, o, replacement)) {
+ this.addToSize(-1);
+ return true;
+ }
+ return this.slowRemove(key, currentTable) != null;
+ }
+ e = e.getNext();
+ }
+ return false;
+ }
+
+ private Entry slowRemove(int key, Entry[] currentTable) {
+ int length;
+ int index;
+ Entry o;
+
+ while (true) {
+ length = currentTable.length;
+ index = this.hash(key, length);
+ o = (Entry) IntMapByDynamicHash.tableAt(currentTable, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentTable = this.helpWithResizeWhileCurrentIndex(currentTable, index);
+ } else {
+ Entry e = o;
+ Entry prev = null;
+
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ Entry replacement = this.createReplacementChainForRemoval(o, e);
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, replacement)) {
+ this.addToSize(-1);
+ return e;
+ }
+ // Key found, but CAS failed, restart the loop
+ break;
+ }
+ prev = e;
+ e = e.getNext();
+ }
+
+ if (prev != null) {
+ // Key not found
+ return null;
+ }
+ }
+ }
+ }
+
+ @Override
+ public boolean containsKey(int key) {
+ return this.getEntry(key) != null;
+ }
+
+ @Override
+ public IntIterator keys() {
+ return new KeyIterator();
+ }
+
+ @Override
+ public IntIterator values() {
+ return new ValueIterator();
+ }
+
+ @Override
+ public void clear() {
+ Entry[] currentArray = this.table;
+ ResizeContainer resizeContainer;
+ do {
+ resizeContainer = null;
+ for (int i = 0; i < currentArray.length - 1; i++) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, i);
+ if (o == RESIZED || o == RESIZING) {
+ resizeContainer = (ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ currentArray.length -
+ 1);
+ } else if (o != null) {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(currentArray, i, o, null)) {
+ int removedEntries = 0;
+ while (e != null) {
+ removedEntries++;
+ e = e.getNext();
+ }
+ this.addToSize(-removedEntries);
+ }
+ }
+ }
+ if (resizeContainer != null) {
+ if (resizeContainer.isNotDone()) {
+ this.helpWithResize(currentArray);
+ resizeContainer.waitForAllResizers();
+ }
+ currentArray = resizeContainer.nextArray;
+ }
+ } while (resizeContainer != null);
+ }
+
+ @Override
+ public int size() {
+ int localSize = this.size;
+ if (this.partitionedSize != null) {
+ for (int i = 0; i < SIZE_BUCKETS; i++) {
+ localSize += this.partitionedSize[i << 4];
+ }
+ }
+ return localSize;
+ }
+
+ @Override
+ public boolean concurrent() {
+ return true;
+ }
+
+ private int hash(int key) {
+ return key & (table.length - 2);
+ }
+
+ private int hash(int key, int length) {
+ return key & (length - 2);
+ }
+
+ private Entry getEntry(int key) {
+ Entry[] currentArray = this.table;
+ while (true) {
+ int length = currentArray.length;
+ int index = this.hash(key, length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = this.helpWithResizeWhileCurrentIndex(currentArray, index);
+ } else {
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ return e;
+ }
+ e = e.getNext();
+ }
+ return null;
+ }
+ }
+ }
+
+ private void addToSize(int value) {
+ if (this.partitionedSize != null) {
+ if (this.incrementPartitionedSize(value)) {
+ return;
+ }
+ }
+ this.incrementLocalSize(value);
+ }
+
+ private boolean incrementPartitionedSize(int value) {
+ int h = (int) Thread.currentThread().getId();
+ h ^= (h >>> 18) ^ (h >>> 12);
+ h = (h ^ (h >>> 10)) & SIZE_BUCKETS;
+ if (h != 0) {
+ h = (h - 1) << 4;
+ long address = ((long) h << INT_ARRAY_SHIFT) + INT_ARRAY_BASE;
+ while (true) {
+ int localSize = UNSAFE.getIntVolatile(this.partitionedSize, address);
+ if (UNSAFE.compareAndSwapInt(this.partitionedSize, address, localSize,
+ localSize + value)) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ private void incrementLocalSize(int value) {
+ while (true) {
+ int localSize = this.size;
+ if (UNSAFE.compareAndSwapInt(this, SIZE_OFFSET, localSize, localSize + value)) {
+ break;
+ }
+ }
+ }
+
+ private Entry createReplacementChainForRemoval(Entry original,
+ Entry toRemove) {
+ if (original == toRemove) {
+ return original.getNext();
+ }
+ Entry replacement = null;
+ Entry e = original;
+ while (e != null) {
+ if (e != toRemove) {
+ replacement = new Entry(e.getKey(), e.getValue(), replacement);
+ }
+ e = e.getNext();
+ }
+ return replacement;
+ }
+
+ private void incrementSizeAndPossiblyResize(Entry[] currentArray, int length, Entry prev) {
+ this.addToSize(1);
+ if (prev != null) {
+ int localSize = this.size();
+ int threshold = (int) (length * LOAD_FACTOR); // threshold = length * 0.75
+ if (localSize + 1 > threshold) {
+ this.resize(currentArray);
+ }
+ }
+ }
+
+ private Entry[] helpWithResizeWhileCurrentIndex(Entry[] currentArray, int index) {
+ Entry[] newArray = this.helpWithResize(currentArray);
+ int helpCount = 0;
+ while (IntMapByDynamicHash.tableAt(currentArray, index) != RESIZED) {
+ helpCount++;
+ newArray = this.helpWithResize(currentArray);
+ if ((helpCount & 7) == 0) {
+ Thread.yield();
+ }
+ }
+ return newArray;
+ }
+
+ private void resize(Entry[] oldTable) {
+ this.resize(oldTable, (oldTable.length - 1 << 1) + 1);
+ }
+
+ // newSize must be a power of 2 + 1
+ @SuppressWarnings("JLM_JSR166_UTILCONCURRENT_MONITORENTER")
+ private void resize(Entry[] oldTable, int newSize) {
+ int oldCapacity = oldTable.length;
+ int end = oldCapacity - 1;
+ Entry last = (Entry) IntMapByDynamicHash.tableAt(oldTable, end);
+ if (this.size() < end && last == RESIZE_SENTINEL) {
+ return;
+ }
+ if (oldCapacity >= MAXIMUM_CAPACITY) {
+ throw new RuntimeException("max capacity of map exceeded");
+ }
+ ResizeContainer resizeContainer = null;
+ // This ownResize records whether current thread need to perform the expansion operation of
+ // the map by itself
+ boolean ownResize = false;
+ if (last == null || last == RESIZE_SENTINEL) {
+ // allocating a new array is too expensive to make this an atomic operation
+ synchronized (oldTable) {
+ if (IntMapByDynamicHash.tableAt(oldTable, end) == null) {
+ IntMapByDynamicHash.setTableAt(oldTable, end, RESIZE_SENTINEL);
+ if (this.partitionedSize == null && newSize >= PARTITIONED_SIZE_THRESHOLD) {
+ this.partitionedSize = new int[SIZE_BUCKETS * 16];
+ }
+ resizeContainer = new ResizeContainer(new Entry[newSize], oldTable.length - 1);
+ IntMapByDynamicHash.setTableAt(oldTable, end, resizeContainer);
+ ownResize = true;
+ }
+ }
+ }
+ if (ownResize) {
+ this.transfer(oldTable, resizeContainer);
+
+ Entry[] src = this.table;
+ while (!TABLE_UPDATER.compareAndSet(this, oldTable, resizeContainer.nextArray)) {
+ /*
+ we're in a double resize situation; we'll have to go help until it's our turn
+ to set the table
+ */
+ if (src != oldTable) {
+ this.helpWithResize(src);
+ }
+ }
+ } else {
+ this.helpWithResize(oldTable);
+ }
+ }
+
+ /**
+ * Transfer all entries from src to dest tables
+ */
+ private void transfer(Entry[] src, ResizeContainer resizeContainer) {
+ Entry[] dest = resizeContainer.nextArray;
+
+ for (int j = 0; j < src.length - 1; ) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(src, j);
+ if (o == null) {
+ if (IntMapByDynamicHash.casTableAt(src, j, null, RESIZED)) {
+ j++;
+ }
+ } else if (o == RESIZED || o == RESIZING) {
+ /*
+ During the expansion process, other threads have already migrated the elements at
+ this location to the new array. This means that the elements in the current
+ position have already been processed and do not need to be migrated again.
+ */
+ j = (j & ~(ResizeContainer.QUEUE_INCREMENT - 1)) + ResizeContainer.QUEUE_INCREMENT;
+ /*
+ When there is only one thread for expansion, there is no concurrency issue
+ and there is no need to wait.
+ */
+ if (resizeContainer.resizers.get() == 1) {
+ break;
+ }
+ } else {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(src, j, o, RESIZING)) {
+ while (e != null) {
+ this.unconditionalCopy(dest, e);
+ e = e.getNext();
+ }
+ IntMapByDynamicHash.setTableAt(src, j, RESIZED);
+ j++;
+ }
+ }
+ }
+ resizeContainer.decrementResizerAndNotify();
+ resizeContainer.waitForAllResizers();
+ }
+
+ /**
+ * Enable the current thread to participate in the expansion
+ */
+ private Entry[] helpWithResize(Entry[] currentArray) {
+ ResizeContainer resizeContainer =
+ (ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ currentArray.length - 1);
+ Entry[] newTable = resizeContainer.nextArray;
+ if (resizeContainer.getQueuePosition() > ResizeContainer.QUEUE_INCREMENT) {
+ resizeContainer.incrementResizer();
+ this.reverseTransfer(currentArray, resizeContainer);
+ resizeContainer.decrementResizerAndNotify();
+ }
+ return newTable;
+ }
+
+ private void reverseTransfer(Entry[] src, ResizeContainer resizeContainer) {
+ Entry[] dest = resizeContainer.nextArray;
+ while (resizeContainer.getQueuePosition() > 0) {
+ int start = resizeContainer.subtractAndGetQueuePosition();
+ int end = start + ResizeContainer.QUEUE_INCREMENT;
+ if (end > 0) {
+ if (start < 0) {
+ start = 0;
+ }
+ for (int j = end - 1; j >= start; ) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(src, j);
+ if (o == null) {
+ if (IntMapByDynamicHash.casTableAt(src, j, null, RESIZED)) {
+ j--;
+ }
+ } else if (o == RESIZED || o == RESIZING) {
+ resizeContainer.zeroOutQueuePosition();
+ return;
+ } else {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(src, j, o, RESIZING)) {
+ while (e != null) {
+ this.unconditionalCopy(dest, e);
+ e = e.getNext();
+ }
+ IntMapByDynamicHash.setTableAt(src, j, RESIZED);
+ j--;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ private void unconditionalCopy(Entry[] dest, Entry toCopyEntry) {
+ Entry[] currentArray = dest;
+ while (true) {
+ int length = currentArray.length;
+ int index = this.hash(toCopyEntry.getKey(), length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = ((ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ length -
+ 1)).nextArray;
+ } else {
+ Entry newEntry;
+ if (o == null) {
+ if (toCopyEntry.getNext() == null) {
+ newEntry = toCopyEntry; // no need to duplicate
+ } else {
+ newEntry = new Entry(toCopyEntry.getKey(), toCopyEntry.getValue());
+ }
+ } else {
+ newEntry =
+ new Entry(toCopyEntry.getKey(), toCopyEntry.getValue(), o);
+ }
+ if (IntMapByDynamicHash.casTableAt(currentArray, index, o, newEntry)) {
+ return;
+ }
+ }
+ }
+ }
+
+ private static final class ResizeContainer extends Entry {
+ private static final int QUEUE_INCREMENT =
+ Math.min(1 << 10,
+ Integer.highestOneBit(Runtime.getRuntime().availableProcessors()) << 4);
+ private final AtomicInteger resizers = new AtomicInteger(1);
+ private final Entry[] nextArray;
+ private final AtomicInteger queuePosition;
+
+ private ResizeContainer(Entry[] nextArray, int oldSize) {
+ super(NULL_VALUE, NULL_VALUE, 4);
+ this.nextArray = nextArray;
+ this.queuePosition = new AtomicInteger(oldSize);
+ }
+
+ public void incrementResizer() {
+ this.resizers.incrementAndGet();
+ }
+
+ public void decrementResizerAndNotify() {
+ int remaining = this.resizers.decrementAndGet();
+ if (remaining == 0) {
+ synchronized (this) {
+ this.notifyAll();
+ }
+ }
+ }
+
+ public int getQueuePosition() {
+ return this.queuePosition.get();
+ }
+
+ public int subtractAndGetQueuePosition() {
+ return this.queuePosition.addAndGet(-QUEUE_INCREMENT);
+ }
+
+ public void waitForAllResizers() {
+ if (this.resizers.get() > 0) {
+ for (int i = 0; i < 16; i++) {
+ if (this.resizers.get() == 0) {
+ break;
+ }
+ }
+ for (int i = 0; i < 16; i++) {
+ if (this.resizers.get() == 0) {
+ break;
+ }
+ Thread.yield();
+ }
+ }
+ if (this.resizers.get() > 0) {
+ synchronized (this) {
+ while (this.resizers.get() > 0) {
+ try {
+ this.wait();
+ } catch (InterruptedException e) {
+ //ginore
+ }
+ }
+ }
+ }
+ }
+
+ public boolean isNotDone() {
+ return this.resizers.get() > 0;
+ }
+
+ public void zeroOutQueuePosition() {
+ this.queuePosition.set(0);
+ }
+ }
+
+ private static class Entry {
+ final int key;
+ volatile int value;
+ volatile Entry next;
+
+ /**
+ * 0 NORMAL
+ * 1 RESIZING
+ * 2 RESIZED
+ * 3 RESIZE_SENTINEL
+ * 4 ResizeContainer
+ */
+ final int state;
+
+ public Entry(int key, int value, int state) {
+ this.key = key;
+ this.value = value;
+ this.state = state;
+ }
+
+ public Entry(int key, int value) {
+ this.key = key;
+ this.value = value;
+ this.next = null;
+ this.state = 0;
+ }
+
+ public Entry(int key, int value, Entry next) {
+ this.key = key;
+ this.value = value;
+ this.next = next;
+ this.state = 0;
+ }
+
+ public int getKey() {
+ return key;
+ }
+
+ public int getValue() {
+ return value;
+ }
+
+ public Entry getNext() {
+ return next;
+ }
+
+ @Override
+ public String toString() {
+ return this.key + "=" + this.value;
+ }
+ }
+
+ /* ---------------- Iterator -------------- */
+
+ private static final class IteratorState {
+ private Entry[] currentTable;
+ private int start;
+ private int end;
+
+ private IteratorState(Entry[] currentTable) {
+ this.currentTable = currentTable;
+ this.end = this.currentTable.length - 1;
+ }
+
+ private IteratorState(Entry[] currentTable, int start, int end) {
+ this.currentTable = currentTable;
+ this.start = start;
+ this.end = end;
+ }
+ }
+
+ private abstract class HashIterator implements IntIterator {
Review Comment:
ditto
##########
hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/util/collection/IntMapByDynamicHash.java:
##########
@@ -0,0 +1,899 @@
+/*
+ * 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.hugegraph.util.collection;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
+
+import sun.misc.Unsafe;
+
+public class IntMapByDynamicHash implements IntMap {
+
+ private static final int DEFAULT_INITIAL_CAPACITY = 16;
+
+ /**
+ * The maximum capacity, used if a higher value is implicitly specified
+ * by either of the constructors with arguments.
+ * MUST be a power of two <= 1<<30.
+ */
+ private static final int MAXIMUM_CAPACITY = 1 << 30;
+
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private static final int PARTITIONED_SIZE_THRESHOLD = 4096;
+
+ private static final int NULL_VALUE = Integer.MIN_VALUE;
+
+ private static final AtomicReferenceFieldUpdater<IntMapByDynamicHash, Entry[]>
+ TABLE_UPDATER =
+ AtomicReferenceFieldUpdater.newUpdater(IntMapByDynamicHash.class, Entry[].class,
+ "table");
+
+ private volatile Entry[] table;
+
+ /**
+ * Partition counting to improve the concurrency performance of addToSize()
+ */
+ private int[] partitionedSize;
+
+ private static final Entry RESIZING = new Entry(NULL_VALUE, NULL_VALUE, 1);
+ private static final Entry RESIZED = new Entry(NULL_VALUE, NULL_VALUE, 2);
+
+ private static final Entry RESIZE_SENTINEL = new Entry(NULL_VALUE, NULL_VALUE, 3);
+
+ /**
+ * must be 2^n - 1
+ */
+ private static final int SIZE_BUCKETS = 7;
+
+
+ /* ---------------- Table element access -------------- */
+ private static Object tableAt(Object[] array, int index) {
+ return UNSAFE.getObjectVolatile(array,
+ ((long) index << ENTRY_ARRAY_SHIFT) +
+ ENTRY_ARRAY_BASE);
+ }
+
+ private static boolean casTableAt(Object[] array, int index, Object expected, Object newValue) {
+ return UNSAFE.compareAndSwapObject(
+ array,
+ ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
Review Comment:
we can define a local var to shorten the length of the parameter
##########
hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/util/collection/IntMapByDynamicHash.java:
##########
@@ -0,0 +1,899 @@
+/*
+ * 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.hugegraph.util.collection;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
+
+import sun.misc.Unsafe;
+
+public class IntMapByDynamicHash implements IntMap {
+
+ private static final int DEFAULT_INITIAL_CAPACITY = 16;
+
+ /**
+ * The maximum capacity, used if a higher value is implicitly specified
+ * by either of the constructors with arguments.
+ * MUST be a power of two <= 1<<30.
+ */
+ private static final int MAXIMUM_CAPACITY = 1 << 30;
+
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private static final int PARTITIONED_SIZE_THRESHOLD = 4096;
+
+ private static final int NULL_VALUE = Integer.MIN_VALUE;
+
+ private static final AtomicReferenceFieldUpdater<IntMapByDynamicHash, Entry[]>
+ TABLE_UPDATER =
+ AtomicReferenceFieldUpdater.newUpdater(IntMapByDynamicHash.class, Entry[].class,
+ "table");
+
+ private volatile Entry[] table;
+
+ /**
+ * Partition counting to improve the concurrency performance of addToSize()
+ */
+ private int[] partitionedSize;
+
+ private static final Entry RESIZING = new Entry(NULL_VALUE, NULL_VALUE, 1);
+ private static final Entry RESIZED = new Entry(NULL_VALUE, NULL_VALUE, 2);
+
+ private static final Entry RESIZE_SENTINEL = new Entry(NULL_VALUE, NULL_VALUE, 3);
+
+ /**
+ * must be 2^n - 1
+ */
+ private static final int SIZE_BUCKETS = 7;
+
+
+ /* ---------------- Table element access -------------- */
+ private static Object tableAt(Object[] array, int index) {
+ return UNSAFE.getObjectVolatile(array,
+ ((long) index << ENTRY_ARRAY_SHIFT) +
+ ENTRY_ARRAY_BASE);
+ }
+
+ private static boolean casTableAt(Object[] array, int index, Object expected, Object newValue) {
+ return UNSAFE.compareAndSwapObject(
+ array,
+ ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ expected,
+ newValue);
+ }
+
+ private static void setTableAt(Object[] array, int index, Object newValue) {
+ UNSAFE.putObjectVolatile(array, ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ newValue);
+ }
+
+ private static int tableSizeFor(int c) {
+ int n = c - 1;
+ n |= n >>> 1;
+ n |= n >>> 2;
+ n |= n >>> 4;
+ n |= n >>> 8;
+ n |= n >>> 16;
+ return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
+ }
+
+ /**
+ * updated via atomic field updater
+ */
+ @SuppressWarnings("UnusedDeclaration")
+ private volatile int size;
+
+ public IntMapByDynamicHash() {
+ this(DEFAULT_INITIAL_CAPACITY);
+ }
+
+ public IntMapByDynamicHash(int initialCapacity) {
+ if (initialCapacity < 0) {
+ throw new IllegalArgumentException("Illegal Initial Capacity: " + initialCapacity);
+ }
+ if (initialCapacity > MAXIMUM_CAPACITY) {
+ initialCapacity = MAXIMUM_CAPACITY;
+ }
+ long size = (long) (1.0 + (long) initialCapacity / LOAD_FACTOR);
+ int cap = (size >= (long) MAXIMUM_CAPACITY) ?
+ MAXIMUM_CAPACITY : tableSizeFor((int) size);
+ if (cap >= PARTITIONED_SIZE_THRESHOLD) {
+ // we want 7 extra slots and 64 bytes for each
+ // slot. int is 4 bytes, so 64 bytes is 16 ints.
+ this.partitionedSize =
+ new int[SIZE_BUCKETS * 16];
+ }
+ // The end index is for resizeContainer
+ this.table = new Entry[cap + 1];
+ }
+
+ @Override
+ public boolean put(int key, int value) {
+ int hash = this.hash(key);
+ Entry[] currentArray = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == null) {
+ Entry newEntry = new Entry(key, value);
+ this.addToSize(1);
+ if (IntMapByDynamicHash.casTableAt(currentArray, hash, null, newEntry)) {
+ return true;
+ }
+ this.addToSize(-1);
+ }
+
+ this.slowPut(key, value, currentArray);
+ return true;
+ }
+
+ private int slowPut(int key, int value, Entry[] currentTable) {
+ int length;
+ int index;
+ Entry o;
+
+ while (true) {
+ length = currentTable.length;
+ index = this.hash(key, length);
+ o = (Entry) IntMapByDynamicHash.tableAt(currentTable, index);
+
+ if (o == RESIZED || o == RESIZING) {
+ currentTable = this.helpWithResizeWhileCurrentIndex(currentTable, index);
+ } else {
+ Entry e = o;
+ boolean found = false;
+
+ // Search for the key in the chain
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ found = true;
+ break;
+ }
+ e = e.getNext();
+ }
+
+ if (found) {
+ int oldVal = e.getValue();
+ // Key found, replace the entry
+ Entry newEntry =
+ new Entry(key, value, this.createReplacementChainForRemoval(o, e));
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, newEntry)) {
+ return oldVal;
+ }
+ } else {
+ // Key not found, add a new entry
+ Entry newEntry = new Entry(key, value, o);
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, newEntry)) {
+ this.incrementSizeAndPossiblyResize(currentTable, length, o);
+ return NULL_VALUE;
+ }
+ }
+ }
+ }
+ }
+
+ @Override
+ public int get(int key) {
+ int hash = this.hash(key);
+ Entry[] currentArray = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == RESIZED || o == RESIZING) {
+ return this.slowGet(key, currentArray);
+ }
+ for (Entry e = o; e != null; e = e.getNext()) {
+ int k;
+ if ((k = e.getKey()) == key || key == k) {
+ return e.value;
+ }
+ }
+ return NULL_VALUE;
+ }
+
+ private int slowGet(int key, Entry[] currentArray) {
+ while (true) {
+ int length = currentArray.length;
+ int hash = this.hash(key, length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = this.helpWithResizeWhileCurrentIndex(currentArray, hash);
+ } else {
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ return e.getValue();
+ }
+ e = e.getNext();
+ }
+ return NULL_VALUE;
+ }
+ }
+ }
+
+ @Override
+ public boolean remove(int key) {
+ int hash = this.hash(key);
+ Entry[] currentTable = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentTable, hash);
+ if (o == RESIZED || o == RESIZING) {
+ return this.slowRemove(key, currentTable) != null;
+ }
+
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ Entry replacement = this.createReplacementChainForRemoval(o, e);
+ if (IntMapByDynamicHash.casTableAt(currentTable, hash, o, replacement)) {
+ this.addToSize(-1);
+ return true;
+ }
+ return this.slowRemove(key, currentTable) != null;
+ }
+ e = e.getNext();
+ }
+ return false;
+ }
+
+ private Entry slowRemove(int key, Entry[] currentTable) {
+ int length;
+ int index;
+ Entry o;
+
+ while (true) {
+ length = currentTable.length;
+ index = this.hash(key, length);
+ o = (Entry) IntMapByDynamicHash.tableAt(currentTable, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentTable = this.helpWithResizeWhileCurrentIndex(currentTable, index);
+ } else {
+ Entry e = o;
+ Entry prev = null;
+
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ Entry replacement = this.createReplacementChainForRemoval(o, e);
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, replacement)) {
+ this.addToSize(-1);
+ return e;
+ }
+ // Key found, but CAS failed, restart the loop
+ break;
+ }
+ prev = e;
+ e = e.getNext();
+ }
+
+ if (prev != null) {
+ // Key not found
+ return null;
+ }
+ }
+ }
+ }
+
+ @Override
+ public boolean containsKey(int key) {
+ return this.getEntry(key) != null;
+ }
+
+ @Override
+ public IntIterator keys() {
+ return new KeyIterator();
+ }
+
+ @Override
+ public IntIterator values() {
+ return new ValueIterator();
+ }
+
+ @Override
+ public void clear() {
+ Entry[] currentArray = this.table;
+ ResizeContainer resizeContainer;
+ do {
+ resizeContainer = null;
+ for (int i = 0; i < currentArray.length - 1; i++) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, i);
+ if (o == RESIZED || o == RESIZING) {
+ resizeContainer = (ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ currentArray.length -
+ 1);
+ } else if (o != null) {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(currentArray, i, o, null)) {
+ int removedEntries = 0;
+ while (e != null) {
+ removedEntries++;
+ e = e.getNext();
+ }
+ this.addToSize(-removedEntries);
+ }
+ }
+ }
+ if (resizeContainer != null) {
+ if (resizeContainer.isNotDone()) {
+ this.helpWithResize(currentArray);
+ resizeContainer.waitForAllResizers();
+ }
+ currentArray = resizeContainer.nextArray;
+ }
+ } while (resizeContainer != null);
+ }
+
+ @Override
+ public int size() {
+ int localSize = this.size;
+ if (this.partitionedSize != null) {
+ for (int i = 0; i < SIZE_BUCKETS; i++) {
+ localSize += this.partitionedSize[i << 4];
+ }
+ }
+ return localSize;
+ }
+
+ @Override
+ public boolean concurrent() {
+ return true;
+ }
+
+ private int hash(int key) {
+ return key & (table.length - 2);
+ }
+
+ private int hash(int key, int length) {
+ return key & (length - 2);
+ }
+
+ private Entry getEntry(int key) {
+ Entry[] currentArray = this.table;
+ while (true) {
+ int length = currentArray.length;
+ int index = this.hash(key, length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = this.helpWithResizeWhileCurrentIndex(currentArray, index);
+ } else {
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ return e;
+ }
+ e = e.getNext();
+ }
+ return null;
+ }
+ }
+ }
+
+ private void addToSize(int value) {
+ if (this.partitionedSize != null) {
+ if (this.incrementPartitionedSize(value)) {
+ return;
+ }
+ }
+ this.incrementLocalSize(value);
+ }
+
+ private boolean incrementPartitionedSize(int value) {
+ int h = (int) Thread.currentThread().getId();
+ h ^= (h >>> 18) ^ (h >>> 12);
+ h = (h ^ (h >>> 10)) & SIZE_BUCKETS;
+ if (h != 0) {
+ h = (h - 1) << 4;
+ long address = ((long) h << INT_ARRAY_SHIFT) + INT_ARRAY_BASE;
+ while (true) {
+ int localSize = UNSAFE.getIntVolatile(this.partitionedSize, address);
+ if (UNSAFE.compareAndSwapInt(this.partitionedSize, address, localSize,
+ localSize + value)) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ private void incrementLocalSize(int value) {
+ while (true) {
+ int localSize = this.size;
+ if (UNSAFE.compareAndSwapInt(this, SIZE_OFFSET, localSize, localSize + value)) {
+ break;
+ }
+ }
+ }
+
+ private Entry createReplacementChainForRemoval(Entry original,
+ Entry toRemove) {
+ if (original == toRemove) {
+ return original.getNext();
+ }
+ Entry replacement = null;
+ Entry e = original;
+ while (e != null) {
+ if (e != toRemove) {
+ replacement = new Entry(e.getKey(), e.getValue(), replacement);
+ }
+ e = e.getNext();
+ }
+ return replacement;
+ }
+
+ private void incrementSizeAndPossiblyResize(Entry[] currentArray, int length, Entry prev) {
+ this.addToSize(1);
+ if (prev != null) {
+ int localSize = this.size();
+ int threshold = (int) (length * LOAD_FACTOR); // threshold = length * 0.75
+ if (localSize + 1 > threshold) {
+ this.resize(currentArray);
+ }
+ }
+ }
+
+ private Entry[] helpWithResizeWhileCurrentIndex(Entry[] currentArray, int index) {
+ Entry[] newArray = this.helpWithResize(currentArray);
+ int helpCount = 0;
+ while (IntMapByDynamicHash.tableAt(currentArray, index) != RESIZED) {
+ helpCount++;
+ newArray = this.helpWithResize(currentArray);
+ if ((helpCount & 7) == 0) {
+ Thread.yield();
+ }
+ }
+ return newArray;
+ }
+
+ private void resize(Entry[] oldTable) {
+ this.resize(oldTable, (oldTable.length - 1 << 1) + 1);
+ }
+
+ // newSize must be a power of 2 + 1
+ @SuppressWarnings("JLM_JSR166_UTILCONCURRENT_MONITORENTER")
+ private void resize(Entry[] oldTable, int newSize) {
+ int oldCapacity = oldTable.length;
+ int end = oldCapacity - 1;
+ Entry last = (Entry) IntMapByDynamicHash.tableAt(oldTable, end);
+ if (this.size() < end && last == RESIZE_SENTINEL) {
+ return;
+ }
+ if (oldCapacity >= MAXIMUM_CAPACITY) {
+ throw new RuntimeException("max capacity of map exceeded");
+ }
+ ResizeContainer resizeContainer = null;
+ // This ownResize records whether current thread need to perform the expansion operation of
+ // the map by itself
+ boolean ownResize = false;
+ if (last == null || last == RESIZE_SENTINEL) {
+ // allocating a new array is too expensive to make this an atomic operation
+ synchronized (oldTable) {
+ if (IntMapByDynamicHash.tableAt(oldTable, end) == null) {
+ IntMapByDynamicHash.setTableAt(oldTable, end, RESIZE_SENTINEL);
+ if (this.partitionedSize == null && newSize >= PARTITIONED_SIZE_THRESHOLD) {
+ this.partitionedSize = new int[SIZE_BUCKETS * 16];
+ }
+ resizeContainer = new ResizeContainer(new Entry[newSize], oldTable.length - 1);
+ IntMapByDynamicHash.setTableAt(oldTable, end, resizeContainer);
+ ownResize = true;
+ }
+ }
+ }
+ if (ownResize) {
+ this.transfer(oldTable, resizeContainer);
+
+ Entry[] src = this.table;
+ while (!TABLE_UPDATER.compareAndSet(this, oldTable, resizeContainer.nextArray)) {
+ /*
+ we're in a double resize situation; we'll have to go help until it's our turn
+ to set the table
+ */
+ if (src != oldTable) {
+ this.helpWithResize(src);
+ }
+ }
+ } else {
+ this.helpWithResize(oldTable);
+ }
+ }
+
+ /**
+ * Transfer all entries from src to dest tables
+ */
+ private void transfer(Entry[] src, ResizeContainer resizeContainer) {
+ Entry[] dest = resizeContainer.nextArray;
+
+ for (int j = 0; j < src.length - 1; ) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(src, j);
+ if (o == null) {
+ if (IntMapByDynamicHash.casTableAt(src, j, null, RESIZED)) {
+ j++;
+ }
+ } else if (o == RESIZED || o == RESIZING) {
+ /*
+ During the expansion process, other threads have already migrated the elements at
+ this location to the new array. This means that the elements in the current
+ position have already been processed and do not need to be migrated again.
+ */
+ j = (j & ~(ResizeContainer.QUEUE_INCREMENT - 1)) + ResizeContainer.QUEUE_INCREMENT;
+ /*
+ When there is only one thread for expansion, there is no concurrency issue
+ and there is no need to wait.
+ */
+ if (resizeContainer.resizers.get() == 1) {
+ break;
+ }
+ } else {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(src, j, o, RESIZING)) {
+ while (e != null) {
+ this.unconditionalCopy(dest, e);
+ e = e.getNext();
+ }
+ IntMapByDynamicHash.setTableAt(src, j, RESIZED);
+ j++;
+ }
+ }
+ }
+ resizeContainer.decrementResizerAndNotify();
+ resizeContainer.waitForAllResizers();
+ }
+
+ /**
+ * Enable the current thread to participate in the expansion
+ */
+ private Entry[] helpWithResize(Entry[] currentArray) {
+ ResizeContainer resizeContainer =
+ (ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ currentArray.length - 1);
+ Entry[] newTable = resizeContainer.nextArray;
+ if (resizeContainer.getQueuePosition() > ResizeContainer.QUEUE_INCREMENT) {
+ resizeContainer.incrementResizer();
+ this.reverseTransfer(currentArray, resizeContainer);
+ resizeContainer.decrementResizerAndNotify();
+ }
+ return newTable;
+ }
+
+ private void reverseTransfer(Entry[] src, ResizeContainer resizeContainer) {
+ Entry[] dest = resizeContainer.nextArray;
+ while (resizeContainer.getQueuePosition() > 0) {
+ int start = resizeContainer.subtractAndGetQueuePosition();
+ int end = start + ResizeContainer.QUEUE_INCREMENT;
+ if (end > 0) {
+ if (start < 0) {
+ start = 0;
+ }
+ for (int j = end - 1; j >= start; ) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(src, j);
+ if (o == null) {
+ if (IntMapByDynamicHash.casTableAt(src, j, null, RESIZED)) {
+ j--;
+ }
+ } else if (o == RESIZED || o == RESIZING) {
+ resizeContainer.zeroOutQueuePosition();
+ return;
+ } else {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(src, j, o, RESIZING)) {
+ while (e != null) {
+ this.unconditionalCopy(dest, e);
+ e = e.getNext();
+ }
+ IntMapByDynamicHash.setTableAt(src, j, RESIZED);
+ j--;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ private void unconditionalCopy(Entry[] dest, Entry toCopyEntry) {
+ Entry[] currentArray = dest;
+ while (true) {
+ int length = currentArray.length;
+ int index = this.hash(toCopyEntry.getKey(), length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = ((ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ length -
+ 1)).nextArray;
+ } else {
+ Entry newEntry;
+ if (o == null) {
+ if (toCopyEntry.getNext() == null) {
+ newEntry = toCopyEntry; // no need to duplicate
+ } else {
+ newEntry = new Entry(toCopyEntry.getKey(), toCopyEntry.getValue());
+ }
+ } else {
+ newEntry =
+ new Entry(toCopyEntry.getKey(), toCopyEntry.getValue(), o);
+ }
+ if (IntMapByDynamicHash.casTableAt(currentArray, index, o, newEntry)) {
+ return;
+ }
+ }
+ }
+ }
+
+ private static final class ResizeContainer extends Entry {
+ private static final int QUEUE_INCREMENT =
+ Math.min(1 << 10,
+ Integer.highestOneBit(Runtime.getRuntime().availableProcessors()) << 4);
+ private final AtomicInteger resizers = new AtomicInteger(1);
+ private final Entry[] nextArray;
+ private final AtomicInteger queuePosition;
+
+ private ResizeContainer(Entry[] nextArray, int oldSize) {
+ super(NULL_VALUE, NULL_VALUE, 4);
+ this.nextArray = nextArray;
+ this.queuePosition = new AtomicInteger(oldSize);
+ }
+
+ public void incrementResizer() {
+ this.resizers.incrementAndGet();
+ }
+
+ public void decrementResizerAndNotify() {
+ int remaining = this.resizers.decrementAndGet();
+ if (remaining == 0) {
+ synchronized (this) {
+ this.notifyAll();
+ }
+ }
+ }
+
+ public int getQueuePosition() {
+ return this.queuePosition.get();
+ }
+
+ public int subtractAndGetQueuePosition() {
+ return this.queuePosition.addAndGet(-QUEUE_INCREMENT);
+ }
+
+ public void waitForAllResizers() {
+ if (this.resizers.get() > 0) {
+ for (int i = 0; i < 16; i++) {
+ if (this.resizers.get() == 0) {
+ break;
+ }
+ }
+ for (int i = 0; i < 16; i++) {
+ if (this.resizers.get() == 0) {
+ break;
+ }
+ Thread.yield();
+ }
+ }
+ if (this.resizers.get() > 0) {
+ synchronized (this) {
+ while (this.resizers.get() > 0) {
+ try {
+ this.wait();
+ } catch (InterruptedException e) {
+ //ginore
Review Comment:
expect a space `// ginore`
##########
hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/util/collection/IntMapByDynamicHash.java:
##########
@@ -0,0 +1,899 @@
+/*
+ * 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.hugegraph.util.collection;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
+
+import sun.misc.Unsafe;
+
+public class IntMapByDynamicHash implements IntMap {
+
+ private static final int DEFAULT_INITIAL_CAPACITY = 16;
+
+ /**
+ * The maximum capacity, used if a higher value is implicitly specified
+ * by either of the constructors with arguments.
+ * MUST be a power of two <= 1<<30.
+ */
+ private static final int MAXIMUM_CAPACITY = 1 << 30;
+
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private static final int PARTITIONED_SIZE_THRESHOLD = 4096;
+
+ private static final int NULL_VALUE = Integer.MIN_VALUE;
+
+ private static final AtomicReferenceFieldUpdater<IntMapByDynamicHash, Entry[]>
+ TABLE_UPDATER =
+ AtomicReferenceFieldUpdater.newUpdater(IntMapByDynamicHash.class, Entry[].class,
+ "table");
+
+ private volatile Entry[] table;
+
+ /**
+ * Partition counting to improve the concurrency performance of addToSize()
+ */
+ private int[] partitionedSize;
+
+ private static final Entry RESIZING = new Entry(NULL_VALUE, NULL_VALUE, 1);
+ private static final Entry RESIZED = new Entry(NULL_VALUE, NULL_VALUE, 2);
+
+ private static final Entry RESIZE_SENTINEL = new Entry(NULL_VALUE, NULL_VALUE, 3);
+
+ /**
+ * must be 2^n - 1
+ */
+ private static final int SIZE_BUCKETS = 7;
+
+
+ /* ---------------- Table element access -------------- */
+ private static Object tableAt(Object[] array, int index) {
+ return UNSAFE.getObjectVolatile(array,
+ ((long) index << ENTRY_ARRAY_SHIFT) +
+ ENTRY_ARRAY_BASE);
+ }
+
+ private static boolean casTableAt(Object[] array, int index, Object expected, Object newValue) {
+ return UNSAFE.compareAndSwapObject(
+ array,
+ ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ expected,
+ newValue);
+ }
+
+ private static void setTableAt(Object[] array, int index, Object newValue) {
+ UNSAFE.putObjectVolatile(array, ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ newValue);
+ }
+
+ private static int tableSizeFor(int c) {
+ int n = c - 1;
+ n |= n >>> 1;
+ n |= n >>> 2;
+ n |= n >>> 4;
+ n |= n >>> 8;
+ n |= n >>> 16;
+ return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
+ }
+
+ /**
+ * updated via atomic field updater
+ */
+ @SuppressWarnings("UnusedDeclaration")
+ private volatile int size;
+
+ public IntMapByDynamicHash() {
+ this(DEFAULT_INITIAL_CAPACITY);
+ }
+
+ public IntMapByDynamicHash(int initialCapacity) {
+ if (initialCapacity < 0) {
+ throw new IllegalArgumentException("Illegal Initial Capacity: " + initialCapacity);
+ }
+ if (initialCapacity > MAXIMUM_CAPACITY) {
+ initialCapacity = MAXIMUM_CAPACITY;
+ }
+ long size = (long) (1.0 + (long) initialCapacity / LOAD_FACTOR);
+ int cap = (size >= (long) MAXIMUM_CAPACITY) ?
+ MAXIMUM_CAPACITY : tableSizeFor((int) size);
+ if (cap >= PARTITIONED_SIZE_THRESHOLD) {
+ // we want 7 extra slots and 64 bytes for each
+ // slot. int is 4 bytes, so 64 bytes is 16 ints.
+ this.partitionedSize =
+ new int[SIZE_BUCKETS * 16];
+ }
+ // The end index is for resizeContainer
+ this.table = new Entry[cap + 1];
+ }
+
+ @Override
+ public boolean put(int key, int value) {
+ int hash = this.hash(key);
+ Entry[] currentArray = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == null) {
+ Entry newEntry = new Entry(key, value);
+ this.addToSize(1);
+ if (IntMapByDynamicHash.casTableAt(currentArray, hash, null, newEntry)) {
+ return true;
+ }
+ this.addToSize(-1);
+ }
+
+ this.slowPut(key, value, currentArray);
+ return true;
+ }
+
+ private int slowPut(int key, int value, Entry[] currentTable) {
+ int length;
+ int index;
+ Entry o;
+
+ while (true) {
+ length = currentTable.length;
+ index = this.hash(key, length);
+ o = (Entry) IntMapByDynamicHash.tableAt(currentTable, index);
+
+ if (o == RESIZED || o == RESIZING) {
+ currentTable = this.helpWithResizeWhileCurrentIndex(currentTable, index);
+ } else {
+ Entry e = o;
+ boolean found = false;
+
+ // Search for the key in the chain
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ found = true;
+ break;
+ }
+ e = e.getNext();
+ }
+
+ if (found) {
+ int oldVal = e.getValue();
+ // Key found, replace the entry
+ Entry newEntry =
+ new Entry(key, value, this.createReplacementChainForRemoval(o, e));
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, newEntry)) {
+ return oldVal;
+ }
+ } else {
+ // Key not found, add a new entry
+ Entry newEntry = new Entry(key, value, o);
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, newEntry)) {
+ this.incrementSizeAndPossiblyResize(currentTable, length, o);
+ return NULL_VALUE;
+ }
+ }
+ }
+ }
+ }
+
+ @Override
+ public int get(int key) {
+ int hash = this.hash(key);
+ Entry[] currentArray = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == RESIZED || o == RESIZING) {
+ return this.slowGet(key, currentArray);
+ }
+ for (Entry e = o; e != null; e = e.getNext()) {
+ int k;
+ if ((k = e.getKey()) == key || key == k) {
+ return e.value;
+ }
+ }
+ return NULL_VALUE;
+ }
+
+ private int slowGet(int key, Entry[] currentArray) {
+ while (true) {
+ int length = currentArray.length;
+ int hash = this.hash(key, length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = this.helpWithResizeWhileCurrentIndex(currentArray, hash);
+ } else {
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ return e.getValue();
+ }
+ e = e.getNext();
+ }
+ return NULL_VALUE;
+ }
+ }
+ }
+
+ @Override
+ public boolean remove(int key) {
+ int hash = this.hash(key);
+ Entry[] currentTable = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentTable, hash);
+ if (o == RESIZED || o == RESIZING) {
+ return this.slowRemove(key, currentTable) != null;
+ }
+
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ Entry replacement = this.createReplacementChainForRemoval(o, e);
+ if (IntMapByDynamicHash.casTableAt(currentTable, hash, o, replacement)) {
+ this.addToSize(-1);
+ return true;
+ }
+ return this.slowRemove(key, currentTable) != null;
+ }
+ e = e.getNext();
+ }
+ return false;
+ }
+
+ private Entry slowRemove(int key, Entry[] currentTable) {
+ int length;
+ int index;
+ Entry o;
+
+ while (true) {
+ length = currentTable.length;
+ index = this.hash(key, length);
+ o = (Entry) IntMapByDynamicHash.tableAt(currentTable, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentTable = this.helpWithResizeWhileCurrentIndex(currentTable, index);
+ } else {
+ Entry e = o;
+ Entry prev = null;
+
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ Entry replacement = this.createReplacementChainForRemoval(o, e);
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, replacement)) {
+ this.addToSize(-1);
+ return e;
+ }
+ // Key found, but CAS failed, restart the loop
+ break;
+ }
+ prev = e;
+ e = e.getNext();
+ }
+
+ if (prev != null) {
+ // Key not found
+ return null;
+ }
+ }
+ }
+ }
+
+ @Override
+ public boolean containsKey(int key) {
+ return this.getEntry(key) != null;
+ }
+
+ @Override
+ public IntIterator keys() {
+ return new KeyIterator();
+ }
+
+ @Override
+ public IntIterator values() {
+ return new ValueIterator();
+ }
+
+ @Override
+ public void clear() {
+ Entry[] currentArray = this.table;
+ ResizeContainer resizeContainer;
+ do {
+ resizeContainer = null;
+ for (int i = 0; i < currentArray.length - 1; i++) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, i);
+ if (o == RESIZED || o == RESIZING) {
+ resizeContainer = (ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ currentArray.length -
+ 1);
+ } else if (o != null) {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(currentArray, i, o, null)) {
+ int removedEntries = 0;
+ while (e != null) {
+ removedEntries++;
+ e = e.getNext();
+ }
+ this.addToSize(-removedEntries);
+ }
+ }
+ }
+ if (resizeContainer != null) {
+ if (resizeContainer.isNotDone()) {
+ this.helpWithResize(currentArray);
+ resizeContainer.waitForAllResizers();
+ }
+ currentArray = resizeContainer.nextArray;
+ }
+ } while (resizeContainer != null);
+ }
+
+ @Override
+ public int size() {
+ int localSize = this.size;
+ if (this.partitionedSize != null) {
+ for (int i = 0; i < SIZE_BUCKETS; i++) {
+ localSize += this.partitionedSize[i << 4];
+ }
+ }
+ return localSize;
+ }
+
+ @Override
+ public boolean concurrent() {
+ return true;
+ }
+
+ private int hash(int key) {
+ return key & (table.length - 2);
+ }
+
+ private int hash(int key, int length) {
+ return key & (length - 2);
+ }
+
+ private Entry getEntry(int key) {
+ Entry[] currentArray = this.table;
+ while (true) {
+ int length = currentArray.length;
+ int index = this.hash(key, length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = this.helpWithResizeWhileCurrentIndex(currentArray, index);
+ } else {
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ return e;
+ }
+ e = e.getNext();
+ }
+ return null;
+ }
+ }
+ }
+
+ private void addToSize(int value) {
+ if (this.partitionedSize != null) {
+ if (this.incrementPartitionedSize(value)) {
+ return;
+ }
+ }
+ this.incrementLocalSize(value);
+ }
+
+ private boolean incrementPartitionedSize(int value) {
+ int h = (int) Thread.currentThread().getId();
+ h ^= (h >>> 18) ^ (h >>> 12);
+ h = (h ^ (h >>> 10)) & SIZE_BUCKETS;
+ if (h != 0) {
+ h = (h - 1) << 4;
+ long address = ((long) h << INT_ARRAY_SHIFT) + INT_ARRAY_BASE;
+ while (true) {
+ int localSize = UNSAFE.getIntVolatile(this.partitionedSize, address);
+ if (UNSAFE.compareAndSwapInt(this.partitionedSize, address, localSize,
+ localSize + value)) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ private void incrementLocalSize(int value) {
+ while (true) {
+ int localSize = this.size;
+ if (UNSAFE.compareAndSwapInt(this, SIZE_OFFSET, localSize, localSize + value)) {
+ break;
+ }
+ }
+ }
+
+ private Entry createReplacementChainForRemoval(Entry original,
+ Entry toRemove) {
+ if (original == toRemove) {
+ return original.getNext();
+ }
+ Entry replacement = null;
+ Entry e = original;
+ while (e != null) {
+ if (e != toRemove) {
+ replacement = new Entry(e.getKey(), e.getValue(), replacement);
+ }
+ e = e.getNext();
+ }
+ return replacement;
+ }
+
+ private void incrementSizeAndPossiblyResize(Entry[] currentArray, int length, Entry prev) {
+ this.addToSize(1);
+ if (prev != null) {
+ int localSize = this.size();
+ int threshold = (int) (length * LOAD_FACTOR); // threshold = length * 0.75
+ if (localSize + 1 > threshold) {
+ this.resize(currentArray);
+ }
+ }
+ }
+
+ private Entry[] helpWithResizeWhileCurrentIndex(Entry[] currentArray, int index) {
+ Entry[] newArray = this.helpWithResize(currentArray);
+ int helpCount = 0;
+ while (IntMapByDynamicHash.tableAt(currentArray, index) != RESIZED) {
+ helpCount++;
+ newArray = this.helpWithResize(currentArray);
+ if ((helpCount & 7) == 0) {
+ Thread.yield();
+ }
+ }
+ return newArray;
+ }
+
+ private void resize(Entry[] oldTable) {
+ this.resize(oldTable, (oldTable.length - 1 << 1) + 1);
+ }
+
+ // newSize must be a power of 2 + 1
+ @SuppressWarnings("JLM_JSR166_UTILCONCURRENT_MONITORENTER")
+ private void resize(Entry[] oldTable, int newSize) {
+ int oldCapacity = oldTable.length;
+ int end = oldCapacity - 1;
+ Entry last = (Entry) IntMapByDynamicHash.tableAt(oldTable, end);
+ if (this.size() < end && last == RESIZE_SENTINEL) {
+ return;
+ }
+ if (oldCapacity >= MAXIMUM_CAPACITY) {
+ throw new RuntimeException("max capacity of map exceeded");
+ }
+ ResizeContainer resizeContainer = null;
+ // This ownResize records whether current thread need to perform the expansion operation of
+ // the map by itself
+ boolean ownResize = false;
+ if (last == null || last == RESIZE_SENTINEL) {
+ // allocating a new array is too expensive to make this an atomic operation
+ synchronized (oldTable) {
+ if (IntMapByDynamicHash.tableAt(oldTable, end) == null) {
+ IntMapByDynamicHash.setTableAt(oldTable, end, RESIZE_SENTINEL);
+ if (this.partitionedSize == null && newSize >= PARTITIONED_SIZE_THRESHOLD) {
+ this.partitionedSize = new int[SIZE_BUCKETS * 16];
+ }
+ resizeContainer = new ResizeContainer(new Entry[newSize], oldTable.length - 1);
+ IntMapByDynamicHash.setTableAt(oldTable, end, resizeContainer);
+ ownResize = true;
+ }
+ }
+ }
+ if (ownResize) {
+ this.transfer(oldTable, resizeContainer);
+
+ Entry[] src = this.table;
+ while (!TABLE_UPDATER.compareAndSet(this, oldTable, resizeContainer.nextArray)) {
+ /*
+ we're in a double resize situation; we'll have to go help until it's our turn
+ to set the table
+ */
+ if (src != oldTable) {
+ this.helpWithResize(src);
+ }
+ }
+ } else {
+ this.helpWithResize(oldTable);
+ }
+ }
+
+ /**
+ * Transfer all entries from src to dest tables
+ */
+ private void transfer(Entry[] src, ResizeContainer resizeContainer) {
+ Entry[] dest = resizeContainer.nextArray;
+
+ for (int j = 0; j < src.length - 1; ) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(src, j);
+ if (o == null) {
+ if (IntMapByDynamicHash.casTableAt(src, j, null, RESIZED)) {
+ j++;
+ }
+ } else if (o == RESIZED || o == RESIZING) {
+ /*
+ During the expansion process, other threads have already migrated the elements at
+ this location to the new array. This means that the elements in the current
+ position have already been processed and do not need to be migrated again.
+ */
+ j = (j & ~(ResizeContainer.QUEUE_INCREMENT - 1)) + ResizeContainer.QUEUE_INCREMENT;
+ /*
+ When there is only one thread for expansion, there is no concurrency issue
+ and there is no need to wait.
+ */
+ if (resizeContainer.resizers.get() == 1) {
+ break;
+ }
+ } else {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(src, j, o, RESIZING)) {
+ while (e != null) {
+ this.unconditionalCopy(dest, e);
+ e = e.getNext();
+ }
+ IntMapByDynamicHash.setTableAt(src, j, RESIZED);
+ j++;
+ }
+ }
+ }
+ resizeContainer.decrementResizerAndNotify();
+ resizeContainer.waitForAllResizers();
+ }
+
+ /**
+ * Enable the current thread to participate in the expansion
+ */
+ private Entry[] helpWithResize(Entry[] currentArray) {
+ ResizeContainer resizeContainer =
+ (ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ currentArray.length - 1);
+ Entry[] newTable = resizeContainer.nextArray;
+ if (resizeContainer.getQueuePosition() > ResizeContainer.QUEUE_INCREMENT) {
+ resizeContainer.incrementResizer();
+ this.reverseTransfer(currentArray, resizeContainer);
+ resizeContainer.decrementResizerAndNotify();
+ }
+ return newTable;
+ }
+
+ private void reverseTransfer(Entry[] src, ResizeContainer resizeContainer) {
+ Entry[] dest = resizeContainer.nextArray;
+ while (resizeContainer.getQueuePosition() > 0) {
+ int start = resizeContainer.subtractAndGetQueuePosition();
+ int end = start + ResizeContainer.QUEUE_INCREMENT;
+ if (end > 0) {
+ if (start < 0) {
+ start = 0;
+ }
+ for (int j = end - 1; j >= start; ) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(src, j);
+ if (o == null) {
+ if (IntMapByDynamicHash.casTableAt(src, j, null, RESIZED)) {
+ j--;
+ }
+ } else if (o == RESIZED || o == RESIZING) {
+ resizeContainer.zeroOutQueuePosition();
+ return;
+ } else {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(src, j, o, RESIZING)) {
+ while (e != null) {
+ this.unconditionalCopy(dest, e);
+ e = e.getNext();
+ }
+ IntMapByDynamicHash.setTableAt(src, j, RESIZED);
+ j--;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ private void unconditionalCopy(Entry[] dest, Entry toCopyEntry) {
+ Entry[] currentArray = dest;
+ while (true) {
+ int length = currentArray.length;
+ int index = this.hash(toCopyEntry.getKey(), length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = ((ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ length -
+ 1)).nextArray;
+ } else {
+ Entry newEntry;
+ if (o == null) {
+ if (toCopyEntry.getNext() == null) {
+ newEntry = toCopyEntry; // no need to duplicate
+ } else {
+ newEntry = new Entry(toCopyEntry.getKey(), toCopyEntry.getValue());
+ }
+ } else {
+ newEntry =
+ new Entry(toCopyEntry.getKey(), toCopyEntry.getValue(), o);
+ }
+ if (IntMapByDynamicHash.casTableAt(currentArray, index, o, newEntry)) {
+ return;
+ }
+ }
+ }
+ }
+
+ private static final class ResizeContainer extends Entry {
+ private static final int QUEUE_INCREMENT =
+ Math.min(1 << 10,
+ Integer.highestOneBit(Runtime.getRuntime().availableProcessors()) << 4);
+ private final AtomicInteger resizers = new AtomicInteger(1);
+ private final Entry[] nextArray;
+ private final AtomicInteger queuePosition;
+
+ private ResizeContainer(Entry[] nextArray, int oldSize) {
+ super(NULL_VALUE, NULL_VALUE, 4);
+ this.nextArray = nextArray;
+ this.queuePosition = new AtomicInteger(oldSize);
+ }
+
+ public void incrementResizer() {
+ this.resizers.incrementAndGet();
+ }
+
+ public void decrementResizerAndNotify() {
+ int remaining = this.resizers.decrementAndGet();
+ if (remaining == 0) {
+ synchronized (this) {
+ this.notifyAll();
+ }
+ }
+ }
+
+ public int getQueuePosition() {
+ return this.queuePosition.get();
+ }
+
+ public int subtractAndGetQueuePosition() {
+ return this.queuePosition.addAndGet(-QUEUE_INCREMENT);
+ }
+
+ public void waitForAllResizers() {
+ if (this.resizers.get() > 0) {
+ for (int i = 0; i < 16; i++) {
+ if (this.resizers.get() == 0) {
+ break;
+ }
+ }
+ for (int i = 0; i < 16; i++) {
+ if (this.resizers.get() == 0) {
+ break;
+ }
+ Thread.yield();
+ }
+ }
+ if (this.resizers.get() > 0) {
+ synchronized (this) {
+ while (this.resizers.get() > 0) {
+ try {
+ this.wait();
+ } catch (InterruptedException e) {
+ //ginore
+ }
+ }
+ }
+ }
+ }
+
+ public boolean isNotDone() {
+ return this.resizers.get() > 0;
+ }
+
+ public void zeroOutQueuePosition() {
+ this.queuePosition.set(0);
+ }
+ }
+
+ private static class Entry {
+ final int key;
+ volatile int value;
+ volatile Entry next;
+
+ /**
+ * 0 NORMAL
+ * 1 RESIZING
+ * 2 RESIZED
+ * 3 RESIZE_SENTINEL
+ * 4 ResizeContainer
+ */
+ final int state;
Review Comment:
can we use 1 8 bits var
##########
hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/util/collection/IntMapByDynamicHash.java:
##########
@@ -0,0 +1,899 @@
+/*
+ * 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.hugegraph.util.collection;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
+
+import sun.misc.Unsafe;
+
+public class IntMapByDynamicHash implements IntMap {
+
+ private static final int DEFAULT_INITIAL_CAPACITY = 16;
+
+ /**
+ * The maximum capacity, used if a higher value is implicitly specified
+ * by either of the constructors with arguments.
+ * MUST be a power of two <= 1<<30.
+ */
+ private static final int MAXIMUM_CAPACITY = 1 << 30;
+
+ private static final float LOAD_FACTOR = 0.75f;
+
+ private static final int PARTITIONED_SIZE_THRESHOLD = 4096;
+
+ private static final int NULL_VALUE = Integer.MIN_VALUE;
+
+ private static final AtomicReferenceFieldUpdater<IntMapByDynamicHash, Entry[]>
+ TABLE_UPDATER =
+ AtomicReferenceFieldUpdater.newUpdater(IntMapByDynamicHash.class, Entry[].class,
+ "table");
+
+ private volatile Entry[] table;
+
+ /**
+ * Partition counting to improve the concurrency performance of addToSize()
+ */
+ private int[] partitionedSize;
+
+ private static final Entry RESIZING = new Entry(NULL_VALUE, NULL_VALUE, 1);
+ private static final Entry RESIZED = new Entry(NULL_VALUE, NULL_VALUE, 2);
+
+ private static final Entry RESIZE_SENTINEL = new Entry(NULL_VALUE, NULL_VALUE, 3);
+
+ /**
+ * must be 2^n - 1
+ */
+ private static final int SIZE_BUCKETS = 7;
+
+
+ /* ---------------- Table element access -------------- */
+ private static Object tableAt(Object[] array, int index) {
+ return UNSAFE.getObjectVolatile(array,
+ ((long) index << ENTRY_ARRAY_SHIFT) +
+ ENTRY_ARRAY_BASE);
+ }
+
+ private static boolean casTableAt(Object[] array, int index, Object expected, Object newValue) {
+ return UNSAFE.compareAndSwapObject(
+ array,
+ ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ expected,
+ newValue);
+ }
+
+ private static void setTableAt(Object[] array, int index, Object newValue) {
+ UNSAFE.putObjectVolatile(array, ((long) index << ENTRY_ARRAY_SHIFT) + ENTRY_ARRAY_BASE,
+ newValue);
+ }
+
+ private static int tableSizeFor(int c) {
+ int n = c - 1;
+ n |= n >>> 1;
+ n |= n >>> 2;
+ n |= n >>> 4;
+ n |= n >>> 8;
+ n |= n >>> 16;
+ return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
+ }
+
+ /**
+ * updated via atomic field updater
+ */
+ @SuppressWarnings("UnusedDeclaration")
+ private volatile int size;
+
+ public IntMapByDynamicHash() {
+ this(DEFAULT_INITIAL_CAPACITY);
+ }
+
+ public IntMapByDynamicHash(int initialCapacity) {
+ if (initialCapacity < 0) {
+ throw new IllegalArgumentException("Illegal Initial Capacity: " + initialCapacity);
+ }
+ if (initialCapacity > MAXIMUM_CAPACITY) {
+ initialCapacity = MAXIMUM_CAPACITY;
+ }
+ long size = (long) (1.0 + (long) initialCapacity / LOAD_FACTOR);
+ int cap = (size >= (long) MAXIMUM_CAPACITY) ?
+ MAXIMUM_CAPACITY : tableSizeFor((int) size);
+ if (cap >= PARTITIONED_SIZE_THRESHOLD) {
+ // we want 7 extra slots and 64 bytes for each
+ // slot. int is 4 bytes, so 64 bytes is 16 ints.
+ this.partitionedSize =
+ new int[SIZE_BUCKETS * 16];
+ }
+ // The end index is for resizeContainer
+ this.table = new Entry[cap + 1];
+ }
+
+ @Override
+ public boolean put(int key, int value) {
+ int hash = this.hash(key);
+ Entry[] currentArray = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == null) {
+ Entry newEntry = new Entry(key, value);
+ this.addToSize(1);
+ if (IntMapByDynamicHash.casTableAt(currentArray, hash, null, newEntry)) {
+ return true;
+ }
+ this.addToSize(-1);
+ }
+
+ this.slowPut(key, value, currentArray);
+ return true;
+ }
+
+ private int slowPut(int key, int value, Entry[] currentTable) {
+ int length;
+ int index;
+ Entry o;
+
+ while (true) {
+ length = currentTable.length;
+ index = this.hash(key, length);
+ o = (Entry) IntMapByDynamicHash.tableAt(currentTable, index);
+
+ if (o == RESIZED || o == RESIZING) {
+ currentTable = this.helpWithResizeWhileCurrentIndex(currentTable, index);
+ } else {
+ Entry e = o;
+ boolean found = false;
+
+ // Search for the key in the chain
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ found = true;
+ break;
+ }
+ e = e.getNext();
+ }
+
+ if (found) {
+ int oldVal = e.getValue();
+ // Key found, replace the entry
+ Entry newEntry =
+ new Entry(key, value, this.createReplacementChainForRemoval(o, e));
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, newEntry)) {
+ return oldVal;
+ }
+ } else {
+ // Key not found, add a new entry
+ Entry newEntry = new Entry(key, value, o);
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, newEntry)) {
+ this.incrementSizeAndPossiblyResize(currentTable, length, o);
+ return NULL_VALUE;
+ }
+ }
+ }
+ }
+ }
+
+ @Override
+ public int get(int key) {
+ int hash = this.hash(key);
+ Entry[] currentArray = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == RESIZED || o == RESIZING) {
+ return this.slowGet(key, currentArray);
+ }
+ for (Entry e = o; e != null; e = e.getNext()) {
+ int k;
+ if ((k = e.getKey()) == key || key == k) {
+ return e.value;
+ }
+ }
+ return NULL_VALUE;
+ }
+
+ private int slowGet(int key, Entry[] currentArray) {
+ while (true) {
+ int length = currentArray.length;
+ int hash = this.hash(key, length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, hash);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = this.helpWithResizeWhileCurrentIndex(currentArray, hash);
+ } else {
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ return e.getValue();
+ }
+ e = e.getNext();
+ }
+ return NULL_VALUE;
+ }
+ }
+ }
+
+ @Override
+ public boolean remove(int key) {
+ int hash = this.hash(key);
+ Entry[] currentTable = this.table;
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentTable, hash);
+ if (o == RESIZED || o == RESIZING) {
+ return this.slowRemove(key, currentTable) != null;
+ }
+
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ Entry replacement = this.createReplacementChainForRemoval(o, e);
+ if (IntMapByDynamicHash.casTableAt(currentTable, hash, o, replacement)) {
+ this.addToSize(-1);
+ return true;
+ }
+ return this.slowRemove(key, currentTable) != null;
+ }
+ e = e.getNext();
+ }
+ return false;
+ }
+
+ private Entry slowRemove(int key, Entry[] currentTable) {
+ int length;
+ int index;
+ Entry o;
+
+ while (true) {
+ length = currentTable.length;
+ index = this.hash(key, length);
+ o = (Entry) IntMapByDynamicHash.tableAt(currentTable, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentTable = this.helpWithResizeWhileCurrentIndex(currentTable, index);
+ } else {
+ Entry e = o;
+ Entry prev = null;
+
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ Entry replacement = this.createReplacementChainForRemoval(o, e);
+ if (IntMapByDynamicHash.casTableAt(currentTable, index, o, replacement)) {
+ this.addToSize(-1);
+ return e;
+ }
+ // Key found, but CAS failed, restart the loop
+ break;
+ }
+ prev = e;
+ e = e.getNext();
+ }
+
+ if (prev != null) {
+ // Key not found
+ return null;
+ }
+ }
+ }
+ }
+
+ @Override
+ public boolean containsKey(int key) {
+ return this.getEntry(key) != null;
+ }
+
+ @Override
+ public IntIterator keys() {
+ return new KeyIterator();
+ }
+
+ @Override
+ public IntIterator values() {
+ return new ValueIterator();
+ }
+
+ @Override
+ public void clear() {
+ Entry[] currentArray = this.table;
+ ResizeContainer resizeContainer;
+ do {
+ resizeContainer = null;
+ for (int i = 0; i < currentArray.length - 1; i++) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, i);
+ if (o == RESIZED || o == RESIZING) {
+ resizeContainer = (ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ currentArray.length -
+ 1);
+ } else if (o != null) {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(currentArray, i, o, null)) {
+ int removedEntries = 0;
+ while (e != null) {
+ removedEntries++;
+ e = e.getNext();
+ }
+ this.addToSize(-removedEntries);
+ }
+ }
+ }
+ if (resizeContainer != null) {
+ if (resizeContainer.isNotDone()) {
+ this.helpWithResize(currentArray);
+ resizeContainer.waitForAllResizers();
+ }
+ currentArray = resizeContainer.nextArray;
+ }
+ } while (resizeContainer != null);
+ }
+
+ @Override
+ public int size() {
+ int localSize = this.size;
+ if (this.partitionedSize != null) {
+ for (int i = 0; i < SIZE_BUCKETS; i++) {
+ localSize += this.partitionedSize[i << 4];
+ }
+ }
+ return localSize;
+ }
+
+ @Override
+ public boolean concurrent() {
+ return true;
+ }
+
+ private int hash(int key) {
+ return key & (table.length - 2);
+ }
+
+ private int hash(int key, int length) {
+ return key & (length - 2);
+ }
+
+ private Entry getEntry(int key) {
+ Entry[] currentArray = this.table;
+ while (true) {
+ int length = currentArray.length;
+ int index = this.hash(key, length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = this.helpWithResizeWhileCurrentIndex(currentArray, index);
+ } else {
+ Entry e = o;
+ while (e != null) {
+ int candidate = e.getKey();
+ if (candidate == key) {
+ return e;
+ }
+ e = e.getNext();
+ }
+ return null;
+ }
+ }
+ }
+
+ private void addToSize(int value) {
+ if (this.partitionedSize != null) {
+ if (this.incrementPartitionedSize(value)) {
+ return;
+ }
+ }
+ this.incrementLocalSize(value);
+ }
+
+ private boolean incrementPartitionedSize(int value) {
+ int h = (int) Thread.currentThread().getId();
+ h ^= (h >>> 18) ^ (h >>> 12);
+ h = (h ^ (h >>> 10)) & SIZE_BUCKETS;
+ if (h != 0) {
+ h = (h - 1) << 4;
+ long address = ((long) h << INT_ARRAY_SHIFT) + INT_ARRAY_BASE;
+ while (true) {
+ int localSize = UNSAFE.getIntVolatile(this.partitionedSize, address);
+ if (UNSAFE.compareAndSwapInt(this.partitionedSize, address, localSize,
+ localSize + value)) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ private void incrementLocalSize(int value) {
+ while (true) {
+ int localSize = this.size;
+ if (UNSAFE.compareAndSwapInt(this, SIZE_OFFSET, localSize, localSize + value)) {
+ break;
+ }
+ }
+ }
+
+ private Entry createReplacementChainForRemoval(Entry original,
+ Entry toRemove) {
+ if (original == toRemove) {
+ return original.getNext();
+ }
+ Entry replacement = null;
+ Entry e = original;
+ while (e != null) {
+ if (e != toRemove) {
+ replacement = new Entry(e.getKey(), e.getValue(), replacement);
+ }
+ e = e.getNext();
+ }
+ return replacement;
+ }
+
+ private void incrementSizeAndPossiblyResize(Entry[] currentArray, int length, Entry prev) {
+ this.addToSize(1);
+ if (prev != null) {
+ int localSize = this.size();
+ int threshold = (int) (length * LOAD_FACTOR); // threshold = length * 0.75
+ if (localSize + 1 > threshold) {
+ this.resize(currentArray);
+ }
+ }
+ }
+
+ private Entry[] helpWithResizeWhileCurrentIndex(Entry[] currentArray, int index) {
+ Entry[] newArray = this.helpWithResize(currentArray);
+ int helpCount = 0;
+ while (IntMapByDynamicHash.tableAt(currentArray, index) != RESIZED) {
+ helpCount++;
+ newArray = this.helpWithResize(currentArray);
+ if ((helpCount & 7) == 0) {
+ Thread.yield();
+ }
+ }
+ return newArray;
+ }
+
+ private void resize(Entry[] oldTable) {
+ this.resize(oldTable, (oldTable.length - 1 << 1) + 1);
+ }
+
+ // newSize must be a power of 2 + 1
+ @SuppressWarnings("JLM_JSR166_UTILCONCURRENT_MONITORENTER")
+ private void resize(Entry[] oldTable, int newSize) {
+ int oldCapacity = oldTable.length;
+ int end = oldCapacity - 1;
+ Entry last = (Entry) IntMapByDynamicHash.tableAt(oldTable, end);
+ if (this.size() < end && last == RESIZE_SENTINEL) {
+ return;
+ }
+ if (oldCapacity >= MAXIMUM_CAPACITY) {
+ throw new RuntimeException("max capacity of map exceeded");
+ }
+ ResizeContainer resizeContainer = null;
+ // This ownResize records whether current thread need to perform the expansion operation of
+ // the map by itself
+ boolean ownResize = false;
+ if (last == null || last == RESIZE_SENTINEL) {
+ // allocating a new array is too expensive to make this an atomic operation
+ synchronized (oldTable) {
+ if (IntMapByDynamicHash.tableAt(oldTable, end) == null) {
+ IntMapByDynamicHash.setTableAt(oldTable, end, RESIZE_SENTINEL);
+ if (this.partitionedSize == null && newSize >= PARTITIONED_SIZE_THRESHOLD) {
+ this.partitionedSize = new int[SIZE_BUCKETS * 16];
+ }
+ resizeContainer = new ResizeContainer(new Entry[newSize], oldTable.length - 1);
+ IntMapByDynamicHash.setTableAt(oldTable, end, resizeContainer);
+ ownResize = true;
+ }
+ }
+ }
+ if (ownResize) {
+ this.transfer(oldTable, resizeContainer);
+
+ Entry[] src = this.table;
+ while (!TABLE_UPDATER.compareAndSet(this, oldTable, resizeContainer.nextArray)) {
+ /*
+ we're in a double resize situation; we'll have to go help until it's our turn
+ to set the table
+ */
+ if (src != oldTable) {
+ this.helpWithResize(src);
+ }
+ }
+ } else {
+ this.helpWithResize(oldTable);
+ }
+ }
+
+ /**
+ * Transfer all entries from src to dest tables
+ */
+ private void transfer(Entry[] src, ResizeContainer resizeContainer) {
+ Entry[] dest = resizeContainer.nextArray;
+
+ for (int j = 0; j < src.length - 1; ) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(src, j);
+ if (o == null) {
+ if (IntMapByDynamicHash.casTableAt(src, j, null, RESIZED)) {
+ j++;
+ }
+ } else if (o == RESIZED || o == RESIZING) {
+ /*
+ During the expansion process, other threads have already migrated the elements at
+ this location to the new array. This means that the elements in the current
+ position have already been processed and do not need to be migrated again.
+ */
+ j = (j & ~(ResizeContainer.QUEUE_INCREMENT - 1)) + ResizeContainer.QUEUE_INCREMENT;
+ /*
+ When there is only one thread for expansion, there is no concurrency issue
+ and there is no need to wait.
+ */
+ if (resizeContainer.resizers.get() == 1) {
+ break;
+ }
+ } else {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(src, j, o, RESIZING)) {
+ while (e != null) {
+ this.unconditionalCopy(dest, e);
+ e = e.getNext();
+ }
+ IntMapByDynamicHash.setTableAt(src, j, RESIZED);
+ j++;
+ }
+ }
+ }
+ resizeContainer.decrementResizerAndNotify();
+ resizeContainer.waitForAllResizers();
+ }
+
+ /**
+ * Enable the current thread to participate in the expansion
+ */
+ private Entry[] helpWithResize(Entry[] currentArray) {
+ ResizeContainer resizeContainer =
+ (ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ currentArray.length - 1);
+ Entry[] newTable = resizeContainer.nextArray;
+ if (resizeContainer.getQueuePosition() > ResizeContainer.QUEUE_INCREMENT) {
+ resizeContainer.incrementResizer();
+ this.reverseTransfer(currentArray, resizeContainer);
+ resizeContainer.decrementResizerAndNotify();
+ }
+ return newTable;
+ }
+
+ private void reverseTransfer(Entry[] src, ResizeContainer resizeContainer) {
+ Entry[] dest = resizeContainer.nextArray;
+ while (resizeContainer.getQueuePosition() > 0) {
+ int start = resizeContainer.subtractAndGetQueuePosition();
+ int end = start + ResizeContainer.QUEUE_INCREMENT;
+ if (end > 0) {
+ if (start < 0) {
+ start = 0;
+ }
+ for (int j = end - 1; j >= start; ) {
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(src, j);
+ if (o == null) {
+ if (IntMapByDynamicHash.casTableAt(src, j, null, RESIZED)) {
+ j--;
+ }
+ } else if (o == RESIZED || o == RESIZING) {
+ resizeContainer.zeroOutQueuePosition();
+ return;
+ } else {
+ Entry e = o;
+ if (IntMapByDynamicHash.casTableAt(src, j, o, RESIZING)) {
+ while (e != null) {
+ this.unconditionalCopy(dest, e);
+ e = e.getNext();
+ }
+ IntMapByDynamicHash.setTableAt(src, j, RESIZED);
+ j--;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ private void unconditionalCopy(Entry[] dest, Entry toCopyEntry) {
+ Entry[] currentArray = dest;
+ while (true) {
+ int length = currentArray.length;
+ int index = this.hash(toCopyEntry.getKey(), length);
+ Entry o = (Entry) IntMapByDynamicHash.tableAt(currentArray, index);
+ if (o == RESIZED || o == RESIZING) {
+ currentArray = ((ResizeContainer) IntMapByDynamicHash.tableAt(currentArray,
+ length -
+ 1)).nextArray;
+ } else {
+ Entry newEntry;
+ if (o == null) {
+ if (toCopyEntry.getNext() == null) {
+ newEntry = toCopyEntry; // no need to duplicate
+ } else {
+ newEntry = new Entry(toCopyEntry.getKey(), toCopyEntry.getValue());
+ }
+ } else {
+ newEntry =
+ new Entry(toCopyEntry.getKey(), toCopyEntry.getValue(), o);
+ }
+ if (IntMapByDynamicHash.casTableAt(currentArray, index, o, newEntry)) {
+ return;
+ }
+ }
+ }
+ }
+
+ private static final class ResizeContainer extends Entry {
+ private static final int QUEUE_INCREMENT =
+ Math.min(1 << 10,
+ Integer.highestOneBit(Runtime.getRuntime().availableProcessors()) << 4);
+ private final AtomicInteger resizers = new AtomicInteger(1);
+ private final Entry[] nextArray;
+ private final AtomicInteger queuePosition;
+
+ private ResizeContainer(Entry[] nextArray, int oldSize) {
+ super(NULL_VALUE, NULL_VALUE, 4);
+ this.nextArray = nextArray;
+ this.queuePosition = new AtomicInteger(oldSize);
+ }
+
+ public void incrementResizer() {
+ this.resizers.incrementAndGet();
+ }
+
+ public void decrementResizerAndNotify() {
+ int remaining = this.resizers.decrementAndGet();
+ if (remaining == 0) {
+ synchronized (this) {
+ this.notifyAll();
+ }
+ }
+ }
+
+ public int getQueuePosition() {
+ return this.queuePosition.get();
+ }
+
+ public int subtractAndGetQueuePosition() {
+ return this.queuePosition.addAndGet(-QUEUE_INCREMENT);
+ }
+
+ public void waitForAllResizers() {
+ if (this.resizers.get() > 0) {
+ for (int i = 0; i < 16; i++) {
+ if (this.resizers.get() == 0) {
+ break;
+ }
+ }
+ for (int i = 0; i < 16; i++) {
+ if (this.resizers.get() == 0) {
+ break;
+ }
+ Thread.yield();
+ }
+ }
+ if (this.resizers.get() > 0) {
+ synchronized (this) {
+ while (this.resizers.get() > 0) {
+ try {
+ this.wait();
+ } catch (InterruptedException e) {
+ //ginore
+ }
+ }
+ }
+ }
+ }
+
+ public boolean isNotDone() {
+ return this.resizers.get() > 0;
+ }
+
+ public void zeroOutQueuePosition() {
+ this.queuePosition.set(0);
+ }
+ }
+
+ private static class Entry {
Review Comment:
expect to serialize it into a chunk memory
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@hugegraph.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@hugegraph.apache.org
For additional commands, e-mail: issues-help@hugegraph.apache.org
Re: [PR] feat(core): add IntMapByDynamicHash V1 implement [incubator-hugegraph]
Posted by "simon824 (via GitHub)" <gi...@apache.org>.
simon824 merged PR #2377:
URL: https://github.com/apache/incubator-hugegraph/pull/2377
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@hugegraph.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@hugegraph.apache.org
For additional commands, e-mail: issues-help@hugegraph.apache.org
Re: [PR] feat: add IntMapByDynamicHash [incubator-hugegraph]
Posted by "javeme (via GitHub)" <gi...@apache.org>.
javeme commented on code in PR #2377:
URL: https://github.com/apache/incubator-hugegraph/pull/2377#discussion_r1417092825
##########
hugegraph-server/hugegraph-test/src/test/java/org/apache/hugegraph/benchmark/map/MapRandomGetPutThroughputTest.java:
##########
@@ -57,9 +58,11 @@ public class MapRandomGetPutThroughputTest {
private ConcurrentHashMap<Integer, Integer> concurrentHashMap;
- private IntMap.IntMapBySegments intMapBySegments;
+ private IntMap intMapBySegments;
- private IntMap.IntMapByEcSegment intMapByEcSegments;
+ private IntMap intMapByDynamicHashNonCap;
+
+ private IntMap intMapByDynamicHash;
Review Comment:
intMapByDynamicHashWithCap
##########
hugegraph-server/hugegraph-test/src/test/java/org/apache/hugegraph/benchmark/map/MapRandomGetPutThroughputTest.java:
##########
@@ -57,9 +58,11 @@ public class MapRandomGetPutThroughputTest {
private ConcurrentHashMap<Integer, Integer> concurrentHashMap;
- private IntMap.IntMapBySegments intMapBySegments;
+ private IntMap intMapBySegments;
- private IntMap.IntMapByEcSegment intMapByEcSegments;
+ private IntMap intMapByDynamicHashNonCap;
Review Comment:
prefer intMapByDynamicHashWithoutCap
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@hugegraph.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@hugegraph.apache.org
For additional commands, e-mail: issues-help@hugegraph.apache.org
Re: [PR] feat: add IntMapByDynamicHash [incubator-hugegraph]
Posted by "codecov[bot] (via GitHub)" <gi...@apache.org>.
codecov[bot] commented on PR #2377:
URL: https://github.com/apache/incubator-hugegraph/pull/2377#issuecomment-1840128418
## [Codecov](https://app.codecov.io/gh/apache/incubator-hugegraph/pull/2377?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
Attention: `455 lines` in your changes are missing coverage. Please review.
> Comparison is base [(`20d1e52`)](https://app.codecov.io/gh/apache/incubator-hugegraph/commit/20d1e5228e39bd974079891fc713574fb14798c5?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) 53.81% compared to head [(`44d03e8`)](https://app.codecov.io/gh/apache/incubator-hugegraph/pull/2377?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) 48.31%.
| [Files](https://app.codecov.io/gh/apache/incubator-hugegraph/pull/2377?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [...hugegraph/util/collection/IntMapByDynamicHash.java](https://app.codecov.io/gh/apache/incubator-hugegraph/pull/2377?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVnZWdyYXBoLXNlcnZlci9odWdlZ3JhcGgtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvaHVnZWdyYXBoL3V0aWwvY29sbGVjdGlvbi9JbnRNYXBCeUR5bmFtaWNIYXNoLmphdmE=) | 0.00% | [455 Missing :warning: ](https://app.codecov.io/gh/apache/incubator-hugegraph/pull/2377?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## master #2377 +/- ##
============================================
- Coverage 53.81% 48.31% -5.51%
+ Complexity 545 272 -273
============================================
Files 509 510 +1
Lines 42139 42591 +452
Branches 5836 5928 +92
============================================
- Hits 22679 20579 -2100
- Misses 17027 19692 +2665
+ Partials 2433 2320 -113
```
</details>
[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/apache/incubator-hugegraph/pull/2377?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@hugegraph.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@hugegraph.apache.org
For additional commands, e-mail: issues-help@hugegraph.apache.org
Re: [PR] feat: add IntMapByDynamicHash [incubator-hugegraph]
Posted by "conghuhu (via GitHub)" <gi...@apache.org>.
conghuhu commented on PR #2377:
URL: https://github.com/apache/incubator-hugegraph/pull/2377#issuecomment-1840120154
@imbajin PTAL
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@hugegraph.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@hugegraph.apache.org
For additional commands, e-mail: issues-help@hugegraph.apache.org