From 313e28df2a8776c82f5493aef6fe44ad40f1935a Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Wed, 6 Oct 2010 07:01:28 +0000 Subject: Changed the Bu::Heap to allow iteration, and added lots of cool features to Bu::MiniCron. --- src/heap.h | 322 +++++++++++++++++++++++++++++++++++++++++++++++-- src/minicron.cpp | 75 ++++++++++-- src/minicron.h | 51 ++++++-- src/tests/heap.cpp | 11 +- src/tests/minicron.cpp | 13 +- 5 files changed, 433 insertions(+), 39 deletions(-) (limited to 'src') 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 { subExceptionDecl( HeapException ); + /** + * A priority queue that allows for an unlimited number of priorities. All + * objects enqueued must support less-than-comparison. Then every time an + * item is dequeued it is always the least item in the heap. The heap + * operates using a binary tree for storage, which allows most operations + * to be very fast. Enqueueing and dequeueing are both O(log(N)) operatoins + * whereas peeking is constant time. + * + * This heap implementation allows iterating, however please note that any + * enqueue or dequeue operation will invalidate the iterator and make it + * unusable (if it still works, you shouldn't trust the results). Also, + * the items are not stored in memory in order, they are optomized into a + * tree. This means that the items will be in effectively random order + * while iterating through them, and the order cannot be trusted. Also, + * modifying an item in the heap will not cause that item to be re-sorted. + * If you want to change the position of an item in the heap you will have + * to dequeue every item before it, dequeue that item, change it, and + * re-enqueue all of the items removed. + */ template, typename itemalloc=std::allocator > class Heap : public Queue { @@ -165,29 +184,306 @@ namespace Bu return iFill; } - /* - void print( class Formatter &f ) + class iterator { - f << "graph G {" << "\n"; - for( int j = 0; j < iFill; j++ ) + friend class const_iterator; + friend class Heap; + private: + Heap *pHeap; + int iIndex; + + iterator( Heap *pHeap, int iIndex ) : + pHeap( pHeap ), iIndex( iIndex ) { - if( j*2+1 < iFill ) - f << " " << j << " -- " << j*2+1 << ";" << "\n"; - if( j*2+2 < iFill ) - f << " " << j << " -- " << j*2+2 << ";" << "\n"; } - for( int j = 0; j < iFill; j++ ) + + void checkValid() + { + if( pHeap == NULL ) + throw Bu::ExceptionBase("Iterator not initialized."); + if( iIndex < 0 || iIndex >= pHeap->iFill ) + throw Bu::ExceptionBase("Iterator out of bounds."); + } + + public: + iterator() : + pHeap( NULL ), + iIndex( -1 ) + { + } + + iterator( const iterator &i ) : + pHeap( i.pHeap ), + iIndex( i.iIndex ) + { + } + + bool operator==( const iterator &oth ) const + { + return (oth.pHeap == pHeap) && (oth.iIndex == iIndex); + } + + bool operator!=( const iterator &oth ) const + { + return (oth.pHeap != pHeap) || (oth.iIndex != iIndex); + } + + item &operator*() + { + return pHeap->aItem[iIndex]; + } + + item *operator->() + { + return &(pHeap->aItem[iIndex]); + } + + iterator &operator++() + { + checkValid(); + iIndex++; + if( iIndex >= pHeap->iFill ) + iIndex = -1; + + return *this; + } + + iterator &operator--() + { + checkValid(); + iIndex--; + + return *this; + } + + iterator &operator++( int ) { - f << " " << j << " [label=\"" << aItem[j] << "\"];" << "\n"; + checkValid(); + iIndex++; + if( iIndex >= pHeap->iFill ) + iIndex = -1; + + return *this; + } + + iterator &operator--( int ) + { + checkValid(); + iIndex--; + + return *this; + } + + iterator operator+( int iDelta ) + { + checkValid(); + iterator ret( *this ); + ret.iIndex += iDelta; + if( ret.iIndex >= pHeap->iFill ) + ret.iIndex = -1; + return ret; + } + + iterator operator-( int iDelta ) + { + checkValid(); + iterator ret( *this ); + ret.iIndex -= iDelta; + if( ret.iIndex < 0 ) + ret.iIndex = -1; + return ret; + } + + operator bool() + { + return iIndex != -1; + } + + bool isValid() + { + return iIndex != -1; + } + + iterator &operator=( const iterator &oth ) + { + pHeap = oth.pHeap; + iIndex = oth.iIndex; + } + }; + + class const_iterator + { + friend class Heap; + private: + Heap *pHeap; + int iIndex; + + const_iterator( Heap *pHeap, + int iIndex ) : + pHeap( pHeap ), iIndex( iIndex ) + { + } + + void checkValid() + { + if( pHeap == NULL ) + throw Bu::ExceptionBase("Iterator not initialized."); + if( iIndex < 0 || iIndex >= pHeap->iFill ) + throw Bu::ExceptionBase("Iterator out of bounds."); } - f << "}" << "\n"; - } */ + + public: + const_iterator() : + pHeap( NULL ), + iIndex( -1 ) + { + } + + const_iterator( const const_iterator &i ) : + pHeap( i.pHeap ), + iIndex( i.iIndex ) + { + } + + const_iterator( const iterator &i ) : + pHeap( i.pHeap ), + iIndex( i.iIndex ) + { + } + + bool operator==( const const_iterator &oth ) const + { + return (oth.pHeap == pHeap) && (oth.iIndex == iIndex); + } + + bool operator!=( const const_iterator &oth ) const + { + return (oth.pHeap != pHeap) || (oth.iIndex != iIndex); + } + + const item &operator*() + { + return pHeap->aItem[iIndex]; + } + + const item *operator->() + { + return &(pHeap->aItem[iIndex]); + } + + const_iterator &operator++() + { + checkValid(); + iIndex++; + if( iIndex >= pHeap->iFill ) + iIndex = -1; + + return *this; + } + + const_iterator &operator--() + { + checkValid(); + iIndex--; + + return *this; + } + + const_iterator &operator++( int ) + { + checkValid(); + iIndex++; + if( iIndex >= pHeap->iFill ) + iIndex = -1; + + return *this; + } + + const_iterator &operator--( int ) + { + checkValid(); + iIndex--; + + return *this; + } + + const_iterator operator+( int iDelta ) + { + checkValid(); + const_iterator ret( *this ); + ret.iIndex += iDelta; + if( ret.iIndex >= pHeap->iFill ) + ret.iIndex = -1; + return ret; + } + + const_iterator operator-( int iDelta ) + { + checkValid(); + const_iterator ret( *this ); + ret.iIndex -= iDelta; + if( ret.iIndex < 0 ) + ret.iIndex = -1; + return ret; + } + + operator bool() + { + return iIndex != -1; + } + + bool isValid() + { + return iIndex != -1; + } + + const_iterator &operator=( const const_iterator &oth ) + { + pHeap = oth.pHeap; + iIndex = oth.iIndex; + } + + const_iterator &operator=( const iterator &oth ) + { + pHeap = oth.pHeap; + iIndex = oth.iIndex; + } + }; + + iterator begin() + { + if( iFill == 0 ) + return end(); + return iterator( this, 0 ); + } + + const_iterator begin() const + { + if( iFill == 0 ) + return end(); + return const_iterator( this, 0 ); + } + + iterator end() + { + return iterator( this, -1 ); + } + + const_iterator end() const + { + return const_iterator( this, -1 ); + } + private: void upSize() { item *aNewItems = ia.allocate( iSize*2+1 ); -// memcpy( aNewItems, aItem, sizeof(item)*iFill ); + // + // We cannot use a memcopy here because we don't know what kind + // of datastructures are being used, we have to copy them one at + // a time. + // for( int j = 0; j < iFill; j++ ) { 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() return -1; } +time_t Bu::MiniCron::getNextRun( Bu::MiniCron::JobId jid ) +{ + for( JobHeap::iterator i = hJobs.begin(); i; i++ ) + { + if( (*i)->getId() == jid ) + { + return (*i)->getNextRunTime(); + } + } + return -1; +} + void Bu::MiniCron::poll() { time_t tNow = time( NULL ); @@ -61,11 +73,11 @@ void Bu::MiniCron::poll() } } -Bu::MiniCron::JobId Bu::MiniCron::addJob( Bu::MiniCron::CronSignal sigJob, - const Bu::MiniCron::Timer &t ) +Bu::MiniCron::JobId Bu::MiniCron::addJob( const Bu::FString &sName, + Bu::MiniCron::CronSignal sigJob, const Bu::MiniCron::Timer &t ) { JobId jid = jidNext++; - Job *pJob = new Job( jid ); + Job *pJob = new Job( sName, jid ); pJob->sigJob = sigJob; pJob->pTimer = t.clone(); pJob->tNextRun = pJob->pTimer->nextTime(); @@ -74,11 +86,11 @@ Bu::MiniCron::JobId Bu::MiniCron::addJob( Bu::MiniCron::CronSignal sigJob, return jid; } -Bu::MiniCron::JobId Bu::MiniCron::addJobOnce( Bu::MiniCron::CronSignal sigJob, - const Bu::MiniCron::Timer &t ) +Bu::MiniCron::JobId Bu::MiniCron::addJobOnce( const Bu::FString &sName, + Bu::MiniCron::CronSignal sigJob, const Bu::MiniCron::Timer &t ) { JobId jid = jidNext++; - Job *pJob = new Job( jid, false ); + Job *pJob = new Job( sName, jid, false ); pJob->sigJob = sigJob; pJob->pTimer = t.clone(); pJob->tNextRun = pJob->pTimer->nextTime(); @@ -107,7 +119,21 @@ void Bu::MiniCron::removeJob( JobId jid ) } } -Bu::MiniCron::Job::Job( JobId jid, bool bRepeat ) : +Bu::MiniCron::JobInfoList Bu::MiniCron::getJobInfo() +{ + JobInfoList lRet; + for( JobHeap::iterator i = hJobs.begin(); i; i++ ) + { + lRet.append( + JobInfo( (*i)->getName(), (*i)->getId(), (*i)->getNextRun() ) + ); + } + lRet.sort(); + return lRet; +} + +Bu::MiniCron::Job::Job( const Bu::FString &sName, JobId jid, bool bRepeat ) : + sName( sName ), pTimer( NULL ), bContinue( bRepeat ), jid( jid ), @@ -129,7 +155,7 @@ void Bu::MiniCron::Job::run() sigJob( *this ); } -time_t Bu::MiniCron::Job::getNextRun() +time_t Bu::MiniCron::Job::getNextRun() const { return tNextRun; } @@ -156,21 +182,48 @@ void Bu::MiniCron::Job::resume() bContinue = true; } -Bu::MiniCron::JobId Bu::MiniCron::Job::getId() +Bu::MiniCron::JobId Bu::MiniCron::Job::getId() const { return jid; } -time_t Bu::MiniCron::Job::getTimeCreated() +time_t Bu::MiniCron::Job::getTimeCreated() const { return tAdded; } -int Bu::MiniCron::Job::getRunCount() +int Bu::MiniCron::Job::getRunCount() const { return iRunCount; } +time_t Bu::MiniCron::Job::getNextRunTime() const +{ + return tNextRun; +} + +Bu::FString Bu::MiniCron::Job::getName() const +{ + return sName; +} + +Bu::MiniCron::JobInfo::JobInfo( const Bu::FString &sName, JobId jid, + time_t tNext ) : + sName( sName ), + jid( jid ), + tNext( tNext ) +{ +} + +Bu::MiniCron::JobInfo::~JobInfo() +{ +} + +bool Bu::MiniCron::JobInfo::operator<( const JobInfo &rhs ) const +{ + return jid < rhs.jid; +} + Bu::MiniCron::Timer::Timer() { } 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 *@returns The timestamp that the next job will execute at. */ virtual time_t getNextRun(); + + /** + * Tells you the time the job matching jid will run next. + *@returns The timestamp that the job jid will next run. + */ + virtual time_t getNextRun( JobId jid ); /** * Call this regularly to execute all jobs that should be executed. @@ -83,7 +89,8 @@ namespace Bu * JobId which can be used at a later time to control the execution of * the job. */ - virtual JobId addJob( CronSignal sigJob, const Timer &t ); + virtual JobId addJob( const Bu::FString &sName, CronSignal sigJob, + const Timer &t ); /** * Add a job for one time scheduling. Pass in a slot to signal, and a @@ -91,7 +98,8 @@ namespace Bu * function returns a JobId which can be used at a later time to control * the execution of the job. */ - virtual JobId addJobOnce( CronSignal sigJob, const Timer &t ); + virtual JobId addJobOnce( const Bu::FString &sName, CronSignal sigJob, + const Timer &t ); /** * Remove a job, preventing all future runs of the job. If there is no @@ -102,6 +110,22 @@ namespace Bu */ virtual void removeJob( JobId jid ); + class JobInfo + { + public: + JobInfo( const Bu::FString &sName, JobId jid, time_t tNext ); + virtual ~JobInfo(); + + bool operator<( const JobInfo &rhs ) const; + + Bu::FString sName; + JobId jid; + time_t tNext; + }; + typedef Bu::List JobInfoList; + + JobInfoList getJobInfo(); + /** * The baseclass for timer/schedulers for MiniCron jobs. Classes that * inherit from this are used to determine when jobs will run and at @@ -201,7 +225,7 @@ namespace Bu { friend class Bu::MiniCron; private: - Job( JobId jid, bool bRepeat=true ); + Job( const Bu::FString &sName, JobId jid, bool bRepeat=true ); virtual ~Job(); public: @@ -215,7 +239,7 @@ namespace Bu /** * Get the time this job will next run. */ - time_t getNextRun(); + time_t getNextRun() const; /** * Compute the time this job will next run. @@ -243,20 +267,33 @@ namespace Bu /** * Get the unique ID of this job. */ - JobId getId(); + JobId getId() const; /** * Get the timestamp this job was created. */ - time_t getTimeCreated(); + time_t getTimeCreated() const; /** * Get the current run count of this job, how many times it has been * executed. This is incremented before the slot is signaled. */ - int getRunCount(); + int getRunCount() const; + + /** + * Get the next time that this job will be run. Certain timers may + * have the ability to delay job executions, so this is the earliest + * time that the job may run. + */ + time_t getNextRunTime() const; + + /** + * Gets the name that was set when the job was created. + */ + Bu::FString getName() const; private: + Bu::FString sName; CronSignal sigJob; time_t tNextRun; 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 } } num; -void printHeap( Bu::Heap &/*h*/, int j ) +void printHeap( Bu::Heap &h, int j ) { - return; +// return; Bu::FString sFName; sFName.format("graph-step-%02d.dot", j ); Bu::File fOut( sFName, Bu::File::WriteNew ); Bu::Formatter f( fOut ); -// h.print( f ); + f << "Graph step: " << j << ", total size: " << h.getSize() << f.nl; + for( Bu::Heap::iterator i = h.begin(); i; i++ ) + { + f << *i << f.nl; + } + f << f.nl; } int 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 ) int main() { - - mCron.addJob( slot( &job0 ), MiniCron::TimerInterval( time(NULL)+3, 5 ) ); - mCron.addJob( slot( &job1 ), MiniCron::TimerInterval( time(NULL)+10, 8 ) ); - mCron.addJob( slot( &job2 ), MiniCron::TimerBasic("weekly wed 17") ); - mCron.addJob( slot( &job3 ), MiniCron::TimerInterval( time(NULL)+1, 2 ) ); + mCron.addJob( + "job0", slot( &job0 ), MiniCron::TimerInterval( time(NULL)+3, 5 ) ); + mCron.addJob( + "job1", slot( &job1 ), MiniCron::TimerInterval( time(NULL)+10, 8 ) ); + mCron.addJob( + "job2", slot( &job2 ), MiniCron::TimerBasic("weekly wed 17") ); + mCron.addJob( + "job3", slot( &job3 ), MiniCron::TimerInterval( time(NULL)+1, 2 ) ); sio << time( NULL ) << ": Program started." << sio.nl; -- cgit v1.2.3