code: /**
   * Copyright (c) 2004-2005, Regents of the University of California
   * All rights reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions
   * are met:
   *
   * Redistributions of source code must retain the above copyright notice,
   * this list of conditions and the following disclaimer.
   *
   * Redistributions in binary form must reproduce the above copyright
   * notice, this list of conditions and the following disclaimer in the
   * documentation and/or other materials provided with the distribution.
   *
   * Neither the name of the University of California, Los Angeles nor the
   * names of its contributors may be used to endorse or promote products
   * derived from this software without specific prior written permission.
   *
   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
   * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
   * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
   * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
   * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
   * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   */
  
  package avrora.sim.clock;
  
  import avrora.sim.Simulator;
  
  /**
   * The <code>DeltaQueue</code> class implements an amortized constant time delta-queue for processing of
   * scheduled events. Events are put into the queue that will fire at a given number of cycles in the future.
   * An internal delta list is maintained where each link in the list represents a set of events to be fired
   * some number of clock cycles after the previous link.
   * <p/>
   * Each delta between links is maintained to be non-zero. Thus, to insert an event X cycles in the future, at
   * most X nodes will be skipped over. Therefore, when the list is advanced over X time steps, this cost is
   * amortized to be constant.
   * <p/>
   * For each clock cycle, only the first node in the list must be checked, leading to constant time work per
   * clock cycle.
   * <p/>
   * This class allows the clock to be advanced multiple ticks at a time.
   * <p/>
   * Also, since this class is used heavily in the simulator, its performance is important and maintains an
   * internal cache of objects. Thus, it does not create garbage over its execution and never uses more space
   * than is required to store the maximum encountered simultaneous events. It does not use standard libraries,
   * casts, virtual dispatch, etc.
   */
  public class DeltaQueue {
  
      /**
       * The <code>EventList</code> class represents a link in the list of events for a given <code>Link</code>
       * in the delta queue chain.
       */
      private static class EventList {
          Simulator.Event event;
          EventList next;
  
          /**
           * The constructor for the <code>EventList</code> class simply initializes the internal references to
           * the event and the next link in the chain based on the parameters passed.
           *
           * @param t a reference the event
           * @param n the next link in the chain
           */
          EventList(Simulator.Event t, EventList n) {
              event = t;
              next = n;
          }
  
      }
  
      /**
       * The <code>Link</code> class represents a link in the list of delta queue items that are being stored.
       * It contains a list of events that share the same delta.
       */
      private class Link {
          EventList events;
  
          Link next;
          long delta;
  
          Link(Simulator.Event t, long d) {
              events = newEventList(t, null);
              delta = d;
          }
  
          void add(Simulator.Event t) {
              events = newEventList(t, events);
          }
  
          void remove(Simulator.Event t) {
              EventList prev = null;
              EventList pos = events;
              while (pos != null) {
                  EventList next = pos.next;
  
                  if (pos.event == t) {
                      if (prev == null)
                      // remove the whole thing.
                          events = pos.next;
                      else
                      // remove the "pos" link
                          prev.next = pos.next;
  
                      free(pos);
                  } else {
                      prev = pos;
                  }
                  pos = next;
              }
          }
  
          void fire() {
              for (EventList pos = events; pos != null; pos = pos.next) {
                  pos.event.fire();
              }
          }
      }
  
      /**
       * The <code>head</code> field stores a reference to the head of the delta queue, which represents the
       * event that is nearest in the future.
       */
      protected Link head;
  
      /**
       * The <code>freeLinks</code> field stores a reference to any free links that have become unused during
       * the processing of events. A free list is used to prevent garbage from accumulating.
       */
      protected Link freeLinks;
  
      /**
       * The <code>freeEventLists</code> field stores a reference to any free event links that have become
       * unused during the processing of events. A free list is used to prevent garbage from accumulating.
       */
      protected EventList freeEventLists;
  
      /**
       * The <code>count</code> field stores the total number of cycles that this queue has been advanced, i.e.
       * the sum of all <code>advance()</code> calls.
       */
      protected long count;
  
      /**
       * The <code>add</code> method adds an event to be executed in the future.
       *
       * @param t      the event to add
       * @param cycles the number of clock cycles in the future
       */
      public void insertEvent(Simulator.Event t, long cycles) {
          // degenerate case, nothing in the queue.
          if (head == null) {
              head = newLink(t, cycles, null);
              return;
          }
  
          // search for first link that is "after" this cycle delta
          Link prev = null;
          Link pos = head;
          while (pos != null && cycles > pos.delta) {
              cycles -= pos.delta;
              prev = pos;
              pos = pos.next;
          }
  
          if (pos == null) {
              // end of the head
              insertAfter(prev, t, cycles, null);
          } else if (cycles == pos.delta) {
              // exactly matched the delta of some other event
              pos.add(t);
          } else {
              // insert a new link in the chain
              insertAfter(prev, t, cycles, pos);
          }
      }
  
      private void insertAfter(Link prev, Simulator.Event t, long cycles, Link next) {
          if (prev != null)
              prev.next = newLink(t, cycles, next);
          else
              head = newLink(t, cycles, next);
      }
  
      /**
       * The <code>remove</code> method removes all occurrences of the specified event within the delta queue.
       *
       * @param e the event to remove
       */
      public void removeEvent(Simulator.Event e) {
          if (head == null) return;
  
          // search for first link that is "after" this cycle delta
          Link prev = null;
          Link pos = head;
          while (pos != null) {
              Link next = pos.next;
              pos.remove(e);
  
              if (pos.events == null) {
                  // the link became empty because of removing this event
                  if (prev == null)
                      head = pos.next;
                  else
                      prev.next = pos.next;
  
                  // fixes up the delta of the next item in the queue
                  if (pos.next != null) {
                      pos.next.delta += pos.delta;
                  }
  
                  free(pos);
              } else {
                  // the link did not become empty, just move on
                  prev = pos;
              }
              // advance to next link in the list
              pos = next;
          }
      }
  
      /**
       * The <code>advance</code> method advances timesteps through the queue by the specified number of clock
       * cycles, processing any events.
       *
       * @param cycles the number of clock cycles to advance
       */
      public void advance(long cycles) {
          if ( head == null ) {
              // fast path 1: nothing in the queue
              count += cycles;
              return;
          }
  
          if ( head.delta > cycles ) {
              // fast path 2: head does not fire
              count += cycles;
              head.delta -= cycles;
              return;
          }
  
          advanceSlow(cycles);
  
      }
  
      /**
       * The <code>skipAhead()</code> method skips ahead to the next event in the queue and fires it.
       */
      public void skipAhead() {
          if ( head == null ) {
              // fast path 1: nothing in the queue
              count++;
              return;
          }
  
          Link h = head;
          count += h.delta;
          head = h.next;
          h.fire();
          free(h);
      }
  
      private void advanceSlow(long cycles) {
          // slow path: head (and maybe more) fires
          while (head != null && cycles > 0) {
  
              Link pos = head;
              Link next = pos.next;
  
              // cache pos.delta because it is used twice
              long delta = pos.delta;
              // number of cycles leftover after advancing by pos.delta
              long leftover = cycles - delta;
  
              // if haven't arrived yet, advance and return
              if (leftover < 0) {
                  count += cycles;
                  pos.delta = -leftover;
                  return;
              }
  
              // advance by the number of cycles at the head of the queue
              count += delta;
  
              // chop off head
              head = next;
  
              // fire all events at head
              pos.fire();
  
              // free the head
              free(pos);
  
              // process leftover cycles next time through loop
              cycles = leftover;
          }
  
          // add in leftover cycles if we reached end of queue (head == null)
          count += cycles;
      }
  
      /**
       * The <code>getHeadDelta()</code> method gets the number of clock cycles until the first event will
       * fire.
       *
       * @return the number of clock cycles until the first event will fire
       */
      public long getFirstEventTime() {
          if (head != null) return head.delta;
          return -1;
      }
  
      /**
       * The <code>getCount()</code> gets the total cumulative count of all the <code>advance()</code> calls on
       * this delta queue.
       *
       * @return the total number of cycles this queue has been advanced
       */
      public long getCount() {
          return count;
      }
  
      private void free(Link l) {
          l.next = freeLinks;
          freeLinks = l;
  
          if (l.events != null) {
              free(l.events);
              l.events = null;
          }
      }
  
      private void free(EventList l) {
          l.event = null;
          l.next = freeEventLists;
          freeEventLists = l;
      }
  
      private Link newLink(Simulator.Event t, long cycles, Link next) {
          Link l;
          if (freeLinks == null)
          // if none in the free list, allocate one
              l = new Link(t, cycles);
          else {
              // grab one from the free list
              l = freeLinks;
              freeLinks = freeLinks.next;
              l.delta = cycles;
              l.add(t);
          }
  
          // adjust delta in the next link in the chain
          if (next != null) {
              next.delta -= cycles;
          }
  
          l.next = next;
          return l;
      }
  
      private EventList newEventList(Simulator.Event t, EventList next) {
          EventList l;
  
          if (freeEventLists == null) {
              // no free links, so allocate one
              l = new EventList(t, next);
          } else {
              // grab the first link off the free chain
              l = freeEventLists;
              freeEventLists = freeEventLists.next;
              l.next = next;
              l.event = t;
          }
  
          return l;
      }
  }
  