Source code: com/opencms/template/cache/CmsLruCache.java
1 /*
2 * File : $Source: /usr/local/cvs/opencms/src/com/opencms/template/cache/CmsLruCache.java,v $
3 * Date : $Date: 2003/02/15 11:14:53 $
4 * Version: $Revision: 1.18 $
5 *
6 * This library is part of OpenCms -
7 * the Open Source Content Mananagement System
8 *
9 * Copyright (C) 2001 The OpenCms Group
10 *
11 * This library is free software; you can redistribute it and/or
12 * modify it under the terms of the GNU Lesser General Public
13 * License as published by the Free Software Foundation; either
14 * version 2.1 of the License, or (at your option) any later version.
15 *
16 * This library is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 * Lesser General Public License for more details.
20 *
21 * For further information about OpenCms, please see the
22 * OpenCms Website: http://www.opencms.org
23 *
24 * You should have received a copy of the GNU Lesser General Public
25 * License along with this library; if not, write to the Free Software
26 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
27 */
28
29 package com.opencms.template.cache;
30
31 import java.util.Vector;
32
33 /**
34 * This class implements a LRU cache. It uses a Hashtable algorithm with the
35 * chaining method for collision handling. The sequence of the Objects is stored in
36 * an extra chain. Each object has a pointer to the previous and next object in this
37 * chain. If an object is inserted or used it is set to the tail of the chain. If an
38 * object has to be remouved it will be the head object. Only works with more than one element.
39 *
40 * @author Hanjo Riege
41 * @version 1.0
42 */
43
44 public class CmsLruCache {
45
46 // enables the login. Just for debugging.
47 private static final boolean C_DEBUG = false;
48
49 // the array to store everthing
50 private CacheItem[] m_cache;
51
52 // the capacity of the cache
53 private int m_maxSize;
54
55 // the aktual size of the cache
56 private int m_size = 0;
57
58 // the head of the time sequence
59 private CacheItem head;
60
61 // the tail of the time sequence
62 private CacheItem tail;
63
64 static class CacheItem {
65 Object key;
66 Object value;
67
68 // the link for the collision hanling
69 CacheItem chain;
70
71 // links for the time sequence chain
72 CacheItem previous;
73 CacheItem next;
74 }
75
76 /**
77 * Constructor
78 * @param size The size of the cache.
79 */
80 public CmsLruCache(int size) {
81 if(C_DEBUG){
82 System.err.println("--LruCache started with "+size);
83 }
84 m_cache = new CacheItem[size];
85 m_maxSize = size;
86 }
87
88 /**
89 * inserts a new object in the cache. If it is there already the value is updated.
90 * @param key The key to find the object.
91 * @param value The object.
92 * @return if the cache is full the deleted object, null otherwise.
93 */
94 public synchronized Vector put (Object key, Object value){
95
96 int hashIndex = (key.hashCode() & 0x7FFFFFFF) % m_maxSize;
97 CacheItem item = m_cache[hashIndex];
98 CacheItem newItem = null;
99 Vector returnValue = null;
100 if(C_DEBUG){
101 System.err.println("put in cache: "+key);
102 }
103 if(item != null){
104 // there is a item allready. Collision.
105 // lets look if the new item was inserted before
106 while(item.chain != null){
107 if(item.key.equals(key)){
108 item.value = value;
109 // TODO: put it to the end of the chain
110 return null;
111 }
112 item = item.chain;
113 }
114 if(item.key.equals(key)){
115 item.value = value;
116 //TODO: put it on the end of the chain
117 return null;
118 }
119 if(m_size >= m_maxSize){
120 // cache full, we have to remove the old head
121 CacheItem helper = head.next;
122 if (item == head){
123 newItem = item;
124 returnValue = new Vector(2);
125 returnValue.add(0, item.key);
126 returnValue.add(1, item.value);
127 }else{
128 newItem = head;
129 returnValue = new Vector(2);
130 returnValue.add(0, head.key);
131 returnValue.add(1, head.value);
132 removeFromTable(head);
133 newItem.chain = null;
134 item.chain = newItem;
135 }
136 newItem.next = null;
137 head = helper;
138 head.previous = null;
139 }else{
140 m_size++;
141 newItem = new CacheItem();
142 item.chain = newItem;
143 }
144 }else{
145 // oh goody, a free place for the new item
146 if(head != null){
147 if(m_size >= m_maxSize){
148 // cache full, we have to remove the old head
149 CacheItem helper = head.next;
150 newItem = head;
151 returnValue = new Vector(2);
152 returnValue.add(0, head.key);
153 returnValue.add(1, head.value);
154 removeFromTable(head);
155 newItem.next = null;
156 newItem.chain = null;
157 head = helper;
158 head.previous = null;
159 }else{
160 m_size++;
161 newItem = new CacheItem();
162 }
163 }else{
164 // first item in the chain
165 newItem = new CacheItem();
166 m_size++;
167 head = newItem;
168 tail = newItem;
169 }
170 item = m_cache[hashIndex] = newItem;
171 }
172 // the new Item is in the array and in the chain. Fill it.
173 newItem.key = key;
174 newItem.value = value;
175 if(tail != newItem){
176 tail.next = newItem;
177 newItem.previous = tail;
178 tail = newItem;
179 }
180 return returnValue;
181 }
182
183 /**
184 * returns the value to the key or null if the key is not in the cache. The found
185 * element has to line up behind the others (set to the tail).
186 * @param key The key for the object.
187 * @return The value.
188 */
189 public synchronized Object get(Object key){
190 int hashIndex = (key.hashCode() & 0x7FFFFFFF) % m_maxSize;
191 CacheItem item = m_cache[hashIndex];
192 if(C_DEBUG){
193 System.err.println("get from Cache: "+key);
194 //checkCondition();
195 }
196 while (item != null){
197 if(item.key.equals(key)){
198 // got it
199 if(item != tail){
200 // hinten anstellen
201 if(item != head){
202 item.previous.next = item.next;
203 }else{
204 head = head.next;
205 }
206 item.next.previous = item.previous;
207 tail.next = item;
208 item.previous = tail;
209 tail = item;
210 tail.next = null;
211 }
212 return item.value;
213 }
214 item = item.chain;
215 }
216 if(C_DEBUG){
217 System.err.println(" not found in Cache!!!!");
218 }
219 return null;
220 }
221
222 /**
223 * removes on item from the cache.
224 * @param key .The key to find the item.
225 */
226 public void remove(Object key){
227 if(key != null){
228 int hashIndex = (key.hashCode() & 0x7FFFFFFF) % m_maxSize;
229 CacheItem item = m_cache[hashIndex];
230 while (item != null){
231 if(item.key.equals(key)){
232 // got it
233 removeItem(item);
234 }
235 item = item.chain;
236 }
237 }
238 }
239
240 /**
241 * deletes one item from the cache. Not from the sequence chain.
242 * @param oldItem The item to be deleted.
243 */
244 private void removeFromTable(CacheItem oldItem){
245 if(C_DEBUG){
246 System.err.println(" --remove from chaincache: "+oldItem.key);
247 }
248 int hashIndex = ((oldItem.key).hashCode() & 0x7FFFFFFF) % m_maxSize;
249 CacheItem item = m_cache[hashIndex];
250 if(item == oldItem){
251 m_cache[hashIndex] = item.chain;
252 }else{
253 if(item != null){
254 while(item.chain != null){
255 if(item.chain == oldItem){
256 item.chain = item.chain.chain;
257 return;
258 }
259 item = item.chain;
260 }
261 }
262 }
263 }
264
265 /**
266 * removes one item from the cache and from the sequence chain.
267 */
268 private synchronized void removeItem(CacheItem item){
269
270 if(C_DEBUG){
271 System.err.println("--remove item from cache: "+item.key);
272 }
273 if(m_size < 2){
274 clearCache();
275 }else{
276 //first remove it from the hashtable
277 removeFromTable(item);
278 // now from the sequence chain
279 if((item != head) && (item != tail)){
280 item.previous.next = item.next;
281 item.next.previous = item.previous;
282 }else{
283 if(item == head){
284 head = item.next;
285 head.previous = null;
286 }
287 if (item == tail){
288 tail = item.previous;
289 tail.next = null;
290 }
291 }
292 m_size--;
293 }
294 }
295
296 /**
297 * Deletes all elements that depend on the template.
298 * use only if the cache is for elements.
299 *
300 * @return Vector a Vector with deleted items. Each item is a Vector with two elements: key and value.
301 */
302 public synchronized Vector deleteElementsByTemplate(String templateName){
303 CacheItem item = head;
304 Vector ret = new Vector();
305 while (item != null){
306 if(templateName.equals(((CmsElementDescriptor)item.key).getTemplateName())){
307 Vector actItem = new Vector();
308 actItem.add(0, item.key);
309 actItem.add(1, item.value);
310 ret.add(actItem);
311 removeItem(item);
312 }
313 item = item.next;
314 }
315 return ret;
316 }
317
318 /**
319 * Deletes all elements that depend on the class.
320 * use only if this cache is for elements.
321 * @return Vector a Vector with deleted items. Each item is a Vector with two elements: key and value.
322 */
323 public synchronized Vector deleteElementsByClass(String className){
324 CacheItem item = head;
325 Vector ret = new Vector();
326 while (item != null){
327 if(className.equals(((CmsElementDescriptor)item.key).getClassName())){
328 Vector actItem = new Vector();
329 actItem.add(0, item.key);
330 actItem.add(1, item.value);
331 ret.add(actItem);
332 removeItem(item);
333 }
334 item = item.next;
335 }
336 return ret;
337 }
338
339 /**
340 * Deletes elements after publish. All elements that depend on the
341 * uri and all element that say so have to be removed.
342 * use only if this cache is for elements.
343 * @return Vector a Vector with deleted items. Each item is a Vector with two elements: key and value.
344 */
345 public synchronized Vector deleteElementsAfterPublish(){
346 CacheItem item = head;
347 Vector ret = new Vector();
348 while (item != null){
349 try{
350 if (((A_CmsElement)item.value).getCacheDirectives().shouldRenew()){
351 Vector actItem = new Vector();
352 actItem.add(0, item.key);
353 actItem.add(1, item.value);
354 ret.add(actItem);
355 removeItem(item);
356 }
357 }catch(NullPointerException e){
358 // cachedirectives are null, so we delete this Element anyway.
359 Vector actItem = new Vector();
360 actItem.add(0, item.key);
361 actItem.add(1, item.value);
362 ret.add(actItem);
363 removeItem(item);
364 }
365 item = item.next;
366 }
367 return ret;
368 }
369
370 /**
371 * Deletes the uri from the Cache. Use only if this is the cache for uris.
372 *
373 */
374 public synchronized void deleteUri(String uri){
375 CacheItem item = head;
376 while (item != null){
377 if(uri.equals(((CmsUriDescriptor)item.key).getKey())){
378 removeItem(item);
379 // found the uri, ready.
380 return;
381 }
382 item = item.next;
383 }
384 }
385
386 /**
387 * Clears the cache completly.
388 */
389 public synchronized void clearCache(){
390 if(C_DEBUG){
391 System.err.println("--LruCache restarted");
392 }
393 m_cache = new CacheItem[m_maxSize];
394 m_size = 0;
395 head = null;
396 tail = null;
397 }
398
399 /**
400 * Gets the Information of max size and size for the cache.
401 *
402 * @return a Vector whith informations about the size of the cache.
403 */
404 public Vector getCacheInfo(){
405
406 if(C_DEBUG){
407 System.err.println("...Cache size should be:"+ m_size + " by a max size of "+m_maxSize);
408 int count = 0;
409 CacheItem item = head;
410 while (item != null){
411 count++;
412 item = item.next;
413 }
414 System.err.println("...Cache size is:"+count);
415 }
416 Vector info = new Vector();
417 info.addElement(new Integer(m_maxSize ));
418 info.addElement(new Integer(m_size));
419 return info;
420 }
421
422 /**
423 * gets all keys in the cache.
424 * @return a vector with the keys.
425 */
426 public synchronized Vector getAllKeys(){
427 Vector ret = new Vector();
428 CacheItem item = head;
429 while (item != null){
430 ret.add(item.key);
431 item = item.next;
432 }
433 return ret;
434 }
435
436 /*
437 * used for debuging only. Checks if the Cache is in a valid condition.
438 private void checkCondition(){
439 System.err.println("");
440 System.err.println("-- Verify condition of Cache");
441 System.err.println("--size: "+m_size);
442 CacheItem item = head;
443 int count = 1;
444 System.err.println("--");
445 System.err.println("--testing content from head to tail:");
446 while(item!=null){
447 System.err.println(" --"+count+". "+item.key);
448 count++;
449 item=item.next;
450 }
451 System.err.println("");
452 System.err.println("--now from tail to head:");
453 item = tail;
454 count--;
455 while(item!=null){
456 System.err.println(" --"+count+". "+item.key);
457 count--;
458 item=item.previous;
459 }
460 System.err.println("--now what is realy in cache:");
461 count = 1;
462 for (int i=0; i<m_maxSize; i++){
463 item = m_cache[i];
464 if(item == null){
465 // System.err.print(" element "+i+" ");
466 // System.err.println(" null");
467 }else{
468 System.err.print(" element "+i+" ");
469 System.err.println(" count="+count++ +" "+item.key);
470 while(item.chain != null){
471 item = item.chain;
472 System.err.println(" chainelement "+" count="+count++ +" "+item.key);
473 }
474 }
475 }
476 System.err.println("--test ready!!");
477 System.err.println("");
478
479 }
480 */
481 }