Advanced scenarios

By default, most of the behavior of intrusive containers in fbl:: are designed to provide as much safety as possible at compile time, typically by disallowing use patterns that might easily lead to mistakes at compile time.

That said, there are certain advanced scenarios where a user may choose to bypass these compile time safeties in order to deliberately permit certain behaviors. Whenever you choose to use one of these options, make sure that you have thought carefully about the implications of taking the safety off, and be sure that you are using the functionality in a safe way.

This section of the guide will show you how to:

Use fbl::NodeOptions to opt into advanced behaviors
Control the copy/move-ability of objects while they are in a container.
Permit an object tracked by unique_ptr to be contained in multiple container types
Clear a container of raw pointers in O(1) time
Remove an object from a container without a reference to the container

Controlling advanced options with `fbl::NodeOptions`

In order to control some advanced options at compile time, node state objects (as well as their associated mix-ins) can take a bit-flag style constant, which can be used to change specific behaviors. Options may be combined using the | operator. By default, options are the second template parameter of either a NodeState or Listable/Containable type, and the third template parameter of a TaggedListable/TaggedContainable mix-in. These options always default to fbl::NodeOptions::None. The syntax looks like this:

class SimpleObject :
  public fbl::DoublyLinkedListable<SimpleObject*, fbl::NodeOption::OptionFoo> { /* ... */ };

class MoreComplexObject :
  public fbl::ContainableBaseClasses<
    fbl::TaggedSinglyLinkedListable<MoreComplex*, Tag1, fbl::NodeOption::OptionBar>,
    fbl::TaggedWAVLTreeContainable <MoreComplex*, Tag2,
                                    fbl::NodeOption::OptionA | fbl::NodeOption::OptionB>> {
  // ...
};

class ExplicitNodesObject {
 public:
  // ...

 private:
  // ...
  static constexpr fbl::NodeOptions kOptions = fbl::NodeOption::OptionX |
                                               fbl::NodeOption::OptionY |
                                               fbl::NodeOption::OptionZ;
  fbl::WAVLTreeNodeState<ExplicitNodesObject*, kOptions> wavl_node_state_;
};

Controlling the copy/move behavior of objects while they are in a container

Copying or moving node state while its object is in a container is not a legal operation can cannot be permitted. Consider the following:

fbl::DoublyLinkedList<Obj*> the_list;
ASSERT(!the_list.is_empty());

Obj the_obj;
the_list.insert_after(the_list.begin());

Obj another_obj{the_obj};

Obj yet_another_object;
the_obj = yet_another_object;

the_obj exists in the list after the first node. If you were to allow the node state to be copied into another_obj via the default copy constructor, you would have two objects with two copies of the bookkeeping. another_obj would incorrectly think that it was in the container, and will now attempt to assert when destroyed.

Worse, if you attempt to remove the object by calling the_list.erase(another_object), you are attempting to erase an object from a container in an incoherent state. In this case, the prev and next pointers of another object point to the first object in the list, the object that used to be after begin() at the start of the example, but the next pointer of *begin() is pointing to the_obj, and likewise for the prev pointer of the next object in the sequence. While the specific behavior will vary on the type of container and the specific implementation of erase, what is going to happen is undefined behavior and cannot end well.

Finally, when the example code assigns the newly stack constructed yet_another_object to the_obj, if the node state data were to be copied from yet_another_object, the_obj would suddenly think it is not in the list even though the objects on either side of it held pointers to it.

Any way you look at it, permitting the node state data to be copied will corrupt the container's structure and cannot be allowed to happen, and the same goes for the definition of most move operations.

To prevent mistakes like this, the default behavior of fbl:: node state objects is to disallow copy construction/assignment as well as move construction/assignment. Any attempt to invoke the copy/move constructor/assignment operator will result in a static_assert and a failure to compile.

What about when objects are not in a container? Shouldn't copy/move be permitted then? The short answer is sure, but in the interest of safety, it is considered to be allowed only if the code author has opted into the behavior. In order to opt in, you may use the following NodeOptions with their mix-in or node storage types.

fbl::NodeOptions::AllowCopy
fbl::NodeOptions::AllowMove
fbl::NodeOptions::AllowCopyAndMove

