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 :
11 : #ifndef CIRCULAR_QUEUE_H
12 : #define CIRCULAR_QUEUE_H
13 :
14 : #include "queue.h"
15 : #include <vector>
16 : namespace Hccl {
17 :
18 : template <typename T>
19 : class CircularQueue : public QueueWithSize<T> {
20 : private:
21 : std::vector<T> elems_;
22 : size_t head_;
23 : size_t tail_;
24 : size_t capacity_;
25 :
26 : public:
27 : class Iterator : public Queue<T>::Iterator {
28 : private:
29 : const CircularQueue* queue_{nullptr};
30 :
31 : protected:
32 4172 : void check() override
33 : {
34 4172 : if (queue_ == nullptr) {
35 0 : THROW<InternalException>(StringFormat("CircularQueue::Iterator queue_ is nullptr"));
36 : }
37 4172 : if ((this->it_) == (queue_->elems_.begin() + queue_->tail_)) {
38 9 : this->it_ = queue_->elems_.end();
39 9 : return;
40 : }
41 :
42 4163 : if (queue_->size_ == 0) {
43 0 : THROW<InternalException>(StringFormat("CircularQueue::Iterator queue_ is empty"));
44 : }
45 4163 : size_t now = this->it_ - queue_->elems_.begin();
46 4163 : if ((queue_->head_ < queue_->tail_) && !(queue_->head_ <= now && now < queue_->tail_)) {
47 0 : THROW<InternalException>(StringFormat("CircularQueue<T>::Iterator out of range"));
48 : }
49 4163 : const size_t start_point = 0;
50 4163 : if ((queue_->tail_ <= queue_->head_)
51 4095 : && !(
52 4095 : (start_point <= now && now < queue_->tail_) || (queue_->head_ <= now && now < queue_->capacity_))) {
53 0 : THROW<InternalException>(StringFormat("CircularQueue<T>::Iterator out of range"));
54 : }
55 : }
56 :
57 : public:
58 4253 : Iterator(typename std::vector<T>::const_iterator it, const CircularQueue* queue)
59 : : Queue<T>::Iterator(it),
60 4253 : queue_(queue)
61 : {
62 4253 : if (queue_ == nullptr) {
63 0 : THROW<InternalException>(StringFormat("CircularQueue::Iterator queue_ is nullptr"));
64 : }
65 4253 : if ((this->it_) == (queue_->elems_.begin() + queue_->tail_)) {
66 2082 : this->it_ = queue_->elems_.end();
67 : }
68 4253 : }
69 :
70 8351 : ~Iterator() override = default;
71 :
72 6 : typename Queue<T>::Iterator& operator++() override
73 : {
74 6 : (this->it_) = ((this->it_) - queue_->elems_.begin() + 1) % queue_->capacity_ + queue_->elems_.begin();
75 6 : check();
76 6 : return *this;
77 : }
78 :
79 2050 : typename Queue<T>::Iterator operator++(int) override
80 : {
81 2050 : Iterator temp = *this;
82 2050 : (this->it_) = ((this->it_) - queue_->elems_.begin() + 1) % queue_->capacity_ + queue_->elems_.begin();
83 2050 : check();
84 4100 : return temp;
85 2050 : }
86 :
87 68 : typename Queue<T>::Iterator& operator--() override
88 : {
89 68 : if (this->it_ == queue_->elems_.begin() + queue_->head_) {
90 0 : THROW<InternalException>(StringFormat("CircularQueue<T>::Iterator out of range"));
91 : }
92 68 : if (this->it_ == this->queue_->elems_.end()) {
93 0 : (this->it_) = queue_->elems_.begin() + queue_->tail_;
94 : }
95 68 : (this->it_) = ((this->it_) - queue_->elems_.begin() - 1 + queue_->capacity_) % queue_->capacity_
96 136 : + queue_->elems_.begin();
97 68 : check();
98 68 : return *this;
99 : }
100 :
101 2048 : typename Queue<T>::Iterator operator--(int) override
102 : {
103 2048 : if (this->it_ == queue_->elems_.begin() + queue_->head_) {
104 0 : THROW<InternalException>(StringFormat("CircularQueue<T>::Iterator out of range"));
105 : }
106 2048 : Iterator temp = *this;
107 2048 : if (this->it_ == this->queue_->elems_.end()) {
108 1 : (this->it_) = queue_->elems_.begin() + queue_->tail_;
109 : }
110 2048 : (this->it_) = ((this->it_) - queue_->elems_.begin() - 1 + queue_->capacity_) % queue_->capacity_
111 4096 : + queue_->elems_.begin();
112 2048 : check();
113 4096 : return temp;
114 2048 : }
115 : };
116 :
117 78 : explicit CircularQueue(size_t capacity) : elems_(capacity + 1), head_(0), tail_(0), capacity_(capacity + 1)
118 : {
119 39 : if (capacity_ == 0) {
120 0 : THROW<InternalException>(StringFormat("CircularQueue capacity cannot be zero"));
121 : }
122 39 : }
123 :
124 187 : ~CircularQueue() override { HCCL_INFO("[CircularQueue]Destroy"); }
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 { return this->size_ == Capacity(); }
170 :
171 20250 : size_t Capacity() const override { return capacity_ - 1; }
172 :
173 13 : std::shared_ptr<typename Queue<T>::Iterator> Find(std::function<bool(const T&)> cond) override
174 : {
175 13 : size_t i = head_;
176 13 : size_t count = 0;
177 164 : while (count < this->size_) {
178 161 : if (cond(elems_[i])) {
179 10 : return std::make_shared<Iterator>(elems_.begin() + i, this);
180 : }
181 151 : i = (i + 1) % capacity_;
182 151 : count++;
183 : }
184 3 : return std::make_shared<Iterator>(elems_.begin() + tail_, this);
185 : }
186 :
187 2151 : std::shared_ptr<typename Queue<T>::Iterator> Begin() const override
188 : {
189 2151 : if (this->IsEmpty()) {
190 6 : HCCL_WARNING("[CircularQueue][Begin] Queue is empty!");
191 2 : return std::make_shared<Iterator>(elems_.begin() + tail_, this);
192 : }
193 2149 : return std::make_shared<Iterator>(elems_.begin() + head_, this);
194 : }
195 :
196 13 : std::shared_ptr<typename Queue<T>::Iterator> Tail() const override
197 : {
198 13 : if (this->IsEmpty()) {
199 3 : HCCL_WARNING("[CircularQueue][Tail] Queue is empty!");
200 1 : return std::make_shared<Iterator>(elems_.begin() + tail_, this);
201 : }
202 12 : return std::make_shared<Iterator>(elems_.begin() + (tail_ - 1 + capacity_) % capacity_, this);
203 : }
204 :
205 2076 : std::shared_ptr<typename Queue<T>::Iterator> End() const override
206 : {
207 2076 : return std::make_shared<Iterator>(elems_.begin() + tail_, this);
208 : }
209 : };
210 :
211 : } // namespace Hccl
212 : #endif // CIRCULAR_QUEUE_H
|
