felix-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From gno...@apache.org
Subject svn commit: r1667213 - in /felix/trunk/resolver/src/main/java/org/apache/felix/resolver: ./ util/
Date Tue, 17 Mar 2015 09:38:08 GMT
Author: gnodet
Date: Tue Mar 17 09:38:07 2015
New Revision: 1667213

URL: http://svn.apache.org/r1667213
Log:
[FELIX-4656] Use more efficient data structures

Added:
    felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/
    felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java
    felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java
    felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java
    felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java
    felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java
    felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/ShadowList.java
Removed:
    felix/trunk/resolver/src/main/java/org/apache/felix/resolver/ShadowList.java
Modified:
    felix/trunk/resolver/src/main/java/org/apache/felix/resolver/Candidates.java

Modified: felix/trunk/resolver/src/main/java/org/apache/felix/resolver/Candidates.java
URL: http://svn.apache.org/viewvc/felix/trunk/resolver/src/main/java/org/apache/felix/resolver/Candidates.java?rev=1667213&r1=1667212&r2=1667213&view=diff
==============================================================================
--- felix/trunk/resolver/src/main/java/org/apache/felix/resolver/Candidates.java (original)
+++ felix/trunk/resolver/src/main/java/org/apache/felix/resolver/Candidates.java Tue Mar 17
09:38:07 2015
@@ -29,6 +29,13 @@ import java.util.Map;
 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 @@ class Candidates
 
     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 @@ class Candidates
      */
     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 @@ class Candidates
     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 @@ class Candidates
         }
 
         // Record the candidates.
-        m_candidateMap.put(req, candidates);
+        m_candidateMap.put(req, new CopyOnWriteList<Capability>(candidates));
     }
 
     /**
@@ -929,10 +936,10 @@ class Candidates
                     // 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 @@ class Candidates
                             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 @@ class Candidates
                             // 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 @@ class Candidates
                 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 @@ class Candidates
         }
 
         populateSubstitutables();
+
+        m_candidateMap.concat();
+        m_dependentMap.concat();
     }
 
     // Maps a host capability to a map containing its potential fragments;
@@ -1043,17 +1052,17 @@ class Candidates
     {
         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 @@ class Candidates
      */
     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());

Added: felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java
URL: http://svn.apache.org/viewvc/felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java?rev=1667213&view=auto
==============================================================================
--- felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java
(added)
+++ felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java
Tue Mar 17 09:38:07 2015
@@ -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);
+    }
+}

Added: felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java
URL: http://svn.apache.org/viewvc/felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java?rev=1667213&view=auto
==============================================================================
--- felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java
(added)
+++ felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java
Tue Mar 17 09:38:07 2015
@@ -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);
+    }
+
+}

Added: felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java
URL: http://svn.apache.org/viewvc/felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java?rev=1667213&view=auto
==============================================================================
--- felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java (added)
+++ felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java Tue
Mar 17 09:38:07 2015
@@ -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>&gt;= desiredCapacity</code>
and very close to <code>desiredCapacity</code>
+     * (within 11% if <code>desiredCapacity &gt;= 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();
+        }
+
+    }
+
+}

Added: felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java
URL: http://svn.apache.org/viewvc/felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java?rev=1667213&view=auto
==============================================================================
--- felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java
(added)
+++ felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java
Tue Mar 17 09:38:07 2015
@@ -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;
+    }
+}

Added: felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java
URL: http://svn.apache.org/viewvc/felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java?rev=1667213&view=auto
==============================================================================
--- felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java
(added)
+++ felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java
Tue Mar 17 09:38:07 2015
@@ -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;
+    }
+}

Added: felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/ShadowList.java
URL: http://svn.apache.org/viewvc/felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/ShadowList.java?rev=1667213&view=auto
==============================================================================
--- felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/ShadowList.java (added)
+++ felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/ShadowList.java Tue
Mar 17 09:38:07 2015
@@ -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



Mime
View raw message