Setting AllowCopy will permit copy (l-value) construction and assignment, while setting AllowMove will permit move (r-value) construction and assignment. AllowCopyAndMove is simply shorthand for the two of them combined.

During the operation itself, the node state object will ZX_DEBUG_ASSERT that neither the source object is not in a container for construction and that neither the source nor the destination object exist in containers during assignment. Regardless of whether or not ZX_DEBUG_ASERTs are enabled, the source and destination objects' states will never be modified.

For example:

struct Point : fbl::DoublyLinkedListable<std::unique_ptr<Point>,
                                         fbl::NodeOptions::AllowCopy> {
  float x, y;
};

fbl::DoublyLinkedList<std::unique_ptr<Point>> all_points;

void AddCopy(const Point& pt) {
  // If pt is in a list, this will assert. If asserts are off, pt will remain
  // where it is and new_pt will not start life in a container.
  auto new_pt = std::make_unique<Point>(pt);
  all_points.push_back(std::move(new_pt));
}

So, what if you want to permit copying or moving of an object even while it is in a container? For example, what if you wanted to clone your list of points making use of your copy constructor in order to do so? Users may opt into this behavior as well by passing appropriate combinations of the following:

fbl::NodeOptions::AllowCopyFromContainer
fbl::NodeOptions::AllowMoveFromContainer
fbl::NodeOptions::AllowCopyAndMoveFromContainer

The behavior described above remains the same; node states will never be changed. New objects will start outside of any container and source objects will remain wherever they are. The only difference between the FromContainer version of this option vs the non-FromContainer version is that the FromContainer version will never assert. So, you could clone your list of points with the following.

struct Point : fbl::DoublyLinkedListable<std::unique_ptr<Point>,
                                         fbl::NodeOptions::AllowCopyFromContainer> {
  float x, y;
};

using PointList = fbl::DoublyLinkedList<std::unique_ptr<Point>>;

PointList CloneList(const PointList& list) {
  PointList ret;
  for (const auto& point : list) {
    ret.push_back(std::make_unique<Point>(point));
  }
  return ret;
}

Allowing objects tracked by `unique_ptr` to exist in multiple containers

Usually, it would be a mistake to define an object that can exist in multiple containers concurrently, while tracking those objects in their containers using unique_ptr semantics. In theory, it should be impossible for two different containers to track the same object at the same time, each using something like a unique_ptr as this would violate the uniqueness of the pointer.

To assist in preventing any mistakes here, ContainableBaseClasses will not permit the use of a std::unique_ptr pointer type for any of the specified mix-ins, unless the length of the list of containable base classes is exactly 1.

struct Tag1 {};
struct Tag2 {};

// This is legal
class Obj : public fbl::ContainableBaseClasses<
  fbl::TaggedSinglyLinkedListable<std::unique_ptr<Obj>, Tag1>> { /* ... */ };

// This is not
class Obj : public fbl::ContainableBaseClasses<
  fbl::TaggedSinglyLinkedListable<std::unique_ptr<Obj>, Tag1>,
  fbl::TaggedSinglyLinkedListable<std::unique_ptr<Obj>, Tag2>> { /* ... */ };

// Neither is this
class Obj : public fbl::ContainableBaseClasses<
  fbl::TaggedSinglyLinkedListable<std::unique_ptr<Obj>, Tag1>,
  fbl::TaggedSinglyLinkedListable<Obj*, Tag2>> { /* ... */ };

There are, however, legitimate uses for types that can exist in multiple containers, which are managed using std::unique_ptrs.

First, you may have a situation where an object can exist in two different types of data structure (perhaps a list and a tree), but never the same data structure at the same time. If the uses of the structure are completely disjoint, you may wish to relax the default restriction.

A second reason you might want to allow this is because you have an object whose life is tracked by a container using std::unique_ptr, but for which you want to allow objects to exist in containers on a temporary basis in order to more easily implement some sort of algorithm. Perhaps a set of objects needs to be filtered into a temporary list and then passed to a function that will operate on the filtered set. Or, perhaps they need to be placed into a temporary WAVLTree with a custom sorting/keys in order to check for duplicates.

