001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. 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: */
017:
018: package org.apache.tomcat.util.collections;
019:
020: import java.util.Hashtable;
021:
022: /**
023: * This class implements a Generic LRU Cache
024: *
025: *
026: * @author Ignacio J. Ortega
027: *
028: */
029:
030: public class LRUCache {
031: class CacheNode {
032:
033: CacheNode prev;
034: CacheNode next;
035: Object value;
036: Object key;
037:
038: CacheNode() {
039: }
040: }
041:
042: public LRUCache(int i) {
043: currentSize = 0;
044: cacheSize = i;
045: nodes = new Hashtable(i);
046: }
047:
048: public Object get(Object key) {
049: CacheNode node = (CacheNode) nodes.get(key);
050: if (node != null) {
051: moveToHead(node);
052: return node.value;
053: } else {
054: return null;
055: }
056: }
057:
058: public void put(Object key, Object value) {
059: CacheNode node = (CacheNode) nodes.get(key);
060: if (node == null) {
061: if (currentSize >= cacheSize) {
062: if (last != null)
063: nodes.remove(last.key);
064: removeLast();
065: } else {
066: currentSize++;
067: }
068: node = new CacheNode();
069: }
070: node.value = value;
071: node.key = key;
072: moveToHead(node);
073: nodes.put(key, node);
074: }
075:
076: public Object remove(Object key) {
077: CacheNode node = (CacheNode) nodes.get(key);
078: if (node != null) {
079: if (node.prev != null) {
080: node.prev.next = node.next;
081: }
082: if (node.next != null) {
083: node.next.prev = node.prev;
084: }
085: if (last == node)
086: last = node.prev;
087: if (first == node)
088: first = node.next;
089: }
090: return node;
091: }
092:
093: public void clear() {
094: first = null;
095: last = null;
096: }
097:
098: private void removeLast() {
099: if (last != null) {
100: if (last.prev != null)
101: last.prev.next = null;
102: else
103: first = null;
104: last = last.prev;
105: }
106: }
107:
108: private void moveToHead(CacheNode node) {
109: if (node == first)
110: return;
111: if (node.prev != null)
112: node.prev.next = node.next;
113: if (node.next != null)
114: node.next.prev = node.prev;
115: if (last == node)
116: last = node.prev;
117: if (first != null) {
118: node.next = first;
119: first.prev = node;
120: }
121: first = node;
122: node.prev = null;
123: if (last == null)
124: last = first;
125: }
126:
127: private int cacheSize;
128: private Hashtable nodes;
129: private int currentSize;
130: private CacheNode first;
131: private CacheNode last;
132: }
|