001 /** 002 * JDBM LICENSE v1.00 003 * 004 * Redistribution and use of this software and associated documentation 005 * ("Software"), with or without modification, are permitted provided 006 * that the following conditions are met: 007 * 008 * 1. Redistributions of source code must retain copyright 009 * statements and notices. Redistributions must also contain a 010 * copy of this document. 011 * 012 * 2. Redistributions in binary form must reproduce the 013 * above copyright notice, this list of conditions and the 014 * following disclaimer in the documentation and/or other 015 * materials provided with the distribution. 016 * 017 * 3. The name "JDBM" must not be used to endorse or promote 018 * products derived from this Software without prior written 019 * permission of Cees de Groot. For written permission, 020 * please contact cg@cdegroot.com. 021 * 022 * 4. Products derived from this Software may not be called "JDBM" 023 * nor may "JDBM" appear in their names without prior written 024 * permission of Cees de Groot. 025 * 026 * 5. Due credit should be given to the JDBM Project 027 * (http://jdbm.sourceforge.net/). 028 * 029 * THIS SOFTWARE IS PROVIDED BY THE JDBM PROJECT AND CONTRIBUTORS 030 * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT 031 * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 032 * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL 033 * CEES DE GROOT OR ANY CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 034 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 035 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 036 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 037 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 038 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 039 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 040 * OF THE POSSIBILITY OF SUCH DAMAGE. 041 * 042 * Copyright 2000 (C) Cees de Groot. All Rights Reserved. 043 * Contributions are Copyright (C) 2000 by their associated contributors. 044 * 045 * $Id: MRU.java,v 1.8 2005/06/25 23:12:31 doomdark Exp $ 046 */ 047 048 package jdbm.helper; 049 050 import java.util.Enumeration; 051 import java.util.Hashtable; 052 import java.util.Vector; 053 054 import org.apache.directory.server.i18n.I18n; 055 056 057 /** 058 * MRU - Most Recently Used cache policy. 059 * 060 * Methods are *not* synchronized, so no concurrent access is allowed. 061 * 062 * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a> 063 * @version $Id: MRU.java,v 1.8 2005/06/25 23:12:31 doomdark Exp $ 064 */ 065 public class MRU implements CachePolicy 066 { 067 068 /** Cached object hashtable */ 069 Hashtable _hash = new Hashtable(); 070 071 /** 072 * Maximum number of objects in the cache. 073 */ 074 int _max; 075 076 /** 077 * Beginning of linked-list of cache elements. First entry is element 078 * which has been used least recently. 079 */ 080 CacheEntry _first; 081 082 /** 083 * End of linked-list of cache elements. Last entry is element 084 * which has been used most recently. 085 */ 086 CacheEntry _last; 087 088 089 /** 090 * Cache eviction listeners 091 */ 092 Vector listeners = new Vector(); 093 094 095 /** 096 * Construct an MRU with a given maximum number of objects. 097 */ 098 public MRU(int max) { 099 if (max <= 0) { 100 throw new IllegalArgumentException( I18n.err( I18n.ERR_528 )); 101 } 102 _max = max; 103 } 104 105 106 /** 107 * Place an object in the cache. 108 */ 109 public void put(Object key, Object value) throws CacheEvictionException { 110 CacheEntry entry = (CacheEntry)_hash.get(key); 111 if (entry != null) { 112 entry.setValue(value); 113 touchEntry(entry); 114 } else { 115 116 if (_hash.size() == _max) { 117 // purge and recycle entry 118 entry = purgeEntry(); 119 entry.setKey(key); 120 entry.setValue(value); 121 } else { 122 entry = new CacheEntry(key, value); 123 } 124 addEntry(entry); 125 _hash.put(entry.getKey(), entry); 126 } 127 } 128 129 130 /** 131 * Obtain an object in the cache 132 */ 133 public Object get(Object key) { 134 CacheEntry entry = (CacheEntry)_hash.get(key); 135 if (entry != null) { 136 touchEntry(entry); 137 return entry.getValue(); 138 } else { 139 return null; 140 } 141 } 142 143 144 /** 145 * Remove an object from the cache 146 */ 147 public void remove(Object key) { 148 CacheEntry entry = (CacheEntry)_hash.get(key); 149 if (entry != null) { 150 removeEntry(entry); 151 _hash.remove(entry.getKey()); 152 } 153 } 154 155 156 /** 157 * Remove all objects from the cache 158 */ 159 public void removeAll() { 160 _hash = new Hashtable(); 161 _first = null; 162 _last = null; 163 } 164 165 166 /** 167 * Enumerate elements' values in the cache 168 */ 169 public Enumeration elements() { 170 return new MRUEnumeration(_hash.elements()); 171 } 172 173 /** 174 * Add a listener to this cache policy 175 * 176 * @param listener Listener to add to this policy 177 */ 178 public void addListener(CachePolicyListener listener) { 179 if (listener == null) { 180 throw new IllegalArgumentException( I18n.err( I18n.ERR_539 ) ); 181 } 182 if ( ! listeners.contains(listener)) { 183 listeners.addElement(listener); 184 } 185 } 186 187 /** 188 * Remove a listener from this cache policy 189 * 190 * @param listener Listener to remove from this policy 191 */ 192 public void removeListener(CachePolicyListener listener) { 193 listeners.removeElement(listener); 194 } 195 196 /** 197 * Add a CacheEntry. Entry goes at the end of the list. 198 */ 199 protected void addEntry(CacheEntry entry) { 200 if (_first == null) { 201 _first = entry; 202 _last = entry; 203 } else { 204 _last.setNext(entry); 205 entry.setPrevious(_last); 206 _last = entry; 207 } 208 } 209 210 211 /** 212 * Remove a CacheEntry from linked list 213 */ 214 protected void removeEntry(CacheEntry entry) { 215 if (entry == _first) { 216 _first = entry.getNext(); 217 } 218 if (_last == entry) { 219 _last = entry.getPrevious(); 220 } 221 CacheEntry previous = entry.getPrevious(); 222 CacheEntry next = entry.getNext(); 223 if (previous != null) { 224 previous.setNext(next); 225 } 226 if (next != null) { 227 next.setPrevious(previous); 228 } 229 entry.setPrevious(null); 230 entry.setNext(null); 231 } 232 233 /** 234 * Place entry at the end of linked list -- Most Recently Used 235 */ 236 protected void touchEntry(CacheEntry entry) { 237 if (_last == entry) { 238 return; 239 } 240 removeEntry(entry); 241 addEntry(entry); 242 } 243 244 /** 245 * Purge least recently used object from the cache 246 * 247 * @return recyclable CacheEntry 248 */ 249 protected CacheEntry purgeEntry() throws CacheEvictionException { 250 CacheEntry entry = _first; 251 252 // Notify policy listeners first. if any of them throw an 253 // eviction exception, then the internal data structure 254 // remains untouched. 255 CachePolicyListener listener; 256 for (int i=0; i<listeners.size(); i++) { 257 listener = (CachePolicyListener)listeners.elementAt(i); 258 listener.cacheObjectEvicted(entry.getValue()); 259 } 260 261 removeEntry(entry); 262 _hash.remove(entry.getKey()); 263 264 entry.setValue(null); 265 return entry; 266 } 267 268 } 269 270 /** 271 * State information for cache entries. 272 */ 273 class CacheEntry { 274 private Object _key; 275 private Object _value; 276 277 private CacheEntry _previous; 278 private CacheEntry _next; 279 280 CacheEntry(Object key, Object value) { 281 _key = key; 282 _value = value; 283 } 284 285 Object getKey() { 286 return _key; 287 } 288 289 void setKey(Object obj) { 290 _key = obj; 291 } 292 293 Object getValue() { 294 return _value; 295 } 296 297 void setValue(Object obj) { 298 _value = obj; 299 } 300 301 CacheEntry getPrevious() { 302 return _previous; 303 } 304 305 void setPrevious(CacheEntry entry) { 306 _previous = entry; 307 } 308 309 CacheEntry getNext() { 310 return _next; 311 } 312 313 void setNext(CacheEntry entry) { 314 _next = entry; 315 } 316 } 317 318 /** 319 * Enumeration wrapper to return actual user objects instead of 320 * CacheEntries. 321 */ 322 class MRUEnumeration implements Enumeration { 323 Enumeration _enum; 324 325 MRUEnumeration(Enumeration enume) { 326 _enum = enume; 327 } 328 329 public boolean hasMoreElements() { 330 return _enum.hasMoreElements(); 331 } 332 333 public Object nextElement() { 334 CacheEntry entry = (CacheEntry)_enum.nextElement(); 335 return entry.getValue(); 336 } 337 }