aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/heap.h322
-rw-r--r--src/minicron.cpp75
-rw-r--r--src/minicron.h51
-rw-r--r--src/tests/heap.cpp11
-rw-r--r--src/tests/minicron.cpp13
5 files changed, 433 insertions, 39 deletions
diff --git a/src/heap.h b/src/heap.h
index ca12a42..9df4121 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -18,6 +18,25 @@ namespace Bu
18{ 18{
19 subExceptionDecl( HeapException ); 19 subExceptionDecl( HeapException );
20 20
21 /**
22 * A priority queue that allows for an unlimited number of priorities. All
23 * objects enqueued must support less-than-comparison. Then every time an
24 * item is dequeued it is always the least item in the heap. The heap
25 * operates using a binary tree for storage, which allows most operations
26 * to be very fast. Enqueueing and dequeueing are both O(log(N)) operatoins
27 * whereas peeking is constant time.
28 *
29 * This heap implementation allows iterating, however please note that any
30 * enqueue or dequeue operation will invalidate the iterator and make it
31 * unusable (if it still works, you shouldn't trust the results). Also,
32 * the items are not stored in memory in order, they are optomized into a
33 * tree. This means that the items will be in effectively random order
34 * while iterating through them, and the order cannot be trusted. Also,
35 * modifying an item in the heap will not cause that item to be re-sorted.
36 * If you want to change the position of an item in the heap you will have
37 * to dequeue every item before it, dequeue that item, change it, and
38 * re-enqueue all of the items removed.
39 */
21 template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> > 40 template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> >
22 class Heap : public Queue<item> 41 class Heap : public Queue<item>
23 { 42 {
@@ -165,29 +184,306 @@ namespace Bu
165 return iFill; 184 return iFill;
166 } 185 }
167 186
168 /* 187 class iterator
169 void print( class Formatter &f )
170 { 188 {
171 f << "graph G {" << "\n"; 189 friend class const_iterator;
172 for( int j = 0; j < iFill; j++ ) 190 friend class Heap<item, cmpfunc, itemalloc>;
191 private:
192 Heap<item, cmpfunc, itemalloc> *pHeap;
193 int iIndex;
194
195 iterator( Heap<item, cmpfunc, itemalloc> *pHeap, int iIndex ) :
196 pHeap( pHeap ), iIndex( iIndex )
173 { 197 {
174 if( j*2+1 < iFill )
175 f << " " << j << " -- " << j*2+1 << ";" << "\n";
176 if( j*2+2 < iFill )
177 f << " " << j << " -- " << j*2+2 << ";" << "\n";
178 } 198 }
179 for( int j = 0; j < iFill; j++ ) 199
200 void checkValid()
201 {
202 if( pHeap == NULL )
203 throw Bu::ExceptionBase("Iterator not initialized.");
204 if( iIndex < 0 || iIndex >= pHeap->iFill )
205 throw Bu::ExceptionBase("Iterator out of bounds.");
206 }
207
208 public:
209 iterator() :
210 pHeap( NULL ),
211 iIndex( -1 )
212 {
213 }
214
215 iterator( const iterator &i ) :
216 pHeap( i.pHeap ),
217 iIndex( i.iIndex )
218 {
219 }
220
221 bool operator==( const iterator &oth ) const
222 {
223 return (oth.pHeap == pHeap) && (oth.iIndex == iIndex);
224 }
225
226 bool operator!=( const iterator &oth ) const
227 {
228 return (oth.pHeap != pHeap) || (oth.iIndex != iIndex);
229 }
230
231 item &operator*()
232 {
233 return pHeap->aItem[iIndex];
234 }
235
236 item *operator->()
237 {
238 return &(pHeap->aItem[iIndex]);
239 }
240
241 iterator &operator++()
242 {
243 checkValid();
244 iIndex++;
245 if( iIndex >= pHeap->iFill )
246 iIndex = -1;
247
248 return *this;
249 }
250
251 iterator &operator--()
252 {
253 checkValid();
254 iIndex--;
255
256 return *this;
257 }
258
259 iterator &operator++( int )
180 { 260 {
181 f << " " << j << " [label=\"" << aItem[j] << "\"];" << "\n"; 261 checkValid();
262 iIndex++;
263 if( iIndex >= pHeap->iFill )
264 iIndex = -1;
265
266 return *this;
267 }
268
269 iterator &operator--( int )
270 {
271 checkValid();
272 iIndex--;
273
274 return *this;
275 }
276
277 iterator operator+( int iDelta )
278 {
279 checkValid();
280 iterator ret( *this );
281 ret.iIndex += iDelta;
282 if( ret.iIndex >= pHeap->iFill )
283 ret.iIndex = -1;
284 return ret;
285 }
286
287 iterator operator-( int iDelta )
288 {
289 checkValid();
290 iterator ret( *this );
291 ret.iIndex -= iDelta;
292 if( ret.iIndex < 0 )
293 ret.iIndex = -1;
294 return ret;
295 }
296
297 operator bool()
298 {
299 return iIndex != -1;
300 }
301
302 bool isValid()
303 {
304 return iIndex != -1;
305 }
306
307 iterator &operator=( const iterator &oth )
308 {
309 pHeap = oth.pHeap;
310 iIndex = oth.iIndex;
311 }
312 };
313
314 class const_iterator
315 {
316 friend class Heap<item, cmpfunc, itemalloc>;
317 private:
318 Heap<item, cmpfunc, itemalloc> *pHeap;
319 int iIndex;
320
321 const_iterator( Heap<item, cmpfunc, itemalloc> *pHeap,
322 int iIndex ) :
323 pHeap( pHeap ), iIndex( iIndex )
324 {
325 }
326
327 void checkValid()
328 {
329 if( pHeap == NULL )
330 throw Bu::ExceptionBase("Iterator not initialized.");
331 if( iIndex < 0 || iIndex >= pHeap->iFill )
332 throw Bu::ExceptionBase("Iterator out of bounds.");
182 } 333 }
183 f << "}" << "\n"; 334
184 } */ 335 public:
336 const_iterator() :
337 pHeap( NULL ),
338 iIndex( -1 )
339 {
340 }
341
342 const_iterator( const const_iterator &i ) :
343 pHeap( i.pHeap ),
344 iIndex( i.iIndex )
345 {
346 }
347
348 const_iterator( const iterator &i ) :
349 pHeap( i.pHeap ),
350 iIndex( i.iIndex )
351 {
352 }
353
354 bool operator==( const const_iterator &oth ) const
355 {
356 return (oth.pHeap == pHeap) && (oth.iIndex == iIndex);
357 }
358
359 bool operator!=( const const_iterator &oth ) const
360 {
361 return (oth.pHeap != pHeap) || (oth.iIndex != iIndex);
362 }
363
364 const item &operator*()
365 {
366 return pHeap->aItem[iIndex];
367 }
368
369 const item *operator->()
370 {
371 return &(pHeap->aItem[iIndex]);
372 }
373
374 const_iterator &operator++()
375 {
376 checkValid();
377 iIndex++;
378 if( iIndex >= pHeap->iFill )
379 iIndex = -1;
380
381 return *this;
382 }
383
384 const_iterator &operator--()
385 {
386 checkValid();
387 iIndex--;
388
389 return *this;
390 }
391
392 const_iterator &operator++( int )
393 {
394 checkValid();
395 iIndex++;
396 if( iIndex >= pHeap->iFill )
397 iIndex = -1;
398
399 return *this;
400 }
401
402 const_iterator &operator--( int )
403 {
404 checkValid();
405 iIndex--;
406
407 return *this;
408 }
409
410 const_iterator operator+( int iDelta )
411 {
412 checkValid();
413 const_iterator ret( *this );
414 ret.iIndex += iDelta;
415 if( ret.iIndex >= pHeap->iFill )
416 ret.iIndex = -1;
417 return ret;
418 }
419
420 const_iterator operator-( int iDelta )
421 {
422 checkValid();
423 const_iterator ret( *this );
424 ret.iIndex -= iDelta;
425 if( ret.iIndex < 0 )
426 ret.iIndex = -1;
427 return ret;
428 }
429
430 operator bool()
431 {
432 return iIndex != -1;
433 }
434
435 bool isValid()
436 {
437 return iIndex != -1;
438 }
439
440 const_iterator &operator=( const const_iterator &oth )
441 {
442 pHeap = oth.pHeap;
443 iIndex = oth.iIndex;
444 }
445
446 const_iterator &operator=( const iterator &oth )
447 {
448 pHeap = oth.pHeap;
449 iIndex = oth.iIndex;
450 }
451 };
452
453 iterator begin()
454 {
455 if( iFill == 0 )
456 return end();
457 return iterator( this, 0 );
458 }
459
460 const_iterator begin() const
461 {
462 if( iFill == 0 )
463 return end();
464 return const_iterator( this, 0 );
465 }
466
467 iterator end()
468 {
469 return iterator( this, -1 );
470 }
471
472 const_iterator end() const
473 {
474 return const_iterator( this, -1 );
475 }
476
185 477
186 private: 478 private:
187 void upSize() 479 void upSize()
188 { 480 {
189 item *aNewItems = ia.allocate( iSize*2+1 ); 481 item *aNewItems = ia.allocate( iSize*2+1 );
190// memcpy( aNewItems, aItem, sizeof(item)*iFill ); 482 //
483 // We cannot use a memcopy here because we don't know what kind
484 // of datastructures are being used, we have to copy them one at
485 // a time.
486 //
191 for( int j = 0; j < iFill; j++ ) 487 for( int j = 0; j < iFill; j++ )
192 { 488 {
193 ia.construct( &aNewItems[j], aItem[j] ); 489 ia.construct( &aNewItems[j], aItem[j] );
diff --git a/src/minicron.cpp b/src/minicron.cpp
index 8aace26..491d143 100644
--- a/src/minicron.cpp
+++ b/src/minicron.cpp
@@ -35,6 +35,18 @@ time_t Bu::MiniCron::getNextRun()
35 return -1; 35 return -1;
36} 36}
37 37
38time_t Bu::MiniCron::getNextRun( Bu::MiniCron::JobId jid )
39{
40 for( JobHeap::iterator i = hJobs.begin(); i; i++ )
41 {
42 if( (*i)->getId() == jid )
43 {
44 return (*i)->getNextRunTime();
45 }
46 }
47 return -1;
48}
49
38void Bu::MiniCron::poll() 50void Bu::MiniCron::poll()
39{ 51{
40 time_t tNow = time( NULL ); 52 time_t tNow = time( NULL );
@@ -61,11 +73,11 @@ void Bu::MiniCron::poll()
61 } 73 }
62} 74}
63 75
64Bu::MiniCron::JobId Bu::MiniCron::addJob( Bu::MiniCron::CronSignal sigJob, 76Bu::MiniCron::JobId Bu::MiniCron::addJob( const Bu::FString &sName,
65 const Bu::MiniCron::Timer &t ) 77 Bu::MiniCron::CronSignal sigJob, const Bu::MiniCron::Timer &t )
66{ 78{
67 JobId jid = jidNext++; 79 JobId jid = jidNext++;
68 Job *pJob = new Job( jid ); 80 Job *pJob = new Job( sName, jid );
69 pJob->sigJob = sigJob; 81 pJob->sigJob = sigJob;
70 pJob->pTimer = t.clone(); 82 pJob->pTimer = t.clone();
71 pJob->tNextRun = pJob->pTimer->nextTime(); 83 pJob->tNextRun = pJob->pTimer->nextTime();
@@ -74,11 +86,11 @@ Bu::MiniCron::JobId Bu::MiniCron::addJob( Bu::MiniCron::CronSignal sigJob,
74 return jid; 86 return jid;
75} 87}
76 88
77Bu::MiniCron::JobId Bu::MiniCron::addJobOnce( Bu::MiniCron::CronSignal sigJob, 89Bu::MiniCron::JobId Bu::MiniCron::addJobOnce( const Bu::FString &sName,
78 const Bu::MiniCron::Timer &t ) 90 Bu::MiniCron::CronSignal sigJob, const Bu::MiniCron::Timer &t )
79{ 91{
80 JobId jid = jidNext++; 92 JobId jid = jidNext++;
81 Job *pJob = new Job( jid, false ); 93 Job *pJob = new Job( sName, jid, false );
82 pJob->sigJob = sigJob; 94 pJob->sigJob = sigJob;
83 pJob->pTimer = t.clone(); 95 pJob->pTimer = t.clone();
84 pJob->tNextRun = pJob->pTimer->nextTime(); 96 pJob->tNextRun = pJob->pTimer->nextTime();
@@ -107,7 +119,21 @@ void Bu::MiniCron::removeJob( JobId jid )
107 } 119 }
108} 120}
109 121
110Bu::MiniCron::Job::Job( JobId jid, bool bRepeat ) : 122Bu::MiniCron::JobInfoList Bu::MiniCron::getJobInfo()
123{
124 JobInfoList lRet;
125 for( JobHeap::iterator i = hJobs.begin(); i; i++ )
126 {
127 lRet.append(
128 JobInfo( (*i)->getName(), (*i)->getId(), (*i)->getNextRun() )
129 );
130 }
131 lRet.sort();
132 return lRet;
133}
134
135Bu::MiniCron::Job::Job( const Bu::FString &sName, JobId jid, bool bRepeat ) :
136 sName( sName ),
111 pTimer( NULL ), 137 pTimer( NULL ),
112 bContinue( bRepeat ), 138 bContinue( bRepeat ),
113 jid( jid ), 139 jid( jid ),
@@ -129,7 +155,7 @@ void Bu::MiniCron::Job::run()
129 sigJob( *this ); 155 sigJob( *this );
130} 156}
131 157
132time_t Bu::MiniCron::Job::getNextRun() 158time_t Bu::MiniCron::Job::getNextRun() const
133{ 159{
134 return tNextRun; 160 return tNextRun;
135} 161}
@@ -156,21 +182,48 @@ void Bu::MiniCron::Job::resume()
156 bContinue = true; 182 bContinue = true;
157} 183}
158 184
159Bu::MiniCron::JobId Bu::MiniCron::Job::getId() 185Bu::MiniCron::JobId Bu::MiniCron::Job::getId() const
160{ 186{
161 return jid; 187 return jid;
162} 188}
163 189
164time_t Bu::MiniCron::Job::getTimeCreated() 190time_t Bu::MiniCron::Job::getTimeCreated() const
165{ 191{
166 return tAdded; 192 return tAdded;
167} 193}
168 194
169int Bu::MiniCron::Job::getRunCount() 195int Bu::MiniCron::Job::getRunCount() const
170{ 196{
171 return iRunCount; 197 return iRunCount;
172} 198}
173 199
200time_t Bu::MiniCron::Job::getNextRunTime() const
201{
202 return tNextRun;
203}
204
205Bu::FString Bu::MiniCron::Job::getName() const
206{
207 return sName;
208}
209
210Bu::MiniCron::JobInfo::JobInfo( const Bu::FString &sName, JobId jid,
211 time_t tNext ) :
212 sName( sName ),
213 jid( jid ),
214 tNext( tNext )
215{
216}
217
218Bu::MiniCron::JobInfo::~JobInfo()
219{
220}
221
222bool Bu::MiniCron::JobInfo::operator<( const JobInfo &rhs ) const
223{
224 return jid < rhs.jid;
225}
226
174Bu::MiniCron::Timer::Timer() 227Bu::MiniCron::Timer::Timer()
175{ 228{
176} 229}
diff --git a/src/minicron.h b/src/minicron.h
index 7475020..b045e79 100644
--- a/src/minicron.h
+++ b/src/minicron.h
@@ -66,6 +66,12 @@ namespace Bu
66 *@returns The timestamp that the next job will execute at. 66 *@returns The timestamp that the next job will execute at.
67 */ 67 */
68 virtual time_t getNextRun(); 68 virtual time_t getNextRun();
69
70 /**
71 * Tells you the time the job matching jid will run next.
72 *@returns The timestamp that the job jid will next run.
73 */
74 virtual time_t getNextRun( JobId jid );
69 75
70 /** 76 /**
71 * Call this regularly to execute all jobs that should be executed. 77 * Call this regularly to execute all jobs that should be executed.
@@ -83,7 +89,8 @@ namespace Bu
83 * JobId which can be used at a later time to control the execution of 89 * JobId which can be used at a later time to control the execution of
84 * the job. 90 * the job.
85 */ 91 */
86 virtual JobId addJob( CronSignal sigJob, const Timer &t ); 92 virtual JobId addJob( const Bu::FString &sName, CronSignal sigJob,
93 const Timer &t );
87 94
88 /** 95 /**
89 * Add a job for one time scheduling. Pass in a slot to signal, and a 96 * Add a job for one time scheduling. Pass in a slot to signal, and a
@@ -91,7 +98,8 @@ namespace Bu
91 * function returns a JobId which can be used at a later time to control 98 * function returns a JobId which can be used at a later time to control
92 * the execution of the job. 99 * the execution of the job.
93 */ 100 */
94 virtual JobId addJobOnce( CronSignal sigJob, const Timer &t ); 101 virtual JobId addJobOnce( const Bu::FString &sName, CronSignal sigJob,
102 const Timer &t );
95 103
96 /** 104 /**
97 * Remove a job, preventing all future runs of the job. If there is no 105 * Remove a job, preventing all future runs of the job. If there is no
@@ -102,6 +110,22 @@ namespace Bu
102 */ 110 */
103 virtual void removeJob( JobId jid ); 111 virtual void removeJob( JobId jid );
104 112
113 class JobInfo
114 {
115 public:
116 JobInfo( const Bu::FString &sName, JobId jid, time_t tNext );
117 virtual ~JobInfo();
118
119 bool operator<( const JobInfo &rhs ) const;
120
121 Bu::FString sName;
122 JobId jid;
123 time_t tNext;
124 };
125 typedef Bu::List<JobInfo> JobInfoList;
126
127 JobInfoList getJobInfo();
128
105 /** 129 /**
106 * The baseclass for timer/schedulers for MiniCron jobs. Classes that 130 * The baseclass for timer/schedulers for MiniCron jobs. Classes that
107 * inherit from this are used to determine when jobs will run and at 131 * inherit from this are used to determine when jobs will run and at
@@ -201,7 +225,7 @@ namespace Bu
201 { 225 {
202 friend class Bu::MiniCron; 226 friend class Bu::MiniCron;
203 private: 227 private:
204 Job( JobId jid, bool bRepeat=true ); 228 Job( const Bu::FString &sName, JobId jid, bool bRepeat=true );
205 virtual ~Job(); 229 virtual ~Job();
206 230
207 public: 231 public:
@@ -215,7 +239,7 @@ namespace Bu
215 /** 239 /**
216 * Get the time this job will next run. 240 * Get the time this job will next run.
217 */ 241 */
218 time_t getNextRun(); 242 time_t getNextRun() const;
219 243
220 /** 244 /**
221 * Compute the time this job will next run. 245 * Compute the time this job will next run.
@@ -243,20 +267,33 @@ namespace Bu
243 /** 267 /**
244 * Get the unique ID of this job. 268 * Get the unique ID of this job.
245 */ 269 */
246 JobId getId(); 270 JobId getId() const;
247 271
248 /** 272 /**
249 * Get the timestamp this job was created. 273 * Get the timestamp this job was created.
250 */ 274 */
251 time_t getTimeCreated(); 275 time_t getTimeCreated() const;
252 276
253 /** 277 /**
254 * Get the current run count of this job, how many times it has been 278 * Get the current run count of this job, how many times it has been
255 * executed. This is incremented before the slot is signaled. 279 * executed. This is incremented before the slot is signaled.
256 */ 280 */
257 int getRunCount(); 281 int getRunCount() const;
282
283 /**
284 * Get the next time that this job will be run. Certain timers may
285 * have the ability to delay job executions, so this is the earliest
286 * time that the job may run.
287 */
288 time_t getNextRunTime() const;
289
290 /**
291 * Gets the name that was set when the job was created.
292 */
293 Bu::FString getName() const;
258 294
259 private: 295 private:
296 Bu::FString sName;
260 CronSignal sigJob; 297 CronSignal sigJob;
261 time_t tNextRun; 298 time_t tNextRun;
262 Timer *pTimer; 299 Timer *pTimer;
diff --git a/src/tests/heap.cpp b/src/tests/heap.cpp
index 6f68598..7538936 100644
--- a/src/tests/heap.cpp
+++ b/src/tests/heap.cpp
@@ -38,14 +38,19 @@ typedef struct num
38 } 38 }
39} num; 39} num;
40 40
41void printHeap( Bu::Heap<Bu::FString> &/*h*/, int j ) 41void printHeap( Bu::Heap<Bu::FString> &h, int j )
42{ 42{
43 return; 43// return;
44 Bu::FString sFName; 44 Bu::FString sFName;
45 sFName.format("graph-step-%02d.dot", j ); 45 sFName.format("graph-step-%02d.dot", j );
46 Bu::File fOut( sFName, Bu::File::WriteNew ); 46 Bu::File fOut( sFName, Bu::File::WriteNew );
47 Bu::Formatter f( fOut ); 47 Bu::Formatter f( fOut );
48// h.print( f ); 48 f << "Graph step: " << j << ", total size: " << h.getSize() << f.nl;
49 for( Bu::Heap<Bu::FString>::iterator i = h.begin(); i; i++ )
50 {
51 f << *i << f.nl;
52 }
53 f << f.nl;
49} 54}
50 55
51int main() 56int main()
diff --git a/src/tests/minicron.cpp b/src/tests/minicron.cpp
index 8abf8ad..0749f90 100644
--- a/src/tests/minicron.cpp
+++ b/src/tests/minicron.cpp
@@ -41,11 +41,14 @@ void job3( Bu::MiniCron::Job &job )
41 41
42int main() 42int main()
43{ 43{
44 44 mCron.addJob(
45 mCron.addJob( slot( &job0 ), MiniCron::TimerInterval( time(NULL)+3, 5 ) ); 45 "job0", slot( &job0 ), MiniCron::TimerInterval( time(NULL)+3, 5 ) );
46 mCron.addJob( slot( &job1 ), MiniCron::TimerInterval( time(NULL)+10, 8 ) ); 46 mCron.addJob(
47 mCron.addJob( slot( &job2 ), MiniCron::TimerBasic("weekly wed 17") ); 47 "job1", slot( &job1 ), MiniCron::TimerInterval( time(NULL)+10, 8 ) );
48 mCron.addJob( slot( &job3 ), MiniCron::TimerInterval( time(NULL)+1, 2 ) ); 48 mCron.addJob(
49 "job2", slot( &job2 ), MiniCron::TimerBasic("weekly wed 17") );
50 mCron.addJob(
51 "job3", slot( &job3 ), MiniCron::TimerInterval( time(NULL)+1, 2 ) );
49 52
50 sio << time( NULL ) << ": Program started." << sio.nl; 53 sio << time( NULL ) << ": Program started." << sio.nl;
51 54