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.

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