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.Comparator;
020import java.util.HashSet;
021import java.util.Iterator;
022import java.util.List;
023import java.util.Set;
024import java.util.SortedSet;
025import java.util.TreeSet;
026import java.util.stream.Collectors;
027
028import org.apache.activemq.command.ActiveMQDestination;
029
030/**
031 * A Map-like data structure allowing values to be indexed by
032 * {@link ActiveMQDestination} and retrieved by destination - supporting both *
033 * and &gt; style of wildcard as well as composite destinations. <br>
034 * This class assumes that the index changes rarely but that fast lookup into
035 * the index is required. So this class maintains a pre-calculated index for
036 * destination steps. So looking up the values for "TEST.*" or "*.TEST" will be
037 * pretty fast. <br>
038 * Looking up of a value could return a single value or a List of matching
039 * values if a wildcard or composite destination is used.
040 */
041public class DestinationMap {
042    protected static final String ANY_DESCENDENT = DestinationFilter.ANY_DESCENDENT;
043    protected static final String ANY_CHILD = DestinationFilter.ANY_CHILD;
044
045    private DestinationMapNode queueRootNode = new DestinationMapNode(null);
046    private DestinationMapNode tempQueueRootNode = new DestinationMapNode(null);
047    private DestinationMapNode topicRootNode = new DestinationMapNode(null);
048    private DestinationMapNode tempTopicRootNode = new DestinationMapNode(null);
049
050
051    /**
052     * Looks up the value(s) matching the given Destination key. For simple
053     * destinations this is typically a List of one single value, for wildcards
054     * or composite destinations this will typically be a List of matching
055     * values.
056     *
057     * @param key the destination to lookup
058     * @return a List of matching values or an empty list if there are no
059     *         matching values.
060     */
061    @SuppressWarnings({"rawtypes", "unchecked"})
062    public Set get(ActiveMQDestination key) {
063        synchronized (this) {
064            return unsynchronizedGet(key);
065        }
066    }
067
068    @SuppressWarnings({"rawtypes", "unchecked"})
069    public Set unsynchronizedGet(ActiveMQDestination key) {
070        if (key.isComposite()) {
071            ActiveMQDestination[] destinations = key.getCompositeDestinations();
072            Set answer = new HashSet(destinations.length);
073            for (int i = 0; i < destinations.length; i++) {
074                ActiveMQDestination childDestination = destinations[i];
075                Object value = unsynchronizedGet(childDestination);
076                if (value instanceof Set) {
077                    answer.addAll((Set) value);
078                } else if (value != null) {
079                    answer.add(value);
080                }
081            }
082            return answer;
083        }
084        return findWildcardMatches(key);
085    }
086
087    public void put(ActiveMQDestination key, Object value) {
088        synchronized (this) {
089            unsynchronizedPut(key, value);
090        }
091    }
092
093    public void unsynchronizedPut(ActiveMQDestination key, Object value) {
094        if (key.isComposite()) {
095            ActiveMQDestination[] destinations = key.getCompositeDestinations();
096            for (int i = 0; i < destinations.length; i++) {
097                ActiveMQDestination childDestination = destinations[i];
098                put(childDestination, value);
099            }
100            return;
101        }
102        String[] paths = key.getDestinationPaths();
103        getRootNode(key).add(paths, 0, value);
104    }
105
106
107    /**
108     * Removes the value from the associated destination
109     */
110    public void remove(ActiveMQDestination key, Object value) {
111        synchronized (this) {
112            unsynchronizedRemove(key, value);
113        }
114    }
115
116    public void unsynchronizedRemove(ActiveMQDestination key, Object value) {
117        if (key.isComposite()) {
118            ActiveMQDestination[] destinations = key.getCompositeDestinations();
119            for (int i = 0; i < destinations.length; i++) {
120                ActiveMQDestination childDestination = destinations[i];
121                remove(childDestination, value);
122            }
123            return;
124        }
125        String[] paths = key.getDestinationPaths();
126        getRootNode(key).remove(paths, 0, value);
127
128    }
129
130    public int getTopicRootChildCount() {
131        return topicRootNode.getChildCount();
132    }
133
134    public int getQueueRootChildCount() {
135        return queueRootNode.getChildCount();
136    }
137
138    public DestinationMapNode getQueueRootNode() {
139        return queueRootNode;
140    }
141
142    public DestinationMapNode getTopicRootNode() {
143        return topicRootNode;
144    }
145
146    public DestinationMapNode getTempQueueRootNode() {
147        return tempQueueRootNode;
148    }
149
150    public DestinationMapNode getTempTopicRootNode() {
151        return tempTopicRootNode;
152    }
153
154    // Implementation methods
155    // -------------------------------------------------------------------------
156
157    /**
158     * A helper method to allow the destination map to be populated from a
159     * dependency injection framework such as Spring
160     */
161    @SuppressWarnings({"rawtypes"})
162    protected void setEntries(List<DestinationMapEntry> entries) {
163        for (Object element : entries) {
164            Class<? extends DestinationMapEntry> type = getEntryClass();
165            if (type.isInstance(element)) {
166                DestinationMapEntry entry = (DestinationMapEntry) element;
167                put(entry.getDestination(), entry.getValue());
168            } else {
169                throw new IllegalArgumentException("Each entry must be an instance of type: " + type.getName() + " but was: " + element);
170            }
171        }
172    }
173
174    /**
175     * Returns the type of the allowed entries which can be set via the
176     * {@link #setEntries(List)} method. This allows derived classes to further
177     * restrict the type of allowed entries to make a type safe destination map
178     * for custom policies.
179     */
180    @SuppressWarnings({"rawtypes"})
181    protected Class<? extends DestinationMapEntry> getEntryClass() {
182        return DestinationMapEntry.class;
183    }
184
185    @SuppressWarnings({"rawtypes", "unchecked"})
186    protected Set findWildcardMatches(ActiveMQDestination key) {
187       return findWildcardMatches(key, true);
188    }
189
190    @SuppressWarnings({"rawtypes", "unchecked"})
191    protected Set findWildcardMatches(ActiveMQDestination key, boolean deep) {
192        String[] paths = key.getDestinationPaths();
193        Set answer = new HashSet();
194        getRootNode(key).appendMatchingValues(answer, paths, 0, deep);
195        return answer;
196    }
197
198    /**
199     * @param key
200     * @return
201     */
202    @SuppressWarnings({"rawtypes", "unchecked"})
203    public Set removeAll(ActiveMQDestination key) {
204        Set rc = new HashSet();
205        if (key.isComposite()) {
206            ActiveMQDestination[] destinations = key.getCompositeDestinations();
207            for (int i = 0; i < destinations.length; i++) {
208                rc.add(removeAll(destinations[i]));
209            }
210            return rc;
211        }
212        String[] paths = key.getDestinationPaths();
213        getRootNode(key).removeAll(rc, paths, 0);
214        return rc;
215    }
216
217    /**
218     * Returns the value which matches the given destination or null if there is
219     * no matching value. If there are multiple values, the results are sorted
220     * and the last item (the biggest) is returned.
221     *
222     * @param destination the destination to find the value for
223     * @return the largest matching value or null if no value matches
224     */
225    @SuppressWarnings({"rawtypes", "unchecked"})
226    public DestinationMapEntry chooseValue(final ActiveMQDestination destination) {
227        Set<DestinationMapEntry> set = get(destination);
228        if (set == null || set.isEmpty()) {
229            return null;
230        }
231
232        //Comparator to sort in order - we want to pick the exact match by destination or the
233        //closest parent that applies
234        final Comparator<DestinationMapEntry> comparator = new Comparator<DestinationMapEntry>() {
235            @Override
236            public int compare(DestinationMapEntry entry1, DestinationMapEntry entry2) {
237                return destination.equals(entry1.destination) ? -1 : (destination.equals(entry2.destination) ? 1 : entry1.compareTo(entry2));
238            }
239        };
240
241        //Sort and filter out any children and non matching entries
242        final SortedSet<DestinationMapEntry> sortedSet = set.stream()
243            .filter(entry -> isMatchOrParent(destination, (DestinationMapEntry)entry))
244            .collect(Collectors.toCollection(() -> new TreeSet<DestinationMapEntry>(comparator)));
245
246        return sortedSet.size() > 0 ? sortedSet.first() : null;
247    }
248
249    @SuppressWarnings("rawtypes")
250    //Used to filter out any child/unmatching entries
251    private boolean isMatchOrParent(final ActiveMQDestination destination, final DestinationMapEntry entry) {
252        //If destination not set then do not filter out
253        if (entry.getDestination() == null) {
254            return true;
255        }
256        final DestinationFilter filter = DestinationFilter.parseFilter(entry.getDestination());
257        return destination.equals(entry.getDestination()) || filter.matches(destination);
258    }
259
260    /**
261     * Returns the root node for the given destination type
262     */
263    protected DestinationMapNode getRootNode(ActiveMQDestination key) {
264        if (key.isTemporary()) {
265            if (key.isQueue()) {
266                return tempQueueRootNode;
267            } else {
268                return tempTopicRootNode;
269            }
270        } else {
271            if (key.isQueue()) {
272                return queueRootNode;
273            } else {
274                return topicRootNode;
275            }
276        }
277    }
278
279    public void reset() {
280        queueRootNode = new DestinationMapNode(null);
281        tempQueueRootNode = new DestinationMapNode(null);
282        topicRootNode = new DestinationMapNode(null);
283        tempTopicRootNode = new DestinationMapNode(null);
284    }
285
286    public boolean isEmpty() {
287        return queueRootNode.isEmpty() && topicRootNode.isEmpty() && tempQueueRootNode.isEmpty() && tempTopicRootNode.isEmpty();
288    }
289
290    public static Set union(Set existing, Set candidates) {
291        if (candidates != null) {
292            if (existing != null) {
293                for (Iterator<Object> iterator = existing.iterator(); iterator.hasNext(); ) {
294                    Object toMatch = iterator.next();
295                    if (!candidates.contains(toMatch)) {
296                        iterator.remove();
297                    }
298                }
299            } else {
300                existing = candidates;
301            }
302        } else if (existing != null) {
303            existing.clear();
304        }
305        return existing;
306    }
307
308}