ViewVC Help

View File | Revision Log | Show Annotations | Revision Graph | Root Listing

root/i-scream/projects/cms/source/util/uk/org/iscream/cms/util/Queue.java

Comparing projects/cms/source/util/uk/org/iscream/cms/util/Queue.java (file contents):
Revision 1.11 by tdb, Sun Feb 25 23:19:46 2001 UTC vs.
Revision 1.20 by tdb, Mon Mar 26 17:59:47 2001 UTC

#	Line 1 | Line 1
1		//---PACKAGE DECLARATION---
2	<	package uk.ac.ukc.iscream.util;
2	>	package uk.org.iscream.util;
3
4		//---IMPORTS---
5		import java.util.LinkedList;
6		import java.util.NoSuchElementException;
7	<	import uk.ac.ukc.iscream.util.*;
7	>	import java.util.Random;
8	>	import uk.org.iscream.util.*;
9
10		/**
11		* A Queue class designed to operate in a multi-threaded environment, with
#	Line 24 | Line 25 | public class Queue {
25		*/
26		public static final String REVISION = "$Revision$";
27
28	+	/**
29	+	* Pass to constructor to remove a RANDOM item from
30	+	* the Queue upon reaching the maximum limit.
31	+	*/
32	+	public static final int RANDOM = 0;
33	+
34	+	/**
35	+	* Pass to constructor to remove the FIRST item from
36	+	* the Queue upon reaching the maximum limit.
37	+	*/
38	+	public static final int FIRST = 1;
39	+
40	+	/**
41	+	* Pass to constructor to remove the LAST item from
42	+	* the Queue upon reaching the maximum limit.
43	+	*/
44	+	public static final int LAST = 2;
45	+
46	+	/**
47	+	* Pass to constructor to drop the new item upon reaching
48	+	* the maximum Queue limit.
49	+	*/
50	+	public static final int DROP = 3;
51	+
52	+	/**
53	+	* To allow opposite lookups.
54	+	*/
55	+	public static final String[] algorithms = {"RANDOM", "FIRST", "LAST", "DROP"};
56	+
57		//---STATIC METHODS---
58
59		//---CONSTRUCTORS---
60	+
61	+	/**
62	+	* Constructs a new Queue with a maximum size limit on
63	+	* any individual queue. This should be used to stop
64	+	* conditions where the Queue cannot be guaranteed to
65	+	* be emptied as quick as it's filled.
66	+	*
67	+	* An algorithm will be used to remove data when new data
68	+	* arrives. There may be choices of algorithms later on.
69	+	*
70	+	* @param maxSize the upper limit for a queue
71	+	* @param removeAlgorithm the remove algorithm to use upon reaching the maxSize
72	+	*/
73	+	public Queue(int maxSize, int removeAlgorithm) {
74	+	_maxSize = maxSize;
75	+	_removeAlgorithm = removeAlgorithm;
76	+	}
77	+
78	+	/**
79	+	* Constructs a Queue with no maximum size.
80	+	*/
81	+	public Queue() {
82	+	_maxSize = -1;
83	+	}
84
85		//---PUBLIC METHODS---
86
#	Line 40 | Line 94 | public class Queue {
94		for(int i=0; i < _lists.size(); i++) {
95		// skip over any gaps left in the list
96		if(_lists.get(i) != null) {
97	+	// get size before adding to the Queue
98		int s = ((LinkedList) _lists.get(i)).size();
99	<	synchronized(this) {
100	<	// add() does the same thing, but this ensures behaviour
101	<	((LinkedList) _lists.get(i)).addLast(o);
99	>	// check whether we need to remove an item from the current Queue
100	>	if(_maxSize!=-1 && s>=_maxSize && _removeAlgorithm!=DROP) {
101	>	// we need to remove an item
102	>	removeQueueItem((LinkedList) _lists.get(i));
103		}
104	+	// check if we should add (not if Queue full, and using DROP algorithm)
105	+	if(!(s>=_maxSize && _removeAlgorithm==DROP)) {
106	+	// add the next item, ensuring we lock
107	+	synchronized(this) {
108	+	// LinkedList.add() does the same thing, but this ensures behaviour
109	+	((LinkedList) _lists.get(i)).addLast(o);
110	+	}
111	+	}
112		// if the queue was empty before the add it is possible
113		// that a consumer is waiting... so we notify them
114	<	if (s == 0) {
115	<	synchronized(((LinkedList) _lists.get(i))) {
52	<	((LinkedList) _lists.get(i)).notifyAll();
53	<	}
114	>	synchronized(((LinkedList) _lists.get(i))) {
115	>	((LinkedList) _lists.get(i)).notifyAll();
116		}
117		}
118		}
#	Line 72 | Line 134 | public class Queue {
134		throw new InvalidQueueException("Requested queue "+queue+" does not exist");
135		}
136		// block if the queue is empty
137	<	if (((LinkedList) _lists.get(queue)).size() == 0) {
138	<	synchronized(((LinkedList) _lists.get(queue))) {
137	>	synchronized(((LinkedList) _lists.get(queue))) {
138	>	if (((LinkedList) _lists.get(queue)).size() == 0) {
139		try { ((LinkedList) _lists.get(queue)).wait(); } catch(Exception e) {}
140		}
141		}
#	Line 135 | Line 197 | public class Queue {
197		status += "queue"+i+"=\""+((LinkedList) _lists.get(i)).size()+"\" ";
198		}
199		else {
200	<	status += "queue"+i+"=\"\<deleted\>\" ";
200	>	status += "queue"+i+"=\"[deleted]\" ";
201		}
202		}
203	<	status += "total=\""+_count+"\"></queue>";
203	>	status += "total=\""+_count+"\"";
204	>	if(_maxSize != -1) {
205	>	status += " maxSize=\""+_maxSize+"\"";
206	>	}
207	>	status += "></queue>";
208		return status;
209		}
210
#	Line 179 | Line 245 | public class Queue {
245		*
246		* @return An integer to be passed to the get() method.
247		*/
248	<	public int getQueue() {
248	>	public synchronized int getQueue() {
249		int pos = -1;
250		for(int i=0; i < _lists.size(); i++) {
251		if(_lists.get(i) == null) {
#	Line 203 | Line 269 | public class Queue {
269		*
270		* @param queue The integer identifier for the queue, given by getQueue().
271		*/
272	<	public void removeQueue(int queue) {
272	>	public synchronized void removeQueue(int queue) {
273		_lists.set(queue, null);
274		}
275
#	Line 264 | Line 330 | public class Queue {
330		* Overrides the {@link java.lang.Object#toString() Object.toString()}
331		* method to provide clean logging (every class should have this).
332		*
333	<	* This uses the uk.ac.ukc.iscream.util.FormatName class
333	>	* This uses the uk.org.iscream.util.FormatName class
334		* to format the toString()
335		*
336		* @return the name of this class and its CVS revision.
#	Line 277 | Line 343 | public class Queue {
343		}
344
345		//---PRIVATE METHODS---
346	<
346	>
347	>	/**
348	>	* This method removes an item from a Queue, using a method
349	>	* requested at construction.
350	>	*
351	>	* @param list The LinkedList from which to remove an item.
352	>	*/
353	>	private void removeQueueItem(LinkedList list) {
354	>	// look at our algorithm
355	>	// remove a random item from the list
356	>	if(_removeAlgorithm==RANDOM) {
357	>	// new Random, with a good seed
358	>	Random rand = new Random(System.currentTimeMillis());
359	>	int i = rand.nextInt(_maxSize);
360	>	synchronized(this) {
361	>	list.remove(i);
362	>	}
363	>	}
364	>	// remove the first item from the list
365	>	else if(_removeAlgorithm==FIRST) {
366	>	synchronized(this) {
367	>	list.removeFirst();
368	>	}
369	>	}
370	>	// remove the last item from the list
371	>	else if(_removeAlgorithm==LAST) {
372	>	synchronized(this) {
373	>	list.removeLast();
374	>	}
375	>	}
376	>	}
377	>
378		//---ACCESSOR/MUTATOR METHODS---
379
380		//---ATTRIBUTES---
#	Line 297 | Line 394 | public class Queue {
394		* A reference to our QueueMonitor, if we have one.
395		*/
396		private QueueMonitor _queueMon = null;
397	+
398	+	/**
399	+	* The maximum size of any Queue.
400	+	*/
401	+	private int _maxSize = -1;
402	+
403	+	/**
404	+	* The remove algorithm to use upon a Queue reaching
405	+	* it's maximum size.
406	+	*/
407	+	private int _removeAlgorithm = -1;
408
409		/**
410		* This is the friendly identifier of the

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines