|
122
|
1 /*******************************************************************************
|
|
|
2 * Copyright (c) 2003, 2006 IBM Corporation and others.
|
|
|
3 * All rights reserved. This program and the accompanying materials
|
|
|
4 * are made available under the terms of the Eclipse Public License v1.0
|
|
|
5 * which accompanies this distribution, and is available at
|
|
|
6 * http://www.eclipse.org/legal/epl-v10.html
|
|
|
7 *
|
|
|
8 * Contributors:
|
|
|
9 * IBM - Initial API and implementation
|
|
|
10 * Port to the D programming language:
|
|
|
11 * Frank Benoit <benoit@tionex.de>
|
|
|
12 *******************************************************************************/
|
|
|
13 module dwtx.core.internal.jobs.JobQueue;
|
|
|
14
|
|
|
15 import dwt.dwthelper.utils;
|
|
|
16
|
|
|
17 import dwtx.core.runtime.Assert;
|
|
|
18 import dwtx.core.runtime.IProgressMonitor;
|
|
|
19 import dwtx.core.runtime.IStatus;
|
|
|
20 import dwtx.core.runtime.Status;
|
|
|
21
|
|
|
22 import dwtx.core.internal.jobs.InternalJob;
|
|
|
23
|
|
|
24 /**
|
|
|
25 * A linked list based priority queue. Either the elements in the queue must
|
|
|
26 * implement Comparable, or a Comparator must be provided.
|
|
|
27 */
|
|
|
28 public class JobQueue {
|
|
|
29 /**
|
|
|
30 * The dummy entry sits between the head and the tail of the queue.
|
|
|
31 * dummy.previous() is the head, and dummy.next() is the tail.
|
|
|
32 */
|
|
|
33 private final InternalJob dummy;
|
|
|
34
|
|
|
35 /**
|
|
|
36 * If true, conflicting jobs will be allowed to overtake others in the
|
|
|
37 * queue that have lower priority. If false, higher priority jumps can only
|
|
|
38 * move up the queue by overtaking jobs that they don't conflict with.
|
|
|
39 */
|
|
|
40 private bool allowConflictOvertaking;
|
|
|
41
|
|
|
42 /**
|
|
|
43 * Create a new job queue.
|
|
|
44 */
|
|
|
45 public this(bool allowConflictOvertaking) {
|
|
|
46 //compareTo on dummy is never called
|
|
|
47 dummy = new class("Queue-Head") InternalJob {//$NON-NLS-1$
|
|
|
48 this( String name ){
|
|
|
49 super(name);
|
|
|
50 }
|
|
|
51 public IStatus run(IProgressMonitor m) {
|
|
|
52 return Status.OK_STATUS;
|
|
|
53 }
|
|
|
54 };
|
|
|
55 dummy.setNext(dummy);
|
|
|
56 dummy.setPrevious(dummy);
|
|
|
57 this.allowConflictOvertaking = allowConflictOvertaking;
|
|
|
58 }
|
|
|
59
|
|
|
60 /**
|
|
|
61 * remove all elements
|
|
|
62 */
|
|
|
63 public void clear() {
|
|
|
64 dummy.setNext(dummy);
|
|
|
65 dummy.setPrevious(dummy);
|
|
|
66 }
|
|
|
67
|
|
|
68 /**
|
|
|
69 * Return and remove the element with highest priority, or null if empty.
|
|
|
70 */
|
|
|
71 public InternalJob dequeue() {
|
|
|
72 InternalJob toRemove = dummy.previous();
|
|
|
73 if (toRemove is dummy)
|
|
|
74 return null;
|
|
|
75 return toRemove.remove();
|
|
|
76 }
|
|
|
77
|
|
|
78 /**
|
|
|
79 * Adds an item to the queue
|
|
|
80 */
|
|
|
81 public void enqueue(InternalJob newEntry) {
|
|
|
82 //assert new entry is does not already belong to some other data structure
|
|
|
83 Assert.isTrue(newEntry.next() is null);
|
|
|
84 Assert.isTrue(newEntry.previous() is null);
|
|
|
85 InternalJob tail = dummy.next();
|
|
|
86 //overtake lower priority jobs. Only overtake conflicting jobs if allowed to
|
|
|
87 while (canOvertake(newEntry, tail))
|
|
|
88 tail = tail.next();
|
|
|
89 //new entry is smaller than tail
|
|
|
90 final InternalJob tailPrevious = tail.previous();
|
|
|
91 newEntry.setNext(tail);
|
|
|
92 newEntry.setPrevious(tailPrevious);
|
|
|
93 tailPrevious.setNext(newEntry);
|
|
|
94 tail.setPrevious(newEntry);
|
|
|
95 }
|
|
|
96
|
|
|
97 /**
|
|
|
98 * Returns whether the new entry to overtake the existing queue entry.
|
|
|
99 * @param newEntry The entry to be added to the queue
|
|
|
100 * @param queueEntry The existing queue entry
|
|
|
101 */
|
|
|
102 private bool canOvertake(InternalJob newEntry, InternalJob queueEntry) {
|
|
|
103 //can never go past the end of the queue
|
|
|
104 if (queueEntry is dummy)
|
|
|
105 return false;
|
|
|
106 //if the new entry was already in the wait queue, ensure it is re-inserted in correct position (bug 211799)
|
|
|
107 if (newEntry.getWaitQueueStamp() > 0 && newEntry.getWaitQueueStamp() < queueEntry.getWaitQueueStamp())
|
|
|
108 return true;
|
|
|
109 //if the new entry has lower priority, there is no need to overtake the existing entry
|
|
|
110 if (queueEntry.compareTo(newEntry) >= 0)
|
|
|
111 return false;
|
|
|
112 //the new entry has higher priority, but only overtake the existing entry if the queue allows it
|
|
|
113 return allowConflictOvertaking || !newEntry.isConflicting(queueEntry);
|
|
|
114 }
|
|
|
115
|
|
|
116 /**
|
|
|
117 * Removes the given element from the queue.
|
|
|
118 */
|
|
|
119 public void remove(InternalJob toRemove) {
|
|
|
120 toRemove.remove();
|
|
|
121 //previous of toRemove might now bubble up
|
|
|
122 }
|
|
|
123
|
|
|
124 /**
|
|
|
125 * The given object has changed priority. Reshuffle the heap until it is
|
|
|
126 * valid.
|
|
|
127 */
|
|
|
128 public void resort(InternalJob entry) {
|
|
|
129 remove(entry);
|
|
|
130 enqueue(entry);
|
|
|
131 }
|
|
|
132
|
|
|
133 /**
|
|
|
134 * Returns true if the queue is empty, and false otherwise.
|
|
|
135 */
|
|
|
136 public bool isEmpty() {
|
|
|
137 return dummy.next() is dummy;
|
|
|
138 }
|
|
|
139
|
|
|
140 /**
|
|
|
141 * Return greatest element without removing it, or null if empty
|
|
|
142 */
|
|
|
143 public InternalJob peek() {
|
|
|
144 return dummy.previous() is dummy ? null : dummy.previous();
|
|
|
145 }
|
|
|
146 }
|
