[KARAF-2888] Optimize start bundle sorting which is really slow
Project: http://git-wip-us.apache.org/repos/asf/karaf/repo Commit: http://git-wip-us.apache.org/repos/asf/karaf/commit/78fbae7f Tree: http://git-wip-us.apache.org/repos/asf/karaf/tree/78fbae7f Diff: http://git-wip-us.apache.org/repos/asf/karaf/diff/78fbae7f Branch: refs/heads/master Commit: 78fbae7faa140f88b76358d89af044dcc8693411 Parents: 286939f Author: Guillaume Nodet <gno...@gmail.com> Authored: Fri Apr 11 15:47:33 2014 +0200 Committer: Guillaume Nodet <gno...@gmail.com> Committed: Fri Apr 11 19:20:03 2014 +0200 ---------------------------------------------------------------------- .../internal/service/FeaturesServiceImpl.java | 5 +- .../internal/service/RequirementSort.java | 87 +++++++------------- 2 files changed, 33 insertions(+), 59 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/karaf/blob/78fbae7f/features/src/main/java/org/apache/karaf/features/internal/service/FeaturesServiceImpl.java ---------------------------------------------------------------------- diff --git a/features/src/main/java/org/apache/karaf/features/internal/service/FeaturesServiceImpl.java b/features/src/main/java/org/apache/karaf/features/internal/service/FeaturesServiceImpl.java index 65223d5..7008ef6 100644 --- a/features/src/main/java/org/apache/karaf/features/internal/service/FeaturesServiceImpl.java +++ b/features/src/main/java/org/apache/karaf/features/internal/service/FeaturesServiceImpl.java @@ -64,10 +64,7 @@ import org.osgi.framework.FrameworkEvent; import org.osgi.framework.FrameworkListener; import org.osgi.framework.ServiceReference; import org.osgi.framework.Version; -import org.osgi.framework.namespace.PackageNamespace; import org.osgi.framework.startlevel.BundleStartLevel; -import org.osgi.framework.wiring.BundleCapability; -import org.osgi.framework.wiring.BundleRequirement; import org.osgi.framework.wiring.BundleRevision; import org.osgi.framework.wiring.BundleWire; import org.osgi.framework.wiring.BundleWiring; @@ -1043,7 +1040,7 @@ public class FeaturesServiceImpl implements FeaturesService { // TODO: remove this hack, but it avoids loading the class after the bundle is refreshed new CopyOnWriteArrayIdentityList().iterator(); - new RequirementSort(); + RequirementSort.sort(Collections.<Resource>emptyList()); if (!noRefresh) { toStop = new HashSet<Bundle>(); http://git-wip-us.apache.org/repos/asf/karaf/blob/78fbae7f/features/src/main/java/org/apache/karaf/features/internal/service/RequirementSort.java ---------------------------------------------------------------------- diff --git a/features/src/main/java/org/apache/karaf/features/internal/service/RequirementSort.java b/features/src/main/java/org/apache/karaf/features/internal/service/RequirementSort.java index e9ecece..96b99ee 100644 --- a/features/src/main/java/org/apache/karaf/features/internal/service/RequirementSort.java +++ b/features/src/main/java/org/apache/karaf/features/internal/service/RequirementSort.java @@ -16,92 +16,69 @@ */ package org.apache.karaf.features.internal.service; +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashSet; +import java.util.LinkedHashSet; +import java.util.Set; -import org.apache.karaf.features.internal.resolver.RequirementImpl; +import org.apache.karaf.features.internal.resolver.CapabilitySet; import org.apache.karaf.features.internal.resolver.SimpleFilter; import org.osgi.framework.Constants; import org.osgi.resource.Capability; import org.osgi.resource.Requirement; import org.osgi.resource.Resource; -import java.util.Collection; -import java.util.LinkedHashSet; -import java.util.List; -import java.util.Set; - -public class RequirementSort { +public class RequirementSort<T extends Resource> { /** * Sorts {@link Resource} based on their {@link Requirement}s and {@link Capability}s. - * @param resources - * @return */ public static <T extends Resource> Collection<T> sort(Collection<T> resources) { + Set<String> namespaces = new HashSet<String>(); + for (Resource r : resources) { + for (Capability cap : r.getCapabilities(null)) { + namespaces.add(cap.getNamespace()); + } + } + CapabilitySet capSet = new CapabilitySet(new ArrayList<String>(namespaces)); + for (Resource r : resources) { + for (Capability cap : r.getCapabilities(null)) { + capSet.addCapability(cap); + } + } Set<T> sorted = new LinkedHashSet<T>(); Set<T> visited = new LinkedHashSet<T>(); for (T r : resources) { - visit(r, resources, visited, sorted); + visit(r, visited, sorted, capSet); } return sorted; } - private static <T extends Resource> void visit(T resource, Collection<T> resources, Set<T> visited, Set<T> sorted) { - if (visited.contains(resource)) { + private static <T extends Resource> void visit(T resource, Set<T> visited, Set<T> sorted, CapabilitySet capSet) { + if (!visited.add(resource)) { return; } - visited.add(resource); - for (T r : collectDependencies(resource, resources)) { - visit(r, resources, visited, sorted); + for (T r : collectDependencies(resource, capSet)) { + visit(r, visited, sorted, capSet); } sorted.add(resource); } - /** - * Finds the dependencies of the current resource. - * @param resource - * @param allResources - * @return - */ - private static <T extends Resource> Set<T> collectDependencies(T resource, Collection<T> allResources) { + @SuppressWarnings("unchecked") + private static <T extends Resource> Set<T> collectDependencies(T resource, CapabilitySet capSet) { Set<T> result = new LinkedHashSet<T>(); - List<Requirement> requirements = resource.getRequirements(null); - for (Requirement requirement : requirements) { - boolean isSatisfied = false; - for (Resource r : result) { - for (Capability capability : r.getCapabilities(null)) { - if (isSatisfied(requirement, capability)) { - isSatisfied = true; - break; - } - } - } - - for (T r : allResources) { - if (!isSatisfied) { - for (Capability capability : r.getCapabilities(null)) { - if (isSatisfied(requirement, capability)) { - result.add(r); - break; - } - } - } - } - } - return result; - } - - private static boolean isSatisfied(Requirement requirement, Capability capability) { - RequirementImpl br; - if (requirement instanceof RequirementImpl) { - br = (RequirementImpl) requirement; - } else { + for (Requirement requirement : resource.getRequirements(null)) { String filter = requirement.getDirectives().get(Constants.FILTER_DIRECTIVE); SimpleFilter sf = (filter != null) ? SimpleFilter.parse(filter) : new SimpleFilter(null, null, SimpleFilter.MATCH_ALL); - br = new RequirementImpl(null, requirement.getNamespace(), requirement.getDirectives(), requirement.getAttributes(), sf); + for (Capability cap : capSet.match(sf, true)) { + result.add((T) cap.getResource()); + } } - return br.matches(capability); + return result; } + }