001 package org.apache.qpid.server.exchange.headers;
002
003 import org.apache.qpid.framing.AMQTypedValue;
004 import org.apache.qpid.framing.AMQShortString;
005 import org.apache.qpid.framing.FieldTable;
006 import org.apache.qpid.server.exchange.topic.TopicMatcherDFAState;
007 import org.apache.qpid.server.exchange.topic.TopicWord;
008 import org.apache.qpid.server.exchange.topic.TopicMatcherResult;
009
010 import java.util.*;
011
012 /*
013 *
014 * Licensed to the Apache Software Foundation (ASF) under one
015 * or more contributor license agreements. See the NOTICE file
016 * distributed with this work for additional information
017 * regarding copyright ownership. The ASF licenses this file
018 * to you under the Apache License, Version 2.0 (the
019 * "License"); you may not use this file except in compliance
020 * with the License. You may obtain a copy of the License at
021 *
022 * http://www.apache.org/licenses/LICENSE-2.0
023 *
024 * Unless required by applicable law or agreed to in writing,
025 * software distributed under the License is distributed on an
026 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
027 * KIND, either express or implied. See the License for the
028 * specific language governing permissions and limitations
029 * under the License.
030 *
031 */
032 public class HeadersMatcherDFAState
033 {
034
035
036 private final Collection<HeaderMatcherResult> _results;
037 private final Map<HeaderKey, Map<AMQTypedValue,HeadersMatcherDFAState>> _nextStateMap;
038 private final HeaderKeyDictionary _dictionary;
039
040 public HeadersMatcherDFAState(Map<HeaderKey, Map<AMQTypedValue,HeadersMatcherDFAState>> nextStateMap,
041 Collection<HeaderMatcherResult> results,
042 HeaderKeyDictionary dictionary)
043 {
044 _nextStateMap = nextStateMap;
045 _results = results;
046 _dictionary = dictionary;
047 }
048
049
050 public Collection<HeaderMatcherResult> match(final FieldTable table)
051 {
052 return match(table.iterator());
053 }
054
055
056
057 public Collection<HeaderMatcherResult> match(Iterator<Map.Entry<AMQShortString,AMQTypedValue>> fieldTableIterator)
058 {
059
060 if(_nextStateMap.isEmpty())
061 {
062 return _results;
063 }
064
065 while(fieldTableIterator.hasNext())
066 {
067
068 Map.Entry<AMQShortString, AMQTypedValue> fieldTableEntry = fieldTableIterator.next();
069 HeaderKey key = _dictionary.get(fieldTableEntry.getKey());
070 if(key != HeaderKey.UNKNOWN)
071 {
072 Map<AMQTypedValue, HeadersMatcherDFAState> valueToStateMap = _nextStateMap.get(key);
073
074 if(valueToStateMap != null)
075 {
076 HeadersMatcherDFAState nextState = valueToStateMap.get(fieldTableEntry.getValue());
077
078 if(nextState == null)
079 {
080 nextState = valueToStateMap.get(null);
081 }
082 if(nextState != null && nextState != this)
083 {
084 return nextState.match(fieldTableIterator);
085 }
086 }
087
088 }
089 }
090
091 return _results;
092
093 }
094
095
096 HeadersMatcherDFAState mergeStateMachines(HeadersMatcherDFAState otherStateMachine)
097 {
098
099 assert(otherStateMachine._dictionary == _dictionary);
100
101 Map<Set<HeadersMatcherDFAState>, HeadersMatcherDFAState> newStateMap= new HashMap<Set<HeadersMatcherDFAState>, HeadersMatcherDFAState>();
102
103 Collection<HeaderMatcherResult> results;
104
105 if(_results.isEmpty())
106 {
107 results = otherStateMachine._results;
108 }
109 else if(otherStateMachine._results.isEmpty())
110 {
111 results = _results;
112 }
113 else
114 {
115 results = new HashSet<HeaderMatcherResult>(_results);
116 results.addAll(otherStateMachine._results);
117 }
118
119
120 final Map<HeaderKey, Map<AMQTypedValue, HeadersMatcherDFAState>> newNextStateMap = new HashMap<HeaderKey, Map<AMQTypedValue, HeadersMatcherDFAState>>();
121
122 HeadersMatcherDFAState newState = new HeadersMatcherDFAState(newNextStateMap, results, _dictionary);
123
124
125 Set<HeadersMatcherDFAState> oldStates = new HashSet<HeadersMatcherDFAState>();
126 oldStates.add(this);
127 oldStates.add(otherStateMachine);
128
129 newStateMap.put(oldStates, newState);
130
131 mergeStateMachines(oldStates, newNextStateMap, newStateMap);
132
133 return newState;
134
135
136 }
137
138 private void mergeStateMachines(final Set<HeadersMatcherDFAState> oldStates,
139 final Map<HeaderKey, Map<AMQTypedValue, HeadersMatcherDFAState>> newNextStateMap,
140 final Map<Set<HeadersMatcherDFAState>, HeadersMatcherDFAState> newStateMap)
141 {
142 Map<HeaderKey, Map<AMQTypedValue, Set<HeadersMatcherDFAState>>> nfaMap = new HashMap<HeaderKey, Map<AMQTypedValue, Set<HeadersMatcherDFAState>>>();
143
144 Set<HeaderKey> distinctKeys = new HashSet<HeaderKey>();
145
146 for(HeadersMatcherDFAState state : oldStates)
147 {
148 Map<HeaderKey, Map<AMQTypedValue, HeadersMatcherDFAState>> map = state._nextStateMap;
149
150 for(Map.Entry<HeaderKey, Map<AMQTypedValue, HeadersMatcherDFAState>> entry : map.entrySet())
151 {
152 Map<AMQTypedValue, Set<HeadersMatcherDFAState>> valueToStatesMap = nfaMap.get(entry.getKey());
153
154 if(valueToStatesMap == null)
155 {
156 valueToStatesMap = new HashMap<AMQTypedValue, Set<HeadersMatcherDFAState>>();
157 nfaMap.put(entry.getKey(), valueToStatesMap);
158 }
159
160 for(Map.Entry<AMQTypedValue, HeadersMatcherDFAState> valueToStateEntry : entry.getValue().entrySet())
161 {
162 Set<HeadersMatcherDFAState> states = valueToStatesMap.get(valueToStateEntry.getKey());
163 if(states == null)
164 {
165 states = new HashSet<HeadersMatcherDFAState>();
166 valueToStatesMap.put(valueToStateEntry.getKey(),states);
167 }
168 states.add(valueToStateEntry.getValue());
169 }
170
171 distinctKeys.add(entry.getKey());
172 }
173 }
174
175 Map<HeaderKey, Set<HeadersMatcherDFAState>> anyValueStates = new HashMap<HeaderKey, Set<HeadersMatcherDFAState>>();
176
177 for(HeaderKey distinctKey : distinctKeys)
178 {
179 Map<AMQTypedValue, Set<HeadersMatcherDFAState>> valueToStateMap = nfaMap.get(distinctKey);
180 if(valueToStateMap != null)
181 {
182 Set<HeadersMatcherDFAState> statesForKeyDefault = valueToStateMap.get(null);
183 if(statesForKeyDefault != null)
184 {
185 anyValueStates.put(distinctKey, statesForKeyDefault);
186 }
187 }
188 }
189
190 // add the defaults for "null" to all other specified values of a given header key
191
192 for( Map.Entry<HeaderKey,Map<AMQTypedValue,Set<HeadersMatcherDFAState>>> entry : nfaMap.entrySet())
193 {
194 Map<AMQTypedValue, Set<HeadersMatcherDFAState>> valueToStatesMap = entry.getValue();
195 for(Map.Entry<AMQTypedValue, Set<HeadersMatcherDFAState>> valueToStates : valueToStatesMap.entrySet())
196 {
197 if(valueToStates.getKey() != null)
198 {
199
200
201 Set<HeadersMatcherDFAState> defaults = anyValueStates.get(entry.getKey());
202 if(defaults != null)
203 {
204 valueToStates.getValue().addAll(defaults);
205 }
206 }
207 }
208 }
209
210 // if a given header key is not mentioned in the map of a machine; then that machine would stay at the same state
211 // for that key.
212 for(HeaderKey distinctKey : distinctKeys)
213 {
214 Map<AMQTypedValue, Set<HeadersMatcherDFAState>> valueToStatesMap = nfaMap.get(distinctKey);
215 for(HeadersMatcherDFAState oldState : oldStates)
216 {
217 if(!oldState._nextStateMap.containsKey(distinctKey))
218 {
219 for(Set<HeadersMatcherDFAState> endStates : valueToStatesMap.values())
220 {
221 endStates.add(oldState);
222 }
223 }
224 }
225 }
226
227
228
229
230 for(Map.Entry<HeaderKey,Map<AMQTypedValue,Set<HeadersMatcherDFAState>>> transitionClass : nfaMap.entrySet())
231 {
232 Map<AMQTypedValue, HeadersMatcherDFAState> valueToDFAState = newNextStateMap.get(transitionClass.getKey());
233 if(valueToDFAState == null)
234 {
235 valueToDFAState = new HashMap<AMQTypedValue, HeadersMatcherDFAState>();
236 newNextStateMap.put(transitionClass.getKey(), valueToDFAState);
237 }
238
239 for(Map.Entry<AMQTypedValue,Set<HeadersMatcherDFAState>> transition : transitionClass.getValue().entrySet())
240 {
241 Set<HeadersMatcherDFAState> destinations = transition.getValue();
242
243
244 HeadersMatcherDFAState nextState = newStateMap.get(destinations);
245
246 if(nextState == null)
247 {
248
249 if(destinations.size() == 1)
250 {
251 nextState = destinations.iterator().next();
252 newStateMap.put(destinations, nextState);
253 }
254 else
255 {
256 Collection<HeaderMatcherResult> results;
257
258 Set<Collection<HeaderMatcherResult>> resultSets = new HashSet<Collection<HeaderMatcherResult>>();
259 for(HeadersMatcherDFAState destination : destinations)
260 {
261 resultSets.add(destination._results);
262 }
263 resultSets.remove(Collections.EMPTY_SET);
264 if(resultSets.size() == 0)
265 {
266 results = Collections.EMPTY_SET;
267 }
268 else if(resultSets.size() == 1)
269 {
270 results = resultSets.iterator().next();
271 }
272 else
273 {
274 results = new HashSet<HeaderMatcherResult>();
275 for(Collection<HeaderMatcherResult> oldResult : resultSets)
276 {
277 results.addAll(oldResult);
278 }
279 }
280
281 final Map<HeaderKey, Map<AMQTypedValue, HeadersMatcherDFAState>> nextStateMap = new HashMap<HeaderKey, Map<AMQTypedValue, HeadersMatcherDFAState>>();
282
283 nextState = new HeadersMatcherDFAState(nextStateMap, results, _dictionary);
284 newStateMap.put(destinations, nextState);
285
286 mergeStateMachines(
287 destinations,
288 nextStateMap,
289 newStateMap);
290
291
292 }
293
294
295 }
296 valueToDFAState.put(transition.getKey(),nextState);
297 }
298 }
299
300
301
302 final ArrayList<HeaderKey> removeKeyList = new ArrayList<HeaderKey>();
303
304 for(Map.Entry<HeaderKey,Map<AMQTypedValue,HeadersMatcherDFAState>> entry : _nextStateMap.entrySet())
305 {
306 final ArrayList<AMQTypedValue> removeValueList = new ArrayList<AMQTypedValue>();
307
308 for(Map.Entry<AMQTypedValue,HeadersMatcherDFAState> valueToDFAState : entry.getValue().entrySet())
309 {
310 if(valueToDFAState.getValue() == this)
311 {
312 HeadersMatcherDFAState defaultState = entry.getValue().get(null);
313 if(defaultState == null || defaultState == this)
314 {
315 removeValueList.add(valueToDFAState.getKey());
316 }
317 }
318 }
319
320 for(AMQTypedValue removeValue : removeValueList)
321 {
322 entry.getValue().remove(removeValue);
323 }
324
325 if(entry.getValue().isEmpty())
326 {
327 removeKeyList.add(entry.getKey());
328 }
329
330 }
331
332 for(HeaderKey removeKey : removeKeyList)
333 {
334 _nextStateMap.remove(removeKey);
335 }
336
337 }
338
339 }
|