MRUBucketMap


1   /*
2    * Copyright 1999-2004 The Apache Software Foundation.
3    * 
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    * 
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    * 
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  package org.apache.cocoon.util;
17  
18  import java.util.Set  ;
19  import java.util.HashSet  ;
20  import java.util.NoSuchElementException  ;
21  import java.util.Map  ;
22  import java.util.Collection  ;
23  import java.util.Iterator  ;
24  
25  /**
26   * A MRUBucketMap is an efficient ThreadSafe implementation of a Map with
27   * addition of the removeLast method implementing LRU removal policy.
28   * <br />
29   * MRUBucketMap is based on the Avalon's BucketMap.
30   *
31   * @author  <a HREF="mailto:vgritsenko@apache.org">Vadim Gritsenko</a>
32   * @deprecated Will be removed in Cocoon 2.2
33   * @version CVS $Id: MRUBucketMap.java 123825 2004-12-31 21:18:01Z antonio $
34   */
35  public final class MRUBucketMap implements Map  
36  {
37      private static final int DEFAULT_BUCKETS = 255;
38      private final Node[] m_buckets;
39      private final Object  [] m_locks;
40      private final Node m_header = new Node();
41      private int m_size = 0;
42  
43      /**
44       * Creates map with default number of buckets.
45       */
46      public MRUBucketMap()
47      {
48          this( DEFAULT_BUCKETS );
49      }
50  
51      /**
52       * Creates map with specified number of buckets.
53       */
54      public MRUBucketMap( int numBuckets )
55      {
56          int size = Math.max( 17, numBuckets );
57  
58          // Ensure that bucketSize is never a power of 2 (to ensure maximal distribution)
59          if( size % 2 == 0 )
60          {
61              size--;
62          }
63  
64          m_buckets = new Node[ size ];
65          m_locks = new Object  [ size ];
66  
67          for( int i = 0; i < size; i++ )
68          {
69              m_locks[ i ] = new Object  ();
70          }
71  
72          m_header.mru_next = m_header.mru_previous = m_header;
73      }
74  
75      private final int getHash( Object   key )
76      {
77          final int hash = key.hashCode() % m_buckets.length;
78          return ( hash < 0 ) ? hash * -1 : hash;
79      }
80  
81      public Set   keySet()
82      {
83          Set   keySet = new HashSet  ();
84  
85          for( int i = 0; i < m_buckets.length; i++ )
86          {
87              synchronized( m_locks[ i ] )
88              {
89                  Node n = m_buckets[ i ];
90  
91                  while( n != null )
92                  {
93                      keySet.add( n.key );
94                      n = n.next;
95                  }
96              }
97          }
98  
99          return keySet;
100     }
101 
102     /**
103      * Returns the current number of key, value pairs.
104      */
105     public int size()
106     {
107         return m_size;
108     }
109 
110     /**
111      * Put a reference in the Map.
112      */
113     public Object   put( final Object   key, final Object   value )
114     {
115         if( null == key || null == value )
116         {
117             return null;
118         }
119 
120         int isNew = 0;
121         Node node;
122         Object   oldValue = null;
123 
124         int hash = getHash( key );
125 
126         synchronized( m_locks[ hash ] )
127         {
128             Node n = m_buckets[ hash ];
129             if( n == null )
130             {
131                 node = new Node();
132                 node.key = key;
133                 node.value = value;
134                 m_buckets[ hash ] = node;
135                 isNew = 1;
136             }
137             else
138             {
139                 // Set n to the last node in the linked list.  Check each key along the way
140                 //  If the key is found, then change the value of that node and return
141                 //  the old value.
142                 for( Node next = n; next != null; next = next.next )
143                 {
144                     n = next;
145 
146                     if( n.key.equals( key ) )
147                     {
148                         oldValue = n.value;
149                         n.value = value;
150                         break;
151                     }
152                 }
153 
154                 if (oldValue == null) {
155                     // The key was not found in the current list of nodes,
156                     // add it to the end in a new node.
157                     node = new Node();
158                     node.key = key;
159                     node.value = value;
160                     n.next = node;
161                     isNew = 1;
162                 } else {
163                     // The key was found in the list. Move it to the head.
164                     node = n;
165                 }
166             }
167         }
168 
169         synchronized ( m_header )
170         {
171             if (isNew == 0) {
172                 // Remove
173                 node.mru_previous.mru_next = node.mru_next;
174                 node.mru_next.mru_previous = node.mru_previous;
175             }
176             // Move node to the head.
177             node.mru_previous = m_header;
178             node.mru_next = m_header.mru_next;
179             node.mru_previous.mru_next = node;
180             node.mru_next.mru_previous = node;
181             m_size += isNew;
182         }
183 
184         return oldValue;
185     }
186 
187     public Object   get( final Object   key )
188     {
189         if( null == key )
190         {
191             return null;
192         }
193 
194         Node n;
195 
196         int hash = getHash( key );
197 
198         synchronized( m_locks[ hash ] )
199         {
200             n = m_buckets[ hash ];
201 
202             while( n != null )
203             {
204                 if( n.key.equals( key ) )
205                 {
206                     break;
207                 }
208 
209                 n = n.next;
210             }
211         }
212 
213         if( n != null ) {
214             synchronized( m_header ) {
215                 // Remove
216                 n.mru_previous.mru_next = n.mru_next;
217                 n.mru_next.mru_previous = n.mru_previous;
218                 // Add first
219                 n.mru_previous = m_header;
220                 n.mru_next = m_header.mru_next;
221                 n.mru_previous.mru_next = n;
222                 n.mru_next.mru_previous = n;
223             }
224             return n.value;
225         }
226 
227         return null;
228     }
229 
230     public boolean containsKey( final Object   key )
231     {
232         if( null == key )
233         {
234             return false;
235         }
236 
237         int hash = getHash( key );
238 
239         synchronized( m_locks[ hash ] )
240         {
241             Node n = m_buckets[ hash ];
242 
243             while( n != null )
244             {
245                 if( n.key.equals( key ) )
246                 {
247                     return true;
248                 }
249 
250                 n = n.next;
251             }
252         }
253 
254         return false;
255     }
256 
257     public boolean containsValue( final Object   value )
258     {
259         if( null == value )
260         {
261             return false;
262         }
263 
264         synchronized( m_header )
265         {
266             for( Node n = m_header.mru_next; n != m_header; n = n.mru_next )
267             {
268                 if( n.value.equals( value ) )
269                 {
270                     return true;
271                 }
272             }
273         }
274 
275         return false;
276     }
277 
278     public Collection   values()
279     {
280         Set   valueSet = new HashSet  ();
281 
282         synchronized( m_header )
283         {
284             for( Node n = m_header.mru_next; n != m_header; n = n.mru_next )
285             {
286                 valueSet.add( n.value );
287             }
288         }
289 
290         return valueSet;
291     }
292 
293     public Set   entrySet()
294     {
295         Set   entrySet = new HashSet  ();
296 
297         synchronized( m_header )
298         {
299             for( Node n = m_header.mru_next; n != m_header; n = n.mru_next )
300             {
301                 entrySet.add( n );
302             }
303         }
304 
305         return entrySet;
306     }
307 
308     /**
309      * Add all the contents of one Map into this one.
310      */
311     public void putAll( Map   other )
312     {
313         for (Iterator   i = other.entrySet().iterator(); i.hasNext(); ) {
314             Map.Entry   me = (Map.Entry  )i.next();
315             put(me.getKey(), me.getValue());
316         }
317     }
318 
319     public Object   remove( Object   key )
320     {
321         if( null == key )
322         {
323             return null;
324         }
325 
326         Node n;
327 
328         int hash = getHash( key );
329 
330         synchronized( m_locks[ hash ] )
331         {
332             n = m_buckets[ hash ];
333             Node prev = null;
334 
335             while( n != null )
336             {
337                 if( n.key.equals( key ) )
338                 {
339                     // Remove this node from the linked list of nodes.
340                     if( null == prev )
341                     {
342                         // This node was the head, set the next node to be the new head.
343                         m_buckets[ hash ] = n.next;
344                     }
345                     else
346                     {
347                         // Set the next node of the previous node to be the node after this one.
348                         prev.next = n.next;
349                     }
350 
351                     break;
352                 }
353 
354                 prev = n;
355                 n = n.next;
356             }
357         }
358 
359         if (n != null) {
360             synchronized(m_header) {
361                 // Remove
362                 n.mru_previous.mru_next = n.mru_next;
363                 n.mru_next.mru_previous = n.mru_previous;
364                 m_size--;
365             }
366 
367             return n.value;
368         }
369 
370         return null;
371     }
372 
373     public final boolean isEmpty()
374     {
375         return m_size == 0;
376     }
377 
378     public final void clear()
379     {
380         synchronized ( m_header ) {
381             for( int i = 0; i < m_buckets.length; i++ )
382             {
383                 m_buckets[ i ] = null;
384             }
385 
386             m_header.mru_next = m_header.mru_previous = m_header;
387             m_size = 0;
388         }
389     }
390 
391     public Map.Entry   removeLast()
392     {
393         Node node = m_header.mru_previous;
394         if (node == m_header) {
395             throw new NoSuchElementException  ("MRUBucketMap is empty");
396         }
397 
398         remove(node.key);
399         node.mru_next = null;
400         node.mru_previous = null;
401         return node;
402     }
403 
404     private static final class Node implements Map.Entry  
405     {
406         protected Object   key;
407         protected Object   value;
408         protected Node next;
409 
410         protected Node mru_previous;
411         protected Node mru_next;
412 
413         public Object   getKey()
414         {
415             return key;
416         }
417 
418         public Object   getValue()
419         {
420             return value;
421         }
422 
423         public Object   setValue( Object   val )
424         {
425             Object   retVal = value;
426             value = val;
427             return retVal;
428         }
429     }
430 
431 
432     static class X {
433         String   x;
434         public X (String   s) {
435             x = s;
436         }
437         public int hashCode() {
438             return 1;
439         }
440 
441         public boolean equals(Object   obj) {
442             return this == obj;
443         }
444 
445         public String   toString() {
446             return x;
447         }
448     }
449 }
450
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags