Class TimeoutQueue

Nested Relationships

Class Documentation

class switchml::TimeoutQueue

An efficient data structure used to check for message timeouts.

In order to ensure that all operations are done in constant time, the timeoutqueue was designed using an ordered double-linked list which also has an index for entries. This allows us to perform all of the 3 functions (push, remove, check) in constant time.

Public Types

using TimePoint = std::chrono::time_point<switchml::clock>

Type of timestamp. Just an alias for user convenience.

Public Functions

TimeoutQueue(const uint32_t num_entries, const std::chrono::milliseconds timeout, const uint32_t timeouts_threshold, const uint32_t timeouts_threshold_increment)

Construct a new Timeout Queue object.

Parameters

  • num_entries – [in] The maximum number of entries that you might push. This should equal the number of outstanding messages.

  • timeout – [in] The initial value of the timeout in milliseconds.

  • threshold – [in] After how many timeouts should we double the timeout value?.

  • threshold – [in] After a timeout occurs how much should we increment the threshold?.

~TimeoutQueue() = default
TimeoutQueue(TimeoutQueue const&) = default
void operator=(TimeoutQueue const&) = delete
TimeoutQueue(TimeoutQueue&&) = default
TimeoutQueue &operator=(TimeoutQueue&&) = default
void Push(int index, const TimePoint &timestamp)

Push an entry onto the queue.

Elements are added to the top of the linked list because they are always assumed to be the newest. This allows us to keep the order and insert into the linked list in constant time.

Parameters

  • index – [in] The index where you want to store the entry for direct access later. This is not the same as the entry’s position in the linked list.

  • timestamp – [in] The current timestamp

void Remove(int index)

Remove an entry.

This operation is done in constant time since the index gives us direct access to the linked list element and we only then need to rewire the pointers of the two adjacent entries in the linked list if they exist.

Parameters

index – [in] The index of the entry to remove.

int Check(const TimePoint &timestamp)

Given the current timestamp, check a timeout occured.

If a timeout occured, then the index of the entry that timed out first is returned.

This is also done in constant time since we only need to check the entry that exists at the tail of the linked list.

Parameters

timestamp – [in] The current timestamp.

Returns

int the index of the entry that timed out first.

struct TQEntry

A struct representing a single entry in the TimeoutQueue.

Public Functions

TQEntry()
~TQEntry() = default
TQEntry(TQEntry const&) = default
void operator=(TQEntry const&) = delete
TQEntry(TQEntry&&) = default
TQEntry &operator=(TQEntry&&) = default

Public Members

bool valid

Whether this entry is just a place holder or an actual entry pushed by the user.

int next

The index of the next entry

int previous

The index of the previous entry

TimePoint timestamp

The time at which this entry was pushed