This is an automated email from the ASF dual-hosted git repository. bchapuis pushed a commit to branch 681-handle-the-out-of-memory-errors in repository https://gitbox.apache.org/repos/asf/incubator-baremaps.git
commit 92232b1b435182be29be02e1353d24e083933de0 Author: Bertil Chapuis <[email protected]> AuthorDate: Tue Jul 4 23:02:26 2023 +0200 Improve jagged data structure --- .../apache/baremaps/collection/JaggedDataMap.java | 216 +++++++++++++++++++++ 1 file changed, 216 insertions(+) diff --git a/baremaps-core/src/main/java/org/apache/baremaps/collection/JaggedDataMap.java b/baremaps-core/src/main/java/org/apache/baremaps/collection/JaggedDataMap.java new file mode 100644 index 00000000..9fd3571d --- /dev/null +++ b/baremaps-core/src/main/java/org/apache/baremaps/collection/JaggedDataMap.java @@ -0,0 +1,216 @@ +package org.apache.baremaps.collection; + +import org.apache.baremaps.database.collection.AppendOnlyBuffer; +import org.apache.baremaps.database.collection.DataMap; +import org.apache.baremaps.stream.StreamUtils; + +import java.util.Arrays; +import java.util.Iterator; +import java.util.Map; +import java.util.concurrent.atomic.AtomicLong; +import java.util.stream.IntStream; + +public class JaggedDataMap<E> extends DataMap<E> { + + private static final int L_BYTES = 8; + private static final int L_SIZE = 1 << L_BYTES; + private static final int L_MASK = L_SIZE - 1; + private static final int L_SHIFT = 0; + + private static final int K_BYTES = 8; + private static final int K_SIZE = 1 << K_BYTES; + private static final int K_MASK = K_SIZE - 1; + private static final int K_SHIFT = L_SHIFT + L_BYTES; + + private static final int J_BYTES = 12; + private static final int J_SIZE = 1 << J_BYTES; + private static final int J_MASK = J_SIZE - 1; + private static final int J_SHIFT = K_SHIFT + K_BYTES; + + private static final int I_BYTES = 12; + private static final int I_SIZE = 1 << I_BYTES; + private static final int I_MASK = I_SIZE - 1; + private static final int I_SHIFT = J_SHIFT + J_BYTES; + + private static final long CAPACITY = 1L << (I_BYTES + J_BYTES + K_BYTES + L_BYTES); + + private long[][][][] index; + + private final AppendOnlyBuffer<E> values; + + private final AtomicLong size = new AtomicLong(); + + /** + * Constructs a map. + * + * @param values the values + */ + public JaggedDataMap(AppendOnlyBuffer<E> values) { + this.index = new long[I_SIZE][][][]; + this.values = values; + } + + /** + * {@inheritDoc} + */ + @Override + public E put(Long key, E value) { + long v = key; + if (v < 0 || v >= CAPACITY) { + throw new IllegalArgumentException(); + } + int i = (int) (v >>> I_SHIFT) & I_MASK; + int j = (int) (v >>> J_SHIFT) & J_MASK; + int k = (int) (v >>> K_SHIFT) & K_MASK; + int l = (int) (v >>> L_SHIFT) & L_MASK; + if (index[i] == null) { + index[i] = new long[J_SIZE][][]; + } + if (index[i][j] == null) { + index[i][j] = new long[K_SIZE][]; + } + if (index[i][j][k] == null) { + index[i][j][k] = new long[L_SIZE]; + Arrays.fill(index[i][j][k], -1); + } + long position = values.addPositioned(value); + if (index[i][j][k][l] == -1) { + size.incrementAndGet(); + } + index[i][j][k][l] = position; + return value; + } + + /** + * {@inheritDoc} + */ + @Override + public E get(Object key) { + long v = (Long) key; + if (v < 0 || v >= CAPACITY) { + throw new IllegalArgumentException(); + } + int i = (int) (v >>> I_SHIFT) & I_MASK; + int j = (int) (v >>> J_SHIFT) & J_MASK; + int k = (int) (v >>> K_SHIFT) & K_MASK; + int l = (int) (v >>> L_SHIFT) & L_MASK; + if (index[i] == null) { + return null; + } + if (index[i][j] == null) { + return null; + } + if (index[i][j][k] == null) { + return null; + } + long position = index[i][j][k][l]; + if (position == -1) { + return null; + } + return values.read(position); + } + + /** + * {@inheritDoc} + */ + @Override + protected Iterator<Long> keyIterator() { + return IntStream.range(0, index.length) + .filter(i -> index[i] != null) + .mapToObj(i -> IntStream.range(0, index[i].length) + .filter(j -> index[i][j] != null) + .mapToObj(j -> IntStream.range(0, index[i][j].length) + .filter(k -> index[i][j][k] != null) + .mapToObj(k -> IntStream.range(0, index[i][j][k].length) + .filter(l -> index[i][j][k][l] != -1) + .mapToObj(l -> (long) ((i << I_SHIFT) | (j << J_SHIFT) | (k << K_SHIFT) | (l << L_SHIFT)))) + .flatMap(x -> x)) + .flatMap(x -> x)) + .flatMap(x -> x) + .iterator(); + } + + /** + * {@inheritDoc} + */ + @Override + protected Iterator<E> valueIterator() { + return StreamUtils.stream(keyIterator()).map(this::get).iterator(); + } + + /** + * {@inheritDoc} + */ + @Override + protected Iterator<Entry<Long, E>> entryIterator() { + return StreamUtils.stream(keyIterator()).map(key -> Map.entry(key, get(key))).iterator(); + } + + /** + * {@inheritDoc} + */ + @Override + public boolean isEmpty() { + return StreamUtils.stream(keyIterator()).findAny().isEmpty(); + } + + /** + * {@inheritDoc} + */ + @Override + public long sizeAsLong() { + return size.get(); + } + + /** + * {@inheritDoc} + */ + @Override + public boolean containsKey(Object key) { + return get(key) != null; + } + + /** + * {@inheritDoc} + */ + @Override + public boolean containsValue(Object value) { + return StreamUtils.stream(valueIterator()).anyMatch(v -> v.equals(value)); + } + + /** + * {@inheritDoc} + */ + @Override + public E remove(Object key) { + long v = (Long) key; + int i = (int) (v >>> I_SHIFT) & I_MASK; + int j = (int) (v >>> J_SHIFT) & J_MASK; + int k = (int) (v >>> K_SHIFT) & K_MASK; + int l = (int) (v >>> L_SHIFT) & L_MASK; + if (index[i] == null) { + return null; + } + if (index[i][j] == null) { + return null; + } + if (index[i][j][k] == null) { + return null; + } + long position = index[i][j][k][l]; + if (position == -1) { + return null; + } + size.decrementAndGet(); + index[i][j][k][l] = -1; + return values.read(position); + } + + /** + * {@inheritDoc} + */ + @Override + public void clear() { + index = new long[I_SIZE][][][]; + } +}
