You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@activemq.apache.org by js...@apache.org on 2006/11/22 22:19:21 UTC
svn commit: r478324 - in /incubator/activemq/trunk/activemq-core/src:
main/java/org/apache/activemq/filter/ test/java/org/apache/activemq/filter/
Author: jstrachan
Date: Wed Nov 22 13:19:21 2006
New Revision: 478324
URL: http://svn.apache.org/viewvc?view=rev&rev=478324
Log:
Added a fix for AMQ-1068 to avoid lots of RAM being used up with deeply nested topic hierarchies - we basically create the AnyChild nodes on demand now rather than up front
Added:
incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/AnyChildDestinationNode.java (with props)
incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationNode.java (with props)
incubator/activemq/trunk/activemq-core/src/test/java/org/apache/activemq/filter/DestinationMapMemoryTest.java (with props)
Modified:
incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationMap.java
incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationMapNode.java
incubator/activemq/trunk/activemq-core/src/test/java/org/apache/activemq/filter/DestinationMapTest.java
Added: incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/AnyChildDestinationNode.java
URL: http://svn.apache.org/viewvc/incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/AnyChildDestinationNode.java?view=auto&rev=478324
==============================================================================
--- incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/AnyChildDestinationNode.java (added)
+++ incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/AnyChildDestinationNode.java Wed Nov 22 13:19:21 2006
@@ -0,0 +1,140 @@
+/**
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.activemq.filter;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Set;
+
+/**
+ * An implementation of {@link DestinationNode} which navigates all the children of the given node
+ * ignoring the name of the current path (so for navigating using * in a wildcard).
+ *
+ * @version $Revision$
+ */
+public class AnyChildDestinationNode implements DestinationNode {
+ private DestinationNode node;
+
+ public AnyChildDestinationNode(DestinationNode node) {
+ this.node = node;
+ }
+
+ public void appendMatchingValues(Set answer, String[] paths, int startIndex) {
+ Iterator iter = getChildNodes().iterator();
+ while (iter.hasNext()) {
+ DestinationNode child = (DestinationNode) iter.next();
+ child.appendMatchingValues(answer, paths, startIndex);
+ }
+ }
+
+
+ public void appendMatchingWildcards(Set answer, String[] paths, int startIndex) {
+ Iterator iter = getChildNodes().iterator();
+ while (iter.hasNext()) {
+ DestinationNode child = (DestinationNode) iter.next();
+ child.appendMatchingWildcards(answer, paths, startIndex);
+ }
+ }
+
+
+ public void appendDescendantValues(Set answer) {
+ Iterator iter = getChildNodes().iterator();
+ while (iter.hasNext()) {
+ DestinationNode child = (DestinationNode) iter.next();
+ child.appendDescendantValues(answer);
+ }
+ }
+
+ public DestinationNode getChild(String path) {
+ final Collection list = new ArrayList();
+ Iterator iter = getChildNodes().iterator();
+ while (iter.hasNext()) {
+ DestinationNode child = (DestinationNode) iter.next();
+ DestinationNode answer = child.getChild(path);
+ if (answer != null) {
+ list.add(answer);
+ }
+ }
+ if (!list.isEmpty()) {
+ return new AnyChildDestinationNode(this) {
+ protected Collection getChildNodes() {
+ return list;
+ }
+ };
+ }
+ return null;
+ }
+
+ public Collection getDesendentValues() {
+ Collection answer = new ArrayList();
+ Iterator iter = getChildNodes().iterator();
+ while (iter.hasNext()) {
+ DestinationNode child = (DestinationNode) iter.next();
+ answer.addAll(child.getDesendentValues());
+ }
+ return answer;
+ }
+
+ public Collection getValues() {
+ Collection answer = new ArrayList();
+ Iterator iter = getChildNodes().iterator();
+ while (iter.hasNext()) {
+ DestinationNode child = (DestinationNode) iter.next();
+ answer.addAll(child.getValues());
+ }
+ return answer;
+ }
+
+
+ public Collection getChildren() {
+ Collection answer = new ArrayList();
+ Iterator iter = getChildNodes().iterator();
+ while (iter.hasNext()) {
+ DestinationNode child = (DestinationNode) iter.next();
+ answer.addAll(child.getChildren());
+ }
+ return answer;
+ }
+
+ public Collection removeDesendentValues() {
+ Collection answer = new ArrayList();
+ Iterator iter = getChildNodes().iterator();
+ while (iter.hasNext()) {
+ DestinationNode child = (DestinationNode) iter.next();
+ answer.addAll(child.removeDesendentValues());
+ }
+ return answer;
+ }
+
+ public Collection removeValues() {
+ Collection answer = new ArrayList();
+ Iterator iter = getChildNodes().iterator();
+ while (iter.hasNext()) {
+ DestinationNode child = (DestinationNode) iter.next();
+ answer.addAll(child.removeValues());
+ }
+ return answer;
+ }
+
+ protected Collection getChildNodes() {
+ return node.getChildren();
+ }
+}
+
+
Propchange: incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/AnyChildDestinationNode.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/AnyChildDestinationNode.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/AnyChildDestinationNode.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Modified: incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationMap.java
URL: http://svn.apache.org/viewvc/incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationMap.java?view=diff&rev=478324&r1=478323&r2=478324
==============================================================================
--- incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationMap.java (original)
+++ incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationMap.java Wed Nov 22 13:19:21 2006
@@ -162,7 +162,7 @@
}
/**
- * @param dest
+ * @param key
* @return
*/
public Set removeAll(ActiveMQDestination key) {
Modified: incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationMapNode.java
URL: http://svn.apache.org/viewvc/incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationMapNode.java?view=diff&rev=478324&r1=478323&r2=478324
==============================================================================
--- incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationMapNode.java (original)
+++ incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationMapNode.java Wed Nov 22 13:19:21 2006
@@ -24,24 +24,33 @@
import java.util.List;
import java.util.Map;
import java.util.Set;
+import java.util.Iterator;
/**
* An implementation class used to implement {@link DestinationMap}
*
* @version $Revision: 1.2 $
*/
-public class DestinationMapNode {
+public class DestinationMapNode implements DestinationNode {
+ protected static final String ANY_CHILD = DestinationMap.ANY_CHILD;
+ protected static final String ANY_DESCENDENT = DestinationMap.ANY_DESCENDENT;
+
// we synchornize at the DestinationMap level
private DestinationMapNode parent;
private List values = new ArrayList();
private Map childNodes = new HashMap();
- private String path = "*";
- private DestinationMapNode anyChild;
- protected static final String ANY_CHILD = DestinationMap.ANY_CHILD;
- protected static final String ANY_DESCENDENT = DestinationMap.ANY_DESCENDENT;
+ private String path = "Root";
+// private DestinationMapNode anyChild;
+ private int pathLength;
public DestinationMapNode(DestinationMapNode parent) {
this.parent = parent;
+ if (parent == null) {
+ pathLength = 0;
+ }
+ else {
+ pathLength = parent.pathLength + 1;
+ }
}
/**
@@ -80,12 +89,12 @@
/**
* Returns the node which represents all children (i.e. the * node)
*/
- public DestinationMapNode getAnyChildNode() {
- if (anyChild == null) {
- anyChild = createChildNode();
- }
- return anyChild;
- }
+// public DestinationMapNode getAnyChildNode() {
+// if (anyChild == null) {
+// anyChild = createChildNode();
+// }
+// return anyChild;
+// }
/**
* Returns a mutable List of the values available at this node in the tree
@@ -99,7 +108,7 @@
*/
public List removeValues() {
ArrayList v = new ArrayList(values);
- parent.getAnyChildNode().getValues().removeAll(v);
+// parent.getAnyChildNode().getValues().removeAll(v);
values.clear();
pruneIfEmpty();
return v;
@@ -113,9 +122,9 @@
}
protected void removeDesendentValues(Set answer) {
- if (anyChild != null) {
- anyChild.removeDesendentValues(answer);
- }
+// if (anyChild != null) {
+// anyChild.removeDesendentValues(answer);
+// }
answer.addAll(removeValues());
}
@@ -133,12 +142,12 @@
values.add(value);
}
else {
- if (idx == paths.length - 1) {
- getAnyChildNode().getValues().add(value);
- }
- else {
- getAnyChildNode().add(paths, idx + 1, value);
- }
+// if (idx == paths.length - 1) {
+// getAnyChildNode().getValues().add(value);
+// }
+// else {
+// getAnyChildNode().add(paths, idx + 1, value);
+// }
getChildOrCreate(paths[idx]).add(paths, idx + 1, value);
}
}
@@ -149,33 +158,18 @@
pruneIfEmpty();
}
else {
- if (idx == paths.length - 1) {
- getAnyChildNode().getValues().remove(value);
- }
- else {
- getAnyChildNode().remove(paths, idx + 1, value);
- }
+// if (idx == paths.length - 1) {
+// getAnyChildNode().getValues().remove(value);
+// }
+// else {
+// getAnyChildNode().remove(paths, idx + 1, value);
+// }
getChildOrCreate(paths[idx]).remove(paths, ++idx, value);
}
}
public void removeAll(Set answer, String[] paths, int startIndex) {
-// if (idx >= paths.length) {
-// values.clear();
-// pruneIfEmpty();
-// }
-// else {
-// if (idx == paths.length - 1) {
-// getAnyChildNode().getValues().clear();
-// }
-// else {
-// getAnyChildNode().removeAll(paths, idx + 1);
-// }
-// getChildOrCreate(paths[idx]).removeAll(paths, ++idx);
-// }
-//
-
- DestinationMapNode node = this;
+ DestinationNode node = this;
for (int i = startIndex, size = paths.length; i < size && node != null; i++) {
String path = paths[i];
@@ -186,7 +180,8 @@
node.appendMatchingWildcards(answer, paths, i);
if (path.equals(ANY_CHILD)) {
- node = node.getAnyChildNode();
+ //node = node.getAnyChildNode();
+ node = new AnyChildDestinationNode(node);
}
else {
node = node.getChild(path);
@@ -200,11 +195,20 @@
}
- protected void appendDescendantValues(Set answer) {
+ public void appendDescendantValues(Set answer) {
answer.addAll(values);
- if (anyChild != null) {
- anyChild.appendDescendantValues(answer);
+
+ // lets add all the children too
+ Iterator iter = childNodes.values().iterator();
+ while (iter.hasNext()) {
+ DestinationNode child = (DestinationNode) iter.next();
+ child.appendDescendantValues(answer);
}
+
+ // TODO???
+// if (anyChild != null) {
+// anyChild.appendDescendantValues(answer);
+// }
}
/**
@@ -214,10 +218,16 @@
return new DestinationMapNode(this);
}
+ /**
+ * Matches any entries in the map containing wildcards
+ */
public void appendMatchingWildcards(Set answer, String[] paths, int idx) {
+ if (idx - 1 > pathLength) {
+ return;
+ }
DestinationMapNode wildCardNode = getChild(ANY_CHILD);
if (wildCardNode != null) {
- wildCardNode.appendMatchingValues(answer, paths, idx + 1);
+ wildCardNode.appendMatchingValues(answer, paths, idx+1);
}
wildCardNode = getChild(ANY_DESCENDENT);
if (wildCardNode != null) {
@@ -226,7 +236,7 @@
}
public void appendMatchingValues(Set answer, String[] paths, int startIndex) {
- DestinationMapNode node = this;
+ DestinationNode node = this;
boolean couldMatchAny = true;
for (int i = startIndex, size = paths.length; i < size && node != null; i++) {
String path = paths[i];
@@ -237,8 +247,10 @@
}
node.appendMatchingWildcards(answer, paths, i);
+
+
if (path.equals(ANY_CHILD)) {
- node = node.getAnyChildNode();
+ node = new AnyChildDestinationNode(node);
}
else {
node = node.getChild(path);
@@ -248,7 +260,7 @@
answer.addAll(node.getValues());
if (couldMatchAny) {
// lets allow FOO.BAR to match the FOO.BAR.> entry in the map
- DestinationMapNode child = node.getChild(ANY_DESCENDENT);
+ DestinationNode child = node.getChild(ANY_DESCENDENT);
if (child != null) {
answer.addAll(child.getValues());
}
Added: incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationNode.java
URL: http://svn.apache.org/viewvc/incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationNode.java?view=auto&rev=478324
==============================================================================
--- incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationNode.java (added)
+++ incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationNode.java Wed Nov 22 13:19:21 2006
@@ -0,0 +1,46 @@
+/**
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.activemq.filter;
+
+import java.util.Collection;
+import java.util.Set;
+
+/**
+ * Represents a node in the {@link DestinationMap} tree
+ *
+ * @version $Revision$
+ */
+public interface DestinationNode {
+ void appendMatchingValues(Set answer, String[] paths, int startIndex);
+
+ void appendMatchingWildcards(Set answer, String[] paths, int startIndex);
+
+ void appendDescendantValues(Set answer);
+
+ Collection getDesendentValues();
+
+ DestinationNode getChild(String path);
+
+ Collection getValues();
+
+ Collection getChildren();
+
+ Collection removeDesendentValues();
+
+ Collection removeValues();
+}
Propchange: incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationNode.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationNode.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: incubator/activemq/trunk/activemq-core/src/main/java/org/apache/activemq/filter/DestinationNode.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: incubator/activemq/trunk/activemq-core/src/test/java/org/apache/activemq/filter/DestinationMapMemoryTest.java
URL: http://svn.apache.org/viewvc/incubator/activemq/trunk/activemq-core/src/test/java/org/apache/activemq/filter/DestinationMapMemoryTest.java?view=auto&rev=478324
==============================================================================
--- incubator/activemq/trunk/activemq-core/src/test/java/org/apache/activemq/filter/DestinationMapMemoryTest.java (added)
+++ incubator/activemq/trunk/activemq-core/src/test/java/org/apache/activemq/filter/DestinationMapMemoryTest.java Wed Nov 22 13:19:21 2006
@@ -0,0 +1,55 @@
+/**
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.activemq.filter;
+
+import junit.framework.TestCase;
+import org.apache.activemq.command.ActiveMQDestination;
+import org.apache.activemq.command.ActiveMQTopic;
+
+public class DestinationMapMemoryTest extends TestCase {
+
+
+ public void testLongDestinationPath() throws Exception {
+ ActiveMQTopic d1 = new ActiveMQTopic("1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18");
+ DestinationMap map = new DestinationMap();
+ map.put(d1, d1);
+ }
+
+ public void testVeryLongestinationPaths() throws Exception {
+
+ for (int i = 1; i < 100; i++) {
+ String name = "1";
+ for (int j = 2; j <= i; j++) {
+ name += "." + j;
+ }
+ System.out.println("Checking: " + name);
+ try {
+ ActiveMQDestination d1 = createDestination(name);
+ DestinationMap map = new DestinationMap();
+ map.put(d1, d1);
+ }
+ catch (Throwable e) {
+ fail("Destination name too long: " + name + " : " + e);
+ }
+ }
+ }
+
+ protected ActiveMQDestination createDestination(String name) {
+ return new ActiveMQTopic(name);
+ }
+}
Propchange: incubator/activemq/trunk/activemq-core/src/test/java/org/apache/activemq/filter/DestinationMapMemoryTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: incubator/activemq/trunk/activemq-core/src/test/java/org/apache/activemq/filter/DestinationMapMemoryTest.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: incubator/activemq/trunk/activemq-core/src/test/java/org/apache/activemq/filter/DestinationMapMemoryTest.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Modified: incubator/activemq/trunk/activemq-core/src/test/java/org/apache/activemq/filter/DestinationMapTest.java
URL: http://svn.apache.org/viewvc/incubator/activemq/trunk/activemq-core/src/test/java/org/apache/activemq/filter/DestinationMapTest.java?view=diff&rev=478324&r1=478323&r2=478324
==============================================================================
--- incubator/activemq/trunk/activemq-core/src/test/java/org/apache/activemq/filter/DestinationMapTest.java (original)
+++ incubator/activemq/trunk/activemq-core/src/test/java/org/apache/activemq/filter/DestinationMapTest.java Wed Nov 22 13:19:21 2006
@@ -193,6 +193,19 @@
assertMapValue("TEST.BAR.*", v2, v5, v6);
}
+ public void testDoubleWildcardDoesNotMatchLongerPattern() throws Exception {
+ put("TEST.*", v1);
+ put("TEST.BAR.D3", v2);
+
+ assertMapValue("*.*.D3", v2);
+ }
+
+ public void testWildcardAtEndOfPathAndAtBeginningOfSearch() throws Exception {
+ put("TEST.*", v1);
+
+ assertMapValue("*.D1", v1);
+ }
+
public void testAnyPathWildcardInMap() throws Exception {
put("TEST.FOO.>", v1);