KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > tomcat > util > collections > LRUCache


1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one or more
3  * contributor license agreements. See the NOTICE file distributed with
4  * this work for additional information regarding copyright ownership.
5  * The ASF licenses this file to You under the Apache License, Version 2.0
6  * (the "License"); you may not use this file except in compliance with
7  * the License. You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17
18 package org.apache.tomcat.util.collections;
19
20 import java.util.Hashtable JavaDoc;
21
22 /**
23  * This class implements a Generic LRU Cache
24  *
25  *
26  * @author Ignacio J. Ortega
27  *
28  */
29
30 public class LRUCache
31 {
32     class CacheNode
33     {
34
35         CacheNode prev;
36         CacheNode next;
37         Object JavaDoc value;
38         Object JavaDoc key;
39
40         CacheNode()
41         {
42         }
43     }
44
45
46     public LRUCache(int i)
47     {
48         currentSize = 0;
49         cacheSize = i;
50         nodes = new Hashtable JavaDoc(i);
51     }
52
53     public Object JavaDoc get(Object JavaDoc key)
54     {
55         CacheNode node = (CacheNode)nodes.get(key);
56         if(node != null)
57         {
58             moveToHead(node);
59             return node.value;
60         }
61         else
62         {
63             return null;
64         }
65     }
66
67     public void put(Object JavaDoc key, Object JavaDoc value)
68     {
69         CacheNode node = (CacheNode)nodes.get(key);
70         if(node == null)
71         {
72             if(currentSize >= cacheSize)
73             {
74                 if(last != null)
75                     nodes.remove(last.key);
76                 removeLast();
77             }
78             else
79             {
80                 currentSize++;
81             }
82             node = new CacheNode();
83         }
84         node.value = value;
85         node.key = key;
86         moveToHead(node);
87         nodes.put(key, node);
88     }
89
90     public Object JavaDoc remove(Object JavaDoc key) {
91         CacheNode node = (CacheNode)nodes.get(key);
92         if (node != null) {
93             if (node.prev != null) {
94                 node.prev.next = node.next;
95             }
96             if (node.next != null) {
97                 node.next.prev = node.prev;
98             }
99             if (last == node)
100                 last = node.prev;
101             if (first == node)
102                 first = node.next;
103         }
104         return node;
105     }
106
107     public void clear()
108     {
109         first = null;
110         last = null;
111     }
112
113     private void removeLast()
114     {
115         if(last != null)
116         {
117             if(last.prev != null)
118                 last.prev.next = null;
119             else
120                 first = null;
121             last = last.prev;
122         }
123     }
124
125     private void moveToHead(CacheNode node)
126     {
127         if(node == first)
128             return;
129         if(node.prev != null)
130             node.prev.next = node.next;
131         if(node.next != null)
132             node.next.prev = node.prev;
133         if(last == node)
134             last = node.prev;
135         if(first != null)
136         {
137             node.next = first;
138             first.prev = node;
139         }
140         first = node;
141         node.prev = null;
142         if(last == null)
143             last = first;
144     }
145
146     private int cacheSize;
147     private Hashtable JavaDoc nodes;
148     private int currentSize;
149     private CacheNode first;
150     private CacheNode last;
151 }
152
Popular Tags