pw_containers/docs.rst

.. _module-pw_containers:

-------------
pw_containers
-------------
The ``pw_containers`` module provides embedded-friendly container classes.

pw::Vector
==========
The Vector class is similar to ``std::vector``, except it is backed by a
fixed-size buffer. Vectors must be declared with an explicit maximum size
(e.g. ``Vector<int, 10>``) but vectors can be used and referred to without the
max size template parameter (e.g. ``Vector<int>``).

To allow referring to a ``pw::Vector`` without an explicit maximum size, all
Vector classes inherit from the generic ``Vector<T>``, which stores the maximum
size in a variable. This allows Vectors to be used without having to know
their maximum size at compile time. It also keeps code size small since
function implementations are shared for all maximum sizes.


pw::IntrusiveList
=================
IntrusiveList provides an embedded-friendly singly-linked list implementation.
An intrusive list is a type of linked list that embeds the "next" pointer into
the list object itself. This allows the construction of a linked list without
the need to dynamically allocate list entries to point to the actual in-memory
objects. In C, an intrusive list can be made by manually including the "next"
pointer as a member of the object's struct. `pw::IntrusiveList` uses C++
features to simplify the process of creating an intrusive list and intrusive
list objects by providing a class that list elements can inherit from. This
protects the "next" pointer from being accessed by the actual item that is
stored in the linked list; only the `pw::IntrusiveList` class can modify the
list.


pw::containers::FlatMap
=======================
FlatMap provides a simple, fixed-size associative array with lookup by key or
value. ``pw::containers::FlatMap`` contains the same methods and features for
looking up data as std::map. However, there are no methods that modify the
underlying data.  The underlying array in ``pw::containers::FlatMap`` does not
need to be sorted. During construction, ``pw::containers::FlatMap`` will
perform a constexpr insertion sort.


Usage
-----
While the API of `pw::IntrusiveList` is relatively similar to a
``std::forward_list``, there are extra steps to creating objects that can be
stored in this data structure. Objects that will be added to a
``IntrusiveList<T>`` must inherit from ``IntrusiveList<T>::Item``. When an item
is instantiated and added to a linked list, the pointer to the object is added
to the "next" pointer of whichever object is the current tail.


That means two key things:

 - An instantiated IntrusiveList::Item must remain in scope for the lifetime of
   the IntrusiveList it has been added to.
 - A linked list item CANNOT be included in two lists, as it is part of a
   preexisting list and adding it to another implicitly breaks correctness
   of the first list.

.. code-block:: cpp

  class Square
     : public pw::IntrusiveList<Square>::Item {
   public:
    Square(unsigned int side_length) : side_length(side_length) {}
    unsigned long Area() { return side_length * side_length; }

   private:
    unsigned int side_length;
  };

  pw::IntrusiveList<Square> squares;

  Square small(1);
  Square large(4000);
  // These elements are not copied into the linked list, the original objects
  // are just chained together and can be accessed via
  // `IntrusiveList<Square> squares`.
  squares.push_back(small);
  squares.push_back(large);

  {
    // ERROR: When this goes out of scope, it will break the linked list.
    Square different_scope = Square(5);
    squares.push_back(&different_scope);
  }

  for (auto& square : squares) {
    PW_LOG_INFO("Found a square with an area of %ul", square.Area());
  }


Compatibility
=============
* C
* C++17

Dependencies
============
* ``pw_span``