jackrabbit-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ang...@apache.org
Subject svn commit: r518926 - in /jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype: BitsetENTCacheImpl.java DefinitionValidator.java EffectiveNodeTypeCache.java EffectiveNodeTypeImpl.java NodeTypeRegistryImpl.java
Date Fri, 16 Mar 2007 10:28:57 GMT
Author: angela
Date: Fri Mar 16 03:28:55 2007
New Revision: 518926

URL: http://svn.apache.org/viewvc?view=rev&rev=518926
Log:
- sync (effective node type cache)
- loading of node types that have a reference to each other failed.

Added:
    jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/BitsetENTCacheImpl.java
  (with props)
Modified:
    jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/DefinitionValidator.java
    jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/EffectiveNodeTypeCache.java
    jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/EffectiveNodeTypeImpl.java
    jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/NodeTypeRegistryImpl.java

Added: jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/BitsetENTCacheImpl.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/BitsetENTCacheImpl.java?view=auto&rev=518926
==============================================================================
--- jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/BitsetENTCacheImpl.java
(added)
+++ jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/BitsetENTCacheImpl.java
Fri Mar 16 03:28:55 2007
@@ -0,0 +1,490 @@
+/*
+ * 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.jackrabbit.jcr2spi.nodetype;
+
+import org.apache.jackrabbit.name.QName;
+
+import java.util.TreeSet;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.ArrayList;
+import java.io.PrintStream;
+
+import EDU.oswego.cs.dl.util.concurrent.ConcurrentReaderHashMap;
+
+/**
+ * Implements an effective node type cache that uses a bit set for storing the
+ * information about participating node types in a set.
+ */
+class BitsetENTCacheImpl implements EffectiveNodeTypeCache {
+
+    /**
+     * constant for bits-per-word
+     */
+    private static final int BPW = 64;
+
+    /**
+     * OR mask for bit set
+     */
+    private static final long[] OR_MASK = new long[BPW];
+    static {
+        for (int i=0; i<BPW; i++) {
+            OR_MASK[i] = 1L << i;
+        }
+    }
+
+    /**
+     * An ordered set of the keys. This is used for {@link #findBest(Key)}.
+     */
+    private final TreeSet sortedKeys;
+
+    /**
+     * cache of pre-built aggregations of node types
+     */
+    private final HashMap aggregates;
+
+    /**
+     * A lookup table for bit numbers for a given name.
+     *
+     * Note: further performance improvements could be made if this index would
+     * be stored in the node type registry since only registered node type names
+     * are allowed in the keys.
+     */
+    private final ConcurrentReaderHashMap nameIndex = new ConcurrentReaderHashMap();
+
+    /**
+     * The reverse lookup table for bit numbers to names
+     */
+    private QName[] names = new QName[1024];
+
+    /**
+     * Creates a new bitset effective node type cache
+     */
+    BitsetENTCacheImpl() {
+        sortedKeys = new TreeSet();
+        aggregates = new HashMap();
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public Key getKey(QName[] ntNames) {
+        return new BitsetKey(ntNames, nameIndex.size() + ntNames.length);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public void put(EffectiveNodeType ent) {
+        put(getKey(ent.getMergedNodeTypes()), ent);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public void put(Key key, EffectiveNodeType ent) {
+        aggregates.put(key, ent);
+        sortedKeys.add(key);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public Key findBest(Key key) {
+        // quick check for already cached key
+        if (contains(key)) {
+            return key;
+        }
+        Iterator iter = sortedKeys.iterator();
+        while (iter.hasNext()) {
+            Key k = (Key) iter.next();
+            if (key.contains(k)) {
+                return k;
+            }
+        }
+        return null;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public void invalidate(QName name) {
+        /**
+         * remove all affected effective node types from aggregates cache
+         * (copy keys first to prevent ConcurrentModificationException)
+         */
+        ArrayList keys = new ArrayList(aggregates.keySet());
+        for (Iterator keysIter = keys.iterator(); keysIter.hasNext();) {
+            Key k = (Key) keysIter.next();
+            EffectiveNodeType ent = get(k);
+            if (ent.includesNodeType(name)) {
+                remove(k);
+            }
+        }
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean contains(Key key) {
+        return aggregates.containsKey(key);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public EffectiveNodeType get(Key key) {
+        return (EffectiveNodeType) aggregates.get(key);
+    }
+
+    /**
+     * Returns the bit number for the given name. If the name does not exist
+     * a new new bit number for that name is created.
+     *
+     * @param name the name to lookup
+     * @return the bit number for the given name
+     */
+    private int getBitNumber(QName name) {
+        Integer i = (Integer) nameIndex.get(name);
+        if (i == null) {
+            synchronized (nameIndex) {
+                i = (Integer) nameIndex.get(name);
+                if (i == null) {
+                    int idx = nameIndex.size();
+                    i = new Integer(idx);
+                    nameIndex.put(name, i);
+                    if (idx >= names.length) {
+                        QName[] newNames = new QName[names.length*2];
+                        System.arraycopy(names, 0, newNames, 0, names.length);
+                        names = newNames;
+                    }
+                    names[idx] = name;
+                }
+            }
+        }
+        return i.intValue();
+    }
+
+    /**
+     * Returns the node type name for a given bit number.
+     * @param n the bit number to lookup
+     * @return the node type name
+     */
+    private QName getName(int n) {
+        return names[n];
+    }
+
+    /**
+     * Removes the effective node type for the given key from the cache.
+     *
+     * @param key the key of the effective node type to remove
+     * @return the removed effective node type or <code>null</code> if it was
+     *         never cached.
+     */
+    private EffectiveNodeType remove(Key key) {
+        EffectiveNodeType removed = (EffectiveNodeType) aggregates.remove(key);
+        if (removed != null) {
+            // other than the original implementation, the weights in the
+            // treeset are now the same as in the given keys. so we can use
+            // the normal remove method
+            sortedKeys.remove(key);
+        }
+        return removed;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public Object clone() {
+        BitsetENTCacheImpl clone = new BitsetENTCacheImpl();
+        clone.sortedKeys.addAll(sortedKeys);
+        clone.aggregates.putAll(aggregates);
+        clone.names = new QName[names.length];
+        System.arraycopy(names, 0, clone.names, 0, names.length);
+        clone.nameIndex.putAll(nameIndex);
+        return clone;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public void dump(PrintStream ps) {
+        ps.println("EffectiveNodeTypeCache (" + this + ")");
+        ps.println();
+        ps.println("EffectiveNodeTypes in cache:");
+        ps.println();
+        Iterator iter = sortedKeys.iterator();
+        while (iter.hasNext()) {
+            Key k = (Key) iter.next();
+            //EffectiveNodeType ent = (EffectiveNodeType) aggregates.get(k);
+            ps.println(k);
+        }
+    }
+
+    /**
+     * Implements a {@link Key} by storing the node type aggregate information
+     * in a bit set. We do not use the {@link java.util.BitSet} because it
+     * does not suite all our needs. Every node type is represented by a bit
+     * in the set. This key is immutable.
+     */
+    private class BitsetKey implements Key {
+
+        /**
+         * The names of the node types that form this key.
+         */
+        private final QName[] names;
+
+        /**
+         * The array of longs that hold the bit information.
+         */
+        private final long[] bits;
+
+        /**
+         * the hashcode, only calculated once
+         */
+        private final int hashCode;
+
+        /**
+         * Creates a ew bitset key.
+         * @param names the node type names
+         * @param maxBit the approximative number of the geatest bit
+         */
+        public BitsetKey(QName[] names, int maxBit) {
+            this.names = names;
+            bits = new long[maxBit/BPW+1];
+
+            for (int i=0; i<names.length; i++) {
+                int n = getBitNumber(names[i]);
+                bits[n/BPW] |= OR_MASK[n%BPW];
+            }
+            hashCode = calcHashCode();
+        }
+
+        /**
+         * Creates new bitset key.
+         * @param bits the array if bits
+         * @param numBits the number of bits that are '1' in the given bis
+         */
+        private BitsetKey(long[] bits, int numBits) {
+            this.bits = bits;
+            names = new QName[numBits];
+            int i = nextSetBit(0);
+            int j=0;
+            while (i >= 0) {
+                names[j++] = BitsetENTCacheImpl.this.getName(i);
+                i = nextSetBit(i+1);
+            }
+            hashCode = calcHashCode();
+        }
+
+        /**
+         * {@inheritDoc}
+         */
+        public QName[] getNames() {
+            return names;
+        }
+
+        /**
+         * {@inheritDoc}
+         */
+        public boolean contains(Key otherKey) {
+            /*
+             * 0 - 0 => 0
+             * 0 - 1 => 1
+             * 1 - 0 => 0
+             * 1 - 1 => 0
+             * !a and b
+             */
+            BitsetKey other = (BitsetKey) otherKey;
+            int len = Math.max(bits.length, other.bits.length);
+            for (int i=0; i<len; i++) {
+                long w1 = i < bits.length ? bits[i] : 0;
+                long w2 = i < other.bits.length ? other.bits[i] : 0;
+                long r = ~w1 & w2;
+                if (r != 0) {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        /**
+         * {@inheritDoc}
+         */
+        public Key subtract(Key otherKey) {
+            /*
+             * 0 - 0 => 0
+             * 0 - 1 => 0
+             * 1 - 0 => 1
+             * 1 - 1 => 0
+             * a and !b
+             */
+            BitsetKey other = (BitsetKey) otherKey;
+            int len = Math.max(bits.length, other.bits.length);
+            long[] newBits = new long[len];
+            int numBits = 0;
+            for (int i=0; i<len; i++) {
+                long w1 = i < bits.length ? bits[i] : 0;
+                long w2 = i < other.bits.length ? other.bits[i] : 0;
+                newBits[i] = w1 & ~w2;
+                numBits += bitCount(newBits[i]);
+            }
+            return new BitsetKey(newBits, numBits);
+        }
+
+        /**
+         * Returns the bit number of the next bit that is set, starting at
+         * <code>fromIndex</code> inclusieve.
+         *
+         * @param fromIndex the bit position to start the search
+         * @return the bit position of the bit or -1 if none found.
+         */
+        private int nextSetBit(int fromIndex) {
+            int addr = fromIndex/BPW;
+            int off = fromIndex%BPW;
+            while (addr < bits.length) {
+                if (bits[addr] != 0) {
+                    while (off < BPW) {
+                        if ((bits[addr] & OR_MASK[off]) != 0) {
+                            return addr * BPW + off;
+                        }
+                        off++;
+                    }
+                    off=0;
+                }
+                addr++;
+            }
+            return -1;
+        }
+
+         /**
+          * Returns the number of bits set in val.
+          * For a derivation of this algorithm, see
+          * "Algorithms and data structures with applications to
+          *  graphics and geometry", by Jurg Nievergelt and Klaus Hinrichs,
+          *  Prentice Hall, 1993.
+          *
+          * @param val the value to calculate the bit count for
+          * @return the number of '1' bits in the value
+          */
+         private int bitCount(long val) {
+             val -= (val & 0xaaaaaaaaaaaaaaaaL) >>> 1;
+             val =  (val & 0x3333333333333333L) + ((val >>> 2) & 0x3333333333333333L);
+             val =  (val + (val >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
+             val += val >>> 8;
+             val += val >>> 16;
+             return ((int)(val) + (int)(val >>> 32)) & 0xff;
+         }
+
+
+        /**
+         * {@inheritDoc}
+         *
+         * This compares 1. the cardinailty (number of set bits) and 2. the
+         * nummeric value of the bitsets in descending order.
+         */
+        public int compareTo(Object other) {
+            BitsetKey o = (BitsetKey) other;
+            int res = o.names.length - names.length;
+            if (res == 0) {
+                int adr = Math.max(bits.length, o.bits.length) - 1;
+                while (adr >= 0) {
+                    long w1 = adr<bits.length ? bits[adr] : 0;
+                    long w2 = adr<o.bits.length ? o.bits[adr] : 0;
+                    if (w1 != w2) {
+                        // some signed arithmetic here
+                        long h1 = w1 >>> 32;
+                        long h2 = w2 >>> 32;
+                        if (h1 == h2) {
+                            h1 = w1 & 0x0ffffL;
+                            h2 = w2 & 0x0ffffL;
+                        }
+                        return (int) (h2-h1);
+                    }
+                    adr--;
+                }
+            }
+            return res;
+        }
+
+        /**
+         * {@inheritDoc}
+         */
+        public boolean equals(Object obj) {
+            if (this == obj) {
+                return true;
+            }
+            if (obj instanceof BitsetKey) {
+                BitsetKey o = (BitsetKey) obj;
+                if (names.length != o.names.length) {
+                    return false;
+                }
+                int adr = Math.max(bits.length, o.bits.length) - 1;
+                while (adr >= 0) {
+                    long w1 = adr<bits.length ? bits[adr] : 0;
+                    long w2 = adr<o.bits.length ? o.bits[adr] : 0;
+                    if (w1 != w2) {
+                        return false;
+                    }
+                    adr--;
+                }
+                return true;
+            }
+            return false;
+        }
+
+        /**
+         * {@inheritDoc}
+         */
+        public int hashCode() {
+            return hashCode;
+        }
+
+        /**
+         * Calculates the hashcode.
+         * @return the calculated hashcode
+         */
+        private int calcHashCode() {
+            long h = 1234;
+            int addr = bits.length -1;
+            while (addr >=0 && bits[addr] == 0) {
+                addr--;
+            }
+            while (addr >=0) {
+                h ^= bits[addr] * (addr + 1);
+                addr--;
+            }
+            return (int)((h >> 32) ^ h);
+        }
+
+        /**
+         * {@inheritDoc}
+         */
+        public String toString() {
+            StringBuffer buf = new StringBuffer("w=");
+            buf.append(names.length);
+            int i = nextSetBit(0);
+            while (i>=0) {
+                buf.append(", ").append(i).append("=");
+                buf.append(BitsetENTCacheImpl.this.getName(i));
+                i = nextSetBit(i+1);
+            }
+            return buf.toString();
+        }
+
+    }
+}
\ No newline at end of file

Propchange: jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/BitsetENTCacheImpl.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/BitsetENTCacheImpl.java
------------------------------------------------------------------------------
    svn:keywords = author date id revision url

Modified: jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/DefinitionValidator.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/DefinitionValidator.java?view=diff&rev=518926&r1=518925&r2=518926
==============================================================================
--- jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/DefinitionValidator.java
(original)
+++ jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/DefinitionValidator.java
Fri Mar 16 03:28:55 2007
@@ -64,7 +64,12 @@
     public Map validateNodeTypeDefs(Collection ntDefs, Map validatedDefs)
         throws InvalidNodeTypeDefException, RepositoryException {
         // tmp. map containing names/defs of validated nodetypes
-        Map validDefs = new HashMap(validatedDefs);
+        Map tmpMap = new HashMap(validatedDefs);
+        for (Iterator it = ntDefs.iterator(); it.hasNext();) {
+            QNodeTypeDefinition ntd = (QNodeTypeDefinition) it.next();
+            tmpMap.put(ntd.getQName(), ntd);
+        }
+
         // map of nodetype definitions and effective nodetypes to be registered
         Map ntMap = new HashMap();
         ArrayList list = new ArrayList(ntDefs);
@@ -80,12 +85,9 @@
                 QNodeTypeDefinition ntd = (QNodeTypeDefinition) iterator.next();
                 // check if definition has unresolved dependencies
                 /* Note: don't compared to 'registered' nodetypes since registr. is performed
later on */
-                if (validDefs.keySet().containsAll(ntd.getDependencies())) {
-                    EffectiveNodeType ent = validateNodeTypeDef(ntd, validDefs);
-                    // keep track of validated definitions and eff. nodetypes
-                    if (!validDefs.containsKey(ntd.getQName())) {
-                        validDefs.put(ntd.getQName(), ntd);
-                    }
+                Collection dependencies = ntd.getDependencies();
+                if (tmpMap.keySet().containsAll(dependencies)) {
+                    EffectiveNodeType ent = validateNodeTypeDef(ntd, tmpMap);
                     ntMap.put(ntd, ent);
                     // remove it from list
                     iterator.remove();

Modified: jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/EffectiveNodeTypeCache.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/EffectiveNodeTypeCache.java?view=diff&rev=518926&r1=518925&r2=518926
==============================================================================
--- jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/EffectiveNodeTypeCache.java
(original)
+++ jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/EffectiveNodeTypeCache.java
Fri Mar 16 03:28:55 2007
@@ -16,297 +16,109 @@
  */
 package org.apache.jackrabbit.jcr2spi.nodetype;
 
-import org.apache.jackrabbit.jcr2spi.util.Dumpable;
 import org.apache.jackrabbit.name.QName;
-
-import java.io.PrintStream;
-import java.util.HashMap;
-import java.util.Iterator;
-import java.util.TreeSet;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.Set;
-import java.util.Arrays;
-import java.util.HashSet;
+import org.apache.jackrabbit.jcr2spi.util.Dumpable;
 
 /**
- * <code>EffectiveNodeTypeCache</code> ...
+ * <code>EffectiveNodeTypeCache</code> defines the interface for a cache for
+ * effective node types. Effective node types are addressed by {@link Key}s.
  */
-class EffectiveNodeTypeCache implements Cloneable, Dumpable {
+public interface EffectiveNodeTypeCache extends Cloneable, Dumpable {
+
     /**
-     * ordered set of keys
+     * Puts an effective node type to the cache. The key is internally generated
+     * from the set of merged node types.
+     * @param ent the effective node type to put to the cache
      */
-    final TreeSet sortedKeys;
+    void put(EffectiveNodeType ent);
+
     /**
-     * cache of pre-built aggregations of node types
+     * Puts an effective node type to the cache for the given key.
+     * @param key the key for the effective node type
+     * @param ent the effective node type to put to the cache
      */
-    final HashMap aggregates;
-
-    EffectiveNodeTypeCache() {
-        sortedKeys = new TreeSet();
-        aggregates = new HashMap();
-    }
-
-    void put(EffectiveNodeType ent) {
-        // we define the weight as the total number of included node types
-        // (through aggregation and inheritance)
-        int weight = ent.getAllNodeTypes().length;
-        // the effective node type is identified by the list of merged
-        // (i.e. aggregated) node types
-        WeightedKey k = new WeightedKey(ent.getMergedNodeTypes(), weight);
-        aggregates.put(k, ent);
-        sortedKeys.add(k);
-    }
-
-    boolean contains(QName[] ntNames) {
-        return aggregates.containsKey(new WeightedKey(ntNames));
-    }
-
-    boolean contains(WeightedKey key) {
-        return aggregates.containsKey(key);
-    }
+    void put(Key key, EffectiveNodeType ent);
 
-    EffectiveNodeType get(QName[] ntNames) {
-        return (EffectiveNodeType) aggregates.get(new WeightedKey(ntNames));
-    }
-
-    EffectiveNodeType get(WeightedKey key) {
-        return (EffectiveNodeType) aggregates.get(key);
-    }
-
-    EffectiveNodeType remove(QName[] ntNames) {
-        return remove(new WeightedKey(ntNames));
-    }
-
-    EffectiveNodeType remove(WeightedKey key) {
-        EffectiveNodeType removed = (EffectiveNodeType) aggregates.remove(key);
-        if (removed != null) {
-            // remove index entry
-
-            // FIXME: can't simply call TreeSet.remove(key) because the entry
-            // in sortedKeys might have a different weight and would thus
-            // not be found
-            Iterator iter = sortedKeys.iterator();
-            while (iter.hasNext()) {
-                WeightedKey k = (WeightedKey) iter.next();
-                // WeightedKey.equals(Object) ignores the weight
-                if (key.equals(k)) {
-                    sortedKeys.remove(k);
-                    break;
-                }
-            }
-        }
-        return removed;
-    }
+    /**
+     * Checks if the effective node type for the given key exists.
+     * @param key the key to check
+     * @return <code>true</code> if the effective node type is cached;
+     *         <code>false</code> otherwise.
+     */
+    boolean contains(Key key);
 
     /**
-     * Returns an iterator over the keys. The order of the returned keys is:
-     * <ol>
-     * <li>descending weight</li>
-     * <li>ascending key (i.e. unique identifier of aggregate)</li>
-     * </ol>
-     *
-     * @see WeightedKey#compareTo
+     * Returns the effective node type for the given key or <code>null</code>
if
+     * the desired node type is not cached.
+     * @param key the key for the effective node type.
+     * @return the effective node type or <code>null</code>
      */
-    Iterator keyIterator() {
-        return sortedKeys.iterator();
-    }
+    EffectiveNodeType get(Key key);
 
     /**
-     * Returns the set of keys.
-     *
-     * @return the set of keys.
+     * Returns a key for an effective node type that consists of the given
+     * node type names.
+     * @param ntNames the array of node type names for the effective node type
+     * @return the key to an effective node type.
      */
-    Set keySet() {
-        return Collections.unmodifiableSet(sortedKeys);
-    }
+    Key getKey(QName[] ntNames);
 
-    //-------------------------------------------< java.lang.Object overrides >
-    public Object clone() {
-        EffectiveNodeTypeCache clone = new EffectiveNodeTypeCache();
-        clone.sortedKeys.addAll(sortedKeys);
-        clone.aggregates.putAll(aggregates);
-        return clone;
-    }
+    /**
+     * Removes all effective node types that are aggregated with the node type
+     * of the given name.
+     * @param name the name of the node type.
+     */
+    void invalidate(QName name);
 
-    //-------------------------------------------------------------< Dumpable >
     /**
      * {@inheritDoc}
      */
-    public void dump(PrintStream ps) {
-        ps.println("EffectiveNodeTypeCache (" + this + ")");
-        ps.println();
-        ps.println("EffectiveNodeTypes in cache:");
-        ps.println();
-        Iterator iter = sortedKeys.iterator();
-        while (iter.hasNext()) {
-            WeightedKey k = (WeightedKey) iter.next();
-            //EffectiveNodeType ent = (EffectiveNodeType) aggregates.get(k);
-            ps.println(k);
-        }
-    }
+    Object clone();
 
-    //--------------------------------------------------------< inner classes >
     /**
-     * A <code>WeightedKey</code> uniquely identifies
-     * a combination (i.e. an aggregation) of one or more node types.
-     * The weight is an indicator for the cost involved in building such an
-     * aggregate (e.g. an aggregation of multiple complex node types with deep
-     * inheritance trees is more costly to build/validate than an agreggation
-     * of two very simple node types with just one property definition each).
-     * <p/>
-     * A very simple (and not very accurate) approximation of the weight would
-     * be the number of explicitly aggregated node types (ignoring inheritance
-     * and complexity of each involved node type). A better approximation would
-     * be the number of <b>all</b>, explicitly and implicitly (note that
-     * inheritance is also an aggregation) aggregated node types.
-     * <p/>
-     * The more accurate the weight definition, the more efficient is the
-     * the building of new aggregates.
-     * <p/>
-     * It is important to note that the weight is not part of the key value,
-     * i.e. it is not considered by the <code>hashCode()</code> and
-     * <code>equals(Object)</code> methods. It does however affect the order
-     * of <code>WeightedKey</code> instances. See
-     * <code>{@link #compareTo(Object)}</code> for more information.
-     * <p/>
-     * Let's assume we have an aggregation of node types named "b", "a" and "c".
-     * Its key would be "[a, b, c]" and the weight 3 (using the simple
-     * approximation).
+     * Searches the best key k for which the given <code>key</code> is a super
+     * set, i.e. for which {@link Key#contains(Key)}} returns
+     * <code>true</code>. If an already cached effective node type matches the
+     * key it is returned.
+     *
+     * @param key the key for which the subkey is to be searched
+     * @return the best key or <code>null</code> if no key could be found.
      */
-    static class WeightedKey implements Comparable {
+    Key findBest(Key key);
 
-        /**
-         * array of node type names, sorted in ascending order
-         */
-        private final QName[] names;
-
-        /**
-         * the weight of this key
-         */
-        private final int weight;
-
-        /**
-         * @param ntNames
-         */
-        WeightedKey(QName[] ntNames) {
-            this(ntNames, ntNames.length);
-        }
-
-        /**
-         * @param ntNames
-         * @param weight
-         */
-        WeightedKey(QName[] ntNames, int weight) {
-            this.weight = weight;
-            names = new QName[ntNames.length];
-            System.arraycopy(ntNames, 0, names, 0, names.length);
-            Arrays.sort(names);
-        }
-
-        /**
-         * @param ntNames
-         */
-        WeightedKey(Collection ntNames) {
-            this(ntNames, ntNames.size());
-        }
-
-        /**
-         * @param ntNames
-         * @param weight
-         */
-        WeightedKey(Collection ntNames, int weight) {
-            this((QName[]) ntNames.toArray(new QName[ntNames.size()]), weight);
-        }
+    /**
+    * An <code>ENTKey</code> uniquely identifies
+    * a combination (i.e. an aggregation) of one or more node types.
+    */
+    interface Key extends Comparable {
 
         /**
-         * @return the weight of this key
+         * Returns the node type names of this key.
+         * @return the node type names of this key.
          */
-        int getWeight() {
-            return weight;
-        }
+        QName[] getNames();
 
         /**
-         * @return the node type names of this key
+         * Checks if the <code>otherKey</code> is contained in this one. I.e.
if
+         * this key contains all node type names of the other key.
+         * @param otherKey the other key to check
+         * @return <code>true</code> if this key contains the other key;
+         *         <code>false</code> otherwise.
          */
-        QName[] getNames() {
-            return names;
-        }
-
-        boolean contains(WeightedKey otherKey) {
-            Set tmp = new HashSet(Arrays.asList(names));
-            for (int i = 0; i < otherKey.names.length; i++) {
-                if (!tmp.contains(otherKey.names[i])) {
-                    return false;
-                }
-            }
-            return true;
-        }
-
-        WeightedKey subtract(WeightedKey otherKey) {
-            Set tmp = new HashSet(Arrays.asList(names));
-            tmp.removeAll(Arrays.asList(otherKey.names));
-            return new WeightedKey(tmp);
-
-        }
+        boolean contains(Key otherKey);
 
         /**
-         * The resulting sort-order is: 1. descending weight, 2. ascending key
-         * (i.e. string representation of this sorted set).
+         * Creates a new key as a result of a subtract operation. i.e. removes all
+         * node type names that from the other key.
+         * <p/>
+         * Please note that no exception is thrown if the other key has node type
+         * names that are not contained in this key (i.e. {@link #contains(Key)}
+         * returns <code>false</code>).
          *
-         * @param o
-         * @return the result of the comparison
+         * @param otherKey the other key to subtract
+         * @return the new key of the subtraction operation.
          */
-        public int compareTo(Object o) {
-            WeightedKey other = (WeightedKey) o;
+        Key subtract(Key otherKey);
 
-            // compare weights
-            if (weight > other.weight) {
-                return -1;
-            } else if (weight < other.weight) {
-                return 1;
-            }
-
-            // compare arrays of names
-            int len1 = names.length;
-            int len2 = other.names.length;
-            int len = Math.min(len1, len2);
-
-            for (int i = 0; i < len; i++) {
-                QName name1 = names[i];
-                QName name2 = other.names[i];
-                int result = name1.compareTo(name2);
-                if (result != 0) {
-                    return result;
-                }
-            }
-            return len1 - len2;
-        }
-
-        public int hashCode() {
-            int h = 17;
-            // ignore weight
-            for (int i = 0; i < names.length; i++) {
-                h *= 37;
-                h += names[i].hashCode();
-            }
-            return h;
-        }
-
-        public boolean equals(Object obj) {
-            if (this == obj) {
-                return true;
-            }
-            if (obj instanceof WeightedKey) {
-                WeightedKey other = (WeightedKey) obj;
-                // ignore weight
-                return Arrays.equals(names, other.names);
-            }
-            return false;
-        }
-
-        public String toString() {
-            return Arrays.asList(names).toString() + " (" + weight + ")";
-        }
     }
-}
\ No newline at end of file
+}

Modified: jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/EffectiveNodeTypeImpl.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/EffectiveNodeTypeImpl.java?view=diff&rev=518926&r1=518925&r2=518926
==============================================================================
--- jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/EffectiveNodeTypeImpl.java
(original)
+++ jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/EffectiveNodeTypeImpl.java
Fri Mar 16 03:28:55 2007
@@ -431,10 +431,10 @@
             throws ConstraintViolationException {
         try {
             getApplicableNodeDefinition(name, null, ntReg);
-        } catch (NoSuchNodeTypeException nsnte) {
+        } catch (NoSuchNodeTypeException e) {
             String msg = "internal eror: inconsistent node type";
             log.debug(msg);
-            throw new ConstraintViolationException(msg, nsnte);
+            throw new ConstraintViolationException(msg, e);
         }
     }
 

Modified: jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/NodeTypeRegistryImpl.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/NodeTypeRegistryImpl.java?view=diff&rev=518926&r1=518925&r2=518926
==============================================================================
--- jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/NodeTypeRegistryImpl.java
(original)
+++ jackrabbit/trunk/contrib/spi/jcr2spi/src/main/java/org/apache/jackrabbit/jcr2spi/nodetype/NodeTypeRegistryImpl.java
Fri Mar 16 03:28:55 2007
@@ -32,7 +32,6 @@
 import javax.jcr.nodetype.NoSuchNodeTypeException;
 import javax.jcr.version.OnParentVersionAction;
 import java.io.PrintStream;
-import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
@@ -105,7 +104,7 @@
         this.storage = storage;
         this.validator = new DefinitionValidator(this, nsRegistry);
 
-        entCache = new EffectiveNodeTypeCache();
+        entCache = new BitsetENTCacheImpl();
         registeredNTDefs = new ConcurrentReaderHashMap();
 
         propDefs = new HashSet();
@@ -208,7 +207,8 @@
                                                    Map ntdCache)
         throws NoSuchNodeTypeException {
         // 1. check if effective node type has already been built
-        EffectiveNodeType ent = entCache.get(new QName[]{ntName});
+        EffectiveNodeTypeCache.Key key = entCache.getKey(new QName[]{ntName});
+        EffectiveNodeType ent = entCache.get(key);
         if (ent != null) {
             return ent;
         }
@@ -248,8 +248,7 @@
                                                    Map ntdCache)
         throws NodeTypeConflictException, NoSuchNodeTypeException {
 
-        EffectiveNodeTypeCache.WeightedKey key = new EffectiveNodeTypeCache.WeightedKey(ntNames);
-
+        EffectiveNodeTypeCache.Key key = entCache.getKey(ntNames);
         // 1. check if aggregate has already been built
         if (entCache.contains(key)) {
             return entCache.get(key);
@@ -263,41 +262,25 @@
         }
 
         // 3. build aggregate
+        EffectiveNodeTypeCache.Key requested = key;
         EffectiveNodeTypeImpl result = null;
         synchronized (entCache) {
             // build list of 'best' existing sub-aggregates
-            ArrayList tmpResults = new ArrayList();
             while (key.getNames().length > 0) {
-                // check if we've already built this aggregate
-                if (entCache.contains(key)) {
-                    tmpResults.add(entCache.get(key));
-                    // subtract the result from the temporary key
-                    // (which is 'empty' now)
-                    key = key.subtract(key);
-                    break;
-                }
-                /**
-                 * walk list of existing aggregates sorted by 'weight' of
-                 * aggregate (i.e. the cost of building it)
-                 */
-                boolean foundSubResult = false;
-                Iterator iter = entCache.keyIterator();
-                while (iter.hasNext()) {
-                    EffectiveNodeTypeCache.WeightedKey k =
-                            (EffectiveNodeTypeCache.WeightedKey) iter.next();
-                    /**
-                     * check if the existing aggregate is a 'subset' of the one
-                     * we're looking for
-                     */
-                    if (key.contains(k)) {
-                        tmpResults.add(entCache.get(k));
-                        // subtract the result from the temporary key
-                        key = key.subtract(k);
-                        foundSubResult = true;
-                        break;
+                // find the (sub) key that matches the current key the best
+                EffectiveNodeTypeCache.Key subKey = entCache.findBest(key);
+                if (subKey != null) {
+                    EffectiveNodeTypeImpl ent = (EffectiveNodeTypeImpl) entCache.get(subKey);
+                    if (result == null) {
+                        result = ent;
+                    } else {
+                        result = result.merge(ent);
+                        // store intermediate result
+                        entCache.put(result);
                     }
-                }
-                if (!foundSubResult) {
+                    // subtract the result from the temporary key
+                    key = key.subtract(subKey);
+                } else {
                     /**
                      * no matching sub-aggregates found:
                      * build aggregate of remaining node types through iteration
@@ -316,21 +299,14 @@
                             entCache.put(result);
                         }
                     }
-                    // add aggregate of remaining node types to result list
-                    tmpResults.add(result);
                     break;
                 }
             }
-            // merge the sub-aggregates into new effective node type
-            for (int i = 0; i < tmpResults.size(); i++) {
-                if (result == null) {
-                    result = (EffectiveNodeTypeImpl) tmpResults.get(i);
-                } else {
-                    result = result.merge((EffectiveNodeTypeImpl) tmpResults.get(i));
-                    // store intermediate result
-                    entCache.put(result);
-                }
-            }
+        }
+        // also put the requested key, since the merge could have removed some
+        // the redundant nodetypes
+        if (!entCache.contains(requested)) {
+            entCache.put(requested, result);
         }
         // we're done
         return result;
@@ -552,26 +528,9 @@
     }
 
     private void internalUnregister(QName name) {
-        /*
-         * NOTE: detection of built-in NodeTypes not possible, since the client
-         * reads all nodetypes from the 'server' only without being able to
-         * destinguish between built-in and custom-defined nodetypes.
-         */
         QNodeTypeDefinition ntd = (QNodeTypeDefinition) registeredNTDefs.get(name);
         registeredNTDefs.remove(name);
-        /*
-         * remove all affected effective node types from aggregates cache
-         * (copy keys first to prevent ConcurrentModificationException)
-         */
-        ArrayList keys = new ArrayList(entCache.keySet());
-        for (Iterator keysIter = keys.iterator(); keysIter.hasNext();) {
-            EffectiveNodeTypeCache.WeightedKey k =
-                    (EffectiveNodeTypeCache.WeightedKey) keysIter.next();
-            EffectiveNodeType ent = entCache.get(k);
-            if (ent.includesNodeType(name)) {
-                entCache.remove(k);
-            }
-        }
+        entCache.invalidate(name);
 
         // remove property & child node definitions
         QPropertyDefinition[] pda = ntd.getPropertyDefs();



Mime
View raw message