Author: rjung
Date: Thu Oct 28 16:27:31 2010
New Revision: 1028377
URL: http://svn.apache.org/viewvc?rev=1028377&view=rev
Log:
Overhaul JspQueue, no functional change for Jasper.
- Rename class to FastRemovalDequeue, because
it can be used gnerally. Nothing jsp related in it.
- Rename "head" to "first" as a better match for the
existing "last"
- Switch previous and next: "previous" was
pointing from first to last, "next" from
last to first. Mind-bending.
- Add a bit to the description. Remove "ticket"
language.
- Use more standard terminology "push" to
insert in front and "pop" to remove from last
- Add methods shift and unshift for the operations
at the other ends. Not used yet.
- Add remove() method (not used yet).
- Rename makeYoungest() to moveFirst() and add
moveLast() (not used yet). This data structure
doesn't actually know about young or old.
Add "Entry-" prefix to Entry.toString().
Rename makeFirst() in JspRuntimeContext to
makeYoungest(), because there we actually are using
timestamp information.
Added:
tomcat/trunk/java/org/apache/jasper/util/FastRemovalDequeue.java
- copied, changed from r1028286,
tomcat/trunk/java/org/apache/jasper/util/JspQueue.java
Removed:
tomcat/trunk/java/org/apache/jasper/util/JspQueue.java
Modified:
tomcat/trunk/java/org/apache/jasper/compiler/JspRuntimeContext.java
tomcat/trunk/java/org/apache/jasper/servlet/JspServletWrapper.java
tomcat/trunk/java/org/apache/jasper/util/Entry.java
Modified: tomcat/trunk/java/org/apache/jasper/compiler/JspRuntimeContext.java
URL:
http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/jasper/compiler/JspRuntimeContext.java?rev=1028377&r1=1028376&r2=1028377&view=diff
==============================================================================
--- tomcat/trunk/java/org/apache/jasper/compiler/JspRuntimeContext.java
(original)
+++ tomcat/trunk/java/org/apache/jasper/compiler/JspRuntimeContext.java Thu Oct
28 16:27:31 2010
@@ -41,7 +41,7 @@ import org.apache.jasper.runtime.JspFact
import org.apache.jasper.security.SecurityClassLoad;
import org.apache.jasper.servlet.JspServletWrapper;
import org.apache.jasper.util.ExceptionUtils;
-import org.apache.jasper.util.JspQueue;
+import org.apache.jasper.util.FastRemovalDequeue;
import org.apache.juli.logging.Log;
import org.apache.juli.logging.LogFactory;
@@ -178,7 +178,7 @@ public final class JspRuntimeContext {
/**
* Keeps JSP pages ordered by last access.
*/
- private JspQueue<JspServletWrapper> jspQueue = new
JspQueue<JspServletWrapper>();
+ private FastRemovalDequeue<JspServletWrapper> jspQueue = new
FastRemovalDequeue<JspServletWrapper>();
// ------------------------------------------------------ Public Methods
@@ -229,9 +229,9 @@ public final class JspRuntimeContext {
*
* @param ticket the ticket for the jsp.
* */
- public void makeFirst(org.apache.jasper.util.Entry<JspServletWrapper>
ticket) {
- synchronized( jspQueue ) {
- jspQueue.makeYoungest(ticket);
+ public void makeYoungest(org.apache.jasper.util.Entry<JspServletWrapper>
ticket) {
+ synchronized(jspQueue) {
+ jspQueue.moveFirst(ticket);
}
}
@@ -505,7 +505,7 @@ public final class JspRuntimeContext {
if( jsps.size() > maxLoadedJsps ) {
synchronized( jsps ) {
JspServletWrapper oldest;
- synchronized( jspQueue) {
+ synchronized(jspQueue) {
oldest = jspQueue.pop();
}
if (oldest != null) {
Modified: tomcat/trunk/java/org/apache/jasper/servlet/JspServletWrapper.java
URL:
http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/jasper/servlet/JspServletWrapper.java?rev=1028377&r1=1028376&r2=1028377&view=diff
==============================================================================
--- tomcat/trunk/java/org/apache/jasper/servlet/JspServletWrapper.java
(original)
+++ tomcat/trunk/java/org/apache/jasper/servlet/JspServletWrapper.java Thu Oct
28 16:27:31 2010
@@ -391,7 +391,7 @@ public class JspServletWrapper {
if (ticket == null)
ticket = ctxt.getRuntimeContext().push(this);
else
- ctxt.getRuntimeContext().makeFirst(ticket);
+ ctxt.getRuntimeContext().makeYoungest(ticket);
}
}
} catch (UnavailableException ex) {
Modified: tomcat/trunk/java/org/apache/jasper/util/Entry.java
URL:
http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/jasper/util/Entry.java?rev=1028377&r1=1028376&r2=1028377&view=diff
==============================================================================
--- tomcat/trunk/java/org/apache/jasper/util/Entry.java (original)
+++ tomcat/trunk/java/org/apache/jasper/util/Entry.java Thu Oct 28 16:27:31 2010
@@ -17,8 +17,8 @@
package org.apache.jasper.util;
/**
- * Implementation of a list entry. It exposes links to previous and next
- * elements on package level only.
+ * Implementation of a doubly linked list entry.
+ * It exposes links to previous and next elements on package level only.
*/
public class Entry<T> {
@@ -55,6 +55,6 @@ public class Entry<T> {
@Override
public String toString() {
- return content.toString();
+ return "Entry-" + content.toString();
}
}
Copied: tomcat/trunk/java/org/apache/jasper/util/FastRemovalDequeue.java (from
r1028286, tomcat/trunk/java/org/apache/jasper/util/JspQueue.java)
URL:
http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/jasper/util/FastRemovalDequeue.java?p2=tomcat/trunk/java/org/apache/jasper/util/FastRemovalDequeue.java&p1=tomcat/trunk/java/org/apache/jasper/util/JspQueue.java&r1=1028286&r2=1028377&rev=1028377&view=diff
==============================================================================
--- tomcat/trunk/java/org/apache/jasper/util/JspQueue.java (original)
+++ tomcat/trunk/java/org/apache/jasper/util/FastRemovalDequeue.java Thu Oct 28
16:27:31 2010
@@ -18,45 +18,73 @@ package org.apache.jasper.util;
/**
*
- * The JspQueue is supposed to hold a set of instances in sorted order. Sorting
- * order is determined by the instances' content. As this content may change
- * during instance lifetime, the Queue must be cheap to update - ideally in
- * constant time.
- *
- * Access to the first element in the queue must happen in constant time.
- *
- * Only a minimal set of operations is implemented.
+ * The FastRemovalDequeue is a Dequeue that supports constant time removal of
+ * entries. This is achieved by using a doubly linked list and wrapping any
object
+ * added to the collection with an Entry type, that is returned to the
consumer.
+ * When removing an object from the list, the consumer provides this Entry
object.
+ *
+ * The Entry type is mostly opaque to the consumer itself. The consumer can
only
+ * retrieve the original object - named content - from the Entry.
+ *
+ * The Entry object contains the links pointing to the neighbours in the doubly
+ * linked list, so that removal of an Entry does not need to search for it but
+ * instead can be done in constant time.
+ *
+ * A typical use of the FastRemovalDequeue is a list of entries in sorted
order,
+ * where the sort position of an object will only switch to first or last.
+ *
+ * Whenever the sort position needs to change, the consumer can remove the
object
+ * and reinsert it in front or at the end in constant time.
+ * So keeping the list sorted is very cheap.
+ *
*/
-public class JspQueue<T> {
+public class FastRemovalDequeue<T> {
- /** Head of the queue. */
- private Entry<T> head;
+ /** First element of the queue. */
+ private Entry<T> first;
/** Last element of the queue. */
private Entry<T> last;
/** Initialize empty queue. */
- public JspQueue() {
- head = null;
+ public FastRemovalDequeue() {
+ first = null;
last = null;
}
/**
- * Adds an object to the end of the queue and returns the entry created for
- * said object. The entry can later be reused for moving the entry back to
- * the front of the list.
- *
- * @param object
- * the object to append to the end of the list.
- * @return a ticket for use when the object should be moved back to the
- * front.
+ * Adds an object to the start of the list and returns the entry created
for
+ * said object. The entry can later be reused for moving the entry.
+ *
+ * @param object the object to prepend to the start of the list.
+ * @return an entry for use when the object should be moved.
* */
public Entry<T> push(final T object) {
Entry<T> entry = new Entry<T>(object);
- if (head == null) {
- head = last = entry;
+ if (first == null) {
+ first = last = entry;
+ } else {
+ first.setPrevious(entry);
+ entry.setNext(first);
+ first = entry;
+ }
+
+ return entry;
+ }
+
+ /**
+ * Adds an object to the end of the list and returns the entry created for
+ * said object. The entry can later be reused for moving the entry.
+ *
+ * @param object the object to append to the end of the list.
+ * @return an entry for use when the object should be moved.
+ * */
+ public Entry<T> unpop(final T object) {
+ Entry<T> entry = new Entry<T>(object);
+ if (first == null) {
+ first = last = entry;
} else {
- last.setPrevious(entry);
- entry.setNext(last);
+ last.setNext(entry);
+ entry.setPrevious(last);
last = entry;
}
@@ -64,40 +92,104 @@ public class JspQueue<T> {
}
/**
- * Removes the head of the queue and returns its content.
+ * Removes the first element of the list and returns its content.
*
- * @return the content of the head of the queue.
+ * @return the content of the first element of the list.
+ **/
+ public T unpush() {
+ T content = null;
+ if (first != null) {
+ content = first.getContent();
+ first = first.getNext();
+ if (first != null) {
+ first.setPrevious(null);
+ }
+ }
+ return content;
+ }
+
+ /**
+ * Removes the last element of the list and returns its content.
+ *
+ * @return the content of the last element of the list.
**/
public T pop() {
T content = null;
- if (head != null) {
- content = head.getContent();
- if (head.getPrevious() != null)
- head.getPrevious().setNext(null);
- head = head.getPrevious();
+ if (last != null) {
+ content = last.getContent();
+ last = last.getPrevious();
+ if (last != null) {
+ last.setNext(null);
+ }
}
return content;
}
/**
- * Moves the candidate to the front of the queue.
+ * Removes any element of the list and returns its content.
+ **/
+ public void remove(final Entry<T> element) {
+ Entry<T> next = element.getNext();
+ Entry<T> prev = element.getPrevious();
+ if (next != null) {
+ next.setPrevious(prev);
+ } else {
+ last = prev;
+ }
+ if (prev != null) {
+ prev.setNext(next);
+ } else {
+ first = next;
+ }
+ }
+
+ /**
+ * Moves the element in front.
+ *
+ * Could also be implemented as remove() and
+ * push(), but explicitely coding might be a bit faster.
+ *
+ * @param element the entry to move in front.
+ * */
+ public void moveFirst(final Entry<T> element) {
+ if (element.getPrevious() != null) {
+ Entry<T> prev = element.getPrevious();
+ Entry<T> next = element.getNext();
+ prev.setNext(next);
+ if (next != null) {
+ next.setPrevious(prev);
+ } else {
+ last = prev;
+ }
+ first.setPrevious(element);
+ element.setNext(first);
+ element.setPrevious(null);
+ first = element;
+ }
+ }
+
+ /**
+ * Moves the element to the back.
+ *
+ * Could also be implemented as remove() and
+ * unpop(), but explicitely coding might be a bit faster.
*
- * @param candidate
- * the entry to move to the front of the queue.
+ * @param element the entry to move to the back.
* */
- public void makeYoungest(final Entry<T> candidate) {
- if (candidate.getPrevious() != null) {
- Entry<T> candidateNext = candidate.getNext();
- Entry<T> candidatePrev = candidate.getPrevious();
- candidatePrev.setNext(candidateNext);
- if (candidateNext != null)
- candidateNext.setPrevious(candidatePrev);
- else
- head = candidatePrev;
- candidate.setNext(last);
- candidate.setPrevious(null);
- last.setPrevious(candidate);
- last = candidate;
+ public void moveLast(final Entry<T> element) {
+ if (element.getNext() != null) {
+ Entry<T> next = element.getNext();
+ Entry<T> prev = element.getPrevious();
+ next.setPrevious(prev);
+ if (prev != null) {
+ prev.setNext(next);
+ } else {
+ first = next;
+ }
+ last.setNext(element);
+ element.setPrevious(last);
+ element.setNext(null);
+ last = element;
}
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@tomcat.apache.org
For additional commands, e-mail: dev-h...@tomcat.apache.org
