StateCache


1   /* 
2    * $Id: StateCache.java,v 1.4 2005/07/08 12:04:11 kofron Exp $
3    * 
4    * Copyright 2004
5    *    Distributed Systems Research Group
6    *    Department of Software Engineering
7    *    Faculty of Mathematics and Physics
8    *    Charles University, Prague
9    *
10   * Copyright 2005
11   *    Formal Methods In Software Engineering Group
12   *    Institute of Computer Science
13   *    Academy of Sciences of the Czech Republic
14   * 
15   * This code was developed by Jan Kofron <kofron@nenya.ms.mff.cuni.cz>
16   */
17  
18  package SOFA.SOFAnode.Util.DFSRChecker.DFSR;
19  
20  import java.util.HashMap  ;
21  import java.util.ArrayList  ;
22  import java.util.Iterator  ;
23  import java.util.NoSuchElementException  ;
24  
25  
26  import SOFA.SOFAnode.Util.DFSRChecker.parser.Debug;
27  import SOFA.SOFAnode.Util.DFSRChecker.state.Signature;
28  
29  /**
30   * This class implements the cache for states while passing the state space of
31   * the protocol. The performance of this class is crucial for the checking
32   * speed.
33   * 
34   * In order to be as fast as possible the HashSet is used. The performance of
35   * this data structure can be fine-tuned via parameters 'load factor' (0.75 is
36   * the default value) and 'initial capacity'.
37   */
38  public class StateCache {
39  
40      /**
41       * Creates a new instance of StateCache.
42       * 
43       * @param maximalcapacity
44       *            the maximal capacity of the cache. In the case the cache
45       *            becomes full, some states are deleted from the cache.
46       */
47      public StateCache(int maximalcapacity) {
48  
49          int initialcapacity = 1000;
50          cache = new HashMap  (initialcapacity, load);
51          if (maximalcapacity != 0)
52              this.maximalCapacity = maximalcapacity;
53          else
54              this.maximalCapacity = Integer.MAX_VALUE;
55  
56          Debug.println(2, "Cache created with capacity of " + this.maximalCapacity + " items.");
57  
58      }
59  
60      /**
61       * Inserts new items to the cache and erases some members if it is too large
62       * already.
63       * 
64       * @throws ItemAlreadyPresentException
65       */
66      public void insert(Signature item) throws ItemAlreadyPresentException {
67  
68          if (cache.size() >= maximalCapacity) {
69              Iterator   it = cache.keySet().iterator();
70              int size = cache.size() / cachePurgeRatio;
71              Debug.print(2, "Purging the cache.....");
72  
73              ArrayList   keys = new ArrayList  ();
74  
75              try {
76                  for (int i = 0; i < size; ++i) {
77                      for (int j = 0; j < currentPurgeIndex; ++j)
78                          it.next();
79  
80                      keys.add(it.next());
81  
82                      for (int j = 0; j < cachePurgeRatio - currentPurgeIndex - 1; ++j)
83                          it.next();
84                  }
85              } catch (NoSuchElementException   e) {
86              }
87  
88              Iterator   it2 = keys.iterator();
89              size = keys.size();
90              for (int i = 0; i < size; ++i) {
91                  cache.remove(it2.next());
92              }
93  
94              currentPurgeIndex = (currentPurgeIndex + 1) % cachePurgeRatio;
95  
96              Debug.println(size + " keys purged.");
97          }
98          //Debug.println("Adding item to the cache: " + item);
99          if (cache.put(item, item) != null)
100             throw new ItemAlreadyPresentException();
101     }
102 
103     /**
104      * @return true if the specified item is present within the database.
105      */
106     public boolean isPresent(Signature item) {
107         /*
108          * boolean oldacc = item.isAcceptingReachable();
109          * item.setAcceptingReachable(false); if (!cache.containsKey(item)) {
110          * item.setAcceptingReachable(true); if (!cache.containsKey(item)) {
111          * item.setAcceptingReachable(oldacc); return false; } }
112          * 
113          * item.setAcceptingReachable(oldacc); return true;
114          */
115         return cache.containsKey(item);
116     }
117 
118     /**
119      * Removes the item from the database.
120      * 
121      * @throws ItemNotPresentException
122      *             if the specified object isn't present
123      */
124     public void remove(Signature item) throws ItemNotPresentException {
125         /*
126          * boolean oldacc = item.isAcceptingReachable();
127          * item.setAcceptingReachable(false); if (cache.remove(item) == null) {
128          * item.setAcceptingReachable(true); if (cache.remove(item) == null) {
129          * item.setAcceptingReachable(oldacc); throw new
130          * ItemNotPresentException(); } } item.setAcceptingReachable(oldacc);
131          */
132         if (cache.remove(item) == null) {
133             throw new ItemNotPresentException();
134         }
135     }
136 
137     /**
138      * Tests whether the given state was visited or not.
139      * 
140      * @param signature
141      *            signature to be tested
142      * @return true if from this state an accepting state is reachable
143      */
144     public boolean acceptingReach(Signature signature) {
145         /*
146          * boolean is; signature.setAcceptingReachable(true);
147          * 
148          * is = cache.containsKey(signature);
149          * signature.setAcceptingReachable(false);
150          * 
151          * return is;
152          */
153         try {
154             return ((((Signature) cache.get(signature)).acceptingCycleId) >>> 63) != 0;
155         } catch (NullPointerException   e) {
156             return false;
157         }
158     }
159 
160     /**
161      * Sets the parameter of acceptance to the state.
162      * 
163      * @param signature
164      *            the state to be changed
165      */
166     public void setAcceptingReach(Signature signature) {
167         try {
168             this.remove(signature);
169         } catch (ItemNotPresentException e) { // the item was purged out of the
170             // cache, nothing to fix
171             return;
172         }
173 
174         signature.setAcceptingReachable(true);
175 
176         // this shouldn't throw an exception
177 
178         if (cache.put(signature, signature) != null)
179             throw new RuntimeException  ("Inconsistent state cache");
180 
181     }
182 
183     /**
184      * Gets the cycle id.
185      * 
186      * @param signature
187      *            the signature for which we want the cycle id
188      * @return the cycle id
189      */
190     public long getCycleId(Signature signature) {
191         Signature sig = (Signature) cache.get(signature);
192         return (sig.acceptingCycleId & (~((long) 1 << 63)));
193     }
194 
195     /**
196      * Sets the signature to the new cycle id.
197      * 
198      * @param signature
199      *            the signature
200      * @param id
201      *            the cycleid
202      */
203     public void setCycleId(Signature signature, long id) {
204         Signature sig = (Signature) cache.get(signature);
205         if (((sig.acceptingCycleId >> 63) & 1) != 0)
206             sig.acceptingCycleId = id | ((long) 1 << 63);
207         else
208             sig.acceptingCycleId = id & (~((long) 1 << 63));
209 
210     }
211 
212     /**
213      * Updates the signature with new information - useful for fast signature change.
214      * @param signature signature to be updated.
215      */
216     public void updateItem(Signature signature) {
217         try {
218             this.remove(signature);
219         } catch (ItemNotPresentException e) { // the item was purged out of the
220             // cache, nothing to fix
221             return;
222         }
223 
224         // this shouldn't throw an exception
225         if (cache.put(signature, signature) != null)
226             throw new RuntimeException  ("Inconsistent state cache");
227 
228     }
229 
230     /**
231      * Clears the cache.
232      */
233     public void clear() {
234         cache.clear();
235     }
236 
237     /**
238      * The cache is implemented via HashSet. The items stored in the HashSet are
239      * state identifiers.
240      */
241     private HashMap   cache;
242 
243     /**
244      * The load factor of the hashset. The factor value can be set between 0 and
245      * 1. The lower values improves time performance, but extends the memory
246      * requirements.
247      */
248     private final float load = 0.75f;
249 
250     /**
251      * Determines the maximal count of items stored within the cache
252      */
253     private final int maximalCapacity;
254 
255     /**
256      * Vars for purging the cache
257      */
258     private final int cachePurgeRatio = 8;
259 
260     /**
261      * Denotes the last purge index.
262      */
263     private int currentPurgeIndex = 0;
264 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags