timer.cs

来自「没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没」· CS 代码 · 共 754 行 · 第 1/2 页

			/// </remarks>
			private class PriorityQueue
			{
				//
				// Priority queue represented as a balanced binary heap: the
				// two children of queue[n] are queue[2*n] and queue[2*n+1].
				// The priority queue is ordered on the nextExecutionTime
				// field: The Alarm with the lowest ExpiryTime is in queue[1]
				// (assuming the queue is nonempty).  For each node n in the
				// heap, and each descendant of n, d:
				//   n.ExpiryTime <= d.ExpiryTime. 
				//
				private Alarm[] queue = new Alarm[4];

				//
				// The number of timeouts in the priority queue.  (The Alarms
				// are stored in queue[1] up to queue[count]).
				//
				private int count = 0;

				/// <summary>Adds an alarm to the priority queue.</summary>
				public void Add(Alarm alarm)
				{
					//
					// Grow backing store if necessary
					//
					if (++this.count == this.queue.Length)
					{
						Alarm[] newQueue = new Alarm[2 * this.count];
						Array.Copy(this.queue, 1, newQueue, 1, this.count - 1);
						this.queue = newQueue;
					}
					this.queue[this.count] = alarm;
					this.fixUp(this.count);
				}

				/// <summary>Get the alarm next due to fire.</summary>
				/// <remarks>
				///     Return the "head Alarm" of the priority queue.  This
				///     is the Alarm with the lowest ExpiryTime.  <c>null</c>
				///     is returned if there is no alarm pending.
				/// </remarks>
				public Alarm Head
				{
					get { return this.queue[1]; }
				}

				/// <summary>Remove an alarm from the priority queue.</summary>
				public void Remove(Alarm alarm)
				{
					int index =
						System.Array.IndexOf(this.queue, alarm, 1, this.count);
					if (index == -1)		// Alarm not in the queue?
						return;
					int oldCount = this.count;
					this.count -= 1;
					if (index != oldCount)	// Not last alarm in the queue?
					{
						//
						// Delete the alarm by overwriting it with the last one
						// in the queue, then re-adjusting the heap to maintain
						// the invariant.
						//
						this.queue[index] = this.queue[oldCount];
						this.fixDown(index);
					}
					this.queue[oldCount] = null; // Prevent memory leaks!
				}

				//
				// Establishes the heap invariant (described above) assuming
				// the heap satisfies the invariant except possibly for the
				// leaf-node indexed by k (which may have a ExpiryTime less
				// than its parent's).
				//
				// This method functions by "promoting" queue[k] up the
				// hierarchy (by swapping it with its parent) repeatedly until
				// queue[k]'s expireTime is greater than or equal to that of
				// its parent.
				//
				private void fixUp(int k)
				{
					while (k > 1)
					{
						int j = k >> 1;
						if (this.queue[j].ExpiryTime <= this.queue[k].ExpiryTime)
							break;
						Alarm tmp = this.queue[j];
						this.queue[j] = this.queue[k];
						this.queue[k] = tmp;
						k = j;
					}
				}

				//
				// Establishes the heap invariant (described above) in the
				// subtree rooted at k, which is assumed to satisfy the heap
				// invariant except possibly for node k itself (which may have
				// a ExpiryTime greater than its children's).
				// 
				// This method functions by "demoting" queue[k] down the
				// hierarchy (by swapping it with its smaller child) repeatedly
				// until queue[k]'s expireTime is less than or equal to those
				// of its children.
				//
				private void fixDown(int k)
				{
					int j;
					while ((j = k << 1) <= this.count)
					{
						if (j < this.count && this.queue[j].ExpiryTime > this.queue[j+1].ExpiryTime)
							j += 1; // j indexes smallest kid
						if (this.queue[k].ExpiryTime <= this.queue[j].ExpiryTime)
							break;
						Alarm tmp = this.queue[j];
						this.queue[j] = this.queue[k];
						this.queue[k] = tmp;
						k = j;
					}
				}
			}

			public interface IAlarm
			{
				/// <summary>Set the Alarm.</summary>
				/// <param name="dueTime">The amount of time to delay before
				///     firing the event for the first time.  If this is 0, the
				///     event is fired immediately.  If this is
				///     <see cref="INFINITE"/> the Alarm is disabled, meaning
				///     it never fires.</param>
				/// <param name="period">After the event is fired, the time to
				///     delay before firing it again.  If this is
				///     <see cref="INFINITE"/> is will never be fired
				///     again.</param>
				///
				/// <remarks>
				///     The event to fire is passed to
				///     <see cref="CreateAlarm"/>.  The units used to measure
				///     time is up to you.  Just be sure they are consistent
				///     with what is passed to <see cref="Sleep"/>.
				/// </remarks>
				void SetAlarm(long dueTime, long period);
			}

			/// <summary>Fired when an alarm expires.</summary>
			public delegate void AlarmExpiredHandler();

			/// <summary>Implementation of an IAlarm.</summary>
			/// <remarks>
			///     No one is meant to look inside of this - except the Alarm
			///     Clock.
			/// </remarks>
			private class Alarm : IAlarm
			{
				public long					ExpiryTime;  // DISABLED or when next due
				public readonly AlarmExpiredHandler	AlarmExpired;
				private readonly AlarmClock	alarmClock;	// Our owner
				private long				period;		// Periodic interval

				private const long			DISABLED = -1;

				/// <summary>Create a new Alarm.</summary>
				public Alarm(AlarmClock alarmClock, AlarmExpiredHandler alarmExpired)
				{
					this.alarmClock = alarmClock;
					this.AlarmExpired = alarmExpired;
					this.ExpiryTime = DISABLED;
				}

				public void SetAlarm(long dueTime, long period)
				{
					//
					// Check arguments.
					//
					if (dueTime < 0)
					{
						throw new ArgumentOutOfRangeException(
							"dueTime", _("ArgRange_NonNegative"));
					}
					if (period <= 0)
					{
						throw new ArgumentOutOfRangeException(
							"period", _("ArgRange_PositiveNonZero"));
					}
					//
					// Lock the clock while the alarm is scheduled for the
					// first time.
					//
					lock (this)
					{
						//
						// First a quick check to see if anything has changed.
						// This has to be done, because this routine may be
						// called by a finalizer wishing to clean up.  The
						// the finalizer will of been called by the garbage
						// collector because it was asked for more memory,
						// and there isn't any.  The thread asking for memory
						// may be in here, allocating a new Alarm, say.
						// Because it is in here, the AlarmClock object may
						// be locked.  If we should then try to lock the
						// AlarmClock, the finializer will block, which means
						// the memory won't be freed, which means the other
						// thread will remain blocked, which means we managed
						// to dead lock the garbage collector.  Oh joy.  A
						// new reason to hate threads.  And yes, this really
						// did happen during testing.
						//
						// The key to this mess is to realise that if this
						// object is being garbage collected, there must be
						// no references to it.  In particular, it is not in
						// the alarm queue, so its ExpiryTime must be DISABLED.
						// Also, since this object is being garbage collected,
						// the only reasonable thing the finalizer can be doing
						// in here it ensuring this alarm is disabled.
						//
						// So, if this call is disabling an already disabled
						// alarm, then under no circumstances must we try to
						// acquire a lock on AlarmClock, as doing so may
						// deadlock the garbage collector.
						//
						if (dueTime == INFINITE && this.ExpiryTime == DISABLED)
							return;
					}
					//
					// The locks must be released and re-acquired in the same
					// order as Sleep/Advance does it below, or again we risk
					// deadlock.
					//
					lock (this.alarmClock)
					{
						lock (this)
						{
							if (this.ExpiryTime != DISABLED)
								this.alarmClock.pending.Remove(this);
							if (dueTime == INFINITE)
							{
								this.ExpiryTime = DISABLED;
								return;
							}
							this.period = period;
							this.ExpiryTime = this.alarmClock.now + dueTime;
							this.alarmClock.pending.Add(this);
						}
					}
				}

				/// <summary>Advance the time for this alarm.</summary>
				/// <param name="to">The proposed new value for the
				///     time.</param>
				/// <returns>The time this alarm is due to go off.</returns>
				///
				/// <remarks>
				///     Must be called while the lock on the clock is held.
				///     If the Alarm would expire in the interval passed it
				///     is rescheduled or disabled, depending on its settings.
				/// </remarks>
				public long Advance(long to)
				{
					long oldExpiryTime;
					lock (this)
					{
						oldExpiryTime = this.ExpiryTime;
						if (this.ExpiryTime <= to)
						{
							this.alarmClock.pending.Remove(this);
							if (this.period == INFINITE)
								this.ExpiryTime = DISABLED;
							else
							{
								this.ExpiryTime += this.period;
								this.alarmClock.pending.Add(this);
							}
						}
					}
					return oldExpiryTime;
				}
			};

			//
			// The current time.
			//
			private long			now = 0;

			//
			// A list of all enabled Alarm's.
			//
			private PriorityQueue	pending = new PriorityQueue();

			/// <summary>Create a new IAlarm.</summary>
			/// <remarks>
			///     The IAlarm is initially disabled.
			/// </remarks>
			public IAlarm CreateAlarm(AlarmExpiredHandler alarmExpired)
			{
				if (alarmExpired == null)
					throw new ArgumentNullException("alarmExpired");
				return new Alarm(this, alarmExpired);
			}

			/// <summary>Advance the time.</summary>
			/// <param name="period">The amount to advance the time by.</param>
			///
			/// <remarks>
			///     Advance the time, and fire all <see cref="IAlarm"/>'s that
			///     exipred during that period.  Because this method may fire
			///     events it must be called *OUTSIDE OF ALL LOCKS*.  The units
			///     used to measure time are up to you - just be sure to keep
			///     them consistent with <see cref="Alarm.SetAlarm"/>.  
			/// </remarks>
			public void Sleep(long period)
			{
				for (;;)
				{
					Alarm nextAlarm;
					lock (this)
					{
						//
						// Find the event to occur.
						//
						long endSleep = this.now + period;
						nextAlarm = this.pending.Head;
						//
						// If there another alarm in the queue?
						//
						if (nextAlarm == null)
						{
							this.now = endSleep;
							return;
						}
						//
						// Is the alarm due to go off?
						//
						long nextExpiryTime = nextAlarm.Advance(endSleep);
						if (nextExpiryTime > endSleep)
						{
							this.now = endSleep;
							return;
						}
						//
						// An alarm has expired.  Advance the time to equal
						// its current expiry time.
						//
						period -= nextExpiryTime - this.now;
						this.now = nextExpiryTime;
					}
					//
					// Must be called outside of the lock to avoid potential
					// deadlocks.
					//
					nextAlarm.AlarmExpired();
				}
			}

			/// <summary>The delay until the next alarm will fire.</summary>
			/// <returns>
			///     The amount of time until the next <see cref="IAlarm"/>
			///     will fire, or <see cref="INFINITE"/> if there is no
			///     <c>Alarm</c>'s pending.  The units are the same as for the
			///     period passed to <see cref="Sleep"/>.
			/// </returns>
			public long TimeTillAlarm
			{
				get
				{
					lock (this)
					{
						Alarm nextAlarm = this.pending.Head;
						if (nextAlarm == null)
							return INFINITE;
						return nextAlarm.ExpiryTime - this.now;
					}
				}
			}
		}
	}; // class Timer
}; // namespace System.Threading