2a3
> * Copyright (c) 2008 The Hewlett-Packard Development Company
37a39
> #include "base/hashmap.hh"
57a60,84
> inline void
> insertBefore(Event *event, Event *curr)
> {
> // Either way, event will be the last element in the 'in bin' list
> // which is the pointer we need in order to look into the list, so
> // we need to insert that into the bin list.
> if (!curr || *event < *curr) {
> // Insert the event before the current list since it is in the future.
> event->nextBin = curr;
>
> // We need to create a new 'in bin' list
> event->nextInBin = event;
> } else {
> // Since we're on the correct list, we need to point to the next list
> event->nextBin = curr->nextBin; // curr->nextBin can now become stale
>
> // Insert event at the end of the 'nextInBin' curr is the last
> // element on the 'in bin' list and curr->nextInBin is the first
>
> event->nextInBin = curr->nextInBin; // event->nextInBin needs to
> // point to the first
> curr->nextInBin = event; // curr->nextInBin is now second to last
> }
> }
>
61,64c88,90
< if (head == NULL || event->when() < head->when() ||
< (event->when() == head->when() &&
< event->priority() <= head->priority())) {
< event->next = head;
---
> // Deal with the head case
> if (!head || *event <= *head) {
> insertBefore(event, head);
66,68c92,93
< } else {
< Event *prev = head;
< Event *curr = head->next;
---
> return;
> }
70,74c95,102
< while (curr) {
< if (event->when() <= curr->when() &&
< (event->when() < curr->when() ||
< event->priority() <= curr->priority()))
< break;
---
> // Figure out either which 'in bin' list we are on, or where a new list
> // needs to be inserted
> Event *curr = head;
> Event *next = head->nextBin;
> while (next && *next < *event) {
> curr = next;
> next = next->nextBin;
> }
76,78c104,107
< prev = curr;
< curr = curr->next;
< }
---
> insertBefore(event, next);
> curr->nextBin = event; // all nextBin pointers on the curr
> // 'in bin' list are now stale
> }
80,81c109,120
< event->next = curr;
< prev->next = event;
---
> inline Event *
> removeItem(Event *event, Event *last)
> {
> Event *prev = last;
> Event *curr = last->nextInBin;
>
> while (event != curr) {
> if (curr == last)
> panic("event not found!");
>
> prev = curr;
> curr = curr->nextInBin;
82a122,137
>
> // If this was the only item in this list, we're done.
> if (prev == curr)
> return NULL;
>
> // remove curr from the 'in bin' list since it's what we're looking for
> prev->nextInBin = curr->nextInBin;
>
> // If we didn't remove the last item, we're done
> if (curr != last)
> return last;
>
> // if we removed the last item, the new last item is prev
> // fix it up since it might be stale and return it
> prev->nextBin = last->nextBin;
> return prev;
89c144
< return;
---
> panic("event not found!");
91,92c146,151
< if (head == event){
< head = event->next;
---
> // deal with an event on the head's 'in bin' list (event has the same
> // time as the head)
> if (*head == *event) {
> head = removeItem(event, head);
> if (!head)
> head = event->nextBin;
95a155
> // Find the 'in bin' list that this event belongs on
97,98c157,158
< Event *curr = head->next;
< while (curr && curr != event) {
---
> Event *curr = head->nextBin;
> while (curr && *curr < *event) {
100c160
< curr = curr->next;
---
> curr = curr->nextBin;
103,104c163,176
< if (curr == event)
< prev->next = curr->next;
---
> if (!curr || *curr != *event)
> panic("event not found!");
>
> // curr points to the last item of the the correct 'in bin' list, when
> // we remove an item, it returns the new last item (which may be
> // unchanged)
> Event *last = removeItem(event, curr);
> if (!last) {
> // The current item was removed, so we need to fix the bin list
> prev->nextBin = curr->nextBin;
> } else if (last != curr) {
> // We have a new last item, so we need to update the bin list
> prev->nextBin = last;
> }
110c182,183
< Event *event = head;
---
> // grab the first element
> Event *event = head->nextInBin;
112d184
< head = event->next;
113a186,194
> if (head == event) {
> // this was the only element on the 'in bin' list, so get rid of
> // the 'in bin' list and point to the next bin list
> head = event->nextBin;
> } else {
> // maintain head->nextInBin as the first element
> head->nextInBin = event->nextInBin;
> }
>
131d211
<
140d219
<
169,175c248,261
< Event *event = head;
< while (event) {
< if (event->getFlags(Event::AutoSerialize)) {
< eventPtrs.push_back(event);
< paramOut(os, csprintf("event%d", numEvents++), event->name());
< }
< event = event->next;
---
> Event *nextBin = head;
> while (nextBin) {
> Event *nextInBin = nextBin->nextInBin;
>
> do {
> if (nextInBin->getFlags(Event::AutoSerialize)) {
> eventPtrs.push_back(nextInBin);
> paramOut(os, csprintf("event%d", numEvents++),
> nextInBin->name());
> }
> nextInBin = nextInBin->nextInBin;
> } while (nextInBin != nextBin);
>
> nextBin = nextBin->nextBin;
180c266
< for (std::list<Event *>::iterator it=eventPtrs.begin();
---
> for (std::list<Event *>::iterator it = eventPtrs.begin();
209a296,297
> m5::hash_map<long, bool> map;
>
213,216c301,312
< Event *event = head;
< while (event) {
< event->dump();
< event = event->next;
---
> Event *nextBin = head;
> while (nextBin) {
> Event *nextInBin = nextBin;
> if (map[reinterpret_cast<long>(nextInBin)])
> break;
> map[reinterpret_cast<long>(nextInBin)] = true;
> do {
> nextInBin = nextInBin->nextInBin;
> nextInBin->dump();
> } while (nextInBin != nextBin);
>
> nextBin = nextBin->nextBin;
222a319,360
> bool
> EventQueue::debugVerify() const
> {
> m5::hash_map<long, bool> map;
>
> Tick time = 0;
> short priority = 0;
>
> Event *nextBin = head;
> while (nextBin) {
> Event *nextInBin = nextBin->nextInBin;
> do {
> if (nextInBin->when() < time) {
> cprintf("time goes backwards!");
> nextInBin->dump();
> return false;
> } else if (nextInBin->when() == time &&
> nextInBin->priority() < priority) {
> cprintf("priority inverted!");
> nextInBin->dump();
> return false;
> }
>
> if (map[reinterpret_cast<long>(nextInBin)]) {
> cprintf("Node already seen");
> nextInBin->dump();
> return false;
> }
> map[reinterpret_cast<long>(nextInBin)] = true;
>
> time = nextInBin->when();
> priority = nextInBin->priority();
>
> nextInBin = nextInBin->nextInBin;
> } while (nextInBin != nextBin);
>
> nextBin = nextBin->nextBin;
> }
>
> return true;
> }
>