001: /*
002: * CacheList.java February 2001
003: *
004: * Copyright (C) 2001, Niall Gallagher <niallg@users.sf.net>
005: *
006: * This library is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU Lesser General Public
008: * License as published by the Free Software Foundation.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
013: * GNU Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General
016: * Public License along with this library; if not, write to the
017: * Free Software Foundation, Inc., 59 Temple Place, Suite 330,
018: * Boston, MA 02111-1307 USA
019: */
020:
021: package simple.util.cache;
022:
023: import java.util.HashMap;
024:
025: /**
026: * This is a LRU, Least Recently Used, list that will store a
027: * limited number of objects. When there is an attempt to store
028: * an object into this list when the list is full then the Least
029: * Recently Used objects are removed from the list, In fact this
030: * will remove twenty percent of the Least Recently Used objects,
031: * this will ensure that there is not a removal of an object for
032: * each insert into the list, this may or may not increase the
033: * performance.
034: *
035: * @author Niall Gallagher
036: */
037: public class CacheList {
038:
039: /**
040: * This is the lists default initial size.
041: */
042: private static final int DEFAULT_SIZE = 16;
043:
044: /**
045: * This is used for quicker access of objects.
046: */
047: private HashMap map;
048:
049: /**
050: * This specifies the front of the list.
051: */
052: private Entry root;
053:
054: /**
055: * This specifies the end of the list.
056: */
057: private Entry tail;
058:
059: /**
060: * The number of items allowed in the list.
061: */
062: private int maxSize;
063:
064: /**
065: * This is the number of items in the list.
066: */
067: private int items;
068:
069: /**
070: * This will create an list with a maximum allowed number of
071: * objects to be inserted into the list. If there are further
072: * inserts after the list fills, then the least hit objects
073: * will be removed from the list, the lookup method is a hit.
074: */
075: public CacheList() {
076: this (DEFAULT_SIZE);
077: }
078:
079: /**
080: * This will create an list with a maximum allowed number of
081: * objects to be inserted into the list. If there are further
082: * inserts after the list fills, then the least hit objects
083: * will be removed from the list, the lookup method is a hit.
084: *
085: * @param maxSize the maximum allowed number of objects
086: */
087: public CacheList(int maxSize) {
088: this .map = new HashMap((maxSize + 1) * 2, 0.2f);
089: this .maxSize = maxSize;
090: }
091:
092: /**
093: * This uses a doubly linked list to store the object within
094: * this list. This uses the key specified to store the object
095: * in the <code>CacheList</code>. Should not use a duplicate key
096: * in the list.
097: *
098: * @param key a unique key, that is not used by any other object
099: * @param obj the object that is being stored in the list
100: */
101: public synchronized void insert(Object key, Object obj) {
102: Entry entry = new Entry();
103: entry.data = obj;
104: entry.key = key;
105: remove(key);
106: map.put(key, entry);
107: insert(entry);
108: clean();
109: }
110:
111: /**
112: * This is used to remove some of the items in the list. This
113: * will remove items from the tail of the list. This means that
114: * only items with the lowest hit rate will be purged.
115: */
116: private void clean() {
117: if (items <= maxSize) {
118: return;
119: }
120: while (tail != null) {
121: if (items <= (maxSize * 0.8f)) {
122: break;
123: }
124: remove(tail.key);
125: }
126: }
127:
128: /**
129: * This uses a doubly linked list to store the entry within
130: * this list. This will simply link the entry in at the top.
131: *
132: * @param entry the entry being linked into the list
133: */
134: private void insert(Entry entry) {
135: if (items == 0) {
136: Entry end = new Entry();
137: Entry start = entry;
138:
139: start.prev = null;
140: end.next = null;
141: end.prev = start;
142: start.next = end;
143: root = start;
144: tail = end;
145: } else if (items == 1) {
146: Entry end = root;
147: Entry start = entry;
148:
149: start.prev = null;
150: end.next = null;
151: end.prev = start;
152: start.next = end;
153: root = start;
154: tail = end;
155: } else {
156: Entry next = root;
157: Entry start = entry;
158:
159: start.prev = null;
160: start.next = next;
161: next.prev = start;
162: root = start;
163: }
164: items++;
165: }
166:
167: /**
168: * This method will search the list to see if there
169: * is an object stored in the list under that name.
170: * If there is an object stored within the list using
171: * the key specified this returns true otherwise false.
172: *
173: * @param key the reference to the list object
174: *
175: * @return true only if the object is in the list
176: */
177: public synchronized boolean contains(Object key) {
178: return map.containsKey(key);
179: }
180:
181: /**
182: * This method will search to see if it can find the
183: * object stored under the key specified and return it.
184: *
185: * @param key the reference to the stored object
186: *
187: * @return the object if it is stored otherwise null
188: */
189: public synchronized Object lookup(Object key) {
190: Object entry = map.get(key);
191: if (entry == null) {
192: return null;
193: }
194: top((Entry) entry);
195: return root.data;
196: }
197:
198: /**
199: * This is used to move an entry object to the top of the doubly
200: * linked list. This is a feature of this list to allow the most
201: * frequently hit entrys in the list to stay at the top of the
202: * linked list. This means that most hit items stay in the list.
203: *
204: * @param entry the entry to move to the top of the list
205: */
206: private void top(Entry entry) {
207: if (entry != null && entry != root && items > 0) {
208: if (entry == tail) {
209: Entry end = tail.prev;
210: Entry start = entry;
211: Entry next = root;
212:
213: end.next = null;
214: start.prev = null;
215: start.next = next;
216: next.prev = start;
217: root = start;
218: tail = end;
219: } else {
220: Entry prev = entry.prev;
221: Entry next = entry.next;
222: Entry start = entry;
223:
224: next.prev = prev;
225: prev.next = next;
226: start.prev = null;
227: start.next = null;
228: start.next = root;
229: root.prev = start;
230: root = start;
231: }
232: }
233: }
234:
235: /**
236: * This method will search the list to see if there
237: * is an object stored in the list under that name.
238: * If there is an object stored within the list using
239: * the key specified this removes that object.
240: *
241: * @param key the reference to the list object
242: */
243: public synchronized Object remove(Object key) {
244: return remove((Entry) map.remove(key));
245: }
246:
247: /**
248: * This method removes an object from the list. This will
249: * unlink the entry object that is stored in the list using
250: * the reference given. This updates the item count.
251: *
252: * @param entry the object that is being unlinked
253: */
254: private Object remove(Entry entry) {
255: if (entry != null && items > 0) {
256: if (root == tail) {
257: root = null;
258: } else if (entry == tail) {
259: tail = tail.prev;
260: tail.next = null;
261: } else if (entry == root) {
262: root = root.next;
263: root.prev = null;
264: } else {
265: entry.prev.next = entry.next;
266: entry.next.prev = entry.prev;
267: }
268: items--;
269: return entry.data;
270: }
271: return null;
272: }
273:
274: /**
275: * This simply specifies the maximum size that this
276: * list can grow and then purges the Least Recently
277: * Used items in the list, that is items at the tail.
278: *
279: * @param maxSize the max size allowed for the list
280: */
281: public synchronized void resize(int maxSize) {
282: this .maxSize = maxSize;
283: clean();
284: }
285:
286: /**
287: * This will simply return the number of items in the list.
288: * Because this is a Least Recently Used list this should
289: * never return a length greater that the maximum size.
290: *
291: * @return the number of items that are in this list.
292: */
293: public synchronized int length() {
294: return items;
295: }
296:
297: /**
298: * This is used to that the capacity of the list can be
299: * determined. The capacity indicates at what point entrys
300: * are pushed off the list. Only capacity entrys can fit
301: * into the list before the least recently used is removed.
302: *
303: * @return this returns the number of possible entrys
304: */
305: public synchronized int capacity() {
306: return maxSize;
307: }
308:
309: /**
310: * This is a simple method that will purge all entrys from
311: * this list. This basically deletes the linked list and
312: * emptys the <code>HashMap</code> and sets the item count
313: * to zero. The garbage collector can collect all objects
314: * that were previously referenced by this list.
315: */
316: public synchronized void clear() {
317: if (items > 0) {
318: map.clear();
319: }
320: root = null;
321: tail = null;
322: items = 0;
323: }
324:
325: /**
326: * This data structure is used to create a doubly
327: * linked list within the <code>CacheList</code>. This
328: * also remembers specifics about the item being
329: * stored. This allows meta-data to be accessed
330: * quickly, and also enables the list to be traversed.
331: */
332: private class Entry {
333: public Object data;
334: public Object key;
335: public Entry next;
336: public Entry prev;
337: }
338: }
|