HeadersMatcherDFAState.java
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         forMap.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 }