• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright 2019 The libgav1 Authors
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef LIBGAV1_SRC_UTILS_QUEUE_H_
18 #define LIBGAV1_SRC_UTILS_QUEUE_H_
19 
20 #include <cassert>
21 #include <cstddef>
22 #include <memory>
23 #include <new>
24 
25 #include "src/utils/compiler_attributes.h"
26 
27 namespace libgav1 {
28 
29 // A FIFO queue of a fixed capacity.
30 //
31 // WARNING: No error checking is performed.
32 template <typename T>
33 class Queue {
34  public:
Init(size_t capacity)35   LIBGAV1_MUST_USE_RESULT bool Init(size_t capacity) {
36     elements_.reset(new (std::nothrow) T[capacity]);
37     if (elements_ == nullptr) return false;
38     capacity_ = capacity;
39     return true;
40   }
41 
42   // Pushes the element |value| to the end of the queue. It is an error to call
43   // Push() when the queue is full.
Push(T && value)44   void Push(T&& value) {
45     assert(size_ < capacity_);
46     elements_[end_++] = std::move(value);
47     if (end_ == capacity_) end_ = 0;
48     ++size_;
49   }
50 
51   // Removes the element at the front of the queue. It is an error to call Pop()
52   // when the queue is empty.
Pop()53   void Pop() {
54     assert(size_ != 0);
55     const T element = std::move(elements_[begin_++]);
56     static_cast<void>(element);
57     if (begin_ == capacity_) begin_ = 0;
58     --size_;
59   }
60 
61   // Returns a reference to the element at the front of the queue. It is an
62   // error to call Front() when the queue is empty.
Front()63   T& Front() {
64     assert(size_ != 0);
65     return elements_[begin_];
66   }
67 
68   // Returns a reference to the element at the back of the queue. It is an error
69   // to call Back() when the queue is empty.
Back()70   T& Back() {
71     assert(size_ != 0);
72     const size_t back = ((end_ == 0) ? capacity_ : end_) - 1;
73     return elements_[back];
74   }
75 
76   // Clears the queue.
Clear()77   void Clear() {
78     while (!Empty()) {
79       Pop();
80     }
81   }
82 
83   // Returns true if the queue is empty.
Empty()84   bool Empty() const { return size_ == 0; }
85 
86   // Returns true if the queue is full.
Full()87   bool Full() const { return size_ >= capacity_; }
88 
89   // Returns the number of elements in the queue.
Size()90   size_t Size() const { return size_; }
91 
92  private:
93   // An array of |capacity| elements. Used as a circular array.
94   std::unique_ptr<T[]> elements_;
95   size_t capacity_ = 0;
96   // The index of the element to be removed by Pop().
97   size_t begin_ = 0;
98   // The index where the new element is inserted by Push().
99   size_t end_ = 0;
100   size_t size_ = 0;
101 };
102 
103 }  // namespace libgav1
104 
105 #endif  // LIBGAV1_SRC_UTILS_QUEUE_H_
106