Using items with multiple containers#

Several of Pigweed’s containers feature instrusive items, where the data needed to track where an item is in a container is stored in the item itself. Intrusive items may be used with multiple containers, provided each of those containers is templated on a type that is not derived from any of the others. This can be achieved using multiple inheritance from distinct types:

 1// The base type for lists can be trivially derived.
 2struct ListItem : public pw::containers::future::IntrusiveList<ListItem>::Item {
 3};
 4
 5// The base type for maps needs a constructor.
 6struct MapPair : public pw::IntrusiveMap<const uint32_t&, MapPair>::Pair {
 7  constexpr MapPair(const uint32_t& id)
 8      : pw::IntrusiveMap<const uint32_t&, MapPair>::Pair(id) {}
 9};
10
11struct Task : public ListItem, public MapPair {
12  uint32_t id = 0;
13  constexpr explicit Task() : MapPair(id) {}
14};
15
16namespace examples {
17
18class Scheduler {
19 public:
20  // Adds a task to the queue, and returns an opaque `id` that identifies it.
21  // Returns INVALID_ARGUMENT if the task is already in the queue.
22  pw::Result<uint32_t> ScheduleTask(Task& task) {
23    if (task.id != 0) {
24      return pw::Status::InvalidArgument();
25    }
26    task.id = ++num_ids_;
27    by_id_.insert(task);
28    queue_.push_back(task);
29    return task.id;
30  }
31
32  // Removes a task associated with a given `id` from the queue.
33  // Returns NOT_FOUND if the task is not in the queue.
34  pw::Status CancelTask(uint32_t id) {
35    auto iter = by_id_.find(id);
36    if (iter == by_id_.end()) {
37      return pw::Status::NotFound();
38    }
39    auto& task = static_cast<Task&>(*iter);
40    by_id_.erase(iter);
41    queue_.remove(task);
42    task.id = 0;
43    return pw::OkStatus();
44  }
45
46  // Runs the next task, if any, and returns its `id`.
47  // Returns NOT_FOUND if the queue is empty.
48  pw::Result<uint32_t> RunTask() {
49    if (queue_.empty()) {
50      return pw::Status::NotFound();
51    }
52    auto& task = static_cast<Task&>(queue_.front());
53    queue_.pop_front();
54    by_id_.erase(task.id);
55    return task.id;
56  }
57
58 private:
59  // NOTE! The containers must be templated on their specific item types, not
60  // the composite `Task` type.
61  pw::containers::future::IntrusiveList<ListItem> queue_;
62  pw::IntrusiveMap<uint32_t, MapPair> by_id_;
63  uint32_t num_ids_ = 0;
64};

If one or more types is derived from another, the compiler will fail to build with an error that ItemType is ambiguous or found in multiple base classes.