You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@rocketmq.apache.org by hu...@apache.org on 2022/03/29 04:32:10 UTC
[rocketmq-mqtt] 42/43: optimize func of trie to more readable and increase its codeCov to 100% (#43)
This is an automated email from the ASF dual-hosted git repository.
huzongtang pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/rocketmq-mqtt.git
commit 09cfe62e8472c1184f4739abb18f083c3d552399
Author: YongXing <xy...@gmail.com>
AuthorDate: Fri Mar 25 10:56:18 2022 +0800
optimize func of trie to more readable and increase its codeCov to 100% (#43)
Co-authored-by: YongXing [勇幸] <yo...@xiaomi.com>
---
.../apache/rocketmq/mqtt/common/model/Trie.java | 100 +++++++++------------
.../apache/rocketmq/mqtt/common/test/TestTrie.java | 73 +++++++++++++--
2 files changed, 109 insertions(+), 64 deletions(-)
diff --git a/mqtt-common/src/main/java/org/apache/rocketmq/mqtt/common/model/Trie.java b/mqtt-common/src/main/java/org/apache/rocketmq/mqtt/common/model/Trie.java
index 675d04b..a7aa9ef 100644
--- a/mqtt-common/src/main/java/org/apache/rocketmq/mqtt/common/model/Trie.java
+++ b/mqtt-common/src/main/java/org/apache/rocketmq/mqtt/common/model/Trie.java
@@ -17,7 +17,6 @@
package org.apache.rocketmq.mqtt.common.model;
-
import org.apache.rocketmq.mqtt.common.util.TopicUtils;
import java.util.HashMap;
@@ -77,13 +76,9 @@ public class Trie<K, V> {
}
V oldValue = currentNode.valueSet.remove(valueKey);
//clean the empty node
- while (currentNode.children.isEmpty() && currentNode.valueSet.isEmpty()) {
- if (currentNode.parentNode != null) {
- currentNode.parentNode.children.remove(keyArray[--level]);
- currentNode = currentNode.parentNode;
- } else {
- break;
- }
+ while (currentNode.children.isEmpty() && currentNode.valueSet.isEmpty() && currentNode.parentNode != null) {
+ currentNode.parentNode.children.remove(keyArray[--level]);
+ currentNode = currentNode.parentNode;
}
return oldValue;
} catch (Throwable e) {
@@ -136,10 +131,24 @@ public class Trie<K, V> {
}
private Set<String> findValuePath(TrieNode<K, V> currentNode, String[] topicArray, int level, int maxLevel,
- StringBuilder builder, boolean isJinFlag) {
+ StringBuilder builder, boolean isNumberSign) {
Set<String> result = new HashSet<>();
+ // match end of path
+ boolean isPathEnd = (level == maxLevel || isNumberSign) && !currentNode.valueSet.isEmpty() && builder.length() > 0;
+ if (isPathEnd) {
+ result.add(TopicUtils.normalizeTopic(builder.toString().substring(0, builder.length() - 1)));
+ }
+ // match the '#'
+ TrieNode numberMatch = currentNode.children.get(Constants.NUMBER_SIGN);
+ if (numberMatch != null) {
+ int start = builder.length();
+ builder.append(Constants.NUMBER_SIGN).append(Constants.MQTT_TOPIC_DELIMITER);
+ result.addAll(findValuePath(numberMatch, topicArray, level + 1, maxLevel, builder, true));
+ builder.delete(start, builder.length());
+ }
+ // match the mqtt-topic path
if (level < maxLevel && !currentNode.children.isEmpty()) {
- //first match the precise
+ // match the precise
TrieNode trieNode = currentNode.children.get(topicArray[level]);
if (trieNode != null) {
int start = builder.length();
@@ -147,35 +156,14 @@ public class Trie<K, V> {
result.addAll(findValuePath(trieNode, topicArray, level + 1, maxLevel, builder, false));
builder.delete(start, builder.length());
}
- //match the #
- TrieNode jinMatch = currentNode.children.get(Constants.NUMBER_SIGN);
- if (jinMatch != null) {
- int start = builder.length();
- builder.append(Constants.NUMBER_SIGN).append(Constants.MQTT_TOPIC_DELIMITER);
- result.addAll(findValuePath(jinMatch, topicArray, level + 1, maxLevel, builder, true));
- builder.delete(start, builder.length());
- }
- //match the +
- TrieNode jiaMatch = currentNode.children.get(Constants.PLUS_SIGN);
- if (jiaMatch != null) {
+ // match the '+'
+ TrieNode plusMatch = currentNode.children.get(Constants.PLUS_SIGN);
+ if (plusMatch != null) {
int start = builder.length();
builder.append(Constants.PLUS_SIGN).append(Constants.MQTT_TOPIC_DELIMITER);
- result.addAll(findValuePath(jiaMatch, topicArray, level + 1, maxLevel, builder, false));
+ result.addAll(findValuePath(plusMatch, topicArray, level + 1, maxLevel, builder, false));
builder.delete(start, builder.length());
}
- } else {
- //match the #
- TrieNode jinMatch = currentNode.children.get(Constants.NUMBER_SIGN);
- if (jinMatch != null) {
- int start = builder.length();
- builder.append(Constants.NUMBER_SIGN).append(Constants.MQTT_TOPIC_DELIMITER);
- result.addAll(findValuePath(jinMatch, topicArray, level + 1, maxLevel, builder, true));
- builder.delete(start, builder.length());
- }
- boolean jin = (level == maxLevel || isJinFlag) && !currentNode.valueSet.isEmpty() && builder.length() > 0;
- if (jin) {
- result.add(TopicUtils.normalizeTopic(builder.toString().substring(0, builder.length() - 1)));
- }
}
return result;
}
@@ -198,36 +186,31 @@ public class Trie<K, V> {
}
private Map<K, V> findValueSet(TrieNode<K, V> currentNode, String[] topicArray, int level, int maxLevel,
- boolean isJinFlag) {
+ boolean isNumberSign) {
Map<K, V> result = new HashMap<>(16);
+ // match the mqtt-topic leaf or match the leaf node of trie
+ if (level == maxLevel || isNumberSign) {
+ result.putAll(currentNode.valueSet);
+ }
+ // match the '#'
+ TrieNode numberMatch = currentNode.children.get(Constants.NUMBER_SIGN);
+ if (numberMatch != null) {
+ result.putAll(findValueSet(numberMatch, topicArray, level + 1, maxLevel, true));
+ }
+ // match the mqtt-topic path
if (level < maxLevel && !currentNode.children.isEmpty()) {
- //first match the precise
+ // match the precise
TrieNode trieNode = currentNode.children.get(topicArray[level]);
if (trieNode != null) {
result.putAll(findValueSet(trieNode, topicArray, level + 1, maxLevel, false));
}
- //match the #
- TrieNode jinMatch = currentNode.children.get(Constants.NUMBER_SIGN);
- if (jinMatch != null) {
- result.putAll(findValueSet(jinMatch, topicArray, level + 1, maxLevel, true));
- }
- //match the +
- TrieNode jiaMatch = currentNode.children.get(Constants.PLUS_SIGN);
- if (jiaMatch != null) {
- result.putAll(findValueSet(jiaMatch, topicArray, level + 1, maxLevel, false));
+ // match the '+'
+ TrieNode plusMatch = currentNode.children.get(Constants.PLUS_SIGN);
+ if (plusMatch != null) {
+ result.putAll(findValueSet(plusMatch, topicArray, level + 1, maxLevel, false));
}
- return result;
- } else {
- //match the #
- TrieNode jinMatch = currentNode.children.get(Constants.NUMBER_SIGN);
- if (jinMatch != null) {
- result.putAll(findValueSet(jinMatch, topicArray, level + 1, maxLevel, true));
- }
- if (level == maxLevel || isJinFlag) {
- result.putAll(currentNode.valueSet);
- }
- return result;
}
+ return result;
}
class TrieNode<K, V> {
@@ -239,5 +222,4 @@ public class Trie<K, V> {
this.parentNode = parentNode;
}
}
-
-}
+}
\ No newline at end of file
diff --git a/mqtt-common/src/test/java/org/apache/rocketmq/mqtt/common/test/TestTrie.java b/mqtt-common/src/test/java/org/apache/rocketmq/mqtt/common/test/TestTrie.java
index 3b12714..d009a88 100644
--- a/mqtt-common/src/test/java/org/apache/rocketmq/mqtt/common/test/TestTrie.java
+++ b/mqtt-common/src/test/java/org/apache/rocketmq/mqtt/common/test/TestTrie.java
@@ -20,18 +20,81 @@
package org.apache.rocketmq.mqtt.common.test;
import org.apache.commons.collections.CollectionUtils;
+import org.apache.commons.collections.MapUtils;
import org.apache.rocketmq.mqtt.common.model.Trie;
import org.junit.Assert;
import org.junit.Test;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
public class TestTrie {
@Test
public void test() {
Trie<String, String> trie = new Trie<>();
- trie.addNode("test", "test", "test");
- Assert.assertTrue(trie.getNodePath("test").contains("test"));
- trie.deleteNode("test", "test");
- Assert.assertTrue(CollectionUtils.isEmpty(trie.getNodePath("test")));
+ List<String> topicFilterList = new ArrayList<>(Arrays.asList(
+ "k/r/b/", "k/r/a/c/", "k/r/#/", "k/r/+/", "k/r/+/c/", "k/r/+/#/", "k/a/b/c/r/"));
+
+ int index = 0;
+ for (String topicFilter : topicFilterList) {
+ // test 'addNode'
+ trie.addNode(topicFilter, topicFilter, Integer.toString(index++));
+ }
+
+ // test 'countSubRecords'
+ Assert.assertEquals(topicFilterList.size(), trie.countSubRecords());
+
+ // test 'getNode' by 'k/r/b'
+ String krbTopic = "k/r/b";
+ Set<String> krbFilterSet = new HashSet<>(Arrays.asList("k/r/b/", "k/r/#/", "k/r/+/", "k/r/+/#/"));
+ Set<String> krbValues = new HashSet<>(trie.getNode(krbTopic).values());
+ Assert.assertEquals(krbFilterSet, krbValues);
+ // test 'getNodePath'
+ Set<String> krbValPaths = new HashSet<>(trie.getNodePath(krbTopic));
+ Assert.assertEquals(krbFilterSet, krbValPaths);
+
+ // test 'getNode' by 'k/r/a/c'
+ String kracTopic = "k/r/a/c";
+ Set<String> kracFilterSet = new HashSet<>(Arrays.asList("k/r/a/c/", "k/r/#/", "k/r/+/c/", "k/r/+/#/"));
+ Set<String> kracValues = new HashSet<>(trie.getNode(kracTopic).values());
+ Assert.assertEquals(kracFilterSet, kracValues);
+ // test 'getNodePath'
+ Set<String> kracValPaths = new HashSet<>(trie.getNodePath(kracTopic));
+ Assert.assertEquals(kracFilterSet, kracValPaths);
+
+ // test 'getNode' by 'k/r/a'
+ String kraTopic = "k/r/a";
+ Set<String> kraFilterSet = new HashSet<>(Arrays.asList("k/r/#/", "k/r/+/", "k/r/+/#/"));
+ Set<String> kraValues = new HashSet<>(trie.getNode(kraTopic).values());
+ Assert.assertEquals(kraFilterSet, kraValues);
+ // test 'getNodePath'
+ Set<String> kraValPaths = new HashSet<>(trie.getNodePath(kraTopic));
+ Assert.assertEquals(kraFilterSet, kraValPaths);
+
+ // test 'deleteNode' by index of 'k/a/b/c/r'
+ String kabcr = topicFilterList.get(topicFilterList.size() - 1);
+ Assert.assertFalse(CollectionUtils.isEmpty(trie.getNodePath(kabcr)));
+ trie.deleteNode(kabcr, String.valueOf(topicFilterList.size() - 1));
+ Assert.assertTrue(CollectionUtils.isEmpty(trie.getNodePath(kabcr)));
+
+ // test 'traverseAll'
+ Trie<String, String> finalTrie = trie;
+ String krbPath = topicFilterList.get(0);
+ trie.traverseAll((path, nodeKey) -> {
+ if (krbPath.equals(path)) {
+ finalTrie.deleteNode(path, String.valueOf(0));
+ }
+ });
+ Assert.assertFalse(trie.getNodePath(krbPath).contains(krbPath));
+
+ // test delete all trie node
+ for (int i = 0; i < topicFilterList.size(); ++i) {
+ trie.deleteNode(topicFilterList.get(i), String.valueOf(i));
+ }
+ Assert.assertTrue(MapUtils.isEmpty(trie.getNode(topicFilterList.get(0))));
}
-}
+}
\ No newline at end of file