KickJava   Java API By Example, From Geeks To Geeks.

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


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.HashMap JavaDoc;
12 import java.util.Iterator JavaDoc;
13 import java.util.Map JavaDoc;
14 import java.util.NoSuchElementException JavaDoc;
15
16 /**
17  * MRU Eviction Queue implementation.
18  * <p/>
19  * This nodeMap is sorted by MRU. The first entry in the nodeMap
20  * will also be the most recently used entry. The sort is implicit
21  * based on a Stack that we can implicitly sort to the top by moving
22  * a node that is used to the top of the eviction stack.
23  *
24  * @author Daniel Huang (dhuang@jboss.org)
25  * @version $Revision: 1.7 $
26  */

27 public class MRUQueue implements EvictionQueue
28 {
29    // we use our own Stack/Linked List implementation here because it guarantees O(n) = 1 for add, remove, get and
30
// we can sort it in order of MRU implicitly while still getting O(n) = 1 access time
31
// throughout.
32
Map JavaDoc nodeMap;
33    EvictionQueueList list;
34    private int numElements = 0;
35
36    MRUQueue()
37    {
38       nodeMap = new HashMap JavaDoc();
39       list = new EvictionQueueList();
40    }
41
42    /**
43     * This call moves a NodeEntry to the top of the stack.
44     * <p/>
45     * When a node is visited this method should be called to guarantee MRU ordering.
46     *
47     * @param fqn Fqn of the nodeEntry to move to the top of the stack.
48     */

49    void moveToTopOfStack(Fqn fqn)
50    {
51       EvictionListEntry le = (EvictionListEntry) nodeMap.remove(fqn);
52       if (le != null)
53       {
54          list.remove(le);
55          list.addToTop(le);
56          nodeMap.put(le.node.getFqn(), le);
57       }
58    }
59
60    /**
61     * Will return the first entry in the nodeMap.
62     * <p/>
63     * The first entry in this nodeMap will also be the most recently used entry.
64     *
65     * @return The first node entry in nodeMap.
66     */

67    public NodeEntry getFirstNodeEntry()
68    {
69       try
70       {
71          return list.getFirst().node;
72       }
73       catch (NoSuchElementException JavaDoc e)
74       {
75          //
76
}
77
78       return null;
79    }
80
81    public NodeEntry getNodeEntry(Fqn fqn)
82    {
83       EvictionListEntry le = (EvictionListEntry) nodeMap.get(fqn);
84       if (le != null)
85          return le.node;
86
87       return null;
88    }
89
90    public NodeEntry getNodeEntry(String JavaDoc fqn)
91    {
92       return this.getNodeEntry(Fqn.fromString(fqn));
93    }
94
95    public boolean containsNodeEntry(NodeEntry entry)
96    {
97       return nodeMap.containsKey(entry.getFqn());
98    }
99
100    public void removeNodeEntry(NodeEntry entry)
101    {
102       EvictionListEntry le = (EvictionListEntry) nodeMap.remove(entry.getFqn());
103       if (le != null)
104       {
105          list.remove(le);
106          this.numElements -= le.node.getNumberOfElements();
107       }
108    }
109
110    public void addNodeEntry(NodeEntry entry)
111    {
112       if (!this.containsNodeEntry(entry))
113       {
114          entry.queue = this;
115          EvictionListEntry le = new EvictionListEntry(entry);
116          list.addToBottom(le);
117          nodeMap.put(entry.getFqn(), le);
118          this.numElements += entry.getNumberOfElements();
119       }
120    }
121
122    public int getNumberOfNodes()
123    {
124       return list.size();
125    }
126
127    public int getNumberOfElements()
128    {
129       return this.numElements;
130    }
131
132    public void modifyElementCount(int difference)
133    {
134       this.numElements += difference;
135    }
136
137    public void clear()
138    {
139       nodeMap.clear();
140       list.clear();
141       this.numElements = 0;
142    }
143
144    public Iterator JavaDoc iterate()
145    {
146       return list.iterator();
147    }
148
149    public String JavaDoc toString()
150    {
151       return list.toString();
152    }
153 }
154
Popular Tags