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