You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@sis.apache.org by de...@apache.org on 2020/01/15 14:23:27 UTC
[sis] branch geoapi-4.0 updated: Initial implementation of
Spliterator.trySplit() for parallelism during PointTree traversal.
Implementation is incomplete since it splits only the first node;
we should go down in other nodes too.
This is an automated email from the ASF dual-hosted git repository.
desruisseaux pushed a commit to branch geoapi-4.0
in repository https://gitbox.apache.org/repos/asf/sis.git
The following commit(s) were added to refs/heads/geoapi-4.0 by this push:
new 29ac56d Initial implementation of Spliterator.trySplit() for parallelism during PointTree traversal. Implementation is incomplete since it splits only the first node; we should go down in other nodes too.
29ac56d is described below
commit 29ac56de59ea5e9404671992a186ebad41e0c245
Author: Martin Desruisseaux <ma...@geomatys.com>
AuthorDate: Wed Jan 15 15:22:34 2020 +0100
Initial implementation of Spliterator.trySplit() for parallelism during PointTree traversal.
Implementation is incomplete since it splits only the first node; we should go down in other nodes too.
---
.../org/apache/sis/index/tree/NodeIterator.java | 40 +++++++++++++++++++---
1 file changed, 35 insertions(+), 5 deletions(-)
diff --git a/core/sis-feature/src/main/java/org/apache/sis/index/tree/NodeIterator.java b/core/sis-feature/src/main/java/org/apache/sis/index/tree/NodeIterator.java
index ebf786a..3cf27cc 100644
--- a/core/sis-feature/src/main/java/org/apache/sis/index/tree/NodeIterator.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/index/tree/NodeIterator.java
@@ -57,8 +57,8 @@ class NodeIterator<E> implements Spliterator<E> {
private final long bitmask;
/**
- * The region on which to iterate. The first half are minimal coordinates
- * and the second half are maximal coordinates.
+ * The region on which to iterate. The first half are minimal coordinates and the second
+ * half are maximal coordinates. The content of this array should not be modified.
*/
private final double[] bounds;
@@ -115,6 +115,24 @@ class NodeIterator<E> implements Spliterator<E> {
}
/**
+ * Creates a new iterator initialized to a copy of the given iterator.
+ *
+ * @param quadrants the value to assign to {@link Cursor#quadrants}.
+ * That bitmask shall not intersect the bitmask of {@code other.cursor}.
+ */
+ private NodeIterator(final NodeIterator<E> other, final long quadrants) {
+ final Cursor<E> c = other.cursor;
+ locator = other.locator;
+ bitmask = other.bitmask;
+ bounds = other.bounds;
+ cursor = new Cursor<>(c.region);
+ cursor.parent = c.parent;
+ cursor.node = c.node;
+ cursor.quadrants = quadrants;
+ current = next();
+ }
+
+ /**
* A provider for arrays of elements of child nodes contained in a {@link PointTreeNode}.
* The starting point is {@link PointTree#root}. A new {@link Cursor} instance is created
* for each level when the node at next level is itself a parent of at least two nodes
@@ -368,12 +386,24 @@ class NodeIterator<E> implements Spliterator<E> {
}
/**
- * If this iterator can be partitioned, returns an iterator covering a strict prefix of the elements.
- *
- * @todo Checks {@link Cursor#quadrants} and take half of the bits.
+ * If this iterator can be partitioned, returns an iterator covering about half of the elements.
+ * Otherwise returns {@code null}.
*/
@Override
public final Spliterator<E> trySplit() {
+ final Cursor<E> c = cursor;
+ if (c != null) {
+ long half = 0;
+ for (int n = Long.bitCount(c.quadrants) / 2; n >= 0; --n) {
+ final long q = Long.lowestOneBit(c.quadrants);
+ c.quadrants &= ~q;
+ half |= q;
+ }
+ if (half != 0) {
+ return new NodeIterator<>(this, half);
+ }
+ // TODO: go down in the tree and explore other quadrants.
+ }
return null;
}