diff options
Diffstat (limited to 'src/sim/eventq.hh')
-rw-r--r-- | src/sim/eventq.hh | 132 |
1 files changed, 97 insertions, 35 deletions
diff --git a/src/sim/eventq.hh b/src/sim/eventq.hh index ea950e625..10c0048a8 100644 --- a/src/sim/eventq.hh +++ b/src/sim/eventq.hh @@ -74,7 +74,20 @@ class Event : public Serializable, public FastAlloc friend class EventQueue; private: - Event *next; + // The event queue is now a linked list of linked lists. The + // 'nextBin' pointer is to find the bin, where a bin is defined as + // when+priority. All events in the same bin will be stored in a + // second circularly linked list maintained by the 'nextInBin' + // pointer. The list will be accessed in FIFO order. The end + // result is that the insert/removal in 'nextBin' is + // linear/constant, and the lookup/removal in 'nextInBin' is + // constant/constant. Hopefully this is a significant improvement + // over the current fully linear insertion. + Event *nextBin; + Event *nextInBin; + + friend void insertBefore(Event *event, Event *curr); + friend Event *removeItem(Event *event, Event *last); /// queue to which this event belongs (though it may or may not be /// scheduled on this queue yet) @@ -99,6 +112,17 @@ class Event : public Serializable, public FastAlloc Tick whenCreated; //!< time created Tick whenScheduled; //!< time scheduled #endif + + protected: + void + setWhen(Tick when) + { + _when = when; +#ifdef DEBUG_EVENTQ + whenScheduled = curTick; +#endif + } + protected: enum Flags { None = 0x0, @@ -181,7 +205,7 @@ class Event : public Serializable, public FastAlloc * @param queue that the event gets scheduled on */ Event(EventQueue *q, Priority p = Default_Pri) - : next(NULL), _queue(q), _priority(p), _flags(None) + : nextBin(NULL), nextInBin(NULL), _queue(q), _priority(p), _flags(None) { #ifndef NDEBUG instance = ++instanceCounter; @@ -343,9 +367,9 @@ class EventQueue : public Serializable virtual const std::string name() const { return objName; } // schedule the given event on this queue - void schedule(Event *ev); + void schedule(Event *ev, Tick when); void deschedule(Event *ev); - void reschedule(Event *ev); + void reschedule(Event *ev, Tick when); Tick nextTick() const { return head->when(); } Event *serviceOne(); @@ -379,6 +403,8 @@ class EventQueue : public Serializable Tick nextEventTime() { return empty() ? curTick : head->when(); } + bool debugVerify() const; + virtual void serialize(std::ostream &os); virtual void unserialize(Checkpoint *cp, const std::string §ion); }; @@ -396,53 +422,77 @@ class EventQueue : public Serializable // schedule at specified time (place on event queue specified via // constructor) inline void -Event::schedule(Tick t) +Event::schedule(Tick when) { - assert(!scheduled()); - assert(t >= curTick); - - setFlags(Scheduled); -#ifdef DEBUG_EVENTQ - whenScheduled = curTick; -#endif - _when = t; - _queue->schedule(this); + _queue->schedule(this, when); } inline void Event::deschedule() { - assert(scheduled()); - - clearFlags(Squashed); - clearFlags(Scheduled); _queue->deschedule(this); } inline void -Event::reschedule(Tick t, bool always) +Event::reschedule(Tick when, bool always) { - assert(scheduled() || always); - assert(t >= curTick); - -#ifdef DEBUG_EVENTQ - whenScheduled = curTick; -#endif - _when = t; - if (scheduled()) { - clearFlags(Squashed); - _queue->reschedule(this); + _queue->reschedule(this, when); } else { - setFlags(Scheduled); - _queue->schedule(this); + assert(always); + _queue->schedule(this, when); } } +inline bool +operator<(const Event &l, const Event &r) +{ + return l.when() < r.when() || + (l.when() == r.when() && l.priority() < r.priority()); +} + +inline bool +operator>(const Event &l, const Event &r) +{ + return l.when() > r.when() || + (l.when() == r.when() && l.priority() > r.priority()); +} + +inline bool +operator<=(const Event &l, const Event &r) +{ + return l.when() < r.when() || + (l.when() == r.when() && l.priority() <= r.priority()); +} +inline bool +operator>=(const Event &l, const Event &r) +{ + return l.when() > r.when() || + (l.when() == r.when() && l.priority() >= r.priority()); +} + +inline bool +operator==(const Event &l, const Event &r) +{ + return l.when() == r.when() && l.priority() == r.priority(); +} + +inline bool +operator!=(const Event &l, const Event &r) +{ + return l.when() != r.when() || l.priority() != r.priority(); +} + inline void -EventQueue::schedule(Event *event) +EventQueue::schedule(Event *event, Tick when) { + assert(when >= curTick); + assert(!event->scheduled()); + + event->setWhen(when); insert(event); + event->setFlags(Event::Scheduled); + if (DTRACE(Event)) event->trace("scheduled"); } @@ -450,19 +500,31 @@ EventQueue::schedule(Event *event) inline void EventQueue::deschedule(Event *event) { + assert(event->scheduled()); + remove(event); - if (DTRACE(Event)) - event->trace("descheduled"); + + event->clearFlags(Event::Squashed); + event->clearFlags(Event::Scheduled); if (event->getFlags(Event::AutoDelete)) delete event; + + if (DTRACE(Event)) + event->trace("descheduled"); } inline void -EventQueue::reschedule(Event *event) +EventQueue::reschedule(Event *event, Tick when) { + assert(when >= curTick); + assert(event->scheduled()); + remove(event); + event->setWhen(when); insert(event); + event->clearFlags(Event::Squashed); + if (DTRACE(Event)) event->trace("rescheduled"); } |