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 {@link #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 {@link #removeLRU(AbstractLinkedMap.LinkEntry)}.
+ * <p>
+ * From Commons Collections 3.1 this method uses {@link #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 {@link #removeEntry}, {@link #reuseEntry} and {@link #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) {
lmpx.com only provides a reader for public news (NNTP) servers. It is not
affiliated with the servers or forums shown here and is not responsible for
the content of articles, which is written by their respective authors.