Shuyi Chen | d7955ce | 2013-05-22 14:51:55 -0700 | [diff] [blame] | 1 | /** |
| 2 | * $Revision: 1456 $ |
| 3 | * $Date: 2005-06-01 22:04:54 -0700 (Wed, 01 Jun 2005) $ |
| 4 | * |
| 5 | * Copyright 2003-2005 Jive Software. |
| 6 | * |
| 7 | * All rights reserved. Licensed under the Apache License, Version 2.0 (the "License"); |
| 8 | * you may not use this file except in compliance with the License. |
| 9 | * You may obtain a copy of the License at |
| 10 | * |
| 11 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 12 | * |
| 13 | * Unless required by applicable law or agreed to in writing, software |
| 14 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 15 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 16 | * See the License for the specific language governing permissions and |
| 17 | * limitations under the License. |
| 18 | */ |
| 19 | |
| 20 | package org.jivesoftware.smack.util; |
| 21 | |
| 22 | import org.jivesoftware.smack.util.collections.AbstractMapEntry; |
| 23 | |
| 24 | import java.util.*; |
| 25 | |
| 26 | /** |
| 27 | * A specialized Map that is size-limited (using an LRU algorithm) and |
| 28 | * has an optional expiration time for cache items. The Map is thread-safe.<p> |
| 29 | * |
| 30 | * The algorithm for cache is as follows: a HashMap is maintained for fast |
| 31 | * object lookup. Two linked lists are maintained: one keeps objects in the |
| 32 | * order they are accessed from cache, the other keeps objects in the order |
| 33 | * they were originally added to cache. When objects are added to cache, they |
| 34 | * are first wrapped by a CacheObject which maintains the following pieces |
| 35 | * of information:<ul> |
| 36 | * <li> A pointer to the node in the linked list that maintains accessed |
| 37 | * order for the object. Keeping a reference to the node lets us avoid |
| 38 | * linear scans of the linked list. |
| 39 | * <li> A pointer to the node in the linked list that maintains the age |
| 40 | * of the object in cache. Keeping a reference to the node lets us avoid |
| 41 | * linear scans of the linked list.</ul> |
| 42 | * <p/> |
| 43 | * To get an object from cache, a hash lookup is performed to get a reference |
| 44 | * to the CacheObject that wraps the real object we are looking for. |
| 45 | * The object is subsequently moved to the front of the accessed linked list |
| 46 | * and any necessary cache cleanups are performed. Cache deletion and expiration |
| 47 | * is performed as needed. |
| 48 | * |
| 49 | * @author Matt Tucker |
| 50 | */ |
| 51 | public class Cache<K, V> implements Map<K, V> { |
| 52 | |
| 53 | /** |
| 54 | * The map the keys and values are stored in. |
| 55 | */ |
| 56 | protected Map<K, CacheObject<V>> map; |
| 57 | |
| 58 | /** |
| 59 | * Linked list to maintain order that cache objects are accessed |
| 60 | * in, most used to least used. |
| 61 | */ |
| 62 | protected LinkedList lastAccessedList; |
| 63 | |
| 64 | /** |
| 65 | * Linked list to maintain time that cache objects were initially added |
| 66 | * to the cache, most recently added to oldest added. |
| 67 | */ |
| 68 | protected LinkedList ageList; |
| 69 | |
| 70 | /** |
| 71 | * Maximum number of items the cache will hold. |
| 72 | */ |
| 73 | protected int maxCacheSize; |
| 74 | |
| 75 | /** |
| 76 | * Maximum length of time objects can exist in cache before expiring. |
| 77 | */ |
| 78 | protected long maxLifetime; |
| 79 | |
| 80 | /** |
| 81 | * Maintain the number of cache hits and misses. A cache hit occurs every |
| 82 | * time the get method is called and the cache contains the requested |
| 83 | * object. A cache miss represents the opposite occurence.<p> |
| 84 | * |
| 85 | * Keeping track of cache hits and misses lets one measure how efficient |
| 86 | * the cache is; the higher the percentage of hits, the more efficient. |
| 87 | */ |
| 88 | protected long cacheHits, cacheMisses = 0L; |
| 89 | |
| 90 | /** |
| 91 | * Create a new cache and specify the maximum size of for the cache in |
| 92 | * bytes, and the maximum lifetime of objects. |
| 93 | * |
| 94 | * @param maxSize the maximum number of objects the cache will hold. -1 |
| 95 | * means the cache has no max size. |
| 96 | * @param maxLifetime the maximum amount of time (in ms) objects can exist in |
| 97 | * cache before being deleted. -1 means objects never expire. |
| 98 | */ |
| 99 | public Cache(int maxSize, long maxLifetime) { |
| 100 | if (maxSize == 0) { |
| 101 | throw new IllegalArgumentException("Max cache size cannot be 0."); |
| 102 | } |
| 103 | this.maxCacheSize = maxSize; |
| 104 | this.maxLifetime = maxLifetime; |
| 105 | |
| 106 | // Our primary data structure is a hash map. The default capacity of 11 |
| 107 | // is too small in almost all cases, so we set it bigger. |
| 108 | map = new HashMap<K, CacheObject<V>>(103); |
| 109 | |
| 110 | lastAccessedList = new LinkedList(); |
| 111 | ageList = new LinkedList(); |
| 112 | } |
| 113 | |
| 114 | public synchronized V put(K key, V value) { |
| 115 | V oldValue = null; |
| 116 | // Delete an old entry if it exists. |
| 117 | if (map.containsKey(key)) { |
| 118 | oldValue = remove(key, true); |
| 119 | } |
| 120 | |
| 121 | CacheObject<V> cacheObject = new CacheObject<V>(value); |
| 122 | map.put(key, cacheObject); |
| 123 | // Make an entry into the cache order list. |
| 124 | // Store the cache order list entry so that we can get back to it |
| 125 | // during later lookups. |
| 126 | cacheObject.lastAccessedListNode = lastAccessedList.addFirst(key); |
| 127 | // Add the object to the age list |
| 128 | LinkedListNode ageNode = ageList.addFirst(key); |
| 129 | ageNode.timestamp = System.currentTimeMillis(); |
| 130 | cacheObject.ageListNode = ageNode; |
| 131 | |
| 132 | // If cache is too full, remove least used cache entries until it is not too full. |
| 133 | cullCache(); |
| 134 | |
| 135 | return oldValue; |
| 136 | } |
| 137 | |
| 138 | public synchronized V get(Object key) { |
| 139 | // First, clear all entries that have been in cache longer than the |
| 140 | // maximum defined age. |
| 141 | deleteExpiredEntries(); |
| 142 | |
| 143 | CacheObject<V> cacheObject = map.get(key); |
| 144 | if (cacheObject == null) { |
| 145 | // The object didn't exist in cache, so increment cache misses. |
| 146 | cacheMisses++; |
| 147 | return null; |
| 148 | } |
| 149 | // Remove the object from it's current place in the cache order list, |
| 150 | // and re-insert it at the front of the list. |
| 151 | cacheObject.lastAccessedListNode.remove(); |
| 152 | lastAccessedList.addFirst(cacheObject.lastAccessedListNode); |
| 153 | |
| 154 | // The object exists in cache, so increment cache hits. Also, increment |
| 155 | // the object's read count. |
| 156 | cacheHits++; |
| 157 | cacheObject.readCount++; |
| 158 | |
| 159 | return cacheObject.object; |
| 160 | } |
| 161 | |
| 162 | public synchronized V remove(Object key) { |
| 163 | return remove(key, false); |
| 164 | } |
| 165 | |
| 166 | /* |
| 167 | * Remove operation with a flag so we can tell coherence if the remove was |
| 168 | * caused by cache internal processing such as eviction or loading |
| 169 | */ |
| 170 | public synchronized V remove(Object key, boolean internal) { |
| 171 | //noinspection SuspiciousMethodCalls |
| 172 | CacheObject<V> cacheObject = map.remove(key); |
| 173 | // If the object is not in cache, stop trying to remove it. |
| 174 | if (cacheObject == null) { |
| 175 | return null; |
| 176 | } |
| 177 | // Remove from the cache order list |
| 178 | cacheObject.lastAccessedListNode.remove(); |
| 179 | cacheObject.ageListNode.remove(); |
| 180 | // Remove references to linked list nodes |
| 181 | cacheObject.ageListNode = null; |
| 182 | cacheObject.lastAccessedListNode = null; |
| 183 | |
| 184 | return cacheObject.object; |
| 185 | } |
| 186 | |
| 187 | public synchronized void clear() { |
| 188 | Object[] keys = map.keySet().toArray(); |
| 189 | for (Object key : keys) { |
| 190 | remove(key); |
| 191 | } |
| 192 | |
| 193 | // Now, reset all containers. |
| 194 | map.clear(); |
| 195 | lastAccessedList.clear(); |
| 196 | ageList.clear(); |
| 197 | |
| 198 | cacheHits = 0; |
| 199 | cacheMisses = 0; |
| 200 | } |
| 201 | |
| 202 | public synchronized int size() { |
| 203 | // First, clear all entries that have been in cache longer than the |
| 204 | // maximum defined age. |
| 205 | deleteExpiredEntries(); |
| 206 | |
| 207 | return map.size(); |
| 208 | } |
| 209 | |
| 210 | public synchronized boolean isEmpty() { |
| 211 | // First, clear all entries that have been in cache longer than the |
| 212 | // maximum defined age. |
| 213 | deleteExpiredEntries(); |
| 214 | |
| 215 | return map.isEmpty(); |
| 216 | } |
| 217 | |
| 218 | public synchronized Collection<V> values() { |
| 219 | // First, clear all entries that have been in cache longer than the |
| 220 | // maximum defined age. |
| 221 | deleteExpiredEntries(); |
| 222 | |
| 223 | return Collections.unmodifiableCollection(new AbstractCollection<V>() { |
| 224 | Collection<CacheObject<V>> values = map.values(); |
| 225 | public Iterator<V> iterator() { |
| 226 | return new Iterator<V>() { |
| 227 | Iterator<CacheObject<V>> it = values.iterator(); |
| 228 | |
| 229 | public boolean hasNext() { |
| 230 | return it.hasNext(); |
| 231 | } |
| 232 | |
| 233 | public V next() { |
| 234 | return it.next().object; |
| 235 | } |
| 236 | |
| 237 | public void remove() { |
| 238 | it.remove(); |
| 239 | } |
| 240 | }; |
| 241 | } |
| 242 | |
| 243 | public int size() { |
| 244 | return values.size(); |
| 245 | } |
| 246 | }); |
| 247 | } |
| 248 | |
| 249 | public synchronized boolean containsKey(Object key) { |
| 250 | // First, clear all entries that have been in cache longer than the |
| 251 | // maximum defined age. |
| 252 | deleteExpiredEntries(); |
| 253 | |
| 254 | return map.containsKey(key); |
| 255 | } |
| 256 | |
| 257 | public void putAll(Map<? extends K, ? extends V> map) { |
| 258 | for (Entry<? extends K, ? extends V> entry : map.entrySet()) { |
| 259 | V value = entry.getValue(); |
| 260 | // If the map is another DefaultCache instance than the |
| 261 | // entry values will be CacheObject instances that need |
| 262 | // to be converted to the normal object form. |
| 263 | if (value instanceof CacheObject) { |
| 264 | //noinspection unchecked |
| 265 | value = ((CacheObject<V>) value).object; |
| 266 | } |
| 267 | put(entry.getKey(), value); |
| 268 | } |
| 269 | } |
| 270 | |
| 271 | public synchronized boolean containsValue(Object value) { |
| 272 | // First, clear all entries that have been in cache longer than the |
| 273 | // maximum defined age. |
| 274 | deleteExpiredEntries(); |
| 275 | |
| 276 | //noinspection unchecked |
| 277 | CacheObject<V> cacheObject = new CacheObject<V>((V) value); |
| 278 | |
| 279 | return map.containsValue(cacheObject); |
| 280 | } |
| 281 | |
| 282 | public synchronized Set<Map.Entry<K, V>> entrySet() { |
| 283 | // Warning -- this method returns CacheObject instances and not Objects |
| 284 | // in the same form they were put into cache. |
| 285 | |
| 286 | // First, clear all entries that have been in cache longer than the |
| 287 | // maximum defined age. |
| 288 | deleteExpiredEntries(); |
| 289 | |
| 290 | return new AbstractSet<Map.Entry<K, V>>() { |
| 291 | private final Set<Map.Entry<K, CacheObject<V>>> set = map.entrySet(); |
| 292 | |
| 293 | public Iterator<Entry<K, V>> iterator() { |
| 294 | return new Iterator<Entry<K, V>>() { |
| 295 | private final Iterator<Entry<K, CacheObject<V>>> it = set.iterator(); |
| 296 | public boolean hasNext() { |
| 297 | return it.hasNext(); |
| 298 | } |
| 299 | |
| 300 | public Entry<K, V> next() { |
| 301 | Map.Entry<K, CacheObject<V>> entry = it.next(); |
| 302 | return new AbstractMapEntry<K, V>(entry.getKey(), entry.getValue().object) { |
| 303 | @Override |
| 304 | public V setValue(V value) { |
| 305 | throw new UnsupportedOperationException("Cannot set"); |
| 306 | } |
| 307 | }; |
| 308 | } |
| 309 | |
| 310 | public void remove() { |
| 311 | it.remove(); |
| 312 | } |
| 313 | }; |
| 314 | |
| 315 | } |
| 316 | |
| 317 | public int size() { |
| 318 | return set.size(); |
| 319 | } |
| 320 | }; |
| 321 | } |
| 322 | |
| 323 | public synchronized Set<K> keySet() { |
| 324 | // First, clear all entries that have been in cache longer than the |
| 325 | // maximum defined age. |
| 326 | deleteExpiredEntries(); |
| 327 | |
| 328 | return Collections.unmodifiableSet(map.keySet()); |
| 329 | } |
| 330 | |
| 331 | public long getCacheHits() { |
| 332 | return cacheHits; |
| 333 | } |
| 334 | |
| 335 | public long getCacheMisses() { |
| 336 | return cacheMisses; |
| 337 | } |
| 338 | |
| 339 | public int getMaxCacheSize() { |
| 340 | return maxCacheSize; |
| 341 | } |
| 342 | |
| 343 | public synchronized void setMaxCacheSize(int maxCacheSize) { |
| 344 | this.maxCacheSize = maxCacheSize; |
| 345 | // It's possible that the new max size is smaller than our current cache |
| 346 | // size. If so, we need to delete infrequently used items. |
| 347 | cullCache(); |
| 348 | } |
| 349 | |
| 350 | public long getMaxLifetime() { |
| 351 | return maxLifetime; |
| 352 | } |
| 353 | |
| 354 | public void setMaxLifetime(long maxLifetime) { |
| 355 | this.maxLifetime = maxLifetime; |
| 356 | } |
| 357 | |
| 358 | /** |
| 359 | * Clears all entries out of cache where the entries are older than the |
| 360 | * maximum defined age. |
| 361 | */ |
| 362 | protected synchronized void deleteExpiredEntries() { |
| 363 | // Check if expiration is turned on. |
| 364 | if (maxLifetime <= 0) { |
| 365 | return; |
| 366 | } |
| 367 | |
| 368 | // Remove all old entries. To do this, we remove objects from the end |
| 369 | // of the linked list until they are no longer too old. We get to avoid |
| 370 | // any hash lookups or looking at any more objects than is strictly |
| 371 | // neccessary. |
| 372 | LinkedListNode node = ageList.getLast(); |
| 373 | // If there are no entries in the age list, return. |
| 374 | if (node == null) { |
| 375 | return; |
| 376 | } |
| 377 | |
| 378 | // Determine the expireTime, which is the moment in time that elements |
| 379 | // should expire from cache. Then, we can do an easy check to see |
| 380 | // if the expire time is greater than the expire time. |
| 381 | long expireTime = System.currentTimeMillis() - maxLifetime; |
| 382 | |
| 383 | while (expireTime > node.timestamp) { |
| 384 | if (remove(node.object, true) == null) { |
| 385 | System.err.println("Error attempting to remove(" + node.object.toString() + |
| 386 | ") - cacheObject not found in cache!"); |
| 387 | // remove from the ageList |
| 388 | node.remove(); |
| 389 | } |
| 390 | |
| 391 | // Get the next node. |
| 392 | node = ageList.getLast(); |
| 393 | // If there are no more entries in the age list, return. |
| 394 | if (node == null) { |
| 395 | return; |
| 396 | } |
| 397 | } |
| 398 | } |
| 399 | |
| 400 | /** |
| 401 | * Removes the least recently used elements if the cache size is greater than |
| 402 | * or equal to the maximum allowed size until the cache is at least 10% empty. |
| 403 | */ |
| 404 | protected synchronized void cullCache() { |
| 405 | // Check if a max cache size is defined. |
| 406 | if (maxCacheSize < 0) { |
| 407 | return; |
| 408 | } |
| 409 | |
| 410 | // See if the cache is too big. If so, clean out cache until it's 10% free. |
| 411 | if (map.size() > maxCacheSize) { |
| 412 | // First, delete any old entries to see how much memory that frees. |
| 413 | deleteExpiredEntries(); |
| 414 | // Next, delete the least recently used elements until 10% of the cache |
| 415 | // has been freed. |
| 416 | int desiredSize = (int) (maxCacheSize * .90); |
| 417 | for (int i=map.size(); i>desiredSize; i--) { |
| 418 | // Get the key and invoke the remove method on it. |
| 419 | if (remove(lastAccessedList.getLast().object, true) == null) { |
| 420 | System.err.println("Error attempting to cullCache with remove(" + |
| 421 | lastAccessedList.getLast().object.toString() + ") - " + |
| 422 | "cacheObject not found in cache!"); |
| 423 | lastAccessedList.getLast().remove(); |
| 424 | } |
| 425 | } |
| 426 | } |
| 427 | } |
| 428 | |
| 429 | /** |
| 430 | * Wrapper for all objects put into cache. It's primary purpose is to maintain |
| 431 | * references to the linked lists that maintain the creation time of the object |
| 432 | * and the ordering of the most used objects. |
| 433 | * |
| 434 | * This class is optimized for speed rather than strictly correct encapsulation. |
| 435 | */ |
| 436 | private static class CacheObject<V> { |
| 437 | |
| 438 | /** |
| 439 | * Underlying object wrapped by the CacheObject. |
| 440 | */ |
| 441 | public V object; |
| 442 | |
| 443 | /** |
| 444 | * A reference to the node in the cache order list. We keep the reference |
| 445 | * here to avoid linear scans of the list. Every time the object is |
| 446 | * accessed, the node is removed from its current spot in the list and |
| 447 | * moved to the front. |
| 448 | */ |
| 449 | public LinkedListNode lastAccessedListNode; |
| 450 | |
| 451 | /** |
| 452 | * A reference to the node in the age order list. We keep the reference |
| 453 | * here to avoid linear scans of the list. The reference is used if the |
| 454 | * object has to be deleted from the list. |
| 455 | */ |
| 456 | public LinkedListNode ageListNode; |
| 457 | |
| 458 | /** |
| 459 | * A count of the number of times the object has been read from cache. |
| 460 | */ |
| 461 | public int readCount = 0; |
| 462 | |
| 463 | /** |
| 464 | * Creates a new cache object wrapper. |
| 465 | * |
| 466 | * @param object the underlying Object to wrap. |
| 467 | */ |
| 468 | public CacheObject(V object) { |
| 469 | this.object = object; |
| 470 | } |
| 471 | |
| 472 | public boolean equals(Object o) { |
| 473 | if (this == o) { |
| 474 | return true; |
| 475 | } |
| 476 | if (!(o instanceof CacheObject)) { |
| 477 | return false; |
| 478 | } |
| 479 | |
| 480 | final CacheObject<?> cacheObject = (CacheObject<?>) o; |
| 481 | |
| 482 | return object.equals(cacheObject.object); |
| 483 | |
| 484 | } |
| 485 | |
| 486 | public int hashCode() { |
| 487 | return object.hashCode(); |
| 488 | } |
| 489 | } |
| 490 | |
| 491 | /** |
| 492 | * Simple LinkedList implementation. The main feature is that list nodes |
| 493 | * are public, which allows very fast delete operations when one has a |
| 494 | * reference to the node that is to be deleted.<p> |
| 495 | */ |
| 496 | private static class LinkedList { |
| 497 | |
| 498 | /** |
| 499 | * The root of the list keeps a reference to both the first and last |
| 500 | * elements of the list. |
| 501 | */ |
| 502 | private LinkedListNode head = new LinkedListNode("head", null, null); |
| 503 | |
| 504 | /** |
| 505 | * Creates a new linked list. |
| 506 | */ |
| 507 | public LinkedList() { |
| 508 | head.next = head.previous = head; |
| 509 | } |
| 510 | |
| 511 | /** |
| 512 | * Returns the first linked list node in the list. |
| 513 | * |
| 514 | * @return the first element of the list. |
| 515 | */ |
| 516 | public LinkedListNode getFirst() { |
| 517 | LinkedListNode node = head.next; |
| 518 | if (node == head) { |
| 519 | return null; |
| 520 | } |
| 521 | return node; |
| 522 | } |
| 523 | |
| 524 | /** |
| 525 | * Returns the last linked list node in the list. |
| 526 | * |
| 527 | * @return the last element of the list. |
| 528 | */ |
| 529 | public LinkedListNode getLast() { |
| 530 | LinkedListNode node = head.previous; |
| 531 | if (node == head) { |
| 532 | return null; |
| 533 | } |
| 534 | return node; |
| 535 | } |
| 536 | |
| 537 | /** |
| 538 | * Adds a node to the beginning of the list. |
| 539 | * |
| 540 | * @param node the node to add to the beginning of the list. |
| 541 | * @return the node |
| 542 | */ |
| 543 | public LinkedListNode addFirst(LinkedListNode node) { |
| 544 | node.next = head.next; |
| 545 | node.previous = head; |
| 546 | node.previous.next = node; |
| 547 | node.next.previous = node; |
| 548 | return node; |
| 549 | } |
| 550 | |
| 551 | /** |
| 552 | * Adds an object to the beginning of the list by automatically creating a |
| 553 | * a new node and adding it to the beginning of the list. |
| 554 | * |
| 555 | * @param object the object to add to the beginning of the list. |
| 556 | * @return the node created to wrap the object. |
| 557 | */ |
| 558 | public LinkedListNode addFirst(Object object) { |
| 559 | LinkedListNode node = new LinkedListNode(object, head.next, head); |
| 560 | node.previous.next = node; |
| 561 | node.next.previous = node; |
| 562 | return node; |
| 563 | } |
| 564 | |
| 565 | /** |
| 566 | * Adds an object to the end of the list by automatically creating a |
| 567 | * a new node and adding it to the end of the list. |
| 568 | * |
| 569 | * @param object the object to add to the end of the list. |
| 570 | * @return the node created to wrap the object. |
| 571 | */ |
| 572 | public LinkedListNode addLast(Object object) { |
| 573 | LinkedListNode node = new LinkedListNode(object, head, head.previous); |
| 574 | node.previous.next = node; |
| 575 | node.next.previous = node; |
| 576 | return node; |
| 577 | } |
| 578 | |
| 579 | /** |
| 580 | * Erases all elements in the list and re-initializes it. |
| 581 | */ |
| 582 | public void clear() { |
| 583 | //Remove all references in the list. |
| 584 | LinkedListNode node = getLast(); |
| 585 | while (node != null) { |
| 586 | node.remove(); |
| 587 | node = getLast(); |
| 588 | } |
| 589 | |
| 590 | //Re-initialize. |
| 591 | head.next = head.previous = head; |
| 592 | } |
| 593 | |
| 594 | /** |
| 595 | * Returns a String representation of the linked list with a comma |
| 596 | * delimited list of all the elements in the list. |
| 597 | * |
| 598 | * @return a String representation of the LinkedList. |
| 599 | */ |
| 600 | public String toString() { |
| 601 | LinkedListNode node = head.next; |
| 602 | StringBuilder buf = new StringBuilder(); |
| 603 | while (node != head) { |
| 604 | buf.append(node.toString()).append(", "); |
| 605 | node = node.next; |
| 606 | } |
| 607 | return buf.toString(); |
| 608 | } |
| 609 | } |
| 610 | |
| 611 | /** |
| 612 | * Doubly linked node in a LinkedList. Most LinkedList implementations keep the |
| 613 | * equivalent of this class private. We make it public so that references |
| 614 | * to each node in the list can be maintained externally. |
| 615 | * |
| 616 | * Exposing this class lets us make remove operations very fast. Remove is |
| 617 | * built into this class and only requires two reference reassignments. If |
| 618 | * remove existed in the main LinkedList class, a linear scan would have to |
| 619 | * be performed to find the correct node to delete. |
| 620 | * |
| 621 | * The linked list implementation was specifically written for the Jive |
| 622 | * cache system. While it can be used as a general purpose linked list, for |
| 623 | * most applications, it is more suitable to use the linked list that is part |
| 624 | * of the Java Collections package. |
| 625 | */ |
| 626 | private static class LinkedListNode { |
| 627 | |
| 628 | public LinkedListNode previous; |
| 629 | public LinkedListNode next; |
| 630 | public Object object; |
| 631 | |
| 632 | /** |
| 633 | * This class is further customized for the Jive cache system. It |
| 634 | * maintains a timestamp of when a Cacheable object was first added to |
| 635 | * cache. Timestamps are stored as long values and represent the number |
| 636 | * of milliseconds passed since January 1, 1970 00:00:00.000 GMT.<p> |
| 637 | * |
| 638 | * The creation timestamp is used in the case that the cache has a |
| 639 | * maximum lifetime set. In that case, when |
| 640 | * [current time] - [creation time] > [max lifetime], the object will be |
| 641 | * deleted from cache. |
| 642 | */ |
| 643 | public long timestamp; |
| 644 | |
| 645 | /** |
| 646 | * Constructs a new linked list node. |
| 647 | * |
| 648 | * @param object the Object that the node represents. |
| 649 | * @param next a reference to the next LinkedListNode in the list. |
| 650 | * @param previous a reference to the previous LinkedListNode in the list. |
| 651 | */ |
| 652 | public LinkedListNode(Object object, LinkedListNode next, |
| 653 | LinkedListNode previous) |
| 654 | { |
| 655 | this.object = object; |
| 656 | this.next = next; |
| 657 | this.previous = previous; |
| 658 | } |
| 659 | |
| 660 | /** |
| 661 | * Removes this node from the linked list that it is a part of. |
| 662 | */ |
| 663 | public void remove() { |
| 664 | previous.next = next; |
| 665 | next.previous = previous; |
| 666 | } |
| 667 | |
| 668 | /** |
| 669 | * Returns a String representation of the linked list node by calling the |
| 670 | * toString method of the node's object. |
| 671 | * |
| 672 | * @return a String representation of the LinkedListNode. |
| 673 | */ |
| 674 | public String toString() { |
| 675 | return object.toString(); |
| 676 | } |
| 677 | } |
| 678 | } |