1 /*--------------------------------------------------------------------------
2 Copyright 1999,2000, 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 Uses a priority queue. For more info, see
23 http://members.xoom.com/killough/heaps.html or any book on data structures.
24 The particular priority queue implementation here is the Heap,
25 invented in 1962 by J.W.J. Williams; our implementation is based on
26 the code in Chapter 12 of "Programming Pearls" by Jon Bentley.
27
28 The priority queue methods are private, and probably should be in a
29 separate class, but they're part of Sked as a historical accident.
30 The public methods addClient() and runAll() are implemented in terms
31 of the private priority queue methods.
32 We have grafted on a kludgy deleteClient() method in a rather horrible
33 way: the index in the heap is stored in the client record, and maintained
34 when a record is moved in the heap. A hash table would be better, but hey.
35 --------------------------------------------------------------------------*/
36
37 #include <errno.h>
38 #include <stdlib.h>
39 #include <stdio.h>
40 #include <assert.h>
41 #include <limits.h> // for MAXINT
42 #include "Sked.h"
43 #include "dprint.h"
44
45 // Uncomment to enable expensive tests; with these on, we're nowhere near n log n
46 // Should do this once in a blue moon, but only with very small n...
47 //#define EXPENSIVE_TESTS
48 #ifdef EXPENSIVE_TESTS
49 #define bigassert(x) assert(x)
50 #else
51 #define bigassert(x)
52 #endif
53
54 //#define VERBOSE
55
56 #ifdef VERBOSE
57 #define VDPRINT(x) DPRINT(x)
58 #else
59 #define VDPRINT(x)
60 #endif
61
62 /*----------------------------------------------------------------------
63 Helper function to store a SkedRecord at a particular index in the
64 heap array.
65 This will make more sense when we implement our planned delClient kludge.
66 The odd 'do { ... } while (0)' trick is just there so ... is treated
67 as a single C statement, even if it contains several statements.
68 This *is* currently faster than an inline function, who knows why.
69
70 Warning: don't call with arguments that have side effects!
71 ----------------------------------------------------------------------*/
72 #define storeAt(i, r) do { m_records[(i)] = (r); (r).skc->skedIndex = i; VDPRINT(("storeAt(%d, %p)\n", i, (r).skc)); } while (0)
73
74 /* The private methods */
75
76 #ifdef EXPENSIVE_TESTS
77 /*----------------------------------------------------------------------
78 Debugging function.
79 Return true if m_records[lb...ub] has the heap property, i.e.
80 if for all i from lb to ub inclusive,
81 m_records[i/2].when <= m_records[i].when
82 ----------------------------------------------------------------------*/
isHeap(int lb,int ub)83 bool Sked::isHeap(int lb, int ub)
84 {
85 int i;
86
87 //DPRINT(("Sked::isHeap(%d, %d)\n", lb, ub));
88 assert((lb >= 1) && (lb <= m_used));
89 assert((ub >= 1) && (ub <= m_used));
90
91 for (i=lb; i<(2*lb) && i<ub; i++) {
92 assert(m_records[i].skc);
93 if (m_records[i].skc->skedIndex != i) {
94 DPRINT(("Sked::isHeap(%d,%d): m_records[%d].skc->skedIndex = %d!\n",
95 lb, ub, i, m_records[i].skc->skedIndex));
96 }
97 assert(m_records[i].skc->skedIndex == i);
98 }
99 for (i=(2*lb); i<=ub; i++) {
100 if (eclock_after(m_records[i/2].when, m_records[i].when)) {
101 DPRINT(("Sked::isHeap(%d, %d): %d.when > %d.when! \n", lb, ub, i/2, i));
102 return false;
103 }
104 assert(m_records[i].skc);
105 if (i != m_records[i].skc->skedIndex) {
106 DPRINT(("Sked::isHeap: %d: index doesn't match one in record, %d\n", i, m_records[i].skc->skedIndex));
107 return false;
108 }
109 }
110 return true;
111 }
112 #endif
113
114 /*----------------------------------------------------------------------
115 Sift up a heap element towards the root until it's in an ok place.
116 On entry, the heap is in good shape except perhaps for the element at
117 the given index is in the wrong place, i.e. its value might be less
118 than the value of its parent.
119 On exit, the heap is rearranged so it is in good shape everywhere.
120 ----------------------------------------------------------------------*/
siftUp(int index)121 void Sked::siftUp(int index)
122 {
123 /* "sift up" the new record to its correct position in the heap */
124 while (index > 1) {
125 /* Invariant: Heap(1,size()) except perhaps between index
126 * and its parent
127 */
128 int parent = index / 2;
129 if (eclock_after(m_records[index].when, m_records[parent].when))
130 break;
131
132 SkedRecord tmp = m_records[parent];
133 storeAt(parent, m_records[index]);
134 storeAt(index, tmp);
135
136 index = parent;
137 }
138
139 /* Postcondition */
140 bigassert(isHeap(1, m_used));
141 }
142
143 /*----------------------------------------------------------------------
144 Sift down a heap element until it's in an ok place.
145 On entry, the heap is in good shape except perhaps for the element at
146 the given index is in the wrong place, i.e. its value might be greater
147 than the values of its children.
148 On exit, the heap is rearranged so it is in good shape everywhere.
149 ----------------------------------------------------------------------*/
siftDown(int index)150 void Sked::siftDown(int index)
151 {
152 VDPRINT(("Sked::siftDown(%d)\n", index));
153
154 /* "sift down" the element to its correct position in the heap */
155 while (true) {
156 /* Invariant: Heap(1,m_used) except perhaps between index
157 * and its (0, 1 or 2) children
158 */
159 int child = index * 2;
160 if (child > m_used)
161 break;
162 /* child is the left child of index */
163 if (child < m_used) {
164 /* child+1 is the right child of index */
165 if (!eclock_after(m_records[child+1].when, m_records[child].when))
166 child++;
167 }
168 assert(child <= m_used);
169 /* child is the least child of index */
170 if (eclock_after(m_records[child].when, m_records[index].when))
171 break;
172 /* swap child and index */
173 VDPRINT(("Sked::siftDown: %d.when > %d.when, so swapping\n", index, child));
174 SkedRecord tmp = m_records[child];
175 storeAt(child, m_records[index]);
176 storeAt(index, tmp);
177 index = child;
178 }
179
180 /* Postcondition */
181 bigassert(isHeap(1, m_used));
182
183 VDPRINT(("Sked::siftDown: done\n"));
184 }
185
186 /*----------------------------------------------------------------------
187 Remove the given element from the middle of the heap.
188 On entry, the heap is in good shape.
189 On exit, the heap is in good shape, and the given element is gone.
190 ----------------------------------------------------------------------*/
remove(int index)191 void Sked::remove(int index)
192 {
193 VDPRINT(("Sked::remove(%d): m_used %d\n", index, m_used));
194 /* Precondition */
195 bigassert(isHeap(1, m_used));
196 assert(m_used >= 0);
197 assert(index <= m_used);
198
199 if (m_used-- > 1) {
200 /* "sift up" the given record to the top, preserving heap property */
201 while (index > 1) {
202 int parent = index / 2;
203
204 VDPRINT(("Sked::remove: swapping %d and %d\n", index, parent));
205 SkedRecord tmp = m_records[parent];
206 storeAt(parent, m_records[index]);
207 storeAt(index, tmp);
208
209 index = parent;
210 }
211
212 /* Move the last element to the head of the heap, overwriting the
213 * element we just moved there.
214 */
215 storeAt(1, m_records[m_used+1]);
216
217 /* "sift down" the new top event to its correct position in the heap */
218 if (m_used > 1) {
219 bigassert(isHeap(2, m_used));
220 siftDown(1);
221 }
222 /* Postcondition */
223 bigassert(isHeap(1, m_used));
224 }
225 VDPRINT(("Sked::remove: done, m_used %d\n", m_used));
226 }
227
228 /*----------------------------------------------------------------------
229 Adds a scheduled event to the priority queue, allocating additional
230 memory if necessary.
231 Copies the given record, does not save the skr pointer.
232 Returns 0 on success, or Unix error code on failure.
233 ----------------------------------------------------------------------*/
push(SkedRecord * skr)234 int Sked::push(SkedRecord *skr)
235 {
236 assert(skr->skc);
237 VDPRINT(("Sked::push: size %d\n", size()));
238
239 /* Resize array if needed */
240 if (m_used+1 == m_allocated) {
241 int new_alloc = m_allocated * 2;
242 int new_size = new_alloc * sizeof(SkedRecord);
243 DPRINT(("Sked::push: Reallocating %d bytes.\n", new_size));
244 SkedRecord *tmp = (SkedRecord*)realloc(m_records, new_size);
245 if (!tmp)
246 return ENOMEM;
247 m_allocated = new_alloc;
248 m_records = tmp;
249 DPRINT(("Sked::push: setting m_allocated to %d\n", m_allocated));
250 }
251
252 /* Precondition */
253 if (m_used > 0)
254 bigassert(isHeap(1, m_used));
255
256 /* Add the new record */
257 m_used = m_used + 1;
258 storeAt(m_used, *skr);
259
260 /* "sift up" the new record to its correct position in the heap */
261 siftUp(m_used);
262
263 /* Postcondition */
264 bigassert(isHeap(1, m_used));
265 VDPRINT(("Sked::push: done, size now %d\n", size()));
266 return 0;
267 }
268
269 /*----------------------------------------------------------------------
270 Removes the first scheduled event in the priority queue and brings the
271 second scheduled event to the top.
272 ----------------------------------------------------------------------*/
pop()273 void Sked::pop()
274 {
275 VDPRINT(("Sked::pop: size %d\n", size()));
276 if (empty())
277 return;
278
279 /* Precondition */
280 bigassert(isHeap(1, m_used));
281
282 /* Tell the element at the head of the heap he's being removed */
283 assert(m_records[1].skc);
284 assert(m_records[1].skc->skedIndex == 1);
285 //DPRINT(("Sked::pop: clearing skc %p ->skedIndex\n", m_records[1].skc));
286 m_records[1].skc->skedIndex = 0;
287 m_used--;
288 assert(size() >= 0);
289
290 if (size() > 0) {
291 /* Move the old last element to the head of the heap */
292 storeAt(1, m_records[m_used+1]);
293 if (size() > 1) {
294 /* "sift down" the new top to its correct position in the heap */
295 bigassert(isHeap(2, m_used));
296 siftDown(1);
297 bigassert(isHeap(1, m_used));
298 }
299 assert(m_records[1].skc->skedIndex == 1);
300 }
301 VDPRINT(("Sked::pop: done, size now %d\n", size()));
302 }
303
304 /* The public methods */
305
306 /*----------------------------------------------------------------------
307 Allocates memory for the priority queue.
308 Returns 0 on success, or Unix error code on failure.
309 ----------------------------------------------------------------------*/
init()310 int Sked::init()
311 {
312 m_allocated = 256;
313 int nbytes = m_allocated * sizeof(SkedRecord);
314 DPRINT(("Sked::init: Allocating %d bytes.\n", nbytes));
315 m_records = (SkedRecord*)malloc(nbytes);
316 if (!m_records) {
317 m_allocated = m_used = 0;
318 return ENOMEM;
319 }
320 m_used = 0;
321 return 0;
322 }
323
324 /*----------------------------------------------------------------------
325 Schedule an event for the future.
326 Returns 0 on success, or Unix error code on failure.
327 ----------------------------------------------------------------------*/
addClient(SkedClient * skc,clock_t when)328 int Sked::addClient(SkedClient *skc, clock_t when)
329 {
330 DPRINT(("Sked::addClient(%p, %d)\n", skc, when));
331 assert(skc);
332 assert(!skc->skedIndex);
333 SkedRecord skr(skc, when);
334 assert(skr.skc);
335 return push(&skr);
336 }
337
338 /*----------------------------------------------------------------------
339 Delete the given client from the queue of future events.
340 Returns 0 on success, or Unix error code on failure.
341 ----------------------------------------------------------------------*/
delClient(SkedClient * skc)342 int Sked::delClient(SkedClient *skc)
343 {
344 DPRINT(("Sked::delClient: index %d, m_used %d\n", skc->skedIndex, m_used));
345 if (skc->skedIndex == 0)
346 return 0; /* not scheduled */
347
348 assert(m_used > 0);
349
350 /* Remove the element from the heap */
351 remove(skc->skedIndex);
352
353 /* Mark the client as not being in the heap */
354 skc->skedIndex = 0;
355
356 return 0;
357 }
358
359 /*----------------------------------------------------------------------
360 Run events whose time has come.
361 i.e. for each client registered with addClient with a 'when' before 'now',
362 calls the client's skedCallback() method.
363 Returns 0 on success, Unix error code on failure.
364 ----------------------------------------------------------------------*/
runAll(clock_t now)365 int Sked::runAll(clock_t now)
366 {
367 do {
368 const SkedRecord *p;
369 p = top();
370
371 /* If there are no more nodes ready to execute, give up happily */
372 //DPRINT(("Sked::runAll: p %p, p->when - now %d\n", p, (p ? p->when : now) - now));
373 if (!p || eclock_after(p->when, now))
374 return 0;
375
376 //DPRINT(("Sked::runAll: p %p, skc %p, index %d\n", p, p->skc, p->skc->skedIndex));
377 if ((p->skc->skedIndex < 1) || (p->skc->skedIndex > m_used) || (m_records[p->skc->skedIndex].skc != p->skc) ) {
378 DPRINT(("Sked::runAll: invalid index %d or pointer doesn't match\n", p->skc->skedIndex));
379 return EINVAL;
380 }
381
382 /* Note: the callback may try to remove itself from the queue
383 * or add itself back in to the queue, so we have to pop it
384 * before we call its callback.
385 */
386 SkedClient *skc = p->skc;
387 //DPRINT(("Sked::runAll: before pop; skc %p, skc->skedIndex %d\n", skc, skc->skedIndex));
388 assert(skc->skedIndex == 1);
389 pop();
390 //DPRINT(("Sked::runAll: after pop; skc %p, skc->skedIndex %d\n", skc, skc->skedIndex));
391 assert(!skc->skedIndex);
392
393 //DPRINT(("Sked::runAll: Calling callback; skc %p\n", skc));
394 skc->skedCallback(now);
395 } while (true);
396 return 0;
397 }
398
399