[f-spot/mipmapped-loading: 3/12] Add task priorities, with priority inheritance for continuations.

[Ruben Vermeersch <rubenv src gnome org>]

commit 1c7761e2bf37b58a89dc6a7191570abdc08b8776
Author: Ruben Vermeersch <ruben savanne be>
Date:   Sun Jun 20 14:17:33 2010 +0200

    Add task priorities, with priority inheritance for continuations.

 src/Makefile.am                      |    1 +
 src/Tasks/QueuedTask.cs              |    5 +
 src/Tasks/Task.cs                    |   48 +++++++-
 src/Tasks/Tests/TaskPriorityTests.cs |  243 ++++++++++++++++++++++++++++++++++
 4 files changed, 296 insertions(+), 1 deletions(-)
---
diff --git a/src/Makefile.am b/src/Makefile.am
index 685899e..9448e7d 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -131,6 +131,7 @@ SOURCES = \
 	Tasks/Task.cs \
 	Tasks/QueuedTask.cs \
 	Tasks/Tests/TaskTests.cs \
+	Tasks/Tests/TaskPriorityTests.cs \
 	ThumbnailCache.cs \
 	ThumbnailGenerator.cs \
 	Term.cs \
diff --git a/src/Tasks/QueuedTask.cs b/src/Tasks/QueuedTask.cs
index 056f062..eb953b8 100644
--- a/src/Tasks/QueuedTask.cs
+++ b/src/Tasks/QueuedTask.cs
@@ -103,6 +103,11 @@ namespace FSpot.Tasks
 			QueueTaskScheduler.Instance.Unschedule (this);
 		}
 
+		protected override void InnerReschedule ()
+		{
+			// NOOP, not supported for this scheduler
+		}
+
 		protected override T InnerExecute () {
 			return handler ();
 		}
diff --git a/src/Tasks/Task.cs b/src/Tasks/Task.cs
index 428f022..efb2eae 100644
--- a/src/Tasks/Task.cs
+++ b/src/Tasks/Task.cs
@@ -1,4 +1,5 @@
 using System;
+using System.Linq;
 using System.Threading;
 using System.Collections.Generic;
 
@@ -8,6 +9,8 @@ namespace FSpot.Tasks
 		void Start ();
 		void Cancel ();
 		void Execute ();
+
+		TaskPriority Priority { get; }
 	}
 
 	interface IChildrenHandling
@@ -19,6 +22,7 @@ namespace FSpot.Tasks
 	{
 		void Schedule ();
 		void Unschedule ();
+		void Reschedule ();
 	}
 
 	public enum TaskState
@@ -30,6 +34,13 @@ namespace FSpot.Tasks
 		Exception
 	}
 
+	public enum TaskPriority
+	{
+		Background,
+		Normal,
+		Interactive
+	}
+
 	public abstract class Task<T> : Task, ISchedulable, IChildrenHandling
 	{
 		public bool CancelWithChildren { get; set; }
@@ -54,6 +65,18 @@ namespace FSpot.Tasks
 			}
 		}
 
+		TaskPriority own_priority = TaskPriority.Normal;
+		TaskPriority run_at_priority = TaskPriority.Normal;
+		public TaskPriority Priority {
+			get {
+				return run_at_priority;
+			}
+			set {
+				own_priority = value;
+				RecalculateChildPriorities ();
+			}
+		}
+
 		private EventWaitHandle WaitEvent { get; set; }
 
 		public Task ()
@@ -62,6 +85,7 @@ namespace FSpot.Tasks
 			Children = new List<Task> ();
 			WaitEvent = new ManualResetEvent (false);
 			State = TaskState.Pending;
+			Priority = TaskPriority.Normal;
 		}
 
 		public void Start ()
