1 /*
2  * Copyright (C) 2013 The Android Open Source Project
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 ART_LIBARTBASE_BASE_BOUNDED_FIFO_H_
18 #define ART_LIBARTBASE_BASE_BOUNDED_FIFO_H_
19 
20 #include <android-base/logging.h>
21 
22 #include "bit_utils.h"
23 
24 namespace art {
25 
26 // A bounded fifo is a fifo which has a bounded size. The power of two version uses a bit mask to
27 // avoid needing to deal with wrapping integers around or using a modulo operation.
28 template <typename T, const size_t kMaxSize>
29 class BoundedFifoPowerOfTwo {
30   static_assert(IsPowerOfTwo(kMaxSize), "kMaxSize must be a power of 2.");
31 
32  public:
33   BoundedFifoPowerOfTwo() {
34     clear();
35   }
36 
37   void clear() {
38     back_index_ = 0;
39     size_ = 0;
40   }
41 
42   bool empty() const {
43     return size() == 0;
44   }
45 
46   size_t size() const {
47     return size_;
48   }
49 
50   void push_back(const T& value) {
51     ++size_;
52     DCHECK_LE(size_, kMaxSize);
53     // Relies on integer overflow behavior.
54     data_[back_index_++ & mask_] = value;
55   }
56 
57   const T& front() const {
58     DCHECK_GT(size_, 0U);
59     return data_[(back_index_ - size_) & mask_];
60   }
61 
62   void pop_front() {
63     DCHECK_GT(size_, 0U);
64     --size_;
65   }
66 
67  private:
68   static const size_t mask_ = kMaxSize - 1;
69   size_t back_index_, size_;
70   T data_[kMaxSize];
71 };
72 
73 }  // namespace art
74 
75 #endif  // ART_LIBARTBASE_BASE_BOUNDED_FIFO_H_
76