# Introduction to `fbl` intrusive containers

Intrusive containers (or intrusive data structures) are the type of containers
offered by the Fuchsia Base Library (`fbl::`).

This document will:

1. [Define what an intrusive container is.](#what-is-an-intrusive-container)
2. [Compare the differences between intrusive and non-intrusive containers.](#intrusive-vs-not)
3. [Discuss the similarities and differences between `fbl::` and `std::` containers.](#fbl-vs-std)
4. [Introduce some basic terminology that will be used throughout this guide.](#terminology)

## What is an intrusive container? {#what-is-an-intrusive-container}

An intrusive container is a data structure that can be used to hold a
collection of objects where the bookkeeping used to track membership in the
container is stored in the objects themselves instead of holding the object
alongside of the bookkeeping in a structure. To highlight the distinction,
consider a structure that defines a point in a 2-dimensional coordinate system.

```cpp
struct Point {
  float x, y;
};
```

In a traditional non-intrusive implementation of a doubly linked list, a node in
the list might look something like this

```cpp
struct ListNode {
  Point val;
  ListNode *next, *prev;
};
```

While an intrusive version of the same list would be

```cpp
struct Point {
  float x, y;
  Point *next, *prev;
};
```

Initially, these appear to be very similar approaches. The distinction seems
mostly like a question of which object is contained within the other. As time goes
on, however, the differences become more apparent.

Adding a point to a non-intrusive list of points means:

1. Allocating a `ListNode`
1. Copying the `Point` you want to add to the list into the `val` member of the `ListNode`
1. Linking the `next`/`prev` pointers of the `ListNode` into the list.

Removing the point is the same process in reverse.

1. The pointers are unlinked.
1. The contents of the `Point` are copied out to local storage.
1. Finally, the `ListNode` is de-allocated.

When using an intrusive list, the add/remove operations skip the
allocation/deallocation and copying of the `Point`'s members. The `next`/`prev`
pointers, which exist in the point object already, are simply linked into the
list during the add operation and unlinked during the remove. While the
intrusive form does not have to perform any allocations or copy any structures
to add elements to a list, every `Point` in the system is must carry around the
overhead of the next/prev bookkeeping, even while not in a list.

While a small structure or primitive data type might be held by value in a
non-intrusive list, when objects become larger, it becomes more common to track
the object using some appropriate pointer type instead of storing the object by
value. For example

```cpp
struct ListNode {
  std::shared_ptr<LargeObject> ptr;
  ListNode *next, *prev;
};
```

The "value" being stored in this list is an instance of a shared pointer, so
while adding or removing a pointer to a `LargeObject` to a list still requires
management of the allocation used to store the node state, the object itself no
longer needs to be copied when being added to a list. Additionally, this
approach allows a single instance of a `LargeObject` to exist in multiple
containers at the same time as the nodes simply track references to the objects
and not copies of the objects. A simple implementation of an intrusive form of
this would put the `next`/`prev` pointers into `LargeObject` directly implying
that an instance of a `LargeObject` could be a member of exactly 0 or 1
intrusive lists, but not more.

## Intrusive vs. non-intrusive containers {#intrusive-vs-not}

The primary advantage of an intrusive container approach to tracking objects is
the lack of allocations when adding/removing elements to/from a container. In
some (usually specialized) environments, heap interactions can introduce a
potential failure path, which would ideally not exist. Additionally,
interactions with heaps usually involve interactions with locks/mutexes, which
could result in involuntary blocking. This might introduce undesirable timing
indeterminism, or in some cases may even not be an option if the code is running
in a context in which blocking is not allowed.

For example, what happens if code needs to add a bookkeeping structure to a list
during a hard interrupt handler in the kernel if the allocation for the
bookkeeping structure cannot be allocated, or if allocation of the bookkeeping
would require the IRQ handler to block due to lock contention (something that
cannot happen in the exception handler)? By allocating the container
bookkeeping as part of the object itself ahead of time, an intrusive container
approach to this problem allows these issues to be avoided.

In general, intrusive containers can provide performance advantages when the
design of the system allows the implementer to know at compile time all of the
various containers that an object will ever exist in. This does not mean that they
are always the best choice, however, as they come with limitations as well.

Finally, for many types of intrusive containers, holding a reference to an
object implies that you have located that object in all of the container types
it can possible exist in where the same is not true when an object is tracked by
reference in multiple non-intrusive container instances. For example, an object
which could exist in a balanced binary search tree as well as in a doubly linked
list (both intrusive) could be located in O(log n) time in the tree, and then
removed from the list in O(1) time, instead of needing to find the object in the
list in O(n) time before removing it.

A short list of some pros and cons of the two approaches might look something
like this:

Non-intrusive:

- Pros

  - Can be used to track simple objects by value, even primitive data types
  like `int` or `float`

  - Does not require changing the definition of the object itself in order to
  manage it in a different container. This is especially helpful when an object
  `O` is defined in Library A, but a user wishes to create a collection of
  `A::O`s in their own program and cannot reasonably re-define `O`.

  - Objects tracked by reference can easily exist in multiple containers
  independently.

- Cons
  - Requires independent allocation management of the bookkeeping, usually on
  every add or remove operation. This management frequently implies hidden heap
  interactions, which can introduce overhead, timing uncertainty, and additional
  complexity as users need to manage potential failure paths.

  - Finding the location of an object in container A provides no information
  about the location of the object in container B. For example, finding an
  object contained in a `std::map` with an O(log n) operation does not
  help me to locate the same object that is simultaneously contained in a
  `std::deque`. If I want to remove the object from the `std::deque`, I must find
  it there with a separate O(n) operation first.

Intrusive:

- Pros

  - Minimal overhead to join or leave a container, and no chance of failure
  or involuntary yielding due to lock contention as the bookkeeping overhead was
  paid up-front during object creation.

  - Finding an instance of an object implicitly finds the instance of the
  object in all of the containers it can exist in.

  - Knowledge of whether an object is currently container in container type A
  is a property of the object and can always be tested (from the object) in O(1)
  time.

- Cons

  - The ability to be contained is a fundamental property of the object. In
  order to change the number or types of the containers an object may exist in,
  the definition of the object itself must be changed, and all of the code that
  depends on that definition must be re-compiled.

  - Only objects themselves can be tracked. Primitive data types do not have
  any place to store extra bookkeeping information and cannot be tracked in an
  intrusive fashion.

## `fbl::` vs. `std::` {#fbl-vs-std}

The C++ Standard Library offers a large set of implementation agnostic
non-intrusive containers. For example, `std::map` is an ordered associative
container, however there are no requirements that an implementation of the
standard library use any specific data structure in order to implement
`std::map`, only that the implementation chosen provides certain
guarantees for various container operations as specified by the standard, such
as worst case algorithmic complexities, or guarantees around iterator
invalidation.

If you need a non-intrusive container, this is where you should be looking.

While there have been draft proposals, the C++ standard library does _not_
currently offer any intrusive container implementations. Similar to `boost::`,
`fbl::` attempts to fill this gap, but in a much more limited/focused fashion.
The algorithms backing the types of containers types offered by `fbl::` are
explicit and embedded in the names of the container types themselves. The APIs
are inspired by and attempt to emulate those offered by `std::`, however there
are some differences as a result of the fundamental differences between
intrusive and non-intrusive containers. There are currently 3 primary container
types defined by `fbl::` and one composed container type. They are:

* `fbl::SinglyLinkedList<>`
* `fbl::DoublyLinkedList<>`
* `fbl::WAVLTree<>`
* `fbl::HashTable<>`

`fbl::HashTable<>` is considered to be a composed container type as it offers a
fixed bucket count hash table that resolves collision using chaining where the
bucket type may be either `fbl::SinglyLinkedList<>` or
`fbl::DoublyLinkedList<>`. Please refer to [Setting up build
dependencies](getting_started.md#build-dependencies) for details on which files
need to be included in order to use the various container types.

## Terminology {#terminology}

Here are some definitions of terms used throughout this
guide.

* Container : An object that tracks a collection of references to objects using
  a specific algorithm.
* Node or Node Storage : The set of data that provides the bookkeeping that
  allows an object to exist in a specific container type.
* Listable, Containable, Mix-in : An object that can be used as a base class to
  allow an object to be easily stored in a container of a specific type.
* Raw pointer : A non-managed `T*`-style pointer to an object.