containers.unrolledlist

Unrolled Linked List.

Authors

Brian Schott

  • Declaration

    struct UnrolledList(T, Allocator = Mallocator, bool supportGC = shouldAddGCRange!T, size_t cacheLineSize = 64);

    Unrolled Linked List.

    Discussion

    Nodes are (by default) sized to fit within a 64-byte cache line. The number of items stored per node can be read from the nodeCapacity field.

    Parameters

    T

    the element type

    Allocator

    the allocator to use. Defaults to Mallocator.

    supportGC

    true to ensure that the GC scans the nodes of the unrolled list, false if you are sure that no references to GC-managed memory will be stored in this container.

    cacheLineSize

    Nodes will be sized to fit within this number of bytes.

    • Declaration

      this();

      No default construction if an allocator must be provided.

    • Declaration

      this(Allocator allocator);

      Use the given allocator for allocations.

    • Declaration

      void clear();

      Removes all items from the list

    • Declaration

      T* insertBack(T item);

      Inserts the given item into the end of the list.

      Return Value

      a pointer to the inserted item.

    • Declaration

      void insertBack(R)(auto ref R range);
      T* opOpAssign(string op)(T item) if (op == "~");
      alias put = insertBack;
      alias insert = insertBack;

      Inserts the given range into the end of the list

    • Declaration

      @trusted T* insertAnywhere(T item);

      Inserts the given item in the frontmost available cell, which may put the item anywhere in the list as removal may leave gaps in list nodes. Use this only if the order of elements is not important.

      Return Value

      a pointer to the inserted item.

    • Declaration

      const pure nothrow @nogc @property @safe size_t length();

      Return Value

      the length of the list

    • Declaration

      const pure nothrow @nogc @property @safe bool empty();

      Return Value

      true if the list is empty

    • Declaration

      bool remove(T item);

      Removes the first instance of the given item from the list.

      Return Value

      true if something was removed.

    • Declaration

      void popFront();

      Pops the front item off of the list

    • Declaration

      T moveFront();

      Pops the front item off of the list and returns it

    • Declaration

      inout nothrow @property ref inout(T) front();

      Time complexity is O(1)

      Return Value

      the item at the front of the list

    • Declaration

      inout nothrow @property ref inout(T) back();

      Time complexity is O(nodeCapacity), where the nodeCapacity is the number of items in a single list node. It is a constant related to the cache line size.

      Return Value

      the item at the back of the list

    • Declaration

      void popBack();

      Pops the back item off of the list.

    • Declaration

      T moveBack();

      Removes an item from the back of the list and returns it.

    • Declaration

      const pure nothrow @nogc @trusted auto opSlice(this This)();

      Return Value

      a range over the list