avrora.sim.util
Class DeltaQueue

java.lang.Object
  avrora.sim.util.DeltaQueue

public class DeltaQueue

extends java.lang.Object

The DeltaQueue 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.

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.

For each clock cycle, only the first node in the list must be checked, leading to constant time work per clock cycle.

This class allows the clock to be advanced multiple ticks at a time.

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.

Field Summary

protected long	count The count field stores the total number of cycles that this queue has been advanced, i.e. the sum of all advance() calls.
protected avrora.sim.util.DeltaQueue.EventList	freeEventLists The freeEventLists field stores a reference to any free event links that have become unused during the processing of events.
protected avrora.sim.util.DeltaQueue.Link	freeLinks The freeLinks field stores a reference to any free links that have become unused during the processing of events.
protected avrora.sim.util.DeltaQueue.Link	head The head field stores a reference to the head of the delta queue, which represents the event that is nearest in the future.

Constructor Summary

DeltaQueue()

Method Summary

void	add(Simulator.Event t, long cycles) The add method adds an event to be executed in the future.
void	advance(long cycles) The advance method advances timesteps through the queue by the specified number of clock cycles, processing any events.
long	getCount() The getCount() gets the total cumulative count of all the advance() calls on this delta queue.
long	getHeadDelta() The getHeadDelta() method gets the number of clock cycles until the first event will fire.
void	remove(Simulator.Event e) The remove method removes all occurrences of the specified event within the delta queue.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

head

protected avrora.sim.util.DeltaQueue.Link head

The head field stores a reference to the head of the delta queue, which represents the event that is nearest in the future.

freeLinks

protected avrora.sim.util.DeltaQueue.Link freeLinks

The freeLinks 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.

freeEventLists

protected avrora.sim.util.DeltaQueue.EventList freeEventLists

The freeEventLists 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.

count

protected long count

The count field stores the total number of cycles that this queue has been advanced, i.e. the sum of all advance() calls.

Constructor Detail

DeltaQueue

public DeltaQueue()

Method Detail

add

public void add(Simulator.Event t,
                long cycles)

The add method adds an event to be executed in the future.

Parameters:

t - the event to add

cycles - the number of clock cycles in the future

remove

public void remove(Simulator.Event e)

The remove method removes all occurrences of the specified event within the delta queue.

Parameters:

e - the event to remove

advance

public void advance(long cycles)

The advance method advances timesteps through the queue by the specified number of clock cycles, processing any events.

Parameters:

cycles - the number of clock cycles to advance

getHeadDelta

public long getHeadDelta()

The getHeadDelta() method gets the number of clock cycles until the first event will fire.

Returns:

the number of clock cycles until the first event will fire

getCount

public long getCount()

The getCount() gets the total cumulative count of all the advance() calls on this delta queue.

Returns:

the total number of cycles this queue has been advanced