Elliott Hughes | 2faa5f1 | 2012-01-30 14:42:07 -0800 | [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 | */ |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 16 | |
David Sehr | 67bf42e | 2018-02-26 16:43:04 -0800 | [diff] [blame] | 17 | #ifndef ART_LIBARTBASE_BASE_STL_UTIL_H_ |
| 18 | #define ART_LIBARTBASE_BASE_STL_UTIL_H_ |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 19 | |
Elliott Hughes | 08fc03a | 2012-06-26 17:34:00 -0700 | [diff] [blame] | 20 | #include <algorithm> |
Alex Light | a9bbc08 | 2019-11-14 14:51:41 -0800 | [diff] [blame^] | 21 | #include <iterator> |
Elliott Hughes | 1aa246d | 2012-12-13 09:29:36 -0800 | [diff] [blame] | 22 | #include <sstream> |
Elliott Hughes | 14134a1 | 2011-09-30 16:55:51 -0700 | [diff] [blame] | 23 | |
Andreas Gampe | 5794381 | 2017-12-06 21:39:13 -0800 | [diff] [blame] | 24 | #include <android-base/logging.h> |
Vladimir Marko | 637ee0b | 2015-09-04 12:47:41 +0100 | [diff] [blame] | 25 | |
Alex Light | a9bbc08 | 2019-11-14 14:51:41 -0800 | [diff] [blame^] | 26 | #include "base/iteration_range.h" |
| 27 | |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 28 | namespace art { |
| 29 | |
| 30 | // STLDeleteContainerPointers() |
| 31 | // For a range within a container of pointers, calls delete |
| 32 | // (non-array version) on these pointers. |
| 33 | // NOTE: for these three functions, we could just implement a DeleteObject |
| 34 | // functor and then call for_each() on the range and functor, but this |
| 35 | // requires us to pull in all of algorithm.h, which seems expensive. |
| 36 | // For hash_[multi]set, it is important that this deletes behind the iterator |
| 37 | // because the hash_set may call the hash function on the iterator when it is |
| 38 | // advanced, which could result in the hash function trying to deference a |
| 39 | // stale pointer. |
| 40 | template <class ForwardIterator> |
| 41 | void STLDeleteContainerPointers(ForwardIterator begin, |
| 42 | ForwardIterator end) { |
| 43 | while (begin != end) { |
| 44 | ForwardIterator temp = begin; |
| 45 | ++begin; |
| 46 | delete *temp; |
| 47 | } |
| 48 | } |
| 49 | |
| 50 | // STLDeleteElements() deletes all the elements in an STL container and clears |
| 51 | // the container. This function is suitable for use with a vector, set, |
| 52 | // hash_set, or any other STL container which defines sensible begin(), end(), |
| 53 | // and clear() methods. |
| 54 | // |
Mathieu Chartier | 2cebb24 | 2015-04-21 16:50:40 -0700 | [diff] [blame] | 55 | // If container is null, this function is a no-op. |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 56 | // |
| 57 | // As an alternative to calling STLDeleteElements() directly, consider |
Richard Uhler | 3c43f8d | 2015-01-15 10:27:22 -0800 | [diff] [blame] | 58 | // using a container of std::unique_ptr, which ensures that your container's |
| 59 | // elements are deleted when the container goes out of scope. |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 60 | template <class T> |
| 61 | void STLDeleteElements(T *container) { |
Mathieu Chartier | 2cebb24 | 2015-04-21 16:50:40 -0700 | [diff] [blame] | 62 | if (container != nullptr) { |
| 63 | STLDeleteContainerPointers(container->begin(), container->end()); |
| 64 | container->clear(); |
| 65 | } |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 66 | } |
| 67 | |
Elliott Hughes | c31664f | 2011-09-29 15:58:28 -0700 | [diff] [blame] | 68 | // Given an STL container consisting of (key, value) pairs, STLDeleteValues |
| 69 | // deletes all the "value" components and clears the container. Does nothing |
Mathieu Chartier | 2cebb24 | 2015-04-21 16:50:40 -0700 | [diff] [blame] | 70 | // in the case it's given a null pointer. |
Elliott Hughes | c31664f | 2011-09-29 15:58:28 -0700 | [diff] [blame] | 71 | template <class T> |
| 72 | void STLDeleteValues(T *v) { |
Mathieu Chartier | 2cebb24 | 2015-04-21 16:50:40 -0700 | [diff] [blame] | 73 | if (v != nullptr) { |
| 74 | for (typename T::iterator i = v->begin(); i != v->end(); ++i) { |
| 75 | delete i->second; |
| 76 | } |
| 77 | v->clear(); |
Elliott Hughes | c31664f | 2011-09-29 15:58:28 -0700 | [diff] [blame] | 78 | } |
Elliott Hughes | c31664f | 2011-09-29 15:58:28 -0700 | [diff] [blame] | 79 | } |
| 80 | |
Vladimir Marko | 637ee0b | 2015-09-04 12:47:41 +0100 | [diff] [blame] | 81 | // Deleter using free() for use with std::unique_ptr<>. See also UniqueCPtr<> below. |
| 82 | struct FreeDelete { |
| 83 | // NOTE: Deleting a const object is valid but free() takes a non-const pointer. |
| 84 | void operator()(const void* ptr) const { |
| 85 | free(const_cast<void*>(ptr)); |
| 86 | } |
| 87 | }; |
| 88 | |
| 89 | // Alias for std::unique_ptr<> that uses the C function free() to delete objects. |
| 90 | template <typename T> |
| 91 | using UniqueCPtr = std::unique_ptr<T, FreeDelete>; |
| 92 | |
Vladimir Marko | 637ee0b | 2015-09-04 12:47:41 +0100 | [diff] [blame] | 93 | // Find index of the first element with the specified value known to be in the container. |
| 94 | template <typename Container, typename T> |
| 95 | size_t IndexOfElement(const Container& container, const T& value) { |
| 96 | auto it = std::find(container.begin(), container.end(), value); |
| 97 | DCHECK(it != container.end()); // Must exist. |
| 98 | return std::distance(container.begin(), it); |
| 99 | } |
| 100 | |
| 101 | // Remove the first element with the specified value known to be in the container. |
| 102 | template <typename Container, typename T> |
| 103 | void RemoveElement(Container& container, const T& value) { |
| 104 | auto it = std::find(container.begin(), container.end(), value); |
| 105 | DCHECK(it != container.end()); // Must exist. |
| 106 | container.erase(it); |
| 107 | } |
| 108 | |
| 109 | // Replace the first element with the specified old_value known to be in the container. |
| 110 | template <typename Container, typename T> |
| 111 | void ReplaceElement(Container& container, const T& old_value, const T& new_value) { |
| 112 | auto it = std::find(container.begin(), container.end(), old_value); |
| 113 | DCHECK(it != container.end()); // Must exist. |
| 114 | *it = new_value; |
| 115 | } |
| 116 | |
| 117 | // Search for an element with the specified value and return true if it was found, false otherwise. |
| 118 | template <typename Container, typename T> |
| 119 | bool ContainsElement(const Container& container, const T& value, size_t start_pos = 0u) { |
| 120 | DCHECK_LE(start_pos, container.size()); |
| 121 | auto start = container.begin(); |
| 122 | std::advance(start, start_pos); |
| 123 | auto it = std::find(start, container.end(), value); |
| 124 | return it != container.end(); |
| 125 | } |
| 126 | |
David Srbecky | 24868a1 | 2016-01-29 18:59:56 +0000 | [diff] [blame] | 127 | // 32-bit FNV-1a hash function suitable for std::unordered_map. |
| 128 | // It can be used with any container which works with range-based for loop. |
| 129 | // See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function |
| 130 | template <typename Vector> |
| 131 | struct FNVHash { |
| 132 | size_t operator()(const Vector& vector) const { |
| 133 | uint32_t hash = 2166136261u; |
| 134 | for (const auto& value : vector) { |
| 135 | hash = (hash ^ value) * 16777619u; |
| 136 | } |
| 137 | return hash; |
| 138 | } |
| 139 | }; |
| 140 | |
Nicolas Geoffray | 4e868fa | 2017-04-21 17:16:44 +0100 | [diff] [blame] | 141 | // Returns a copy of the passed vector that doesn't memory-own its entries. |
| 142 | template <typename T> |
| 143 | static inline std::vector<T*> MakeNonOwningPointerVector(const std::vector<std::unique_ptr<T>>& src) { |
| 144 | std::vector<T*> result; |
| 145 | result.reserve(src.size()); |
| 146 | for (const std::unique_ptr<T>& t : src) { |
| 147 | result.push_back(t.get()); |
| 148 | } |
| 149 | return result; |
| 150 | } |
| 151 | |
Alex Light | a9bbc08 | 2019-11-14 14:51:41 -0800 | [diff] [blame^] | 152 | template <typename IterLeft, typename IterRight> |
| 153 | class ZipLeftIter : public std::iterator< |
| 154 | std::forward_iterator_tag, |
| 155 | std::pair<typename IterLeft::value_type, typename IterRight::value_type>> { |
| 156 | public: |
| 157 | ZipLeftIter(IterLeft left, IterRight right) : left_iter_(left), right_iter_(right) {} |
| 158 | ZipLeftIter<IterLeft, IterRight>& operator++() { |
| 159 | ++left_iter_; |
| 160 | ++right_iter_; |
| 161 | return *this; |
| 162 | } |
| 163 | ZipLeftIter<IterLeft, IterRight> operator++(int) { |
| 164 | ZipLeftIter<IterLeft, IterRight> ret(left_iter_, right_iter_); |
| 165 | ++(*this); |
| 166 | return ret; |
| 167 | } |
| 168 | bool operator==(const ZipLeftIter<IterLeft, IterRight>& other) const { |
| 169 | return left_iter_ == other.left_iter_; |
| 170 | } |
| 171 | bool operator!=(const ZipLeftIter<IterLeft, IterRight>& other) const { |
| 172 | return !(*this == other); |
| 173 | } |
| 174 | std::pair<typename IterLeft::value_type, typename IterRight::value_type> operator*() const { |
| 175 | return std::make_pair(*left_iter_, *right_iter_); |
| 176 | } |
| 177 | |
| 178 | private: |
| 179 | IterLeft left_iter_; |
| 180 | IterRight right_iter_; |
| 181 | }; |
| 182 | |
| 183 | class CountIter : public std::iterator<std::forward_iterator_tag, size_t, size_t, size_t, size_t> { |
| 184 | public: |
| 185 | CountIter() : count_(0) {} |
| 186 | explicit CountIter(size_t count) : count_(count) {} |
| 187 | CountIter& operator++() { |
| 188 | ++count_; |
| 189 | return *this; |
| 190 | } |
| 191 | CountIter operator++(int) { |
| 192 | size_t ret = count_; |
| 193 | ++count_; |
| 194 | return CountIter(ret); |
| 195 | } |
| 196 | bool operator==(const CountIter& other) const { |
| 197 | return count_ == other.count_; |
| 198 | } |
| 199 | bool operator!=(const CountIter& other) const { |
| 200 | return !(*this == other); |
| 201 | } |
| 202 | size_t operator*() const { |
| 203 | return count_; |
| 204 | } |
| 205 | |
| 206 | private: |
| 207 | size_t count_; |
| 208 | }; |
| 209 | |
| 210 | // Make an iteration range that returns a pair of the element and the index of the element. |
| 211 | template <typename Iter> |
| 212 | static inline IterationRange<ZipLeftIter<Iter, CountIter>> ZipCount(IterationRange<Iter> iter) { |
| 213 | return IterationRange(ZipLeftIter(iter.begin(), CountIter(0)), |
| 214 | ZipLeftIter(iter.end(), CountIter(-1))); |
| 215 | } |
| 216 | |
| 217 | // Make an iteration range that returns a pair of the outputs of two iterators. Stops when the first |
| 218 | // (left) one is exhausted. The left iterator must be at least as long as the right one. |
| 219 | template <typename IterLeft, typename IterRight> |
| 220 | static inline IterationRange<ZipLeftIter<IterLeft, IterRight>> ZipLeft( |
| 221 | IterationRange<IterLeft> iter_left, IterationRange<IterRight> iter_right) { |
| 222 | return IterationRange(ZipLeftIter(iter_left.begin(), iter_right.begin()), |
| 223 | ZipLeftIter(iter_left.end(), iter_right.end())); |
| 224 | } |
| 225 | |
Carl Shapiro | 58551df | 2011-07-24 03:09:51 -0700 | [diff] [blame] | 226 | } // namespace art |
| 227 | |
David Sehr | 67bf42e | 2018-02-26 16:43:04 -0800 | [diff] [blame] | 228 | #endif // ART_LIBARTBASE_BASE_STL_UTIL_H_ |