Return-Path: X-Original-To: apmail-commons-commits-archive@minotaur.apache.org Delivered-To: apmail-commons-commits-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 57AB410BCE for ; Mon, 7 Apr 2014 14:40:48 +0000 (UTC) Received: (qmail 67575 invoked by uid 500); 7 Apr 2014 14:40:44 -0000 Delivered-To: apmail-commons-commits-archive@commons.apache.org Received: (qmail 67261 invoked by uid 500); 7 Apr 2014 14:40:44 -0000 Mailing-List: contact commits-help@commons.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@commons.apache.org Delivered-To: mailing list commits@commons.apache.org Received: (qmail 67247 invoked by uid 99); 7 Apr 2014 14:40:43 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 07 Apr 2014 14:40:43 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 07 Apr 2014 14:40:37 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id 2600823888E4; Mon, 7 Apr 2014 14:40:13 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1585494 - in /commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine: control/CompositeCache.java memory/AbstractDoubleLinkedListMemoryCache.java memory/AbstractMemoryCache.java memory/behavior/IMemoryCache.java Date: Mon, 07 Apr 2014 14:40:12 -0000 To: commits@commons.apache.org From: tv@apache.org X-Mailer: svnmailer-1.0.9 Message-Id: <20140407144013.2600823888E4@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org Author: tv Date: Mon Apr 7 14:40:12 2014 New Revision: 1585494 URL: http://svn.apache.org/r1585494 Log: Remove Iterator. It is prone to ConcurrentModificationExceptions Modified: commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/control/CompositeCache.java commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/memory/AbstractDoubleLinkedListMemoryCache.java (contents, props changed) commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/memory/AbstractMemoryCache.java commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/memory/behavior/IMemoryCache.java Modified: commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/control/CompositeCache.java URL: http://svn.apache.org/viewvc/commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/control/CompositeCache.java?rev=1585494&r1=1585493&r2=1585494&view=diff ============================================================================== --- commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/control/CompositeCache.java (original) +++ commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/control/CompositeCache.java Mon Apr 7 14:40:12 2014 @@ -49,7 +49,6 @@ import org.apache.commons.jcs.engine.mat import org.apache.commons.jcs.engine.match.behavior.IKeyMatcher; import org.apache.commons.jcs.engine.memory.behavior.IMemoryCache; import org.apache.commons.jcs.engine.memory.lru.LRUMemoryCache; -import org.apache.commons.jcs.engine.memory.util.MemoryElementDescriptor; import org.apache.commons.jcs.engine.stats.CacheStats; import org.apache.commons.jcs.engine.stats.StatElement; import org.apache.commons.jcs.engine.stats.Stats; @@ -1446,17 +1445,14 @@ public class CompositeCache>> itr = - memCache.getIterator(); - - while (itr.hasNext()) + for (K key : memCache.getKeySet()) { - Map.Entry> entry = itr.next(); - - ICacheElement ce = entry.getValue().ce; + ICacheElement ce = memCache.get(key); - aux.update( ce ); + if (ce != null) + { + aux.update( ce ); + } } } } Modified: commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/memory/AbstractDoubleLinkedListMemoryCache.java URL: http://svn.apache.org/viewvc/commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/memory/AbstractDoubleLinkedListMemoryCache.java?rev=1585494&r1=1585493&r2=1585494&view=diff ============================================================================== --- commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/memory/AbstractDoubleLinkedListMemoryCache.java (original) +++ commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/memory/AbstractDoubleLinkedListMemoryCache.java Mon Apr 7 14:40:12 2014 @@ -1,766 +1,755 @@ -package org.apache.commons.jcs.engine.memory; - -/* - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - -import java.io.IOException; -import java.io.Serializable; -import java.util.ArrayList; -import java.util.Hashtable; -import java.util.Iterator; -import java.util.LinkedHashSet; -import java.util.Map; -import java.util.Map.Entry; -import java.util.Set; - -import org.apache.commons.jcs.engine.CacheConstants; -import org.apache.commons.jcs.engine.behavior.ICacheElement; -import org.apache.commons.jcs.engine.control.CompositeCache; -import org.apache.commons.jcs.engine.control.group.GroupAttrName; -import org.apache.commons.jcs.engine.memory.util.MemoryElementDescriptor; -import org.apache.commons.jcs.engine.stats.StatElement; -import org.apache.commons.jcs.engine.stats.Stats; -import org.apache.commons.jcs.engine.stats.behavior.IStatElement; -import org.apache.commons.jcs.engine.stats.behavior.IStats; -import org.apache.commons.jcs.utils.struct.DoubleLinkedList; -import org.apache.commons.logging.Log; -import org.apache.commons.logging.LogFactory; - -/** - * This class contains methods that are common to memory caches using the double linked list, such - * as the LRU, MRU, FIFO, and LIFO caches. - *