Whatever the reason, you can permit this behavior by passing the AllowMultiContainerUptr option to the node state types that you use. Here is an example for the disjoint container use case:

struct FreeObjTag {};
struct ActiveObjTag {};
class Obj : public fbl::ContainableBaseClasses<
  fbl::TaggedSinglyLinkedListable<std::unique_ptr<Obj>, FreeObjTag,
                                  fbl::NodeOptions::AllowMultiContainerUptr>,
  fbl::TaggedWAVLTreeContainable<std::unique_ptr<Obj>, ActiveObjTag,
                                 fbl::NodeOptions::AllowMultiContainerUptr>> {
 public:
  using FreeStack = fbl::TaggedSinglyLinkedList<std::unique_ptr<Obj>, FreeObjTag>;
  using ActiveSet = fbl::TaggedWAVLTree<UniqueId, std::unique_ptr<Obj>, ActiveObjTag>;

  // ...
  UniqueId GetKey() const { return unique_id_; }
  void AssignId(UniqueId id) {
    ZX_DEBUG_ASSERT(!fbl::InContainer<ActiveObjTag>(*this));
    unique_id_ = id;
  }
  // ...

 private:
  // ...
};

fbl::Mutex obj_lock_;
Obj::FreeStack free_objects_ TA_GUARDED(obj_lock_);
Obj::ActiveSet active_objects_ TA_GUARDED(obj_lock_);

zx_status_t ActivateObject(UniqueId id) {
  fbl::AutoLock lock(&obj_lock_);

  if (free_objects_.is_empty()) {
    return ZX_ERR_NO_MEMORY;
  }

  auto ptr = free_objects_.pop_front();
  ptr.AssignId(id);
  active_objects_.insert(std::move(ptr));
  return ZX_OK;
}

Allowing O(1) clearing of containers with `clear_unsafe()`

As noted in the Lifecycle checks section, containers of unmanaged pointers may not destruct with objects still in them, and objects cannot destruct while they think that they are still in a container. Either behavior is considered to be an error and will trigger an assert in a debug build.

What if you had a situation where you didn't care that your objects still thought that they were in a container when they destructed? Perhaps you allocated a contiguous slab of memory and carved it up into object that you then placed onto a free list. If you want to free your slab of memory, and you know that all of the objects have been returned to the free list, then why bother walking the list to zero out all of the linked list bookkeeping? This would just be wasted work.

You can bypass these checks and skip the mandatory O(N) unlinking of the list by using the AllowClearUnsafe NodeOption on your objects. When used, the asserts present in the node state object are skipped, and a method on the container called clear_unsafe() becomes available for use. clear_unsafe() will simply reset the container to its original empty state making no effort to clean up the objects' node states. This is a simple O(1) operation. Attempting to call clear_unsafe() on a container that uses a node state object without this flag will trigger a static_assert. Here is a simple example of what this would look like:

class SlabObject :
  public fbl::SinglyLinkedListable<SlabObject*,
                                   fbl::NodeOptions::AllowClearUnsafe> { /* ... */ };

static fbl::Mutex slab_lock;
static SlabObject* slab_memory TA_GUARDED(slab_lock) = nullptr;
static fbl::SizedSinglyLinkedList<SlabObject*> TA_GUARDED(slab_lock) free_objects;

static constexpr size_t kSlabSize = (1 << 20);   // One MB of objects
static constexpr size_t kSlabCount = kSlabSize / sizeof(SlabObject);

zx_status_t InitSlab() {
  fbl::AutoLock lock(&slab_lock);
  if ((slab_memory != nullptr) || !free_objects.is_empty()) {
    return ZX_ERR_BAD_STATE;
  }

  fbl::AllocChecker ac;
  slab_memory = new (&ac) SlabObject[kSlabCount];
  if (!ac.check()) {
    return ZX_ERR_NO_MEMORY;
  }

  for (size_t i = 0; i < kSlabCount; ++i) {
    free_objects.push_front(slab_memory + i);
  }

  return ZX_OK;
}

SlabObject* GetFreeObj() {
  fbl::AutoLock lock(&slab_lock);
  return !free_objects.is_empty() ? free_objects.pop_front() : nullptr;
}

