Security-55163.44.tar.gz

[apple/security.git] / libsecurity_utilities / lib / tqueue.h

diff --git a/libsecurity_utilities/lib/tqueue.h b/libsecurity_utilities/lib/tqueue.h
new file mode 100644 (file)
index 0000000..fe716f0
--- /dev/null
+++ b/libsecurity_utilities/lib/tqueue.h
@@ -0,0 +1,141 @@
+/*
+ * Copyright (c) 2000-2004 Apple Computer, Inc. All Rights Reserved.
+ * 
+ * @APPLE_LICENSE_HEADER_START@
+ * 
+ * This file contains Original Code and/or Modifications of Original Code
+ * as defined in and that are subject to the Apple Public Source License
+ * Version 2.0 (the 'License'). You may not use this file except in
+ * compliance with the License. Please obtain a copy of the License at
+ * http://www.opensource.apple.com/apsl/ and read it before using this
+ * file.
+ * 
+ * The Original Code and all software distributed under the License are
+ * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
+ * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
+ * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
+ * Please see the License for the specific language governing rights and
+ * limitations under the License.
+ * 
+ * @APPLE_LICENSE_HEADER_END@
+ */
+
+
+//
+// tqueue.h -- timer queues
+//
+#ifndef _H_TQUEUE
+#define _H_TQUEUE
+
+#include <security_utilities/utilities.h>
+#include <security_utilities/debugging.h>
+
+
+namespace Security {
+
+
+//
+// A TimerQueue is a container of elements that have relative "timer" positions.
+// TimerQueues are concerned with shuffling these elements around as their "times"
+// change, and with processing elements that fall off the front of the queue as
+// "time" passes.
+// We put "time" into quotes because nothing here really cares what kind of time
+// you are playing with. It could be seconds, points scored, etc. The only requirement
+// is that "time" doesn't ever flow backwards...
+//
+template <class Time>
+class ScheduleQueue {
+public:
+       ScheduleQueue()                                 { first.fwd = first.back = &first; }
+       virtual ~ScheduleQueue()                { }
+       
+public:
+       class Event {
+               friend class ScheduleQueue;
+       public:
+               Event() : mScheduled(false) { }
+               ~Event() { if (scheduled()) unschedule(); }
+               
+               void unschedule();
+               
+               Time when() const                       { return fireTime; }
+               bool scheduled() const          { return mScheduled; }
+               
+       private:
+               Time fireTime;                          // when will it happen?
+               bool mScheduled;                        // are we scheduled?
+               Event *back, *fwd;                      // doubly-linked interior list
+               
+               void putBefore(Event *ev)
+               { back = ev->back; fwd = ev; ev->back = back->fwd = this; mScheduled = true; }
+       };
+       
+public:
+       void schedule(Event *event, Time when);
+       void unschedule(Event *event)
+       { event->unschedule(); }
+       
+       bool empty() const      { return first.fwd == &first; }
+       Time next() const       { assert(!empty()); return first.fwd->fireTime; }
+       
+       Event *pop(Time now);
+
+private:
+       Event first;                                    // root of active timers list
+};
+
+template <class Time>
+void ScheduleQueue<Time>::Event::unschedule()
+{
+       assert(mScheduled);
+       back->fwd = fwd; fwd->back = back; 
+       mScheduled = false;
+       secdebug("schedq", "event %p unscheduled", this);
+}
+
+template <class Time>
+inline void ScheduleQueue<Time>::schedule(Event *event, Time when)
+{
+       Event *ev = first.fwd;
+       if (event->scheduled()) {
+               if (when == event->fireTime) {  // no change
+                       secdebug("schedq", "%p (%.3f) no change", event, double(when));
+                       return;
+               }
+               else if (when > event->fireTime && event != first.fwd)  // forward move
+                       ev = event->back;
+               event->unschedule();
+       }
+       event->fireTime = when;
+       // newly schedule the event
+       for (; ev != &first; ev = ev->fwd) {
+               if (ev->fireTime > when) {
+                       event->putBefore(ev);
+                       secdebug("schedq", "%p (%.3f) scheduled before %p", event, double(when), ev);
+                       return;
+               }
+       }
+       
+       // hit the end-of-queue; put at end
+       event->putBefore(&first);
+       secdebug("schedq", "%p (%.3f) scheduled last", event, double(when));
+}
+
+template <class Time>
+inline typename ScheduleQueue<Time>::Event *ScheduleQueue<Time>::pop(Time now)
+{
+       if (!empty()) {
+               Event *top = first.fwd;
+               if (top->fireTime <= now) {
+                       top->unschedule();
+                       secdebug("schedq", "event %p delivered at %.3f", top, double(now));
+                       return top;
+               }
+       }
+       return NULL;
+}
+
+} // end namespace Security
+
+#endif // _H_TQUEUE