1 /** 2 * Copyright (c) 2021-2024 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 #ifndef PANDA_VERIFIER_UTIL_OBJ_POOL_HPP_ 17 #define PANDA_VERIFIER_UTIL_OBJ_POOL_HPP_ 18 19 #include "macros.h" 20 21 #include <cstdint> 22 #include <optional> 23 #include <utility> 24 25 namespace ark::verifier { 26 27 template <typename T, template <typename...> class Vector, typename InitializerType = void (*)(T &, std::size_t), 28 typename CleanerType = void (*)(T &)> 29 class ObjPool { 30 public: 31 class Accessor { 32 public: Accessor()33 Accessor() : idx_ {0}, pool_ {nullptr}, prev_ {nullptr}, next_ {nullptr} {} Accessor(std::size_t index,ObjPool * objPool)34 Accessor(std::size_t index, ObjPool *objPool) : idx_ {index}, pool_ {objPool}, prev_ {nullptr}, next_ {nullptr} 35 { 36 Insert(); 37 } Accessor(const Accessor & p)38 Accessor(const Accessor &p) : idx_ {p.idx_}, pool_ {p.pool_}, prev_ {nullptr}, next_ {nullptr} 39 { 40 Insert(); 41 } Accessor(Accessor && p)42 Accessor(Accessor &&p) : idx_ {p.idx_}, pool_ {p.pool_}, prev_ {p.prev_}, next_ {p.next_} 43 { 44 p.Reset(); 45 Rebind(); 46 } 47 Accessor &operator=(const Accessor &p) 48 { 49 if (&p == this) { 50 return *this; 51 } 52 Erase(); 53 Reset(); 54 idx_ = p.idx_; 55 pool_ = p.pool_; 56 Insert(); 57 return *this; 58 } 59 Accessor &operator=(Accessor &&p) 60 { 61 Erase(); 62 idx_ = p.idx_; 63 pool_ = p.pool_; 64 prev_ = p.prev_; 65 next_ = p.next_; 66 p.Reset(); 67 Rebind(); 68 return *this; 69 } ~Accessor()70 ~Accessor() 71 { 72 Erase(); 73 } 74 T &operator*() 75 { 76 return pool_->storage_[idx_]; 77 } 78 const T &operator*() const 79 { 80 return pool_->storage_[idx_]; 81 } 82 // NOLINTNEXTLINE(google-explicit-constructor) 83 operator bool() const 84 { 85 return pool_ != nullptr; 86 } Free()87 void Free() 88 { 89 Erase(); 90 Reset(); 91 } 92 93 private: Reset()94 void Reset() 95 { 96 idx_ = 0; 97 pool_ = nullptr; 98 prev_ = nullptr; 99 next_ = nullptr; 100 } Insert()101 void Insert() 102 { 103 if (pool_ != nullptr) { 104 next_ = pool_->accessors_[idx_]; 105 if (next_ != nullptr) { 106 next_->prev_ = this; 107 } 108 pool_->accessors_[idx_] = this; 109 } 110 } Erase()111 void Erase() 112 { 113 if (pool_ != nullptr) { 114 if (prev_ == nullptr) { 115 pool_->accessors_[idx_] = next_; 116 if (pool_->accessors_[idx_] == nullptr) { 117 pool_->cleaner_(pool_->storage_[idx_]); 118 pool_->free_.push_back(idx_); 119 } 120 } else { 121 prev_->next_ = next_; 122 } 123 if (next_ != nullptr) { 124 next_->prev_ = prev_; 125 } 126 } 127 } Rebind()128 void Rebind() 129 { 130 if (pool_ != nullptr) { 131 if (prev_ != nullptr) { 132 prev_->next_ = this; 133 } else { 134 pool_->accessors_[idx_] = this; 135 } 136 if (next_ != nullptr) { 137 next_->prev_ = this; 138 } 139 } 140 } 141 142 std::size_t idx_; 143 ObjPool *pool_; 144 Accessor *prev_; 145 Accessor *next_; 146 147 friend class ObjPool; 148 }; 149 ObjPool(InitializerType initializer,CleanerType cleaner)150 ObjPool(InitializerType initializer, CleanerType cleaner) : initializer_ {initializer}, cleaner_ {cleaner} {} ObjPool(InitializerType initializer)151 explicit ObjPool(InitializerType initializer) : initializer_ {initializer}, cleaner_ {[](T &) { return; }} {} ObjPool()152 ObjPool() : initializer_ {[](T &, std::size_t) { return; }}, cleaner_ {[](T &) { return; }} {} 153 154 ~ObjPool() = default; 155 156 DEFAULT_MOVE_SEMANTIC(ObjPool); 157 DEFAULT_COPY_SEMANTIC(ObjPool); 158 New()159 Accessor New() 160 { 161 std::size_t idx; 162 if (FreeCount() > 0) { 163 idx = free_.back(); 164 free_.pop_back(); 165 } else { 166 idx = storage_.size(); 167 storage_.emplace_back(); 168 accessors_.emplace_back(nullptr); 169 } 170 initializer_(storage_[idx], idx); 171 return Accessor {idx, this}; 172 } 173 FreeCount()174 std::size_t FreeCount() const 175 { 176 return free_.size(); 177 } 178 Count()179 std::size_t Count() const 180 { 181 return storage_.size(); 182 } 183 AccCount()184 std::size_t AccCount() const 185 { 186 size_t count = 0; 187 for (auto el : accessors_) { 188 Accessor *acc = el; 189 while (acc != nullptr) { 190 ++count; 191 acc = acc->next_; 192 } 193 } 194 return count; 195 } 196 AllObjects()197 auto AllObjects() 198 { 199 thread_local size_t idx = 0; 200 return [this]() -> std::optional<Accessor> { 201 while (idx < storage_.size() && accessors_[idx] == nullptr) { 202 ++idx; 203 } 204 if (idx >= storage_.size()) { 205 idx = 0; 206 return std::nullopt; 207 } 208 return {Accessor {idx++, this}}; 209 }; 210 } 211 ShrinkToFit()212 void ShrinkToFit() 213 { 214 size_t idx1 = 0; 215 size_t idx2 = storage_.size() - 1; 216 while (idx1 < idx2) { 217 while ((idx1 < idx2) && (accessors_[idx1] != nullptr)) { 218 ++idx1; 219 } 220 while ((idx1 < idx2) && (accessors_[idx2] == nullptr)) { 221 --idx2; 222 } 223 if (idx1 < idx2) { 224 storage_[idx1] = std::move(storage_[idx2]); 225 accessors_[idx1] = accessors_[idx2]; 226 Accessor *acc = accessors_[idx1]; 227 while (acc != nullptr) { 228 acc->idx_ = idx1; 229 acc = acc->next_; 230 } 231 --idx2; 232 } 233 } 234 if (accessors_[idx1] != nullptr) { 235 ++idx1; 236 } 237 storage_.resize(idx1); 238 storage_.shrink_to_fit(); 239 accessors_.resize(idx1); 240 accessors_.shrink_to_fit(); 241 free_.clear(); 242 free_.shrink_to_fit(); 243 } 244 245 private: 246 InitializerType initializer_; 247 CleanerType cleaner_; 248 249 Vector<T> storage_; 250 Vector<std::size_t> free_; 251 Vector<Accessor *> accessors_; 252 }; 253 254 } // namespace ark::verifier 255 256 #endif // !PANDA_VERIFIER_UTIL_OBJ_POOL_HPP_ 257