001/** 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.activemq.filter; 018 019import java.util.ArrayList; 020import java.util.Collection; 021import java.util.HashMap; 022import java.util.HashSet; 023import java.util.List; 024import java.util.Map; 025import java.util.Set; 026 027/** 028 * An implementation class used to implement {@link DestinationMap} 029 * 030 * 031 */ 032public class DestinationMapNode implements DestinationNode { 033 protected static final String ANY_CHILD = DestinationMap.ANY_CHILD; 034 protected static final String ANY_DESCENDENT = DestinationMap.ANY_DESCENDENT; 035 036 // we synchronize at the DestinationMap level 037 private DestinationMapNode parent; 038 private List<Object> values = new ArrayList<Object>(); 039 private Map<String, DestinationNode> childNodes = new HashMap<String, DestinationNode>(); 040 private String path = "Root"; 041 // private DestinationMapNode anyChild; 042 private int pathLength; 043 044 public DestinationMapNode(DestinationMapNode parent) { 045 this.parent = parent; 046 if (parent == null) { 047 pathLength = 0; 048 } else { 049 pathLength = parent.pathLength + 1; 050 } 051 } 052 053 /** 054 * Returns the child node for the given named path or null if it does not 055 * exist 056 */ 057 public DestinationNode getChild(String path) { 058 return childNodes.get(path); 059 } 060 061 /** 062 * Returns the child nodes 063 */ 064 public Collection<DestinationNode> getChildren() { 065 return childNodes.values(); 066 } 067 068 public int getChildCount() { 069 return childNodes.size(); 070 } 071 072 /** 073 * Returns the child node for the given named path, lazily creating one if 074 * it does not yet exist 075 */ 076 public DestinationMapNode getChildOrCreate(String path) { 077 DestinationMapNode answer = (DestinationMapNode)childNodes.get(path); 078 if (answer == null) { 079 answer = createChildNode(); 080 answer.path = path; 081 childNodes.put(path, answer); 082 } 083 return answer; 084 } 085 086 /** 087 * Returns a mutable List of the values available at this node in the tree 088 */ 089 @SuppressWarnings({ "rawtypes", "unchecked" }) 090 public List getValues() { 091 return values; 092 } 093 094 /** 095 * Removes values available at this node in the tree 096 */ 097 @SuppressWarnings({ "rawtypes", "unchecked" }) 098 public List removeValues() { 099 ArrayList v = new ArrayList(values); 100 // parent.getAnyChildNode().getValues().removeAll(v); 101 values.clear(); 102 pruneIfEmpty(); 103 return v; 104 } 105 106 @SuppressWarnings({ "rawtypes", "unchecked" }) 107 public Set removeDesendentValues() { 108 Set answer = new HashSet(); 109 removeDesendentValues(answer); 110 return answer; 111 } 112 113 @SuppressWarnings({ "rawtypes", "unchecked" }) 114 protected void removeDesendentValues(Set answer) { 115 ArrayList<DestinationNode> candidates = new ArrayList<>(); 116 for (Map.Entry<String, DestinationNode> child : childNodes.entrySet()) { 117 candidates.add(child.getValue()); 118 } 119 120 for (DestinationNode node : candidates) { 121 // remove all the values from the child 122 answer.addAll(node.removeValues()); 123 answer.addAll(node.removeDesendentValues()); 124 } 125 } 126 127 /** 128 * Returns a list of all the values from this node down the tree 129 */ 130 @SuppressWarnings({ "rawtypes", "unchecked" }) 131 public Set getDesendentValues() { 132 Set answer = new HashSet(); 133 appendDescendantValues(answer); 134 return answer; 135 } 136 137 public void add(String[] paths, int idx, Object value) { 138 if (idx >= paths.length) { 139 values.add(value); 140 } else { 141 getChildOrCreate(paths[idx]).add(paths, idx + 1, value); 142 } 143 } 144 145 public void set(String[] paths, int idx, Object value) { 146 if (idx >= paths.length) { 147 values.clear(); 148 values.add(value); 149 } else { 150 getChildOrCreate(paths[idx]).set(paths, idx + 1, value); 151 } 152 } 153 154 public void remove(String[] paths, int idx, Object value) { 155 if (idx >= paths.length) { 156 values.remove(value); 157 pruneIfEmpty(); 158 } else { 159 getChildOrCreate(paths[idx]).remove(paths, ++idx, value); 160 } 161 } 162 163 public void removeAll(Set<DestinationNode> answer, String[] paths, int startIndex) { 164 DestinationNode node = this; 165 int size = paths.length; 166 for (int i = startIndex; i < size && node != null; i++) { 167 168 String path = paths[i]; 169 if (path.equals(ANY_DESCENDENT)) { 170 answer.addAll(node.removeDesendentValues()); 171 break; 172 } 173 174 // TODO is this correct, we are appending wildcard values here??? 175 node.appendMatchingWildcards(answer, paths, i); 176 if (path.equals(ANY_CHILD)) { 177 // node = node.getAnyChildNode(); 178 node = new AnyChildDestinationNode(node); 179 } else { 180 node = node.getChild(path); 181 } 182 } 183 184 if (node != null) { 185 answer.addAll(node.removeValues()); 186 } 187 188 } 189 190 @SuppressWarnings({ "rawtypes", "unchecked" }) 191 public void appendDescendantValues(Set answer) { 192 // add children values, then recursively add their children 193 for(DestinationNode child : childNodes.values()) { 194 answer.addAll(child.getValues()); 195 child.appendDescendantValues(answer); 196 } 197 } 198 199 /** 200 * Factory method to create a child node 201 */ 202 protected DestinationMapNode createChildNode() { 203 return new DestinationMapNode(this); 204 } 205 206 /** 207 * Matches any entries in the map containing wildcards 208 */ 209 @SuppressWarnings({ "rawtypes", "unchecked" }) 210 public void appendMatchingWildcards(Set answer, String[] paths, int idx) { 211 if (idx - 1 > pathLength) { 212 return; 213 } 214 DestinationNode wildCardNode = getChild(ANY_CHILD); 215 if (wildCardNode != null) { 216 wildCardNode.appendMatchingValues(answer, paths, idx + 1); 217 } 218 wildCardNode = getChild(ANY_DESCENDENT); 219 if (wildCardNode != null) { 220 // for a wildcard Node match, add all values of the descendant node 221 answer.addAll(wildCardNode.getValues()); 222 // and all descendants for paths like ">.>" 223 answer.addAll(wildCardNode.getDesendentValues()); 224 } 225 } 226 227 @SuppressWarnings({"rawtypes", "unchecked"}) 228 public void appendMatchingValues(Set answer, String[] paths, int idx) { 229 appendMatchingValues(answer, paths, idx, true); 230 } 231 232 public void appendMatchingValues(Set<DestinationNode> answer, String[] paths, int startIndex, boolean deep) { 233 DestinationNode node = this; 234 boolean couldMatchAny = true; 235 int size = paths.length; 236 for (int i = startIndex; i < size && node != null; i++) { 237 String path = paths[i]; 238 if (deep && path.equals(ANY_DESCENDENT)) { 239 answer.addAll(node.getDesendentValues()); 240 couldMatchAny = false; 241 break; 242 } 243 244 node.appendMatchingWildcards(answer, paths, i); 245 246 if (path.equals(ANY_CHILD)) { 247 node = new AnyChildDestinationNode(node); 248 } else { 249 node = node.getChild(path); 250 } 251 } 252 if (node != null) { 253 answer.addAll(node.getValues()); 254 if (couldMatchAny) { 255 // lets allow FOO.BAR to match the FOO.BAR.> entry in the map 256 DestinationNode child = node.getChild(ANY_DESCENDENT); 257 if (child != null) { 258 answer.addAll(child.getValues()); 259 } 260 } 261 } 262 } 263 264 public String getPath() { 265 return path; 266 } 267 268 public boolean isEmpty(){ 269 return childNodes.isEmpty(); 270 } 271 272 protected void pruneIfEmpty() { 273 if (parent != null && childNodes.isEmpty() && values.isEmpty()) { 274 parent.removeChild(this); 275 } 276 } 277 278 protected void removeChild(DestinationMapNode node) { 279 childNodes.remove(node.getPath()); 280 pruneIfEmpty(); 281 } 282}