Changeset 8297 in josm


Ignore:
Timestamp:
2015-04-30T23:38:08+02:00 (6 years ago)
Author:
Don-vip
Message:

fix #11382 - Improve MapCSS speed by using BitSets (patch by michael2402)

Location:
trunk/src/org/openstreetmap/josm/gui/mappaint
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/gui/mappaint/StyleSource.java

    r8126 r8297  
    5757    public Map<String, Object> settingValues = new HashMap<>();
    5858
     59    /**
     60     * Constructs a new, active {@link StyleSource}.
     61     * @param url URL that {@link org.openstreetmap.josm.io.CachedFile} understands
     62     * @param name The name for this StyleSource
     63     * @param title The title that can be used as menu entry
     64     */
    5965    public StyleSource(String url, String name, String title) {
    6066        super(url, name, title, true);
    6167    }
    6268
     69    /**
     70     * Constructs a new {@link StyleSource}
     71     * @param entry The entry to copy the data (url, name, ...) from.
     72     */
    6373    public StyleSource(SourceEntry entry) {
    6474        super(entry);
  • trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/Condition.java

    r8266 r8297  
    8484        REGEX, NREGEX, ONE_OF, BEGINS_WITH, ENDS_WITH, CONTAINS;
    8585
    86         private static final Set<Op> NEGATED_OPS = EnumSet.of(NEQ, NREGEX);
     86        public static final Set<Op> NEGATED_OPS = EnumSet.of(NEQ, NREGEX);
    8787
    8888        public boolean eval(String testString, String prototypeString) {
  • trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSStyleSource.java

    r8291 r8297  
    1313import java.text.MessageFormat;
    1414import java.util.ArrayList;
     15import java.util.BitSet;
    1516import java.util.Collections;
    1617import java.util.HashMap;
    1718import java.util.HashSet;
     19import java.util.Iterator;
    1820import java.util.List;
    1921import java.util.Map;
    2022import java.util.Map.Entry;
    21 import java.util.PriorityQueue;
    2223import java.util.Set;
    2324import java.util.concurrent.locks.ReadWriteLock;
     
    4142import org.openstreetmap.josm.gui.mappaint.StyleSetting.BooleanStyleSetting;
    4243import org.openstreetmap.josm.gui.mappaint.StyleSource;
     44import org.openstreetmap.josm.gui.mappaint.mapcss.Condition.KeyCondition;
     45import org.openstreetmap.josm.gui.mappaint.mapcss.Condition.KeyMatchType;
     46import org.openstreetmap.josm.gui.mappaint.mapcss.Condition.KeyValueCondition;
     47import org.openstreetmap.josm.gui.mappaint.mapcss.Condition.Op;
    4348import org.openstreetmap.josm.gui.mappaint.mapcss.Condition.SimpleKeyValueCondition;
    4449import org.openstreetmap.josm.gui.mappaint.mapcss.Selector.ChildOrParentSelector;
     
    5459import org.openstreetmap.josm.tools.Utils;
    5560
     61/**
     62 * This is a mappaint style that is based on MapCSS rules.
     63 */
    5664public class MapCSSStyleSource extends StyleSource {
    5765
     
    122130     * Speeds up the process of finding all rules that match a certain primitive.
    123131     *
    124      * Rules with a {@link SimpleKeyValueCondition} [key=value] are indexed by
    125      * key and value in a HashMap. Now you only need to loop the tags of a
    126      * primitive to retrieve the possibly matching rules.
     132     * Rules with a {@link SimpleKeyValueCondition} [key=value] or rules that require a specific key to be set are
     133     * indexed. Now you only need to loop the tags of a primitive to retrieve the possibly matching rules.
    127134     *
    128      * Rules with no SimpleKeyValueCondition in the selector have to be
    129      * checked separately.
    130      *
    131      * The order of rules gets mixed up by this and needs to be sorted later.
     135     * To use this index, you need to {@link #add(MapCSSRule)} all rules to it. You then need to call
     136     * {@link #initIndex()}. Afterwards, you can use {@link #getRuleCandidates(OsmPrimitive)} to get an iterator over
     137     * all rules that might be applied to that primitive.
    132138     */
    133139    public static class MapCSSRuleIndex {
    134         /* all rules for this index */
    135         public final List<MapCSSRule> rules = new ArrayList<>();
    136         /* tag based index */
    137         public final Map<String,Map<String,Set<MapCSSRule>>> index = new HashMap<>();
    138         /* rules without SimpleKeyValueCondition */
    139         public final ArrayList<MapCSSRule> remaining = new ArrayList<>();
    140 
     140        /**
     141         * This is an iterator over all rules that are marked as possible in the bitset.
     142         *
     143         * @author Michael Zangl
     144         */
     145        private final class RuleCandidatesIterator implements Iterator<MapCSSRule> {
     146            private final BitSet ruleCandidates;
     147            private int next;
     148
     149            private RuleCandidatesIterator(BitSet ruleCandidates) {
     150                this.ruleCandidates = ruleCandidates;
     151                next = ruleCandidates.nextSetBit(0);
     152            }
     153
     154            @Override
     155            public boolean hasNext() {
     156                return next >= 0;
     157            }
     158
     159            @Override
     160            public MapCSSRule next() {
     161                MapCSSRule rule = rules.get(next);
     162                next = ruleCandidates.nextSetBit(next + 1);
     163                return rule;
     164            }
     165
     166            @Override
     167            public void remove() {
     168                throw new UnsupportedOperationException();
     169            }
     170        }
     171
     172        /**
     173         * This is a map of all rules that are only applied if the primitive has a given key (and possibly value)
     174         *
     175         * @author Michael Zangl
     176         */
     177        private final static class MapCSSKeyRules {
     178            /**
     179             * The indexes of rules that might be applied if this tag is present and the value has no special handling.
     180             */
     181            BitSet generalRules = new BitSet();
     182
     183            /**
     184             * A map that sores the indexes of rules that might be applied if the key=value pair is present on this
     185             * primitive. This includes all key=* rules.
     186             */
     187            HashMap<String, BitSet> specialRules = new HashMap<>();
     188
     189            public void addForKey(int ruleIndex) {
     190                generalRules.set(ruleIndex);
     191                for (BitSet r : specialRules.values()) {
     192                    r.set(ruleIndex);
     193                }
     194            }
     195
     196            public void addForKeyAndValue(String value, int ruleIndex) {
     197                BitSet forValue = specialRules.get(value);
     198                if (forValue == null) {
     199                    forValue = new BitSet();
     200                    forValue.or(generalRules);
     201                    specialRules.put(value.intern(), forValue);
     202                }
     203                forValue.set(ruleIndex);
     204            }
     205
     206            public BitSet get(String value) {
     207                BitSet forValue = specialRules.get(value);
     208                if (forValue != null) return forValue; else return generalRules;
     209            }
     210        }
     211
     212        /**
     213         * All rules this index is for. Once this index is built, this list is sorted.
     214         */
     215        private final List<MapCSSRule> rules = new ArrayList<>();
     216        /**
     217         * All rules that only apply when the given key is present.
     218         */
     219        private final Map<String, MapCSSKeyRules> index = new HashMap<>();
     220        /**
     221         * Rules that do not require any key to be present. Only the index in the {@link #rules} array is stored.
     222         */
     223        private final BitSet remaining = new BitSet();
     224
     225        /**
     226         * Add a rule to this index. This needs to be called before {@link #initIndex()} is called.
     227         * @param rule The rule to add.
     228         */
    141229        public void add(MapCSSRule rule) {
    142230            rules.add(rule);
     
    145233        /**
    146234         * Initialize the index.
    147          *
     235         * <p>
    148236         * You must own the write lock of STYLE_SOURCE_LOCK when calling this method.
    149237         */
    150238        public void initIndex() {
    151             for (MapCSSRule r: rules) {
     239            Collections.sort(rules);
     240            for (int ruleIndex = 0; ruleIndex < rules.size(); ruleIndex++) {
     241                MapCSSRule r = rules.get(ruleIndex);
    152242                // find the rightmost selector, this must be a GeneralSelector
    153243                Selector selRightmost = r.selector;
     
    157247                OptimizedGeneralSelector s = (OptimizedGeneralSelector) selRightmost;
    158248                if (s.conds == null) {
    159                     remaining.add(r);
     249                    remaining.set(ruleIndex);
    160250                    continue;
    161251                }
    162                 List<SimpleKeyValueCondition> sk = new ArrayList<>(Utils.filteredCollection(s.conds, SimpleKeyValueCondition.class));
    163                 if (sk.isEmpty()) {
    164                     remaining.add(r);
    165                     continue;
    166                 }
    167                 SimpleKeyValueCondition c = sk.get(sk.size() - 1);
    168                 Map<String,Set<MapCSSRule>> rulesWithMatchingKey = index.get(c.k);
    169                 if (rulesWithMatchingKey == null) {
    170                     rulesWithMatchingKey = new HashMap<>();
    171                     index.put(c.k, rulesWithMatchingKey);
    172                 }
    173                 Set<MapCSSRule> rulesWithMatchingKeyValue = rulesWithMatchingKey.get(c.v);
    174                 if (rulesWithMatchingKeyValue == null) {
    175                     rulesWithMatchingKeyValue = new HashSet<>();
    176                     rulesWithMatchingKey.put(c.v, rulesWithMatchingKeyValue);
    177                 }
    178                 rulesWithMatchingKeyValue.add(r);
    179             }
    180             Collections.sort(remaining);
    181         }
    182 
    183         /**
    184          * Get a subset of all rules that might match the primitive.
     252                List<SimpleKeyValueCondition> sk = new ArrayList<>(Utils.filteredCollection(s.conds,
     253                        SimpleKeyValueCondition.class));
     254                if (!sk.isEmpty()) {
     255                    SimpleKeyValueCondition c = sk.get(sk.size() - 1);
     256                    getEntryInIndex(c.k).addForKeyAndValue(c.v, ruleIndex);
     257                } else {
     258                    String key = findAnyRequiredKey(s.conds);
     259                    if (key != null) {
     260                        getEntryInIndex(key).addForKey(ruleIndex);
     261                    } else {
     262                        remaining.set(ruleIndex);
     263                    }
     264                }
     265            }
     266        }
     267
     268        /**
     269         * Search for any key that condition might depend on.
     270         *
     271         * @param conds The conditions to search through.
     272         * @return An arbitrary key this rule depends on or <code>null</code> if there is no such key.
     273         */
     274        private String findAnyRequiredKey(List<Condition> conds) {
     275            String key = null;
     276            for (Condition c : conds) {
     277                if (c instanceof KeyCondition) {
     278                    KeyCondition keyCondition = (KeyCondition) c;
     279                    if (!keyCondition.negateResult && conditionRequiresKeyPresence(keyCondition.matchType)) {
     280                        key = keyCondition.label;
     281                    }
     282                } else if (c instanceof KeyValueCondition) {
     283                    KeyValueCondition keyValueCondition = (KeyValueCondition) c;
     284                    if (!Op.NEGATED_OPS.contains(keyValueCondition)) {
     285                        key = keyValueCondition.k;
     286                    }
     287                }
     288            }
     289            return key;
     290        }
     291
     292        private boolean conditionRequiresKeyPresence(KeyMatchType matchType) {
     293            return matchType != KeyMatchType.REGEX;
     294        }
     295
     296        private MapCSSKeyRules getEntryInIndex(String key) {
     297            MapCSSKeyRules rulesWithMatchingKey = index.get(key);
     298            if (rulesWithMatchingKey == null) {
     299                rulesWithMatchingKey = new MapCSSKeyRules();
     300                index.put(key.intern(), rulesWithMatchingKey);
     301            }
     302            return rulesWithMatchingKey;
     303        }
     304
     305        /**
     306         * Get a subset of all rules that might match the primitive. Rules not included in the result are guaranteed to
     307         * not match this primitive.
     308         * <p>
     309         * You must have a read lock of STYLE_SOURCE_LOCK when calling this method.
     310         *
    185311         * @param osm the primitive to match
    186          * @return a Collection of rules that filters out most of the rules
    187          * that cannot match, based on the tags of the primitive
    188          *
    189          * You must have a read lock of STYLE_SOURCE_LOCK when calling this method.
    190          */
    191         public PriorityQueue<MapCSSRule> getRuleCandidates(OsmPrimitive osm) {
    192             PriorityQueue<MapCSSRule> ruleCandidates = new PriorityQueue<>(remaining);
    193             for (Map.Entry<String,String> e : osm.getKeys().entrySet()) {
    194                 Map<String,Set<MapCSSRule>> v = index.get(e.getKey());
     312         * @return An iterator over possible rules in the right order.
     313         */
     314        public Iterator<MapCSSRule> getRuleCandidates(OsmPrimitive osm) {
     315            final BitSet ruleCandidates = new BitSet(rules.size());
     316            ruleCandidates.or(remaining);
     317
     318            for (Map.Entry<String, String> e : osm.getKeys().entrySet()) {
     319                MapCSSKeyRules v = index.get(e.getKey());
    195320                if (v != null) {
    196                     Set<MapCSSRule> rs = v.get(e.getValue());
    197                     if (rs != null)  {
    198                         ruleCandidates.addAll(rs);
    199                     }
    200                 }
    201             }
    202             return ruleCandidates;
     321                    BitSet rs = v.get(e.getValue());
     322                    ruleCandidates.or(rs);
     323                }
     324            }
     325            return new RuleCandidatesIterator(ruleCandidates);
    203326        }
    204327
    205328        /**
    206329         * Clear the index.
    207          *
     330         * <p>
    208331         * You must own the write lock STYLE_SOURCE_LOCK when calling this method.
    209332         */
     
    215338    }
    216339
     340    /**
     341     * Constructs a new, active {@link MapCSSStyleSource}.
     342     * @param url URL that {@link org.openstreetmap.josm.io.CachedFile} understands
     343     * @param name The name for this StyleSource
     344     * @param shortdescription The title for that source.
     345     */
    217346    public MapCSSStyleSource(String url, String name, String shortdescription) {
    218347        super(url, name, shortdescription);
    219348    }
    220349
     350    /**
     351     * Constructs a new {@link MapCSSStyleSource}
     352     * @param entry The entry to copy the data (url, name, ...) from.
     353     */
    221354    public MapCSSStyleSource(SourceEntry entry) {
    222355        super(entry);
     
    489622        int lastDeclUsed = -1;
    490623
    491         PriorityQueue<MapCSSRule> candidates = matchingRuleIndex.getRuleCandidates(osm);
    492         MapCSSRule r;
    493         while ((r = candidates.poll()) != null) {
     624        Iterator<MapCSSRule> candidates = matchingRuleIndex.getRuleCandidates(osm);
     625        while (candidates.hasNext()) {
     626            MapCSSRule r = candidates.next();
    494627            env.clearSelectorMatchingInformation();
    495628            env.layer = null;
     
    504637                }
    505638
    506                 if (r.declaration.idx == lastDeclUsed) continue; // don't apply one declaration more than once
     639                if (r.declaration.idx == lastDeclUsed)
     640                    continue; // don't apply one declaration more than once
    507641                lastDeclUsed = r.declaration.idx;
    508642                if ("*".equals(sub)) {
Note: See TracChangeset for help on using the changeset viewer.