activemq-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jstrac...@apache.org
Subject svn commit: r478324 - in /incubator/activemq/trunk/activemq-core/src: main/java/org/apache/activemq/filter/ test/java/org/apache/activemq/filter/
Date Wed, 22 Nov 2006 21:19:21 GMT
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);
 



Mime
View raw message