1/*
2 * Copyright (c) 2000-2004 Apple Computer, Inc. All Rights Reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
11 * file.
12 *
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 */
23
24
25//
26// tqueue.h -- timer queues
27//
28#ifndef _H_TQUEUE
29#define _H_TQUEUE
30
31#include <security_utilities/utilities.h>
32#include <security_utilities/debugging.h>
33
34
35namespace Security {
36
37
38//
39// A TimerQueue is a container of elements that have relative "timer" positions.
40// TimerQueues are concerned with shuffling these elements around as their "times"
41// change, and with processing elements that fall off the front of the queue as
42// "time" passes.
43// We put "time" into quotes because nothing here really cares what kind of time
44// you are playing with. It could be seconds, points scored, etc. The only requirement
45// is that "time" doesn't ever flow backwards...
46//
47template <class Time>
48class ScheduleQueue {
49public:
50	ScheduleQueue()					{ first.fwd = first.back = &first; }
51	virtual ~ScheduleQueue()		{ }
52
53public:
54	class Event {
55		friend class ScheduleQueue;
56	public:
57		Event() : mScheduled(false) { }
58		~Event() { if (scheduled()) unschedule(); }
59
60		void unschedule();
61
62		Time when() const			{ return fireTime; }
63		bool scheduled() const		{ return mScheduled; }
64
65	private:
66		Time fireTime;				// when will it happen?
67		bool mScheduled;			// are we scheduled?
68		Event *back, *fwd;			// doubly-linked interior list
69
70		void putBefore(Event *ev)
71		{ back = ev->back; fwd = ev; ev->back = back->fwd = this; mScheduled = true; }
72	};
73
74public:
75	void schedule(Event *event, Time when);
76	void unschedule(Event *event)
77	{ event->unschedule(); }
78
79	bool empty() const	{ return first.fwd == &first; }
80	Time next() const	{ assert(!empty()); return first.fwd->fireTime; }
81
82	Event *pop(Time now);
83
84private:
85	Event first;					// root of active timers list
86};
87
88template <class Time>
89void ScheduleQueue<Time>::Event::unschedule()
90{
91	assert(mScheduled);
92	back->fwd = fwd; fwd->back = back;
93	mScheduled = false;
94	secdebug("schedq", "event %p unscheduled", this);
95}
96
97template <class Time>
98inline void ScheduleQueue<Time>::schedule(Event *event, Time when)
99{
100	Event *ev = first.fwd;
101	if (event->scheduled()) {
102		if (when == event->fireTime) {	// no change
103			secdebug("schedq", "%p (%.3f) no change", event, double(when));
104			return;
105		}
106		else if (when > event->fireTime && event != first.fwd)	// forward move
107			ev = event->back;
108		event->unschedule();
109	}
110	event->fireTime = when;
111	// newly schedule the event
112	for (; ev != &first; ev = ev->fwd) {
113		if (ev->fireTime > when) {
114			event->putBefore(ev);
115			secdebug("schedq", "%p (%.3f) scheduled before %p", event, double(when), ev);
116			return;
117		}
118	}
119
120	// hit the end-of-queue; put at end
121	event->putBefore(&first);
122	secdebug("schedq", "%p (%.3f) scheduled last", event, double(when));
123}
124
125template <class Time>
126inline typename ScheduleQueue<Time>::Event *ScheduleQueue<Time>::pop(Time now)
127{
128	if (!empty()) {
129		Event *top = first.fwd;
130		if (top->fireTime <= now) {
131			top->unschedule();
132			secdebug("schedq", "event %p delivered at %.3f", top, double(now));
133			return top;
134		}
135	}
136	return NULL;
137}
138
139} // end namespace Security
140
141#endif // _H_TQUEUE
142