void ReturnObj(SlabObject* obj) {
  fbl::AutoLock lock(&slab_lock);
  ZX_DEBUG_ASSERT(obj != nullptr);
  free_objects.push_front(obj);
}

zx_status_t DeinitSlab() {
  fbl::AutoLock lock(&slab_lock);

  // If not all of our objects have returned, or if we don't have any slab
  // memory allocated, then we cannot de-init our slab.
  if ((slab_memory == nullptr) || (free_objects.size() != kSlabCount)) {
    return ZX_ERR_BAD_STATE;
  }

  // Great, reset the free list with clear unsafe. This basically just sets the
  // head pointer to nullptr.
  free_objects.clear_unsafe();

  // Now give our memory back. Since our objects are flagged with
  // AllowClearUnsafe, node state destructors do nothing. Provided that
  // SlabObject destructors do nothing, this delete should just return memory to
  // the heap and not need to call N destructors.
  delete[] free_objects;
  free_objects = nullptr;

  return ZX_OK;
}

Directly removing objects from whatever container instance they are in.

In general, even though it is sometimes possible, it is not considered best practice to design code that needs to remove objects directly from a container without having a reference to the container itself. As a design principle, users of intrusive containers should always be aware of which container types and instances objects exist in at all times. Still, sometimes direct removal might be the easiest and best option available.

Containers that track size by default might require an O(n) traversal of the data structure in order to find the container to update the bookkeeping if nodes are removed from the container without knowledge of the container instance. Therefore, these containers do not support direct removal. Other container types, such as a SinglyLinkedList, simply cannot do this as they lack a back-pointer to their previous node.

It is, however, possible for an unsized doubly linked list to support direct node removal. To enable this, add the AllowRemoveFromContainer to the node state's NodeOptions. When enabled, node state structures will have a RemoveFromContainer() method available. Calling RemoveFromContainer is identical to calling InContainer. It may be called directly from the object if there is no ambiguity, using explicit types to select the container to remove from when inheritance produces ambiguity, or using the top level fbl::RemoveFromContaier<Tag>(obj_ref) call when using the ContainableBaseClasses helper. See InContainer()

Consider the following use case. You have a bunch of jobs that need to be processed by several stages of a pipeline. The pipeline stages each have a queue of pending work that threads take jobs from, process, and then queue to the next stage of a pipeline.

If you want to cancel a job while it is in flight, how do you easily know which pipeline stage it is in? One answer might be that you don't need to, as long as you can directly remove it from the processing stage it is currently in. This might end up looking like the following:

struct PipelineTag {};
struct ActiveTag {};

fbl::Mutex pipeline_lock;

class Job : public fbl::RefCounted<Job>,
            public fbl::ContainableBaseClasses<
              fbl::TaggedDoublyLinkedListable<fbl::RefPtr<Job>, PipelineTag,
                                              fbl::NodeOptions::AllowRemoveFromContainer>,
              fbl::TaggedWAVLTreeContainable<fbl::RefPtr<Job>, ActiveTag>> {
 public:
  // ...
  UniqueId GetKey() const { return unique_id_; }
  bool is_canceled() const TA_REQ(pipeline_lock) { return cancel_flag_; }
  void set_canceled() TA_REQ(pipeline_lock) { cancel_flag_ = true; }
  // ...
 private:
  bool cancel_flag_ TA_GUARDED(pipeline_lock) = false;
};

using PipelineQueue = fbl::TaggedDoublyLinkedList<fbl::RefPtr<Job>, PipelineTag>;
std::array<PipelineQueue, 10> pipeline_stages TA_GUARDED(pipeline_lock);
fbl::TaggedWAVLTree<fbl::RefPtr<Job>, ActiveTag> active_jobs TA_GUARDED(pipeline_lock);

zx_status_t QueueJob(fbl::RefPtr<Job> job) {
  ZX_DEBUG_ASSERT(job != nullptr);
  {
    fbl::AutoLock lock(&pipeline_lock);

    // Can't queue a job for processing if it is already being processed.
    if (fbl::InContainer<ActiveTag>(*job)) {
      return ZX_ERR_BAD_STATE;
    }

    // If we are not in the active set, then we had better not be in any of the
    // pipeline stages.
    ZX_DEBUG_ASSERT(!fbl::InContainer<PipelineTag>(*job));

    // Put the job into the active set and into the first pipeline stage.
    active_jobs.insert(job);
    pipeline_stages[0].push_back(std::move(job));
  }

  SignalPipelineStage(0);
}

