001/** 002 * 003 * Copyright 2003-2005 Jive Software. 004 * 005 * Licensed under the Apache License, Version 2.0 (the "License"); 006 * you may not use this file except in compliance with the License. 007 * You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.jivesoftware.smack.util; 018 019import java.util.*; 020import java.util.logging.Logger; 021 022/** 023 * A specialized Map that is size-limited (using an LRU algorithm) and 024 * has an optional expiration time for cache items. The Map is thread-safe.<p> 025 * 026 * The algorithm for cache is as follows: a HashMap is maintained for fast 027 * object lookup. Two linked lists are maintained: one keeps objects in the 028 * order they are accessed from cache, the other keeps objects in the order 029 * they were originally added to cache. When objects are added to cache, they 030 * are first wrapped by a CacheObject which maintains the following pieces 031 * of information:<ul> 032 * <li> A pointer to the node in the linked list that maintains accessed 033 * order for the object. Keeping a reference to the node lets us avoid 034 * linear scans of the linked list. 035 * <li> A pointer to the node in the linked list that maintains the age 036 * of the object in cache. Keeping a reference to the node lets us avoid 037 * linear scans of the linked list.</ul> 038 * <p/> 039 * To get an object from cache, a hash lookup is performed to get a reference 040 * to the CacheObject that wraps the real object we are looking for. 041 * The object is subsequently moved to the front of the accessed linked list 042 * and any necessary cache cleanups are performed. Cache deletion and expiration 043 * is performed as needed. 044 * 045 * @author Matt Tucker 046 */ 047public class Cache<K, V> implements Map<K, V> { 048 private static final Logger LOGGER = Logger.getLogger(Cache.class.getName()); 049 /** 050 * The map the keys and values are stored in. 051 */ 052 protected Map<K, CacheObject<V>> map; 053 054 /** 055 * Linked list to maintain order that cache objects are accessed 056 * in, most used to least used. 057 */ 058 protected LinkedList lastAccessedList; 059 060 /** 061 * Linked list to maintain time that cache objects were initially added 062 * to the cache, most recently added to oldest added. 063 */ 064 protected LinkedList ageList; 065 066 /** 067 * Maximum number of items the cache will hold. 068 */ 069 protected int maxCacheSize; 070 071 /** 072 * Maximum length of time objects can exist in cache before expiring. 073 */ 074 protected long maxLifetime; 075 076 /** 077 * Maintain the number of cache hits and misses. A cache hit occurs every 078 * time the get method is called and the cache contains the requested 079 * object. A cache miss represents the opposite occurence.<p> 080 * 081 * Keeping track of cache hits and misses lets one measure how efficient 082 * the cache is; the higher the percentage of hits, the more efficient. 083 */ 084 protected long cacheHits, cacheMisses = 0L; 085 086 /** 087 * Create a new cache and specify the maximum size of for the cache in 088 * bytes, and the maximum lifetime of objects. 089 * 090 * @param maxSize the maximum number of objects the cache will hold. -1 091 * means the cache has no max size. 092 * @param maxLifetime the maximum amount of time (in ms) objects can exist in 093 * cache before being deleted. -1 means objects never expire. 094 */ 095 public Cache(int maxSize, long maxLifetime) { 096 if (maxSize == 0) { 097 throw new IllegalArgumentException("Max cache size cannot be 0."); 098 } 099 this.maxCacheSize = maxSize; 100 this.maxLifetime = maxLifetime; 101 102 // Our primary data structure is a hash map. The default capacity of 11 103 // is too small in almost all cases, so we set it bigger. 104 map = new HashMap<K, CacheObject<V>>(103); 105 106 lastAccessedList = new LinkedList(); 107 ageList = new LinkedList(); 108 } 109 110 public synchronized V put(K key, V value) { 111 V oldValue = null; 112 // Delete an old entry if it exists. 113 if (map.containsKey(key)) { 114 oldValue = remove(key, true); 115 } 116 117 CacheObject<V> cacheObject = new CacheObject<V>(value); 118 map.put(key, cacheObject); 119 // Make an entry into the cache order list. 120 // Store the cache order list entry so that we can get back to it 121 // during later lookups. 122 cacheObject.lastAccessedListNode = lastAccessedList.addFirst(key); 123 // Add the object to the age list 124 LinkedListNode ageNode = ageList.addFirst(key); 125 ageNode.timestamp = System.currentTimeMillis(); 126 cacheObject.ageListNode = ageNode; 127 128 // If cache is too full, remove least used cache entries until it is not too full. 129 cullCache(); 130 131 return oldValue; 132 } 133 134 public synchronized V get(Object key) { 135 // First, clear all entries that have been in cache longer than the 136 // maximum defined age. 137 deleteExpiredEntries(); 138 139 CacheObject<V> cacheObject = map.get(key); 140 if (cacheObject == null) { 141 // The object didn't exist in cache, so increment cache misses. 142 cacheMisses++; 143 return null; 144 } 145 // Remove the object from it's current place in the cache order list, 146 // and re-insert it at the front of the list. 147 cacheObject.lastAccessedListNode.remove(); 148 lastAccessedList.addFirst(cacheObject.lastAccessedListNode); 149 150 // The object exists in cache, so increment cache hits. Also, increment 151 // the object's read count. 152 cacheHits++; 153 cacheObject.readCount++; 154 155 return cacheObject.object; 156 } 157 158 public synchronized V remove(Object key) { 159 return remove(key, false); 160 } 161 162 /* 163 * Remove operation with a flag so we can tell coherence if the remove was 164 * caused by cache internal processing such as eviction or loading 165 */ 166 public synchronized V remove(Object key, boolean internal) { 167 //noinspection SuspiciousMethodCalls 168 CacheObject<V> cacheObject = map.remove(key); 169 // If the object is not in cache, stop trying to remove it. 170 if (cacheObject == null) { 171 return null; 172 } 173 // Remove from the cache order list 174 cacheObject.lastAccessedListNode.remove(); 175 cacheObject.ageListNode.remove(); 176 // Remove references to linked list nodes 177 cacheObject.ageListNode = null; 178 cacheObject.lastAccessedListNode = null; 179 180 return cacheObject.object; 181 } 182 183 public synchronized void clear() { 184 Object[] keys = map.keySet().toArray(); 185 for (Object key : keys) { 186 remove(key); 187 } 188 189 // Now, reset all containers. 190 map.clear(); 191 lastAccessedList.clear(); 192 ageList.clear(); 193 194 cacheHits = 0; 195 cacheMisses = 0; 196 } 197 198 public synchronized int size() { 199 // First, clear all entries that have been in cache longer than the 200 // maximum defined age. 201 deleteExpiredEntries(); 202 203 return map.size(); 204 } 205 206 public synchronized boolean isEmpty() { 207 // First, clear all entries that have been in cache longer than the 208 // maximum defined age. 209 deleteExpiredEntries(); 210 211 return map.isEmpty(); 212 } 213 214 public synchronized Collection<V> values() { 215 // First, clear all entries that have been in cache longer than the 216 // maximum defined age. 217 deleteExpiredEntries(); 218 219 return Collections.unmodifiableCollection(new AbstractCollection<V>() { 220 Collection<CacheObject<V>> values = map.values(); 221 public Iterator<V> iterator() { 222 return new Iterator<V>() { 223 Iterator<CacheObject<V>> it = values.iterator(); 224 225 public boolean hasNext() { 226 return it.hasNext(); 227 } 228 229 public V next() { 230 return it.next().object; 231 } 232 233 public void remove() { 234 it.remove(); 235 } 236 }; 237 } 238 239 public int size() { 240 return values.size(); 241 } 242 }); 243 } 244 245 public synchronized boolean containsKey(Object key) { 246 // First, clear all entries that have been in cache longer than the 247 // maximum defined age. 248 deleteExpiredEntries(); 249 250 return map.containsKey(key); 251 } 252 253 @SuppressWarnings("unchecked") 254 public void putAll(Map<? extends K, ? extends V> map) { 255 for (Entry<? extends K, ? extends V> entry : map.entrySet()) { 256 V value = entry.getValue(); 257 // If the map is another DefaultCache instance than the 258 // entry values will be CacheObject instances that need 259 // to be converted to the normal object form. 260 if (value instanceof CacheObject) { 261 //noinspection unchecked 262 value = ((CacheObject<V>) value).object; 263 } 264 put(entry.getKey(), value); 265 } 266 } 267 268 public synchronized boolean containsValue(Object value) { 269 // First, clear all entries that have been in cache longer than the 270 // maximum defined age. 271 deleteExpiredEntries(); 272 273 //noinspection unchecked 274 @SuppressWarnings("unchecked") 275 CacheObject<V> cacheObject = new CacheObject<V>((V) value); 276 277 return map.containsValue(cacheObject); 278 } 279 280 public synchronized Set<Map.Entry<K, V>> entrySet() { 281 // Warning -- this method returns CacheObject instances and not Objects 282 // in the same form they were put into cache. 283 284 // First, clear all entries that have been in cache longer than the 285 // maximum defined age. 286 deleteExpiredEntries(); 287 288 return new AbstractSet<Map.Entry<K, V>>() { 289 private final Set<Map.Entry<K, CacheObject<V>>> set = map.entrySet(); 290 291 public Iterator<Entry<K, V>> iterator() { 292 return new Iterator<Entry<K, V>>() { 293 private final Iterator<Entry<K, CacheObject<V>>> it = set.iterator(); 294 public boolean hasNext() { 295 return it.hasNext(); 296 } 297 298 public Entry<K, V> next() { 299 Map.Entry<K, CacheObject<V>> entry = it.next(); 300 return new AbstractMapEntry<K, V>(entry.getKey(), entry.getValue().object) { 301 @Override 302 public V setValue(V value) { 303 throw new UnsupportedOperationException("Cannot set"); 304 } 305 }; 306 } 307 308 public void remove() { 309 it.remove(); 310 } 311 }; 312 313 } 314 315 public int size() { 316 return set.size(); 317 } 318 }; 319 } 320 321 public synchronized Set<K> keySet() { 322 // First, clear all entries that have been in cache longer than the 323 // maximum defined age. 324 deleteExpiredEntries(); 325 326 return Collections.unmodifiableSet(map.keySet()); 327 } 328 329 public long getCacheHits() { 330 return cacheHits; 331 } 332 333 public long getCacheMisses() { 334 return cacheMisses; 335 } 336 337 public int getMaxCacheSize() { 338 return maxCacheSize; 339 } 340 341 public synchronized void setMaxCacheSize(int maxCacheSize) { 342 this.maxCacheSize = maxCacheSize; 343 // It's possible that the new max size is smaller than our current cache 344 // size. If so, we need to delete infrequently used items. 345 cullCache(); 346 } 347 348 public long getMaxLifetime() { 349 return maxLifetime; 350 } 351 352 public void setMaxLifetime(long maxLifetime) { 353 this.maxLifetime = maxLifetime; 354 } 355 356 /** 357 * Clears all entries out of cache where the entries are older than the 358 * maximum defined age. 359 */ 360 protected synchronized void deleteExpiredEntries() { 361 // Check if expiration is turned on. 362 if (maxLifetime <= 0) { 363 return; 364 } 365 366 // Remove all old entries. To do this, we remove objects from the end 367 // of the linked list until they are no longer too old. We get to avoid 368 // any hash lookups or looking at any more objects than is strictly 369 // neccessary. 370 LinkedListNode node = ageList.getLast(); 371 // If there are no entries in the age list, return. 372 if (node == null) { 373 return; 374 } 375 376 // Determine the expireTime, which is the moment in time that elements 377 // should expire from cache. Then, we can do an easy check to see 378 // if the expire time is greater than the expire time. 379 long expireTime = System.currentTimeMillis() - maxLifetime; 380 381 while (expireTime > node.timestamp) { 382 if (remove(node.object, true) == null) { 383 LOGGER.warning("Error attempting to remove(" + node.object.toString() + ") - cacheObject not found in cache!"); 384 // remove from the ageList 385 node.remove(); 386 } 387 388 // Get the next node. 389 node = ageList.getLast(); 390 // If there are no more entries in the age list, return. 391 if (node == null) { 392 return; 393 } 394 } 395 } 396 397 /** 398 * Removes the least recently used elements if the cache size is greater than 399 * or equal to the maximum allowed size until the cache is at least 10% empty. 400 */ 401 protected synchronized void cullCache() { 402 // Check if a max cache size is defined. 403 if (maxCacheSize < 0) { 404 return; 405 } 406 407 // See if the cache is too big. If so, clean out cache until it's 10% free. 408 if (map.size() > maxCacheSize) { 409 // First, delete any old entries to see how much memory that frees. 410 deleteExpiredEntries(); 411 // Next, delete the least recently used elements until 10% of the cache 412 // has been freed. 413 int desiredSize = (int) (maxCacheSize * .90); 414 for (int i=map.size(); i>desiredSize; i--) { 415 // Get the key and invoke the remove method on it. 416 if (remove(lastAccessedList.getLast().object, true) == null) { 417 LOGGER.warning("Error attempting to cullCache with remove(" + lastAccessedList.getLast().object.toString() + ") - cacheObject not found in cache!"); 418 lastAccessedList.getLast().remove(); 419 } 420 } 421 } 422 } 423 424 /** 425 * Wrapper for all objects put into cache. It's primary purpose is to maintain 426 * references to the linked lists that maintain the creation time of the object 427 * and the ordering of the most used objects. 428 * 429 * This class is optimized for speed rather than strictly correct encapsulation. 430 */ 431 private static class CacheObject<V> { 432 433 /** 434 * Underlying object wrapped by the CacheObject. 435 */ 436 public V object; 437 438 /** 439 * A reference to the node in the cache order list. We keep the reference 440 * here to avoid linear scans of the list. Every time the object is 441 * accessed, the node is removed from its current spot in the list and 442 * moved to the front. 443 */ 444 public LinkedListNode lastAccessedListNode; 445 446 /** 447 * A reference to the node in the age order list. We keep the reference 448 * here to avoid linear scans of the list. The reference is used if the 449 * object has to be deleted from the list. 450 */ 451 public LinkedListNode ageListNode; 452 453 /** 454 * A count of the number of times the object has been read from cache. 455 */ 456 @SuppressWarnings("unused") 457 public int readCount = 0; 458 459 /** 460 * Creates a new cache object wrapper. 461 * 462 * @param object the underlying Object to wrap. 463 */ 464 public CacheObject(V object) { 465 this.object = object; 466 } 467 468 public boolean equals(Object o) { 469 if (this == o) { 470 return true; 471 } 472 if (!(o instanceof CacheObject)) { 473 return false; 474 } 475 476 final CacheObject<?> cacheObject = (CacheObject<?>) o; 477 478 return object.equals(cacheObject.object); 479 480 } 481 482 public int hashCode() { 483 return object.hashCode(); 484 } 485 } 486 487 /** 488 * Simple LinkedList implementation. The main feature is that list nodes 489 * are public, which allows very fast delete operations when one has a 490 * reference to the node that is to be deleted.<p> 491 */ 492 private static class LinkedList { 493 494 /** 495 * The root of the list keeps a reference to both the first and last 496 * elements of the list. 497 */ 498 private LinkedListNode head = new LinkedListNode("head", null, null); 499 500 /** 501 * Creates a new linked list. 502 */ 503 public LinkedList() { 504 head.next = head.previous = head; 505 } 506 507 /** 508 * Returns the first linked list node in the list. 509 * 510 * @return the first element of the list. 511 */ 512 @SuppressWarnings("unused") 513 public LinkedListNode getFirst() { 514 LinkedListNode node = head.next; 515 if (node == head) { 516 return null; 517 } 518 return node; 519 } 520 521 /** 522 * Returns the last linked list node in the list. 523 * 524 * @return the last element of the list. 525 */ 526 public LinkedListNode getLast() { 527 LinkedListNode node = head.previous; 528 if (node == head) { 529 return null; 530 } 531 return node; 532 } 533 534 /** 535 * Adds a node to the beginning of the list. 536 * 537 * @param node the node to add to the beginning of the list. 538 * @return the node 539 */ 540 public LinkedListNode addFirst(LinkedListNode node) { 541 node.next = head.next; 542 node.previous = head; 543 node.previous.next = node; 544 node.next.previous = node; 545 return node; 546 } 547 548 /** 549 * Adds an object to the beginning of the list by automatically creating a 550 * a new node and adding it to the beginning of the list. 551 * 552 * @param object the object to add to the beginning of the list. 553 * @return the node created to wrap the object. 554 */ 555 public LinkedListNode addFirst(Object object) { 556 LinkedListNode node = new LinkedListNode(object, head.next, head); 557 node.previous.next = node; 558 node.next.previous = node; 559 return node; 560 } 561 562 /** 563 * Adds an object to the end of the list by automatically creating a 564 * a new node and adding it to the end of the list. 565 * 566 * @param object the object to add to the end of the list. 567 * @return the node created to wrap the object. 568 */ 569 @SuppressWarnings("unused") 570 public LinkedListNode addLast(Object object) { 571 LinkedListNode node = new LinkedListNode(object, head, head.previous); 572 node.previous.next = node; 573 node.next.previous = node; 574 return node; 575 } 576 577 /** 578 * Erases all elements in the list and re-initializes it. 579 */ 580 public void clear() { 581 //Remove all references in the list. 582 LinkedListNode node = getLast(); 583 while (node != null) { 584 node.remove(); 585 node = getLast(); 586 } 587 588 //Re-initialize. 589 head.next = head.previous = head; 590 } 591 592 /** 593 * Returns a String representation of the linked list with a comma 594 * delimited list of all the elements in the list. 595 * 596 * @return a String representation of the LinkedList. 597 */ 598 public String toString() { 599 LinkedListNode node = head.next; 600 StringBuilder buf = new StringBuilder(); 601 while (node != head) { 602 buf.append(node.toString()).append(", "); 603 node = node.next; 604 } 605 return buf.toString(); 606 } 607 } 608 609 /** 610 * Doubly linked node in a LinkedList. Most LinkedList implementations keep the 611 * equivalent of this class private. We make it public so that references 612 * to each node in the list can be maintained externally. 613 * 614 * Exposing this class lets us make remove operations very fast. Remove is 615 * built into this class and only requires two reference reassignments. If 616 * remove existed in the main LinkedList class, a linear scan would have to 617 * be performed to find the correct node to delete. 618 * 619 * The linked list implementation was specifically written for the Jive 620 * cache system. While it can be used as a general purpose linked list, for 621 * most applications, it is more suitable to use the linked list that is part 622 * of the Java Collections package. 623 */ 624 private static class LinkedListNode { 625 626 public LinkedListNode previous; 627 public LinkedListNode next; 628 public Object object; 629 630 /** 631 * This class is further customized for the Jive cache system. It 632 * maintains a timestamp of when a Cacheable object was first added to 633 * cache. Timestamps are stored as long values and represent the number 634 * of milliseconds passed since January 1, 1970 00:00:00.000 GMT.<p> 635 * 636 * The creation timestamp is used in the case that the cache has a 637 * maximum lifetime set. In that case, when 638 * [current time] - [creation time] > [max lifetime], the object will be 639 * deleted from cache. 640 */ 641 public long timestamp; 642 643 /** 644 * Constructs a new linked list node. 645 * 646 * @param object the Object that the node represents. 647 * @param next a reference to the next LinkedListNode in the list. 648 * @param previous a reference to the previous LinkedListNode in the list. 649 */ 650 public LinkedListNode(Object object, LinkedListNode next, 651 LinkedListNode previous) 652 { 653 this.object = object; 654 this.next = next; 655 this.previous = previous; 656 } 657 658 /** 659 * Removes this node from the linked list that it is a part of. 660 */ 661 public void remove() { 662 previous.next = next; 663 next.previous = previous; 664 } 665 666 /** 667 * Returns a String representation of the linked list node by calling the 668 * toString method of the node's object. 669 * 670 * @return a String representation of the LinkedListNode. 671 */ 672 public String toString() { 673 return object.toString(); 674 } 675 } 676 677 static class AbstractMapEntry<K, V> implements Map.Entry<K, V> { 678 final K key; 679 V value; 680 681 AbstractMapEntry(K key, V value) { 682 this.key = key; 683 this.value = value; 684 } 685 686 @Override 687 public K getKey() { 688 return key; 689 } 690 691 @Override 692 public V getValue() { 693 return value; 694 } 695 696 @Override 697 public V setValue(V value) { 698 V answer = this.value; 699 this.value = value; 700 return answer; 701 } 702 703 /** 704 * Compares this Map Entry with another Map Entry. 705 * <p/> 706 * Implemented per API documentation of {@link java.util.Map.Entry#equals(Object)} 707 * 708 * @param obj the object to compare to 709 * @return true if equal key and value 710 */ 711 @SuppressWarnings("rawtypes") 712 @Override 713 public boolean equals(Object obj) { 714 if (obj == this) { 715 return true; 716 } 717 if (obj instanceof Map.Entry == false) { 718 return false; 719 } 720 Map.Entry other = (Map.Entry) obj; 721 return (getKey() == null ? other.getKey() == null : getKey().equals(other.getKey())) 722 && (getValue() == null ? other.getValue() == null : getValue().equals( 723 other.getValue())); 724 } 725 726 /** 727 * Gets a hashCode compatible with the equals method. 728 * <p/> 729 * Implemented per API documentation of {@link java.util.Map.Entry#hashCode()} 730 * 731 * @return a suitable hash code 732 */ 733 @Override 734 public int hashCode() { 735 return (getKey() == null ? 0 : getKey().hashCode()) 736 ^ (getValue() == null ? 0 : getValue().hashCode()); 737 } 738 } 739}