cdsa/cdsa_utilities/tqueue.h

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