This is an automated email from the ASF dual-hosted git repository.
rdblue pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/iceberg.git
The following commit(s) were added to refs/heads/main by this push:
new e055c68fff Core: Add MutableBitmap.merge (#18704)
e055c68fff is described below
commit e055c68fff4472dbd79fde05711b238d22b04c7d
Author: Ryan Blue <[email protected]>
AuthorDate: Tue Nov 3 11:46:18 2026 -0800
Core: Add MutableBitmap.merge (#18704)
Co-Authored-By: Claude Opus 5.5 <[email protected]>
---
.../apache/iceberg/mumbling/MumblingBitmap.java | 111 +++++-
.../org/apache/iceberg/mumbling/MutableBitmap.java | 4 +
.../iceberg/mumbling/TestMumblingBitmap.java | 440 +++++++++++++++++++++
3 files changed, 540 insertions(+), 15 deletions(-)
diff --git a/core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java
b/core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java
index aea57c518e..ef86f581bc 100644
--- a/core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java
+++ b/core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java
@@ -19,6 +19,7 @@
package org.apache.iceberg.mumbling;
import java.nio.ByteBuffer;
+import java.util.Arrays;
import java.util.Map;
import java.util.NavigableMap;
import org.apache.iceberg.ManifestBitmap;
@@ -54,7 +55,7 @@ class MumblingBitmap implements ManifestBitmap {
private static final int MAX_CONTAINER_COUNT = 8_192;
private static final int MAX_CARDINALITY = 2_097_152;
- static MutableBitmap newMutableBitmap() {
+ static Mutable newMutableBitmap() {
return new MumblingBitmap(EMPTY_BITMAP).asMutable();
}
@@ -161,7 +162,7 @@ class MumblingBitmap implements ManifestBitmap {
return offsets[containerIndex];
}
- public MutableBitmap asMutable() {
+ public Mutable asMutable() {
return new Mutable(this);
}
@@ -172,7 +173,8 @@ class MumblingBitmap implements ManifestBitmap {
*
* <p>The initial buffer is not modified.
*/
- private static class Mutable implements MutableBitmap {
+ @VisibleForTesting
+ static class Mutable implements MutableBitmap {
private final NavigableMap<Integer, Container> overlays =
Maps.newTreeMap();
private final MumblingBitmap base;
private final int baseContainerCount;
@@ -206,17 +208,7 @@ class MumblingBitmap implements ManifestBitmap {
pos < MAX_CARDINALITY, "Cannot set invalid bit position: %s (must be
< 2,097,152)", pos);
int containerIndex = containerIndex(pos);
- Container overlay = overlays.get(containerIndex);
- if (overlay == null) {
- if (containerIndex < baseContainerCount) {
- ByteBuffer src = base.buffer();
- int offset = src.position() + base.offset(containerIndex);
- overlay = new Container(src, offset,
base.descriptor(containerIndex));
- } else {
- overlay = new Container();
- }
- overlays.put(containerIndex, overlay);
- }
+ Container overlay = overlay(containerIndex);
if (overlay.set(posInContainer(pos))) {
this.cardinality += 1;
@@ -226,6 +218,18 @@ class MumblingBitmap implements ManifestBitmap {
return false;
}
+ @Override
+ public void merge(ManifestBitmap bitmap) {
+ if (bitmap instanceof Mutable) {
+ merge((Mutable) bitmap);
+ } else if (bitmap instanceof MumblingBitmap) {
+ merge((MumblingBitmap) bitmap);
+ } else {
+ // use the buffer to get the bitmap as a supported class
+ merge(new MumblingBitmap(bitmap.buffer()));
+ }
+ }
+
@Override
public ByteBuffer buffer() {
int[] descriptorArray = descriptorArray();
@@ -255,7 +259,8 @@ class MumblingBitmap implements ManifestBitmap {
return buffer;
}
- private int[] descriptorArray() {
+ @VisibleForTesting
+ int[] descriptorArray() {
int[] baseDescriptors = base.descriptors();
int lastOverlayIndex = overlays.isEmpty() ? -1 : overlays.lastKey();
int numContainers = Math.max(lastOverlayIndex + 1,
baseDescriptors.length);
@@ -307,9 +312,49 @@ class MumblingBitmap implements ManifestBitmap {
return 0;
}
+
+ private Container overlay(int containerIndex) {
+ Container overlay = overlays.get(containerIndex);
+ if (overlay == null) {
+ overlay = Container.newOverlay(base, containerIndex);
+ overlays.put(containerIndex, overlay);
+ }
+
+ return overlay;
+ }
+
+ private void merge(Mutable other) {
+ int[] descriptors = other.descriptorArray();
+ for (int containerIndex = 0; containerIndex < descriptors.length;
containerIndex += 1) {
+ if (descriptors[containerIndex] != 0) {
+ Container overlay = overlay(containerIndex);
+ this.cardinality += overlay.merge(other.overlay(containerIndex));
+ }
+ }
+ }
+
+ private void merge(MumblingBitmap other) {
+ int[] descriptors = other.descriptors();
+ for (int containerIndex = 0; containerIndex < descriptors.length;
containerIndex += 1) {
+ if (descriptors[containerIndex] != 0) {
+ Container overlay = overlay(containerIndex);
+ this.cardinality += overlay.merge(Container.newOverlay(other,
containerIndex));
+ }
+ }
+ }
}
private static class Container {
+ private static Container newOverlay(MumblingBitmap bitmap, int
containerIndex) {
+ if (containerIndex < bitmap.containerCount) {
+ ByteBuffer src = bitmap.buffer();
+ int offset = src.position() + bitmap.offset(containerIndex);
+ return new Container(src, offset, bitmap.descriptor(containerIndex));
+ }
+
+ return new Container();
+ }
+
private byte[] dense = null;
private byte[] sparse = null;
private int cardinality = 0;
@@ -371,6 +416,42 @@ class MumblingBitmap implements ManifestBitmap {
}
}
+ private int merge(Container other) {
+ int initialCardinality = cardinality;
+
+ if (other.dense != null) {
+ // other may be sparse and have a dense array
+ if (dense != null) {
+ // OR the dense bytes together
+ for (int i = 0; i < dense.length; i += 1) {
+ this.dense[i] |= other.dense[i];
+ }
+ } else {
+ // Copy the dense bytes and set the positions from this container
+ this.dense = Arrays.copyOf(other.dense, other.dense.length);
+ for (int i = 0; i < cardinality; i += 1) {
+ denseSet(dense, (sparse[i] & 0xFF));
+ }
+ }
+
+ this.cardinality = denseCardinality(dense);
+
+ // copy the sparse array if needed; other was sparse and merge set no
new bits
+ if (cardinality < DENSE_CONTAINER_SIZE) {
+ this.sparse = Arrays.copyOf(other.sparse, other.sparse.length);
+ } else {
+ this.sparse = null;
+ }
+ } else {
+ // Set the positions from the other container in this container
+ for (int i = 0; i < other.cardinality; i += 1) {
+ set(other.sparse[i] & 0xFF);
+ }
+ }
+
+ return cardinality - initialCardinality;
+ }
+
private boolean setInternal(int posInContainer) {
if (cardinality < MAX_SPARSE_CARDINALITY) {
return sparseSet(sparse, cardinality, posInContainer);
diff --git a/core/src/main/java/org/apache/iceberg/mumbling/MutableBitmap.java
b/core/src/main/java/org/apache/iceberg/mumbling/MutableBitmap.java
index 7c46ed5d24..078cb7aad1 100644
--- a/core/src/main/java/org/apache/iceberg/mumbling/MutableBitmap.java
+++ b/core/src/main/java/org/apache/iceberg/mumbling/MutableBitmap.java
@@ -22,5 +22,9 @@ import org.apache.iceberg.ManifestBitmap;
/** Mutation methods for ManifestBitmap. */
public interface MutableBitmap extends ManifestBitmap {
+ /** Set the bit at {@code position}. */
boolean set(int position);
+
+ /** Set all bits in this bitmap that are set in {@code bitmap}. */
+ void merge(ManifestBitmap bitmap);
}
diff --git
a/core/src/test/java/org/apache/iceberg/mumbling/TestMumblingBitmap.java
b/core/src/test/java/org/apache/iceberg/mumbling/TestMumblingBitmap.java
index ed61fed195..4feaf229f1 100644
--- a/core/src/test/java/org/apache/iceberg/mumbling/TestMumblingBitmap.java
+++ b/core/src/test/java/org/apache/iceberg/mumbling/TestMumblingBitmap.java
@@ -28,6 +28,9 @@ import static
org.assertj.core.api.Assertions.assertThatThrownBy;
import java.nio.ByteBuffer;
import java.util.Arrays;
import java.util.Random;
+import java.util.stream.IntStream;
+import org.apache.iceberg.ManifestBitmap;
+import org.apache.iceberg.mumbling.MumblingBitmap.Mutable;
import org.junit.jupiter.api.Test;
class TestMumblingBitmap {
@@ -776,6 +779,443 @@ class TestMumblingBitmap {
assertThat(serialized.slice(containersOffset + 35, 2)).isEqualTo(sparse(3,
7).buffer());
}
+ @Test
+ public void testMergeSparseIntoSparse() {
+ int[] positions = new int[] {0, 10, 20, 255};
+ int[] otherPositions = new int[] {0, 15, 20, 30, 255};
+
+ Mutable bitmap = bitmap(sparse(positions)).asMutable();
+ bitmap.merge(bitmap(sparse(otherPositions)));
+
+ assertThat(bitmap.cardinality()).isEqualTo(6);
+ assertThat(bitmap.descriptorArray()).containsExactly(6);
+ assertSet(bitmap, 0, positions);
+ assertSet(bitmap, 0, otherPositions);
+ }
+
+ @Test
+ public void testMergeSparseIntoSparseConvertsToDense() {
+ int[] positions = range(0, 20);
+ int[] otherPositions = range(10, 40);
+
+ Mutable bitmap = bitmap(sparse(positions)).asMutable();
+ bitmap.merge(bitmap(sparse(otherPositions)));
+
+ assertThat(bitmap.cardinality()).isEqualTo(40);
+ assertThat(bitmap.descriptorArray()).containsExactly(32);
+ assertSet(bitmap, 0, positions);
+ assertSet(bitmap, 0, otherPositions);
+ }
+
+ @Test
+ public void testMergeSparseIntoDense() {
+ int[] otherPositions = new int[] {0, 15, 40, 100, 255};
+
+ Mutable bitmap = bitmap(dense(DENSE_CONTAINER)).asMutable();
+ bitmap.merge(bitmap(sparse(otherPositions)));
+
+ assertThat(bitmap.cardinality()).isEqualTo(35);
+ assertThat(bitmap.descriptorArray()).containsExactly(32);
+ assertSet(bitmap, 0, DENSE_CONTAINER);
+ assertSet(bitmap, 0, otherPositions);
+ }
+
+ @Test
+ public void testMergeDenseIntoSparse() {
+ int[] positions = new int[] {0, 15, 40, 100, 255};
+
+ Mutable bitmap = bitmap(sparse(positions)).asMutable();
+ bitmap.merge(bitmap(dense(DENSE_CONTAINER)));
+
+ assertThat(bitmap.cardinality()).isEqualTo(35);
+ assertThat(bitmap.descriptorArray()).containsExactly(32);
+ assertSet(bitmap, 0, positions);
+ assertSet(bitmap, 0, DENSE_CONTAINER);
+ }
+
+ @Test
+ public void testMergeDenseIntoDense() {
+ // positions 48-79
+ byte[] otherDense = new byte[32];
+ otherDense[6] = (byte) 0xFF;
+ otherDense[7] = (byte) 0xFF;
+ otherDense[8] = (byte) 0xFF;
+ otherDense[9] = (byte) 0xFF;
+
+ Mutable bitmap = bitmap(dense(DENSE_CONTAINER)).asMutable();
+ bitmap.merge(bitmap(dense(otherDense)));
+
+ assertThat(bitmap.cardinality()).isEqualTo(56);
+ assertThat(bitmap.descriptorArray()).containsExactly(32);
+ assertSet(bitmap, 0, DENSE_CONTAINER);
+ assertSet(bitmap, 0, otherDense);
+ }
+
+ @Test
+ public void testMergeSparseIntoSparseWithDenseArray() {
+ int[] positions = range(0, 31);
+ int[] otherPositions = new int[] {0, 255};
+
+ Mutable bitmap = bitmap(sparse(positions)).asMutable();
+ assertThat(bitmap.set(0)).as("Converts to dense but does not set a new
bit").isFalse();
+
+ bitmap.merge(bitmap(sparse(otherPositions)));
+
+ assertThat(bitmap.cardinality()).isEqualTo(32);
+ assertThat(bitmap.descriptorArray()).containsExactly(32);
+ assertSet(bitmap, 0, positions);
+ assertSet(bitmap, 0, otherPositions);
+ }
+
+ @Test
+ public void testMergeSparseWithDenseArrayIntoEmpty() {
+ int[] otherPositions = range(0, 31);
+
+ Mutable other = bitmap(sparse(otherPositions)).asMutable();
+ assertThat(other.set(0)).as("Converts to dense but does not set a new
bit").isFalse();
+
+ Mutable bitmap = MumblingBitmap.newMutableBitmap();
+ bitmap.merge(other);
+
+ assertThat(bitmap.cardinality()).isEqualTo(31);
+ assertThat(bitmap.descriptorArray()).containsExactly(31);
+ assertSet(bitmap, 0, otherPositions);
+ }
+
+ @Test
+ public void testMergeSparseWithDenseArrayIntoSparse() {
+ int[] positions = new int[] {0, 30};
+ int[] otherPositions = range(0, 31);
+
+ Mutable other = bitmap(sparse(otherPositions)).asMutable();
+ assertThat(other.set(0)).as("Converts to dense but does not set a new
bit").isFalse();
+
+ Mutable bitmap = bitmap(sparse(positions)).asMutable();
+ bitmap.merge(other);
+
+ assertThat(bitmap.cardinality()).isEqualTo(31);
+ assertThat(bitmap.descriptorArray()).containsExactly(31);
+ assertSet(bitmap, 0, positions);
+ assertSet(bitmap, 0, otherPositions);
+ }
+
+ @Test
+ public void testMergeDenseIntoSparseWithDenseArray() {
+ int[] positions = range(0, 31);
+
+ Mutable bitmap = bitmap(sparse(positions)).asMutable();
+ assertThat(bitmap.set(0)).as("Converts to dense but does not set a new
bit").isFalse();
+
+ bitmap.merge(bitmap(dense(DENSE_CONTAINER)));
+
+ assertThat(bitmap.cardinality()).isEqualTo(48);
+ assertThat(bitmap.descriptorArray()).containsExactly(32);
+ assertSet(bitmap, 0, positions);
+ assertSet(bitmap, 0, DENSE_CONTAINER);
+ }
+
+ @Test
+ public void testMergeSparseWithDenseArrayIntoSparseWithDenseArray() {
+ int[] positions = range(0, 31);
+ int[] otherPositions = range(1, 32);
+
+ Mutable bitmap = bitmap(sparse(positions)).asMutable();
+ assertThat(bitmap.set(0)).as("Converts to dense but does not set a new
bit").isFalse();
+
+ Mutable other = bitmap(sparse(otherPositions)).asMutable();
+ assertThat(other.set(1)).as("Converts to dense but does not set a new
bit").isFalse();
+
+ bitmap.merge(other);
+
+ assertThat(bitmap.cardinality()).isEqualTo(32);
+ assertThat(bitmap.descriptorArray()).containsExactly(32);
+ assertSet(bitmap, 0, positions);
+ assertSet(bitmap, 0, otherPositions);
+ }
+
+ @Test
+ public void testMergeSparseWithDenseArrayIntoDense() {
+ int[] otherPositions = range(0, 31);
+
+ Mutable other = bitmap(sparse(otherPositions)).asMutable();
+ assertThat(other.set(0)).as("Converts to dense but does not set a new
bit").isFalse();
+
+ Mutable bitmap = bitmap(dense(DENSE_CONTAINER)).asMutable();
+ bitmap.merge(other);
+
+ assertThat(bitmap.cardinality()).isEqualTo(48);
+ assertThat(bitmap.descriptorArray()).containsExactly(32);
+ assertSet(bitmap, 0, DENSE_CONTAINER);
+ assertSet(bitmap, 0, otherPositions);
+ }
+
+ @Test
+ public void testMergeEmptyContainers() {
+ int[] positions = new int[] {0, 10, 255};
+ int[] otherPositions = new int[] {0, 15, 255};
+
+ Mutable bitmap =
+ bitmap(sparse(), dense(DENSE_CONTAINER), sparse(positions),
sparse()).asMutable();
+ bitmap.merge(bitmap(sparse(otherPositions), sparse(), sparse(),
dense(DENSE_CONTAINER)));
+
+ assertThat(bitmap.cardinality()).isEqualTo(70);
+ assertThat(bitmap.descriptorArray()).containsExactly(3, 32, 3, 32);
+ assertSet(bitmap, 0, otherPositions);
+ assertSet(bitmap, 1, DENSE_CONTAINER);
+ assertSet(bitmap, 2, positions);
+ assertSet(bitmap, 3, DENSE_CONTAINER);
+ }
+
+ @Test
+ public void testMergeIntoEmptyBitmap() {
+ int[] otherPositions = new int[] {0, 15, 255};
+
+ Mutable bitmap = MumblingBitmap.newMutableBitmap();
+ bitmap.merge(bitmap(sparse(otherPositions), dense(DENSE_CONTAINER)));
+
+ assertThat(bitmap.cardinality()).isEqualTo(35);
+ assertThat(bitmap.descriptorArray()).containsExactly(3, 32);
+ assertSet(bitmap, 0, otherPositions);
+ assertSet(bitmap, 1, DENSE_CONTAINER);
+ }
+
+ @Test
+ public void testMergeEmptyBitmap() {
+ int[] positions = new int[] {0, 10, 255};
+
+ Mutable bitmap = bitmap(sparse(positions),
dense(DENSE_CONTAINER)).asMutable();
+ bitmap.merge(MumblingBitmap.newMutableBitmap());
+
+ assertThat(bitmap.cardinality()).isEqualTo(35);
+ assertThat(bitmap.descriptorArray()).containsExactly(3, 32);
+ assertSet(bitmap, 0, positions);
+ assertSet(bitmap, 1, DENSE_CONTAINER);
+ }
+
+ @Test
+ public void testMergeWithMoreContainers() {
+ int[] positions = new int[] {0, 10, 255};
+ int[] otherPositions = new int[] {0, 15, 255};
+
+ Mutable bitmap = bitmap(sparse(positions)).asMutable();
+ bitmap.merge(
+ bitmap(sparse(otherPositions), dense(DENSE_CONTAINER), sparse(),
sparse(otherPositions)));
+
+ assertThat(bitmap.cardinality()).isEqualTo(39);
+ assertThat(bitmap.descriptorArray()).containsExactly(4, 32, 0, 3);
+ assertSet(bitmap, 0, positions);
+ assertSet(bitmap, 0, otherPositions);
+ assertSet(bitmap, 1, DENSE_CONTAINER);
+ assertSet(bitmap, 3, otherPositions);
+ }
+
+ @Test
+ public void testMergeArgumentWithFewerContainers() {
+ int[] positions = new int[] {0, 10, 255};
+ int[] otherPositions = new int[] {0, 15, 255};
+
+ Mutable bitmap =
+ bitmap(sparse(positions), dense(DENSE_CONTAINER), sparse(),
sparse(positions)).asMutable();
+ bitmap.merge(bitmap(sparse(otherPositions)));
+
+ assertThat(bitmap.cardinality()).isEqualTo(39);
+ assertThat(bitmap.descriptorArray()).containsExactly(4, 32, 0, 3);
+ assertSet(bitmap, 0, positions);
+ assertSet(bitmap, 0, otherPositions);
+ assertSet(bitmap, 1, DENSE_CONTAINER);
+ assertSet(bitmap, 3, positions);
+ }
+
+ @Test
+ public void testMergeWithEmptyContainerGaps() {
+ int[] positions = new int[] {0, 10, 255};
+ int[] otherPositions = new int[] {0, 15, 255};
+
+ Mutable bitmap =
+ bitmap(sparse(positions), sparse(), sparse(),
dense(DENSE_CONTAINER)).asMutable();
+ bitmap.merge(
+ bitmap(sparse(), sparse(otherPositions), sparse(), sparse(),
dense(DENSE_CONTAINER)));
+
+ assertThat(bitmap.cardinality()).isEqualTo(70);
+ assertThat(bitmap.descriptorArray()).containsExactly(3, 3, 0, 32, 32);
+ assertSet(bitmap, 0, positions);
+ assertSet(bitmap, 1, otherPositions);
+ assertSet(bitmap, 3, DENSE_CONTAINER);
+ assertSet(bitmap, 4, DENSE_CONTAINER);
+ }
+
+ @Test
+ public void testMergeIntoOverlayAndBaseContainers() {
+ int[] positions = new int[] {0, 10, 255};
+ int[] otherPositions = new int[] {0, 15, 255};
+
+ Mutable bitmap = bitmap(sparse(positions),
dense(DENSE_CONTAINER)).asMutable();
+ assertThat(bitmap.set(5)).isTrue(); // creates an overlay for container 0
only
+
+ bitmap.merge(bitmap(sparse(otherPositions), sparse(otherPositions)));
+
+ assertThat(bitmap.cardinality()).isEqualTo(39);
+ assertThat(bitmap.descriptorArray()).containsExactly(5, 32);
+ assertThat(bitmap.isSet(5)).isTrue();
+ assertSet(bitmap, 0, positions);
+ assertSet(bitmap, 0, otherPositions);
+ assertSet(bitmap, 1, DENSE_CONTAINER);
+ assertSet(bitmap, 1, otherPositions);
+ }
+
+ @Test
+ public void testMergeBitmapWithBufferOffset() {
+ int[] positions = new int[] {0, 10, 255};
+ int[] otherPositions = new int[] {0, 15, 255};
+
+ // positions 48-79
+ byte[] otherDense = new byte[32];
+ otherDense[6] = (byte) 0xFF;
+ otherDense[7] = (byte) 0xFF;
+ otherDense[8] = (byte) 0xFF;
+ otherDense[9] = (byte) 0xFF;
+
+ Mutable bitmap = bitmap(sparse(positions),
dense(DENSE_CONTAINER)).asMutable();
+ bitmap.merge(new MumblingBitmap(relocate(build(sparse(otherPositions),
dense(otherDense)))));
+
+ assertThat(bitmap.cardinality()).isEqualTo(60);
+ assertThat(bitmap.descriptorArray()).containsExactly(4, 32);
+ assertSet(bitmap, 0, positions);
+ assertSet(bitmap, 0, otherPositions);
+ assertSet(bitmap, 1, DENSE_CONTAINER);
+ assertSet(bitmap, 1, otherDense);
+ }
+
+ @Test
+ public void testMergeMutableWithoutOverlays() {
+ int[] positions = new int[] {0, 10, 255};
+ int[] otherPositions = new int[] {0, 15, 255};
+
+ // positions 48-79
+ byte[] otherDense = new byte[32];
+ otherDense[6] = (byte) 0xFF;
+ otherDense[7] = (byte) 0xFF;
+ otherDense[8] = (byte) 0xFF;
+ otherDense[9] = (byte) 0xFF;
+
+ Mutable other = bitmap(sparse(otherPositions),
dense(otherDense)).asMutable();
+
+ Mutable bitmap = bitmap(sparse(positions),
dense(DENSE_CONTAINER)).asMutable();
+ bitmap.merge(other);
+
+ assertThat(bitmap.cardinality()).isEqualTo(60);
+ assertThat(bitmap.descriptorArray()).containsExactly(4, 32);
+ assertSet(bitmap, 0, positions);
+ assertSet(bitmap, 0, otherPositions);
+ assertSet(bitmap, 1, DENSE_CONTAINER);
+ assertSet(bitmap, 1, otherDense);
+ }
+
+ @Test
+ public void testMergeMutableWithOverlays() {
+ int[] positions = new int[] {0, 10, 255};
+ int[] otherPositions = new int[] {0, 15, 255};
+ int[] otherDensePositions = range(48, 80);
+
+ Mutable other = MumblingBitmap.newMutableBitmap();
+ for (int pos : otherPositions) {
+ assertThat(other.set(pos)).isTrue();
+ }
+
+ for (int pos : otherDensePositions) {
+ assertThat(other.set(256 + pos)).isTrue();
+ }
+
+ Mutable bitmap = bitmap(sparse(positions),
dense(DENSE_CONTAINER)).asMutable();
+ bitmap.merge(other);
+
+ assertThat(bitmap.cardinality()).isEqualTo(60);
+ assertThat(bitmap.descriptorArray()).containsExactly(4, 32);
+ assertSet(bitmap, 0, positions);
+ assertSet(bitmap, 0, otherPositions);
+ assertSet(bitmap, 1, DENSE_CONTAINER);
+ assertSet(bitmap, 1, otherDensePositions);
+ }
+
+ @Test
+ public void testMergeMutableWithMixedOverlays() {
+ int[] positions = new int[] {0, 10, 255};
+ int[] otherPositions = new int[] {0, 15, 255};
+
+ // positions 48-79
+ byte[] otherDense = new byte[32];
+ otherDense[6] = (byte) 0xFF;
+ otherDense[7] = (byte) 0xFF;
+ otherDense[8] = (byte) 0xFF;
+ otherDense[9] = (byte) 0xFF;
+
+ Mutable other = bitmap(sparse(otherPositions),
dense(otherDense)).asMutable();
+ assertThat(other.set(356)).isTrue(); // creates an overlay for container 1
only
+
+ Mutable bitmap = bitmap(sparse(positions),
dense(DENSE_CONTAINER)).asMutable();
+ bitmap.merge(other);
+
+ assertThat(bitmap.cardinality()).isEqualTo(61);
+ assertThat(bitmap.descriptorArray()).containsExactly(4, 32);
+ assertSet(bitmap, 0, positions);
+ assertSet(bitmap, 0, otherPositions);
+ assertSet(bitmap, 1, DENSE_CONTAINER);
+ assertSet(bitmap, 1, otherDense);
+ assertThat(bitmap.isSet(356)).isTrue();
+ }
+
+ @Test
+ public void testMergeDoesNotShareContainers() {
+ int[] otherPositions = range(0, 31);
+
+ Mutable other = bitmap(sparse(otherPositions),
dense(DENSE_CONTAINER)).asMutable();
+ assertThat(other.set(0)).as("Converts to dense but does not set a new
bit").isFalse();
+
+ // merging into empty containers copies the sparse and dense arrays
+ Mutable bitmap = MumblingBitmap.newMutableBitmap();
+ bitmap.merge(other);
+ assertThat(bitmap.cardinality()).isEqualTo(63);
+ assertThat(bitmap.descriptorArray()).containsExactly(31, 32);
+
+ assertThat(bitmap.set(100)).isTrue();
+ assertThat(bitmap.set(356)).isTrue();
+ assertThat(bitmap.cardinality()).isEqualTo(65);
+ assertThat(other.isSet(100)).isFalse();
+ assertThat(other.isSet(356)).isFalse();
+ assertThat(other.cardinality()).isEqualTo(63);
+
+ assertThat(other.set(101)).isTrue();
+ assertThat(other.set(357)).isTrue();
+ assertThat(other.cardinality()).isEqualTo(65);
+ assertThat(bitmap.isSet(101)).isFalse();
+ assertThat(bitmap.isSet(357)).isFalse();
+ assertThat(bitmap.cardinality()).isEqualTo(65);
+ }
+
+ /** Returns the positions from {@code start} (inclusive) to {@code end}
(exclusive). */
+ private static int[] range(int start, int end) {
+ return IntStream.range(start, end).toArray();
+ }
+
+ private static void assertSet(ManifestBitmap bitmap, int containerIndex,
int[] positions) {
+ for (int pos : positions) {
+ assertThat(bitmap.isSet(containerIndex * 256 + pos))
+ .as("Position %s in container %s", pos, containerIndex)
+ .isTrue();
+ }
+ }
+
+ /** Asserts that the positions set in a dense container's bytes are set in
the bitmap. */
+ private static void assertSet(ManifestBitmap bitmap, int containerIndex,
byte[] dense) {
+ for (int pos = 0; pos < 256; pos += 1) {
+ if ((dense[pos >>> 3] & (0x80 >>> (pos & 0b111))) != 0) {
+ assertThat(bitmap.isSet(containerIndex * 256 + pos))
+ .as("Position %s in container %s", pos, containerIndex)
+ .isTrue();
+ }
+ }
+ }
+
/** Copy into a buffer with garbage padding outside of position and limit. */
private static ByteBuffer relocate(ByteBuffer serialized) {
int prefix = 17;
