001package org.apache.commons.jcs3.utils.struct; 002 003/* 004 * Licensed to the Apache Software Foundation (ASF) under one 005 * or more contributor license agreements. See the NOTICE file 006 * distributed with this work for additional information 007 * regarding copyright ownership. The ASF licenses this file 008 * to you under the Apache License, Version 2.0 (the 009 * "License"); you may not use this file except in compliance 010 * with the License. You may obtain a copy of the License at 011 * 012 * http://www.apache.org/licenses/LICENSE-2.0 013 * 014 * Unless required by applicable law or agreed to in writing, 015 * software distributed under the License is distributed on an 016 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 017 * KIND, either express or implied. See the License for the 018 * specific language governing permissions and limitations 019 * under the License. 020 */ 021 022import java.util.AbstractMap; 023import java.util.ArrayList; 024import java.util.Collection; 025import java.util.Map; 026import java.util.Set; 027import java.util.concurrent.ConcurrentHashMap; 028import java.util.concurrent.locks.Lock; 029import java.util.concurrent.locks.ReentrantLock; 030import java.util.stream.Collectors; 031 032import org.apache.commons.jcs3.engine.control.group.GroupAttrName; 033import org.apache.commons.jcs3.engine.stats.StatElement; 034import org.apache.commons.jcs3.engine.stats.Stats; 035import org.apache.commons.jcs3.engine.stats.behavior.IStatElement; 036import org.apache.commons.jcs3.engine.stats.behavior.IStats; 037import org.apache.commons.jcs3.log.Log; 038import org.apache.commons.jcs3.log.LogManager; 039 040/** 041 * This is a simple LRUMap. It implements most of the map methods. It is not recommended that you 042 * use any but put, get, remove, and clear. 043 * <p> 044 * Children can implement the processRemovedLRU method if they want to handle the removal of the 045 * least recently used item. 046 * </p> 047 * <p> 048 * This class was abstracted out of the LRU Memory cache. Put, remove, and get should be thread 049 * safe. It uses a hashtable and our own double linked list. 050 * </p> 051 * <p> 052 * Locking is done on the instance. 053 * </p> 054 */ 055public abstract class AbstractLRUMap<K, V> 056 implements Map<K, V> 057{ 058 /** The logger */ 059 private static final Log log = LogManager.getLog( AbstractLRUMap.class ); 060 061 /** double linked list for lru */ 062 private final DoubleLinkedList<LRUElementDescriptor<K, V>> list; 063 064 /** Map where items are stored by key. */ 065 private final Map<K, LRUElementDescriptor<K, V>> map; 066 067 /** lock to keep map and list synchronous */ 068 private final Lock lock = new ReentrantLock(); 069 070 /** stats */ 071 private long hitCnt; 072 073 /** stats */ 074 private long missCnt; 075 076 /** stats */ 077 private long putCnt; 078 079 /** 080 * This creates an unbounded version. Setting the max objects will result in spooling on 081 * subsequent puts. 082 */ 083 public AbstractLRUMap() 084 { 085 list = new DoubleLinkedList<>(); 086 087 // normal hashtable is faster for 088 // sequential keys. 089 map = new ConcurrentHashMap<>(); 090 } 091 092 093 /** 094 * This simply returns the number of elements in the map. 095 * <p> 096 * @see java.util.Map#size() 097 */ 098 @Override 099 public int size() 100 { 101 return map.size(); 102 } 103 104 /** 105 * This removes all the items. It clears the map and the double linked list. 106 * <p> 107 * @see java.util.Map#clear() 108 */ 109 @Override 110 public void clear() 111 { 112 lock.lock(); 113 try 114 { 115 map.clear(); 116 list.removeAll(); 117 } 118 finally 119 { 120 lock.unlock(); 121 } 122 } 123 124 /** 125 * Returns true if the map is empty. 126 * <p> 127 * @see java.util.Map#isEmpty() 128 */ 129 @Override 130 public boolean isEmpty() 131 { 132 return map.isEmpty(); 133 } 134 135 /** 136 * Returns true if the map contains an element for the supplied key. 137 * <p> 138 * @see java.util.Map#containsKey(Object) 139 */ 140 @Override 141 public boolean containsKey( final Object key ) 142 { 143 return map.containsKey( key ); 144 } 145 146 /** 147 * This is an expensive operation that determines if the object supplied is mapped to any key. 148 * <p> 149 * @see java.util.Map#containsValue(Object) 150 */ 151 @Override 152 public boolean containsValue( final Object value ) 153 { 154 return map.containsValue( value ); 155 } 156 157 /** 158 * @return map.values(); 159 */ 160 @Override 161 public Collection<V> values() 162 { 163 return map.values().stream() 164 .map(LRUElementDescriptor::getPayload) 165 .collect(Collectors.toList()); 166 } 167 168 /** 169 * @param source 170 */ 171 @Override 172 public void putAll( final Map<? extends K, ? extends V> source ) 173 { 174 if ( source != null ) 175 { 176 source.forEach(this::put); 177 } 178 } 179 180 /** 181 * @param key 182 * @return Object 183 */ 184 @Override 185 public V get( final Object key ) 186 { 187 final V retVal; 188 189 log.debug( "getting item for key {0}", key ); 190 191 final LRUElementDescriptor<K, V> me = map.get( key ); 192 193 if ( me == null ) 194 { 195 missCnt++; 196 retVal = null; 197 } 198 else 199 { 200 hitCnt++; 201 retVal = me.getPayload(); 202 list.makeFirst( me ); 203 } 204 205 if ( me == null ) 206 { 207 log.debug( "LRUMap miss for {0}", key ); 208 } 209 else 210 { 211 log.debug( "LRUMap hit for {0}", key ); 212 } 213 214 // verifyCache(); 215 return retVal; 216 } 217 218 /** 219 * This gets an element out of the map without adjusting it's position in the LRU. In other 220 * words, this does not count as being used. If the element is the last item in the list, it 221 * will still be the last time in the list. 222 * <p> 223 * @param key 224 * @return Object 225 */ 226 public V getQuiet( final Object key ) 227 { 228 V ce = null; 229 final LRUElementDescriptor<K, V> me = map.get( key ); 230 231 if ( me != null ) 232 { 233 ce = me.getPayload(); 234 } 235 236 if ( me == null ) 237 { 238 log.debug( "LRUMap quiet miss for {0}", key ); 239 } 240 else 241 { 242 log.debug( "LRUMap quiet hit for {0}", key ); 243 } 244 245 return ce; 246 } 247 248 /** 249 * @param key 250 * @return Object removed 251 */ 252 @Override 253 public V remove( final Object key ) 254 { 255 log.debug( "removing item for key: {0}", key ); 256 257 // remove single item. 258 lock.lock(); 259 try 260 { 261 final LRUElementDescriptor<K, V> me = map.remove(key); 262 263 if (me != null) 264 { 265 list.remove(me); 266 return me.getPayload(); 267 } 268 } 269 finally 270 { 271 lock.unlock(); 272 } 273 274 return null; 275 } 276 277 /** 278 * @param key 279 * @param value 280 * @return Object 281 */ 282 @Override 283 public V put(final K key, final V value) 284 { 285 putCnt++; 286 287 LRUElementDescriptor<K, V> old = null; 288 final LRUElementDescriptor<K, V> me = new LRUElementDescriptor<>(key, value); 289 290 lock.lock(); 291 try 292 { 293 list.addFirst( me ); 294 old = map.put(key, me); 295 296 // If the node was the same as an existing node, remove it. 297 if ( old != null && key.equals(old.getKey())) 298 { 299 list.remove( old ); 300 } 301 } 302 finally 303 { 304 lock.unlock(); 305 } 306 307 // If the element limit is reached, we need to spool 308 if (shouldRemove()) 309 { 310 log.debug( "In memory limit reached, removing least recently used." ); 311 312 // The spool will put them in a disk event queue, so there is no 313 // need to pre-queue the queuing. This would be a bit wasteful 314 // and wouldn't save much time in this synchronous call. 315 while (shouldRemove()) 316 { 317 lock.lock(); 318 try 319 { 320 final LRUElementDescriptor<K, V> last = list.getLast(); 321 if (last == null) { 322 verifyCache(); 323 throw new Error("update: last is null!"); 324 } 325 processRemovedLRU(last.getKey(), last.getPayload()); 326 if (map.remove(last.getKey()) == null) 327 { 328 log.warn("update: remove failed for key: {0}", 329 last::getKey); 330 verifyCache(); 331 } 332 list.removeLast(); 333 } 334 finally 335 { 336 lock.unlock(); 337 } 338 } 339 340 log.debug( "update: After spool map size: {0}", map::size); 341 if ( map.size() != list.size() ) 342 { 343 log.error("update: After spool, size mismatch: map.size() = {0}, " 344 + "linked list size = {1}", 345 map::size, list::size); 346 } 347 } 348 349 if ( old != null ) 350 { 351 return old.getPayload(); 352 } 353 return null; 354 } 355 356 protected abstract boolean shouldRemove(); 357 358 /** 359 * Dump the cache entries from first to list for debugging. 360 */ 361 @SuppressWarnings("unchecked") // No generics for public fields 362 public void dumpCacheEntries() 363 { 364 if (log.isTraceEnabled()) 365 { 366 log.trace("dumpingCacheEntries"); 367 for (LRUElementDescriptor<K, V> me = list.getFirst(); me != null; me = (LRUElementDescriptor<K, V>) me.next) 368 { 369 log.trace("dumpCacheEntries> key={0}, val={1}", me.getKey(), me.getPayload()); 370 } 371 } 372 } 373 374 /** 375 * Dump the cache map for debugging. 376 */ 377 public void dumpMap() 378 { 379 if (log.isTraceEnabled()) 380 { 381 log.trace("dumpingMap"); 382 map.forEach((key, value) -> log.trace("dumpMap> key={0}, val={1}", key, value.getPayload())); 383 } 384 } 385 386 /** 387 * Checks to see if all the items that should be in the cache are. Checks consistency between 388 * List and map. 389 */ 390 @SuppressWarnings("unchecked") // No generics for public fields 391 protected void verifyCache() 392 { 393 if ( !log.isTraceEnabled() ) 394 { 395 return; 396 } 397 398 log.trace( "verifycache: mapContains {0} elements, linked list " 399 + "contains {1} elements", map.size(), list.size() ); 400 log.trace( "verifycache: checking linked list by key" ); 401 for (LRUElementDescriptor<K, V> li = list.getFirst(); li != null; li = (LRUElementDescriptor<K, V>) li.next ) 402 { 403 final K key = li.getKey(); 404 if ( !map.containsKey( key ) ) 405 { 406 log.error( "verifycache: map does not contain key : {0}", li.getKey() ); 407 log.error( "li.hashCode={0}", li.getKey().hashCode() ); 408 log.error( "key class={0}", key.getClass() ); 409 log.error( "key hashCode={0}", key.hashCode() ); 410 log.error( "key toString={0}", key.toString() ); 411 if ( key instanceof GroupAttrName ) 412 { 413 final GroupAttrName<?> name = (GroupAttrName<?>) key; 414 log.error( "GroupID hashCode={0}", name.groupId.hashCode() ); 415 log.error( "GroupID.class={0}", name.groupId.getClass() ); 416 log.error( "AttrName hashCode={0}", name.attrName.hashCode() ); 417 log.error( "AttrName.class={0}", name.attrName.getClass() ); 418 } 419 dumpMap(); 420 } 421 else if ( map.get( li.getKey() ) == null ) 422 { 423 log.error( "verifycache: linked list retrieval returned null for key: {0}", 424 li.getKey() ); 425 } 426 } 427 428 log.trace( "verifycache: checking linked list by value " ); 429 for (LRUElementDescriptor<K, V> li3 = list.getFirst(); li3 != null; li3 = (LRUElementDescriptor<K, V>) li3.next ) 430 { 431 if (!map.containsValue(li3)) 432 { 433 log.error( "verifycache: map does not contain value : {0}", li3 ); 434 dumpMap(); 435 } 436 } 437 438 log.trace( "verifycache: checking via keysets!" ); 439 map.keySet().stream() 440 .filter(key -> { 441 for (LRUElementDescriptor<K, V> li2 = list.getFirst(); li2 != null; li2 = (LRUElementDescriptor<K, V>) li2.next ) 442 { 443 if ( key.equals( li2.getKey() ) ) 444 { 445 return true; 446 } 447 } 448 449 log.error( "verifycache: key not found in list : {0}", key ); 450 dumpCacheEntries(); 451 if ( map.containsKey( key ) ) 452 { 453 log.error( "verifycache: map contains key" ); 454 } 455 else 456 { 457 log.error( "verifycache: map does NOT contain key, what the HECK!" ); 458 } 459 460 return false; 461 }) 462 .findFirst(); 463 } 464 465 /** 466 * This is called when an item is removed from the LRU. We just log some information. 467 * <p> 468 * Children can implement this method for special behavior. 469 * @param key 470 * @param value 471 */ 472 protected void processRemovedLRU(final K key, final V value ) 473 { 474 log.debug( "Removing key: [{0}] from LRUMap store, value = [{1}]", key, value ); 475 log.debug( "LRUMap store size: \"{0}\".", this.size() ); 476 } 477 478 /** 479 * @return IStats 480 */ 481 public IStats getStatistics() 482 { 483 final IStats stats = new Stats(); 484 stats.setTypeName( "LRUMap" ); 485 486 final ArrayList<IStatElement<?>> elems = new ArrayList<>(); 487 488 elems.add(new StatElement<>( "List Size", Integer.valueOf(list.size()) ) ); 489 elems.add(new StatElement<>( "Map Size", Integer.valueOf(map.size()) ) ); 490 elems.add(new StatElement<>( "Put Count", Long.valueOf(putCnt) ) ); 491 elems.add(new StatElement<>( "Hit Count", Long.valueOf(hitCnt) ) ); 492 elems.add(new StatElement<>( "Miss Count", Long.valueOf(missCnt) ) ); 493 494 stats.setStatElements( elems ); 495 496 return stats; 497 } 498 499 /** 500 * This returns a set of entries. Our LRUMapEntry is used since the value stored in the 501 * underlying map is a node in the double linked list. We wouldn't want to return this to the 502 * client, so we construct a new entry with the payload of the node. 503 * <p> 504 * TODO we should return out own set wrapper, so we can avoid the extra object creation if it 505 * isn't necessary. 506 * <p> 507 * @see java.util.Map#entrySet() 508 */ 509 @Override 510 public Set<Map.Entry<K, V>> entrySet() 511 { 512 lock.lock(); 513 try 514 { 515 return map.entrySet().stream() 516 .map(entry -> new AbstractMap.SimpleEntry<>( 517 entry.getKey(), entry.getValue().getPayload())) 518 .collect(Collectors.toSet()); 519 } 520 finally 521 { 522 lock.unlock(); 523 } 524 } 525 526 /** 527 * @return map.keySet(); 528 */ 529 @Override 530 public Set<K> keySet() 531 { 532 return map.values().stream() 533 .map(LRUElementDescriptor::getKey) 534 .collect(Collectors.toSet()); 535 } 536}