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 triggers 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 a trigger X cycles in the future, at most X nodes will be skipped over. Therefore 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
protected avrora.sim.util.DeltaQueue.Link	freeLinks
protected avrora.sim.util.DeltaQueue.TriggerLink	freeTriggerLinks
protected avrora.sim.util.DeltaQueue.Link	head

Constructor Summary

DeltaQueue()

Method Summary

void	add(Simulator.Trigger t, long cycles) The add method adds a trigger 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 triggers.
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.Trigger e) The remove method removes all occurrences of the specified trigger 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

freeLinks

protected avrora.sim.util.DeltaQueue.Link freeLinks

freeTriggerLinks

protected avrora.sim.util.DeltaQueue.TriggerLink freeTriggerLinks

count

protected long count

Constructor Detail

DeltaQueue

public DeltaQueue()

Method Detail

add

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

The add method adds a trigger to be executed in the future.

Parameters:

t - the trigger to fire

cycles - the number of clock cycles in the future

remove

public void remove(Simulator.Trigger e)

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

Parameters:

e - the trigger 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 triggers.

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