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