001package org.apache.commons.jcs.utils.struct; 002 003/* 004 * Licensed to the Apache Software Foundation (ASF) under one 005 * or more contributor license agreements. See the NOTICE file 006 * distributed with this work for additional information 007 * regarding copyright ownership. The ASF licenses this file 008 * to you under the Apache License, Version 2.0 (the 009 * "License"); you may not use this file except in compliance 010 * with the License. You may obtain a copy of the License at 011 * 012 * http://www.apache.org/licenses/LICENSE-2.0 013 * 014 * Unless required by applicable law or agreed to in writing, 015 * software distributed under the License is distributed on an 016 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 017 * KIND, either express or implied. See the License for the 018 * specific language governing permissions and limitations 019 * under the License. 020 */ 021 022import java.io.Serializable; 023import java.util.ArrayList; 024import java.util.Collection; 025import java.util.HashSet; 026import java.util.Iterator; 027import java.util.List; 028import java.util.Map; 029import java.util.NoSuchElementException; 030import java.util.Set; 031import java.util.concurrent.ConcurrentHashMap; 032import java.util.concurrent.locks.Lock; 033import java.util.concurrent.locks.ReentrantLock; 034 035import org.apache.commons.jcs.engine.control.group.GroupAttrName; 036import org.apache.commons.jcs.engine.stats.StatElement; 037import org.apache.commons.jcs.engine.stats.Stats; 038import org.apache.commons.jcs.engine.stats.behavior.IStatElement; 039import org.apache.commons.jcs.engine.stats.behavior.IStats; 040import org.apache.commons.logging.Log; 041import org.apache.commons.logging.LogFactory; 042 043/** 044 * This is a simple LRUMap. It implements most of the map methods. It is not recommended that you 045 * use any but put, get, remove, and clear. 046 * <p> 047 * Children can implement the processRemovedLRU method if they want to handle the removal of the 048 * lest recently used item. 049 * <p> 050 * This class was abstracted out of the LRU Memory cache. Put, remove, and get should be thread 051 * safe. It uses a hashtable and our own double linked list. 052 * <p> 053 * Locking is done on the instance. 054 * <p> 055 * @author aaron smuts 056 */ 057public abstract class AbstractLRUMap<K, V> 058 implements Map<K, V> 059{ 060 /** The logger */ 061 private static final Log log = LogFactory.getLog( AbstractLRUMap.class ); 062 063 /** double linked list for lru */ 064 private final DoubleLinkedList<LRUElementDescriptor<K, V>> list; 065 066 /** Map where items are stored by key. */ 067 private Map<K, LRUElementDescriptor<K, V>> map; 068 069 /** stats */ 070 int hitCnt = 0; 071 072 /** stats */ 073 int missCnt = 0; 074 075 /** stats */ 076 int putCnt = 0; 077 078 /** make configurable */ 079 private int chunkSize = 1; 080 081 private final Lock lock = new ReentrantLock(); 082 083 /** 084 * This creates an unbounded version. Setting the max objects will result in spooling on 085 * subsequent puts. 086 */ 087 public AbstractLRUMap() 088 { 089 list = new DoubleLinkedList<LRUElementDescriptor<K, V>>(); 090 091 // normal hashtable is faster for 092 // sequential keys. 093 map = new ConcurrentHashMap<K, LRUElementDescriptor<K, V>>(); 094 } 095 096 097 /** 098 * This simply returns the number of elements in the map. 099 * <p> 100 * @see java.util.Map#size() 101 */ 102 @Override 103 public int size() 104 { 105 return map.size(); 106 } 107 108 /** 109 * This removes all the items. It clears the map and the double linked list. 110 * <p> 111 * @see java.util.Map#clear() 112 */ 113 @Override 114 public void clear() 115 { 116 lock.lock(); 117 try 118 { 119 map.clear(); 120 list.removeAll(); 121 } 122 finally 123 { 124 lock.unlock(); 125 } 126 } 127 128 /** 129 * Returns true if the map is empty. 130 * <p> 131 * @see java.util.Map#isEmpty() 132 */ 133 @Override 134 public boolean isEmpty() 135 { 136 return map.isEmpty(); 137 } 138 139 /** 140 * Returns true if the map contains an element for the supplied key. 141 * <p> 142 * @see java.util.Map#containsKey(java.lang.Object) 143 */ 144 @Override 145 public boolean containsKey( Object key ) 146 { 147 return map.containsKey( key ); 148 } 149 150 /** 151 * This is an expensive operation that determines if the object supplied is mapped to any key. 152 * <p> 153 * @see java.util.Map#containsValue(java.lang.Object) 154 */ 155 @Override 156 public boolean containsValue( Object value ) 157 { 158 return map.containsValue( value ); 159 } 160 161 /** 162 * @return map.values(); 163 */ 164 @Override 165 public Collection<V> values() 166 { 167 List<V> valueList = new ArrayList<V>(map.size()); 168 169 for (LRUElementDescriptor<K, V> value : map.values()) 170 { 171 valueList.add(value.getPayload()); 172 } 173 174 return valueList; 175 } 176 177 /** 178 * @param source 179 */ 180 @Override 181 public void putAll( Map<? extends K, ? extends V> source ) 182 { 183 if ( source != null ) 184 { 185 for (Map.Entry<? extends K, ? extends V> entry : source.entrySet()) 186 { 187 this.put( entry.getKey(), entry.getValue() ); 188 } 189 } 190 } 191 192 /** 193 * @param key 194 * @return Object 195 */ 196 @Override 197 public V get( Object key ) 198 { 199 V retVal = null; 200 201 if ( log.isDebugEnabled() ) 202 { 203 log.debug( "getting item for key " + key ); 204 } 205 206 LRUElementDescriptor<K, V> me = map.get( key ); 207 208 if ( me != null ) 209 { 210 hitCnt++; 211 if ( log.isDebugEnabled() ) 212 { 213 log.debug( "LRUMap hit for " + key ); 214 } 215 216 retVal = me.getPayload(); 217 218 list.makeFirst( me ); 219 } 220 else 221 { 222 missCnt++; 223 log.debug( "LRUMap miss for " + key ); 224 } 225 226 // verifyCache(); 227 return retVal; 228 } 229 230 /** 231 * This gets an element out of the map without adjusting it's position in the LRU. In other 232 * words, this does not count as being used. If the element is the last item in the list, it 233 * will still be the last time in the list. 234 * <p> 235 * @param key 236 * @return Object 237 */ 238 public V getQuiet( Object key ) 239 { 240 V ce = null; 241 242 LRUElementDescriptor<K, V> me = map.get( key ); 243 if ( me != null ) 244 { 245 if ( log.isDebugEnabled() ) 246 { 247 log.debug( "LRUMap quiet hit for " + key ); 248 } 249 250 ce = me.getPayload(); 251 } 252 else if ( log.isDebugEnabled() ) 253 { 254 log.debug( "LRUMap quiet miss for " + key ); 255 } 256 257 return ce; 258 } 259 260 /** 261 * @param key 262 * @return Object removed 263 */ 264 @Override 265 public V remove( Object key ) 266 { 267 if ( log.isDebugEnabled() ) 268 { 269 log.debug( "removing item for key: " + key ); 270 } 271 272 // remove single item. 273 lock.lock(); 274 try 275 { 276 LRUElementDescriptor<K, V> me = map.remove(key); 277 278 if (me != null) 279 { 280 list.remove(me); 281 return me.getPayload(); 282 } 283 } 284 finally 285 { 286 lock.unlock(); 287 } 288 289 return null; 290 } 291 292 /** 293 * @param key 294 * @param value 295 * @return Object 296 */ 297 @Override 298 public V put(K key, V value) 299 { 300 putCnt++; 301 302 LRUElementDescriptor<K, V> old = null; 303 lock.lock(); 304 try 305 { 306 // TODO address double synchronization of addFirst, use write lock 307 addFirst( key, value ); 308 // this must be synchronized 309 LRUElementDescriptor<K, V> first = list.getFirst(); 310 old = map.put(first.getKey(), first); 311 312 // If the node was the same as an existing node, remove it. 313 if ( old != null && first.getKey().equals(old.getKey())) 314 { 315 list.remove( old ); 316 } 317 } 318 finally 319 { 320 lock.unlock(); 321 } 322 323 // If the element limit is reached, we need to spool 324 325 if (shouldRemove()) 326 { 327 if (log.isDebugEnabled()) 328 { 329 log.debug( "In memory limit reached, removing least recently used." ); 330 } 331 332 // The spool will put them in a disk event queue, so there is no 333 // need to pre-queue the queuing. This would be a bit wasteful 334 // and wouldn't save much time in this synchronous call. 335 336 while ( shouldRemove() ) 337 { 338 lock.lock(); 339 try 340 { 341 LRUElementDescriptor<K, V> last = list.getLast(); 342 if (last != null) 343 { 344 processRemovedLRU(last.getKey(), last.getPayload()); 345 if (map.remove(last.getKey()) == null) 346 { 347 log.warn("update: remove failed for key: " 348 + last.getKey()); 349 verifyCache(); 350 } 351 list.removeLast(); 352 } 353 else 354 { 355 verifyCache(); 356 throw new Error("update: last is null!"); 357 } 358 } 359 finally 360 { 361 lock.unlock(); 362 } 363 } 364 365 if ( log.isDebugEnabled() ) 366 { 367 log.debug( "update: After spool map size: " + map.size() ); 368 } 369 if ( map.size() != dumpCacheSize() ) 370 { 371 log.error("update: After spool, size mismatch: map.size() = " + map.size() + ", linked list size = " 372 + dumpCacheSize()); 373 } 374 } 375 376 if ( old != null ) 377 { 378 return old.getPayload(); 379 } 380 return null; 381 } 382 383 protected abstract boolean shouldRemove(); 384 385 386 /** 387 * Adds a new node to the start of the link list. 388 * <p> 389 * @param key 390 * @param val The feature to be added to the First 391 */ 392 private void addFirst(K key, V val) 393 { 394 lock.lock(); 395 try 396 { 397 LRUElementDescriptor<K, V> me = new LRUElementDescriptor<K, V>(key, val); 398 list.addFirst( me ); 399 } 400 finally 401 { 402 lock.unlock(); 403 } 404 } 405 406 /** 407 * Returns the size of the list. 408 * <p> 409 * @return int 410 */ 411 private int dumpCacheSize() 412 { 413 return list.size(); 414 } 415 416 /** 417 * Dump the cache entries from first to list for debugging. 418 */ 419 @SuppressWarnings("unchecked") // No generics for public fields 420 public void dumpCacheEntries() 421 { 422 log.debug( "dumpingCacheEntries" ); 423 for ( LRUElementDescriptor<K, V> me = list.getFirst(); me != null; me = (LRUElementDescriptor<K, V>) me.next ) 424 { 425 if ( log.isDebugEnabled() ) 426 { 427 log.debug( "dumpCacheEntries> key=" + me.getKey() + ", val=" + me.getPayload() ); 428 } 429 } 430 } 431 432 /** 433 * Dump the cache map for debugging. 434 */ 435 public void dumpMap() 436 { 437 log.debug( "dumpingMap" ); 438 for (Map.Entry<K, LRUElementDescriptor<K, V>> e : map.entrySet()) 439 { 440 LRUElementDescriptor<K, V> me = e.getValue(); 441 if ( log.isDebugEnabled() ) 442 { 443 log.debug( "dumpMap> key=" + e.getKey() + ", val=" + me.getPayload() ); 444 } 445 } 446 } 447 448 /** 449 * Checks to see if all the items that should be in the cache are. Checks consistency between 450 * List and map. 451 */ 452 @SuppressWarnings("unchecked") // No generics for public fields 453 protected void verifyCache() 454 { 455 if ( !log.isDebugEnabled() ) 456 { 457 return; 458 } 459 460 boolean found = false; 461 log.debug( "verifycache: mapContains " + map.size() + " elements, linked list contains " + dumpCacheSize() 462 + " elements" ); 463 log.debug( "verifycache: checking linked list by key " ); 464 for (LRUElementDescriptor<K, V> li = list.getFirst(); li != null; li = (LRUElementDescriptor<K, V>) li.next ) 465 { 466 K key = li.getKey(); 467 if ( !map.containsKey( key ) ) 468 { 469 log.error( "verifycache: map does not contain key : " + li.getKey() ); 470 log.error( "li.hashcode=" + li.getKey().hashCode() ); 471 log.error( "key class=" + key.getClass() ); 472 log.error( "key hashcode=" + key.hashCode() ); 473 log.error( "key toString=" + key.toString() ); 474 if ( key instanceof GroupAttrName ) 475 { 476 GroupAttrName<?> name = (GroupAttrName<?>) key; 477 log.error( "GroupID hashcode=" + name.groupId.hashCode() ); 478 log.error( "GroupID.class=" + name.groupId.getClass() ); 479 log.error( "AttrName hashcode=" + name.attrName.hashCode() ); 480 log.error( "AttrName.class=" + name.attrName.getClass() ); 481 } 482 dumpMap(); 483 } 484 else if ( map.get( li.getKey() ) == null ) 485 { 486 log.error( "verifycache: linked list retrieval returned null for key: " + li.getKey() ); 487 } 488 } 489 490 log.debug( "verifycache: checking linked list by value " ); 491 for (LRUElementDescriptor<K, V> li3 = list.getFirst(); li3 != null; li3 = (LRUElementDescriptor<K, V>) li3.next ) 492 { 493 if ( map.containsValue( li3 ) == false ) 494 { 495 log.error( "verifycache: map does not contain value : " + li3 ); 496 dumpMap(); 497 } 498 } 499 500 log.debug( "verifycache: checking via keysets!" ); 501 for (Iterator<K> itr2 = map.keySet().iterator(); itr2.hasNext(); ) 502 { 503 found = false; 504 Serializable val = null; 505 try 506 { 507 val = (Serializable) itr2.next(); 508 } 509 catch ( NoSuchElementException nse ) 510 { 511 log.error( "verifycache: no such element exception" ); 512 continue; 513 } 514 515 for (LRUElementDescriptor<K, V> li2 = list.getFirst(); li2 != null; li2 = (LRUElementDescriptor<K, V>) li2.next ) 516 { 517 if ( val.equals( li2.getKey() ) ) 518 { 519 found = true; 520 break; 521 } 522 } 523 if ( !found ) 524 { 525 log.error( "verifycache: key not found in list : " + val ); 526 dumpCacheEntries(); 527 if ( map.containsKey( val ) ) 528 { 529 log.error( "verifycache: map contains key" ); 530 } 531 else 532 { 533 log.error( "verifycache: map does NOT contain key, what the HECK!" ); 534 } 535 } 536 } 537 } 538 539 /** 540 * Logs an error is an element that should be in the cache is not. 541 * <p> 542 * @param key 543 */ 544 @SuppressWarnings("unchecked") // No generics for public fields 545 protected void verifyCache( Object key ) 546 { 547 if ( !log.isDebugEnabled() ) 548 { 549 return; 550 } 551 552 boolean found = false; 553 554 // go through the linked list looking for the key 555 for (LRUElementDescriptor<K, V> li = list.getFirst(); li != null; li = (LRUElementDescriptor<K, V>) li.next ) 556 { 557 if ( li.getKey() == key ) 558 { 559 found = true; 560 log.debug( "verifycache(key) key match: " + key ); 561 break; 562 } 563 } 564 if ( !found ) 565 { 566 log.error( "verifycache(key), couldn't find key! : " + key ); 567 } 568 } 569 570 /** 571 * This is called when an item is removed from the LRU. We just log some information. 572 * <p> 573 * Children can implement this method for special behavior. 574 * @param key 575 * @param value 576 */ 577 protected void processRemovedLRU(K key, V value ) 578 { 579 if ( log.isDebugEnabled() ) 580 { 581 log.debug( "Removing key: [" + key + "] from LRUMap store, value = [" + value + "]" ); 582 log.debug( "LRUMap store size: '" + this.size() + "'." ); 583 } 584 } 585 586 /** 587 * The chunk size is the number of items to remove when the max is reached. By default it is 1. 588 * <p> 589 * @param chunkSize The chunkSize to set. 590 */ 591 public void setChunkSize( int chunkSize ) 592 { 593 this.chunkSize = chunkSize; 594 } 595 596 /** 597 * @return Returns the chunkSize. 598 */ 599 public int getChunkSize() 600 { 601 return chunkSize; 602 } 603 604 /** 605 * @return IStats 606 */ 607 public IStats getStatistics() 608 { 609 IStats stats = new Stats(); 610 stats.setTypeName( "LRUMap" ); 611 612 ArrayList<IStatElement<?>> elems = new ArrayList<IStatElement<?>>(); 613 614 elems.add(new StatElement<Integer>( "List Size", Integer.valueOf(list.size()) ) ); 615 elems.add(new StatElement<Integer>( "Map Size", Integer.valueOf(map.size()) ) ); 616 elems.add(new StatElement<Integer>( "Put Count", Integer.valueOf(putCnt) ) ); 617 elems.add(new StatElement<Integer>( "Hit Count", Integer.valueOf(hitCnt) ) ); 618 elems.add(new StatElement<Integer>( "Miss Count", Integer.valueOf(missCnt) ) ); 619 620 stats.setStatElements( elems ); 621 622 return stats; 623 } 624 625 /** 626 * This returns a set of entries. Our LRUMapEntry is used since the value stored in the 627 * underlying map is a node in the double linked list. We wouldn't want to return this to the 628 * client, so we construct a new entry with the payload of the node. 629 * <p> 630 * TODO we should return out own set wrapper, so we can avoid the extra object creation if it 631 * isn't necessary. 632 * <p> 633 * @see java.util.Map#entrySet() 634 */ 635 @Override 636 public Set<Map.Entry<K, V>> entrySet() 637 { 638 lock.lock(); 639 try 640 { 641 // TODO we should return a defensive copy 642 Set<Map.Entry<K, LRUElementDescriptor<K, V>>> entries = map.entrySet(); 643 Set<Map.Entry<K, V>> unWrapped = new HashSet<Map.Entry<K, V>>(); 644 645 for (Map.Entry<K, LRUElementDescriptor<K, V>> pre : entries) { 646 Map.Entry<K, V> post = new LRUMapEntry<K, V>(pre.getKey(), pre.getValue().getPayload()); 647 unWrapped.add(post); 648 } 649 650 return unWrapped; 651 } 652 finally 653 { 654 lock.unlock(); 655 } 656 } 657 658 /** 659 * @return map.keySet(); 660 */ 661 @Override 662 public Set<K> keySet() 663 { 664 // TODO fix this, it needs to return the keys inside the wrappers. 665 return map.keySet(); 666 } 667 668}