1 /*-------------------------------------------------------------------------- 2 Copyright 1999, Dan Kegel http://www.kegel.com/ 3 See the file COPYING 4 5 This program is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation; either version 2 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program; if not, write to the Free Software 17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 18 --------------------------------------------------------------------------*/ 19 20 /*-------------------------------------------------------------------------- 21 Module to schedule events in the future. 22 Takes little time to add or delete an event even when tens of thousands 23 of events are scheduled, i.e. adding or deleting an event takes CPU 24 time proportional to the log of the number of already-scheduled events. 25 Stores scheduled events in a priority queue. For more info, see 26 http://members.xoom.com/killough/heaps.html or any book on data structures. 27 The particular priority queue implementation here is the Heap, 28 invented in 1962 by J.W.J. Williams; our implementation is based on 29 the code in Chapter 12 of "Programming Pearls" by Jon Bentley. 30 Bentley didn't provide a delete(), so the one here is my own attempt; 31 there may be a better way to do it. 32 33 The priority queue methods are private, and probably should be in a 34 separate class, but they're part of Sked as a historical accident. 35 The public methods addClient() and runAll() are implemented in terms 36 of the private priority queue methods. 37 The SkedClient interface is really wierd in that it has a data element, 38 which is used by this module to remember where in the heap the client 39 is. There's probably a better way. 40 --------------------------------------------------------------------------*/ 41 42 #ifndef Sked_h 43 #define Sked_h 44 45 #include "eclock.h" 46 47 /*---------------------------------------------------------------------- 48 Interface that must be implemented by user code that wishes to be 49 scheduled. 50 ----------------------------------------------------------------------*/ 51 class SkedClient { 52 public: 53 /*---------------------------------------------------------------------- 54 User-supplied function. 55 When the specified time has elapsed, Sked calls this method. 56 ----------------------------------------------------------------------*/ 57 virtual void skedCallback(clock_t now) = 0; 58 SkedClient()59 SkedClient() { skedIndex = 0; } 60 61 /* A data element used to track where this client is in the heap. */ 62 int skedIndex; // 0 if not in heap yet, else index into m_records 63 }; 64 65 /*-------------------------------------------------------------------------- 66 The scheduler itself. 67 --------------------------------------------------------------------------*/ 68 class Sked { 69 public: 70 struct SkedRecord { SkedRecordSkedRecord71 SkedRecord(SkedClient *c, clock_t w) { skc=c; when=w; } 72 SkedClient *skc; 73 clock_t when; 74 }; 75 76 private: 77 /* m_records is the array holding the implicit tree heap. 78 * Note: m_records[0] is never used. We use m_records as a 1-based array. 79 */ 80 SkedRecord *m_records; 81 int m_allocated; // allocated size, including 0th element 82 83 /* m_used is the highest index in use. 84 * It's also the number of events queued. 85 * It starts out at zero. When the first event is queued, 86 * it's stored at m_records[1], and m_used is incremented to 1. 87 */ 88 int m_used; // highest index in use 89 90 /*====================================================================== 91 Private methods for managing the priority queue. The priority 92 queue is implemented as a binary heap. The functions isHeap(), 93 push() and pop() are based upon the algorithms isHeap(), siftUp() 94 and siftDown() in Chapter 12 of "Programming Pearls" by Jon Bentley. 95 Note that m_records[1] is the top of the queue and m_records[0] 96 is not used. 97 ======================================================================*/ 98 99 public: /* Only public for self-test */ 100 /*---------------------------------------------------------------------- 101 Debugging function. 102 Return true if m_records[lb...ub] has the heap property, i.e. 103 if for all i from lb to ub inclusive, 104 m_records[i/2].when <= m_records[i].when 105 ----------------------------------------------------------------------*/ 106 bool isHeap(int lb, int ub); 107 108 /*---------------------------------------------------------------------- 109 Returns the actual number of scheduled events in the queue. 110 ----------------------------------------------------------------------*/ size()111 int size() { return m_used; } 112 113 /*---------------------------------------------------------------------- 114 Returns the first scheduled event in the queue, or NULL if the 115 queue is empty. 116 ----------------------------------------------------------------------*/ top()117 const SkedRecord *top() { return empty() ? NULL : m_records+1; } 118 119 /*---------------------------------------------------------------------- 120 Sift up a heap element towards the root until it's in an ok place. 121 On entry, the heap is in good shape except perhaps for the element at 122 the given index is in the wrong place, i.e. its value might be less 123 than the value of its parent. 124 On exit, the heap is rearranged so it is in good shape everywhere. 125 ----------------------------------------------------------------------*/ 126 void siftUp(int index); 127 128 /*---------------------------------------------------------------------- 129 Sift down a heap element until it's in an ok place. 130 On entry, the heap is in good shape except perhaps for the element at 131 the given index is in the wrong place, i.e. its value might be greater 132 than the values of its children. 133 On exit, the heap is rearranged so it is in good shape everywhere. 134 ----------------------------------------------------------------------*/ 135 void siftDown(int index); 136 137 /*---------------------------------------------------------------------- 138 Remove the given element from the middle of the heap. 139 On entry, the heap is in good shape. 140 On exit, the heap is in good shape, and the given element is gone. 141 ----------------------------------------------------------------------*/ 142 void remove(int index); 143 144 /*---------------------------------------------------------------------- 145 Adds a scheduled event to the priority queue, allocating additional 146 memory if necessary. 147 Copies the given record, does not save the skr pointer. 148 Returns 0 on success, or Unix error code on failure. 149 ----------------------------------------------------------------------*/ 150 int push(SkedRecord *skr); 151 152 /*---------------------------------------------------------------------- 153 Removes the first scheduled event in the priority queue and brings the 154 second scheduled event to the top. 155 ----------------------------------------------------------------------*/ 156 void pop(); 157 158 public: 159 /*---------------------------------------------------------------------- 160 Constructor. 161 ----------------------------------------------------------------------*/ Sked()162 Sked() { m_used = 0; m_records = NULL; } 163 164 /*---------------------------------------------------------------------- 165 Allocates memory for the priority queue. 166 Returns 0 on success, or Unix error code on failure. 167 ----------------------------------------------------------------------*/ 168 int init(); 169 170 /*---------------------------------------------------------------------- 171 Returns true if there are no scheduled events in the queue. 172 ----------------------------------------------------------------------*/ empty()173 bool empty() { return size() == 0; } 174 175 /*---------------------------------------------------------------------- 176 Schedule an event for the future. 177 Only one event may be outstanding for any one SkedClient. 178 Returns 0 on success, or Unix error code on failure. 179 ----------------------------------------------------------------------*/ 180 int addClient(SkedClient *skc, clock_t when); 181 182 /*---------------------------------------------------------------------- 183 Delete the given client from the queue of future events. 184 Returns 0 on success, or Unix error code on failure. 185 ----------------------------------------------------------------------*/ 186 int delClient(SkedClient *skc); 187 188 /*---------------------------------------------------------------------- 189 Run events whose time has come. 190 i.e. for each client registered with addClient with a 'when' before 'now', 191 calls the client's skedCallback() method. 192 Returns 0 on success, Unix error code on failure. 193 ----------------------------------------------------------------------*/ 194 int runAll(clock_t now); 195 196 /*---------------------------------------------------------------------- 197 Return time of next event, or the given default if no event scheduled. 198 ----------------------------------------------------------------------*/ nextTime(clock_t defval)199 clock_t nextTime(clock_t defval) { return empty() ? defval : top()->when; } 200 }; 201 202 #endif 203