Repository: calcite Updated Branches: refs/heads/master b1789ba18 -> 0a330e79f
[CALCITE-2491] Refactor NameSet, NameMap, and NameMultimap Collections are thread-safe when used in read-only scenarios. Name*.immutableCopyOf are always thread-safe as writes are prohibited :) fixes #815 Project: http://git-wip-us.apache.org/repos/asf/calcite/repo Commit: http://git-wip-us.apache.org/repos/asf/calcite/commit/0a330e79 Tree: http://git-wip-us.apache.org/repos/asf/calcite/tree/0a330e79 Diff: http://git-wip-us.apache.org/repos/asf/calcite/diff/0a330e79 Branch: refs/heads/master Commit: 0a330e79ff1c120cf7e53af1787be913d83f73ca Parents: b1789ba Author: Vladimir Sitnikov <[email protected]> Authored: Fri Aug 31 21:40:28 2018 +0300 Committer: Vladimir Sitnikov <[email protected]> Committed: Sat Sep 1 04:47:14 2018 +0300 ---------------------------------------------------------------------- .../org/apache/calcite/jdbc/CalciteSchema.java | 19 +- .../calcite/util/CaseInsensitiveComparator.java | 78 ++++++++ .../org/apache/calcite/util/NameHelper.java | 197 ------------------- .../java/org/apache/calcite/util/NameMap.java | 18 +- .../org/apache/calcite/util/NameMultimap.java | 44 ++--- .../java/org/apache/calcite/util/NameSet.java | 65 ++---- .../java/org/apache/calcite/util/UtilTest.java | 2 + 7 files changed, 130 insertions(+), 293 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/calcite/blob/0a330e79/core/src/main/java/org/apache/calcite/jdbc/CalciteSchema.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/jdbc/CalciteSchema.java b/core/src/main/java/org/apache/calcite/jdbc/CalciteSchema.java index 2cba4be..6698810 100644 --- a/core/src/main/java/org/apache/calcite/jdbc/CalciteSchema.java +++ b/core/src/main/java/org/apache/calcite/jdbc/CalciteSchema.java @@ -43,7 +43,6 @@ import com.google.common.collect.Lists; import java.util.ArrayList; import java.util.Collection; import java.util.List; -import java.util.Locale; import java.util.Map; import java.util.NavigableMap; import java.util.NavigableSet; @@ -452,20 +451,22 @@ public abstract class CalciteSchema { } /** Returns a subset of a map whose keys match the given string - * case-insensitively. */ + * case-insensitively. + * @deprecated use NameMap + */ + @Deprecated // to be removed before 2.0 protected static <V> NavigableMap<String, V> find(NavigableMap<String, V> map, String s) { - assert map.comparator() == NameSet.COMPARATOR; - return map.subMap(s.toUpperCase(Locale.ROOT), true, - s.toLowerCase(Locale.ROOT), true); + return NameMap.immutableCopyOf(map).range(s, false); } /** Returns a subset of a set whose values match the given string - * case-insensitively. */ + * case-insensitively. + * @deprecated use NameSet + */ + @Deprecated // to be removed before 2.0 protected static Iterable<String> find(NavigableSet<String> set, String name) { - assert set.comparator() == NameSet.COMPARATOR; - return set.subSet(name.toUpperCase(Locale.ROOT), true, - name.toLowerCase(Locale.ROOT), true); + return NameSet.immutableCopyOf(set).range(name, false); } /** Creates a root schema. http://git-wip-us.apache.org/repos/asf/calcite/blob/0a330e79/core/src/main/java/org/apache/calcite/util/CaseInsensitiveComparator.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/util/CaseInsensitiveComparator.java b/core/src/main/java/org/apache/calcite/util/CaseInsensitiveComparator.java new file mode 100644 index 0000000..ad28da1 --- /dev/null +++ b/core/src/main/java/org/apache/calcite/util/CaseInsensitiveComparator.java @@ -0,0 +1,78 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.calcite.util; + +import java.util.Comparator; + +/** + * Comparator that compares all strings differently, but if two strings are + * equal in case-insensitive match they are right next to each other. + * + * <p>Note: strings that differ only in upper-lower case are treated by this comparator + * as distinct. + * + * <p>In a collection sorted on this comparator, we can find case-insensitive matches + * for a given string using + * {@link org.apache.calcite.util.CaseInsensitiveComparator#floorKey(java.lang.String)} + * and {@link org.apache.calcite.util.CaseInsensitiveComparator#ceilingKey(java.lang.String)}. + */ +class CaseInsensitiveComparator implements Comparator { + static final CaseInsensitiveComparator COMPARATOR = new CaseInsensitiveComparator(); + + /** + * Enables to create floor and ceiling keys for given string. + */ + private static final class Key { + public final String value; + public final int compareResult; + + private Key(String value, int compareResult) { + this.value = value; + this.compareResult = compareResult; + } + + @Override public String toString() { + return value; + } + } + + static Object floorKey(String key) { + return new Key(key, -1); + } + + static Object ceilingKey(String key) { + return new Key(key, 1); + } + + @Override public int compare(Object o1, Object o2) { + String s1 = o1.toString(); + String s2 = o2.toString(); + int c = s1.compareToIgnoreCase(s2); + if (c != 0) { + return c; + } + if (o1 instanceof Key) { + return ((Key) o1).compareResult; + } + if (o2 instanceof Key) { + return -((Key) o2).compareResult; + } + return s1.compareTo(s2); + } +} + +// End CaseInsensitiveComparator.java http://git-wip-us.apache.org/repos/asf/calcite/blob/0a330e79/core/src/main/java/org/apache/calcite/util/NameHelper.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/util/NameHelper.java b/core/src/main/java/org/apache/calcite/util/NameHelper.java deleted file mode 100644 index bba80ac..0000000 --- a/core/src/main/java/org/apache/calcite/util/NameHelper.java +++ /dev/null @@ -1,197 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to you under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.calcite.util; - -import com.google.common.collect.ImmutableList; -import com.google.common.collect.ImmutableMap; -import com.google.common.collect.ImmutableSortedMap; -import com.google.common.collect.Ordering; - -import java.util.Collection; -import java.util.List; -import java.util.Map; -import java.util.NavigableMap; -import java.util.NavigableSet; -import java.util.SortedMap; -import java.util.SortedSet; -import java.util.function.BiFunction; -import java.util.stream.Collectors; - -import static org.apache.calcite.util.NameSet.COMPARATOR; - -/** Helps construct case-insensitive ranges of {@link NameSet}, - * {@link NameMap}, {@link NameMultimap}. - * - * <p>Not thread-safe. */ -class NameHelper { - /** Characters whose floor/ceiling are not the same as their upper/lower - * case. Out of 64k unicode characters, there are 289 weird characters. */ - private static final ImmutableMap<Character, Pair<Character, Character>> - WEIRD_CHARACTERS = weirdCharacters(); - - /** Workspace for computing the floor key. */ - private final StringBuilder floorBuilder = new StringBuilder(); - - /** Workspace for computing the ceiling key. */ - private final StringBuilder ceilingBuilder = new StringBuilder(); - - /** Given a string, computes the smallest and largest strings that are - * case-insensitive equal to that string, - * calls the given function, - * and returns its result. - * - * <p>For latin strings such as "bAz" computing the smallest and largest - * strings is straightforward: - * the floor is the upper-case string ("BAZ"), and - * the ceiling is the lower-case string ("baz"). - * - * <p>It's more complicated for non-Latin strings that have characters - * whose lower-case value is less than their upper-case value. - * - * <p>This method is not thread-safe. - */ - private <R> R applyFloorCeiling(String name, - BiFunction<String, String, R> f) { - name.chars() - .forEachOrdered(i -> { - final char c = (char) i; - final Pair<Character, Character> pair = WEIRD_CHARACTERS.get(c); - if (pair == null) { - floorBuilder.append(Character.toUpperCase(c)); - ceilingBuilder.append(Character.toLowerCase(c)); - } else { - floorBuilder.append(pair.left); - ceilingBuilder.append(pair.right); - } - }); - final String floor = bufValue(floorBuilder, name); - final String ceiling = bufValue(ceilingBuilder, name); - assert floor.compareTo(ceiling) <= 0; - return f.apply(floor, ceiling); - } - - /** Returns the value of a {@link StringBuilder} as a string, - * and clears the builder. - * - * <p>If the value is the same the given string, returns that string, - * thereby saving the effort of building a new string. */ - private static String bufValue(StringBuilder b, String s) { - if (b.length() != s.length() || b.indexOf(s) != 0) { - s = b.toString(); - } - b.setLength(0); - return s; - } - - /** Used by {@link NameSet#range(String, boolean)}. */ - Collection<String> set(NavigableSet<String> names, String name) { - return applyFloorCeiling(name, - (floor, ceiling) -> { - final NavigableSet<String> subSet = - names.subSet(floor, true, ceiling, true); - return subSet - .stream() - .filter(s -> s.equalsIgnoreCase(name)) - .collect(Collectors.toList()); - }); - } - - /** Used by {@link NameMap#range(String, boolean)}. */ - <V> ImmutableSortedMap<String, V> map(NavigableMap<String, V> map, - String name) { - return applyFloorCeiling(name, - (floor, ceiling) -> { - final ImmutableSortedMap.Builder<String, V> builder = - new ImmutableSortedMap.Builder<>(COMPARATOR); - final NavigableMap<String, V> subMap = - map.subMap(floor, true, ceiling, true); - for (Map.Entry<String, V> e : subMap.entrySet()) { - if (e.getKey().equalsIgnoreCase(name)) { - builder.put(e.getKey(), e.getValue()); - } - } - return builder.build(); - }); - } - - /** Used by {@link NameMultimap#range(String, boolean)}. */ - <V> Collection<Map.Entry<String, V>> multimap( - NavigableMap<String, List<V>> map, String name) { - return applyFloorCeiling(name, - (floor, ceiling) -> { - final NavigableMap<String, List<V>> subMap = - map.subMap(floor, true, ceiling, true); - final ImmutableList.Builder<Map.Entry<String, V>> builder = - ImmutableList.builder(); - for (Map.Entry<String, List<V>> e : subMap.entrySet()) { - if (e.getKey().equalsIgnoreCase(name)) { - for (V v : e.getValue()) { - builder.add(Pair.of(e.getKey(), v)); - } - } - } - return builder.build(); - }); - } - - /** Returns whether an equivalence class of characters is simple. - * - * <p>It is simple if - * the floor of the class is the upper-case value of every character, and - * the ceiling of the class is the lower-case value of every character. */ - private static boolean isSimple(Collection<Character> characters, - Character floor, Character ceiling) { - for (Character character : characters) { - if (!floor.equals(Character.toUpperCase(character))) { - return false; - } - if (!ceiling.equals(Character.toLowerCase(character))) { - return false; - } - } - return true; - } - - private static ImmutableMap<Character, Pair<Character, Character>> - weirdCharacters() { - final EquivalenceSet<Character> strange = new EquivalenceSet<>(); - for (int i = 0; i < 0xffff; i++) { - char c = (char) i; - strange.add(c); - strange.equiv(c, Character.toLowerCase(c)); - strange.equiv(c, Character.toUpperCase(c)); - } - final SortedMap<Character, SortedSet<Character>> map = strange.map(); - final ImmutableMap.Builder<Character, Pair<Character, Character>> builder = - ImmutableMap.builder(); - for (Map.Entry<Character, SortedSet<Character>> entry : map.entrySet()) { - final Collection<Character> characters = entry.getValue(); - final Character floor = Ordering.natural().min(characters); - final Character ceiling = Ordering.natural().max(characters); - if (isSimple(characters, floor, ceiling)) { - continue; - } - final Pair<Character, Character> pair = Pair.of(floor, ceiling); - for (Character character : characters) { - builder.put(character, pair); - } - } - return builder.build(); - } -} - -// End NameHelper.java http://git-wip-us.apache.org/repos/asf/calcite/blob/0a330e79/core/src/main/java/org/apache/calcite/util/NameMap.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/util/NameMap.java b/core/src/main/java/org/apache/calcite/util/NameMap.java index e48d63f..b5380d7 100644 --- a/core/src/main/java/org/apache/calcite/util/NameMap.java +++ b/core/src/main/java/org/apache/calcite/util/NameMap.java @@ -20,11 +20,12 @@ import org.apache.calcite.linq4j.function.Experimental; import com.google.common.collect.ImmutableSortedMap; +import java.util.Collections; import java.util.Map; import java.util.NavigableMap; import java.util.TreeMap; -import static org.apache.calcite.util.NameSet.COMPARATOR; +import static org.apache.calcite.util.CaseInsensitiveComparator.COMPARATOR; /** Map whose keys are names and can be accessed with and without case * sensitivity. @@ -32,7 +33,6 @@ import static org.apache.calcite.util.NameSet.COMPARATOR; * @param <V> Value type */ public class NameMap<V> { private final NavigableMap<String, V> map; - private final NameHelper helper = new NameHelper(); /** Creates a NameSet based on an existing set. */ private NameMap(NavigableMap<String, V> map) { @@ -72,15 +72,17 @@ public class NameMap<V> { * name. If case-sensitive, that map will have 0 or 1 elements; if * case-insensitive, it may have 0 or more. */ public NavigableMap<String, V> range(String name, boolean caseSensitive) { + Object floorKey; + Object ceilingKey; if (caseSensitive) { - if (map.containsKey(name)) { - return ImmutableSortedMap.of(name, map.get(name)); - } else { - return ImmutableSortedMap.of(); - } + floorKey = name; + ceilingKey = name; } else { - return helper.map(map, name); + floorKey = COMPARATOR.floorKey(name); + ceilingKey = COMPARATOR.ceilingKey(name); } + NavigableMap subMap = ((NavigableMap) map).subMap(floorKey, true, ceilingKey, true); + return Collections.unmodifiableNavigableMap((NavigableMap<String, V>) subMap); } /** Returns whether this map contains a given key, with a given http://git-wip-us.apache.org/repos/asf/calcite/blob/0a330e79/core/src/main/java/org/apache/calcite/util/NameMultimap.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/util/NameMultimap.java b/core/src/main/java/org/apache/calcite/util/NameMultimap.java index 5e51818..e7b7888 100644 --- a/core/src/main/java/org/apache/calcite/util/NameMultimap.java +++ b/core/src/main/java/org/apache/calcite/util/NameMultimap.java @@ -18,34 +18,32 @@ package org.apache.calcite.util; import org.apache.calcite.linq4j.function.Experimental; -import com.google.common.collect.ImmutableList; - import java.util.ArrayList; import java.util.Collection; +import java.util.Collections; import java.util.List; import java.util.Map; import java.util.NavigableMap; -import java.util.TreeMap; +import java.util.stream.Collectors; -import static org.apache.calcite.util.NameSet.COMPARATOR; +import static org.apache.calcite.util.CaseInsensitiveComparator.COMPARATOR; /** Multimap whose keys are names and can be accessed with and without case * sensitivity. * * @param <V> Value type */ public class NameMultimap<V> { - private final NavigableMap<String, List<V>> map; - private final NameHelper helper = new NameHelper(); + private final NameMap<List<V>> map; /** Creates a NameMultimap based on an existing map. */ - private NameMultimap(NavigableMap<String, List<V>> map) { + private NameMultimap(NameMap<List<V>> map) { this.map = map; - assert this.map.comparator() == COMPARATOR; + assert map.map().comparator() == COMPARATOR; } /** Creates a NameMultimap, initially empty. */ public NameMultimap() { - this(new TreeMap<String, List<V>>(COMPARATOR)); + this(new NameMap<>()); } @Override public String toString() { @@ -64,7 +62,7 @@ public class NameMultimap<V> { /** Adds an entry to this multimap. */ public void put(String name, V v) { - List<V> list = map.computeIfAbsent(name, k -> new ArrayList<>()); + List<V> list = map().computeIfAbsent(name, k -> new ArrayList<>()); list.add(v); } @@ -73,7 +71,7 @@ public class NameMultimap<V> { * @return Whether a value was removed */ @Experimental public boolean remove(String key, V value) { - final List<V> list = map.get(key); + final List<V> list = map().get(key); if (list == null) { return false; } @@ -84,33 +82,23 @@ public class NameMultimap<V> { * given name. */ public Collection<Map.Entry<String, V>> range(String name, boolean caseSensitive) { - if (caseSensitive) { - final List<V> list = map.get(name); - if (list != null && !list.isEmpty()) { - final ImmutableList.Builder<Map.Entry<String, V>> builder = - ImmutableList.builder(); - for (V v : list) { - builder.add(Pair.of(name, v)); - } - return builder.build(); - } else { - return ImmutableList.of(); - } - } else { - return helper.multimap(map, name); - } + NavigableMap<String, List<V>> range = map.range(name, caseSensitive); + List<Pair<String, V>> result = range.entrySet().stream() + .flatMap(e -> e.getValue().stream().map(v -> Pair.of(e.getKey(), v))) + .collect(Collectors.toList()); + return Collections.unmodifiableList(result); } /** Returns whether this map contains a given key, with a given * case-sensitivity. */ public boolean containsKey(String name, boolean caseSensitive) { - return !range(name, caseSensitive).isEmpty(); + return map.containsKey(name, caseSensitive); } /** Returns the underlying map. * Its size is the number of keys, not the number of values. */ public NavigableMap<String, List<V>> map() { - return map; + return map.map(); } } http://git-wip-us.apache.org/repos/asf/calcite/blob/0a330e79/core/src/main/java/org/apache/calcite/util/NameSet.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/util/NameSet.java b/core/src/main/java/org/apache/calcite/util/NameSet.java index 12a291e..a04922b 100644 --- a/core/src/main/java/org/apache/calcite/util/NameSet.java +++ b/core/src/main/java/org/apache/calcite/util/NameSet.java @@ -16,53 +16,38 @@ */ package org.apache.calcite.util; -import com.google.common.collect.ImmutableList; -import com.google.common.collect.ImmutableSortedSet; +import com.google.common.collect.Maps; import java.util.Collection; import java.util.Collections; import java.util.Comparator; -import java.util.Locale; -import java.util.NavigableSet; import java.util.Set; -import java.util.TreeSet; /** Set of names that can be accessed with and without case sensitivity. */ public class NameSet { - /** Comparator that compares all strings differently, but if two strings are - * equal in case-insensitive match they are right next to each other. In a - * collection sorted on this comparator, we can find case-insensitive matches - * for a given string using a range scan between the upper-case string and - * the lower-case string. */ - public static final Comparator<String> COMPARATOR = (o1, o2) -> { - int c = o1.compareToIgnoreCase(o2); - if (c == 0) { - c = o1.compareTo(o2); - } - return c; - }; - - private final NavigableSet<String> names; - private final NameHelper helper = new NameHelper(); + public static final Comparator<String> COMPARATOR = CaseInsensitiveComparator.COMPARATOR; + + private static final Object DUMMY = new Object(); + + private final NameMap<Object> names; /** Creates a NameSet based on an existing set. */ - private NameSet(NavigableSet<String> names) { + private NameSet(NameMap<Object> names) { this.names = names; - assert names.comparator() == COMPARATOR; } /** Creates a NameSet, initially empty. */ public NameSet() { - this(new TreeSet<>(COMPARATOR)); + this(new NameMap<>()); } /** Creates a NameSet that is an immutable copy of a given collection. */ public static NameSet immutableCopyOf(Set<String> names) { - return new NameSet(ImmutableSortedSet.copyOf(NameSet.COMPARATOR, names)); + return new NameSet(NameMap.immutableCopyOf(Maps.asMap(names, (k) -> DUMMY))); } @Override public String toString() { - return names.toString(); + return names.map().keySet().toString(); } @Override public int hashCode() { @@ -76,47 +61,25 @@ public class NameSet { } public void add(String name) { - names.add(name); + names.put(name, DUMMY); } /** Returns an iterable over all the entries in the set that match the given * name. If case-sensitive, that iterable will have 0 or 1 elements; if * case-insensitive, it may have 0 or more. */ public Collection<String> range(String name, boolean caseSensitive) { - if (caseSensitive) { - if (names.contains(name)) { - return ImmutableList.of(name); - } else { - return ImmutableList.of(); - } - } else { - return helper.set(names, name); - } + return names.range(name, caseSensitive).keySet(); } /** Returns whether this set contains the given name, with a given * case-sensitivity. */ public boolean contains(String name, boolean caseSensitive) { - if (names.contains(name)) { - return true; - } - if (!caseSensitive) { - final String lowerName = name.toLowerCase(Locale.ROOT); - final String ceiling = names.ceiling(lowerName); - if (ceiling != null && ceiling.equalsIgnoreCase(name)) { - return true; - } - final String floor = names.floor(lowerName); - if (floor != null && floor.equalsIgnoreCase(name)) { - return true; - } - } - return false; + return names.containsKey(name, caseSensitive); } /** Returns the contents as an iterable. */ public Iterable<String> iterable() { - return Collections.unmodifiableSet(names); + return Collections.unmodifiableSet(names.map().keySet()); } } http://git-wip-us.apache.org/repos/asf/calcite/blob/0a330e79/core/src/test/java/org/apache/calcite/util/UtilTest.java ---------------------------------------------------------------------- diff --git a/core/src/test/java/org/apache/calcite/util/UtilTest.java b/core/src/test/java/org/apache/calcite/util/UtilTest.java index a4070b2..f164071 100644 --- a/core/src/test/java/org/apache/calcite/util/UtilTest.java +++ b/core/src/test/java/org/apache/calcite/util/UtilTest.java @@ -1656,6 +1656,8 @@ public class UtilTest { } private NavigableSet<String> checkNav(NavigableSet<String> set, String s) { + // Note this does not support some unicode characters + // however it is fine for testing purposes return set.subSet(s.toUpperCase(Locale.ROOT), true, s.toLowerCase(Locale.ROOT), true); }
