An LRU (Least Recently Used) cache replacement policy : Cache « Development Class « Java

Java
1. 2D Graphics GUI
2. 3D
3. Advanced Graphics
4. Ant
5. Apache Common
6. Chart
7. Class
8. Collections Data Structure
9. Data Type
10. Database SQL JDBC
11. Design Pattern
12. Development Class
13. EJB3
14. Email
15. Event
16. File Input Output
17. Game
18. Generics
19. GWT
20. Hibernate
21. I18N
22. J2EE
23. J2ME
24. JDK 6
25. JNDI LDAP
26. JPA
27. JSP
28. JSTL
29. Language Basics
30. Network Protocol
31. PDF RTF
32. Reflection
33. Regular Expressions
34. Scripting
35. Security
36. Servlets
37. Spring
38. Swing Components
39. Swing JFC
40. SWT JFace Eclipse
41. Threads
42. Tiny Application
43. Velocity
44. Web Services SOA
45. XML
Java Tutorial
Java Source Code / Java Documentation
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java » Development Class » CacheScreenshots 
An LRU (Least Recently Used) cache replacement policy
   


/*
 * $Id: CacheLRU.java,v 1.10 2003/11/07 20:16:25 dfs Exp $
 *
 
 * The Apache Software License, Version 1.1
 *
 * Copyright (c) 2000 The Apache Software Foundation.  All rights
 * reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:
 *       "This product includes software developed by the
 *        Apache Software Foundation (http://www.apache.org/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" 
 *    must not be used to endorse or promote products derived from this
 *    software without prior written permission. For written
 *    permission, please contact apache@apache.org.
 *
 * 5. Products derived from this software may not be called "Apache" 
 *    or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their 
 *    name, without prior written permission of the Apache Software Foundation.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Apache Software Foundation.  For more
 * information on the Apache Software Foundation, please see
 * <http://www.apache.org/>.
 */



import java.util.*;

/**
 * This class is a GenericCache subclass implementing an LRU
 * (Least Recently Used) cache replacement policy.  In other words,
 * values are added to the cache until it becomes full.  Once the
 * cache is full, when a new value is added to the cache, it replaces
 * the least recently used value currently in the cache.  This is probably
 * the best general purpose cache replacement policy.
 
 @version @version@
 @since 1.0
 @see GenericCache
 */
public final class CacheLRU extends GenericCache {
  private int __head = 0, __tail = 0;
  private int[] __next, __prev;

