KickJava   Java API By Example, From Geeks To Geeks.

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


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.Iterator JavaDoc;
12 import java.util.LinkedHashMap JavaDoc;
13 import java.util.Map JavaDoc;
14
15 /**
16  * LRU Eviction Queue implementation.
17  * <p/>
18  * This eviction queue will iterate properly through two sorted lists.
19  * One sorted by maxAge and the other sorted by idleTime.
20  *
21  * @author Daniel Huang (dhuang@jboss.org)
22  * @version $Revision: 1.4 $
23  */
24 public class LRUQueue implements EvictionQueue
25 {
26    private Map JavaDoc maxAgeQueue;
27    private Map JavaDoc lruQueue;
28    private long alternatingCount = 0;
29    private int numElements = 0;
30
31    LRUQueue()
32    {
33       maxAgeQueue = new LinkedHashMap JavaDoc();
34       lruQueue = new LinkedHashMap JavaDoc(16, 0.75f, true);
35    }
36
37    void reorderByLRU(Fqn fqn)
38    {
39       // leave the max age queue alone - it is like a fifo.
40
41       // the lru queue is access ordered. meaning the most recently read item is moved to the bottom of the queue.
42 // simply calling get against it visits it and will cause LinkedHashMap to move it to the bottom of the queue.
43 lruQueue.get(fqn);
44    }
45
46    public NodeEntry getFirstNodeEntry()
47    {
48       // because the underlying queue is in two differently sorted queues, we alternate between them when calling
49 // a generic getFirstNodeEntry.
50 // we must alternate to keep things balanced when evicting nodes based on the maxNodes attribute. We don't
51 // want to just prune from one queue but rather we want to be able to prune from both.
52 NodeEntry ne;
53       if (alternatingCount % 2 == 0)
54       {
55          ne = this.getFirstLRUNodeEntry();
56          if (ne == null)
57          {
58             ne = this.getFirstMaxAgeNodeEntry();
59          }
60       }
61       else
62       {
63          ne = this.getFirstMaxAgeNodeEntry();
64          if (ne == null)
65          {
66             ne = this.getFirstLRUNodeEntry();
67          }
68       }
69       alternatingCount++;
70       return ne;
71    }
72
73    public NodeEntry getFirstLRUNodeEntry()
74    {
75       if (lruQueue.size() > 0)
76       {
77          return (NodeEntry) lruQueue.values().iterator().next();
78       }
79
80       return null;
81    }
82
83    public NodeEntry getFirstMaxAgeNodeEntry()
84    {
85       if (maxAgeQueue.size() > 0)
86       {
87          return (NodeEntry) maxAgeQueue.values().iterator().next();
88       }
89
90       return null;
91    }
92
93    public NodeEntry getNodeEntry(Fqn fqn)
94    {
95       return (NodeEntry) lruQueue.get(fqn);
96    }
97
98    public NodeEntry getNodeEntry(String JavaDoc fqn)
99    {
100       return this.getNodeEntry(Fqn.fromString(fqn));
101    }
102
103    public boolean containsNodeEntry(NodeEntry entry)
104    {
105       return this.maxAgeQueue.containsKey(entry.getFqn());
106    }
107
108    void removeNodeEntryFromLRU(NodeEntry entry)
109    {
110       Fqn fqn = entry.getFqn();
111       lruQueue.remove(fqn);
112    }
113
114    void removeNodeEntryFromMaxAge(NodeEntry entry)
115    {
116       Fqn fqn = entry.getFqn();
117       maxAgeQueue.remove(fqn);
118    }
119
120    public void removeNodeEntry(NodeEntry entry)
121    {
122       if (!this.containsNodeEntry(entry))
123       {
124          return;
125       }
126       Fqn fqn = entry.getFqn();
127       NodeEntry ne1 = (NodeEntry) lruQueue.remove(fqn);
128       NodeEntry ne2 = (NodeEntry) maxAgeQueue.remove(fqn);
129
130       if (ne1 == null || ne2 == null)
131       {
132          throw new RuntimeException JavaDoc("The queues are out of sync.");
133       }
134
135       this.numElements -= ne1.getNumberOfElements();
136
137    }
138
139    public void addNodeEntry(NodeEntry entry)
140    {
141       if (!this.containsNodeEntry(entry))
142       {
143          Fqn fqn = entry.getFqn();
144          entry.queue = this;
145          maxAgeQueue.put(fqn, entry);
146          lruQueue.put(fqn, entry);
147          this.numElements += entry.getNumberOfElements();
148       }
149    }
150
151    public int getNumberOfNodes()
152    {
153       return maxAgeQueue.size();
154    }
155
156    public int getNumberOfElements()
157    {
158       return this.numElements;
159    }
160
161    public void clear()
162    {
163       maxAgeQueue.clear();
164       lruQueue.clear();
165       this.numElements = 0;
166    }
167
168    public void modifyElementCount(int difference)
169    {
170       this.numElements += difference;
171    }
172
173    public Iterator JavaDoc iterate()
174    {
175       return lruQueue.values().iterator();
176    }
177
178    final Iterator JavaDoc iterateMaxAgeQueue()
179    {
180       return maxAgeQueue.values().iterator();
181    }
182
183    final Iterator JavaDoc iterateLRUQueue()
184    {
185       return lruQueue.values().iterator();
186    }
187
188 }
189
Popular Tags