commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From pj...@apache.org
Subject cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections StaticBucketMap.java
Date Thu, 15 Aug 2002 03:22:29 GMT
pjack       2002/08/14 20:22:29

  Modified:    collections/src/java/org/apache/commons/collections
                        StaticBucketMap.java
  Log:
  1.  Collection views are now backed by map.
  2.  Used bit-mixing hash function.
  3.  Added docs about the non-atomic nature of bulk operations.
  4.  Improved performance of size() operation.
  5.  Added atomic(Runnable) method.
  
  Revision  Changes    Path
  1.3       +314 -89   jakarta-commons/collections/src/java/org/apache/commons/collections/StaticBucketMap.java
  
  Index: StaticBucketMap.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/StaticBucketMap.java,v
  retrieving revision 1.2
  retrieving revision 1.3
  diff -u -r1.2 -r1.3
  --- StaticBucketMap.java	10 Jul 2002 03:35:32 -0000	1.2
  +++ StaticBucketMap.java	15 Aug 2002 03:22:29 -0000	1.3
  @@ -60,36 +60,91 @@
    */
   package org.apache.commons.collections;
   
  +import java.util.AbstractCollection;
  +import java.util.AbstractSet;
   import java.util.Collection;
   import java.util.HashSet;
   import java.util.Iterator;
   import java.util.Map;
   import java.util.Set;
   import java.util.ArrayList;
  +import java.util.NoSuchElementException;
   
   /**
    * A StaticBucketMap is an efficient, thread-safe implementation of
    * <code>java.util.Map</code> that performs well in in a highly
    * thread-contentious environment.  The map supports very efficient
  - * <code>get</code>, <code>put</code>, <code>contains</code>,
and
  - * <code>remove</code> operations, assuming (approximate) uniform hashing and
  - * that the number of entries does not exceed the size of the map.  If the
  - * number of entries exceeds the size of the map or if the hashcodes of the
  + * {@link #get(Object) get}, {@link #put(Object,Object) put}, 
  + * {@link #remove(Object) remove} and {@link #containsKey(Object) containsKey}
  + * operations, assuming (approximate) uniform hashing and
  + * that the number of entries does not exceed the number of buckets.  If the
  + * number of entries exceeds the number of buckets or if the hashcodes of the
    * objects are not uniformly distributed, these operations have a worst case
    * scenario that is proportional to the number of elements in the map
  - * (<I>O(n)</I>).
  + * (<I>O(n)</I>).<P>
  + *
  + * Each bucket in the hash table has its own monitor, so two threads can 
  + * safely operate on the map at the same time, often without incurring any 
  + * monitor contention.  This means that you don't have to wrap instances
  + * of this class with {@link java.util.Collections#synchronizedMap(Map)};
  + * instances are already thread-safe.  Unfortunately, however, this means 
  + * that this map implementation behaves in ways you may find disconcerting.  
  + * Bulk operations, such as {@link #putAll(Map) putAll} or the
  + * {@link Collection#retainAll(Collection) retainAll} operation in collection 
  + * views, are <I>not</I> atomic.  If two threads are simultaneously 
  + * executing 
  + *
  + * <Pre>
  + *   staticBucketMapInstance.putAll(map);
  + * </Pre>
  + *
  + * and
  + *
  + * <Pre>
  + *   staticBucketMapInstance.entrySet().removeAll(map.entrySet());
  + * </Pre>
  + *
  + * then the results are generally random.  Those two statement could cancel
  + * each other out, leaving <Code>staticBucketMapInstance</Code> essentially

  + * unchanged, or they could leave some random subset of <Code>map</Code> in

  + * <Code>staticBucketMapInstance</Code>.<P>
  + *
  + * Also, much like an encyclopedia, the results of {@link #size()} and 
  + * {@link #isEmpty()} are out-of-date as soon as they are produced.<P>
  + *
  + * The iterators returned by the collection views of this class are <I>not</I>
  + * fail-fast.  They will <I>never</I> raise a 
  + * {@link java.util.ConcurrentModificationException}.  Keys and values 
  + * added to the map after the iterator is created do not necessarily appear
  + * during iteration.  Similarly, the iterator does not necessarily fail to 
  + * return keys and values that were removed after the iterator was created.<P>
  + *
  + * Finally, unlike {@link java.util.HashMap}-style implementations, this
  + * class <I>never</I> rehashes the map.  The number of buckets is fixed 
  + * at construction time and never altered.  Performance may degrade if 
  + * you do not allocate enough buckets upfront.<P>
  + *
  + * The {@link #atomic(Runnable)} method is provided to allow atomic iterations
  + * and bulk operations; however, overuse of {@link #atomic(Runnable) atomic}
  + * will basically result in a map that's slower than an ordinary synchronized
  + * {@link java.util.HashMap}.
  + *
  + * Use this class if you do not require reliable bulk operations and 
  + * iterations, or if you can make your own guarantees about how bulk 
  + * operations will affect the map.<P>
    *
    * @author  <a href="mailto:bloritsch@apache.org">Berin Loritsch</a>
    * @author  <a href="mailto:g-froehlich@gmx.de">Gerhard Froehlich</a>
    * @author  <a href="mailto:mas@apache.org">Michael A. Smith</a>
  + * @author  Paul Jack
    * @version CVS $Revision$ $Date$
    * @since Avalon 4.0
    */
   public final class StaticBucketMap implements Map
   {
       private static final int DEFAULT_BUCKETS = 255;
  -    private final Node[] m_buckets;
  -    private final Object[] m_locks;
  +    private Node[] m_buckets;
  +    private Lock[] m_locks;
   
       /**
        * Initializes the map with the default number of buckets (255).
  @@ -106,6 +161,8 @@
        * chances for thread contention.  The fewer buckets, the more chances for
        * thread contention.  The more buckets the fewer chances for thread
        * contention.
  +     *
  +     * @param numBuckets  the number of buckets for this map
        */
       public StaticBucketMap( int numBuckets )
       {
  @@ -118,11 +175,11 @@
           }
   
           m_buckets = new Node[ size ];
  -        m_locks = new Object[ size ];
  +        m_locks = new Lock[ size ];
   
           for( int i = 0; i < size; i++ )
           {
  -            m_locks[ i ] = new Object();
  +            m_locks[ i ] = new Lock();
           }
       }
   
  @@ -142,34 +199,23 @@
       private final int getHash( Object key )
       {
           if( key == null ) return 0;
  -        final int hash = key.hashCode() % m_buckets.length;
  +        int hash = key.hashCode();
  +        hash += ~(hash << 15);
  +        hash ^= (hash >>> 10);
  +        hash += (hash << 3);
  +        hash ^= (hash >>> 6);
  +        hash += ~(hash << 11);
  +        hash ^= (hash >>> 16);
  +        hash %= m_buckets.length;
           return ( hash < 0 ) ? hash * -1 : hash;
       }
   
       /**
  -     * Obtain a Set for the keys.  This operation crosses bucket boundaries,
  -     * so it is less efficient, and greatly increases the chance for thread
  -     * contention.
  +     *  Returns a set view of this map's keys.
        */
       public Set keySet()
       {
  -        Set keySet = new HashSet();
  -
  -        for( int i = 0; i < m_buckets.length; i++ )
  -        {
  -            synchronized( m_locks[ i ] )
  -            {
  -                Node n = m_buckets[ i ];
  -
  -                while( n != null )
  -                {
  -                    keySet.add( n.key );
  -                    n = n.next;
  -                }
  -            }
  -        }
  -
  -        return keySet;
  +        return new KeySet();
       }
   
       /**
  @@ -181,16 +227,7 @@
   
           for( int i = 0; i < m_buckets.length; i++ )
           {
  -            synchronized( m_locks[ i ] )
  -            {
  -                Node n = m_buckets[ i ];
  -
  -                while( n != null )
  -                {
  -                    cnt++;
  -                    n = n.next;
  -                }
  -            }
  +            cnt += m_locks[i].size;
           }
   
           return cnt;
  @@ -213,6 +250,7 @@
                   n.key = key;
                   n.value = value;
                   m_buckets[ hash ] = n;
  +                m_locks[hash].size++;
                   return null;
               }
   
  @@ -237,6 +275,7 @@
               newNode.key = key;
               newNode.value = value;
               n.next = newNode;
  +            m_locks[hash].size++;
           }
   
           return null;
  @@ -328,23 +367,7 @@
        */
       public Collection values()
       {
  -        ArrayList values = new ArrayList();
  -
  -        for( int i = 0; i < m_buckets.length; i++ )
  -        {
  -            synchronized( m_locks[ i ] )
  -            {
  -                Node n = m_buckets[ i ];
  -
  -                while( n != null )
  -                {
  -                    values.add( n.value );
  -                    n = n.next;
  -                }
  -            }
  -        }
  -
  -        return values;
  +        return new Values();
       }
   
       /**
  @@ -354,23 +377,7 @@
        */
       public Set entrySet()
       {
  -        Set entrySet = new HashSet();
  -
  -        for( int i = 0; i < m_buckets.length; i++ )
  -        {
  -            synchronized( m_locks[ i ] )
  -            {
  -                Node n = m_buckets[ i ];
  -
  -                while( n != null )
  -                {
  -                    entrySet.add( n );
  -                    n = n.next;
  -                }
  -            }
  -        }
  -
  -        return entrySet;
  +        return new EntrySet();
       }
   
       /**
  @@ -414,7 +421,7 @@
                           // Set the next node of the previous node to be the node after
this one.
                           prev.next = n.next;
                       }
  -
  +                    m_locks[hash].size--;
                       return n.value;
                   }
   
  @@ -431,15 +438,7 @@
        */
       public final boolean isEmpty()
       {
  -        for( int i = 0; i < m_buckets.length; i++ )
  -        {
  -            if( m_buckets[ i ] != null )
  -            {
  -                return false;
  -            }
  -        }
  -
  -        return true;
  +        return size() == 0;
       }
   
       /**
  @@ -449,10 +448,21 @@
       {
           for( int i = 0; i < m_buckets.length; i++ )
           {
  -            m_buckets[ i ] = null;
  +            Lock lock = m_locks[i];
  +            synchronized (lock) {
  +                m_buckets[ i ] = null;
  +                lock.size = 0;
  +            }
           }
       }
   
  +    /**
  +     *  Returns true if the given object is a map with the same mappings
  +     *  as this map.
  +     *
  +     *  @return true if the given object is the a map with same mappings
  +     *   as this map
  +     */
       public final boolean equals( Object obj )
       {
           if( obj == null ) return false;
  @@ -465,6 +475,11 @@
           return entrySet().equals(other.entrySet());
       }
   
  +    /**
  +     *  Returns a hash code for this map.
  +     *
  +     *  @return a hash code for this map
  +     */
       public final int hashCode() 
       {
           int hashCode = 0;
  @@ -532,4 +547,214 @@
               return retVal;
           }
       }
  +
  +    private final static class Lock {
  +
  +        public int size;
  +
  +    }
  +
  +
  +    private class EntryIterator implements Iterator {
  +
  +        private ArrayList current = new ArrayList();
  +        private int bucket;
  +        private Map.Entry last;
  +
  +
  +        public boolean hasNext() {
  +            if (current.size() > 0) return true;
  +            while (bucket < m_buckets.length) {
  +                synchronized (m_locks[bucket]) {
  +                    Node n = m_buckets[bucket];
  +                    while (n != null) {
  +                        current.add(n);
  +                        n = n.next;
  +                    }
  +                    bucket++;
  +                    if (current.size() > 0) return true;
  +                }
  +            }
  +            return false;
  +        }
  +
  +        protected Map.Entry nextEntry() {
  +            if (!hasNext()) throw new NoSuchElementException();
  +            last = (Map.Entry)current.remove(current.size() - 1);
  +            return last;
  +        }
  +
  +        public Object next() {
  +            return nextEntry();
  +        }
  +
  +        public void remove() {
  +            if (last == null) throw new IllegalStateException();
  +            StaticBucketMap.this.remove(last.getKey());
  +            last = null;
  +        }
  +
  +    }
  +
  +    private class ValueIterator extends EntryIterator {
  +
  +        public Object next() {
  +            return nextEntry().getValue();
  +        }
  +
  +    }
  +
  +    private class KeyIterator extends EntryIterator {
  +
  +        public Object next() {
  +            return nextEntry().getKey();
  +        }
  +
  +    }
  +
  +    private class EntrySet extends AbstractSet {
  +
  +        public int size() {
  +            return StaticBucketMap.this.size();
  +        }
  +
  +        public void clear() {
  +            StaticBucketMap.this.clear();
  +        }
  +
  +        public Iterator iterator() {
  +            return new EntryIterator();
  +        }
  +
  +        public boolean contains(Object o) {
  +            Map.Entry entry = (Map.Entry)o;
  +            int hash = getHash(entry.getKey());
  +            synchronized (m_locks[hash]) {
  +                for (Node n = m_buckets[hash]; n != null; n = n.next) {
  +                    if (n.equals(entry)) return true;
  +                }
  +            }
  +            return false;
  +        }
  +
  +        public boolean remove(Object o) {
  +            Map.Entry entry = (Map.Entry)o;
  +            int hash = getHash(entry.getKey());
  +            synchronized (m_locks[hash]) {
  +                for (Node n = m_buckets[hash]; n != null; n = n.next) {
  +                    if (n.equals(entry)) {
  +                        StaticBucketMap.this.remove(n.getKey());
  +                        return true;
  +                    }
  +                }
  +            }
  +            return false;
  +        }
  +
  +    }
  +
  +
  +    private class KeySet extends AbstractSet {
  +
  +        public int size() {
  +            return StaticBucketMap.this.size();
  +        }
  +
  +        public void clear() {
  +            StaticBucketMap.this.clear();
  +        }
  +
  +        public Iterator iterator() {
  +            return new KeyIterator();
  +        }
  +
  +        public boolean contains(Object o) {
  +            return StaticBucketMap.this.containsKey(o);
  +        }
  +
  +        public boolean remove(Object o) {
  +            int hash = getHash(o);
  +            synchronized (m_locks[hash]) {
  +                for (Node n = m_buckets[hash]; n != null; n = n.next) {
  +                    Object k = n.getKey();
  +                    if ((k == o) || ((k != null) && k.equals(o))) {
  +                        StaticBucketMap.this.remove(k);
  +                        return true;
  +                    }
  +                }
  +            }
  +            return false;
  +
  +        }
  +
  +    }
  +
  +
  +    private class Values extends AbstractCollection {
  +
  +        public int size() {
  +            return StaticBucketMap.this.size();
  +        }
  +
  +        public void clear() {
  +            StaticBucketMap.this.clear();
  +        }
  +
  +        public Iterator iterator() {
  +            return new ValueIterator();
  +        }
  +
  +    }
  +
  +
  +    /**
  +     *  Prevents any operations from occuring on this map while the
  +     *  given {@link Runnable} executes.  This method can be used, for
  +     *  instance, to execute a bulk operation atomicly: 
  +     *
  +     *  <Pre>
  +     *    staticBucketMapInstance.atomic(new Runnable() {
  +     *        public void run() {
  +     *            staticBucketMapInstance.putAll(map);
  +     *        }
  +     *    });
  +     *  </Pre>
  +     *
  +     *  It can also be used if you need a reliable iterator:
  +     *
  +     *  <Pre>
  +     *    staticBucketMapInstance.atomic(new Runnable() {
  +     *        public void run() {
  +     *            Iterator iterator = staticBucketMapInstance.iterator();
  +     *            while (iterator.hasNext()) {
  +     *                foo(iterator.next();
  +     *            }
  +     *        }
  +     *    });
  +     *  </Pre>
  +     *
  +     *  <B>Implementation note:</B> This method requires a lot of time
  +     *  and a ton of stack space.  Essentially a recursive algorithm is used
  +     *  to enter each bucket's monitor.  If you have twenty thousand buckets
  +     *  in your map, then the recursive method will be invoked twenty thousand
  +     *  times.  You have been warned.
  +     *
  +     *  @param r  the code to execute atomicly
  +     */
  +    public void atomic(Runnable r) {
  +        if (r == null) throw new NullPointerException();
  +        atomic(r, 0);
  +    }
  +
  +    private void atomic(Runnable r, int bucket) {
  +        if (bucket >= m_buckets.length) {
  +            r.run();
  +            return;
  +        }
  +        synchronized (m_locks[bucket]) {
  +            atomic(r, bucket + 1);
  +        }
  +    }
  +
  +
   }
  
  
  

--
To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message