OSX/libsecurity_utilities/lib/tqueue.h

   1 /*
   2  * Copyright (c) 2000-2004,2011,2014 Apple 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
  35 namespace 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 //
  47 template <class Time>
  48 class ScheduleQueue {
  49 public:
  50         ScheduleQueue()                                 { first.fwd = first.back = &first; }
  51         virtual ~ScheduleQueue()                { }
  52
  53 public:
  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
  74 public:
  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
  84 private:
  85         Event first;                                    // root of active timers list
  86 };
  87
  88 template <class Time>
  89 void ScheduleQueue<Time>::Event::unschedule()
  90 {
  91         assert(mScheduled);
  92         back->fwd = fwd; fwd->back = back;
  93         mScheduled = false;
  94         secinfo("schedq", "event %p unscheduled", this);
  95 }
  96
  97 template <class Time>
  98 inline 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                         secinfo("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                         secinfo("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         secinfo("schedq", "%p (%.3f) scheduled last", event, double(when));
 123 }
 124
 125 template <class Time>
 126 inline 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                         secinfo("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