001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * https://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 * 019 */ 020package org.apache.directory.api.util; 021 022 023import java.io.Externalizable; 024 025 026/** 027 * <p> 028 * An implementation of a Map which has a maximum size and uses a Least Recently 029 * Used algorithm to remove items from the Map when the maximum size is reached 030 * and new items are added. 031 * </p> 032 * <p> 033 * A synchronized version can be obtained with: 034 * <code>Collections.synchronizedMap( theMapToSynchronize )</code> If it will 035 * be accessed by multiple threads, you _must_ synchronize access to this Map. 036 * Even concurrent get(Object) operations produce indeterminate behaviour. 037 * </p> 038 * <p> 039 * Unlike the Collections 1.0 version, this version of LRUMap does use a true 040 * LRU algorithm. The keys for all gets and puts are moved to the front of the 041 * list. LRUMap is now a subclass of SequencedHashMap, and the "LRU" key is now 042 * equivalent to LRUMap.getFirst(). 043 * </p> 044 * 045 * @since Commons Collections 1.0 046 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 047 */ 048public final class SynchronizedLRUMap extends SequencedHashMap implements Externalizable 049{ 050 // add a serial version uid, so that if we change things in the future 051 // without changing the format, we can still deserialize properly. 052 private static final long serialVersionUID = 2197433140769957051L; 053 054 /** Maximum size */ 055 private int maximumSize = 0; 056 057 /** Default maximum size */ 058 protected static final int DEFAULT_MAX_SIZE = 100; 059 060 /** 061 * Default constructor, primarily for the purpose of de-externalization. 062 * This constructors sets a default LRU limit of 100 keys, but this value 063 * may be overridden internally as a result of de-externalization. 064 */ 065 public SynchronizedLRUMap() 066 { 067 this( DEFAULT_MAX_SIZE ); 068 } 069 070 071 /** 072 * Create a new LRUMap with a maximum capacity of <i>i</i>. Once <i>i</i> 073 * capacity is achieved, subsequent gets and puts will push keys out of the 074 * map. See . 075 * 076 * @param maxSize Maximum capacity of the LRUMap 077 */ 078 public SynchronizedLRUMap( int maxSize ) 079 { 080 super( maxSize ); 081 maximumSize = maxSize; 082 } 083 084 085 /** 086 * <p> 087 * Get the value for a key from the Map. The key will be promoted to the 088 * Most Recently Used position. Note that get(Object) operations will modify 089 * the underlying Collection. Calling get(Object) inside of an iteration 090 * over keys, values, etc. is currently unsupported. 091 * </p> 092 * 093 * @param key Key to retrieve 094 * @return Returns the value. Returns null if the key has a null value <i>or</i> 095 * if the key has no value. 096 */ 097 @Override 098 public synchronized Object get( Object key ) 099 { 100 if ( !containsKey( key ) ) 101 { 102 return null; 103 } 104 105 Object value = remove( key ); 106 super.put( key, value ); 107 108 return value; 109 } 110 111 112 /** 113 * <p> 114 * Removes the key and its Object from the Map. 115 * </p> 116 * <p> 117 * (Note: this may result in the "Least Recently Used" object being removed 118 * from the Map. In that case, the removeLRU() method is called. See javadoc 119 * for removeLRU() for more details.) 120 * </p> 121 * 122 * @param key Key of the Object to add. 123 * @param value Object to add 124 * @return Former value of the key 125 */ 126 @Override 127 public synchronized Object put( Object key, Object value ) 128 { 129 // don't retire LRU if you are just 130 // updating an existing key 131 if ( ( maximumSize <= size() ) && ( !containsKey( key ) ) ) 132 { 133 // lets retire the least recently used item in the cache 134 removeLRU(); 135 } 136 137 return super.put( key, value ); 138 } 139 140 141 /** 142 * This method is used internally by the class for finding and removing the 143 * LRU Object. 144 */ 145 private void removeLRU() 146 { 147 Object key = getFirstKey(); 148 // be sure to call super.get(key), or you're likely to 149 // get infinite promotion recursion 150 super.get( key ); 151 152 remove( key ); 153 } 154 155 156 /** 157 * Getter for property maximumSize. 158 * 159 * @return Value of property maximumSize. 160 */ 161 public synchronized int getMaximumSize() 162 { 163 return maximumSize; 164 } 165 166 167 /** 168 * Setter for property maximumSize. 169 * 170 * @param maximumSize New value of property maximumSize. 171 */ 172 public synchronized void setMaximumSize( int maximumSize ) 173 { 174 this.maximumSize = maximumSize; 175 176 while ( size() > maximumSize ) 177 { 178 removeLRU(); 179 } 180 } 181}