Line data Source code
1 : /**
2 : * Copyright (c) 2025 Huawei Technologies Co., Ltd.
3 : * This program is free software, you can redistribute it and/or modify it under the terms and conditions of
4 : * CANN Open Software License Agreement Version 2.0 (the "License").
5 : * Please refer to the License for details. You may not use this file except in compliance with the License.
6 : * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR IMPLIED,
7 : * INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY, OR FITNESS FOR A PARTICULAR PURPOSE.
8 : * See LICENSE in the root of the software repository for the full text of the License.
9 : */
10 : #ifndef CIRCULAR_QUEUE_H
11 : #define CIRCULAR_QUEUE_H
12 :
13 : #include "queue.h"
14 : #include <vector>
15 : namespace Hccl {
16 :
17 : template <typename T> class CircularQueue : public QueueWithSize<T> {
18 : private:
19 : std::vector<T> elems_;
20 : size_t head_;
21 : size_t tail_;
22 : size_t capacity_;
23 :
24 : public:
25 : class Iterator : public Queue<T>::Iterator {
26 : private:
27 : const CircularQueue *queue_{nullptr};
28 :
29 : protected:
30 4172 : void check() override
31 : {
32 4172 : if (queue_ == nullptr) {
33 0 : THROW<InternalException>(StringFormat("CircularQueue::Iterator queue_ is nullptr"));
34 : }
35 4172 : if ((this->it_) == (queue_->elems_.begin() + queue_->tail_)) {
36 9 : this->it_ = queue_->elems_.end();
37 9 : return;
38 : }
39 :
40 4163 : if (queue_->size_ == 0) {
41 0 : THROW<InternalException>(StringFormat("CircularQueue::Iterator queue_ is empty"));
42 : }
43 4163 : size_t now = this->it_ - queue_->elems_.begin();
44 4163 : if ((queue_->head_ < queue_->tail_) && !(queue_->head_ <= now && now < queue_->tail_)) {
45 0 : THROW<InternalException>(StringFormat("CircularQueue<T>::Iterator out of range"));
46 : }
47 4163 : const size_t start_point = 0;
48 4163 : if ((queue_->tail_ <= queue_->head_)
49 4095 : && !((start_point <= now && now < queue_->tail_)
50 487 : || (queue_->head_ <= now && now < queue_->capacity_))) {
51 0 : THROW<InternalException>(StringFormat("CircularQueue<T>::Iterator out of range"));
52 : }
53 : }
54 :
55 : public:
56 4253 : Iterator(typename std::vector<T>::const_iterator it, const CircularQueue *queue) : Queue<T>::Iterator(it), queue_(queue)
57 : {
58 4253 : if (queue_ == nullptr) {
59 0 : THROW<InternalException>(StringFormat("CircularQueue::Iterator queue_ is nullptr"));
60 : }
61 4253 : if ((this->it_) == (queue_->elems_.begin() + queue_->tail_)) {
62 2082 : this->it_ = queue_->elems_.end();
63 : }
64 4253 : }
65 :
66 8351 : ~Iterator() override = default;
67 :
68 6 : typename Queue<T>::Iterator &operator++() override
69 : {
70 6 : (this->it_) = ((this->it_) - queue_->elems_.begin() + 1) % queue_->capacity_ + queue_->elems_.begin();
71 6 : check();
72 6 : return *this;
73 : }
74 :
75 2050 : typename Queue<T>::Iterator operator++(int) override
76 : {
77 2050 : Iterator temp = *this;
78 2050 : (this->it_) = ((this->it_) - queue_->elems_.begin() + 1) % queue_->capacity_ + queue_->elems_.begin();
79 2050 : check();
80 4100 : return temp;
81 2050 : }
82 :
83 68 : typename Queue<T>::Iterator &operator--() override
84 : {
85 68 : if (this->it_ == queue_->elems_.begin() + queue_->head_) {
86 0 : THROW<InternalException>(StringFormat("CircularQueue<T>::Iterator out of range"));
87 : }
88 68 : if (this->it_ == this->queue_->elems_.end()) {
89 0 : (this->it_) = queue_->elems_.begin() + queue_->tail_;
90 : }
91 68 : (this->it_) = ((this->it_) - queue_->elems_.begin() - 1 + queue_->capacity_) % queue_->capacity_
92 136 : + queue_->elems_.begin();
93 68 : check();
94 68 : return *this;
95 : }
96 :
97 2048 : typename Queue<T>::Iterator operator--(int) override
98 : {
99 2048 : if (this->it_ == queue_->elems_.begin() + queue_->head_) {
100 0 : THROW<InternalException>(StringFormat("CircularQueue<T>::Iterator out of range"));
101 : }
102 2048 : Iterator temp = *this;
103 2048 : if (this->it_ == this->queue_->elems_.end()) {
104 1 : (this->it_) = queue_->elems_.begin() + queue_->tail_;
105 : }
106 2048 : (this->it_) = ((this->it_) - queue_->elems_.begin() - 1 + queue_->capacity_) % queue_->capacity_
107 4096 : + queue_->elems_.begin();
108 2048 : check();
109 4096 : return temp;
110 2048 : }
111 : };
112 :
113 38 : explicit CircularQueue(size_t capacity)
114 76 : : elems_(capacity + 1), head_(0), tail_(0), capacity_(capacity + 1)
115 : {
116 38 : if (capacity_ == 0) {
117 0 : THROW<InternalException>(StringFormat("CircularQueue capacity cannot be zero"));
118 : }
119 38 : }
120 :
121 74 : ~CircularQueue() override
122 : {
123 110 : HCCL_INFO("[CircularQueue]Destroy");
124 112 : }
125 :
126 38 : void Append(T &&value) override
127 : {
128 38 : if (IsFull()) {
129 0 : head_ = (head_ + 1) % capacity_;
130 0 : this->size_--;
131 : }
132 38 : elems_[tail_] = std::move(value);
133 38 : tail_ = (tail_ + 1) % capacity_;
134 38 : this->size_++;
135 38 : }
136 :
137 10106 : T& GetAndUpdate() override
138 : {
139 10106 : if (IsFull()) {
140 7952 : head_ = (head_ + 1) % capacity_;
141 7952 : this->size_--;
142 : }
143 10106 : auto curTail = tail_;
144 10106 : tail_ = (tail_ + 1) % capacity_;
145 10106 : this->size_++;
146 10106 : return elems_[curTail];
147 : }
148 :
149 1 : void PopFront() override
150 : {
151 1 : if (this->IsEmpty()) {
152 0 : THROW<InternalException>(StringFormat("CircularQueue<T>::PopFront Queue is empty!"));
153 : }
154 1 : head_ = (head_ + 1) % capacity_;
155 1 : this->size_--;
156 1 : }
157 :
158 0 : void Traverse(std::function<void(const T &)> action) override
159 : {
160 0 : size_t i = head_;
161 0 : size_t count = 0;
162 0 : while (count < this->size_) {
163 0 : action(elems_[i]);
164 0 : i = (i + 1) % capacity_;
165 0 : count++;
166 : }
167 0 : }
168 :
169 10144 : bool IsFull() const override
170 : {
171 10144 : return this->size_ == Capacity();
172 : }
173 :
174 20250 : size_t Capacity() const override
175 : {
176 20250 : return capacity_ - 1;
177 : }
178 :
179 13 : std::shared_ptr<typename Queue<T>::Iterator> Find(std::function<bool(const T &)> cond) override
180 : {
181 13 : size_t i = head_;
182 13 : size_t count = 0;
183 166 : while (count < this->size_) {
184 163 : if (cond(elems_[i])) {
185 10 : return std::make_shared<Iterator>(elems_.begin() + i, this);
186 : }
187 153 : i = (i + 1) % capacity_;
188 153 : count++;
189 : }
190 3 : return std::make_shared<Iterator>(elems_.begin() + tail_, this);
191 : }
192 :
193 2151 : std::shared_ptr<typename Queue<T>::Iterator> Begin() const override
194 : {
195 2151 : if (this->IsEmpty()) {
196 6 : HCCL_WARNING("[CircularQueue][Begin] Queue is empty!");
197 2 : return std::make_shared<Iterator>(elems_.begin() + tail_, this);
198 : }
199 2149 : return std::make_shared<Iterator>(elems_.begin() + head_, this);
200 : }
201 :
202 13 : std::shared_ptr<typename Queue<T>::Iterator> Tail() const override
203 : {
204 13 : if (this->IsEmpty()) {
205 3 : HCCL_WARNING("[CircularQueue][Tail] Queue is empty!");
206 1 : return std::make_shared<Iterator>(elems_.begin() + tail_, this);
207 : }
208 12 : return std::make_shared<Iterator>(elems_.begin() + (tail_ - 1 + capacity_) % capacity_, this);
209 : }
210 :
211 2076 : std::shared_ptr<typename Queue<T>::Iterator> End() const override
212 : {
213 2076 : return std::make_shared<Iterator>(elems_.begin() + tail_, this);
214 : }
215 : };
216 :
217 : } // namespace Hccl
218 : #endif // CIRCULAR_QUEUE_H
|