  /**
   * Creates a CacheLRU instance with a given cache capacity.
   * <p>
   @param capacity  The capacity of the cache.
   */
  public CacheLRU(int capacity) { 
    super(capacity);

    int i;

    __next = new int[_cache.length];
    __prev = new int[_cache.length];

    for(i=0; i < __next.length; i++)
      __next[i= __prev[i= -1;
  }


  /**
   * Same as:
   * <blockquote><pre>
   * CacheLRU(GenericCache.DEFAULT_CAPACITY);
   * </pre></blockquote>
   */
  public CacheLRU(){
    this(GenericCache.DEFAULT_CAPACITY);
  }


  private void __moveToFront(int index) {
    int next, prev;

    if(__head != index) {
      next = __next[index];
      prev = __prev[index];

      // Only the head has a prev entry that is an invalid index so
      // we don't check.
      __next[prev= next;

      // Make sure index is valid.  If it isn't, we're at the tail
      // and don't set __prev[next].
      if(next >= 0)
  __prev[next= prev;
      else
  __tail = prev;

      __prev[index= -1;
      __next[index= __head;
      __prev[__head= index;
      __head        = index;
    }
  }


  public synchronized Object getElement(Object key) { 
    Object obj;

    obj = _table.get(key);

    if(obj != null) {
      GenericCacheEntry entry;

      entry = (GenericCacheEntry)obj;
      // Maintain LRU property
      __moveToFront(entry._index);

      return entry._value;
    }

    return null;
  }


  /**
   * Adds a value to the cache.  If the cache is full, when a new value
   * is added to the cache, it replaces the least recently used value
   * in the cache (i.e., LRU).
   * <p>
   @param key   The key referencing the value added to the cache.
   @param value The value to add to the cache.
   */
  public final synchronized void addElement(Object key, Object value) {
    Object obj;

    obj = _table.get(key);

    if(obj != null) {
      GenericCacheEntry entry;

      // Just replace the value, but move it to the front.
      entry = (GenericCacheEntry)obj;
      entry._value = value;
      entry._key   = key;

      __moveToFront(entry._index);

      return;
    }

    // If we haven't filled the cache yet, place in next available spot
    // and move to front.
    if(!isFull()) {
      if(_numEntries > 0) {
  __prev[_numEntries= __tail;
  __next[_numEntries= -1;
  __moveToFront(_numEntries);
      }
      ++_numEntries;
    else {
      // We replace the tail of the list.
      _table.remove(_cache[__tail]._key);
      __moveToFront(__tail);
    }

    _cache[__head]._value = value;
    _cache[__head]._key   = key;
    _table.put(key, _cache[__head]);
  }
}


/*
 * $Id: GenericCache.java,v 1.8 2003/11/07 20:16:25 dfs Exp $
 *
 
 * The Apache Software License, Version 1.1
 *
 * Copyright (c) 2000 The Apache Software Foundation.  All rights
 * reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:
 *       "This product includes software developed by the
 *        Apache Software Foundation (http://www.apache.org/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" 
 *    must not be used to endorse or promote products derived from this
 *    software without prior written permission. For written
 *    permission, please contact apache@apache.org.
 *
 * 5. Products derived from this software may not be called "Apache" 
 *    or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their 
 *    name, without prior written permission of the Apache Software Foundation.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Apache Software Foundation.  For more
 * information on the Apache Software Foundation, please see
 * <http://www.apache.org/>.
 */



/**
 * This is the base class for all cache implementations provided in the
 * org.apache.oro.util package.  To derive a subclass from GenericCache
 * only the ... methods
 * need be overridden.
 * Although 4 subclasses of GenericCache are provided with this
 * package, users may not derive subclasses from this class.
 * Rather, users should create their own implmentations of the
 {@link Cache} interface.
 *
 @version @version@
 @since 1.0
 @see Cache
 @see CacheLRU
 @see CacheFIFO
 @see CacheFIFO2
 @see CacheRandom
 */
 abstract class GenericCache implements Cache, java.io.Serializable {
  /**
   * The default capacity to be used by the GenericCache subclasses
   * provided with this package.  Its value is 20.
   */
  public static final int DEFAULT_CAPACITY = 20;

  int _numEntries;
  GenericCacheEntry[] _cache;
  HashMap _table;

  /**
   * The primary constructor for GenericCache.  It has default
   * access so it will only be used within the package.  It initializes
   * _table to a Hashtable of capacity equal to the capacity argument,
   * _cache to an array of size equal to the capacity argument, and
   * _numEntries to 0.
   * <p>
   @param capacity The maximum capacity of the cache.
   */
  GenericCache(int capacity) {
    _numEntries = 0;
    _table    = new HashMap(capacity);
    _cache    = new GenericCacheEntry[capacity];

    while(--capacity >= 0)
      _cache[capacitynew GenericCacheEntry(capacity);
  }

  public abstract void addElement(Object key, Object value);

  public synchronized Object getElement(Object key) { 
    Object obj;

    obj = _table.get(key);

    if(obj != null)
      return ((GenericCacheEntry)obj)._value;

    return null;
  }

  public final Iterator keys() {
    return _table.keySet().iterator();
  }

  /**
   * Returns the number of elements in the cache, not to be confused with
   * the {@link #capacity()} which returns the number
   * of elements that can be held in the cache at one time.
   * <p>
   @return  The current size of the cache (i.e., the number of elements
   *          currently cached).
   */
  public final int size() { return _numEntries; }

  /**
   * Returns the maximum number of elements that can be cached at one time.
   * <p>
   @return The maximum number of elements that can be cached at one time.
   */
  public final int capacity() { return _cache.length; }

  public final boolean isFull() { return (_numEntries >= _cache.length)}
}

 /*
  * $Id: Cache.java,v 1.7 2003/11/07 20:16:25 dfs Exp $
  *
  
  * The Apache Software License, Version 1.1
  *
  * Copyright (c) 2000 The Apache Software Foundation.  All rights
  * reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  *
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  *
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in
  *    the documentation and/or other materials provided with the
  *    distribution.
  *
  * 3. The end-user documentation included with the redistribution,
  *    if any, must include the following acknowledgment:
  *       "This product includes software developed by the
  *        Apache Software Foundation (http://www.apache.org/)."
  *    Alternately, this acknowledgment may appear in the software itself,
  *    if and wherever such third-party acknowledgments normally appear.
  *
  * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" 
  *    must not be used to endorse or promote products derived from this
  *    software without prior written permission. For written
  *    permission, please contact apache@apache.org.
  *
  * 5. Products derived from this software may not be called "Apache" 
  *    or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their 
  *    name, without prior written permission of the Apache Software Foundation.
  *
  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  
  *
  * This software consists of voluntary contributions made by many
  * individuals on behalf of the Apache Software Foundation.  For more
  * information on the Apache Software Foundation, please see
  * <http://www.apache.org/>.
  */




 /**
  * An interface defining the basic functions of a cache.
  *
  @version @version@
  @since 1.0
  */
  interface Cache {

   public void addElement(Object key, Object value);

   public Object getElement(Object key);

   /**
    * Returns the number of elements in the cache, not to be confused with
    * the {@link #capacity()} which returns the number
    * of elements that can be held in the cache at one time.
    * <p>
    @return  The current size of the cache (i.e., the number of elements
    *          currently cached).
    */
   public int size();


   /**
    * Returns the maximum number of elements that can be cached at one time.
    * <p>
    @return The maximum number of elements that can be cached at one time.
    */
   public int capacity();

 }

  /*
   * $Id: GenericCacheEntry.java,v 1.7 2003/11/07 20:16:25 dfs Exp $
   *
   
   * The Apache Software License, Version 1.1
   *
   * Copyright (c) 2000 The Apache Software Foundation.  All rights
   * reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions
   * are met:
   *
   * 1. Redistributions of source code must retain the above copyright
   *    notice, this list of conditions and the following disclaimer.
   *
   * 2. Redistributions in binary form must reproduce the above copyright
   *    notice, this list of conditions and the following disclaimer in
   *    the documentation and/or other materials provided with the
   *    distribution.
   *
   * 3. The end-user documentation included with the redistribution,
   *    if any, must include the following acknowledgment:
   *       "This product includes software developed by the
   *        Apache Software Foundation (http://www.apache.org/)."
   *    Alternately, this acknowledgment may appear in the software itself,
   *    if and wherever such third-party acknowledgments normally appear.
   *
   * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" 
   *    must not be used to endorse or promote products derived from this
   *    software without prior written permission. For written
   *    permission, please contact apache@apache.org.
   *
   * 5. Products derived from this software may not be called "Apache" 
   *    or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their 
   *    name, without prior written permission of the Apache Software Foundation.
   *
   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
   * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
   * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
   * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
   * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
   * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   * SUCH DAMAGE.
   
   *
   * This software consists of voluntary contributions made by many
   * individuals on behalf of the Apache Software Foundation.  For more
   * information on the Apache Software Foundation, please see
   * <http://www.apache.org/>.
   */



  /**
   * A structure used to store values in a GenericCache.  It
   * is declared with default access to limit it to use only within the
   * package.
   *
   @version @version@
   @since 1.0
   */
  final class GenericCacheEntry implements java.io.Serializable {
    /** The cache array index of the entry. */
    int _index;
    /** The value stored at this entry. */
    Object _value;
    /** The key used to store the value. */
    Object _key;

    GenericCacheEntry(int index) {
      _index = index;
      _value = null;
      _key   = null;
    }
  }

   
    
    
  
Related examples in the same category
1. A LRU (Least Recently Used) cache replacement policy
2. A Map that is size-limited using an LRU algorithm
3. A random cache replacement policy
4. A second chance FIFO (First In First Out) cache replacement policy
5. Async LRU List
6. FIFO First In First Out cache replacement policy
7. Implementation of a Least Recently Used cache policy
8. Generic LRU Cache
9. LRU Cache
10. A Least Recently Used Cache
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.