LinkedListQueue

A typed-queue based on a linked list. (Internally, the queue is composed of instances of a struct which contains a value (of type T) and a pointer to next item.)

The linked list implementation allows the following extensions to ITypedQueue:

* The ability to find a specified value in the queue: contains(). * The ability to remove one or all instances of a specified value from the queue: remove().

The items in the linked list are allocated and deallocated by Malloc allocation manager, to avoid the GC from not so efficiently going over the linked list (see explanation at LinkedListQueue.heap below).

Members

Functions

bottom T* bottom()
clear void clear(): Removes all items from the queue in O(n)
contains bool contains(T value): Checks whether a value exists in queue in O(n).
deleteItem void deleteItem(QueueItem* to_delete): Deallocate an item. Called upon item removal from queue.
discardTop void discardTop(): Discards the item at the top of the queue.
empty bool empty()
length size_t length()
newItem QueueItem* newItem(): Allocate an item. Called upon item addition to queue.
opApply int opApply(int delegate(ref T value) dg): Walk through the linked list
push T* push(): Pushes an item to the queue. The caller should set the returned item as desired
remove size_t remove(T value, bool all): Removes a value from queue, in O(n)
top T* top()

Static functions

isRootedValues bool isRootedValues()

Static variables

root_values bool root_values;: Should the values in queue be added to GC as roots, thus preventing the GC from collecting these values.

Structs

QueueItem struct QueueItem: Type of items in queue - a struct of value and pointer to next item

Variables

count size_t count;: Number of items in the queue
head QueueItem* head;: Pointer to first (and oldest) item in queue
heap Container.Malloc!(QueueItem) heap;: Malloc allocation manager, to allocate and deallocate items in queue. We use the malloc allocation manager as to keep the linked list away from the reach of the GC, for efficiency reasons. The reason for this is: The GC collector scans the memory in order to identify the root objects, and then collect them. The scanning process, roughly speaking, is done in such a way that each time the GC detects a new address it runs another scan. On the entire memory. After each scan the amount of detected addresses is increased until there are mo more undetected addresses, and the scanning stops. The problem with linked list is that the GC will detect a single item in each scan. So GC will run as many scans as the number of items in the linked list. And again, each scan goes over the entire memory.
tail QueueItem* tail;: Pointer to last item in queue

Parameters

T: Type of values stored in the linked list queue
gc_tracking_policy: defines the GC tracking policy for T (see GCTrackingPolicy struct below)