deweese 01/08/06 08:35:13 Modified: sources/org/apache/batik/ext/awt/image/rendered LRUCache.java sources/org/apache/batik/util RunnableQueue.java Added: sources/org/apache/batik/util DoublyLinkedList.java test-sources/org/apache/batik/util RunnableQueueTest.java ThreadPounder.java Log: 1) Generic DoublyLinkedList class (used by LRU and now RunnableQueue). 2) Updated version of RunnableQueue. 3) ThreadPounder utility class that tries to get a bunch of threads to start as close to the same time as possible, presumably to 'pound' on a supposedly thread safe interface. 4) RunnableQueueTest start of a test for the RunnableQueue class. Currently this really isn't very good (it takes a lot of 'human' work to make sense of the output....). Revision Changes Path 1.4 +29 -117 xml-batik/sources/org/apache/batik/ext/awt/image/rendered/LRUCache.java Index: LRUCache.java =================================================================== RCS file: /home/cvs/xml-batik/sources/org/apache/batik/ext/awt/image/rendered/LRUCache.java,v retrieving revision 1.3 retrieving revision 1.4 diff -u -r1.3 -r1.4 --- LRUCache.java 2001/07/18 22:04:53 1.3 +++ LRUCache.java 2001/08/06 15:35:13 1.4 @@ -8,7 +8,10 @@ package org.apache.batik.ext.awt.image.rendered; +import org.apache.batik.util.DoublyLinkedList; + public class LRUCache { + /** * Interface for object participating in the LRU Cache. These * inform the object of key events in the status of the object in @@ -37,119 +40,27 @@ * Interface for nodes in the LRU cache, basicly nodes in a doubly * linked list. */ - public class LRUNode { - private LRUNode next = null; - private LRUNode prev = null; - private LRUObj obj = null; - - public LRUNode getNext() { return next; } - public LRUNode getPrev() { return prev; } - public LRUObj getObj() { return obj; } - - protected void setNext(LRUNode newNext) { next = newNext; } - protected void setPrev(LRUNode newPrev) { prev = newPrev; } - protected void setObj (LRUObj newObj) { + public class LRUNode extends DoublyLinkedList.Node { + private LRUObj obj = null; + public LRUObj getObj () { return obj; } + protected void setObj (LRUObj newObj) { if (obj != null) obj.lruRemove(); obj = newObj; if (obj != null) obj.lruSet(this); } - - - protected void unlink() { - // Unlink this node from it's current pos... - if (getNext() != null) - getNext().setPrev(getPrev()); - if (getPrev() != null) - getPrev().setNext(getNext()); - - setNext(null); - setPrev(null); - } - - protected void insertBefore(LRUNode nde) { - // Already here... - if (this == nde) return; - - unlink(); - - // Actually insert this node... - if (nde == null) { - // empty lst... - setNext(this); - setPrev(this); - } else { - setNext(nde); - setPrev(nde.getPrev()); - nde.setPrev(this); - if (getPrev() != null) - getPrev().setNext(this); - } - } - } - - /** - * A simple Doublly Linked list class, designed to avoid - * O(n) behaviour on insert and delete. - */ - public class LRUList { - - private LRUNode head = null; - private int size = 0; - - public LRUList() {} - - public synchronized int getSize() { return size; } - - public synchronized void empty() { - while(size > 0) pop(); - } - - public LRUNode getHead() { return head; } - public LRUNode getTail() { return head.getPrev(); } - - public synchronized void touch(LRUNode nde) { - if (nde == null) return; - nde.insertBefore(head); - head = nde; - } - - public synchronized void add(LRUNode nde) { - touch(nde); - size++; - } - - public synchronized void remove(LRUNode nde) { - if (nde == null) return; - if (nde == head) head = nde.getNext(); - nde.unlink(); - size--; - } - - public synchronized LRUNode pop() { - if (head == null) return null; - - LRUNode nde = head; - - if (head.getNext() == head) head = null; // Last node... - else head = head.getNext(); - - nde.unlink(); - size--; - return nde; - } } - private LRUList free = null; - private LRUList used = null; + private DoublyLinkedList free = null; + private DoublyLinkedList used = null; private int maxSize = 0; public LRUCache(int size) { if (size <= 0) size=1; maxSize = size; - free = new LRUList(); - used = new LRUList(); + free = new DoublyLinkedList(); + used = new DoublyLinkedList(); while (size > 0) { free.add(new LRUNode()); @@ -161,7 +72,7 @@ return used.getSize(); } - public void setSize(int newSz) { + public synchronized void setSize(int newSz) { if (maxSize < newSz) { // list grew... @@ -171,7 +82,7 @@ } else if (maxSize > newSz) { for (int i=used.getSize(); i>newSz; i--) { - LRUNode nde = used.getTail(); + LRUNode nde = (LRUNode)used.getTail(); used.remove(nde); nde.setObj(null); } @@ -180,30 +91,30 @@ maxSize = newSz; } - public void flush() { + public synchronized void flush() { while (used.getSize() > 0) { - LRUNode nde = used.pop(); + LRUNode nde = (LRUNode)used.pop(); nde.setObj(null); free.add(nde); } } - public void remove(LRUObj obj) { - LRUNode nde = obj.lruGet(); + public synchronized void remove(LRUObj obj) { + LRUNode nde = (LRUNode)obj.lruGet(); if (nde == null) return; used.remove(nde); nde.setObj(null); free.add(nde); } - public void touch(LRUObj obj) { - LRUNode nde = obj.lruGet(); + public synchronized void touch(LRUObj obj) { + LRUNode nde = (LRUNode)obj.lruGet(); if (nde == null) return; used.touch(nde); } - public void add(LRUObj obj) { - LRUNode nde = obj.lruGet(); + public synchronized void add(LRUObj obj) { + LRUNode nde = (LRUNode)obj.lruGet(); // already linked in... if (nde != null) { @@ -212,24 +123,25 @@ } if (free.getSize() > 0) { - nde = free.pop(); + nde = (LRUNode)free.pop(); nde.setObj(obj); used.add(nde); } else { - nde = used.getTail(); + nde = (LRUNode)used.getTail(); nde.setObj(obj); used.touch(nde); } } - protected void print() { + protected synchronized void print() { System.out.println("In Use: " + used.getSize() + " Free: " + free.getSize()); - LRUNode cur = used.getHead(); + LRUNode nde = (LRUNode)used.getHead(); + if (nde == null) return; do { - System.out.println(cur.getObj()); - cur = cur.getNext(); - } while (cur != used.getHead()); + System.out.println(nde.getObj()); + nde = (LRUNode)nde.getNext(); + } while (nde != used.getHead()); } } 1.3 +90 -129 xml-batik/sources/org/apache/batik/util/RunnableQueue.java Index: RunnableQueue.java =================================================================== RCS file: /home/cvs/xml-batik/sources/org/apache/batik/util/RunnableQueue.java,v retrieving revision 1.2 retrieving revision 1.3 diff -u -r1.2 -r1.3 --- RunnableQueue.java 2001/08/06 12:33:35 1.2 +++ RunnableQueue.java 2001/08/06 15:35:13 1.3 @@ -16,36 +16,21 @@ * invocation in a single thread. * * @author <a href="mailto:[EMAIL PROTECTED]">Stephane Hillion</a> - * @version $Id: RunnableQueue.java,v 1.2 2001/08/06 12:33:35 hillion Exp $ + * @version $Id: RunnableQueue.java,v 1.3 2001/08/06 15:35:13 deweese Exp $ */ public class RunnableQueue implements Runnable { /** - * The lock used to wait for Runnable objects to be available. - */ - protected Object invocationLock = new Object(); - - /** - * The lock used to suspend the queue execution. - */ - protected Object suspendLock = new Object(); - - /** * whether this thread is suspended. */ protected boolean suspended; /** - * The Runnable objects list's head. + * The Runnable objects list. */ - protected Link head; + protected DoublyLinkedList list = new DoublyLinkedList(); /** - * The Runnable objects list's tail. - */ - protected Link tail; - - /** * The object which handle run events. */ protected RunHandler runHandler; @@ -53,7 +38,7 @@ /** * The current thread. */ - protected volatile Thread runnableQueueThread; + protected Thread runnableQueueThread; /** * Creates a new RunnableQueue started in a new thread. @@ -62,9 +47,14 @@ */ public static RunnableQueue createRunnableQueue() { RunnableQueue result = new RunnableQueue(); - new Thread(result).start(); - while (result.getThread() == null) { - Thread.yield(); + synchronized (result) { + new Thread(result).start(); + while (result.getThread() == null) { + try { + result.wait(); + } catch (InterruptedException ie) { + } + } } return result; } @@ -73,48 +63,47 @@ * Runs this queue. */ public void run() { - runnableQueueThread = Thread.currentThread(); + synchronized (this) { + runnableQueueThread = Thread.currentThread(); + notify(); + } + Link l; + Runnable rable; try { while (!Thread.currentThread().isInterrupted()) { - if (suspended) { - if (runHandler != null) { - runHandler.executionSuspended(this); - } - synchronized (suspendLock) { + synchronized (this) { + if (suspended) { + if (runHandler != null) { + runHandler.executionSuspended(this); + } while (suspended) { - suspendLock.wait(); + wait(); } - } - if (runHandler != null) { - runHandler.executionResumed(this); + if (runHandler != null) { + runHandler.executionResumed(this); + } } - } - if (head == null) { - synchronized (invocationLock) { - invocationLock.wait(); + + l = (Link)list.pop(); + if (l == null) { + wait(); + continue; // start loop over again... } + rable = l.runnable; } - Link l = head; + rable.run(); + l.unlock(); synchronized (this) { - head = head.next; - } - l.runnable.run(); - if (l.isLock()) { - LockedLink ll = (LockedLink)l; - synchronized (l) { - while (!ll.isLocked()) { - l.wait(); - } - l.notify(); + if (runHandler != null) { + runHandler.runnableInvoked(this, rable); } } - if (runHandler != null) { - runHandler.runnableInvoked(this, l.runnable); - } } } catch (InterruptedException e) { } finally { - runnableQueueThread = null; + synchronized (this) { + runnableQueueThread = null; + } } } @@ -134,18 +123,11 @@ */ public synchronized void invokeLater(Runnable r) { if (runnableQueueThread == null) { - throw new IllegalStateException("RunnableQueue not started"); - } - - if (head == null) { - head = tail = new UnlockedLink(r); - synchronized (invocationLock) { - invocationLock.notify(); - } - } else { - tail.next = new UnlockedLink(r); - tail = tail.next; + throw new IllegalStateException + ("RunnableQueue not started or has exited"); } + list.push(new Link(r)); + notify(); } /** @@ -158,39 +140,34 @@ */ public void invokeAndWait(Runnable r) throws InterruptedException { if (runnableQueueThread == null) { - throw new IllegalStateException("RunnableQueue not started"); + throw new IllegalStateException + ("RunnableQueue not started or has exited"); } if (runnableQueueThread == Thread.currentThread()) { throw new IllegalStateException ("Cannot be called from the RunnableQueue thread"); } - LockedLink l; + LockableLink l = new LockableLink(r); synchronized (this) { - if (head == null) { - l = new LockedLink(r); - head = tail = l; - synchronized (invocationLock) { - invocationLock.notify(); - } - } else { - l = new LockedLink(r); - tail.next = l; - tail = tail.next; - } + list.push(l); + notify(); } l.lock(); } + public synchronized boolean isSuspended() { return suspended; } + /** * Suspends the execution of this queue. * @throws IllegalStateException if getThread() is null. */ - public void suspendExecution() { + public synchronized void suspendExecution() { if (runnableQueueThread == null) { - throw new IllegalStateException("RunnableQueue not started"); + throw new IllegalStateException + ("RunnableQueue not started or has exited"); } - + suspended = true; } @@ -198,16 +175,15 @@ * Resumes the execution of this queue. * @throws IllegalStateException if getThread() is null. */ - public void resumeExecution() { + public synchronized void resumeExecution() { if (runnableQueueThread == null) { - throw new IllegalStateException("RunnableQueue not started"); + throw new IllegalStateException + ("RunnableQueue not started or has exited"); } - synchronized (suspendLock) { - if (suspended) { - suspended = false; - suspendLock.notify(); - } + if (suspended) { + suspended = false; + notify(); } } @@ -220,29 +196,33 @@ */ public synchronized List getRunnableList() { if (runnableQueueThread == null) { - throw new IllegalStateException("RunnableQueue not started"); + throw new IllegalStateException + ("RunnableQueue not started or has exited"); } List result = new LinkedList(); - Link l = head; - while (l != null) { + Link l, h; + l = h = (Link)list.getHead(); + if (h==null) return result; + do { result.add(l.runnable); - l = l.next; - } + l = (Link)l.getNext(); + } while (l != h); + return result; } /** * Sets the RunHandler for this queue. */ - public void setRunHandler(RunHandler rh) { + public synchronized void setRunHandler(RunHandler rh) { runHandler = rh; } /** * Returns the RunHandler or null. */ - public RunHandler getRunHandler() { + public synchronized RunHandler getRunHandler() { return runHandler; } @@ -272,7 +252,7 @@ /** * To store a Runnable. */ - protected abstract static class Link { + protected static class Link extends DoublyLinkedList.Node { /** * The Runnable. @@ -280,47 +260,23 @@ public Runnable runnable; /** - * The next link. - */ - public Link next; - - /** * Creates a new link. */ public Link(Runnable r) { runnable = r; } - /** - * Whether the link is a lock. - */ - public abstract boolean isLock(); - } - - /** - * To store a Runnable to invoke later. - */ - protected static class UnlockedLink extends Link { - - /** - * Creates a new link. - */ - public UnlockedLink(Runnable r) { - super(r); - } - /** - * Whether the link is a lock. + * unlock link and notify locker. + * Basic implementation does nothing. */ - public boolean isLock() { - return false; - } + public void unlock() throws InterruptedException { return; } } /** * To store a Runnable with an object waiting for him to be executed. */ - protected static class LockedLink extends Link { + protected static class LockableLink extends Link { /** * Whether this link is actually locked. @@ -330,18 +286,11 @@ /** * Creates a new link. */ - public LockedLink(Runnable r) { + public LockableLink(Runnable r) { super(r); } /** - * Whether the link is a lock. - */ - public boolean isLock() { - return true; - } - - /** * Whether the link is actually locked. */ public boolean isLocked() { @@ -355,6 +304,18 @@ locked = true; notify(); wait(); + } + + /** + * unlocks this link. + */ + public synchronized void unlock() throws InterruptedException { + while (!locked) { + // Wait until lock is called... + wait(); + } + // Wake the locking thread... + notify(); } } } 1.1 xml-batik/sources/org/apache/batik/util/DoublyLinkedList.java Index: DoublyLinkedList.java =================================================================== /***************************************************************************** * Copyright (C) The Apache Software Foundation. All rights reserved. * * ------------------------------------------------------------------------- * * This software is published under the terms of the Apache Software License * * version 1.1, a copy of which has been included with this distribution in * * the LICENSE file. * *****************************************************************************/ package org.apache.batik.util; /** * A simple Doubly Linked list class, designed to avoid * O(n) behaviour on insert and delete. */ public class DoublyLinkedList { /** * Basic doubly linked list node interface. */ public static class Node { private Node next = null; private Node prev = null; public final Node getNext() { return next; } public final Node getPrev() { return prev; } protected final void setNext(Node newNext) { next = newNext; } protected final void setPrev(Node newPrev) { prev = newPrev; } /** * Unlink this node from it's current list... */ protected final void unlink() { if (getNext() != null) getNext().setPrev(getPrev()); if (getPrev() != null) getPrev().setNext(getNext()); setNext(null); setPrev(null); } /** * Link this node in, infront of nde (unlinks it's self * before hand if needed). * @param nde the node to link in before. */ protected final void insertBefore(Node nde) { // Already here... if (this == nde) return; if (getPrev() != null) unlink(); // Actually insert this node... if (nde == null) { // empty lst... setNext(this); setPrev(this); } else { setNext(nde); setPrev(nde.getPrev()); nde.setPrev(this); if (getPrev() != null) getPrev().setNext(this); } } } private Node head = null; private int size = 0; public DoublyLinkedList() {} /** * Returns the number of elements currently in the list. */ public synchronized int getSize() { return size; } /** * Removes all elements from the list. */ public synchronized void empty() { while(size > 0) pop(); } /** * Get the current head element * @return The current 'first' element in list. */ public Node getHead() { return head; } /** * Get the current tail element * @return The current 'last' element in list. */ public Node getTail() { return head.getPrev(); } /** * Moves <tt>nde</tt> to the head of the list (equivilent to * remove(nde); add(nde); but faster. */ public void touch(Node nde) { if (nde == null) return; nde.insertBefore(head); head = nde; } /** * Adds <tt>nde</tt> to the head of the list. * In perl this is called an 'unpop'. <tt>nde</tt> should * not currently be part of any list. * @param nde the node to add to the list. */ public void add(Node nde) { if (nde == null) return; nde.insertBefore(head); head = nde; size++; } /** * Removes nde from the list it is part of (should be this * one, otherwise results are undefined). If nde is the * current head element, then the next element becomes head, * if there are no more elements the list becomes empty. * @param nde node to remove. */ public void remove(Node nde) { if (nde == null) return; if (nde == head) { if (head.getNext() == head) head = null; // Last node... else head = head.getNext(); } nde.unlink(); size--; } /** * Removes 'head' from list and returns it. Returns null if list is empty. * @returns current head element, next element becomes head. */ public Node pop() { if (head == null) return null; Node nde = head; remove(head); return nde; } /** * Adds <tt>nde</tt> to tail of list */ public void push(Node nde) { nde.insertBefore(head); if (head == null) head = nde; size++; } } 1.1 xml-batik/test-sources/org/apache/batik/util/RunnableQueueTest.java Index: RunnableQueueTest.java =================================================================== /***************************************************************************** * Copyright (C) The Apache Software Foundation. All rights reserved. * * ------------------------------------------------------------------------- * * This software is published under the terms of the Apache Software License * * version 1.1, a copy of which has been included with this distribution in * * the LICENSE file. * *****************************************************************************/ package org.apache.batik.util; import org.apache.batik.test.AbstractTest; import org.apache.batik.test.DefaultTestReport; import org.apache.batik.test.TestReport; import java.util.List; import java.util.ArrayList; import java.util.Random; public class RunnableQueueTest extends AbstractTest { public int nThreads; public int activeThreads; /** * Constructor * @param nThreads number of runnables to queue * @param sync Should requests be made synchronously (from * different threads). */ public RunnableQueueTest(int nThreads, boolean sync) { this.nThreads = nThreads; } /** * Returns this Test's name */ public String getName() { return "RunnableQueue Stress Test"; } /** * This method will only throw exceptions if some aspect * of the test's internal operation fails. */ public TestReport runImpl() throws Exception { RunnableQueue rq = RunnableQueue.createRunnableQueue(); List l = new ArrayList(nThreads); Random rand = new Random(2345); for (int i=0; i<nThreads; i++) { Runnable rqRable = new RQRable(i, rand.nextInt(50)); l.add(new TPRable(rq, i, rand.nextBoolean(), rand.nextInt(1000), 20, rqRable)); } synchronized (this) { ThreadPounder tp = new ThreadPounder(l); tp.start(); activeThreads = nThreads; while (activeThreads != 0) { rq.suspendExecution(); System.out.println("Suspended"); wait(rand.nextInt(100)); if (activeThreads == 0) break; System.out.println("Resuming"); rq.resumeExecution(); wait(rand.nextInt(500)); } } System.exit(0); return null; } public class TPRable implements Runnable { RunnableQueue rq; int idx; boolean invokeAndWait; long repeatDelay; int count; Runnable rqRable; TPRable(RunnableQueue rq, int idx, boolean invokeAndWait, long repeatDelay, int count, Runnable rqRable) { this.rq = rq; this.idx = idx; this.invokeAndWait = invokeAndWait; this.repeatDelay = repeatDelay; this.count = count; this.rqRable = rqRable; } public void run() { try { while (count-- != 0) { if (invokeAndWait) { System.out.println(" InvW #" + idx); rq.invokeAndWait(rqRable); System.out.println("Done InvW #" + idx); } else { synchronized (rqRable) { System.out.println(" InvL #" + idx); rq.invokeLater(rqRable); System.out.println("Done InvL #" + idx); rqRable.wait(); } } if (repeatDelay < 0) break; Thread.sleep(repeatDelay); } } catch (InterruptedException ie) { } synchronized(RunnableQueueTest.this) { activeThreads--; RunnableQueueTest.this.notify(); } } } public static class RQRable implements Runnable { int idx; long dur; RQRable(int idx, long dur) { this.idx = idx; this.dur = dur; } public void run() { try { System.out.println(" B Rable #" + idx); Thread.sleep(dur); System.out.println(" E Rable #" + idx); synchronized (this) { notify(); } } catch (InterruptedException ie) { } } } public static void main(String []args) { RunnableQueueTest rqt = new RunnableQueueTest(20, false); try { rqt.runImpl(); } catch (Exception e) { e.printStackTrace(); } } } 1.1 xml-batik/test-sources/org/apache/batik/util/ThreadPounder.java Index: ThreadPounder.java =================================================================== /***************************************************************************** * Copyright (C) The Apache Software Foundation. All rights reserved. * * ------------------------------------------------------------------------- * * This software is published under the terms of the Apache Software License * * version 1.1, a copy of which has been included with this distribution in * * the LICENSE file. * *****************************************************************************/ package org.apache.batik.util; import java.util.ArrayList; import java.util.List; import java.util.Iterator; import java.util.Collections; import java.util.Random; /** * The purpose of this class is to invoke a series of runnables as * closely to synchronously as possible. It does this by starting * a thread for each one, getting the threads into there run method, * then quickly running through (in random order) and notifying each * thread. */ public class ThreadPounder { List runnables; Object [] threads; Object lock = new Object(); public ThreadPounder(List runnables) throws InterruptedException { this(runnables, new Random(1234)); } public ThreadPounder(List runnables, Random rand) throws InterruptedException { this.runnables = new ArrayList(runnables); Collections.shuffle(this.runnables, rand); threads = new Object[this.runnables.size()]; int i=0; Iterator iter= this.runnables.iterator(); synchronized (lock) { while (iter.hasNext()) { Thread t = new SyncThread((Runnable)iter.next()); t.start(); lock.wait(); threads[i] = t; i++; } } } public void start() { synchronized(this) { this.notifyAll(); } } class SyncThread extends Thread { Runnable toRun; public long runTime; public SyncThread(Runnable toRun) { this.toRun = toRun; } public void run() { try { synchronized (ThreadPounder.this) { synchronized (lock) { // Let pounder know I'm ready to go lock.notify(); } // Wait for pounder to wake me up. ThreadPounder.this.wait(); } toRun.run(); } catch (InterruptedException ie) { } } } public static void main(String [] str) { List l = new ArrayList(20); for (int i=0; i<20; i++) { final int x = i; l.add(new Runnable() { public void run() { System.out.println("Thread " + x); } }); } try { ThreadPounder tp = new ThreadPounder(l); System.out.println("Starting:" ); tp.start(); System.out.println("All Started:" ); } catch (InterruptedException ie) { ie.printStackTrace(); } } } --------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]