KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jboss > cache > eviction > ElementSizeQueue


1 /*
2  * JBoss, the OpenSource J2EE webOS
3  *
4  * Distributable under LGPL license.
5  * See terms of license at gnu.org.
6  */
7 package org.jboss.cache.eviction;
8
9 import org.jboss.cache.Fqn;
10
11 import java.util.Collections JavaDoc;
12 import java.util.Comparator JavaDoc;
13 import java.util.HashMap JavaDoc;
14 import java.util.HashSet JavaDoc;
15 import java.util.Iterator JavaDoc;
16 import java.util.LinkedList JavaDoc;
17 import java.util.List JavaDoc;
18 import java.util.Map JavaDoc;
19 import java.util.NoSuchElementException JavaDoc;
20 import java.util.Set JavaDoc;
21
22 /**
23  * @author Daniel Huang
24  * @version $Revision: 1.2 $
25  */
26 public class ElementSizeQueue implements SortedEvictionQueue
27 {
28    private Map JavaDoc nodeMap;
29    private LinkedList JavaDoc evictionList;
30    private Comparator JavaDoc comparator;
31
32    private Set JavaDoc removalQueue;
33    private int numElements = 0;
34
35    ElementSizeQueue()
36    {
37       nodeMap = new HashMap JavaDoc();
38       evictionList = new LinkedList JavaDoc();
39       comparator = new MaxElementComparator();
40       removalQueue = new HashSet JavaDoc();
41    }
42
43    public void resortEvictionQueue()
44    {
45       Collections.sort(evictionList, comparator);
46    }
47
48    public NodeEntry getFirstNodeEntry()
49    {
50       try
51       {
52          NodeEntry ne;
53          while ((ne = (NodeEntry) evictionList.getFirst()) != null)
54          {
55             if (removalQueue.contains(ne))
56             {
57                evictionList.removeFirst();
58                removalQueue.remove(ne);
59             }
60             else
61             {
62                break;
63             }
64          }
65          return ne;
66       }
67       catch (NoSuchElementException JavaDoc e)
68       {
69          //
70 }
71
72       return null;
73    }
74
75    public NodeEntry getNodeEntry(Fqn fqn)
76    {
77       return (NodeEntry) nodeMap.get(fqn);
78    }
79
80    public NodeEntry getNodeEntry(String JavaDoc fqn)
81    {
82       return this.getNodeEntry(Fqn.fromString(fqn));
83    }
84
85    public boolean containsNodeEntry(NodeEntry entry)
86    {
87       Fqn fqn = entry.getFqn();
88       return this.getNodeEntry(fqn) != null;
89    }
90
91    public void removeNodeEntry(NodeEntry entry)
92    {
93       NodeEntry ne = (NodeEntry) nodeMap.remove(entry.getFqn());
94       if (ne != null)
95       {
96          // don't remove directly from the LinkedList otherwise we will incur a O(n) = n
97 // performance penalty for every removal! In the prune method for LFU, we will iterate the LinkedList through ONCE
98 // doing a single O(n) = n operation and removal. This is much preferred over running O(n) = n every single time
99 // remove is called. There is also special logic in the getFirstNodeEntry that will know to check
100 // the removalQueue before returning.
101 this.removalQueue.add(ne);
102 /* if(!evictionList.remove(ne)) {
103             throw new RuntimeException("");
104          } */
105          this.numElements -= ne.getNumberOfElements();
106       }
107    }
108
109    public void addNodeEntry(NodeEntry entry)
110    {
111       if (!this.containsNodeEntry(entry))
112       {
113          Fqn fqn = entry.getFqn();
114          entry.queue = this;
115          nodeMap.put(fqn, entry);
116          evictionList.add(entry);
117          this.numElements += entry.getNumberOfElements();
118       }
119    }
120
121    public int getNumberOfNodes()
122    {
123       return nodeMap.size();
124    }
125
126    public int getNumberOfElements()
127    {
128       return this.numElements;
129    }
130
131    public void modifyElementCount(int difference)
132    {
133       this.numElements += difference;
134    }
135
136    public void clear()
137    {
138       nodeMap.clear();
139       evictionList.clear();
140       removalQueue.clear();
141       this.numElements = 0;
142    }
143
144    final List JavaDoc getEvictionList()
145    {
146       return evictionList;
147    }
148
149    final Set JavaDoc getRemovalQueue()
150    {
151       return removalQueue;
152    }
153
154    final void prune()
155    {
156       Iterator JavaDoc it = evictionList.iterator();
157       while (it.hasNext() && removalQueue.size() > 0)
158       {
159          if (removalQueue.remove(it.next()))
160          {
161             it.remove();
162          }
163       }
164    }
165
166    public Iterator JavaDoc iterate()
167    {
168       return evictionList.iterator();
169    }
170
171    /**
172     * Comparator class for Max Elements.
173     * <p/>
174     * This class will sort the eviction queue in the correct eviction order.
175     * The top of the list should evict before the bottom of the list.
176     * <p/>
177     * The sort is based on descending order of numElements.
178     * <p/>
179     * Note: this class has a natural ordering that is inconsistent with equals as defined by the java.lang.Comparator
180     * contract.
181     */
182    static class MaxElementComparator implements Comparator JavaDoc
183    {
184       MaxElementComparator()
185       {
186       }
187
188       public int compare(Object JavaDoc o, Object JavaDoc o1)
189       {
190          if (o.equals(o1))
191          {
192             return 0;
193          }
194          NodeEntry ne = (NodeEntry) o;
195          NodeEntry ne2 = (NodeEntry) o1;
196
197          int neNumElements = ne.getNumberOfElements();
198          int neNumElements2 = ne2.getNumberOfElements();
199
200          if (neNumElements > neNumElements2)
201          {
202             return -1;
203          }
204          else if (neNumElements < neNumElements2)
205          {
206             return 1;
207          }
208          else if (neNumElements == neNumElements2)
209          {
210             return 0;
211          }
212
213          throw new RuntimeException JavaDoc("Should never reach this condition");
214       }
215    }
216
217 }
218
219
220
Popular Tags