You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iotdb.apache.org by ja...@apache.org on 2022/10/17 01:54:20 UTC
[iotdb] branch master updated: [IODB-4657] Fix PatternTreeMap#getOverlapped does not return correct values (#7625)
This is an automated email from the ASF dual-hosted git repository.
jackietien pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/iotdb.git
The following commit(s) were added to refs/heads/master by this push:
new c912f937cd [IODB-4657] Fix PatternTreeMap#getOverlapped does not return correct values (#7625)
c912f937cd is described below
commit c912f937cdc8f6bd3476721422f654f68a0a0dab
Author: Chen YZ <43...@users.noreply.github.com>
AuthorDate: Mon Oct 17 09:54:15 2022 +0800
[IODB-4657] Fix PatternTreeMap#getOverlapped does not return correct values (#7625)
---
.../apache/iotdb/commons/path/PatternTreeMap.java | 44 ++++++-----
.../iotdb/db/metadata/path/PatternTreeMapTest.java | 88 +++++++++++-----------
2 files changed, 69 insertions(+), 63 deletions(-)
diff --git a/node-commons/src/main/java/org/apache/iotdb/commons/path/PatternTreeMap.java b/node-commons/src/main/java/org/apache/iotdb/commons/path/PatternTreeMap.java
index 2d701dd2c0..8b065fc151 100644
--- a/node-commons/src/main/java/org/apache/iotdb/commons/path/PatternTreeMap.java
+++ b/node-commons/src/main/java/org/apache/iotdb/commons/path/PatternTreeMap.java
@@ -23,6 +23,7 @@ import org.apache.iotdb.commons.conf.IoTDBConstant;
import javax.annotation.concurrent.NotThreadSafe;
import java.util.ArrayList;
+import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.function.BiConsumer;
@@ -119,12 +120,12 @@ public class PatternTreeMap<V, VSerializer extends PathPatternNode.Serializer<V>
* Get value list related to PathPattern that overlapped with fullPath.
*
* @param fullPath full path without wildcard
- * @return value list
+ * @return de-duplicated value list
*/
public List<V> getOverlapped(PartialPath fullPath) {
- List<V> res = new ArrayList<>();
+ Set<V> res = new HashSet<>();
searchOverlapped(root, fullPath.getNodes(), 0, res);
- return res;
+ return new ArrayList<>(res);
}
/**
@@ -133,19 +134,19 @@ public class PatternTreeMap<V, VSerializer extends PathPatternNode.Serializer<V>
* @param node current PathPatternNode
* @param pathNodes pathNodes of key
* @param pos current index of pathNodes
- * @param resultList result list
+ * @param resultSet result set
*/
private void searchOverlapped(
- PathPatternNode<V, VSerializer> node, String[] pathNodes, int pos, List<V> resultList) {
+ PathPatternNode<V, VSerializer> node, String[] pathNodes, int pos, Set<V> resultSet) {
if (pos == pathNodes.length - 1) {
- resultList.addAll(node.getValues());
+ resultSet.addAll(node.getValues());
return;
}
if (node.isMultiLevelWildcard()) {
- searchOverlapped(node, pathNodes, pos + 1, resultList);
+ searchOverlapped(node, pathNodes, pos + 1, resultSet);
}
for (PathPatternNode<V, VSerializer> child : node.getMatchChildren(pathNodes[pos + 1])) {
- searchOverlapped(child, pathNodes, pos + 1, resultList);
+ searchOverlapped(child, pathNodes, pos + 1, resultSet);
}
}
@@ -155,14 +156,18 @@ public class PatternTreeMap<V, VSerializer extends PathPatternNode.Serializer<V>
*
* @param devicePath device path without wildcard
* @param measurements list of measurements
- * @return value list
+ * @return de-duplicated value list
*/
public List<List<V>> getOverlapped(PartialPath devicePath, List<String> measurements) {
- List<List<V>> res = new ArrayList<>();
+ List<Set<V>> resultSet = new ArrayList<>();
for (int i = 0; i < measurements.size(); i++) {
- res.add(new ArrayList<>());
+ resultSet.add(new HashSet<>());
+ }
+ searchOverlapped(root, devicePath.getNodes(), 0, measurements, resultSet);
+ List<List<V>> res = new ArrayList<>();
+ for (Set<V> set : resultSet) {
+ res.add(new ArrayList<>(set));
}
- searchOverlapped(root, devicePath.getNodes(), 0, measurements, res);
return res;
}
@@ -171,29 +176,32 @@ public class PatternTreeMap<V, VSerializer extends PathPatternNode.Serializer<V>
*
* @param node current PathPatternNode
* @param deviceNodes pathNodes of device
- * @param pos current index of pathNodes
+ * @param pos current index of deviceNodes
* @param measurements list of measurements under device
- * @param resultList result list
+ * @param resultSet result set
*/
private void searchOverlapped(
PathPatternNode<V, VSerializer> node,
String[] deviceNodes,
int pos,
List<String> measurements,
- List<List<V>> resultList) {
+ List<Set<V>> resultSet) {
if (pos == deviceNodes.length - 1) {
for (int i = 0; i < measurements.size(); i++) {
for (PathPatternNode<V, VSerializer> child : node.getMatchChildren(measurements.get(i))) {
- resultList.get(i).addAll(child.getValues());
+ resultSet.get(i).addAll(child.getValues());
+ }
+ if (node.isMultiLevelWildcard()) {
+ resultSet.get(i).addAll(node.getValues());
}
}
return;
}
if (node.isMultiLevelWildcard()) {
- searchOverlapped(node, deviceNodes, pos + 1, measurements, resultList);
+ searchOverlapped(node, deviceNodes, pos + 1, measurements, resultSet);
}
for (PathPatternNode<V, VSerializer> child : node.getMatchChildren(deviceNodes[pos + 1])) {
- searchOverlapped(child, deviceNodes, pos + 1, measurements, resultList);
+ searchOverlapped(child, deviceNodes, pos + 1, measurements, resultSet);
}
}
}
diff --git a/server/src/test/java/org/apache/iotdb/db/metadata/path/PatternTreeMapTest.java b/server/src/test/java/org/apache/iotdb/db/metadata/path/PatternTreeMapTest.java
index 3a328cc359..268c51080c 100644
--- a/server/src/test/java/org/apache/iotdb/db/metadata/path/PatternTreeMapTest.java
+++ b/server/src/test/java/org/apache/iotdb/db/metadata/path/PatternTreeMapTest.java
@@ -52,34 +52,33 @@ public class PatternTreeMapTest {
patternTreeMap.append(new PartialPath("root.**.d1.**"), "H");
patternTreeMap.append(new PartialPath("root.*.d1.**"), "I");
patternTreeMap.append(new PartialPath("root.**"), "J");
+ patternTreeMap.append(new PartialPath("root.**.**"), "K");
+
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d1.s1"),
- new HashSet<>(Arrays.asList("A", "B", "C", "D", "E", "G", "H", "I", "J")));
- checkOverlapped(
- patternTreeMap, new PartialPath("root.sg2.s1"), new HashSet<>(Arrays.asList("B", "J")));
+ Arrays.asList("A", "B", "C", "D", "E", "G", "H", "I", "J", "K"));
+ checkOverlapped(patternTreeMap, new PartialPath("root.sg2.s1"), Arrays.asList("B", "J", "K"));
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d1.s2"),
- new HashSet<>(Arrays.asList("E", "F", "G", "H", "I", "J")));
+ Arrays.asList("E", "F", "G", "H", "I", "J", "K"));
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d1.v1.s1"),
- new HashSet<>(Arrays.asList("B", "E", "H", "I", "J")));
+ Arrays.asList("B", "E", "H", "I", "J", "K"));
checkOverlappedByDeviceMeasurements(
patternTreeMap,
new PartialPath("root.sg1.d1"),
Arrays.asList("s1", "s2"),
Arrays.asList(
- new HashSet<>(Arrays.asList("A", "B", "C", "D", "E", "G", "H", "I", "J")),
- new HashSet<>(Arrays.asList("E", "F", "G", "H", "I", "J"))));
+ Arrays.asList("A", "B", "C", "D", "E", "G", "H", "I", "J", "K"),
+ Arrays.asList("E", "F", "G", "H", "I", "J", "K")));
checkOverlappedByDeviceMeasurements(
patternTreeMap,
new PartialPath("root.sg1.d2"),
Arrays.asList("s1", "s2"),
- Arrays.asList(
- new HashSet<>(Arrays.asList("B", "C", "E", "G", "H", "I", "J")),
- new HashSet<>(Arrays.asList("E", "F", "G", "H", "I", "J"))));
+ Arrays.asList(Arrays.asList("B", "C", "E", "J", "K"), Arrays.asList("E", "F", "J", "K")));
// delete leaf node with common parent
patternTreeMap.delete(new PartialPath("root.**.d1.*"), "G");
// only delete value, no delete leaf node
@@ -89,29 +88,30 @@ public class PatternTreeMapTest {
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d1.s1"),
- new HashSet<>(Arrays.asList("A", "B", "C", "E", "H", "I")));
+ Arrays.asList("A", "B", "C", "E", "H", "I", "K"));
checkOverlapped(
- patternTreeMap,
- new PartialPath("root.sg1.d1.s2"),
- new HashSet<>(Arrays.asList("E", "F", "H", "I")));
+ patternTreeMap, new PartialPath("root.sg1.d1.s2"), Arrays.asList("E", "F", "H", "I", "K"));
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d1.v1.s1"),
- new HashSet<>(Arrays.asList("B", "E", "H", "I")));
+ Arrays.asList("B", "E", "H", "I", "K"));
checkOverlappedByDeviceMeasurements(
patternTreeMap,
new PartialPath("root.sg1.d1"),
Arrays.asList("s1", "s2"),
Arrays.asList(
- new HashSet<>(Arrays.asList("A", "B", "C", "E", "H", "I")),
- new HashSet<>(Arrays.asList("E", "F", "H", "I"))));
+ Arrays.asList("A", "B", "C", "E", "H", "I", "K"),
+ Arrays.asList("E", "F", "H", "I", "K")));
checkOverlappedByDeviceMeasurements(
patternTreeMap,
new PartialPath("root.sg1.d2"),
Arrays.asList("s1", "s2"),
- Arrays.asList(
- new HashSet<>(Arrays.asList("B", "C", "E", "H", "I")),
- new HashSet<>(Arrays.asList("E", "F", "H", "I"))));
+ Arrays.asList(Arrays.asList("B", "C", "E", "K"), Arrays.asList("E", "F", "K")));
+ checkOverlappedByDeviceMeasurements(
+ patternTreeMap,
+ new PartialPath("root.sg1.v1.d1"),
+ Arrays.asList("s1", "s2"),
+ Arrays.asList(Arrays.asList("B", "E", "H", "K"), Arrays.asList("E", "F", "H", "K")));
}
@Test
@@ -140,35 +140,32 @@ public class PatternTreeMapTest {
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d1.s1"),
- new HashSet<>(
- Arrays.asList(
- new Deletion(new PartialPath("root.sg1.d1.s1"), 1, 1, 3),
- new Deletion(new PartialPath("root.sg1.d1.s1"), 1, 6, 10),
- new Deletion(new PartialPath("root.**.s1"), 5, 10, 100),
- new Deletion(new PartialPath("root.**.s1"), 10, 100, 200),
- new Deletion(new PartialPath("root.**"), 5, 10, 100))));
+ Arrays.asList(
+ new Deletion(new PartialPath("root.sg1.d1.s1"), 1, 1, 3),
+ new Deletion(new PartialPath("root.sg1.d1.s1"), 1, 6, 10),
+ new Deletion(new PartialPath("root.**.s1"), 5, 10, 100),
+ new Deletion(new PartialPath("root.**.s1"), 10, 100, 200),
+ new Deletion(new PartialPath("root.**"), 5, 10, 100)));
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d2.s1"),
- new HashSet<>(
- Arrays.asList(
- new Deletion(new PartialPath("root.**.s1"), 5, 10, 100),
- new Deletion(new PartialPath("root.**.s1"), 10, 100, 200),
- new Deletion(new PartialPath("root.**"), 5, 10, 100))));
+ Arrays.asList(
+ new Deletion(new PartialPath("root.**.s1"), 5, 10, 100),
+ new Deletion(new PartialPath("root.**.s1"), 10, 100, 200),
+ new Deletion(new PartialPath("root.**"), 5, 10, 100)));
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d1.s2"),
- new HashSet<>(
- Collections.singletonList(new Deletion(new PartialPath("root.**"), 5, 10, 100))));
+ Collections.singletonList(new Deletion(new PartialPath("root.**"), 5, 10, 100)));
}
private <T> void checkOverlapped(
- PatternTreeMap<T, ?> patternTreeMap, PartialPath partialPath, Set<T> resultSet) {
- List<T> list = patternTreeMap.getOverlapped(partialPath);
- Assert.assertEquals(resultSet.size(), list.size());
- for (T o : list) {
+ PatternTreeMap<T, ?> patternTreeMap, PartialPath partialPath, List<T> expectedList) {
+ Set<T> resultSet = new HashSet<>(patternTreeMap.getOverlapped(partialPath));
+ Assert.assertEquals(expectedList.size(), resultSet.size());
+ for (T o : expectedList) {
Assert.assertTrue(resultSet.contains(o));
}
}
@@ -177,14 +174,15 @@ public class PatternTreeMapTest {
PatternTreeMap<T, ?> patternTreeMap,
PartialPath devicePath,
List<String> measurements,
- List<Set<T>> resultSet) {
- List<List<T>> list = patternTreeMap.getOverlapped(devicePath, measurements);
- Assert.assertEquals(resultSet.size(), list.size());
+ List<List<T>> expectedList) {
+ List<List<T>> actualList = patternTreeMap.getOverlapped(devicePath, measurements);
+ Assert.assertEquals(expectedList.size(), actualList.size());
for (int i = 0; i < measurements.size(); i++) {
- List<T> subList = list.get(i);
- Set<T> subSet = resultSet.get(i);
- for (T o : subList) {
- Assert.assertTrue(subSet.contains(o));
+ List<T> expectedSubList = expectedList.get(i);
+ Set<T> actualSubSet = new HashSet<>(actualList.get(i));
+ Assert.assertEquals(expectedSubList.size(), actualSubSet.size());
+ for (T o : expectedSubList) {
+ Assert.assertTrue(actualSubSet.contains(o));
}
}
}