60c60
< inline void
---
> inline Event *
63c63
< // Either way, event will be the last element in the 'in bin' list
---
> // Either way, event will be the top element in the 'in bin' list
69,71c69
<
< // We need to create a new 'in bin' list
< event->nextInBin = event;
---
> event->nextInBin = NULL;
76,81c74,75
< // 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
---
> // Insert event at the top of the stack
> event->nextInBin = curr;
82a77,78
>
> return event;
90,91c86
< insertBefore(event, head);
< head = event;
---
> head = insertBefore(event, head);
97,101c92,96
< Event *curr = head;
< Event *next = head->nextBin;
< while (next && *next < *event) {
< curr = next;
< next = next->nextBin;
---
> Event *prev = head;
> Event *curr = head->nextBin;
> while (curr && *curr < *event) {
> prev = curr;
> curr = curr->nextBin;
104,106c99,101
< insertBefore(event, next);
< curr->nextBin = event; // all nextBin pointers on the curr
< // 'in bin' list are now stale
---
> // Note: this operation may render all nextBin pointers on the
> // prev 'in bin' list stale (except for the top one)
> prev->nextBin = insertBefore(event, curr);
110c105
< removeItem(Event *event, Event *last)
---
> removeItem(Event *event, Event *top)
112,113c107,108
< Event *prev = last;
< Event *curr = last->nextInBin;
---
> Event *curr = top;
> Event *next = top->nextInBin;
115,116c110,123
< while (event != curr) {
< if (curr == last)
---
> // if we removed the top item, we need to handle things specially
> // and just remove the top item, fixing up the next bin pointer of
> // the new top item
> if (event == top) {
> if (!next)
> return top->nextBin;
> next->nextBin = top->nextBin;
> return next;
> }
>
> // Since we already checked the current element, we're going to
> // keep checking event against the next element.
> while (event != next) {
> if (!next)
119,120c126,127
< prev = curr;
< curr = curr->nextInBin;
---
> curr = next;
> next = next->nextInBin;
123,137c130,132
< // 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;
---
> // remove next from the 'in bin' list since it's what we're looking for
> curr->nextInBin = next->nextInBin;
> return top;
150,151d144
< if (!head)
< head = event->nextBin;
166,167c159,160
< // 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
---
> // curr points to the top item of the the correct 'in bin' list, when
> // we remove an item, it returns the new top item (which may be
169,176c162
< 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;
< }
---
> prev->nextBin = removeItem(event, curr);
182,183c168,169
< // grab the first element
< Event *event = head->nextInBin;
---
> Event *event = head;
> Event *next = head->nextInBin;
186c172,178
< if (head == event) {
---
> if (next) {
> // update the next bin pointer since it could be stale
> next->nextBin = head->nextBin;
>
> // pop the stack
> head = next;
> } else {
189,192c181
< head = event->nextBin;
< } else {
< // maintain head->nextInBin as the first element
< head->nextInBin = event->nextInBin;
---
> head = head->nextBin;
250c239
< Event *nextInBin = nextBin->nextInBin;
---
> Event *nextInBin = nextBin;
252c241
< do {
---
> while (nextInBin) {
259c248
< } while (nextInBin != nextBin);
---
> }
296,297d284
< m5::hash_map<long, bool> map;
<
304,308c291
< if (map[reinterpret_cast<long>(nextInBin)])
< break;
< map[reinterpret_cast<long>(nextInBin)] = true;
< do {
< nextInBin = nextInBin->nextInBin;
---
> while (nextInBin) {
310c293,294
< } while (nextInBin != nextBin);
---
> nextInBin = nextInBin->nextInBin;
> }
329,330c313,314
< Event *nextInBin = nextBin->nextInBin;
< do {
---
> Event *nextInBin = nextBin;
> while (nextInBin) {
353c337
< } while (nextInBin != nextBin);
---
> }