@@ -91,6 +115,7 @@ namespace FSpot.Tasks
 				} else {
 					task.Parent = this;
 					Children.Add (task);
+					RecalculateChildPriorities ();
 					if (autostart) {
 						var to_start = Parent ?? this;
 						to_start.Start ();
@@ -103,11 +128,26 @@ namespace FSpot.Tasks
 		{
 			lock (Children) {
 				Children.Remove (task);
+				RecalculateChildPriorities ();
 				if (Children.Count == 0 && CancelWithChildren)
 					Cancel ();
 			}
 		}
 
+		void RecalculateChildPriorities ()
+		{
+			TaskPriority previous = run_at_priority;
+			if (Children.Count == 0) {
+				run_at_priority = own_priority;
+			} else {
+				run_at_priority = Children.Max (child => child.Priority);
+			}
+
+			if (previous != run_at_priority && State == TaskState.Scheduled) {
+				(this as ISchedulable).Reschedule ();
+			}
+		}
+
 		public void Cancel ()
 		{
 			State = TaskState.Cancelled;
@@ -130,7 +170,7 @@ namespace FSpot.Tasks
 			if (State != TaskState.Scheduled && State != TaskState.Cancelled)
 				throw new Exception ("Can't start task manually!");
 
-			if (State == TaskState.Cancelled)
+			if (State == TaskState.Cancelled || State == TaskState.Completed)
 				return;
 
 			try {
@@ -169,8 +209,14 @@ namespace FSpot.Tasks
 			InnerUnschedule ();
 		}
 
+		void ISchedulable.Reschedule ()
+		{
+			InnerReschedule ();
+		}
+
 		protected abstract void InnerSchedule ();
 		protected abstract void InnerUnschedule ();
+		protected abstract void InnerReschedule ();
 
 #endregion
 
diff --git a/src/Tasks/Tests/TaskPriorityTests.cs b/src/Tasks/Tests/TaskPriorityTests.cs
new file mode 100644
index 0000000..86484cf
--- /dev/null
+++ b/src/Tasks/Tests/TaskPriorityTests.cs
@@ -0,0 +1,243 @@
+#if ENABLE_TESTS
+using NUnit.Framework;
+using System;
+using System.Threading;
+using System.Collections.Generic;
+using Hyena;
+using Hyena.Collections;
+using FSpot;
+
+namespace FSpot.Tasks.Tests
+{
+	[TestFixture]
+	public class TaskPriorityTests
+	{
+		[SetUp]
+		public void Initialize () {
+			Hyena.Log.Debugging = true;
+		}
+
+		[Test]
+		public void TestDefaultPriority () {
+			var scheduler = new StaticScheduler ();
+			var task = new StaticTask (scheduler);
+
+			// Task is initially unscheduled
+			Assert.AreEqual (TaskPriority.Normal, task.Priority);
+			Assert.AreEqual (TaskState.Pending, task.State);
+			Assert.AreEqual (new Task [] {}, scheduler.Tasks);
+
+			// Sent to scheduler when started
+			task.Start ();
+			Assert.AreEqual (TaskPriority.Normal, task.Priority);
+			Assert.AreEqual (TaskState.Scheduled, task.State);
+			Assert.AreEqual (new Task [] { task }, scheduler.Tasks);
+		}
+
+		[Test]
+		public void TestCancel () {
+			var scheduler = new StaticScheduler ();
+			var task = new StaticTask (scheduler);
+
+			// Task is initially unscheduled
+			Assert.AreEqual (new Task [] {}, scheduler.Tasks);
+
+			// Sent to scheduler when started
+			task.Start ();
+			Assert.AreEqual (TaskState.Scheduled, task.State);
+			Assert.AreEqual (new Task [] { task }, scheduler.Tasks);
+
+			// Removed from scheduler when cancelled
+			task.Cancel ();
+			Assert.AreEqual (TaskState.Cancelled, task.State);
+			Assert.AreEqual (new Task [] { }, scheduler.Tasks);
+		}
+
+		[Test]
+		public void TestOrdering () {
+			var scheduler = new StaticScheduler ();
+			var task1 = new StaticTask (scheduler);
+			var task2 = new StaticTask (scheduler) {
+				Priority = TaskPriority.Interactive
+			};
+
+			// Initially unscheduled
+			Assert.AreEqual (TaskPriority.Normal, task1.Priority);
+			Assert.AreEqual (TaskState.Pending, task1.State);
+			Assert.AreEqual (TaskPriority.Interactive, task2.Priority);
+			Assert.AreEqual (TaskState.Pending, task2.State);
+			Assert.AreEqual (new Task [] {}, scheduler.Tasks);
+
+			// Sent to scheduler when started
+			task1.Start ();
+			Assert.AreEqual (TaskPriority.Normal, task1.Priority);
+			Assert.AreEqual (TaskState.Scheduled, task1.State);
+			Assert.AreEqual (TaskPriority.Interactive, task2.Priority);
+			Assert.AreEqual (TaskState.Pending, task2.State);
+			Assert.AreEqual (new Task [] { task1 }, scheduler.Tasks);
+
+			// High priority task gets sent to the front of the queue
+			task2.Start ();
+			Assert.AreEqual (TaskPriority.Normal, task1.Priority);
+			Assert.AreEqual (TaskState.Scheduled, task1.State);
+			Assert.AreEqual (TaskPriority.Interactive, task2.Priority);
+			Assert.AreEqual (TaskState.Scheduled, task2.State);
+			Assert.AreEqual (task2, scheduler.heap.Peek ());
+			Assert.AreEqual (new Task [] { task2, task1 }, scheduler.Tasks);
+		}
+
+		[Test]
+		public void TestFIFOOrdering () {
+			var scheduler = new StaticScheduler ();
+			var task1 = new StaticTask (scheduler);
+			var task2 = new StaticTask (scheduler);
+
+			// Initially unscheduled
+			Assert.AreEqual (TaskPriority.Normal, task1.Priority);
+			Assert.AreEqual (TaskState.Pending, task1.State);
+			Assert.AreEqual (TaskPriority.Normal, task2.Priority);
+			Assert.AreEqual (TaskState.Pending, task2.State);
+			Assert.AreEqual (new Task [] {}, scheduler.Tasks);
+
+			// Sent to scheduler when started
+			task1.Start ();
+			Assert.AreEqual (TaskPriority.Normal, task1.Priority);
+			Assert.AreEqual (TaskState.Scheduled, task1.State);
+			Assert.AreEqual (TaskPriority.Normal, task2.Priority);
+			Assert.AreEqual (TaskState.Pending, task2.State);
+			Assert.AreEqual (new Task [] { task1 }, scheduler.Tasks);
+
+			// Equal priority tasks get scheduled FIFO
+			task2.Start ();
+			Assert.AreEqual (TaskPriority.Normal, task1.Priority);
+			Assert.AreEqual (TaskState.Scheduled, task1.State);
+			Assert.AreEqual (TaskPriority.Normal, task2.Priority);
+			Assert.AreEqual (TaskState.Scheduled, task2.State);
+			Assert.AreEqual (task1, scheduler.heap.Peek ());
+			Assert.AreEqual (new Task [] { task1, task2 }, scheduler.Tasks);
+		}
+
+		[Test]
+		public void TestPriorityInheritance () {
+			var scheduler = new StaticScheduler ();
+			var task1 = new StaticTask (scheduler);
+			var task2 = new StaticTask (scheduler);
+			var task3 = new StaticTask (scheduler) {
+				Priority = TaskPriority.Interactive
+			};
+
+			// Initially unscheduled
+			Assert.AreEqual (new Task [] {}, scheduler.Tasks);
+
+			// Send task1 to the scheduler
+			task1.Start ();
+			Assert.AreEqual (new Task [] { task1 }, scheduler.Tasks);
+
+			// Start a continuation. Should cause task2 to be scheduled.
+			// It should inherit the priority from task3 and go to the
+			// front of the queue.
+			Assert.AreEqual (TaskPriority.Normal, task2.Priority);
+			task2.ContinueWith (task3);
+			Assert.AreEqual (TaskPriority.Normal, task1.Priority);
+			Assert.AreEqual (TaskPriority.Interactive, task2.Priority);
+			Assert.AreEqual (new Task [] { task2, task1 }, scheduler.Tasks);
+		}
+
+		[Test]
+		public void TestPriorityRevert () {
+			var scheduler = new StaticScheduler ();
+			var task1 = new StaticTask (scheduler);
+			var task2 = new StaticTask (scheduler);
+			var task3 = new StaticTask (scheduler) {
+				Priority = TaskPriority.Interactive
+			};
+
+			// Initially unscheduled
+			Assert.AreEqual (new Task [] {}, scheduler.Tasks);
+
+			// Send task1 and task2 to the scheduler
+			task1.Start ();
+			task2.Start ();
+			Assert.AreEqual (TaskPriority.Normal, task1.Priority);
+			Assert.AreEqual (TaskPriority.Normal, task2.Priority);
+			Assert.AreEqual (TaskState.Scheduled, task1.State);
+			Assert.AreEqual (TaskState.Scheduled, task2.State);
+			Assert.AreEqual (new Task [] { task1, task2 }, scheduler.Tasks);
+
+			// Start a continuation. Should cause task2 to be rescheduled.
+			// It should inherit the priority from task3 and go to the
+			// front of the queue.
+			task2.ContinueWith (task3);
+			Assert.AreEqual (TaskPriority.Normal, task1.Priority);
+			Assert.AreEqual (TaskPriority.Interactive, task2.Priority);
+			Assert.AreEqual (TaskState.Scheduled, task1.State);
+			Assert.AreEqual (TaskState.Scheduled, task2.State);
+			Assert.AreEqual (new Task [] { task2, task1 }, scheduler.Tasks);
+
+			// Priority should revert after cancelling the child.
+			task3.Cancel ();
+			Assert.AreEqual (TaskPriority.Normal, task1.Priority);
+			Assert.AreEqual (TaskPriority.Normal, task2.Priority);
+			Assert.AreEqual (TaskState.Scheduled, task1.State);
+			Assert.AreEqual (TaskState.Scheduled, task2.State);
+			Assert.AreEqual (new Task [] { task1, task2 }, scheduler.Tasks);
+		}
+	}
+
+	class StaticScheduler
+	{
+		internal IntervalHeap<Task> heap = new IntervalHeap<Task> ();
+
+		public Task[] Tasks {
+			get {
+				List<Task> tasks = new List<Task> ();
+				foreach (var item in heap) {
+					tasks.Add (item);
+				}
+				return tasks.ToArray ();
+			}
+		}
+	}
+
+	class StaticTask : Task<bool>
+	{
+		public StaticScheduler Scheduler { get; set; }
+
+		internal StaticTask (StaticScheduler scheduler)
+		{
+			Scheduler = scheduler;
+		}
+
+		protected override void InnerSchedule ()
+		{
+			lock (Scheduler.heap) {
+				Scheduler.heap.Push (this, (int) Priority);
+			}
+		}
+
+		protected override void InnerUnschedule ()
+		{
+			lock (Scheduler.heap) {
+				Scheduler.heap.Remove (this);
+			}
+		}
+
+		protected override void InnerReschedule ()
+		{
+			lock (Scheduler.heap) {
+				Scheduler.heap.Remove (this);
+				Scheduler.heap.Push (this, (int) Priority);
+			}
+		}
+
+
+		protected override bool InnerExecute () {
+			throw new Exception ("Not supported for this task");
+		}
+
+		public override string ToString () {
+			return String.Format ("StaticTask (Priority: {0}, State: {1})", Priority, State);
+		}
+	}
+}
+#endif