001/*
002 * WeakCache.java July 2006
003 *
004 * Copyright (C) 2006, Niall Gallagher <niallg@users.sf.net>
005 *
006 * Licensed under the Apache License, Version 2.0 (the "License");
007 * you may not use this file except in compliance with the License.
008 * You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or 
015 * implied. See the License for the specific language governing 
016 * permissions and limitations under the License.
017 */
018
019package org.simpleframework.xml.util;
020
021import java.util.ArrayList;
022import java.util.Iterator;
023import java.util.List;
024import java.util.WeakHashMap;
025
026/**
027 * The <code>WeakCache</code> object is an implementation of a cache
028 * that holds on to cached items only if the key remains in memory.
029 * This is effectively like a concurrent hash map with weak keys, it
030 * ensures that multiple threads can concurrently access weak hash
031 * maps in a way that lowers contention for the locks used. 
032 * 
033 * @author Niall Gallagher
034 */
035public class WeakCache<T> implements Cache<T> {
036   
037   /**
038    * This is used to store a list of segments for the cache.
039    */
040   private SegmentList list;
041   
042   /**
043    * Constructor for the <code>WeakCache</code> object. This is
044    * used to create a cache that stores values in such a way that
045    * when the key is garbage collected the value is removed from
046    * the map. This is similar to the concurrent hash map.
047    */
048   public WeakCache() {
049      this(10);
050   }
051   
052   /**
053    * Constructor for the <code>WeakCache</code> object. This is
054    * used to create a cache that stores values in such a way that
055    * when the key is garbage collected the value is removed from
056    * the map. This is similar to the concurrent hash map.
057    * 
058    * @param size this is the number of segments within the cache
059    */
060   public WeakCache(int size) {      
061      this.list = new SegmentList(size);
062   }
063   
064   public boolean isEmpty() {
065      for(Segment segment : list) {
066         if(!segment.isEmpty()) {
067            return false;
068         }
069      }
070      return true;
071   }
072   
073   
074   /**
075    * This method is used to insert a key value mapping in to the
076    * cache. The value can later be retrieved or removed from the
077    * cache if desired. If the value associated with the key is 
078    * null then nothing is stored within the cache.
079    * 
080    * @param key this is the key to cache the provided value to
081    * @param value this is the value that is to be cached
082    */
083   public void cache(Object key, T value) {
084      map(key).cache(key, value);
085   }
086   
087   /**
088    * This is used to exclusively take the value mapped to the 
089    * specified key from the cache. Invoking this is effectively
090    * removing the value from the cache.
091    * 
092    * @param key this is the key to acquire the cache value with
093    * 
094    * @return this returns the value mapped to the specified key 
095    */
096   public T take(Object key) {
097      return map(key).take(key);
098   }
099   
100   /**
101    * This method is used to get the value from the cache that is
102    * mapped to the specified key. If there is no value mapped to
103    * the specified key then this method will return a null.
104    * 
105    * @param key this is the key to acquire the cache value with
106    * 
107    * @return this returns the value mapped to the specified key 
108    */
109   public T fetch(Object key) {
110      return map(key).fetch(key);
111   }
112   
113   /**
114    * This is used to determine whether the specified key exists
115    * with in the cache. Typically this can be done using the 
116    * fetch method, which will acquire the object. 
117    * 
118    * @param key this is the key to check within this segment
119    * 
120    * @return true if the specified key is within the cache
121    */
122   public boolean contains(Object key) {
123      return map(key).contains(key);
124   }
125   
126   /**
127    * This method is used to acquire a <code>Segment</code> using
128    * the keys has code. This method effectively uses the hash to
129    * find a specific segment within the fixed list of segments.
130    * 
131    * @param key this is the key used to acquire the segment
132    * 
133    * @return this returns the segment used to get acquire value
134    */
135   private Segment map(Object key) {
136      return list.get(key);
137   }   
138   
139   /**
140    * This is used to maintain a list of segments. All segments that
141    * are stored by this object can be acquired using a given key.
142    * The keys hash is used to select the segment, this ensures that
143    * all read and write operations with the same key result in the
144    * same segment object within this list.
145    * 
146    * @author Niall Gallagher
147    */
148   private class SegmentList implements Iterable<Segment> {
149      
150      /**
151       * The list of segment objects maintained by this object.
152       */
153      private List<Segment> list;
154      
155      /**
156       * Represents the number of segments this object maintains.
157       */
158      private int size;
159      
160      /**
161       * Constructor for the <code>SegmentList</code> object. This
162       * is used to create a list of weak hash maps that can be
163       * acquired using the hash code of a given key. 
164       * 
165       * @param size this is the number of hash maps to maintain
166       */
167      public SegmentList(int size) {
168         this.list = new ArrayList<Segment>();
169         this.size = size;
170         this.create(size);         
171      }
172      
173      public Iterator<Segment> iterator() {
174         return list.iterator();
175      }
176      
177      /**
178       * This is used to acquire the segment using the given key.
179       * The keys hash is used to determine the index within the 
180       * list to acquire the segment, which is a synchronized weak        
181       * hash map storing the key value pairs for a given hash.
182       * 
183       * @param key this is the key used to determine the segment
184       * 
185       * @return the segment that is stored at the resolved hash 
186       */
187      public Segment get(Object key) {
188         int segment = segment(key);
189         
190         if(segment < size) {
191            return list.get(segment);
192         }
193         return null;
194      }
195      
196      /**
197       * Upon initialization the segment list is populated in such
198       * a way that synchronization is not needed. Each segment is
199       * created and stored in an increasing index within the list.
200       * 
201       * @param size this is the number of segments to be used
202       */
203      private void create(int size) {
204         int count = size;
205         
206         while(count-- > 0) {
207            list.add(new Segment());
208         }
209      }
210      
211      /**
212       * This method performs the translation of the key hash code
213       * to the segment index within the list. Translation is done
214       * by acquiring the modulus of the hash and the list size.
215       * 
216       * @param key this is the key used to resolve the index
217       * 
218       * @return the index of the segment within the list 
219       */
220      private int segment(Object key) {
221         return Math.abs(key.hashCode() % size);
222      }
223   }
224   
225   /**
226    * The segment is effectively a synchronized weak hash map. If is
227    * used to store the key value pairs in such a way that they are
228    * kept only as long as the garbage collector does not collect 
229    * the key. This ensures the cache does not cause memory issues. 
230    * 
231    * @author Niall Gallagher
232    */
233   private class Segment extends WeakHashMap<Object, T> {      
234      
235      /**
236       * This method is used to insert a key value mapping in to the
237       * cache. The value can later be retrieved or removed from the
238       * cache if desired. If the value associated with the key is 
239       * null then nothing is stored within the cache.
240       * 
241       * @param key this is the key to cache the provided value to
242       * @param value this is the value that is to be cached
243       */
244      public synchronized void cache(Object key, T value) {
245         put(key, value);
246      }
247      
248      /**
249       * This method is used to get the value from the cache that is
250       * mapped to the specified key. If there is no value mapped to
251       * the specified key then this method will return a null.
252       * 
253       * @param key this is the key to acquire the cache value with
254       * 
255       * @return this returns the value mapped to the specified key 
256       */
257      public synchronized T fetch(Object key) {
258         return get(key);
259      }
260      
261      /**
262       * This is used to exclusively take the value mapped to the 
263       * specified key from the cache. Invoking this is effectively
264       * removing the value from the cache.
265       * 
266       * @param key this is the key to acquire the cache value with
267       * 
268       * @return this returns the value mapped to the specified key 
269       */
270      public synchronized T take(Object key) {
271         return remove(key);
272      }
273 
274      /**
275       * This is used to determine whether the specified key exists
276       * with in the cache. Typically this can be done using the 
277       * fetch method, which will acquire the object. 
278       * 
279       * @param key this is the key to check within this segment
280       * 
281       * @return true if the specified key is within the cache
282       */
283      public synchronized boolean contains(Object key) {
284         return containsKey(key);
285      }
286   }
287}