Added:
jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/extra/collections/map/AbstractLinkedMap.java
URL:
http://svn.apache.org/viewvc/jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/extra/collections/map/AbstractLinkedMap.java?rev=580198&view=auto
==============================================================================
---
jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/extra/collections/map/AbstractLinkedMap.java
(added)
+++
jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/extra/collections/map/AbstractLinkedMap.java
Thu Sep 27 20:08:40 2007
@@ -0,0 +1,608 @@
+/*
+ * Copyright 2003-2004 The Apache Software Foundation
+ *
+ * Licensed 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.
+ */
+package org.apache.taglibs.standard.extra.commons.collections.map;
+
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+
+import org.apache.taglibs.standard.extra.commons.collections.MapIterator;
+import org.apache.taglibs.standard.extra.commons.collections.OrderedIterator;
+import org.apache.taglibs.standard.extra.commons.collections.OrderedMap;
+import
org.apache.taglibs.standard.extra.commons.collections.OrderedMapIterator;
+import
org.apache.taglibs.standard.extra.commons.collections.ResettableIterator;
+import
org.apache.taglibs.standard.extra.commons.collections.iterators.EmptyOrderedIterator;
+import
org.apache.taglibs.standard.extra.commons.collections.iterators.EmptyOrderedMapIterator;
+
+/**
+ * An abstract implementation of a hash-based map that links entries to create
an
+ * ordered map and which provides numerous points for subclasses to override.
+ * <p>
+ * This class implements all the features necessary for a subclass linked
+ * hash-based map. Key-value entries are stored in instances of the
+ * <code>LinkEntry</code> class which can be overridden and replaced.
+ * The iterators can similarly be replaced, without the need to replace the
KeySet,
+ * EntrySet and Values view classes.
+ * <p>
+ * Overridable methods are provided to change the default hashing behaviour,
and
+ * to change how entries are added to and removed from the map. Hopefully, all
you
+ * need for unusual subclasses is here.
+ * <p>
+ * This implementation maintains order by original insertion, but subclasses
+ * may work differently. The <code>OrderedMap</code> interface is implemented
+ * to provide access to bidirectional iteration and extra convenience methods.
+ * <p>
+ * The <code>orderedMapIterator()</code> method provides direct access to a
+ * bidirectional iterator. The iterators from the other views can also be cast
+ * to <code>OrderedIterator</code> if required.
+ * <p>
+ * All the available iterators can be reset back to the start by casting to
+ * <code>ResettableIterator</code> and calling <code>reset()</code>.
+ * <p>
+ * The implementation is also designed to be subclassed, with lots of useful
+ * methods exposed.
+ *
+ * @since Commons Collections 3.0
+ * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct
2004) $
+ *
+ * @author java util LinkedHashMap
+ * @author Stephen Colebourne
+ */
+public class AbstractLinkedMap extends AbstractHashedMap implements OrderedMap
{
+
+ /** Header in the linked list */
+ protected transient LinkEntry header;
+
+ /**
+ * Constructor only used in deserialization, do not use otherwise.
+ */
+ protected AbstractLinkedMap() {
+ super();
+ }
+
+ /**
+ * Constructor which performs no validation on the passed in parameters.
+ *
+ * @param initialCapacity the initial capacity, must be a power of two
+ * @param loadFactor the load factor, must be > 0.0f and generally < 1.0f
+ * @param threshold the threshold, must be sensible
+ */
+ protected AbstractLinkedMap(int initialCapacity, float loadFactor, int
threshold) {
+ super(initialCapacity, loadFactor, threshold);
+ }
+
+ /**
+ * Constructs a new, empty map with the specified initial capacity.
+ *
+ * @param initialCapacity the initial capacity
+ * @throws IllegalArgumentException if the initial capacity is less than
one
+ */
+ protected AbstractLinkedMap(int initialCapacity) {
+ super(initialCapacity);
+ }
+
+ /**
+ * Constructs a new, empty map with the specified initial capacity and
+ * load factor.
+ *
+ * @param initialCapacity the initial capacity
+ * @param loadFactor the load factor
+ * @throws IllegalArgumentException if the initial capacity is less than
one
+ * @throws IllegalArgumentException if the load factor is less than zero
+ */
+ protected AbstractLinkedMap(int initialCapacity, float loadFactor) {
+ super(initialCapacity, loadFactor);
+ }
+
+ /**
+ * Constructor copying elements from another map.
+ *
+ * @param map the map to copy
+ * @throws NullPointerException if the map is null
+ */
+ protected AbstractLinkedMap(Map map) {
+ super(map);
+ }
+
+ /**
+ * Initialise this subclass during construction.
+ */
+ protected void init() {
+ header = new LinkEntry(null, -1, null, null);
+ header.before = header.after = header;
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Checks whether the map contains the specified value.
+ *
+ * @param value the value to search for
+ * @return true if the map contains the value
+ */
+ public boolean containsValue(Object value) {
+ // override uses faster iterator
+ if (value == null) {
+ for (LinkEntry entry = header.after; entry != header; entry =
entry.after) {
+ if (entry.getValue() == null) {
+ return true;
+ }
+ }
+ } else {
+ for (LinkEntry entry = header.after; entry != header; entry =
entry.after) {
+ if (isEqualValue(value, entry.getValue())) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Clears the map, resetting the size to zero and nullifying references
+ * to avoid garbage collection issues.
+ */
+ public void clear() {
+ // override to reset the linked list
+ super.clear();
+ header.before = header.after = header;
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Gets the first key in the map, which is the most recently inserted.
+ *
+ * @return the most recently inserted key
+ */
+ public Object firstKey() {
+ if (size == 0) {
+ throw new NoSuchElementException("Map is empty");
+ }
+ return header.after.getKey();
+ }
+
+ /**
+ * Gets the last key in the map, which is the first inserted.
+ *
+ * @return the eldest key
+ */
+ public Object lastKey() {
+ if (size == 0) {
+ throw new NoSuchElementException("Map is empty");
+ }
+ return header.before.getKey();
+ }
+
+ /**
+ * Gets the next key in sequence.
+ *
+ * @param key the key to get after
+ * @return the next key
+ */
+ public Object nextKey(Object key) {
+ LinkEntry entry = (LinkEntry) getEntry(key);
+ return (entry == null || entry.after == header ? null :
entry.after.getKey());
+ }
+
+ /**
+ * Gets the previous key in sequence.
+ *
+ * @param key the key to get before
+ * @return the previous key
+ */
+ public Object previousKey(Object key) {
+ LinkEntry entry = (LinkEntry) getEntry(key);
+ return (entry == null || entry.before == header ? null :
entry.before.getKey());
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Gets the key at the specified index.
+ *
+ * @param index the index to retrieve
+ * @return the key at the specified index
+ * @throws IndexOutOfBoundsException if the index is invalid
+ */
+ protected LinkEntry getEntry(int index) {
+ if (index < 0) {
+ throw new IndexOutOfBoundsException("Index " + index + " is less
than zero");
+ }
+ if (index >= size) {
+ throw new IndexOutOfBoundsException("Index " + index + " is
invalid for size " + size);
+ }
+ LinkEntry entry;
+ if (index < (size / 2)) {
+ // Search forwards
+ entry = header.after;
+ for (int currentIndex = 0; currentIndex < index; currentIndex++) {
+ entry = entry.after;
+ }
+ } else {
+ // Search backwards
+ entry = header;
+ for (int currentIndex = size; currentIndex > index;
currentIndex--) {
+ entry = entry.before;
+ }
+ }
+ return entry;
+ }
+
+ /**
+ * Adds an entry into this map, maintaining insertion order.
+ * <p>
+ * This implementation adds the entry to the data storage table and
+ * to the end of the linked list.
+ *
+ * @param entry the entry to add
+ * @param hashIndex the index into the data array to store at
+ */
+ protected void addEntry(HashEntry entry, int hashIndex) {
+ LinkEntry link = (LinkEntry) entry;
+ link.after = header;
+ link.before = header.before;
+ header.before.after = link;
+ header.before = link;
+ data[hashIndex] = entry;
+ }
+
+ /**
+ * Creates an entry to store the data.
+ * <p>
+ * This implementation creates a new LinkEntry instance.
+ *
+ * @param next the next entry in sequence
+ * @param hashCode the hash code to use
+ * @param key the key to store
+ * @param value the value to store
+ * @return the newly created entry
+ */
+ protected HashEntry createEntry(HashEntry next, int hashCode, Object key,
Object value) {
+ return new LinkEntry(next, hashCode, key, value);
+ }
+
+ /**
+ * Removes an entry from the map and the linked list.
+ * <p>
+ * This implementation removes the entry from the linked list chain, then
+ * calls the superclass implementation.
+ *
+ * @param entry the entry to remove
+ * @param hashIndex the index into the data structure
+ * @param previous the previous entry in the chain
+ */
+ protected void removeEntry(HashEntry entry, int hashIndex, HashEntry
previous) {
+ LinkEntry link = (LinkEntry) entry;
+ link.before.after = link.after;
+ link.after.before = link.before;
+ link.after = null;
+ link.before = null;
+ super.removeEntry(entry, hashIndex, previous);
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Gets the <code>before</code> field from a <code>LinkEntry</code>.
+ * Used in subclasses that have no visibility of the field.
+ *
+ * @param entry the entry to query, must not be null
+ * @return the <code>before</code> field of the entry
+ * @throws NullPointerException if the entry is null
+ * @since Commons Collections 3.1
+ */
+ protected LinkEntry entryBefore(LinkEntry entry) {
+ return entry.before;
+ }
+
+ /**
+ * Gets the <code>after</code> field from a <code>LinkEntry</code>.
+ * Used in subclasses that have no visibility of the field.
+ *
+ * @param entry the entry to query, must not be null
+ * @return the <code>after</code> field of the entry
+ * @throws NullPointerException if the entry is null
+ * @since Commons Collections 3.1
+ */
+ protected LinkEntry entryAfter(LinkEntry entry) {
+ return entry.after;
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Gets an iterator over the map.
+ * Changes made to the iterator affect this map.
+ * <p>
+ * A MapIterator returns the keys in the map. It also provides convenient
+ * methods to get the key and value, and set the value.
+ * It avoids the need to create an entrySet/keySet/values object.
+ *
+ * @return the map iterator
+ */
+ public MapIterator mapIterator() {
+ if (size == 0) {
+ return EmptyOrderedMapIterator.INSTANCE;
+ }
+ return new LinkMapIterator(this);
+ }
+
+ /**
+ * Gets a bidirectional iterator over the map.
+ * Changes made to the iterator affect this map.
+ * <p>
+ * A MapIterator returns the keys in the map. It also provides convenient
+ * methods to get the key and value, and set the value.
+ * It avoids the need to create an entrySet/keySet/values object.
+ *
+ * @return the map iterator
+ */
+ public OrderedMapIterator orderedMapIterator() {
+ if (size == 0) {
+ return EmptyOrderedMapIterator.INSTANCE;
+ }
+ return new LinkMapIterator(this);
+ }
+
+ /**
+ * MapIterator implementation.
+ */
+ protected static class LinkMapIterator extends LinkIterator implements
OrderedMapIterator {
+
+ protected LinkMapIterator(AbstractLinkedMap parent) {
+ super(parent);
+ }
+
+ public Object next() {
+ return super.nextEntry().getKey();
+ }
+
+ public Object previous() {
+ return super.previousEntry().getKey();
+ }
+
+ public Object getKey() {
+ HashEntry current = currentEntry();
+ if (current == null) {
+ throw new
IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
+ }
+ return current.getKey();
+ }
+
+ public Object getValue() {
+ HashEntry current = currentEntry();
+ if (current == null) {
+ throw new
IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
+ }
+ return current.getValue();
+ }
+
+ public Object setValue(Object value) {
+ HashEntry current = currentEntry();
+ if (current == null) {
+ throw new
IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
+ }
+ return current.setValue(value);
+ }
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Creates an entry set iterator.
+ * Subclasses can override this to return iterators with different
properties.
+ *
+ * @return the entrySet iterator
+ */
+ protected Iterator createEntrySetIterator() {
+ if (size() == 0) {
+ return EmptyOrderedIterator.INSTANCE;
+ }
+ return new EntrySetIterator(this);
+ }
+
+ /**
+ * EntrySet iterator.
+ */
+ protected static class EntrySetIterator extends LinkIterator {
+
+ protected EntrySetIterator(AbstractLinkedMap parent) {
+ super(parent);
+ }
+
+ public Object next() {
+ return super.nextEntry();
+ }
+
+ public Object previous() {
+ return super.previousEntry();
+ }
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Creates a key set iterator.
+ * Subclasses can override this to return iterators with different
properties.
+ *
+ * @return the keySet iterator
+ */
+ protected Iterator createKeySetIterator() {
+ if (size() == 0) {
+ return EmptyOrderedIterator.INSTANCE;
+ }
+ return new KeySetIterator(this);
+ }
+
+ /**
+ * KeySet iterator.
+ */
+ protected static class KeySetIterator extends EntrySetIterator {
+
+ protected KeySetIterator(AbstractLinkedMap parent) {
+ super(parent);
+ }
+
+ public Object next() {
+ return super.nextEntry().getKey();
+ }
+
+ public Object previous() {
+ return super.previousEntry().getKey();
+ }
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Creates a values iterator.
+ * Subclasses can override this to return iterators with different
properties.
+ *
+ * @return the values iterator
+ */
+ protected Iterator createValuesIterator() {
+ if (size() == 0) {
+ return EmptyOrderedIterator.INSTANCE;
+ }
+ return new ValuesIterator(this);
+ }
+
+ /**
+ * Values iterator.
+ */
+ protected static class ValuesIterator extends LinkIterator {
+
+ protected ValuesIterator(AbstractLinkedMap parent) {
+ super(parent);
+ }
+
+ public Object next() {
+ return super.nextEntry().getValue();
+ }
+
+ public Object previous() {
+ return super.previousEntry().getValue();
+ }
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * LinkEntry that stores the data.
+ * <p>
+ * If you subclass <code>AbstractLinkedMap</code> but not
<code>LinkEntry</code>
+ * then you will not be able to access the protected fields.
+ * The <code>entryXxx()</code> methods on <code>AbstractLinkedMap</code>
exist
+ * to provide the necessary access.
+ */
+ protected static class LinkEntry extends HashEntry {
+ /** The entry before this one in the order */
+ protected LinkEntry before;
+ /** The entry after this one in the order */
+ protected LinkEntry after;
+
+ /**
+ * Constructs a new entry.
+ *
+ * @param next the next entry in the hash bucket sequence
+ * @param hashCode the hash code
+ * @param key the key
+ * @param value the value
+ */
+ protected LinkEntry(HashEntry next, int hashCode, Object key, Object
value) {
+ super(next, hashCode, key, value);
+ }
+ }
+
+ /**
+ * Base Iterator that iterates in link order.
+ */
+ protected static abstract class LinkIterator
+ implements OrderedIterator, ResettableIterator {
+
+ /** The parent map */
+ protected final AbstractLinkedMap parent;
+ /** The current (last returned) entry */
+ protected LinkEntry last;
+ /** The next entry */
+ protected LinkEntry next;
+ /** The modification count expected */
+ protected int expectedModCount;
+
+ protected LinkIterator(AbstractLinkedMap parent) {
+ super();
+ this.parent = parent;
+ this.next = parent.header.after;
+ this.expectedModCount = parent.modCount;
+ }
+
+ public boolean hasNext() {
+ return (next != parent.header);
+ }
+
+ public boolean hasPrevious() {
+ return (next.before != parent.header);
+ }
+
+ protected LinkEntry nextEntry() {
+ if (parent.modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ if (next == parent.header) {
+ throw new
NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
+ }
+ last = next;
+ next = next.after;
+ return last;
+ }
+
+ protected LinkEntry previousEntry() {
+ if (parent.modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ LinkEntry previous = next.before;
+ if (previous == parent.header) {
+ throw new
NoSuchElementException(AbstractHashedMap.NO_PREVIOUS_ENTRY);
+ }
+ next = previous;
+ last = previous;
+ return last;
+ }
+
+ protected LinkEntry currentEntry() {
+ return last;
+ }
+
+ public void remove() {
+ if (last == null) {
+ throw new
IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
+ }
+ if (parent.modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ parent.remove(last.getKey());
+ last = null;
+ expectedModCount = parent.modCount;
+ }
+
+ public void reset() {
+ last = null;
+ next = parent.header.after;
+ }
+
+ public String toString() {
+ if (last != null) {
+ return "Iterator[" + last.getKey() + "=" + last.getValue() +
"]";
+ } else {
+ return "Iterator[]";
+ }
+ }
+ }
+
+}
Propchange:
jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/extra/collections/map/AbstractLinkedMap.java
------------------------------------------------------------------------------
svn:eol-style = native
Added:
jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/extra/collections/map/LRUMap.java
URL:
http://svn.apache.org/viewvc/jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/extra/collections/map/LRUMap.java?rev=580198&view=auto
==============================================================================
---
jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/extra/collections/map/LRUMap.java
(added)
+++
jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/extra/collections/map/LRUMap.java
Thu Sep 27 20:08:40 2007
@@ -0,0 +1,391 @@
+/*
+ * Copyright 2001-2004 The Apache Software Foundation
+ *
+ * Licensed 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.
+ */
+package org.apache.taglibs.standard.extra.commons.collections.map;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+import java.util.Map;
+
+import org.apache.taglibs.standard.extra.commons.collections.BoundedMap;
+
+/**
+ * A <code>Map</code> implementation with a fixed maximum size which removes
+ * the least recently used entry if an entry is added when full.
+ * <p>
+ * The least recently used algorithm works on the get and put operations only.
+ * Iteration of any kind, including setting the value by iteration, does not
+ * change the order. Queries such as containsKey and containsValue or access
+ * via views also do not change the order.
+ * <p>
+ * The map implements <code>OrderedMap</code> and entries may be queried using
+ * the bidirectional <code>OrderedMapIterator</code>. The order returned is
+ * least recently used to most recently used. Iterators from map views can
+ * also be cast to <code>OrderedIterator</code> if required.
+ * <p>
+ * All the available iterators can be reset back to the start by casting to
+ * <code>ResettableIterator</code> and calling <code>reset()</code>.
+ *
+ * @since Commons Collections 3.0 (previously in main package v1.0)
+ * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct
2004) $
+ *
+ * @author James Strachan
+ * @author Morgan Delagrange
+ * @author Stephen Colebourne
+ * @author Mike Pettypiece
+ * @author Mario Ivankovits
+ */
+public class LRUMap
+ extends AbstractLinkedMap implements BoundedMap, Serializable,
Cloneable {
+
+ /** Serialisation version */
+ static final long serialVersionUID = -612114643488955218L;
+ /** Default maximum size */
+ protected static final int DEFAULT_MAX_SIZE = 100;
+
+ /** Maximum size */
+ private transient int maxSize;
+ /** Scan behaviour */
+ private boolean scanUntilRemovable;
+
+ /**
+ * Constructs a new empty map with a maximum size of 100.
+ */
+ public LRUMap() {
+ this(DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR, false);
+ }
+
+ /**
+ * Constructs a new, empty map with the specified maximum size.
+ *
+ * @param maxSize the maximum size of the map
+ * @throws IllegalArgumentException if the maximum size is less than one
+ */
+ public LRUMap(int maxSize) {
+ this(maxSize, DEFAULT_LOAD_FACTOR);
+ }
+
+ /**
+ * Constructs a new, empty map with the specified maximum size.
+ *
+ * @param maxSize the maximum size of the map
+ * @param scanUntilRemovable scan until a removeable entry is found,
default false
+ * @throws IllegalArgumentException if the maximum size is less than one
+ * @since Commons Collections 3.1
+ */
+ public LRUMap(int maxSize, boolean scanUntilRemovable) {
+ this(maxSize, DEFAULT_LOAD_FACTOR, scanUntilRemovable);
+ }
+
+ /**
+ * Constructs a new, empty map with the specified initial capacity and
+ * load factor.
+ *
+ * @param maxSize the maximum size of the map, -1 for no limit,
+ * @param loadFactor the load factor
+ * @throws IllegalArgumentException if the maximum size is less than one
+ * @throws IllegalArgumentException if the load factor is less than zero
+ */
+ public LRUMap(int maxSize, float loadFactor) {
+ this(maxSize, loadFactor, false);
+ }
+
+ /**
+ * Constructs a new, empty map with the specified initial capacity and
+ * load factor.
+ *
+ * @param maxSize the maximum size of the map, -1 for no limit,
+ * @param loadFactor the load factor
+ * @param scanUntilRemovable scan until a removeable entry is found,
default false
+ * @throws IllegalArgumentException if the maximum size is less than one
+ * @throws IllegalArgumentException if the load factor is less than zero
+ * @since Commons Collections 3.1
+ */
+ public LRUMap(int maxSize, float loadFactor, boolean scanUntilRemovable) {
+ super((maxSize < 1 ? DEFAULT_CAPACITY : maxSize), loadFactor);
+ if (maxSize < 1) {
+ throw new IllegalArgumentException("LRUMap max size must be
greater than 0");
+ }
+ this.maxSize = maxSize;
+ this.scanUntilRemovable = scanUntilRemovable;
+ }
+
+ /**
+ * Constructor copying elements from another map.
+ * <p>
+ * The maximum size is set from the map's size.
+ *
+ * @param map the map to copy
+ * @throws NullPointerException if the map is null
+ * @throws IllegalArgumentException if the map is empty
+ */
+ public LRUMap(Map map) {
+ this(map, false);
+ }
+
+ /**
+ * Constructor copying elements from another map.
+ * <p/>
+ * The maximum size is set from the map's size.
+ *
+ * @param map the map to copy
+ * @param scanUntilRemovable scan until a removeable entry is found,
default false
+ * @throws NullPointerException if the map is null
+ * @throws IllegalArgumentException if the map is empty
+ * @since Commons Collections 3.1
+ */
+ public LRUMap(Map map, boolean scanUntilRemovable) {
+ this(map.size(), DEFAULT_LOAD_FACTOR, scanUntilRemovable);
+ putAll(map);
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Gets the value mapped to the key specified.
+ * <p>
+ * This operation changes the position of the key in the map to the
+ * most recently used position (first).
+ *
+ * @param key the key
+ * @return the mapped value, null if no match
+ */
+ public Object get(Object key) {
+ LinkEntry entry = (LinkEntry) getEntry(key);
+ if (entry == null) {
+ return null;
+ }
+ moveToMRU(entry);
+ return entry.getValue();
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Moves an entry to the MRU position at the end of the list.
+ * <p>
+ * This implementation moves the updated entry to the end of the list.
+ *
+ * @param entry the entry to update
+ */
+ protected void moveToMRU(LinkEntry entry) {
+ if (entry.after != header) {
+ modCount++;
+ // remove
+ entry.before.after = entry.after;
+ entry.after.before = entry.before;
+ // add first
+ entry.after = header;
+ entry.before = header.before;
+ header.before.after = entry;
+ header.before = entry;
+ }
+ }
+
+ /**
+ * Updates an existing key-value mapping.
+ * <p>
+ * This implementation moves the updated entry to the top of the list
+ * using [EMAIL PROTECTED] #moveToMRU(AbstractLinkedMap.LinkEntry)}.
+ *
+ * @param entry the entry to update
+ * @param newValue the new value to store
+ */
+ protected void updateEntry(HashEntry entry, Object newValue) {
+ moveToMRU((LinkEntry) entry); // handles modCount
+ entry.setValue(newValue);
+ }
+
+ /**
+ * Adds a new key-value mapping into this map.
+ * <p>
+ * This implementation checks the LRU size and determines whether to
+ * discard an entry or not using [EMAIL PROTECTED]
#removeLRU(AbstractLinkedMap.LinkEntry)}.
+ * <p>
+ * From Commons Collections 3.1 this method uses [EMAIL PROTECTED]
#isFull()} rather
+ * than accessing <code>size</code> and <code>maxSize</code> directly.
+ * It also handles the scanUntilRemovable functionality.
+ *
+ * @param hashIndex the index into the data array to store at
+ * @param hashCode the hash code of the key to add
+ * @param key the key to add
+ * @param value the value to add
+ */
+ protected void addMapping(int hashIndex, int hashCode, Object key, Object
value) {
+ if (isFull()) {
+ LinkEntry reuse = header.after;
+ boolean removeLRUEntry = false;
+ if (scanUntilRemovable) {
+ while (reuse != header) {
+ if (removeLRU(reuse)) {
+ removeLRUEntry = true;
+ break;
+ }
+ reuse = reuse.after;
+ }
+ } else {
+ removeLRUEntry = removeLRU(reuse);
+ }
+
+ if (removeLRUEntry) {
+ reuseMapping(reuse, hashIndex, hashCode, key, value);
+ } else {
+ super.addMapping(hashIndex, hashCode, key, value);
+ }
+ } else {
+ super.addMapping(hashIndex, hashCode, key, value);
+ }
+ }
+
+ /**
+ * Reuses an entry by removing it and moving it to a new place in the map.
+ * <p>
+ * This method uses [EMAIL PROTECTED] #removeEntry}, [EMAIL PROTECTED]
#reuseEntry} and [EMAIL PROTECTED] #addEntry}.
+ *
+ * @param entry the entry to reuse
+ * @param hashIndex the index into the data array to store at
+ * @param hashCode the hash code of the key to add
+ * @param key the key to add
+ * @param value the value to add
+ */
+ protected void reuseMapping(LinkEntry entry, int hashIndex, int hashCode,
Object key, Object value) {
+ // find the entry before the entry specified in the hash table
+ // remember that the parameters (except the first) refer to the new
entry,
+ // not the old one
+ int removeIndex = hashIndex(entry.hashCode, data.length);
+ HashEntry loop = data[removeIndex];
+ HashEntry previous = null;
+ while (loop != entry) {
+ previous = loop;
+ loop = loop.next;
+ }
+
+ // reuse the entry
+ modCount++;
+ removeEntry(entry, removeIndex, previous);
+ reuseEntry(entry, hashIndex, hashCode, key, value);
+ addEntry(entry, hashIndex);
+ }
+
+ /**
+ * Subclass method to control removal of the least recently used entry
from the map.
+ * <p>
+ * This method exists for subclasses to override. A subclass may wish to
+ * provide cleanup of resources when an entry is removed. For example:
+ * <pre>
+ * protected boolean removeLRU(LinkEntry entry) {
+ * releaseResources(entry.getValue()); // release resources held by
entry
+ * return true; // actually delete entry
+ * }
+ * </pre>
+ * <p>
+ * Alternatively, a subclass may choose to not remove the entry or
selectively
+ * keep certain LRU entries. For example:
+ * <pre>
+ * protected boolean removeLRU(LinkEntry entry) {
+ * if (entry.getKey().toString().startsWith("System.")) {
+ * return false; // entry not removed from LRUMap
+ * } else {
+ * return true; // actually delete entry
+ * }
+ * }
+ * </pre>
+ * The effect of returning false is dependent on the scanUntilRemovable
flag.
+ * If the flag is true, the next LRU entry will be passed to this method
and so on
+ * until one returns false and is removed, or every entry in the map has
been passed.
+ * If the scanUntilRemovable flag is false, the map will exceed the
maximum size.
+ * <p>
+ * NOTE: Commons Collections 3.0 passed the wrong entry to this method.
+ * This is fixed in version 3.1 onwards.
+ *
+ * @param entry the entry to be removed
+ */
+ protected boolean removeLRU(LinkEntry entry) {
+ return true;
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Returns true if this map is full and no new mappings can be added.
+ *
+ * @return <code>true</code> if the map is full
+ */
+ public boolean isFull() {
+ return (size >= maxSize);
+ }
+
+ /**
+ * Gets the maximum size of the map (the bound).
+ *
+ * @return the maximum number of elements the map can hold
+ */
+ public int maxSize() {
+ return maxSize;
+ }
+
+ /**
+ * Whether this LRUMap will scan until a removable entry is found when the
+ * map is full.
+ *
+ * @return true if this map scans
+ * @since Commons Collections 3.1
+ */
+ public boolean isScanUntilRemovable() {
+ return scanUntilRemovable;
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Clones the map without cloning the keys or values.
+ *
+ * @return a shallow clone
+ */
+ public Object clone() {
+ return super.clone();
+ }
+
+ /**
+ * Write the map out using a custom routine.
+ */
+ private void writeObject(ObjectOutputStream out) throws IOException {
+ out.defaultWriteObject();
+ doWriteObject(out);
+ }
+
+ /**
+ * Read the map in using a custom routine.
+ */
+ private void readObject(ObjectInputStream in) throws IOException,
ClassNotFoundException {
+ in.defaultReadObject();
+ doReadObject(in);
+ }
+
+ /**
+ * Writes the data necessary for <code>put()</code> to work in
deserialization.
+ */
+ protected void doWriteObject(ObjectOutputStream out) throws IOException {
+ out.writeInt(maxSize);
+ super.doWriteObject(out);
+ }
+
+ /**
+ * Reads the data necessary for <code>put()</code> to work in the
superclass.
+ */
+ protected void doReadObject(ObjectInputStream in) throws IOException,
ClassNotFoundException {
+ maxSize = in.readInt();
+ super.doReadObject(in);
+ }
+
+}
Propchange:
jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/extra/collections/map/LRUMap.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified:
jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/lang/jstl/ELEvaluator.java
URL:
http://svn.apache.org/viewvc/jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/lang/jstl/ELEvaluator.java?rev=580198&r1=580197&r2=580198&view=diff
==============================================================================
---
jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/lang/jstl/ELEvaluator.java
(original)
+++
jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/lang/jstl/ELEvaluator.java
Thu Sep 27 20:08:40 2007
@@ -27,6 +27,10 @@
import org.apache.taglibs.standard.lang.jstl.parser.ParseException;
import org.apache.taglibs.standard.lang.jstl.parser.Token;
import org.apache.taglibs.standard.lang.jstl.parser.TokenMgrError;
+import org.apache.taglibs.standard.extra.commons.collections.map.LRUMap;
+
+import javax.servlet.jsp.PageContext;
+import javax.servlet.jsp.jstl.core.Config;
/**
*
@@ -89,14 +93,30 @@
// Member variables
//-------------------------------------
+ /**
+ * Name of configuration setting for maximum number of entries in the
+ * cached expression string map
+ */
+ private static final String EXPR_CACHE_PARAM
+ = "org.apache.taglibs.standard.lang.jstl.exprCacheSize";
+ /**
+ * Default maximum cache size
+ */
+ private static final int MAX_SIZE = 100;
+
/** The mapping from expression String to its parsed form (String,
- Expression, or ExpressionString) **/
- static Map sCachedExpressionStrings =
- Collections.synchronizedMap (new HashMap ());
+ * Expression, or ExpressionString)
+ *
+ * Using LRU Map with a maximum capacity to avoid out of bound map
+ * growth.
+ *
+ * NOTE: use LinkedHashmap if a dependency on J2SE 1.4+ is ok
+ */
+ static Map sCachedExpressionStrings = null;
/** The mapping from ExpectedType to Maps mapping literal String to
parsed value **/
- static Map sCachedExpectedTypes = new HashMap ();
+ static Map sCachedExpectedTypes = new HashMap();
/** The static Logger **/
static Logger sLogger = new Logger (System.out);
@@ -107,6 +127,10 @@
/** Flag if the cache should be bypassed **/
boolean mBypassCache;
+ /** The PageContext **/
+ PageContext pageContext;
+
+
//-------------------------------------
/**
*
@@ -123,20 +147,11 @@
//-------------------------------------
/**
+ * Enable cache bypass
*
- * Constructor
- *
- * @param pResolver the object that should be used to resolve
- * variable names encountered in expressions. If null, all variable
- * references will resolve to null.
- *
- * @param pBypassCache flag indicating if the cache should be
- * bypassed
+ * @param pBypassCache flag indicating cache should be bypassed
**/
- public ELEvaluator (VariableResolver pResolver,
- boolean pBypassCache)
- {
- mResolver = pResolver;
+ public void setBypassCache(boolean pBypassCache) {
mBypassCache = pBypassCache;
}
@@ -187,6 +202,9 @@
(Constants.NULL_EXPRESSION_STRING);
}
+ // Set the PageContext;
+ pageContext = (PageContext) pContext;
+
// Get the parsed version of the expression string
Object parsedValue = parseExpressionString (pExpressionString);
@@ -247,6 +265,10 @@
return "";
}
+ if (!(mBypassCache) && (sCachedExpressionStrings == null)) {
+ createExpressionStringMap();
+ }
+
// See if it's in the cache
Object ret =
mBypassCache ?
@@ -259,7 +281,9 @@
ELParser parser = new ELParser (r);
try {
ret = parser.ExpressionString ();
- sCachedExpressionStrings.put (pExpressionString, ret);
+ if (!mBypassCache) {
+ sCachedExpressionStrings.put (pExpressionString, ret);
+ }
}
catch (ParseException exc) {
throw new ELException
@@ -339,6 +363,30 @@
}
return ret;
}
+ }
+
+ //-------------------------------------
+ /**
+ *
+ * Creates LRU map of expression strings. If context parameter
+ * specifying cache size is present use that as the maximum size
+ * of the LRU map otherwise use default.
+ **/
+ private synchronized void createExpressionStringMap () {
+ if (sCachedExpressionStrings != null) {
+ return;
+ }
+
+ String value = pageContext.getServletContext().
+ getInitParameter(EXPR_CACHE_PARAM);
+ if (value != null) {
+ sCachedExpressionStrings =
+ Collections.synchronizedMap(new LRUMap(Integer.parseInt(value)));
+ }
+ else {
+ sCachedExpressionStrings =
+ Collections.synchronizedMap(new LRUMap(MAX_SIZE));
+ }
}
//-------------------------------------
Modified:
jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/lang/jstl/Evaluator.java
URL:
http://svn.apache.org/viewvc/jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/lang/jstl/Evaluator.java?rev=580198&r1=580197&r2=580198&view=diff
==============================================================================
---
jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/lang/jstl/Evaluator.java
(original)
+++
jakarta/taglibs/proper/standard/trunk/src/org/apache/taglibs/standard/lang/jstl/Evaluator.java
Thu Sep 27 20:08:40 2007
@@ -68,7 +68,9 @@
String pAttributeValue)
{
try {
+ sEvaluator.setBypassCache(true);
sEvaluator.parseExpressionString (pAttributeValue);
+ sEvaluator.setBypassCache(false);
return null;
}
catch (ELException exc) {
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
