1 // Copyright 2024 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14
15 #include <cstdint>
16
17 #include "pw_containers/intrusive_list.h"
18 #include "pw_containers/intrusive_map.h"
19 #include "pw_result/result.h"
20 #include "pw_status/status.h"
21 #include "pw_unit_test/framework.h"
22
23 // DOCSTAG: [pw_containers-multiple_containers]
24
25 // The base type for lists can be trivially derived.
26 struct ListItem : public pw::containers::future::IntrusiveList<ListItem>::Item {
27 };
28
29 // The base type for maps needs a constructor.
30 struct MapPair : public pw::IntrusiveMap<const uint32_t&, MapPair>::Pair {
MapPairMapPair31 constexpr MapPair(const uint32_t& id)
32 : pw::IntrusiveMap<const uint32_t&, MapPair>::Pair(id) {}
33 };
34
35 struct Task : public ListItem, public MapPair {
36 uint32_t id = 0;
TaskTask37 constexpr explicit Task() : MapPair(id) {}
38 };
39
40 namespace examples {
41
42 class Scheduler {
43 public:
44 // Adds a task to the queue, and returns an opaque `id` that identifies it.
45 // Returns INVALID_ARGUMENT the task is already in the queue.
ScheduleTask(Task & task)46 pw::Result<uint32_t> ScheduleTask(Task& task) {
47 if (task.id != 0) {
48 return pw::Status::InvalidArgument();
49 }
50 task.id = ++num_ids_;
51 by_id_.insert(task);
52 queue_.push_back(task);
53 return task.id;
54 }
55
56 // Removes a task associated with a given `id` from the queue.
57 // Returns NOT_FOUND if the task is not in the queue.
CancelTask(uint32_t id)58 pw::Status CancelTask(uint32_t id) {
59 auto iter = by_id_.find(id);
60 if (iter == by_id_.end()) {
61 return pw::Status::NotFound();
62 }
63 auto& task = static_cast<Task&>(*iter);
64 by_id_.erase(iter);
65 queue_.remove(task);
66 task.id = 0;
67 return pw::OkStatus();
68 }
69
70 // Runs the next task, if any, and returns its `id`.
71 // Returns NOT_FOUND if the queue is empty.
RunTask()72 pw::Result<uint32_t> RunTask() {
73 if (queue_.empty()) {
74 return pw::Status::NotFound();
75 }
76 auto& task = static_cast<Task&>(queue_.front());
77 queue_.pop_front();
78 by_id_.erase(task.id);
79 return task.id;
80 }
81
82 private:
83 // NOTE! The containers must be templated on their specific item types, not
84 // the composite `Task` type.
85 pw::containers::future::IntrusiveList<ListItem> queue_;
86 pw::IntrusiveMap<uint32_t, MapPair> by_id_;
87 uint32_t num_ids_ = 0;
88 };
89
90 // DOCSTAG: [pw_containers-multiple_containers]
91
92 } // namespace examples
93
94 namespace {
95
TEST(ListedAndMappedExampleTest,RunScheduler)96 TEST(ListedAndMappedExampleTest, RunScheduler) {
97 examples::Scheduler scheduler;
98 constexpr size_t kNumTasks = 10;
99 std::array<Task, kNumTasks> tasks;
100 std::array<uint32_t, kNumTasks> ids;
101 pw::Result<uint32_t> result;
102
103 for (size_t i = 0; i < tasks.size(); ++i) {
104 result = scheduler.ScheduleTask(tasks[i]);
105 ASSERT_EQ(result.status(), pw::OkStatus());
106 ids[i] = *result;
107 }
108 result = scheduler.ScheduleTask(tasks[0]);
109 EXPECT_EQ(result.status(), pw::Status::InvalidArgument());
110
111 EXPECT_EQ(scheduler.CancelTask(ids[3]), pw::OkStatus());
112 EXPECT_EQ(scheduler.CancelTask(ids[7]), pw::OkStatus());
113 EXPECT_EQ(scheduler.CancelTask(ids[7]), pw::Status::NotFound());
114
115 for (size_t i = 0; i < tasks.size(); ++i) {
116 if (i % 4 == 3) {
117 continue;
118 }
119 result = scheduler.RunTask();
120 ASSERT_EQ(result.status(), pw::OkStatus());
121 EXPECT_EQ(*result, ids[i]);
122 }
123 result = scheduler.RunTask();
124 EXPECT_EQ(result.status(), pw::Status::NotFound());
125 }
126
127 } // namespace
128