1
#pragma once
2
 
3
#include <kj/common.h>
4
#include <kj/debug.h>
5
#include <kj/exception.h>
6
 
7
#include <concepts>
8
#include <list>
9
 
10
namespace workerd::util {
11
 
12
template <typename T>
13
concept Movable = std::is_move_constructible_v<T> && std::is_move_assignable_v<T>;
14
 
15
// A simple wrapper around std::list that provides a checked queue interface,
16
// ensuring that items can only be moved out of the queue if they exist.
17
// Members are not copyable, only movable. The intention here is to provide
18
// a safe-to-use queue that avoids the pitfalls of using std::list directly
19
// (such as accidentally dangling references when the list is empty but someone
20
// calls front(), etc).
21
template <Movable T>
22
class Queue final {
23
 public:
24
  Queue() = default;
25
  Queue(Queue<T>&&) = default;
26
  Queue<T>& operator=(Queue<T>&&) = default;
27
  KJ_DISALLOW_COPY(Queue);
28
 
29
  inline void push(T&& value) {
30
    inner.push_back(kj::mv(value));
31
  }
32
 
33
  template <typename... Args>
34
  T& emplace(Args&&... args) KJ_LIFETIMEBOUND {
35
    return inner.emplace_back(kj::fwd<Args>(args)...);
36
  }
37
 
38
  // Pops the front element from the queue, moving it out.
39
  // Returns kj::none if the queue is empty.
40
  inline kj::Maybe<T> pop() {
41
    if (inner.empty()) {
42
      return kj::none;
43
    }
44
    T value = kj::mv(inner.front());
45
    inner.pop_front();
46
    // While the kj::mv below is not strictly necessary, I've
47
    // included it intentionally to make it absolutely clear
48
    // that value is being moved and not copied. It's ok to
49
    // refactor that out if it is bothersome.
50
    return kj::mv(value);
51
  }
52
 
53
  // Returns a reference to the front element without removing it.
54
  // Returns kj::none if the queue is empty.
55
  inline kj::Maybe<T&> peek() KJ_LIFETIMEBOUND {
56
    if (inner.empty()) {
57
      return kj::none;
58
    }
59
    return inner.front();
60
  }
61
 
62
  // Returns a reference to the front element without removing it.
63
  // Returns kj::none if the queue is empty.
64
  inline kj::Maybe<const T&> peek() const KJ_LIFETIMEBOUND {
65
    if (inner.empty()) {
66
      return kj::none;
67
    }
68
    return inner.front();
69
  }
70
 
71
  // Returns a reference to the last element without removing it.
72
  // Returns kj::none if the queue is empty.
73
  inline kj::Maybe<T&> peekBack() KJ_LIFETIMEBOUND {
74
    if (inner.empty()) {
75
      return kj::none;
76
    }
77
    return inner.back();
78
  }
79
 
80
  // Returns a reference to the last element without removing it.
81
  // Returns kj::none if the queue is empty.
82
  inline kj::Maybe<const T&> peekBack() const KJ_LIFETIMEBOUND {
83
    if (inner.empty()) {
84
      return kj::none;
85
    }
86
    return inner.back();
87
  }
88
 
89
  // Drains the queue, moving each element to the callback one at a time.
90
  // Returns the number of elements moved.
91
  inline size_t drainTo(auto callback) {
92
    size_t count = 0;
93
    while (!inner.empty()) {
94
      callback(KJ_ASSERT_NONNULL(pop()));
95
      count++;
96
    }
97
    return count;
98
  }
99
 
100
  // Removes elements from the queue that satisfy the given condition.
101
  // Returns the number of elements removed.
102
  inline size_t deleteIf(auto callback) {
103
    size_t count = 0;
104
    auto it = inner.begin();
105
    while (it != inner.end()) {
106
      if (callback(*it)) {
107
        it = inner.erase(it);
108
        count++;
109
      } else {
110
        ++it;
111
      }
112
    }
113
    return count;
114
  }
115
 
116
  // Takes the first element in the queue that satisfies the given condition, if any.
117
  inline kj::Maybe<T> takeIf(auto callback) {
118
    for (auto it = inner.begin(); it != inner.end(); ++it) {
119
      if (callback(*it)) {
120
        T value = kj::mv(*it);
121
        inner.erase(it);
122
        return kj::mv(value);
123
      }
124
    }
125
    return kj::none;
126
  }
127
 
128
  // Applies the callback to each element in the queue.
129
  // Returns the number of elements processed.
130
  // If the callback returns false, the iteration stops.
131
  inline size_t forEach(auto callback) const {
132
    size_t count = 0;
133
    for (const auto& item: inner) {
134
      count++;
135
      if constexpr (std::is_void_v<decltype(callback(item))>) {
136
        callback(item);
137
      } else {
138
        if (!callback(item)) break;
139
      }
140
    }
141
    return count;
142
  }
143
 
144
  // Checks if the queue is empty.
145
  inline bool empty() const {
146
    return inner.empty();
147
  }
148
 
149
  // Returns the number of elements in the queue.
150
  inline size_t size() const {
151
    return inner.size();
152
  }
153
 
154
  // Clears the queue, removing all elements.
155
  inline void clear() {
156
    inner.clear();
157
  }
158
 
159
  // Swap the contents of this queue with another.
160
  inline void swap(Queue<T>& other) {
161
    inner.swap(other.inner);
162
  }
163
 
164
  // Delete the new and delete operators to prevent heap allocation.
165
  void* operator new(size_t) = delete;
166
  void operator delete(void*) = delete;
167
 
168
 private:
169
  std::list<T> inner;
170
};
171
}  // namespace workerd::util