cvs commit: jakarta-avalon-excalibur/collections/src/java/org/apache/avalon/excalibur/collections BucketMap.java

[bloritsch]

bloritsch    2002/06/26 10:43:54

  Modified:    collections/src/java/org/apache/avalon/excalibur/collections
                        BucketMap.java
  Log:
  cache the size of the BucketMap--reducing cost of size() and empty() methods 
from O(n) to O
  
  Revision  Changes    Path
  1.19      +8 -27     
jakarta-avalon-excalibur/collections/src/java/org/apache/avalon/excalibur/collections/BucketMap.java
  
  Index: BucketMap.java
  ===================================================================
  RCS file: 
/home/cvs/jakarta-avalon-excalibur/collections/src/java/org/apache/avalon/excalibur/collections/BucketMap.java,v
  retrieving revision 1.18
  retrieving revision 1.19
  diff -u -r1.18 -r1.19
  --- BucketMap.java    25 Jun 2002 20:54:47 -0000      1.18
  +++ BucketMap.java    26 Jun 2002 17:43:54 -0000      1.19
  @@ -29,6 +29,7 @@
   {
       private static final int DEFAULT_BUCKETS = 255;
       private final Node[] m_buckets;
  +    private volatile int m_size = 0;
   
       /**
        * Initializes the map with the default number of buckets (255).
  @@ -114,23 +115,7 @@
        */
       public int size()
       {
  -        int cnt = 0;
  -
  -        for( int i = 0; i < m_buckets.length; i++ )
  -        {
  -            synchronized( m_buckets[ i ] )
  -            {
  -                Node n = m_buckets[ i ];
  -
  -                while( n != null && n.key != null )
  -                {
  -                    cnt++;
  -                    n = n.next;
  -                }
  -            }
  -        }
  -
  -        return cnt;
  +        return m_size;
       }
   
       /**
  @@ -153,6 +138,7 @@
               {
                   n.key = key;
                   n.value = value;
  +                m_size++;
                   return value;
               }
   
  @@ -165,6 +151,7 @@
   
                   if( n.key.equals( key ) )
                   {
  +                    // do not adjust size because nothing was added
                       Object returnVal = n.value;
                       n.value = value;
                       return returnVal;
  @@ -177,6 +164,7 @@
               newNode.key = key;
               newNode.value = value;
               n.next = newNode;
  +            m_size++;
           }
   
           return null;
  @@ -374,6 +362,7 @@
                           prev.next = n.next;
                       }
   
  +                    m_size--;
                       return n.value;
                   }
   
  @@ -390,15 +379,7 @@
        */
       public final boolean isEmpty()
       {
  -        for( int i = 0; i < m_buckets.length; i++ )
  -        {
  -            if( m_buckets[ i ].key != null )
  -            {
  -                return false;
  -            }
  -        }
  -
  -        return true;
  +        return m_size == 0;
       }
   
       /**
  
  
  

--
To unsubscribe, e-mail:   <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>