CmsLruCache


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