void WorkThread(size_t pipeline_stage) {
  ZX_DEBUG_ASSERT(pipeline_stage < pipeline_stages.size());
  PipelineQueue& our_stage = pipeline_stages[pipeline_stage];
  PipelineQueue* next_stage = ((pipeline_stage + 1) < pipeline_stages.size())
                            ? (pipeline_stages + pipeline_stage + 1)
                            : nullptr;

  while (!QuitTime()) {
    fbl::RefPtr<Job> job;
    {
      // If there is work in our stage, take it out and get to work.
      fbl::AutoLock lock(&pipeline_lock);
      if (!our_stage.is_empty()) {
        job = our_stage.pop_front();
      }
    }

    // Did we not find a job? Just wait for something to do then.
    if (job == nullptr) {
      WaitForPipelineStageWorkOrQuit(pipeline_stage);
      continue;
    }

    // Do the job.
    ProcessJob(job, pipeline_stage);

    // If the job was canceled or reached the end of the pipeline, we will call
    // a handler to take care of it once we are out of the lock.
    void(*handler)(fbl::RefPtr<Job>) = nullptr;
    {
      fbl::AutoLock lock(&pipeline_lock);

      if (job->is_canceled()) {
        // Handle job cancellation if it was flagged for cancel while we were
        // working. No need to take it out of the active set, the cancel
        // operation should have already done that for us.
        ZX_DEBUG_ASSERT(!fbl::InContainer<ActiveTag>(*job));
        handler = HandleCanceledJob;
      } else if (next_stage != nullptr) {
        // Queue to the next stage if there is one.
        next_stage->push_back(std::move(job));
        signal_next_stage = true;
      } else {
        // End of pipeline. This job is finished, remember to take it out of
        // the active set.
        ZX_DEBUG_ASSERT(fbl::InContainer<ActiveTag>(*job));
        active_jobs.erase(*job);
        handler = HandleFinishedJob;
      }
    }

    // Now that we are out of the lock, either signal the next stage so that it
    // knows that it might have some work, or call the chosen handler on the job.
    if (handler) {
      ZX_DEBUG_ASERT(job != nullptr);
      handler(std::move(job));
    } else {
      SignalPipelineStage(pipeline_stage + 1);
    }
  }
}

zx_status_t CancelJob(UniqueId id) {
  fbl::RefPtr<Job> canceled_job;
  {
    fbl::AutoLock lock(&pipeline_lock);

    // Is there an active job with the provided ID?
    auto iter = active_jobs.find(id);
    if (!iter.IsValid()) {
      return ZX_ERR_NOT_FOUND;
    }

    // No matter what, the job is no longer active. Take its reference back from
    // the active job set.
    fbl::RefPtr<Job> job = active_jobs.erase(iter);

    // Flag the job as canceled.
    job->set_canceled();

    // If the job is in a pipeline stage, then no thread is currently working on
    // it. We can just pull it out of whatever stage we are in and we are done.
    if (fbl::InContainer<PipelineTag>(*job)) {
      canceled_job = fbl::RemoveFromContainer<PipelineTag>(*job);
    }
  }

  // Now that we are out of the lock, if we were the ones to pull the job out of
  // the pipeline, we should hand it over to the cancel handler.
  HandleCanceledJob(std::move(canceled_job));
  return ZX_OK;
}

Advanced scenarios

Controlling advanced options with fbl::NodeOptions

Controlling the copy/move behavior of objects while they are in a container

Allowing objects tracked by unique_ptr to exist in multiple containers

Allowing O(1) clearing of containers with clear_unsafe()

Directly removing objects from whatever container instance they are in.

Controlling advanced options with `fbl::NodeOptions`

Allowing objects tracked by `unique_ptr` to exist in multiple containers

Allowing O(1) clearing of containers with `clear_unsafe()`