001: /*
002: * Copyright 1999-2004 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016:
017: package org.apache.tomcat.util.collections;
018:
019: import java.util.Hashtable;
020:
021: /**
022: * This class implements a Generic LRU Cache
023: *
024: *
025: * @author Ignacio J. Ortega
026: *
027: */
028:
029: public class LRUCache {
030: class CacheNode {
031:
032: CacheNode prev;
033: CacheNode next;
034: Object value;
035: Object key;
036:
037: CacheNode() {
038: }
039: }
040:
041: public LRUCache(int i) {
042: currentSize = 0;
043: cacheSize = i;
044: nodes = new Hashtable(i);
045: }
046:
047: public Object get(Object key) {
048: CacheNode node = (CacheNode) nodes.get(key);
049: if (node != null) {
050: moveToHead(node);
051: return node.value;
052: } else {
053: return null;
054: }
055: }
056:
057: public void put(Object key, Object value) {
058: CacheNode node = (CacheNode) nodes.get(key);
059: if (node == null) {
060: if (currentSize >= cacheSize) {
061: if (last != null)
062: nodes.remove(last.key);
063: removeLast();
064: } else {
065: currentSize++;
066: }
067: node = new CacheNode();
068: }
069: node.value = value;
070: node.key = key;
071: moveToHead(node);
072: nodes.put(key, node);
073: }
074:
075: public Object remove(Object key) {
076: CacheNode node = (CacheNode) nodes.get(key);
077: if (node != null) {
078: if (node.prev != null) {
079: node.prev.next = node.next;
080: }
081: if (node.next != null) {
082: node.next.prev = node.prev;
083: }
084: if (last == node)
085: last = node.prev;
086: if (first == node)
087: first = node.next;
088: }
089: return node;
090: }
091:
092: public void clear() {
093: first = null;
094: last = null;
095: }
096:
097: private void removeLast() {
098: if (last != null) {
099: if (last.prev != null)
100: last.prev.next = null;
101: else
102: first = null;
103: last = last.prev;
104: }
105: }
106:
107: private void moveToHead(CacheNode node) {
108: if (node == first)
109: return;
110: if (node.prev != null)
111: node.prev.next = node.next;
112: if (node.next != null)
113: node.next.prev = node.prev;
114: if (last == node)
115: last = node.prev;
116: if (first != null) {
117: node.next = first;
118: first.prev = node;
119: }
120: first = node;
121: node.prev = null;
122: if (last == null)
123: last = first;
124: }
125:
126: private int cacheSize;
127: private Hashtable nodes;
128: private int currentSize;
129: private CacheNode first;
130: private CacheNode last;
131: }
|