[FELIX-4656] Use more efficient data structures
git-svn-id: https://svn.apache.org/repos/asf/felix/trunk@1667213 13f79535-47bb-0310-9956-ffa450edef68
diff --git a/resolver/src/main/java/org/apache/felix/resolver/Candidates.java b/resolver/src/main/java/org/apache/felix/resolver/Candidates.java
index 409a770..1cb929e 100644
--- a/resolver/src/main/java/org/apache/felix/resolver/Candidates.java
+++ b/resolver/src/main/java/org/apache/felix/resolver/Candidates.java
@@ -29,6 +29,13 @@
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;
+
+import org.apache.felix.resolver.util.CopyOnWriteSet;
+import org.apache.felix.resolver.util.CopyOnWriteList;
+import org.apache.felix.resolver.util.OpenHashMap;
+import org.apache.felix.resolver.util.OpenHashMapList;
+import org.apache.felix.resolver.util.OpenHashMapSet;
+import org.apache.felix.resolver.util.ShadowList;
import org.osgi.framework.Version;
import org.osgi.framework.namespace.HostNamespace;
import org.osgi.framework.namespace.IdentityNamespace;
@@ -49,9 +56,9 @@
private final Set<Resource> m_mandatoryResources;
// Maps a capability to requirements that match it.
- private final Map<Capability, Set<Requirement>> m_dependentMap;
+ private final OpenHashMapSet<Capability, Requirement> m_dependentMap;
// Maps a requirement to the capability it matches.
- private final Map<Requirement, List<Capability>> m_candidateMap;
+ private final OpenHashMapList<Requirement, Capability> m_candidateMap;
// Maps a bundle revision to its associated wrapped revision; this only happens
// when a revision being resolved has fragments to attach to it.
private final Map<Resource, WrappedResource> m_allWrappedHosts;
@@ -70,8 +77,8 @@
*/
private Candidates(
Set<Resource> mandatoryResources,
- Map<Capability, Set<Requirement>> dependentMap,
- Map<Requirement, List<Capability>> candidateMap,
+ OpenHashMapSet<Capability, Requirement> dependentMap,
+ OpenHashMapList<Requirement, Capability> candidateMap,
Map<Resource, WrappedResource> wrappedHosts, Map<Resource, Object> populateResultCache,
boolean fragmentsPresent,
Map<Resource, Boolean> onDemandResources,
@@ -93,8 +100,8 @@
public Candidates(Map<Resource, Boolean> validOnDemandResources)
{
m_mandatoryResources = new HashSet<Resource>();
- m_dependentMap = new HashMap<Capability, Set<Requirement>>();
- m_candidateMap = new HashMap<Requirement, List<Capability>>();
+ m_dependentMap = new OpenHashMapSet<Capability, Requirement>();
+ m_candidateMap = new OpenHashMapList<Requirement, Capability>();
m_allWrappedHosts = new HashMap<Resource, WrappedResource>();
m_populateResultCache = new HashMap<Resource, Object>();
m_validOnDemandResources = validOnDemandResources;
@@ -732,7 +739,7 @@
}
// Record the candidates.
- m_candidateMap.put(req, candidates);
+ m_candidateMap.put(req, new CopyOnWriteList<Capability>(candidates));
}
/**
@@ -929,10 +936,10 @@
// from the dependent map, but you can't since it may come from
// a fragment that is attached to multiple hosts, so each host
// will need to make their own copy.
- Set<Requirement> dependents = m_dependentMap.get(origCap);
+ CopyOnWriteSet<Requirement> dependents = m_dependentMap.get(origCap);
if (dependents != null)
{
- dependents = new HashSet<Requirement>(dependents);
+ dependents = new CopyOnWriteSet<Requirement>(dependents);
m_dependentMap.put(c, dependents);
for (Requirement r : dependents)
{
@@ -966,8 +973,7 @@
List<Capability> cands = m_candidateMap.get(r);
if (!(cands instanceof ShadowList))
{
- ShadowList<Capability> shadow =
- new ShadowList<Capability>(cands);
+ ShadowList<Capability> shadow = new ShadowList<Capability>(cands);
m_candidateMap.put(r, shadow);
cands = shadow;
}
@@ -977,7 +983,7 @@
// shadow copy of the list accordingly.
if (!origCap.getResource().equals(hostResource.getDeclaredResource()))
{
- List<Capability> original = ((ShadowList) cands).getOriginal();
+ List<Capability> original = ((ShadowList<Capability>) cands).getOriginal();
int removeIdx = original.indexOf(origCap);
if (removeIdx != -1)
{
@@ -1010,7 +1016,7 @@
List<Capability> cands = m_candidateMap.get(origReq);
if (cands != null)
{
- m_candidateMap.put(r, new ArrayList<Capability>(cands));
+ m_candidateMap.put(r, new CopyOnWriteList<Capability>(cands));
for (Capability cand : cands)
{
Set<Requirement> dependents = m_dependentMap.get(cand);
@@ -1033,6 +1039,9 @@
}
populateSubstitutables();
+
+ m_candidateMap.concat();
+ m_dependentMap.concat();
}
// Maps a host capability to a map containing its potential fragments;
@@ -1043,17 +1052,17 @@
{
Map<Capability, Map<String, Map<Version, List<Requirement>>>> hostFragments =
new HashMap<Capability, Map<String, Map<Version, List<Requirement>>>>();
- for (Entry<Requirement, List<Capability>> entry : m_candidateMap.entrySet())
+ for (Entry<Requirement, CopyOnWriteList<Capability>> entry : m_candidateMap.entrySet())
{
Requirement req = entry.getKey();
List<Capability> caps = entry.getValue();
for (Capability cap : caps)
{
// Record the requirement as dependent on the capability.
- Set<Requirement> dependents = m_dependentMap.get(cap);
+ CopyOnWriteSet<Requirement> dependents = m_dependentMap.get(cap);
if (dependents == null)
{
- dependents = new HashSet<Requirement>();
+ dependents = new CopyOnWriteSet<Requirement>();
m_dependentMap.put(cap, dependents);
}
dependents.add(req);
@@ -1214,35 +1223,22 @@
*/
public Candidates copy()
{
- Map<Capability, Set<Requirement>> dependentMap =
- new HashMap<Capability, Set<Requirement>>();
- for (Entry<Capability, Set<Requirement>> entry : m_dependentMap.entrySet())
- {
- Set<Requirement> dependents = new HashSet<Requirement>(entry.getValue());
- dependentMap.put(entry.getKey(), dependents);
- }
-
- Map<Requirement, List<Capability>> candidateMap =
- new HashMap<Requirement, List<Capability>>();
- for (Entry<Requirement, List<Capability>> entry
- : m_candidateMap.entrySet())
- {
- List<Capability> candidates =
- new ArrayList<Capability>(entry.getValue());
- candidateMap.put(entry.getKey(), candidates);
- }
-
return new Candidates(
- m_mandatoryResources, dependentMap, candidateMap,
- m_allWrappedHosts, m_populateResultCache, m_fragmentsPresent, m_validOnDemandResources,
- m_subtitutableMap);
+ m_mandatoryResources,
+ m_dependentMap.deepClone(),
+ m_candidateMap.deepClone(),
+ m_allWrappedHosts,
+ m_populateResultCache,
+ m_fragmentsPresent,
+ m_validOnDemandResources,
+ m_subtitutableMap);
}
public void dump(ResolveContext rc)
{
// Create set of all revisions from requirements.
- Set<Resource> resources = new HashSet<Resource>();
- for (Entry<Requirement, List<Capability>> entry
+ Set<Resource> resources = new CopyOnWriteSet<Resource>();
+ for (Entry<Requirement, CopyOnWriteList<Capability>> entry
: m_candidateMap.entrySet())
{
resources.add(entry.getKey().getResource());
diff --git a/resolver/src/main/java/org/apache/felix/resolver/ShadowList.java b/resolver/src/main/java/org/apache/felix/resolver/ShadowList.java
deleted file mode 100644
index 05734da..0000000
--- a/resolver/src/main/java/org/apache/felix/resolver/ShadowList.java
+++ /dev/null
@@ -1,157 +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.felix.resolver;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Iterator;
-import java.util.List;
-import java.util.ListIterator;
-
-public class ShadowList<T> implements List<T>
-{
- private final List<T> m_original;
- private final List<T> m_shadow;
-
- public ShadowList(List<T> original)
- {
- m_original = original;
- m_shadow = new ArrayList<T>(original);
- }
-
- public List<T> getOriginal()
- {
- return m_original;
- }
-
- public int size()
- {
- return m_shadow.size();
- }
-
- public boolean isEmpty()
- {
- return m_shadow.isEmpty();
- }
-
- public boolean contains(Object o)
- {
- return m_shadow.contains(o);
- }
-
- public Iterator<T> iterator()
- {
- return m_shadow.iterator();
- }
-
- public Object[] toArray()
- {
- return m_shadow.toArray();
- }
-
- public <T> T[] toArray(T[] ts)
- {
- return m_shadow.toArray(ts);
- }
-
- public boolean add(T e)
- {
- return m_shadow.add(e);
- }
-
- public boolean remove(Object o)
- {
- return m_shadow.remove(o);
- }
-
- public boolean containsAll(Collection<?> clctn)
- {
- return m_shadow.containsAll(clctn);
- }
-
- public boolean addAll(Collection<? extends T> clctn)
- {
- return m_shadow.addAll(clctn);
- }
-
- public boolean addAll(int i, Collection<? extends T> clctn)
- {
- return m_shadow.addAll(i, clctn);
- }
-
- public boolean removeAll(Collection<?> clctn)
- {
- return m_shadow.removeAll(clctn);
- }
-
- public boolean retainAll(Collection<?> clctn)
- {
- return m_shadow.retainAll(clctn);
- }
-
- public void clear()
- {
- m_shadow.clear();
- }
-
- public T get(int i)
- {
- return m_shadow.get(i);
- }
-
- public T set(int i, T e)
- {
- return m_shadow.set(i, e);
- }
-
- public void add(int i, T e)
- {
- m_shadow.add(i, e);
- }
-
- public T remove(int i)
- {
- return m_shadow.remove(i);
- }
-
- public int indexOf(Object o)
- {
- return m_shadow.indexOf(o);
- }
-
- public int lastIndexOf(Object o)
- {
- return m_shadow.lastIndexOf(o);
- }
-
- public ListIterator<T> listIterator()
- {
- return m_shadow.listIterator();
- }
-
- public ListIterator<T> listIterator(int i)
- {
- return m_shadow.listIterator(i);
- }
-
- public List<T> subList(int i, int i1)
- {
- return m_shadow.subList(i, i1);
- }
-}
\ No newline at end of file
diff --git a/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java b/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java
new file mode 100644
index 0000000..b22ab30
--- /dev/null
+++ b/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java
@@ -0,0 +1,94 @@
+/*
+ * 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.AbstractList;
+import java.util.Arrays;
+import java.util.Collection;
+
+public class CopyOnWriteList<T> extends AbstractList<T> {
+
+ Object[] data;
+
+ public CopyOnWriteList() {
+ data = new Object[0];
+ }
+
+ public CopyOnWriteList(Collection<T> col) {
+ if (col instanceof CopyOnWriteList) {
+ data = ((CopyOnWriteList) col).data;
+ } else {
+ data = col.toArray(new Object[col.size()]);
+ }
+ }
+
+ @Override
+ public int size() {
+ return data.length;
+ }
+
+ public T get(int index) {
+ return (T) data[index];
+ }
+
+ @Override
+ public T set(int index, T element) {
+ data = Arrays.copyOf(data, data.length);
+ T prev = (T) data[index];
+ data[index] = element;
+ return prev;
+ }
+
+ @Override
+ public void add(int index, T element) {
+ Object[] elements = data;
+ int len = elements.length;
+ Object[] newElements = new Object[len + 1];
+ int numMoved = len - index;
+ if (index > 0) {
+ System.arraycopy(elements, 0, newElements, 0, index);
+ }
+ if (numMoved > 0) {
+ System.arraycopy(elements, index, newElements, index + 1, numMoved);
+ }
+ newElements[index] = element;
+ data = newElements;
+ }
+
+ public T remove(int index) {
+ Object[] elements = data;
+ int len = elements.length;
+ T oldValue = (T) elements[index];
+ Object[] newElements = new Object[len - 1];
+ int numMoved = len - index - 1;
+ if (index > 0) {
+ System.arraycopy(elements, 0, newElements, 0, index);
+ }
+ if (numMoved > 0) {
+ System.arraycopy(elements, index + 1, newElements, index, numMoved);
+ }
+ data = newElements;
+ return oldValue;
+ }
+
+ @Override
+ public int hashCode() {
+ return Arrays.hashCode(data);
+ }
+}
diff --git a/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java b/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java
new file mode 100644
index 0000000..239233b
--- /dev/null
+++ b/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java
@@ -0,0 +1,110 @@
+/*
+ * 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.AbstractSet;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Iterator;
+
+public class CopyOnWriteSet<E> extends AbstractSet<E> {
+
+ Object[] data;
+
+ public CopyOnWriteSet() {
+ data = new Object[0];
+ }
+
+ public CopyOnWriteSet(Collection<E> col) {
+ if (col instanceof CopyOnWriteSet) {
+ data = ((CopyOnWriteSet) col).data;
+ } else {
+ data = col.toArray(new Object[col.size()]);
+ }
+ }
+
+ @Override
+ public Iterator<E> iterator() {
+ return new Iterator<E>() {
+ int idx = 0;
+ public boolean hasNext() {
+ return idx < data.length;
+ }
+ @SuppressWarnings("unchecked")
+ public E next() {
+ return (E) data[idx++];
+ }
+ public void remove() {
+ CopyOnWriteSet.this.remove(--idx);
+ }
+ };
+ }
+
+ @Override
+ public int size() {
+ return data.length;
+ }
+
+ @Override
+ public boolean add(E e) {
+ Object[] d = data;
+ if (d.length == 0) {
+ data = new Object[] {e};
+ } else {
+ for (Object o : d) {
+ if (o == null ? e == null : o.equals(e)) {
+ return false;
+ }
+ }
+ Object[] a = new Object[d.length + 1];
+ System.arraycopy(d, 0, a, 0, d.length);
+ a[d.length] = e;
+ data = a;
+ }
+ return true;
+ }
+
+ private void remove(int index) {
+ Object[] d = data;
+ int len = d.length;
+ Object[] a = new Object[len - 1];
+ int numMoved = len - index - 1;
+ if (index > 0) {
+ System.arraycopy(d, 0, a, 0, index);
+ }
+ if (numMoved > 0) {
+ System.arraycopy(d, index + 1, a, index, numMoved);
+ }
+ data = a;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (o instanceof CopyOnWriteSet && ((CopyOnWriteSet) o).data == data) {
+ return true;
+ }
+ return super.equals(o);
+ }
+
+ @Override
+ public int hashCode() {
+ return Arrays.hashCode(data);
+ }
+
+}
diff --git a/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java b/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java
new file mode 100644
index 0000000..8920a65
--- /dev/null
+++ b/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java
@@ -0,0 +1,621 @@
+/*
+ * 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.AbstractMap;
+import java.util.AbstractSet;
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+/**
+ * An open addressing map.
+ * Low memory consumption compared to a HashMap.
+ *
+ * Based on the mahout collection classes.
+ */
+public class OpenHashMap<K, V> extends AbstractMap<K, V> implements Cloneable {
+
+ static final int[] primeCapacities = {
+ 3, 5, 7, 11, 17, 23, 31, 37, 43, 47, 67, 79, 89, 97, 137, 163, 179, 197, 277, 311,
+ 331, 359, 379, 397, 433, 557, 599, 631, 673, 719, 761, 797, 877, 953, 1039, 1117,
+ 1201, 1277, 1361, 1439, 1523, 1597, 1759, 1907, 2081, 2237, 2411, 2557, 2729, 2879,
+ 3049, 3203, 3527, 3821, 4177, 4481, 4831, 5119, 5471, 5779, 6101, 6421, 7057, 7643,
+ 8363, 8963, 9677, 10243, 10949, 11579, 12203, 12853, 14143, 15287, 16729, 17929,
+ 19373, 20507, 21911, 23159, 24407, 25717, 28289, 30577, 33461, 35863, 38747, 41017,
+ 43853, 46327, 48817, 51437, 56591, 61169, 66923, 71741, 77509, 82037, 87719, 92657,
+ 97649, 102877, 113189, 122347, 133853, 143483, 155027, 164089, 175447, 185323,
+ 195311, 205759, 226379, 244703, 267713, 286973, 310081, 328213, 350899, 370661,
+ 390647, 411527, 452759, 489407, 535481, 573953, 620171, 656429, 701819, 741337,
+ 781301, 823117, 905551, 978821, 1070981, 1147921, 1240361, 1312867, 1403641, 1482707,
+ 1562611, 1646237, 1811107, 1957651, 2141977, 2295859, 2480729, 2625761, 2807303,
+ 2965421, 3125257, 3292489, 3622219, 3915341, 4283963, 4591721, 4961459, 5251529,
+ 5614657, 5930887, 6250537, 6584983, 7244441, 7830701, 8567929, 9183457, 9922933,
+ 10503061, 11229331, 11861791, 12501169, 13169977, 14488931, 15661423, 17135863,
+ 18366923, 19845871, 21006137, 22458671, 23723597, 25002389, 26339969, 28977863,
+ 31322867, 34271747, 36733847, 39691759, 42012281, 44917381, 47447201, 50004791,
+ 52679969, 57955739, 62645741, 68543509, 73467739, 79383533, 84024581, 89834777,
+ 94894427, 100009607, 105359939, 115911563, 125291483, 137087021, 146935499,
+ 158767069, 168049163, 179669557, 189788857, 200019221, 210719881, 231823147,
+ 250582987, 274174111, 293871013, 317534141, 336098327, 359339171, 379577741,
+ 400038451, 421439783, 463646329, 501165979, 548348231, 587742049, 635068283,
+ 672196673, 718678369, 759155483, 800076929, 842879579, 927292699, 1002331963,
+ 1096696463, 1175484103, 1270136683, 1344393353, 1437356741, 1518310967,
+ 1600153859, 1685759167, 1854585413, 2004663929, 2147483647
+ };
+ static final int largestPrime = primeCapacities[primeCapacities.length - 1];
+
+ protected static final int defaultCapacity = 277;
+ protected static final double defaultMinLoadFactor = 0.2;
+ protected static final double defaultMaxLoadFactor = 0.5;
+
+ protected static final Object FREE = null;
+ protected static final Object REMOVED = new Object();
+
+ /** The number of distinct associations in the map; its "size()". */
+ protected int distinct;
+
+ /**
+ * The table capacity c=table.length always satisfies the invariant <tt>c * minLoadFactor <= s <= c *
+ * maxLoadFactor</tt>, where s=size() is the number of associations currently contained. The term "c * minLoadFactor"
+ * is called the "lowWaterMark", "c * maxLoadFactor" is called the "highWaterMark". In other words, the table capacity
+ * (and proportionally the memory used by this class) oscillates within these constraints. The terms are precomputed
+ * and cached to avoid recalculating them each time put(..) or removeKey(...) is called.
+ */
+ protected int lowWaterMark;
+ protected int highWaterMark;
+
+ /** The minimum load factor for the hashtable. */
+ protected double minLoadFactor;
+
+ /** The maximum load factor for the hashtable. */
+ protected double maxLoadFactor;
+
+ /** The hash table keys. */
+ protected Object[] table;
+
+ /** The hash table values. */
+ protected Object[] values;
+
+ /** The number of table entries in state==FREE. */
+ protected int freeEntries;
+
+
+ /** Constructs an empty map with default capacity and default load factors. */
+ public OpenHashMap() {
+ this(defaultCapacity);
+ }
+
+ /**
+ * Constructs an empty map with the specified initial capacity and default load factors.
+ *
+ * @param initialCapacity the initial capacity of the map.
+ * @throws IllegalArgumentException if the initial capacity is less than zero.
+ */
+ public OpenHashMap(int initialCapacity) {
+ this(initialCapacity, defaultMinLoadFactor, defaultMaxLoadFactor);
+ }
+
+ /**
+ * Constructs an empty map with the specified initial capacity and the specified minimum and maximum load factor.
+ *
+ * @param initialCapacity the initial capacity.
+ * @param minLoadFactor the minimum load factor.
+ * @param maxLoadFactor the maximum load factor.
+ * @throws IllegalArgumentException if <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) ||
+ * (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >=
+ * maxLoadFactor)</tt>.
+ */
+ public OpenHashMap(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
+ setUp(initialCapacity, minLoadFactor, maxLoadFactor);
+ }
+
+ /** Removes all (key,value) associations from the receiver. Implicitly calls <tt>trimToSize()</tt>. */
+ @Override
+ public void clear() {
+ Arrays.fill(this.table, FREE);
+ Arrays.fill(this.values, null);
+ distinct = 0;
+ freeEntries = table.length; // delta
+ trimToSize();
+ }
+
+ /**
+ * Returns a deep copy of the receiver.
+ *
+ * @return a deep copy of the receiver.
+ */
+ @Override
+ @SuppressWarnings("unchecked")
+ public OpenHashMap<K, V> clone() {
+ try {
+ OpenHashMap<K,V> copy = (OpenHashMap<K,V>) super.clone();
+ copy.table = copy.table.clone();
+ copy.values = copy.values.clone();
+ return copy;
+ } catch (CloneNotSupportedException exc) {
+ InternalError e = new InternalError();
+ e.initCause(exc);
+ throw e; //should never happen since we are cloneable
+ }
+ }
+
+ /**
+ * Returns <tt>true</tt> if the receiver contains the specified key.
+ *
+ * @return <tt>true</tt> if the receiver contains the specified key.
+ */
+ @SuppressWarnings("unchecked")
+ @Override
+ public boolean containsKey(Object key) {
+ return indexOfKey((K) key) >= 0;
+ }
+
+ /**
+ * Returns <tt>true</tt> if the receiver contains the specified value.
+ *
+ * @return <tt>true</tt> if the receiver contains the specified value.
+ */
+ @SuppressWarnings("unchecked")
+ @Override
+ public boolean containsValue(Object value) {
+ return indexOfValue((V)value) >= 0;
+ }
+
+ /**
+ * Ensures that the receiver can hold at least the specified number of associations without needing to allocate new
+ * internal memory. If necessary, allocates new internal memory and increases the capacity of the receiver. <p> This
+ * method never need be called; it is for performance tuning only. Calling this method before <tt>put()</tt>ing a
+ * large number of associations boosts performance, because the receiver will grow only once instead of potentially
+ * many times and hash collisions get less probable.
+ *
+ * @param minCapacity the desired minimum capacity.
+ */
+ public void ensureCapacity(int minCapacity) {
+ if (table.length < minCapacity) {
+ int newCapacity = nextPrime(minCapacity);
+ rehash(newCapacity);
+ }
+ }
+
+ /**
+ * Returns the value associated with the specified key. It is often a good idea to first check with {@link
+ * #containsKey(Object)} whether the given key has a value associated or not, i.e. whether there exists an association
+ * for the given key or not.
+ *
+ * @param key the key to be searched for.
+ * @return the value associated with the specified key; <tt>0</tt> if no such key is present.
+ */
+ @SuppressWarnings("unchecked")
+ @Override
+ public V get(Object key) {
+ int i = indexOfKey((K)key);
+ if (i < 0) {
+ return null;
+ } //not contained
+ return (V)values[i];
+ }
+
+ /**
+ * @param key the key to be added to the receiver.
+ * @return the index where the key would need to be inserted, if it is not already contained. Returns -index-1 if the
+ * key is already contained at slot index. Therefore, if the returned index < 0, then it is already contained
+ * at slot -index-1. If the returned index >= 0, then it is NOT already contained and should be inserted at
+ * slot index.
+ */
+ protected int indexOfInsertion(K key) {
+ Object[] tab = table;
+ int length = tab.length;
+
+ int hash = key.hashCode() & 0x7FFFFFFF;
+ int i = hash % length;
+ int decrement = hash % (length - 2); // double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
+ //int decrement = (hash / length) % length;
+ if (decrement == 0) {
+ decrement = 1;
+ }
+
+ // stop if we find a removed or free slot, or if we find the key itself
+ // do NOT skip over removed slots (yes, open addressing is like that...)
+ while (table[i] != FREE && table[i] != REMOVED && !equalsMindTheNull(key, tab[i])) {
+ i -= decrement;
+ //hashCollisions++;
+ if (i < 0) {
+ i += length;
+ }
+ }
+
+ if (table[i] == REMOVED) {
+ // stop if we find a free slot, or if we find the key itself.
+ // do skip over removed slots (yes, open addressing is like that...)
+ // assertion: there is at least one FREE slot.
+ int j = i;
+ while (table[i] != FREE && (table[i] == REMOVED || tab[i] != key)) {
+ i -= decrement;
+ //hashCollisions++;
+ if (i < 0) {
+ i += length;
+ }
+ }
+ if (table[i] == FREE) {
+ i = j;
+ }
+ }
+
+
+ if (table[i] != FREE && table[i] != REMOVED) {
+ // key already contained at slot i.
+ // return a negative number identifying the slot.
+ return -i - 1;
+ }
+ // not already contained, should be inserted at slot i.
+ // return a number >= 0 identifying the slot.
+ return i;
+ }
+
+ /**
+ * @param key the key to be searched in the receiver.
+ * @return the index where the key is contained in the receiver, returns -1 if the key was not found.
+ */
+ protected int indexOfKey(K key) {
+ Object[] tab = table;
+ int length = tab.length;
+
+ int hash = key.hashCode() & 0x7FFFFFFF;
+ int i = hash % length;
+ int decrement = hash % (length - 2); // double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
+ //int decrement = (hash / length) % length;
+ if (decrement == 0) {
+ decrement = 1;
+ }
+
+ // stop if we find a free slot, or if we find the key itself.
+ // do skip over removed slots (yes, open addressing is like that...)
+ while (tab[i] != FREE && (tab[i] == REMOVED || !equalsMindTheNull(key, tab[i]))) {
+ i -= decrement;
+ //hashCollisions++;
+ if (i < 0) {
+ i += length;
+ }
+ }
+
+ if (tab[i] == FREE) {
+ return -1;
+ } // not found
+ return i; //found, return index where key is contained
+ }
+
+ /**
+ * @param value the value to be searched in the receiver.
+ * @return the index where the value is contained in the receiver, returns -1 if the value was not found.
+ */
+ protected int indexOfValue(V value) {
+ Object[] val = values;
+
+ for (int i = values.length; --i >= 0;) {
+ if (table[i] != FREE && table[i] != REMOVED && equalsMindTheNull(val[i], value)) {
+ return i;
+ }
+ }
+
+ return -1; // not found
+ }
+
+ /**
+ * Associates the given key with the given value. Replaces any old <tt>(key,someOtherValue)</tt> association, if
+ * existing.
+ *
+ * @param key the key the value shall be associated with.
+ * @param value the value to be associated.
+ * @return <tt>true</tt> if the receiver did not already contain such a key; <tt>false</tt> if the receiver did
+ * already contain such a key - the new value has now replaced the formerly associated value.
+ */
+ @SuppressWarnings("unchecked")
+ @Override
+ public V put(K key, V value) {
+ int i = indexOfInsertion(key);
+ if (i < 0) { //already contained
+ i = -i - 1;
+ V previous = (V) this.values[i];
+ this.values[i] = value;
+ return previous;
+ }
+
+ if (this.distinct > this.highWaterMark) {
+ int newCapacity = chooseGrowCapacity(this.distinct + 1, this.minLoadFactor, this.maxLoadFactor);
+ rehash(newCapacity);
+ return put(key, value);
+ }
+
+ if (this.table[i] == FREE) {
+ this.freeEntries--;
+ }
+ this.table[i] = key;
+ this.values[i] = value;
+ this.distinct++;
+
+ if (this.freeEntries < 1) { //delta
+ int newCapacity = chooseGrowCapacity(this.distinct + 1, this.minLoadFactor, this.maxLoadFactor);
+ rehash(newCapacity);
+ }
+
+ return null;
+ }
+
+ /**
+ * Rehashes the contents of the receiver into a new table with a smaller or larger capacity. This method is called
+ * automatically when the number of keys in the receiver exceeds the high water mark or falls below the low water
+ * mark.
+ */
+ @SuppressWarnings("unchecked")
+ protected void rehash(int newCapacity) {
+ int oldCapacity = table.length;
+ //if (oldCapacity == newCapacity) return;
+
+ Object[] oldTable = table;
+ Object[] oldValues = values;
+
+ Object[] newTable = new Object[newCapacity];
+ Object[] newValues = new Object[newCapacity];
+
+ this.lowWaterMark = chooseLowWaterMark(newCapacity, this.minLoadFactor);
+ this.highWaterMark = chooseHighWaterMark(newCapacity, this.maxLoadFactor);
+
+ this.table = newTable;
+ this.values = newValues;
+ this.freeEntries = newCapacity - this.distinct; // delta
+
+ for (int i = oldCapacity; i-- > 0;) {
+ if (oldTable[i] != FREE && oldTable[i] != REMOVED) {
+ Object element = oldTable[i];
+ int index = indexOfInsertion((K)element);
+ newTable[index] = element;
+ newValues[index] = oldValues[i];
+ }
+ }
+ }
+
+ /**
+ * Removes the given key with its associated element from the receiver, if present.
+ *
+ * @param key the key to be removed from the receiver.
+ * @return <tt>true</tt> if the receiver contained the specified key, <tt>false</tt> otherwise.
+ */
+ @SuppressWarnings("unchecked")
+ @Override
+ public V remove(Object key) {
+ int i = indexOfKey((K)key);
+ if (i < 0) {
+ return null;
+ }
+ // key not contained
+ V removed = (V) values[i];
+
+ this.table[i] = REMOVED;
+ this.values[i] = null;
+ this.distinct--;
+
+ if (this.distinct < this.lowWaterMark) {
+ int newCapacity = chooseShrinkCapacity(this.distinct, this.minLoadFactor, this.maxLoadFactor);
+ rehash(newCapacity);
+ }
+
+ return removed;
+ }
+
+ /**
+ * Initializes the receiver.
+ *
+ * @param initialCapacity the initial capacity of the receiver.
+ * @param minLoadFactor the minLoadFactor of the receiver.
+ * @param maxLoadFactor the maxLoadFactor of the receiver.
+ * @throws IllegalArgumentException if <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) ||
+ * (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >=
+ * maxLoadFactor)</tt>.
+ */
+ protected void setUp(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
+ if (initialCapacity < 0) {
+ throw new IllegalArgumentException("Initial Capacity must not be less than zero: " + initialCapacity);
+ }
+ if (minLoadFactor < 0.0 || minLoadFactor >= 1.0) {
+ throw new IllegalArgumentException("Illegal minLoadFactor: " + minLoadFactor);
+ }
+ if (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) {
+ throw new IllegalArgumentException("Illegal maxLoadFactor: " + maxLoadFactor);
+ }
+ if (minLoadFactor >= maxLoadFactor) {
+ throw new IllegalArgumentException(
+ "Illegal minLoadFactor: " + minLoadFactor + " and maxLoadFactor: " + maxLoadFactor);
+ }
+ int capacity = initialCapacity;
+ capacity = nextPrime(capacity);
+ if (capacity == 0) {
+ capacity = 1;
+ } // open addressing needs at least one FREE slot at any time.
+
+ this.table = new Object[capacity];
+ this.values = new Object[capacity];
+
+ // memory will be exhausted long before this pathological case happens, anyway.
+ this.minLoadFactor = minLoadFactor;
+ if (capacity == largestPrime) {
+ this.maxLoadFactor = 1.0;
+ } else {
+ this.maxLoadFactor = maxLoadFactor;
+ }
+
+ this.distinct = 0;
+ this.freeEntries = capacity; // delta
+
+ // lowWaterMark will be established upon first expansion.
+ // establishing it now (upon instance construction) would immediately make the table shrink upon first put(...).
+ // After all the idea of an "initialCapacity" implies violating lowWaterMarks when an object is young.
+ // See ensureCapacity(...)
+ this.lowWaterMark = 0;
+ this.highWaterMark = chooseHighWaterMark(capacity, this.maxLoadFactor);
+ }
+
+ /**
+ * Trims the capacity of the receiver to be the receiver's current size. Releases any superfluous internal memory. An
+ * application can use this operation to minimize the storage of the receiver.
+ */
+ public void trimToSize() {
+ // * 1.2 because open addressing's performance exponentially degrades beyond that point
+ // so that even rehashing the table can take very long
+ int newCapacity = nextPrime((int) (1 + 1.2 * size()));
+ if (table.length > newCapacity) {
+ rehash(newCapacity);
+ }
+ }
+
+ public void concat() {
+ int newCap = nextPrime(size() + 1); // +1 as we always need a free slot
+ if (newCap != table.length) {
+ rehash(newCap);
+ }
+ }
+
+ /**
+ * Allocate a set to contain Map.Entry objects for the pairs and return it.
+ */
+ @Override
+ public Set<Entry<K,V>> entrySet() {
+ return new EntrySet();
+ }
+
+ /**
+ * Chooses a new prime table capacity optimized for growing that (approximately) satisfies the invariant <tt>c *
+ * minLoadFactor <= size <= c * maxLoadFactor</tt> and has at least one FREE slot for the given size.
+ */
+ protected int chooseGrowCapacity(int size, double minLoad, double maxLoad) {
+ return nextPrime(Math.max(size + 1, (int) ((4 * size / (3 * minLoad + maxLoad)))));
+ }
+
+ /**
+ * Returns new high water mark threshold based on current capacity and maxLoadFactor.
+ *
+ * @return int the new threshold.
+ */
+ protected int chooseHighWaterMark(int capacity, double maxLoad) {
+ return Math.min(capacity - 2, (int) (capacity * maxLoad)); //makes sure there is always at least one FREE slot
+ }
+
+ /**
+ * Returns new low water mark threshold based on current capacity and minLoadFactor.
+ *
+ * @return int the new threshold.
+ */
+ protected int chooseLowWaterMark(int capacity, double minLoad) {
+ return (int) (capacity * minLoad);
+ }
+
+ /**
+ * Chooses a new prime table capacity optimized for shrinking that (approximately) satisfies the invariant <tt>c *
+ * minLoadFactor <= size <= c * maxLoadFactor</tt> and has at least one FREE slot for the given size.
+ */
+ protected int chooseShrinkCapacity(int size, double minLoad, double maxLoad) {
+ return nextPrime(Math.max(size + 1, (int) ((4 * size / (minLoad + 3 * maxLoad)))));
+ }
+
+ /**
+ * Returns a prime number which is <code>>= desiredCapacity</code> and very close to <code>desiredCapacity</code>
+ * (within 11% if <code>desiredCapacity >= 1000</code>).
+ *
+ * @param desiredCapacity the capacity desired by the user.
+ * @return the capacity which should be used for a hashtable.
+ */
+ protected int nextPrime(int desiredCapacity) {
+ int i = java.util.Arrays.binarySearch(primeCapacities, desiredCapacity);
+ if (i < 0) {
+ // desired capacity not found, choose next prime greater than desired capacity
+ i = -i - 1; // remember the semantics of binarySearch...
+ }
+ return primeCapacities[i];
+ }
+
+ /**
+ * Returns the number of (key,value) associations currently contained.
+ *
+ * @return the number of (key,value) associations currently contained.
+ */
+ public int size() {
+ return distinct;
+ }
+
+ protected static boolean equalsMindTheNull(Object a, Object b) {
+ if (a == null && b == null) {
+ return true;
+ }
+ if (a == null || b == null) {
+ return false;
+ }
+ return a.equals(b);
+ }
+
+ private class EntrySet extends AbstractSet<Entry<K, V>> {
+ @Override
+ public Iterator<Entry<K, V>> iterator() {
+ return new EntrySetIterator();
+ }
+
+ @Override
+ public int size() {
+ return OpenHashMap.this.size();
+ }
+ }
+
+ private class EntrySetIterator implements Iterator<Entry<K, V>> {
+ int idx = -1;
+ Entry<K,V> next;
+
+ EntrySetIterator() {
+ forward();
+ }
+
+ @SuppressWarnings("unchecked")
+ private void forward() {
+ next = null;
+ while (next == null && ++idx < table.length) {
+ if (table[idx] != FREE && table[idx] != REMOVED) {
+ next = new SimpleImmutableEntry<K, V>((K) table[idx], (V) values[idx]);
+ }
+ }
+ }
+
+ public boolean hasNext() {
+ return next != null;
+ }
+
+ public Entry<K, V> next() {
+ if (next == null) {
+ throw new NoSuchElementException();
+ }
+ Entry<K,V> n = next;
+ forward();
+ return n;
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+
+ }
+
+}
diff --git a/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java b/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java
new file mode 100644
index 0000000..54d7da1
--- /dev/null
+++ b/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java
@@ -0,0 +1,45 @@
+/*
+ * 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;
+
+public class OpenHashMapList<K, V> extends OpenHashMap<K, CopyOnWriteList<V>> {
+
+ public OpenHashMapList() {
+ super();
+ }
+
+ public OpenHashMapList(int initialCapacity) {
+ super(initialCapacity);
+ }
+
+ public OpenHashMapList(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
+ super(initialCapacity, minLoadFactor, maxLoadFactor);
+ }
+
+ public OpenHashMapList<K, V> deepClone() {
+ OpenHashMapList<K, V> copy = (OpenHashMapList<K, V>) super.clone();
+ Object[] values = copy.values;
+ for (int i = 0, l = values.length; i < l; i++) {
+ if (values[i] != null) {
+ values[i] = new CopyOnWriteList<V>((CopyOnWriteList<V>) values[i]);
+ }
+ }
+ return copy;
+ }
+}
diff --git a/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java b/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java
new file mode 100644
index 0000000..60a1c98
--- /dev/null
+++ b/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java
@@ -0,0 +1,45 @@
+/*
+ * 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;
+
+public class OpenHashMapSet<K, V> extends OpenHashMap<K, CopyOnWriteSet<V>> {
+
+ public OpenHashMapSet() {
+ super();
+ }
+
+ public OpenHashMapSet(int initialCapacity) {
+ super(initialCapacity);
+ }
+
+ public OpenHashMapSet(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
+ super(initialCapacity, minLoadFactor, maxLoadFactor);
+ }
+
+ public OpenHashMapSet<K, V> deepClone() {
+ OpenHashMapSet<K, V> copy = (OpenHashMapSet<K, V>) super.clone();
+ Object[] values = copy.values;
+ for (int i = 0, l = values.length; i < l; i++) {
+ if (values[i] != null) {
+ values[i] = new CopyOnWriteSet<V>((CopyOnWriteSet<V>) values[i]);
+ }
+ }
+ return copy;
+ }
+}
diff --git a/resolver/src/main/java/org/apache/felix/resolver/util/ShadowList.java b/resolver/src/main/java/org/apache/felix/resolver/util/ShadowList.java
new file mode 100644
index 0000000..52335fa
--- /dev/null
+++ b/resolver/src/main/java/org/apache/felix/resolver/util/ShadowList.java
@@ -0,0 +1,40 @@
+/*
+ * 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.List;
+
+import org.apache.felix.resolver.util.CopyOnWriteList;
+
+public class ShadowList<T> extends CopyOnWriteList<T>
+{
+ private final List<T> m_original;
+
+ public ShadowList(List<T> original)
+ {
+ super(original);
+ m_original = original;
+ }
+
+ public List<T> getOriginal()
+ {
+ return m_original;
+ }
+
+}
\ No newline at end of file