1 |
|
package org.apache.jcs.utils.struct; |
2 |
|
|
3 |
|
|
4 |
|
|
5 |
|
|
6 |
|
|
7 |
|
|
8 |
|
|
9 |
|
|
10 |
|
|
11 |
|
|
12 |
|
|
13 |
|
|
14 |
|
|
15 |
|
|
16 |
|
|
17 |
|
|
18 |
|
|
19 |
|
|
20 |
|
|
21 |
|
|
22 |
|
import java.io.Serializable; |
23 |
|
import java.util.ArrayList; |
24 |
|
import java.util.Collection; |
25 |
|
import java.util.HashSet; |
26 |
|
import java.util.Hashtable; |
27 |
|
import java.util.Iterator; |
28 |
|
import java.util.Map; |
29 |
|
import java.util.NoSuchElementException; |
30 |
|
import java.util.Set; |
31 |
|
|
32 |
|
import org.apache.commons.logging.Log; |
33 |
|
import org.apache.commons.logging.LogFactory; |
34 |
|
import org.apache.jcs.engine.control.group.GroupAttrName; |
35 |
|
import org.apache.jcs.engine.stats.StatElement; |
36 |
|
import org.apache.jcs.engine.stats.Stats; |
37 |
|
import org.apache.jcs.engine.stats.behavior.IStatElement; |
38 |
|
import org.apache.jcs.engine.stats.behavior.IStats; |
39 |
|
|
40 |
|
|
41 |
|
|
42 |
|
|
43 |
|
|
44 |
|
|
45 |
|
|
46 |
|
|
47 |
|
|
48 |
|
|
49 |
|
|
50 |
|
|
51 |
|
|
52 |
|
|
53 |
|
|
54 |
2 |
public class LRUMap |
55 |
|
implements Map |
56 |
|
{ |
57 |
294 |
private final static Log log = LogFactory.getLog( LRUMap.class ); |
58 |
|
|
59 |
|
|
60 |
|
private DoubleLinkedList list; |
61 |
|
|
62 |
|
|
63 |
|
protected Map map; |
64 |
|
|
65 |
1283 |
int hitCnt = 0; |
66 |
|
|
67 |
1283 |
int missCnt = 0; |
68 |
|
|
69 |
1283 |
int putCnt = 0; |
70 |
|
|
71 |
|
|
72 |
1283 |
int maxObjects = -1; |
73 |
|
|
74 |
|
|
75 |
1283 |
private int chunkSize = 1; |
76 |
|
|
77 |
|
|
78 |
|
|
79 |
|
|
80 |
|
|
81 |
|
|
82 |
|
|
83 |
10 |
public LRUMap() |
84 |
1273 |
{ |
85 |
1283 |
list = new DoubleLinkedList(); |
86 |
|
|
87 |
|
|
88 |
|
|
89 |
1283 |
map = new Hashtable(); |
90 |
|
|
91 |
1283 |
} |
92 |
|
|
93 |
|
|
94 |
|
|
95 |
|
|
96 |
|
|
97 |
|
|
98 |
|
public LRUMap( int maxObjects ) |
99 |
|
{ |
100 |
1275 |
this(); |
101 |
1275 |
this.maxObjects = maxObjects; |
102 |
1275 |
} |
103 |
|
|
104 |
|
|
105 |
|
|
106 |
|
|
107 |
|
|
108 |
|
|
109 |
|
public int size() |
110 |
|
{ |
111 |
112259 |
return map.size(); |
112 |
|
} |
113 |
|
|
114 |
|
|
115 |
|
|
116 |
|
|
117 |
|
|
118 |
|
|
119 |
|
public void clear() |
120 |
|
{ |
121 |
8 |
map.clear(); |
122 |
8 |
list.removeAll(); |
123 |
8 |
} |
124 |
|
|
125 |
|
|
126 |
|
|
127 |
|
|
128 |
|
|
129 |
|
|
130 |
|
public boolean isEmpty() |
131 |
|
{ |
132 |
0 |
return map.size() == 0; |
133 |
|
} |
134 |
|
|
135 |
|
|
136 |
|
|
137 |
|
|
138 |
|
|
139 |
|
|
140 |
|
public boolean containsKey( Object key ) |
141 |
|
{ |
142 |
761469 |
return map.containsKey( key ); |
143 |
|
} |
144 |
|
|
145 |
|
|
146 |
|
|
147 |
|
|
148 |
|
|
149 |
|
|
150 |
|
public boolean containsValue( Object value ) |
151 |
|
{ |
152 |
0 |
return map.containsValue( value ); |
153 |
|
} |
154 |
|
|
155 |
|
|
156 |
|
|
157 |
|
|
158 |
|
|
159 |
|
public Collection values() |
160 |
|
{ |
161 |
0 |
return map.values(); |
162 |
|
} |
163 |
|
|
164 |
|
|
165 |
|
|
166 |
|
|
167 |
|
|
168 |
|
public void putAll( Map source ) |
169 |
|
{ |
170 |
107 |
if ( source != null ) |
171 |
|
{ |
172 |
107 |
Set entries = source.entrySet(); |
173 |
107 |
Iterator it = entries.iterator(); |
174 |
216128 |
while ( it.hasNext() ) |
175 |
|
{ |
176 |
216021 |
Entry entry = (Entry) it.next(); |
177 |
216021 |
this.put( entry.getKey(), entry.getValue() ); |
178 |
216021 |
} |
179 |
|
} |
180 |
107 |
} |
181 |
|
|
182 |
|
|
183 |
|
|
184 |
|
|
185 |
|
|
186 |
|
public Object get( Object key ) |
187 |
|
{ |
188 |
3427341 |
Object retVal = null; |
189 |
|
|
190 |
3430311 |
if ( log.isDebugEnabled() ) |
191 |
|
{ |
192 |
0 |
log.debug( "getting item for key " + key ); |
193 |
|
} |
194 |
|
|
195 |
3429025 |
LRUElementDescriptor me = (LRUElementDescriptor) map.get( key ); |
196 |
|
|
197 |
3428592 |
if ( me != null ) |
198 |
|
{ |
199 |
1339676 |
hitCnt++; |
200 |
1339661 |
if ( log.isDebugEnabled() ) |
201 |
|
{ |
202 |
0 |
log.debug( "LRUMap hit for " + key ); |
203 |
|
} |
204 |
|
|
205 |
1339610 |
retVal = me.getPayload(); |
206 |
|
|
207 |
1339468 |
list.makeFirst( me ); |
208 |
1283540 |
} |
209 |
|
else |
210 |
|
{ |
211 |
2090412 |
missCnt++; |
212 |
2090723 |
log.debug( "LRUMap miss for " + key ); |
213 |
|
} |
214 |
|
|
215 |
|
|
216 |
3428465 |
return retVal; |
217 |
|
} |
218 |
|
|
219 |
|
|
220 |
|
|
221 |
|
|
222 |
|
|
223 |
|
|
224 |
|
|
225 |
|
|
226 |
|
|
227 |
|
public Object getQuiet( Object key ) |
228 |
|
{ |
229 |
0 |
Object ce = null; |
230 |
|
|
231 |
0 |
LRUElementDescriptor me = (LRUElementDescriptor) map.get( key ); |
232 |
0 |
if ( me != null ) |
233 |
|
{ |
234 |
0 |
if ( log.isDebugEnabled() ) |
235 |
|
{ |
236 |
0 |
log.debug( "LRUMap quiet hit for " + key ); |
237 |
|
} |
238 |
|
|
239 |
0 |
ce = me.getPayload(); |
240 |
0 |
} |
241 |
0 |
else if ( log.isDebugEnabled() ) |
242 |
|
{ |
243 |
0 |
log.debug( "LRUMap quiet miss for " + key ); |
244 |
|
} |
245 |
|
|
246 |
0 |
return ce; |
247 |
|
} |
248 |
|
|
249 |
|
|
250 |
|
|
251 |
|
|
252 |
|
|
253 |
|
public Object remove( Object key ) |
254 |
|
{ |
255 |
1150354 |
if ( log.isDebugEnabled() ) |
256 |
|
{ |
257 |
0 |
log.debug( "removing item for key: " + key ); |
258 |
|
} |
259 |
|
|
260 |
|
|
261 |
1150187 |
LRUElementDescriptor me = (LRUElementDescriptor) map.remove( key ); |
262 |
|
|
263 |
1150492 |
if ( me != null ) |
264 |
|
{ |
265 |
848516 |
list.remove( me ); |
266 |
|
|
267 |
848493 |
return me.getPayload(); |
268 |
|
} |
269 |
|
|
270 |
302119 |
return null; |
271 |
|
} |
272 |
|
|
273 |
|
|
274 |
|
|
275 |
|
|
276 |
|
|
277 |
|
public Object put( Object key, Object value ) |
278 |
|
{ |
279 |
1858453 |
putCnt++; |
280 |
|
|
281 |
1858505 |
LRUElementDescriptor old = null; |
282 |
1924219 |
synchronized ( this ) |
283 |
|
{ |
284 |
|
|
285 |
1858382 |
addFirst( key, value ); |
286 |
|
|
287 |
1858712 |
old = (LRUElementDescriptor) map.put( ( (LRUElementDescriptor) list.getFirst() ).getKey(), list.getFirst() ); |
288 |
|
|
289 |
|
|
290 |
1858714 |
if ( old != null && ( (LRUElementDescriptor) list.getFirst() ).getKey().equals( old.getKey() ) ) |
291 |
|
{ |
292 |
87621 |
list.remove( old ); |
293 |
|
} |
294 |
1792580 |
} |
295 |
|
|
296 |
1858549 |
int size = map.size(); |
297 |
|
|
298 |
|
|
299 |
1858465 |
if ( this.maxObjects >= 0 && size > class="keyword">this.maxObjects ) |
300 |
|
{ |
301 |
215693 |
if ( log.isDebugEnabled() ) |
302 |
|
{ |
303 |
0 |
log.debug( "In memory limit reached, removing least recently used." ); |
304 |
|
} |
305 |
|
|
306 |
|
|
307 |
215693 |
int chunkSizeCorrected = Math.min( size, getChunkSize() ); |
308 |
|
|
309 |
215693 |
if ( log.isDebugEnabled() ) |
310 |
|
{ |
311 |
0 |
log.debug( "About to remove the least recently used. map size: " + size + ", max objects: " |
312 |
|
+ this.maxObjects + ", items to spool: " + chunkSizeCorrected ); |
313 |
|
} |
314 |
|
|
315 |
|
|
316 |
|
|
317 |
|
|
318 |
|
|
319 |
431380 |
for ( int i = 0; i < chunkSizeCorrected; i++ ) |
320 |
|
{ |
321 |
225694 |
synchronized ( this ) |
322 |
|
{ |
323 |
215693 |
if ( list.getLast() != null ) |
324 |
|
{ |
325 |
215693 |
if ( ( (LRUElementDescriptor) list.getLast() ) != null ) |
326 |
|
{ |
327 |
225694 |
processRemovedLRU( ( (LRUElementDescriptor) list.getLast() ).getKey(), |
328 |
10001 |
( (LRUElementDescriptor) list.getLast() ).getPayload() ); |
329 |
215687 |
if ( !map.containsKey( ( (LRUElementDescriptor) list.getLast() ).getKey() ) ) |
330 |
|
{ |
331 |
0 |
log.error( "update: map does not contain key: " |
332 |
|
+ ( (LRUElementDescriptor) list.getLast() ).getKey() ); |
333 |
0 |
verifyCache(); |
334 |
|
} |
335 |
215687 |
if ( map.remove( ( (LRUElementDescriptor) list.getLast() ).getKey() ) == null ) |
336 |
|
{ |
337 |
0 |
log.warn( "update: remove failed for key: " |
338 |
|
+ ( (LRUElementDescriptor) list.getLast() ).getKey() ); |
339 |
0 |
verifyCache(); |
340 |
0 |
} |
341 |
|
} |
342 |
|
else |
343 |
|
{ |
344 |
0 |
throw new Error( "update: last.ce is null!" ); |
345 |
|
} |
346 |
215687 |
list.removeLast(); |
347 |
205686 |
} |
348 |
|
else |
349 |
|
{ |
350 |
0 |
verifyCache(); |
351 |
0 |
throw new Error( "update: last is null!" ); |
352 |
|
} |
353 |
205686 |
} |
354 |
|
} |
355 |
|
|
356 |
215687 |
if ( log.isDebugEnabled() ) |
357 |
|
{ |
358 |
0 |
log.debug( "update: After spool map size: " + map.size() ); |
359 |
|
} |
360 |
215687 |
if ( map.size() != dumpCacheSize() ) |
361 |
|
{ |
362 |
0 |
log.error( "update: After spool, size mismatch: map.size() = " + map.size() + ", linked list size = " |
363 |
|
+ dumpCacheSize() ); |
364 |
|
} |
365 |
|
} |
366 |
|
|
367 |
1858521 |
if ( old != null ) |
368 |
|
{ |
369 |
87621 |
return old.getPayload(); |
370 |
|
} |
371 |
1771027 |
return null; |
372 |
|
} |
373 |
|
|
374 |
|
|
375 |
|
|
376 |
|
|
377 |
|
|
378 |
|
|
379 |
|
|
380 |
|
private synchronized void addFirst( Object key, Object val ) |
381 |
|
{ |
382 |
|
|
383 |
1858530 |
LRUElementDescriptor me = new LRUElementDescriptor( key, val ); |
384 |
1858266 |
list.addFirst( me ); |
385 |
1858041 |
return; |
386 |
|
} |
387 |
|
|
388 |
|
|
389 |
|
|
390 |
|
|
391 |
|
|
392 |
|
|
393 |
|
private int dumpCacheSize() |
394 |
|
{ |
395 |
215688 |
return list.size(); |
396 |
|
} |
397 |
|
|
398 |
|
|
399 |
|
|
400 |
|
|
401 |
|
public void dumpCacheEntries() |
402 |
|
{ |
403 |
0 |
log.debug( "dumpingCacheEntries" ); |
404 |
0 |
for ( LRUElementDescriptor me = (LRUElementDescriptor) list.getFirst(); me != null; me = (LRUElementDescriptor) me.next ) |
405 |
|
{ |
406 |
0 |
if ( log.isDebugEnabled() ) |
407 |
|
{ |
408 |
0 |
log.debug( "dumpCacheEntries> key=" + me.getKey() + ", val=" + me.getPayload() ); |
409 |
|
} |
410 |
|
} |
411 |
0 |
} |
412 |
|
|
413 |
|
|
414 |
|
|
415 |
|
|
416 |
|
public void dumpMap() |
417 |
|
{ |
418 |
0 |
log.debug( "dumpingMap" ); |
419 |
0 |
for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); ) |
420 |
|
{ |
421 |
0 |
Map.Entry e = (Map.Entry) itr.next(); |
422 |
0 |
LRUElementDescriptor me = (LRUElementDescriptor) e.getValue(); |
423 |
0 |
if ( log.isDebugEnabled() ) |
424 |
|
{ |
425 |
0 |
log.debug( "dumpMap> key=" + e.getKey() + ", val=" + me.getPayload() ); |
426 |
|
} |
427 |
0 |
} |
428 |
0 |
} |
429 |
|
|
430 |
|
|
431 |
|
|
432 |
|
|
433 |
|
|
434 |
|
protected void verifyCache() |
435 |
|
{ |
436 |
0 |
if ( !log.isDebugEnabled() ) |
437 |
|
{ |
438 |
0 |
return; |
439 |
|
} |
440 |
|
|
441 |
0 |
boolean found = false; |
442 |
0 |
log.debug( "verifycache: mapContains " + map.size() + " elements, linked list contains " + dumpCacheSize() |
443 |
|
+ " elements" ); |
444 |
0 |
log.debug( "verifycache: checking linked list by key " ); |
445 |
0 |
for ( LRUElementDescriptor li = (LRUElementDescriptor) list.getFirst(); li != null; li = (LRUElementDescriptor) li.next ) |
446 |
|
{ |
447 |
0 |
Object key = li.getKey(); |
448 |
0 |
if ( !map.containsKey( key ) ) |
449 |
|
{ |
450 |
0 |
log.error( "verifycache: map does not contain key : " + li.getKey() ); |
451 |
0 |
log.error( "li.hashcode=" + li.getKey().hashCode() ); |
452 |
0 |
log.error( "key class=" + key.getClass() ); |
453 |
0 |
log.error( "key hashcode=" + key.hashCode() ); |
454 |
0 |
log.error( "key toString=" + key.toString() ); |
455 |
0 |
if ( key instanceof GroupAttrName ) |
456 |
|
{ |
457 |
0 |
GroupAttrName name = (GroupAttrName) key; |
458 |
0 |
log.error( "GroupID hashcode=" + name.groupId.hashCode() ); |
459 |
0 |
log.error( "GroupID.class=" + name.groupId.getClass() ); |
460 |
0 |
log.error( "AttrName hashcode=" + name.attrName.hashCode() ); |
461 |
0 |
log.error( "AttrName.class=" + name.attrName.getClass() ); |
462 |
|
} |
463 |
0 |
dumpMap(); |
464 |
0 |
} |
465 |
0 |
else if ( map.get( li.getKey() ) == null ) |
466 |
|
{ |
467 |
0 |
log.error( "verifycache: linked list retrieval returned null for key: " + li.getKey() ); |
468 |
|
} |
469 |
|
} |
470 |
|
|
471 |
0 |
log.debug( "verifycache: checking linked list by value " ); |
472 |
0 |
for ( LRUElementDescriptor li3 = (LRUElementDescriptor) list.getFirst(); li3 != null; li3 = (LRUElementDescriptor) li3.next ) |
473 |
|
{ |
474 |
0 |
if ( map.containsValue( li3 ) == false ) |
475 |
|
{ |
476 |
0 |
log.error( "verifycache: map does not contain value : " + li3 ); |
477 |
0 |
dumpMap(); |
478 |
|
} |
479 |
|
} |
480 |
|
|
481 |
0 |
log.debug( "verifycache: checking via keysets!" ); |
482 |
0 |
for ( Iterator itr2 = map.keySet().iterator(); itr2.hasNext(); ) |
483 |
|
{ |
484 |
0 |
found = false; |
485 |
0 |
Serializable val = null; |
486 |
|
try |
487 |
|
{ |
488 |
0 |
val = (Serializable) itr2.next(); |
489 |
|
} |
490 |
0 |
catch ( NoSuchElementException nse ) |
491 |
|
{ |
492 |
0 |
log.error( "verifycache: no such element exception" ); |
493 |
0 |
} |
494 |
|
|
495 |
0 |
for ( LRUElementDescriptor li2 = (LRUElementDescriptor) list.getFirst(); li2 != null; li2 = (LRUElementDescriptor) li2.next ) |
496 |
|
{ |
497 |
0 |
if ( val.equals( li2.getKey() ) ) |
498 |
|
{ |
499 |
0 |
found = true; |
500 |
0 |
break; |
501 |
|
} |
502 |
|
} |
503 |
0 |
if ( !found ) |
504 |
|
{ |
505 |
0 |
log.error( "verifycache: key not found in list : " + val ); |
506 |
0 |
dumpCacheEntries(); |
507 |
0 |
if ( map.containsKey( val ) ) |
508 |
|
{ |
509 |
0 |
log.error( "verifycache: map contains key" ); |
510 |
0 |
} |
511 |
|
else |
512 |
|
{ |
513 |
0 |
log.error( "verifycache: map does NOT contain key, what the HECK!" ); |
514 |
|
} |
515 |
|
} |
516 |
0 |
} |
517 |
0 |
} |
518 |
|
|
519 |
|
|
520 |
|
|
521 |
|
|
522 |
|
|
523 |
|
|
524 |
|
protected void verifyCache( Object key ) |
525 |
|
{ |
526 |
0 |
if ( !log.isDebugEnabled() ) |
527 |
|
{ |
528 |
0 |
return; |
529 |
|
} |
530 |
|
|
531 |
0 |
boolean found = false; |
532 |
|
|
533 |
|
|
534 |
0 |
for ( LRUElementDescriptor li = (LRUElementDescriptor) list.getFirst(); li != null; li = (LRUElementDescriptor) li.next ) |
535 |
|
{ |
536 |
0 |
if ( li.getKey() == key ) |
537 |
|
{ |
538 |
0 |
found = true; |
539 |
0 |
log.debug( "verifycache(key) key match: " + key ); |
540 |
0 |
break; |
541 |
|
} |
542 |
|
} |
543 |
0 |
if ( !found ) |
544 |
|
{ |
545 |
0 |
log.error( "verifycache(key), couldn't find key! : " + key ); |
546 |
|
} |
547 |
0 |
} |
548 |
|
|
549 |
|
|
550 |
|
|
551 |
|
|
552 |
|
|
553 |
|
|
554 |
|
|
555 |
|
|
556 |
|
protected void processRemovedLRU( Object key, Object value ) |
557 |
|
{ |
558 |
80008 |
if ( log.isDebugEnabled() ) |
559 |
|
{ |
560 |
0 |
log.debug( "Removing key: [" + key + "] from LRUMap store, value = [" + value + "]" ); |
561 |
0 |
log.debug( "LRUMap store size: '" + this.size() + "'." ); |
562 |
|
} |
563 |
80008 |
} |
564 |
|
|
565 |
|
|
566 |
|
|
567 |
|
|
568 |
|
|
569 |
|
|
570 |
|
public void setChunkSize( int chunkSize ) |
571 |
|
{ |
572 |
16 |
this.chunkSize = chunkSize; |
573 |
16 |
} |
574 |
|
|
575 |
|
|
576 |
|
|
577 |
|
|
578 |
|
public int getChunkSize() |
579 |
|
{ |
580 |
215693 |
return chunkSize; |
581 |
|
} |
582 |
|
|
583 |
|
|
584 |
|
|
585 |
|
|
586 |
|
public IStats getStatistics() |
587 |
|
{ |
588 |
24 |
IStats stats = new Stats(); |
589 |
24 |
stats.setTypeName( "LRUMap" ); |
590 |
|
|
591 |
24 |
ArrayList elems = new ArrayList(); |
592 |
|
|
593 |
24 |
IStatElement se = null; |
594 |
|
|
595 |
24 |
se = new StatElement(); |
596 |
24 |
se.setName( "List Size" ); |
597 |
24 |
se.setData( "" + list.size() ); |
598 |
24 |
elems.add( se ); |
599 |
|
|
600 |
24 |
se = new StatElement(); |
601 |
24 |
se.setName( "Map Size" ); |
602 |
24 |
se.setData( "" + map.size() ); |
603 |
24 |
elems.add( se ); |
604 |
|
|
605 |
24 |
se = new StatElement(); |
606 |
24 |
se.setName( "Put Count" ); |
607 |
24 |
se.setData( "" + putCnt ); |
608 |
24 |
elems.add( se ); |
609 |
|
|
610 |
24 |
se = new StatElement(); |
611 |
24 |
se.setName( "Hit Count" ); |
612 |
24 |
se.setData( "" + hitCnt ); |
613 |
24 |
elems.add( se ); |
614 |
|
|
615 |
24 |
se = new StatElement(); |
616 |
24 |
se.setName( "Miss Count" ); |
617 |
24 |
se.setData( "" + missCnt ); |
618 |
24 |
elems.add( se ); |
619 |
|
|
620 |
|
|
621 |
24 |
IStatElement[] ses = (IStatElement[]) elems.toArray( new StatElement[0] ); |
622 |
24 |
stats.setStatElements( ses ); |
623 |
|
|
624 |
24 |
return stats; |
625 |
|
} |
626 |
|
|
627 |
|
|
628 |
|
|
629 |
|
|
630 |
|
|
631 |
|
|
632 |
|
|
633 |
|
|
634 |
|
|
635 |
|
|
636 |
|
|
637 |
|
public synchronized Set entrySet() |
638 |
|
{ |
639 |
|
|
640 |
688 |
Set entries = map.entrySet(); |
641 |
|
|
642 |
687 |
Set unWrapped = new HashSet(); |
643 |
|
|
644 |
689 |
Iterator it = entries.iterator(); |
645 |
256027 |
while ( it.hasNext() ) |
646 |
|
{ |
647 |
255426 |
Entry pre = (Entry) it.next(); |
648 |
255488 |
Entry post = new LRUMapEntry( pre.getKey(), ( (LRUElementDescriptor) pre.getValue() ).getPayload() ); |
649 |
255536 |
unWrapped.add( post ); |
650 |
255620 |
} |
651 |
|
|
652 |
660 |
return unWrapped; |
653 |
|
} |
654 |
|
|
655 |
|
|
656 |
|
|
657 |
|
|
658 |
|
|
659 |
|
public Set keySet() |
660 |
|
{ |
661 |
|
|
662 |
0 |
return map.keySet(); |
663 |
|
} |
664 |
|
} |