001 /** 002 * 003 * Copyright 2004 Hiram Chirino 004 * 005 * Licensed under the Apache License, Version 2.0 (the "License"); 006 * you may not use this file except in compliance with the License. 007 * 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 * 017 **/ 018 package org.activemq.filter; 019 020 import javax.jms.JMSException; 021 import javax.jms.Message; 022 import java.util.ArrayList; 023 import java.util.Collection; 024 import java.util.HashMap; 025 import java.util.Iterator; 026 027 /** 028 * A MultiExpressionEvaluator is used to evaluate multiple expressions in 029 * single method call. 030 * <p/> 031 * Multiple Expression/ExpressionListener pairs can be added to a MultiExpressionEvaluator object. When 032 * the MultiExpressionEvaluator object is evaluated, all the registed Expressions are evaluated and then the 033 * associated ExpressionListener is invoked to inform it of the evaluation result. 034 * <p/> 035 * By evaluating multiple expressions at one time, some optimizations can be made 036 * to reduce the number of computations normally required to evaluate all the expressions. 037 * <p/> 038 * When this class adds an Expression it wrapps each node in the Expression's AST with a 039 * CacheExpression object. Then each CacheExpression object (one for each node) is placed 040 * in the cachedExpressions map. The cachedExpressions map allows us to find the sub expressions 041 * that are common across two different expressions. When adding an Expression in, if a sub 042 * Expression of the Expression is allready in the cachedExpressions map, then instead of 043 * wrapping the sub expression in a new CacheExpression object, we reuse the CacheExpression allready 044 * int the map. 045 * <p/> 046 * To help illustrate what going on, lets try to give an exmample: 047 * If we denote the AST of a Expression as follows: [AST-Node-Type,Left-Node,Right-Node], then 048 * A expression like: "3*5+6" would result in "[*,3,[+,5,6]]" 049 * <p/> 050 * If the [*,3,[+,5,6]] expression is added to the MultiExpressionEvaluator, it would really 051 * be converted to: [c0,[*,3,[c1,[+,5,6]]]] where c0 and c1 represent the CacheExpression expression 052 * objects that cache the results of the * and the + operation. Constants and Property nodes are not 053 * cached. 054 * <p/> 055 * If later on we add the following expression [=,11,[+,5,6]] ("11=5+6") to the MultiExpressionEvaluator 056 * it would be converted to: [c2,[=,11,[c1,[+,5,6]]]], where c2 is a new CacheExpression object 057 * but c1 is the same CacheExpression used in the previous expression. 058 * <p/> 059 * When the expressions are evaluated, the c1 CacheExpression object will only evaluate the 060 * [+,5,6] expression once and cache the resulting value. Hence evauating the second expression 061 * costs less because that [+,5,6] is not done 2 times. 062 * <p/> 063 * Problems: 064 * - cacheing the values introduces overhead. It may be possible to be smarter about WHICH 065 * nodes in the AST are cached and which are not. 066 * - Current implementation is not thread safe. This is because you need a way to invalidate 067 * all the cached values so that the next evaluation re-evaluates the nodes. By going single 068 * threaded, chache invalidation is done quickly by incrementing a 'view' counter. 069 * When a CacheExpressionnotices it's last cached value was generated in an old 'view', 070 * it invalidates its cached value. 071 * 072 * @version $Revision: 1.1.1.1 $ $Date: 2005/03/11 21:14:23 $ 073 */ 074 public class MultiExpressionEvaluator { 075 076 HashMap rootExpressions = new HashMap(); 077 HashMap cachedExpressions = new HashMap(); 078 079 int view = 0; 080 081 /** 082 * A UnaryExpression that caches the result of the 083 * nested expression. The cached value is valid 084 * if the CacheExpression.cview==MultiExpressionEvaluator.view 085 */ 086 public class CacheExpression extends UnaryExpression { 087 short refCount = 0; 088 int cview = view - 1; 089 Object cachedValue; 090 int cachedHashCode; 091 092 public CacheExpression(Expression realExpression) { 093 super(realExpression); 094 cachedHashCode = realExpression.hashCode(); 095 } 096 097 /** 098 * @see org.activemq.filter.Expression#evaluate(javax.jms.Message) 099 */ 100 public Object evaluate(Message message) throws JMSException { 101 if (view == cview) { 102 return cachedValue; 103 } 104 cachedValue = right.evaluate(message); 105 cview = view; 106 return cachedValue; 107 } 108 109 public int hashCode() { 110 return cachedHashCode; 111 } 112 113 public boolean equals(Object o) { 114 return ((CacheExpression) o).right.equals(right); 115 } 116 117 public String getExpressionSymbol() { 118 return null; 119 } 120 121 public String toString() { 122 return right.toString(); 123 } 124 125 } 126 127 /** 128 * Multiple listeners my be interested in the results 129 * of a single expression. 130 */ 131 static class ExpressionListenerSet { 132 Expression expression; 133 ArrayList listeners = new ArrayList(); 134 } 135 136 /** 137 * Objects that are interested in the results of an expression 138 * should implement this interface. 139 */ 140 static interface ExpressionListener { 141 public void evaluateResultEvent(Expression selector, Message message, Object result); 142 } 143 144 /** 145 * Adds an ExpressionListener to a given expression. When evaluate is 146 * called, the ExpressionListener will be provided the results of the 147 * Expression applied to the evaluated message. 148 */ 149 public void addExpressionListner(Expression selector, ExpressionListener c) { 150 ExpressionListenerSet data = (ExpressionListenerSet) rootExpressions.get(selector.toString()); 151 if (data == null) { 152 data = new ExpressionListenerSet(); 153 data.expression = addToCache(selector); 154 rootExpressions.put(selector.toString(), data); 155 } 156 data.listeners.add(c); 157 } 158 159 /** 160 * Removes an ExpressionListener from receiving the results of 161 * a given evaluation. 162 */ 163 public boolean removeEventListner(String selector, ExpressionListener c) { 164 String expKey = selector; 165 ExpressionListenerSet d = (ExpressionListenerSet) rootExpressions.get(expKey); 166 if (d == null) // that selector had not been added. 167 { 168 return false; 169 } 170 if (!d.listeners.remove(c)) // that selector did not have that listner.. 171 { 172 return false; 173 } 174 175 // If there are no more listners for this expression.... 176 if (d.listeners.size() == 0) { 177 // Uncache it... 178 removeFromCache((CacheExpression) d.expression); 179 rootExpressions.remove(expKey); 180 } 181 return true; 182 } 183 184 /** 185 * Finds the CacheExpression that has been associated 186 * with an expression. If it is the first time the 187 * Expression is being added to the Cache, a new 188 * CacheExpression is created and associated with 189 * the expression. 190 * <p/> 191 * This method updates the reference counters on the 192 * CacheExpression to know when it is no longer needed. 193 */ 194 private CacheExpression addToCache(Expression expr) { 195 196 CacheExpression n = (CacheExpression) cachedExpressions.get(expr); 197 if (n == null) { 198 n = new CacheExpression(expr); 199 cachedExpressions.put(expr, n); 200 if (expr instanceof UnaryExpression) { 201 202 // Cache the sub expressions too 203 UnaryExpression un = (UnaryExpression) expr; 204 un.setRight(addToCache(un.getRight())); 205 206 } 207 else if (expr instanceof BinaryExpression) { 208 209 // Cache the sub expressions too. 210 BinaryExpression bn = (BinaryExpression) expr; 211 bn.setRight(addToCache(bn.getRight())); 212 bn.setLeft(addToCache(bn.getLeft())); 213 214 } 215 } 216 n.refCount++; 217 return n; 218 } 219 220 /** 221 * Removes an expression from the cache. Updates the 222 * reference counters on the CacheExpression object. When 223 * the refernce counter goes to zero, the entry 224 * int the Expression to CacheExpression map is removed. 225 * 226 * @param cn 227 */ 228 private void removeFromCache(CacheExpression cn) { 229 cn.refCount--; 230 Expression realExpr = cn.getRight(); 231 if (cn.refCount == 0) { 232 cachedExpressions.remove(realExpr); 233 } 234 if (realExpr instanceof UnaryExpression) { 235 UnaryExpression un = (UnaryExpression) realExpr; 236 removeFromCache((CacheExpression) un.getRight()); 237 } 238 if (realExpr instanceof BinaryExpression) { 239 BinaryExpression bn = (BinaryExpression) realExpr; 240 removeFromCache((CacheExpression) bn.getRight()); 241 } 242 } 243 244 /** 245 * Evaluates the message against all the Expressions added to 246 * this object. The added ExpressionListeners are notified 247 * of the result of the evaluation. 248 * 249 * @param message 250 */ 251 public void evaluate(Message message) { 252 Collection expressionListeners = rootExpressions.values(); 253 for (Iterator iter = expressionListeners.iterator(); iter.hasNext();) { 254 ExpressionListenerSet els = (ExpressionListenerSet) iter.next(); 255 try { 256 Object result = els.expression.evaluate(message); 257 for (Iterator iterator = els.listeners.iterator(); iterator.hasNext();) { 258 ExpressionListener l = (ExpressionListener) iterator.next(); 259 l.evaluateResultEvent(els.expression, message, result); 260 } 261 } 262 catch (Throwable e) { 263 e.printStackTrace(); 264 } 265 } 266 } 267 }