1*09537850SAkhilesh Sanikop /* 2*09537850SAkhilesh Sanikop * Copyright 2019 The libgav1 Authors 3*09537850SAkhilesh Sanikop * 4*09537850SAkhilesh Sanikop * Licensed under the Apache License, Version 2.0 (the "License"); 5*09537850SAkhilesh Sanikop * you may not use this file except in compliance with the License. 6*09537850SAkhilesh Sanikop * You may obtain a copy of the License at 7*09537850SAkhilesh Sanikop * 8*09537850SAkhilesh Sanikop * http://www.apache.org/licenses/LICENSE-2.0 9*09537850SAkhilesh Sanikop * 10*09537850SAkhilesh Sanikop * Unless required by applicable law or agreed to in writing, software 11*09537850SAkhilesh Sanikop * distributed under the License is distributed on an "AS IS" BASIS, 12*09537850SAkhilesh Sanikop * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13*09537850SAkhilesh Sanikop * See the License for the specific language governing permissions and 14*09537850SAkhilesh Sanikop * limitations under the License. 15*09537850SAkhilesh Sanikop */ 16*09537850SAkhilesh Sanikop 17*09537850SAkhilesh Sanikop #ifndef LIBGAV1_SRC_UTILS_STACK_H_ 18*09537850SAkhilesh Sanikop #define LIBGAV1_SRC_UTILS_STACK_H_ 19*09537850SAkhilesh Sanikop 20*09537850SAkhilesh Sanikop #include <cassert> 21*09537850SAkhilesh Sanikop #include <utility> 22*09537850SAkhilesh Sanikop 23*09537850SAkhilesh Sanikop namespace libgav1 { 24*09537850SAkhilesh Sanikop 25*09537850SAkhilesh Sanikop // A LIFO stack of a fixed capacity. The elements are moved using std::move, so 26*09537850SAkhilesh Sanikop // the element type T has to be movable. 27*09537850SAkhilesh Sanikop // 28*09537850SAkhilesh Sanikop // WARNING: No error checking is performed. 29*09537850SAkhilesh Sanikop template <typename T, int capacity> 30*09537850SAkhilesh Sanikop class Stack { 31*09537850SAkhilesh Sanikop public: 32*09537850SAkhilesh Sanikop // Pushes the element |value| to the top of the stack. It is an error to call 33*09537850SAkhilesh Sanikop // Push() when the stack is full. Push(T value)34*09537850SAkhilesh Sanikop void Push(T value) { 35*09537850SAkhilesh Sanikop ++top_; 36*09537850SAkhilesh Sanikop assert(top_ < capacity); 37*09537850SAkhilesh Sanikop elements_[top_] = std::move(value); 38*09537850SAkhilesh Sanikop } 39*09537850SAkhilesh Sanikop 40*09537850SAkhilesh Sanikop // Returns the element at the top of the stack and removes it from the stack. 41*09537850SAkhilesh Sanikop // It is an error to call Pop() when the stack is empty. Pop()42*09537850SAkhilesh Sanikop T Pop() { 43*09537850SAkhilesh Sanikop assert(top_ >= 0); 44*09537850SAkhilesh Sanikop return std::move(elements_[top_--]); 45*09537850SAkhilesh Sanikop } 46*09537850SAkhilesh Sanikop 47*09537850SAkhilesh Sanikop // Returns true if the stack is empty. Empty()48*09537850SAkhilesh Sanikop bool Empty() const { return top_ < 0; } 49*09537850SAkhilesh Sanikop 50*09537850SAkhilesh Sanikop private: 51*09537850SAkhilesh Sanikop static_assert(capacity > 0, ""); 52*09537850SAkhilesh Sanikop T elements_[capacity]; 53*09537850SAkhilesh Sanikop // The array index of the top of the stack. The stack is empty if top_ is -1. 54*09537850SAkhilesh Sanikop int top_ = -1; 55*09537850SAkhilesh Sanikop }; 56*09537850SAkhilesh Sanikop 57*09537850SAkhilesh Sanikop } // namespace libgav1 58*09537850SAkhilesh Sanikop 59*09537850SAkhilesh Sanikop #endif // LIBGAV1_SRC_UTILS_STACK_H_ 60