Martin Stjernholm | c15e7e4 | 2020-12-02 22:50:53 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2011 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_STL_UTIL_H_ |
| 18 | #define ART_LIBARTBASE_BASE_STL_UTIL_H_ |
| 19 | |
| 20 | #include <algorithm> |
| 21 | #include <iterator> |
| 22 | #include <set> |
| 23 | #include <sstream> |
| 24 | |
| 25 | #include <android-base/logging.h> |
| 26 | |
| 27 | #include "base/iteration_range.h" |
| 28 | |
| 29 | namespace art { |
| 30 | |
| 31 | // STLDeleteContainerPointers() |
| 32 | // For a range within a container of pointers, calls delete |
| 33 | // (non-array version) on these pointers. |
| 34 | // NOTE: for these three functions, we could just implement a DeleteObject |
| 35 | // functor and then call for_each() on the range and functor, but this |
| 36 | // requires us to pull in all of algorithm.h, which seems expensive. |
| 37 | // For hash_[multi]set, it is important that this deletes behind the iterator |
| 38 | // because the hash_set may call the hash function on the iterator when it is |
| 39 | // advanced, which could result in the hash function trying to deference a |
| 40 | // stale pointer. |
| 41 | template <class ForwardIterator> |
| 42 | void STLDeleteContainerPointers(ForwardIterator begin, |
| 43 | ForwardIterator end) { |
| 44 | while (begin != end) { |
| 45 | ForwardIterator temp = begin; |
| 46 | ++begin; |
| 47 | delete *temp; |
| 48 | } |
| 49 | } |
| 50 | |
| 51 | // STLDeleteElements() deletes all the elements in an STL container and clears |
| 52 | // the container. This function is suitable for use with a vector, set, |
| 53 | // hash_set, or any other STL container which defines sensible begin(), end(), |
| 54 | // and clear() methods. |
| 55 | // |
| 56 | // If container is null, this function is a no-op. |
| 57 | // |
| 58 | // As an alternative to calling STLDeleteElements() directly, consider |
| 59 | // using a container of std::unique_ptr, which ensures that your container's |
| 60 | // elements are deleted when the container goes out of scope. |
| 61 | template <class T> |
| 62 | void STLDeleteElements(T *container) { |
| 63 | if (container != nullptr) { |
| 64 | STLDeleteContainerPointers(container->begin(), container->end()); |
| 65 | container->clear(); |
| 66 | } |
| 67 | } |
| 68 | |
| 69 | // Given an STL container consisting of (key, value) pairs, STLDeleteValues |
| 70 | // deletes all the "value" components and clears the container. Does nothing |
| 71 | // in the case it's given a null pointer. |
| 72 | template <class T> |
| 73 | void STLDeleteValues(T *v) { |
| 74 | if (v != nullptr) { |
| 75 | for (typename T::iterator i = v->begin(); i != v->end(); ++i) { |
| 76 | delete i->second; |
| 77 | } |
| 78 | v->clear(); |
| 79 | } |
| 80 | } |
| 81 | |
| 82 | // Deleter using free() for use with std::unique_ptr<>. See also UniqueCPtr<> below. |
| 83 | struct FreeDelete { |
| 84 | // NOTE: Deleting a const object is valid but free() takes a non-const pointer. |
| 85 | void operator()(const void* ptr) const { |
| 86 | free(const_cast<void*>(ptr)); |
| 87 | } |
| 88 | }; |
| 89 | |
| 90 | // Alias for std::unique_ptr<> that uses the C function free() to delete objects. |
| 91 | template <typename T> |
| 92 | using UniqueCPtr = std::unique_ptr<T, FreeDelete>; |
| 93 | |
| 94 | // Find index of the first element with the specified value known to be in the container. |
| 95 | template <typename Container, typename T> |
| 96 | size_t IndexOfElement(const Container& container, const T& value) { |
| 97 | auto it = std::find(container.begin(), container.end(), value); |
| 98 | DCHECK(it != container.end()); // Must exist. |
| 99 | return std::distance(container.begin(), it); |
| 100 | } |
| 101 | |
| 102 | // Remove the first element with the specified value known to be in the container. |
| 103 | template <typename Container, typename T> |
| 104 | void RemoveElement(Container& container, const T& value) { |
| 105 | auto it = std::find(container.begin(), container.end(), value); |
| 106 | DCHECK(it != container.end()); // Must exist. |
| 107 | container.erase(it); |
| 108 | } |
| 109 | |
| 110 | // Replace the first element with the specified old_value known to be in the container. |
| 111 | template <typename Container, typename T> |
| 112 | void ReplaceElement(Container& container, const T& old_value, const T& new_value) { |
| 113 | auto it = std::find(container.begin(), container.end(), old_value); |
| 114 | DCHECK(it != container.end()); // Must exist. |
| 115 | *it = new_value; |
| 116 | } |
| 117 | |
| 118 | // Search for an element with the specified value and return true if it was found, false otherwise. |
| 119 | template <typename Container, typename T> |
| 120 | bool ContainsElement(const Container& container, const T& value, size_t start_pos = 0u) { |
| 121 | DCHECK_LE(start_pos, container.size()); |
| 122 | auto start = container.begin(); |
| 123 | std::advance(start, start_pos); |
| 124 | auto it = std::find(start, container.end(), value); |
| 125 | return it != container.end(); |
| 126 | } |
| 127 | |
| 128 | template <typename T> |
| 129 | bool ContainsElement(const std::set<T>& container, const T& value) { |
| 130 | return container.count(value) != 0u; |
| 131 | } |
| 132 | |
| 133 | // 32-bit FNV-1a hash function suitable for std::unordered_map. |
| 134 | // It can be used with any container which works with range-based for loop. |
| 135 | // See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function |
| 136 | template <typename Vector> |
| 137 | struct FNVHash { |
| 138 | size_t operator()(const Vector& vector) const { |
| 139 | uint32_t hash = 2166136261u; |
| 140 | for (const auto& value : vector) { |
| 141 | hash = (hash ^ value) * 16777619u; |
| 142 | } |
| 143 | return hash; |
| 144 | } |
| 145 | }; |
| 146 | |
| 147 | // Returns a copy of the passed vector that doesn't memory-own its entries. |
| 148 | template <typename T> |
| 149 | static inline std::vector<T*> MakeNonOwningPointerVector(const std::vector<std::unique_ptr<T>>& src) { |
| 150 | std::vector<T*> result; |
| 151 | result.reserve(src.size()); |
| 152 | for (const std::unique_ptr<T>& t : src) { |
| 153 | result.push_back(t.get()); |
| 154 | } |
| 155 | return result; |
| 156 | } |
| 157 | |
| 158 | template <typename IterLeft, typename IterRight> |
| 159 | class ZipLeftIter : public std::iterator< |
| 160 | std::forward_iterator_tag, |
| 161 | std::pair<typename IterLeft::value_type, typename IterRight::value_type>> { |
| 162 | public: |
| 163 | ZipLeftIter(IterLeft left, IterRight right) : left_iter_(left), right_iter_(right) {} |
| 164 | ZipLeftIter<IterLeft, IterRight>& operator++() { |
| 165 | ++left_iter_; |
| 166 | ++right_iter_; |
| 167 | return *this; |
| 168 | } |
| 169 | ZipLeftIter<IterLeft, IterRight> operator++(int) { |
| 170 | ZipLeftIter<IterLeft, IterRight> ret(left_iter_, right_iter_); |
| 171 | ++(*this); |
| 172 | return ret; |
| 173 | } |
| 174 | bool operator==(const ZipLeftIter<IterLeft, IterRight>& other) const { |
| 175 | return left_iter_ == other.left_iter_; |
| 176 | } |
| 177 | bool operator!=(const ZipLeftIter<IterLeft, IterRight>& other) const { |
| 178 | return !(*this == other); |
| 179 | } |
| 180 | std::pair<typename IterLeft::value_type, typename IterRight::value_type> operator*() const { |
| 181 | return std::make_pair(*left_iter_, *right_iter_); |
| 182 | } |
| 183 | |
| 184 | private: |
| 185 | IterLeft left_iter_; |
| 186 | IterRight right_iter_; |
| 187 | }; |
| 188 | |
| 189 | class CountIter : public std::iterator<std::forward_iterator_tag, size_t, size_t, size_t, size_t> { |
| 190 | public: |
| 191 | CountIter() : count_(0) {} |
| 192 | explicit CountIter(size_t count) : count_(count) {} |
| 193 | CountIter& operator++() { |
| 194 | ++count_; |
| 195 | return *this; |
| 196 | } |
| 197 | CountIter operator++(int) { |
| 198 | size_t ret = count_; |
| 199 | ++count_; |
| 200 | return CountIter(ret); |
| 201 | } |
| 202 | bool operator==(const CountIter& other) const { |
| 203 | return count_ == other.count_; |
| 204 | } |
| 205 | bool operator!=(const CountIter& other) const { |
| 206 | return !(*this == other); |
| 207 | } |
| 208 | size_t operator*() const { |
| 209 | return count_; |
| 210 | } |
| 211 | |
| 212 | private: |
| 213 | size_t count_; |
| 214 | }; |
| 215 | |
| 216 | // Make an iteration range that returns a pair of the element and the index of the element. |
| 217 | template <typename Iter> |
| 218 | static inline IterationRange<ZipLeftIter<Iter, CountIter>> ZipCount(IterationRange<Iter> iter) { |
| 219 | return IterationRange(ZipLeftIter(iter.begin(), CountIter(0)), |
| 220 | ZipLeftIter(iter.end(), CountIter(-1))); |
| 221 | } |
| 222 | |
| 223 | // Make an iteration range that returns a pair of the outputs of two iterators. Stops when the first |
| 224 | // (left) one is exhausted. The left iterator must be at least as long as the right one. |
| 225 | template <typename IterLeft, typename IterRight> |
| 226 | static inline IterationRange<ZipLeftIter<IterLeft, IterRight>> ZipLeft( |
| 227 | IterationRange<IterLeft> iter_left, IterationRange<IterRight> iter_right) { |
| 228 | return IterationRange(ZipLeftIter(iter_left.begin(), iter_right.begin()), |
| 229 | ZipLeftIter(iter_left.end(), iter_right.end())); |
| 230 | } |
| 231 | |
| 232 | static inline IterationRange<CountIter> Range(size_t start, size_t end) { |
| 233 | return IterationRange(CountIter(start), CountIter(end)); |
| 234 | } |
| 235 | |
| 236 | static inline IterationRange<CountIter> Range(size_t end) { |
| 237 | return Range(0, end); |
| 238 | } |
| 239 | |
| 240 | template <typename RealIter, typename Filter> |
| 241 | struct FilterIterator |
| 242 | : public std::iterator<std::forward_iterator_tag, typename RealIter::value_type> { |
| 243 | public: |
| 244 | FilterIterator(RealIter rl, |
| 245 | Filter cond, |
| 246 | std::optional<RealIter> end = std::nullopt) |
| 247 | : real_iter_(rl), cond_(cond), end_(end) { |
| 248 | DCHECK(std::make_optional(rl) == end_ || cond_(*real_iter_)); |
| 249 | } |
| 250 | |
| 251 | FilterIterator<RealIter, Filter>& operator++() { |
| 252 | DCHECK(std::make_optional(real_iter_) != end_); |
| 253 | do { |
| 254 | if (std::make_optional(++real_iter_) == end_) { |
| 255 | break; |
| 256 | } |
| 257 | } while (!cond_(*real_iter_)); |
| 258 | return *this; |
| 259 | } |
| 260 | FilterIterator<RealIter, Filter> operator++(int) { |
| 261 | FilterIterator<RealIter, Filter> ret(real_iter_, cond_, end_); |
| 262 | ++(*this); |
| 263 | return ret; |
| 264 | } |
| 265 | bool operator==(const FilterIterator<RealIter, Filter>& other) const { |
| 266 | return real_iter_ == other.real_iter_; |
| 267 | } |
| 268 | bool operator!=(const FilterIterator<RealIter, Filter>& other) const { |
| 269 | return !(*this == other); |
| 270 | } |
| 271 | typename RealIter::value_type operator*() const { |
| 272 | return *real_iter_; |
| 273 | } |
| 274 | |
| 275 | private: |
| 276 | RealIter real_iter_; |
| 277 | Filter cond_; |
| 278 | std::optional<RealIter> end_; |
| 279 | }; |
| 280 | |
| 281 | template <typename Iter, typename Filter> |
| 282 | static inline IterationRange<FilterIterator<Iter, Filter>> Filter( |
| 283 | IterationRange<Iter> it, Filter cond) { |
| 284 | auto end = it.end(); |
| 285 | auto start = std::find_if(it.begin(), end, cond); |
| 286 | return MakeIterationRange(FilterIterator(start, cond, std::make_optional(end)), |
| 287 | FilterIterator(end, cond, std::make_optional(end))); |
| 288 | } |
| 289 | |
| 290 | template <typename Val> |
| 291 | struct NonNullFilter { |
| 292 | public: |
android-t1 | 3d2c5b2 | 2022-10-12 13:43:18 +0800 | [diff] [blame] | 293 | static_assert(std::is_pointer_v<Val>, "Must be pointer type!"); |
Martin Stjernholm | c15e7e4 | 2020-12-02 22:50:53 +0000 | [diff] [blame] | 294 | constexpr bool operator()(Val v) const { |
| 295 | return v != nullptr; |
| 296 | } |
| 297 | }; |
| 298 | |
| 299 | template <typename InnerIter> |
| 300 | using FilterNull = FilterIterator<InnerIter, NonNullFilter<typename InnerIter::value_type>>; |
| 301 | |
| 302 | template <typename InnerIter> |
| 303 | static inline IterationRange<FilterNull<InnerIter>> FilterOutNull(IterationRange<InnerIter> inner) { |
| 304 | return Filter(inner, NonNullFilter<typename InnerIter::value_type>()); |
| 305 | } |
| 306 | |
Paul Duffin | 7d02088 | 2021-02-08 10:16:27 +0000 | [diff] [blame] | 307 | template <typename Val> |
| 308 | struct SafePrinter { |
| 309 | const Val* val_; |
| 310 | }; |
| 311 | |
| 312 | template<typename Val> |
| 313 | std::ostream& operator<<(std::ostream& os, const SafePrinter<Val>& v) { |
| 314 | if (v.val_ == nullptr) { |
| 315 | return os << "NULL"; |
| 316 | } else { |
| 317 | return os << *v.val_; |
| 318 | } |
| 319 | } |
| 320 | |
| 321 | template<typename Val> |
| 322 | SafePrinter<Val> SafePrint(const Val* v) { |
| 323 | return SafePrinter<Val>{v}; |
| 324 | } |
| 325 | |
Martin Stjernholm | c82f8f0 | 2021-02-10 13:23:48 +0000 | [diff] [blame] | 326 | // Helper struct for iterating a split-string without allocation. |
| 327 | struct SplitStringIter : public std::iterator<std::forward_iterator_tag, std::string_view> { |
| 328 | public: |
| 329 | // Direct iterator constructor. The iteration state is only the current index. |
| 330 | // We use that with the split char and the full string to get the current and |
| 331 | // next segment. |
| 332 | SplitStringIter(size_t index, char split, std::string_view sv) |
| 333 | : cur_index_(index), split_on_(split), sv_(sv) {} |
| 334 | SplitStringIter(const SplitStringIter&) = default; |
| 335 | SplitStringIter(SplitStringIter&&) = default; |
| 336 | SplitStringIter& operator=(SplitStringIter&&) = default; |
| 337 | SplitStringIter& operator=(const SplitStringIter&) = default; |
| 338 | |
| 339 | SplitStringIter& operator++() { |
| 340 | size_t nxt = sv_.find(split_on_, cur_index_); |
| 341 | if (nxt == std::string_view::npos) { |
| 342 | cur_index_ = std::string_view::npos; |
| 343 | } else { |
| 344 | cur_index_ = nxt + 1; |
| 345 | } |
| 346 | return *this; |
| 347 | } |
| 348 | |
| 349 | SplitStringIter operator++(int) { |
| 350 | SplitStringIter ret(cur_index_, split_on_, sv_); |
| 351 | ++(*this); |
| 352 | return ret; |
| 353 | } |
| 354 | |
| 355 | bool operator==(const SplitStringIter& other) const { |
| 356 | return sv_ == other.sv_ && split_on_ == other.split_on_ && cur_index_== other.cur_index_; |
| 357 | } |
| 358 | |
| 359 | bool operator!=(const SplitStringIter& other) const { |
| 360 | return !(*this == other); |
| 361 | } |
| 362 | |
| 363 | typename std::string_view operator*() const { |
| 364 | return sv_.substr(cur_index_, sv_.substr(cur_index_).find(split_on_)); |
| 365 | } |
| 366 | |
| 367 | private: |
| 368 | size_t cur_index_; |
| 369 | char split_on_; |
| 370 | std::string_view sv_; |
| 371 | }; |
| 372 | |
| 373 | // Create an iteration range over the string 'sv' split at each 'target' occurrence. |
| 374 | // Eg: SplitString(":foo::bar") -> ["", "foo", "", "bar"] |
| 375 | inline IterationRange<SplitStringIter> SplitString(std::string_view sv, char target) { |
| 376 | return MakeIterationRange(SplitStringIter(0, target, sv), |
| 377 | SplitStringIter(std::string_view::npos, target, sv)); |
| 378 | } |
| 379 | |
Martin Stjernholm | c15e7e4 | 2020-12-02 22:50:53 +0000 | [diff] [blame] | 380 | } // namespace art |
| 381 | |
| 382 | #endif // ART_LIBARTBASE_BASE_STL_UTIL_H_ |