[FELIX-4942] Use OpenHashMap in Packages and introduce a very fast ArrayMap for very small maps
git-svn-id: https://svn.apache.org/repos/asf/felix/trunk@1690706 13f79535-47bb-0310-9956-ffa450edef68
diff --git a/resolver/src/main/java/org/apache/felix/resolver/ResolverImpl.java b/resolver/src/main/java/org/apache/felix/resolver/ResolverImpl.java
index ab6e352..72ac40b 100644
--- a/resolver/src/main/java/org/apache/felix/resolver/ResolverImpl.java
+++ b/resolver/src/main/java/org/apache/felix/resolver/ResolverImpl.java
@@ -31,6 +31,8 @@
import java.util.Map.Entry;
import java.util.Set;
+import org.apache.felix.resolver.util.ArrayMap;
+import org.apache.felix.resolver.util.OpenHashMap;
import org.osgi.framework.namespace.BundleNamespace;
import org.osgi.framework.namespace.ExecutionEnvironmentNamespace;
import org.osgi.framework.namespace.HostNamespace;
@@ -820,7 +822,7 @@
}
}
// Merge uses constraints from imported packages.
- for (Entry<String, List<Blame>> entry : resourcePkgs.m_importedPkgs.entrySet())
+ for (Entry<String, List<Blame>> entry : resourcePkgs.m_importedPkgs.fast())
{
for (Blame blame : entry.getValue())
{
@@ -844,7 +846,7 @@
}
}
// Merge uses constraints from required bundles.
- for (Entry<String, List<Blame>> entry : resourcePkgs.m_requiredPkgs.entrySet())
+ for (Entry<String, List<Blame>> entry : resourcePkgs.m_requiredPkgs.fast())
{
for (Blame blame : entry.getValue())
{
@@ -908,7 +910,7 @@
{
// We have to merge all exported packages from the candidate,
// since the current resource requires it.
- for (Entry<String, Blame> entry : candPkgs.m_exportedPkgs.entrySet())
+ for (Entry<String, Blame> entry : candPkgs.m_exportedPkgs.fast())
{
mergeCandidatePackage(
current,
@@ -989,15 +991,10 @@
Packages currentPkgs = resourcePkgMap.get(current);
- Map<String, List<Blame>> packages = (requires)
+ OpenHashMap<String, List<Blame>> packages = (requires)
? currentPkgs.m_requiredPkgs
: currentPkgs.m_importedPkgs;
- List<Blame> blames = packages.get(pkgName);
- if (blames == null)
- {
- blames = new ArrayList<Blame>();
- packages.put(pkgName, blames);
- }
+ List<Blame> blames = packages.getOrCompute(pkgName);
blames.add(new Blame(candCap, blameReqs));
//dumpResourcePkgs(current, currentPkgs);
@@ -1087,12 +1084,7 @@
continue;
}
- Map<Capability, UsedBlames> usedPkgBlames = currentPkgs.m_usedPkgs.get(usedPkgName);
- if (usedPkgBlames == null)
- {
- usedPkgBlames = new LinkedHashMap<Capability, UsedBlames>();
- currentPkgs.m_usedPkgs.put(usedPkgName, usedPkgBlames);
- }
+ ArrayMap<Capability, UsedBlames> usedPkgBlames = currentPkgs.m_usedPkgs.getOrCompute(usedPkgName);
for (Blame blame : candSourceBlames)
{
if (blame.m_reqs != null)
@@ -1153,20 +1145,14 @@
}
private static void addUsedBlame(
- Map<Capability, UsedBlames> usedBlames, Capability usedCap,
+ ArrayMap<Capability, UsedBlames> usedBlames, Capability usedCap,
List<Requirement> blameReqs, Capability matchingCap)
{
// Create a new Blame based off the used capability and the
// blame chain requirements.
Blame newBlame = new Blame(usedCap, blameReqs);
// Find UsedBlame that uses the same capablity as the new blame.
- UsedBlames addToBlame = usedBlames.get(usedCap);
- if (addToBlame == null)
- {
- // If none exist create a new UsedBlame for the capability.
- addToBlame = new UsedBlames(usedCap);
- usedBlames.put(usedCap, addToBlame);
- }
+ UsedBlames addToBlame = usedBlames.getOrCompute(usedCap);
// Add the new Blame and record the matching capability cause
// in case the root requirement has multiple cardinality.
addToBlame.addBlame(newBlame, matchingCap);
@@ -1213,7 +1199,7 @@
// TODO: Is this only needed for imports or are generic and bundle requirements also needed?
// I think this is only a special case for fragment imports because they can overlap
// host imports, which is not allowed in normal metadata.
- for (Entry<String, List<Blame>> entry : pkgs.m_importedPkgs.entrySet())
+ for (Entry<String, List<Blame>> entry : pkgs.m_importedPkgs.fast())
{
if (entry.getValue().size() > 1)
{
@@ -1249,7 +1235,7 @@
}
// Check if there are any uses conflicts with exported packages.
- for (Entry<String, Blame> entry : pkgs.m_exportedPkgs.entrySet())
+ for (Entry<String, Blame> entry : pkgs.m_exportedPkgs.fast())
{
String pkgName = entry.getKey();
Blame exportBlame = entry.getValue();
@@ -1332,12 +1318,12 @@
// We combine the imported and required packages here into one map.
// Imported packages are added after required packages because they shadow or override
// the packages from required bundles.
- Map<String, List<Blame>> allImportRequirePkgs =
- new LinkedHashMap<String, List<Blame>>(pkgs.m_requiredPkgs.size() + pkgs.m_importedPkgs.size());
+ OpenHashMap<String, List<Blame>> allImportRequirePkgs =
+ new OpenHashMap<String, List<Blame>>(pkgs.m_requiredPkgs.size() + pkgs.m_importedPkgs.size());
allImportRequirePkgs.putAll(pkgs.m_requiredPkgs);
allImportRequirePkgs.putAll(pkgs.m_importedPkgs);
- for (Entry<String, List<Blame>> requirementBlames : allImportRequirePkgs.entrySet())
+ for (Entry<String, List<Blame>> requirementBlames : allImportRequirePkgs.fast())
{
String pkgName = requirementBlames.getKey();
if (!pkgs.m_usedPkgs.containsKey(pkgName))
@@ -1952,7 +1938,7 @@
System.out.println(" " + entry.getKey() + " - " + entry.getValue());
}
System.out.println(" USED");
- for (Entry<String, Map<Capability, UsedBlames>> entry : packages.m_usedPkgs.entrySet())
+ for (Entry<String, ArrayMap<Capability, UsedBlames>> entry : packages.m_usedPkgs.entrySet())
{
System.out.println(" " + entry.getKey() + " - " + entry.getValue().values());
}
@@ -2099,16 +2085,39 @@
private static class Packages
{
- private final Resource m_resource;
- public final Map<String, Blame> m_exportedPkgs = new LinkedHashMap<String, Blame>(32);
- public final Map<String, List<Blame>> m_importedPkgs = new LinkedHashMap<String, List<Blame>>(32);
- public final Map<String, List<Blame>> m_requiredPkgs = new LinkedHashMap<String, List<Blame>>(32);
- public final Map<String, Map<Capability, UsedBlames>> m_usedPkgs = new LinkedHashMap<String, Map<Capability, UsedBlames>>(32);
+ public final OpenHashMap<String, Blame> m_exportedPkgs;
+ public final OpenHashMap<String, List<Blame>> m_importedPkgs;
+ public final OpenHashMap<String, List<Blame>> m_requiredPkgs;
+ public final OpenHashMap<String, ArrayMap<Capability, UsedBlames>> m_usedPkgs;
public boolean m_isCalculated = false;
public Packages(Resource resource)
{
- m_resource = resource;
+ int nbCaps = resource.getCapabilities(null).size();
+ int nbReqs = resource.getRequirements(null).size();
+
+ m_exportedPkgs = new OpenHashMap<String, Blame>(nbCaps);
+ m_importedPkgs = new OpenHashMap<String, List<Blame>>(nbReqs) {
+ public List<Blame> compute(String s) {
+ return new ArrayList<Blame>();
+ }
+ };
+ m_requiredPkgs = new OpenHashMap<String, List<Blame>>(nbReqs) {
+ public List<Blame> compute(String s) {
+ return new ArrayList<Blame>();
+ }
+ };
+ m_usedPkgs = new OpenHashMap<String, ArrayMap<Capability, UsedBlames>>(128) {
+ @Override
+ protected ArrayMap<Capability, UsedBlames> compute(String s) {
+ return new ArrayMap<Capability, UsedBlames>() {
+ @Override
+ protected UsedBlames compute(Capability key) {
+ return new UsedBlames(key);
+ }
+ };
+ }
+ };
}
}
diff --git a/resolver/src/main/java/org/apache/felix/resolver/util/ArrayMap.java b/resolver/src/main/java/org/apache/felix/resolver/util/ArrayMap.java
new file mode 100644
index 0000000..9f2931e
--- /dev/null
+++ b/resolver/src/main/java/org/apache/felix/resolver/util/ArrayMap.java
@@ -0,0 +1,192 @@
+/*
+ * 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.felix.resolver.util;
+
+import java.util.*;
+import java.util.function.Function;
+
+public class ArrayMap<K, V> extends AbstractMap<K, V> {
+
+ private Object[] table;
+ private int size;
+ protected transient volatile Collection<V> values;
+
+ public ArrayMap() {
+ this(32);
+ }
+
+ public ArrayMap(int capacity) {
+ table = new Object[capacity * 2];
+ size = 0;
+ }
+
+ @Override
+ @SuppressWarnings("unchecked")
+ public V get(Object key) {
+ for (int i = 0, l = size << 1; i < l; i += 2) {
+ if (key.equals(table[i])) {
+ return (V) table[i + 1];
+ }
+ }
+ return null;
+ }
+
+ @Override
+ @SuppressWarnings("unchecked")
+ public V put(K key, V value) {
+ for (int i = 0, l = size << 1; i < l; i += 2) {
+ if (key.equals(table[i])) {
+ V old = (V) table[i + 1];
+ table[i + 1] = value;
+ return old;
+ }
+ }
+ if (size * 2 == table.length) {
+ Object[] n = new Object[table.length * 2];
+ System.arraycopy(table, 0, n, 0, table.length);
+ table = n;
+ }
+ int i = size++ << 1;
+ table[i++] = key;
+ table[i] = value;
+ return null;
+ }
+
+ @SuppressWarnings("unchecked")
+ public V getOrCompute(K key) {
+ for (int i = 0, l = size << 1; i < l; i += 2) {
+ if (key.equals(table[i])) {
+ return (V) table[i + 1];
+ }
+ }
+ V v = compute(key);
+ if (size << 1 == table.length) {
+ Object[] n = new Object[table.length << 1];
+ System.arraycopy(table, 0, n, 0, table.length);
+ table = n;
+ }
+ int i = size++ << 1;
+ table[i++] = key;
+ table[i] = v;
+ return v;
+ }
+
+ protected V compute(K key) {
+ throw new UnsupportedOperationException();
+ }
+
+ @SuppressWarnings("unchecked")
+ public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
+ for (int i = 0, l = size << 1; i < l; i += 2) {
+ if (key.equals(table[i])) {
+ return (V) table[i + 1];
+ }
+ }
+ if (size << 1 == table.length) {
+ Object[] n = new Object[table.length << 1];
+ System.arraycopy(table, 0, n, 0, table.length);
+ table = n;
+ }
+ int i = size++ << 1;
+ table[i++] = key;
+ return (V) (table[i] = mappingFunction.apply(key));
+ }
+
+ @Override
+ public Collection<V> values() {
+ if (values == null) {
+ values = new AbstractCollection<V>() {
+ @Override
+ public Iterator<V> iterator() {
+ return new Iterator<V>() {
+ int index = 0;
+
+ public boolean hasNext() {
+ return index < size;
+ }
+
+ public V next() {
+ if (index >= size) {
+ throw new NoSuchElementException();
+ }
+ return (V) table[(index++ << 1) + 1];
+ }
+ };
+ }
+
+ @Override
+ public int size() {
+ return size;
+ }
+ };
+ }
+ return values;
+ }
+
+ @Override
+ public Set<Entry<K, V>> entrySet() {
+ return new AbstractSet<Entry<K, V>>() {
+ @Override
+ public Iterator<Entry<K, V>> iterator() {
+ return new Iterator<Entry<K, V>>() {
+ FastEntry entry = new FastEntry();
+ int index = 0;
+
+ public boolean hasNext() {
+ return index < size;
+ }
+
+ public Entry<K, V> next() {
+ if (index >= size) {
+ throw new NoSuchElementException();
+ }
+ int i = index << 1;
+ entry.key = table[i];
+ entry.value = table[i + 1];
+ index++;
+ return entry;
+ }
+ };
+ }
+
+ @Override
+ public int size() {
+ return size;
+ }
+ };
+ }
+
+ static class FastEntry<K, V> implements Entry<K, V> {
+ K key;
+ V value;
+
+ public K getKey() {
+ return key;
+ }
+
+
+ public V getValue() {
+ return value;
+ }
+
+ public V setValue(V value) {
+ throw new UnsupportedOperationException();
+ }
+ }
+}