1 // Copyright 2017 The Fuchsia Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #pragma once
6 
7 #include <fbl/intrusive_single_list.h>
8 #include <fbl/macros.h>
9 
10 #include <utility>
11 
12 namespace fs {
13 
14 // A wrapper around a singly linked list to make it appear as a queue.
15 // We pop from the front (moving the head forward) and push onto the tail.
16 template <typename PtrType>
17 class Queue {
18 public:
19     using QueueType = fbl::SinglyLinkedList<PtrType>;
Queue()20     Queue() : next_(queue_.end()) {}
~Queue()21     ~Queue() { ZX_DEBUG_ASSERT(is_empty()); }
22 
23     template <typename T>
push(T && ptr)24     void push(T&& ptr) {
25         if (queue_.is_empty()) {
26             queue_.push_front(std::forward<T>(ptr));
27             next_ = queue_.begin();
28         } else {
29             auto to_be_next = queue_.make_iterator(*ptr);
30             queue_.insert_after(next_, std::forward<T>(ptr));
31             next_ = to_be_next;
32         }
33     }
34 
front()35     typename QueueType::PtrTraits::RefType      front()       { return queue_.front(); }
front()36     typename QueueType::PtrTraits::ConstRefType front() const { return queue_.front(); }
37 
pop()38     PtrType pop() { return queue_.pop_front(); }
39 
is_empty()40     bool is_empty() const { return queue_.is_empty(); }
41 
42 private:
43     // Add work to the front of the queue, remove work from the back
44     QueueType queue_;
45     typename QueueType::iterator next_;
46 };
47 
48 }
49