- * Children can control the expiration algorithm by controlling the update and get. The last item in - * the list will be the one removed when the list fills. For instance LRU should more items to the - * front as they are used. FIFO should simply add new items to the front of the list. - */ -public abstract class AbstractDoubleLinkedListMemoryCache - extends AbstractMemoryCache -{ - /** Don't change. */ - private static final long serialVersionUID = 1422569420563967389L; - - /** The logger. */ - private static final Log log = LogFactory.getLog( AbstractDoubleLinkedListMemoryCache.class ); - - /** thread-safe double linked list for lru */ - protected DoubleLinkedList> list; // TODO privatise - - /** number of hits */ - private int hitCnt = 0; - - /** number of misses */ - private int missCnt = 0; - - /** number of puts */ - private int putCnt = 0; - - /** - * For post reflection creation initialization. - *

- * @param hub - */ - @Override - public synchronized void initialize( CompositeCache hub ) - { - super.initialize( hub ); - list = new DoubleLinkedList>(); - log.info( "initialized MemoryCache for " + cacheName ); - } - - /** - * This is called by super initialize. - *

- * @return new Hashtable() - */ - @Override - public Map> createMap() - { - return new Hashtable>(); - } - - /** - * Calls the abstract method updateList. - *

- * If the max size is reached, an element will be put to disk. - *

- * @param ce The cache element, or entry wrapper - * @throws IOException - */ - @Override - public final void update( ICacheElement ce ) - throws IOException - { - putCnt++; - - synchronized ( this ) - { - // ABSTRACT - MemoryElementDescriptor newNode = adjustListForUpdate( ce ); - - // this must be synchronized - MemoryElementDescriptor oldNode = map.put( newNode.ce.getKey(), newNode ); - - // If the node was the same as an existing node, remove it. - if ( oldNode != null && newNode.ce.getKey().equals( oldNode.ce.getKey() ) ) - { - list.remove( oldNode ); - } - } - - // If we are over the max spool some - spoolIfNeeded(); - } - - /** - * Children implement this to control the cache expiration algorithm - *

- * @param ce - * @return MemoryElementDescriptor the new node - * @throws IOException - */ - protected abstract MemoryElementDescriptor adjustListForUpdate( ICacheElement ce ) - throws IOException; - - /** - * If the max size has been reached, spool. - *

- * @throws Error - */ - private void spoolIfNeeded() - throws Error - { - int size = map.size(); - // If the element limit is reached, we need to spool - - if ( size <= this.cacheAttributes.getMaxObjects() ) - { - return; - } - - if ( log.isDebugEnabled() ) - { - log.debug( "In memory limit reached, spooling" ); - } - - // Write the last 'chunkSize' items to disk. - int chunkSizeCorrected = Math.min( size, chunkSize ); - - if ( log.isDebugEnabled() ) - { - log.debug( "About to spool to disk cache, map size: " + size + ", max objects: " - + this.cacheAttributes.getMaxObjects() + ", items to spool: " + chunkSizeCorrected ); - } - - // The spool will put them in a disk event queue, so there is no - // need to pre-queue the queuing. This would be a bit wasteful - // and wouldn't save much time in this synchronous call. - for ( int i = 0; i < chunkSizeCorrected; i++ ) - { - spoolLastElement(); - } - - if ( log.isDebugEnabled() ) - { - log.debug( "update: After spool map size: " + map.size() + " linked list size = " + dumpCacheSize() ); - } - } - - /** - * Get an item from the cache If the item is found, it is removed from the list and added first. - *

- * @param key Identifies item to find - * @return ICacheElement if found, else null - * @throws IOException - */ - @Override - public final synchronized ICacheElement get( K key ) - throws IOException - { - ICacheElement ce = null; - - if ( log.isDebugEnabled() ) - { - log.debug( "getting item from cache " + cacheName + " for key " + key ); - } - - MemoryElementDescriptor me = map.get( key ); - - if ( me != null ) - { - ce = me.ce; - hitCnt++; - if ( log.isDebugEnabled() ) - { - log.debug( cacheName + ": LRUMemoryCache hit for " + ce.getKey() ); - } - - // ABSTRACT - adjustListForGet( me ); - } - else - { - missCnt++; - if ( log.isDebugEnabled() ) - { - log.debug( cacheName + ": LRUMemoryCache miss for " + key ); - } - } - - verifyCache(); - return ce; - } - - /** - * Adjust the list as needed for a get. This allows children to control the algorithm - *

- * @param me - */ - protected abstract void adjustListForGet( MemoryElementDescriptor me ); - - /** - * This instructs the memory cache to remove the numberToFree according to its eviction - * policy. For example, the LRUMemoryCache will remove the numberToFree least recently - * used items. These will be spooled to disk if a disk auxiliary is available. - *

- * @param numberToFree - * @return the number that were removed. if you ask to free 5, but there are only 3, you will - * get 3. - * @throws IOException - */ - @Override - public int freeElements( int numberToFree ) - throws IOException - { - int freed = 0; - for ( ; freed < numberToFree; freed++ ) - { - ICacheElement element = spoolLastElement(); - if ( element == null ) - { - break; - } - } - return freed; - } - - /** - * This spools the last element in the LRU, if one exists. - *

- * @return ICacheElement if there was a last element, else null. - * @throws Error - */ - protected ICacheElement spoolLastElement() - throws Error - { - ICacheElement toSpool = null; - synchronized ( this ) - { - if ( list.getLast() != null ) - { - toSpool = list.getLast().ce; - if ( toSpool != null ) - { - cache.spoolToDisk( list.getLast().ce ); - if ( !map.containsKey( list.getLast().ce.getKey() ) ) - { - log.error( "update: map does not contain key: " - + list.getLast().ce.getKey() ); - verifyCache(); - } - if ( map.remove( list.getLast().ce.getKey() ) == null ) - { - log.warn( "update: remove failed for key: " - + list.getLast().ce.getKey() ); - verifyCache(); - } - } - else - { - throw new Error( "update: last.ce is null!" ); - } - list.removeLast(); - } - else - { - verifyCache(); - throw new Error( "update: last is null!" ); - } - - // If this is out of the sync block it can detect a mismatch - // where there is none. - if ( map.size() != dumpCacheSize() ) - { - log.warn( "update: After spool, size mismatch: map.size() = " + map.size() + ", linked list size = " - + dumpCacheSize() ); - } - } - return toSpool; - } - - /** - * Removes an item from the cache. This method handles hierarchical removal. If the key is a - * String and ends with the CacheConstants.NAME_COMPONENT_DELIMITER, then all items with keys - * starting with the argument String will be removed. - *

- * @param key - * @return true if the removal was successful - * @throws IOException - */ - @Override - public synchronized boolean remove( K key ) - throws IOException - { - if ( log.isDebugEnabled() ) - { - log.debug( "removing item for key: " + key ); - } - - boolean removed = false; - - // handle partial removal - if ( key instanceof String && ( (String) key ).endsWith( CacheConstants.NAME_COMPONENT_DELIMITER ) ) - { - // remove all keys of the same name hierarchy. - synchronized ( map ) - { - for (Iterator>> itr = map.entrySet().iterator(); itr.hasNext(); ) - { - Map.Entry> entry = itr.next(); - K k = entry.getKey(); - - if ( k instanceof String && ( (String) k ).startsWith( key.toString() ) ) - { - list.remove( entry.getValue() ); - itr.remove(); - removed = true; - } - } - } - } - else if ( key instanceof GroupAttrName ) - { - // remove all keys of the same name hierarchy. - synchronized ( map ) - { - for (Iterator>> itr = map.entrySet().iterator(); itr.hasNext(); ) - { - Map.Entry> entry = itr.next(); - K k = entry.getKey(); - - if ( k instanceof GroupAttrName && - ((GroupAttrName)k).groupId.equals(((GroupAttrName)key).groupId)) - { - list.remove( entry.getValue() ); - itr.remove(); - removed = true; - } - } - } - } - else - { - // remove single item. - MemoryElementDescriptor me = map.remove( key ); - - if ( me != null ) - { - list.remove( me ); - removed = true; - } - } - - return removed; - } - - /** - * Remove all of the elements from both the Map and the linked list implementation. Overrides - * base class. - *

- * @throws IOException - */ - @Override - public synchronized void removeAll() - throws IOException - { - map.clear(); - list.removeAll(); - } - - // --------------------------- internal methods (linked list implementation) - /** - * Adds a new node to the start of the link list. - *

- * @param ce The feature to be added to the First - * @return MemoryElementDescriptor - */ - protected synchronized MemoryElementDescriptor addFirst( ICacheElement ce ) - { - MemoryElementDescriptor me = new MemoryElementDescriptor( ce ); - list.addFirst( me ); - verifyCache( ce.getKey() ); - return me; - } - - /** - * Adds a new node to the end of the link list. - *

- * @param ce The feature to be added to the First - * @return MemoryElementDescriptor - */ - protected synchronized MemoryElementDescriptor addLast( ICacheElement ce ) - { - MemoryElementDescriptor me = new MemoryElementDescriptor( ce ); - list.addLast( me ); - verifyCache( ce.getKey() ); - return me; - } - - // ---------------------------------------------------------- debug methods - - /** - * Dump the cache entries from first to list for debugging. - */ - @SuppressWarnings("unchecked") // No generics for public fields - public void dumpCacheEntries() - { - log.debug( "dumpingCacheEntries" ); - for ( MemoryElementDescriptor me = list.getFirst(); me != null; me = (MemoryElementDescriptor) me.next ) - { - log.debug( "dumpCacheEntries> key=" + me.ce.getKey() + ", val=" + me.ce.getVal() ); - } - } - - /** - * Returns the size of the list. - *

- * @return the number of items in the map. - */ - protected int dumpCacheSize() - { - return list.size(); - } - - /** - * Checks to see if all the items that should be in the cache are. Checks consistency between - * List and map. - */ - @SuppressWarnings("unchecked") // No generics for public fields - protected void verifyCache() - { - if ( !log.isDebugEnabled() ) - { - return; - } - - boolean found = false; - log.debug( "verifycache[" + cacheName + "]: mapContains " + map.size() + " elements, linked list contains " - + dumpCacheSize() + " elements" ); - log.debug( "verifycache: checking linked list by key " ); - for ( MemoryElementDescriptor li = list.getFirst(); li != null; li = (MemoryElementDescriptor) li.next ) - { - Object key = li.ce.getKey(); - if ( !map.containsKey( key ) ) - { - log.error( "verifycache[" + cacheName + "]: map does not contain key : " + li.ce.getKey() ); - log.error( "li.hashcode=" + li.ce.getKey().hashCode() ); - log.error( "key class=" + key.getClass() ); - log.error( "key hashcode=" + key.hashCode() ); - log.error( "key toString=" + key.toString() ); - if ( key instanceof GroupAttrName ) - { - GroupAttrName name = (GroupAttrName) key; - log.error( "GroupID hashcode=" + name.groupId.hashCode() ); - log.error( "GroupID.class=" + name.groupId.getClass() ); - log.error( "AttrName hashcode=" + name.attrName.hashCode() ); - log.error( "AttrName.class=" + name.attrName.getClass() ); - } - dumpMap(); - } - else if ( map.get( li.ce.getKey() ) == null ) - { - log.error( "verifycache[" + cacheName + "]: linked list retrieval returned null for key: " - + li.ce.getKey() ); - } - } - - log.debug( "verifycache: checking linked list by value " ); - for ( MemoryElementDescriptor li3 = list.getFirst(); li3 != null; li3 = (MemoryElementDescriptor) li3.next ) - { - if ( map.containsValue( li3 ) == false ) - { - log.error( "verifycache[" + cacheName + "]: map does not contain value : " + li3 ); - dumpMap(); - } - } - - log.debug( "verifycache: checking via keysets!" ); - for (Serializable val : map.keySet()) - { - found = false; - - for ( MemoryElementDescriptor li2 = list.getFirst(); li2 != null; li2 = (MemoryElementDescriptor) li2.next ) - { - if ( val.equals( li2.ce.getKey() ) ) - { - found = true; - break; - } - } - if ( !found ) - { - log.error( "verifycache[" + cacheName + "]: key not found in list : " + val ); - dumpCacheEntries(); - if ( map.containsKey( val ) ) - { - log.error( "verifycache: map contains key" ); - } - else - { - log.error( "verifycache: map does NOT contain key, what the HECK!" ); - } - } - } - } - - /** - * Logs an error if an element that should be in the cache is not. - *

- * @param key - */ - @SuppressWarnings("unchecked") // No generics for public fields - private void verifyCache( K key ) - { - if ( !log.isDebugEnabled() ) - { - return; - } - - boolean found = false; - - // go through the linked list looking for the key - for ( MemoryElementDescriptor li = list.getFirst(); li != null; li = (MemoryElementDescriptor) li.next ) - { - if ( li.ce.getKey() == key ) - { - found = true; - log.debug( "verifycache(key) key match: " + key ); - break; - } - } - if ( !found ) - { - log.error( "verifycache(key)[" + cacheName + "], couldn't find key! : " + key ); - } - } - - // --------------------------- iteration methods (iteration helpers) - /** - * iteration aid - */ - public static class IteratorWrapper - implements Iterator>> - { - /** The internal iterator */ - private final Iterator>> i; - - /** - * Wrapped to remove our wrapper object - * @param m - */ - protected IteratorWrapper(Map> m) - { - i = m.entrySet().iterator(); - } - - /** @return i.hasNext() */ - @Override - public boolean hasNext() - { - return i.hasNext(); - } - - /** @return new MapEntryWrapper( (Map.Entry) i.next() ) */ - @Override - public Entry> next() - { - // return new MapEntryWrapper( i.next() ); - return i.next(); - } - - /** i.remove(); */ - @Override - public void remove() - { - i.remove(); - } - - /** - * @param o - * @return i.equals( o )) - */ - @Override - public boolean equals( Object o ) - { - return i.equals( o ); - } - - /** @return i.hashCode() */ - @Override - public int hashCode() - { - return i.hashCode(); - } - } - - /** - * @author Aaron Smuts - */ - public static class MapEntryWrapper - implements Map.Entry> - { - /** The internal entry */ - private final Map.Entry> e; - - /** - * @param e - */ - private MapEntryWrapper( Map.Entry> e ) - { - this.e = e; - } - - /** - * @param o - * @return e.equals( o ) - */ - @Override - public boolean equals( Object o ) - { - return e.equals( o ); - } - - /** @return e.getKey() */ - @Override - public K getKey() - { - return e.getKey(); - } - - /** @return ( (MemoryElementDescriptor) e.getValue() ).ce */ - @Override - public ICacheElement getValue() - { - return e.getValue().ce; - } - - /** @return e.hashCode() */ - @Override - public int hashCode() - { - return e.hashCode(); - } - - /** - * invalid - * @param value - * @return always throws - */ - @Override - public ICacheElement setValue(ICacheElement value) - { - throw new UnsupportedOperationException( "Use normal cache methods" - + " to alter the contents of the cache." ); - } - } - - /** - * Gets the iterator attribute of the LRUMemoryCache object - *

- * @return The iterator value - */ - @Override - public Iterator>> getIterator() - { - return new IteratorWrapper( map ); - } - - /** - * Get an Array of the keys for all elements in the memory cache - * @return An Object[] - */ - @Override - public Set getKeySet() - { - // need a better locking strategy here. - synchronized ( this ) - { - // may need to lock to map here? - return new LinkedHashSet(map.keySet()); - } - } - - /** - * This returns semi-structured information on the memory cache, such as the size, put count, - * hit count, and miss count. - *

- * @see org.apache.commons.jcs.engine.memory.behavior.IMemoryCache#getStatistics() - */ - @Override - public synchronized IStats getStatistics() - { - IStats stats = new Stats(); - stats.setTypeName( /*add algorithm name*/"Memory Cache" ); - - ArrayList elems = new ArrayList(); - - IStatElement se = null; - - se = new StatElement(); - se.setName( "List Size" ); - se.setData( "" + list.size() ); - elems.add( se ); - - se = new StatElement(); - se.setName( "Map Size" ); - se.setData( "" + map.size() ); - elems.add( se ); - - se = new StatElement(); - se.setName( "Put Count" ); - se.setData( "" + putCnt ); - elems.add( se ); - - se = new StatElement(); - se.setName( "Hit Count" ); - se.setData( "" + hitCnt ); - elems.add( se ); - - se = new StatElement(); - se.setName( "Miss Count" ); - se.setData( "" + missCnt ); - elems.add( se ); - - // get an array and put them in the Stats object - IStatElement[] ses = elems.toArray( new StatElement[0] ); - stats.setStatElements( ses ); - - return stats; - } -} +package org.apache.commons.jcs.engine.memory; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.io.IOException; +import java.io.Serializable; +import java.util.ArrayList; +import java.util.Hashtable; +import java.util.Iterator; +import java.util.LinkedHashSet; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Set; + +import org.apache.commons.jcs.engine.CacheConstants; +import org.apache.commons.jcs.engine.behavior.ICacheElement; +import org.apache.commons.jcs.engine.control.CompositeCache; +import org.apache.commons.jcs.engine.control.group.GroupAttrName; +import org.apache.commons.jcs.engine.memory.util.MemoryElementDescriptor; +import org.apache.commons.jcs.engine.stats.StatElement; +import org.apache.commons.jcs.engine.stats.Stats; +import org.apache.commons.jcs.engine.stats.behavior.IStatElement; +import org.apache.commons.jcs.engine.stats.behavior.IStats; +import org.apache.commons.jcs.utils.struct.DoubleLinkedList; +import org.apache.commons.logging.Log; +import org.apache.commons.logging.LogFactory; + +/** + * This class contains methods that are common to memory caches using the double linked list, such + * as the LRU, MRU, FIFO, and LIFO caches. + *

+ * Children can control the expiration algorithm by controlling the update and get. The last item in + * the list will be the one removed when the list fills. For instance LRU should more items to the + * front as they are used. FIFO should simply add new items to the front of the list. + */ +public abstract class AbstractDoubleLinkedListMemoryCache + extends AbstractMemoryCache +{ + /** Don't change. */ + private static final long serialVersionUID = 1422569420563967389L; + + /** The logger. */ + private static final Log log = LogFactory.getLog( AbstractDoubleLinkedListMemoryCache.class ); + + /** thread-safe double linked list for lru */ + protected DoubleLinkedList> list; // TODO privatise + + /** number of hits */ + private int hitCnt = 0; + + /** number of misses */ + private int missCnt = 0; + + /** number of puts */ + private int putCnt = 0; + + /** + * For post reflection creation initialization. + *

+ * @param hub + */ + @Override + public synchronized void initialize( CompositeCache hub ) + { + super.initialize( hub ); + list = new DoubleLinkedList>(); + log.info( "initialized MemoryCache for " + cacheName ); + } + + /** + * This is called by super initialize. + *

+ * @return new Hashtable() + */ + @Override + public Map> createMap() + { + return new Hashtable>(); + } + + /** + * Calls the abstract method updateList. + *

+ * If the max size is reached, an element will be put to disk. + *

+ * @param ce The cache element, or entry wrapper + * @throws IOException + */ + @Override + public final void update( ICacheElement ce ) + throws IOException + { + putCnt++; + + synchronized ( this ) + { + // ABSTRACT + MemoryElementDescriptor newNode = adjustListForUpdate( ce ); + + // this must be synchronized + MemoryElementDescriptor oldNode = map.put( newNode.ce.getKey(), newNode ); + + // If the node was the same as an existing node, remove it. + if ( oldNode != null && newNode.ce.getKey().equals( oldNode.ce.getKey() ) ) + { + list.remove( oldNode ); + } + } + + // If we are over the max spool some + spoolIfNeeded(); + } + + /** + * Children implement this to control the cache expiration algorithm + *

+ * @param ce + * @return MemoryElementDescriptor the new node + * @throws IOException + */ + protected abstract MemoryElementDescriptor adjustListForUpdate( ICacheElement ce ) + throws IOException; + + /** + * If the max size has been reached, spool. + *

+ * @throws Error + */ + private void spoolIfNeeded() + throws Error + { + int size = map.size(); + // If the element limit is reached, we need to spool + + if ( size <= this.cacheAttributes.getMaxObjects() ) + { + return; + } + + if ( log.isDebugEnabled() ) + { + log.debug( "In memory limit reached, spooling" ); + } + + // Write the last 'chunkSize' items to disk. + int chunkSizeCorrected = Math.min( size, chunkSize ); + + if ( log.isDebugEnabled() ) + { + log.debug( "About to spool to disk cache, map size: " + size + ", max objects: " + + this.cacheAttributes.getMaxObjects() + ", items to spool: " + chunkSizeCorrected ); + } + + // The spool will put them in a disk event queue, so there is no + // need to pre-queue the queuing. This would be a bit wasteful + // and wouldn't save much time in this synchronous call. + for ( int i = 0; i < chunkSizeCorrected; i++ ) + { + spoolLastElement(); + } + + if ( log.isDebugEnabled() ) + { + log.debug( "update: After spool map size: " + map.size() + " linked list size = " + dumpCacheSize() ); + } + } + + /** + * Get an item from the cache If the item is found, it is removed from the list and added first. + *

+ * @param key Identifies item to find + * @return ICacheElement if found, else null + * @throws IOException + */ + @Override + public final synchronized ICacheElement get( K key ) + throws IOException + { + ICacheElement ce = null; + + if ( log.isDebugEnabled() ) + { + log.debug( "getting item from cache " + cacheName + " for key " + key ); + } + + MemoryElementDescriptor me = map.get( key ); + + if ( me != null ) + { + ce = me.ce; + hitCnt++; + if ( log.isDebugEnabled() ) + { + log.debug( cacheName + ": LRUMemoryCache hit for " + ce.getKey() ); + } + + // ABSTRACT + adjustListForGet( me ); + } + else + { + missCnt++; + if ( log.isDebugEnabled() ) + { + log.debug( cacheName + ": LRUMemoryCache miss for " + key ); + } + } + + verifyCache(); + return ce; + } + + /** + * Adjust the list as needed for a get. This allows children to control the algorithm + *

+ * @param me + */ + protected abstract void adjustListForGet( MemoryElementDescriptor me ); + + /** + * This instructs the memory cache to remove the numberToFree according to its eviction + * policy. For example, the LRUMemoryCache will remove the numberToFree least recently + * used items. These will be spooled to disk if a disk auxiliary is available. + *

+ * @param numberToFree + * @return the number that were removed. if you ask to free 5, but there are only 3, you will + * get 3. + * @throws IOException + */ + @Override + public int freeElements( int numberToFree ) + throws IOException + { + int freed = 0; + for ( ; freed < numberToFree; freed++ ) + { + ICacheElement element = spoolLastElement(); + if ( element == null ) + { + break; + } + } + return freed; + } + + /** + * This spools the last element in the LRU, if one exists. + *

+ * @return ICacheElement if there was a last element, else null. + * @throws Error + */ + protected ICacheElement spoolLastElement() + throws Error + { + ICacheElement toSpool = null; + synchronized ( this ) + { + if ( list.getLast() != null ) + { + toSpool = list.getLast().ce; + if ( toSpool != null ) + { + cache.spoolToDisk( list.getLast().ce ); + if ( !map.containsKey( list.getLast().ce.getKey() ) ) + { + log.error( "update: map does not contain key: " + + list.getLast().ce.getKey() ); + verifyCache(); + } + if ( map.remove( list.getLast().ce.getKey() ) == null ) + { + log.warn( "update: remove failed for key: " + + list.getLast().ce.getKey() ); + verifyCache(); + } + } + else + { + throw new Error( "update: last.ce is null!" ); + } + list.removeLast(); + } + else + { + verifyCache(); + throw new Error( "update: last is null!" ); + } + + // If this is out of the sync block it can detect a mismatch + // where there is none. + if ( map.size() != dumpCacheSize() ) + { + log.warn( "update: After spool, size mismatch: map.size() = " + map.size() + ", linked list size = " + + dumpCacheSize() ); + } + } + return toSpool; + } + + /** + * Removes an item from the cache. This method handles hierarchical removal. If the key is a + * String and ends with the CacheConstants.NAME_COMPONENT_DELIMITER, then all items with keys + * starting with the argument String will be removed. + *

+ * @param key + * @return true if the removal was successful + * @throws IOException + */ + @Override + public synchronized boolean remove( K key ) + throws IOException + { + if ( log.isDebugEnabled() ) + { + log.debug( "removing item for key: " + key ); + } + + boolean removed = false; + + // handle partial removal + if ( key instanceof String && ( (String) key ).endsWith( CacheConstants.NAME_COMPONENT_DELIMITER ) ) + { + // remove all keys of the same name hierarchy. + synchronized ( map ) + { + for (Iterator>> itr = map.entrySet().iterator(); itr.hasNext(); ) + { + Map.Entry> entry = itr.next(); + K k = entry.getKey(); + + if ( k instanceof String && ( (String) k ).startsWith( key.toString() ) ) + { + list.remove( entry.getValue() ); + itr.remove(); + removed = true; + } + } + } + } + else if ( key instanceof GroupAttrName ) + { + // remove all keys of the same name hierarchy. + synchronized ( map ) + { + for (Iterator>> itr = map.entrySet().iterator(); itr.hasNext(); ) + { + Map.Entry> entry = itr.next(); + K k = entry.getKey(); + + if ( k instanceof GroupAttrName && + ((GroupAttrName)k).groupId.equals(((GroupAttrName)key).groupId)) + { + list.remove( entry.getValue() ); + itr.remove(); + removed = true; + } + } + } + } + else + { + // remove single item. + MemoryElementDescriptor me = map.remove( key ); + + if ( me != null ) + { + list.remove( me ); + removed = true; + } + } + + return removed; + } + + /** + * Remove all of the elements from both the Map and the linked list implementation. Overrides + * base class. + *

+ * @throws IOException + */ + @Override + public synchronized void removeAll() + throws IOException + { + map.clear(); + list.removeAll(); + } + + // --------------------------- internal methods (linked list implementation) + /** + * Adds a new node to the start of the link list. + *

+ * @param ce The feature to be added to the First + * @return MemoryElementDescriptor + */ + protected synchronized MemoryElementDescriptor addFirst( ICacheElement ce ) + { + MemoryElementDescriptor me = new MemoryElementDescriptor( ce ); + list.addFirst( me ); + verifyCache( ce.getKey() ); + return me; + } + + /** + * Adds a new node to the end of the link list. + *

+ * @param ce The feature to be added to the First + * @return MemoryElementDescriptor + */ + protected synchronized MemoryElementDescriptor addLast( ICacheElement ce ) + { + MemoryElementDescriptor me = new MemoryElementDescriptor( ce ); + list.addLast( me ); + verifyCache( ce.getKey() ); + return me; + } + + // ---------------------------------------------------------- debug methods + + /** + * Dump the cache entries from first to list for debugging. + */ + @SuppressWarnings("unchecked") // No generics for public fields + public void dumpCacheEntries() + { + log.debug( "dumpingCacheEntries" ); + for ( MemoryElementDescriptor me = list.getFirst(); me != null; me = (MemoryElementDescriptor) me.next ) + { + log.debug( "dumpCacheEntries> key=" + me.ce.getKey() + ", val=" + me.ce.getVal() ); + } + } + + /** + * Returns the size of the list. + *

+ * @return the number of items in the map. + */ + protected int dumpCacheSize() + { + return list.size(); + } + + /** + * Checks to see if all the items that should be in the cache are. Checks consistency between + * List and map. + */ + @SuppressWarnings("unchecked") // No generics for public fields + protected void verifyCache() + { + if ( !log.isDebugEnabled() ) + { + return; + } + + boolean found = false; + log.debug( "verifycache[" + cacheName + "]: mapContains " + map.size() + " elements, linked list contains " + + dumpCacheSize() + " elements" ); + log.debug( "verifycache: checking linked list by key " ); + for ( MemoryElementDescriptor li = list.getFirst(); li != null; li = (MemoryElementDescriptor) li.next ) + { + Object key = li.ce.getKey(); + if ( !map.containsKey( key ) ) + { + log.error( "verifycache[" + cacheName + "]: map does not contain key : " + li.ce.getKey() ); + log.error( "li.hashcode=" + li.ce.getKey().hashCode() ); + log.error( "key class=" + key.getClass() ); + log.error( "key hashcode=" + key.hashCode() ); + log.error( "key toString=" + key.toString() ); + if ( key instanceof GroupAttrName ) + { + GroupAttrName name = (GroupAttrName) key; + log.error( "GroupID hashcode=" + name.groupId.hashCode() ); + log.error( "GroupID.class=" + name.groupId.getClass() ); + log.error( "AttrName hashcode=" + name.attrName.hashCode() ); + log.error( "AttrName.class=" + name.attrName.getClass() ); + } + dumpMap(); + } + else if ( map.get( li.ce.getKey() ) == null ) + { + log.error( "verifycache[" + cacheName + "]: linked list retrieval returned null for key: " + + li.ce.getKey() ); + } + } + + log.debug( "verifycache: checking linked list by value " ); + for ( MemoryElementDescriptor li3 = list.getFirst(); li3 != null; li3 = (MemoryElementDescriptor) li3.next ) + { + if ( map.containsValue( li3 ) == false ) + { + log.error( "verifycache[" + cacheName + "]: map does not contain value : " + li3 ); + dumpMap(); + } + } + + log.debug( "verifycache: checking via keysets!" ); + for (Serializable val : map.keySet()) + { + found = false; + + for ( MemoryElementDescriptor li2 = list.getFirst(); li2 != null; li2 = (MemoryElementDescriptor) li2.next ) + { + if ( val.equals( li2.ce.getKey() ) ) + { + found = true; + break; + } + } + if ( !found ) + { + log.error( "verifycache[" + cacheName + "]: key not found in list : " + val ); + dumpCacheEntries(); + if ( map.containsKey( val ) ) + { + log.error( "verifycache: map contains key" ); + } + else + { + log.error( "verifycache: map does NOT contain key, what the HECK!" ); + } + } + } + } + + /** + * Logs an error if an element that should be in the cache is not. + *

+ * @param key + */ + @SuppressWarnings("unchecked") // No generics for public fields + private void verifyCache( K key ) + { + if ( !log.isDebugEnabled() ) + { + return; + } + + boolean found = false; + + // go through the linked list looking for the key + for ( MemoryElementDescriptor li = list.getFirst(); li != null; li = (MemoryElementDescriptor) li.next ) + { + if ( li.ce.getKey() == key ) + { + found = true; + log.debug( "verifycache(key) key match: " + key ); + break; + } + } + if ( !found ) + { + log.error( "verifycache(key)[" + cacheName + "], couldn't find key! : " + key ); + } + } + + // --------------------------- iteration methods (iteration helpers) + /** + * iteration aid + */ + public static class IteratorWrapper + implements Iterator>> + { + /** The internal iterator */ + private final Iterator>> i; + + /** + * Wrapped to remove our wrapper object + * @param m + */ + protected IteratorWrapper(Map> m) + { + i = m.entrySet().iterator(); + } + + /** @return i.hasNext() */ + @Override + public boolean hasNext() + { + return i.hasNext(); + } + + /** @return new MapEntryWrapper( (Map.Entry) i.next() ) */ + @Override + public Entry> next() + { + // return new MapEntryWrapper( i.next() ); + return i.next(); + } + + /** i.remove(); */ + @Override + public void remove() + { + i.remove(); + } + + /** + * @param o + * @return i.equals( o )) + */ + @Override + public boolean equals( Object o ) + { + return i.equals( o ); + } + + /** @return i.hashCode() */ + @Override + public int hashCode() + { + return i.hashCode(); + } + } + + /** + * @author Aaron Smuts + */ + public static class MapEntryWrapper + implements Map.Entry> + { + /** The internal entry */ + private final Map.Entry> e; + + /** + * @param e + */ + private MapEntryWrapper( Map.Entry> e ) + { + this.e = e; + } + + /** + * @param o + * @return e.equals( o ) + */ + @Override + public boolean equals( Object o ) + { + return e.equals( o ); + } + + /** @return e.getKey() */ + @Override + public K getKey() + { + return e.getKey(); + } + + /** @return ( (MemoryElementDescriptor) e.getValue() ).ce */ + @Override + public ICacheElement getValue() + { + return e.getValue().ce; + } + + /** @return e.hashCode() */ + @Override + public int hashCode() + { + return e.hashCode(); + } + + /** + * invalid + * @param value + * @return always throws + */ + @Override + public ICacheElement setValue(ICacheElement value) + { + throw new UnsupportedOperationException( "Use normal cache methods" + + " to alter the contents of the cache." ); + } + } + + /** + * Get an Array of the keys for all elements in the memory cache + * @return An Object[] + */ + @Override + public Set getKeySet() + { + // need a better locking strategy here. + synchronized ( this ) + { + // may need to lock to map here? + return new LinkedHashSet(map.keySet()); + } + } + + /** + * This returns semi-structured information on the memory cache, such as the size, put count, + * hit count, and miss count. + *

+ * @see org.apache.commons.jcs.engine.memory.behavior.IMemoryCache#getStatistics() + */ + @Override + public synchronized IStats getStatistics() + { + IStats stats = new Stats(); + stats.setTypeName( /*add algorithm name*/"Memory Cache" ); + + ArrayList elems = new ArrayList(); + + IStatElement se = null; + + se = new StatElement(); + se.setName( "List Size" ); + se.setData( "" + list.size() ); + elems.add( se ); + + se = new StatElement(); + se.setName( "Map Size" ); + se.setData( "" + map.size() ); + elems.add( se ); + + se = new StatElement(); + se.setName( "Put Count" ); + se.setData( "" + putCnt ); + elems.add( se ); + + se = new StatElement(); + se.setName( "Hit Count" ); + se.setData( "" + hitCnt ); + elems.add( se ); + + se = new StatElement(); + se.setName( "Miss Count" ); + se.setData( "" + missCnt ); + elems.add( se ); + + // get an array and put them in the Stats object + IStatElement[] ses = elems.toArray( new StatElement[0] ); + stats.setStatElements( ses ); + + return stats; + } +} Propchange: commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/memory/AbstractDoubleLinkedListMemoryCache.java ('svn:eol-style' removed) Modified: commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/memory/AbstractMemoryCache.java URL: http://svn.apache.org/viewvc/commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/memory/AbstractMemoryCache.java?rev=1585494&r1=1585493&r2=1585494&view=diff ============================================================================== --- commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/memory/AbstractMemoryCache.java (original) +++ commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/memory/AbstractMemoryCache.java Mon Apr 7 14:40:12 2014 @@ -22,7 +22,6 @@ package org.apache.commons.jcs.engine.me import java.io.IOException; import java.io.Serializable; import java.util.HashMap; -import java.util.Iterator; import java.util.Map; import java.util.Set; import java.util.concurrent.ScheduledExecutorService; @@ -301,17 +300,6 @@ public abstract class AbstractMemoryCach this.cache.spoolToDisk( ce ); } - /** - * Gets the iterator attribute of the LRUMemoryCache object - *

- * @return The iterator value - */ - @Override - public Iterator>> getIterator() - { - return map.entrySet().iterator(); - } - // ---------------------------------------------------------- debug method /** * Dump the cache map for debugging. Modified: commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/memory/behavior/IMemoryCache.java URL: http://svn.apache.org/viewvc/commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/memory/behavior/IMemoryCache.java?rev=1585494&r1=1585493&r2=1585494&view=diff ============================================================================== --- commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/memory/behavior/IMemoryCache.java (original) +++ commons/proper/jcs/trunk/src/java/org/apache/commons/jcs/engine/memory/behavior/IMemoryCache.java Mon Apr 7 14:40:12 2014 @@ -21,14 +21,12 @@ package org.apache.commons.jcs.engine.me import java.io.IOException; import java.io.Serializable; -import java.util.Iterator; import java.util.Map; import java.util.Set; import org.apache.commons.jcs.engine.behavior.ICacheElement; import org.apache.commons.jcs.engine.behavior.ICompositeCacheAttributes; import org.apache.commons.jcs.engine.control.CompositeCache; -import org.apache.commons.jcs.engine.memory.util.MemoryElementDescriptor; import org.apache.commons.jcs.engine.stats.behavior.IStats; /** For the framework. Insures methods a MemoryCache needs to access. */ @@ -64,15 +62,6 @@ public interface IMemoryCache - * @return An iterator - */ - Iterator>> getIterator(); - - /** * Get a set of the keys for all elements in the memory cache. *

* @return a set of the key type