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