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_RUNTIME_BASE_STL_UTIL_H_ 18 #define ART_RUNTIME_BASE_STL_UTIL_H_ 19 20 #include <algorithm> 21 #include <set> 22 #include <sstream> 23 24 #include "base/logging.h" 25 26 namespace art { 27 28 // Sort and remove duplicates of an STL vector or deque. 29 template<class T> 30 void STLSortAndRemoveDuplicates(T* v) { 31 std::sort(v->begin(), v->end()); 32 v->erase(std::unique(v->begin(), v->end()), v->end()); 33 } 34 35 // STLDeleteContainerPointers() 36 // For a range within a container of pointers, calls delete 37 // (non-array version) on these pointers. 38 // NOTE: for these three functions, we could just implement a DeleteObject 39 // functor and then call for_each() on the range and functor, but this 40 // requires us to pull in all of algorithm.h, which seems expensive. 41 // For hash_[multi]set, it is important that this deletes behind the iterator 42 // because the hash_set may call the hash function on the iterator when it is 43 // advanced, which could result in the hash function trying to deference a 44 // stale pointer. 45 template <class ForwardIterator> 46 void STLDeleteContainerPointers(ForwardIterator begin, 47 ForwardIterator end) { 48 while (begin != end) { 49 ForwardIterator temp = begin; 50 ++begin; 51 delete *temp; 52 } 53 } 54 55 // STLDeleteElements() deletes all the elements in an STL container and clears 56 // the container. This function is suitable for use with a vector, set, 57 // hash_set, or any other STL container which defines sensible begin(), end(), 58 // and clear() methods. 59 // 60 // If container is null, this function is a no-op. 61 // 62 // As an alternative to calling STLDeleteElements() directly, consider 63 // using a container of std::unique_ptr, which ensures that your container's 64 // elements are deleted when the container goes out of scope. 65 template <class T> 66 void STLDeleteElements(T *container) { 67 if (container != nullptr) { 68 STLDeleteContainerPointers(container->begin(), container->end()); 69 container->clear(); 70 } 71 } 72 73 // Given an STL container consisting of (key, value) pairs, STLDeleteValues 74 // deletes all the "value" components and clears the container. Does nothing 75 // in the case it's given a null pointer. 76 template <class T> 77 void STLDeleteValues(T *v) { 78 if (v != nullptr) { 79 for (typename T::iterator i = v->begin(); i != v->end(); ++i) { 80 delete i->second; 81 } 82 v->clear(); 83 } 84 } 85 86 template <class T> 87 std::string ToString(const T& v) { 88 std::ostringstream os; 89 os << "["; 90 for (size_t i = 0; i < v.size(); ++i) { 91 os << v[i]; 92 if (i < v.size() - 1) { 93 os << ", "; 94 } 95 } 96 os << "]"; 97 return os.str(); 98 } 99 100 // Deleter using free() for use with std::unique_ptr<>. See also UniqueCPtr<> below. 101 struct FreeDelete { 102 // NOTE: Deleting a const object is valid but free() takes a non-const pointer. 103 void operator()(const void* ptr) const { 104 free(const_cast<void*>(ptr)); 105 } 106 }; 107 108 // Alias for std::unique_ptr<> that uses the C function free() to delete objects. 109 template <typename T> 110 using UniqueCPtr = std::unique_ptr<T, FreeDelete>; 111 112 // C++14 from-the-future import (std::make_unique) 113 // Invoke the constructor of 'T' with the provided args, and wrap the result in a unique ptr. 114 template <typename T, typename ... Args> 115 std::unique_ptr<T> MakeUnique(Args&& ... args) { 116 return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); 117 } 118 119 // Find index of the first element with the specified value known to be in the container. 120 template <typename Container, typename T> 121 size_t IndexOfElement(const Container& container, const T& value) { 122 auto it = std::find(container.begin(), container.end(), value); 123 DCHECK(it != container.end()); // Must exist. 124 return std::distance(container.begin(), it); 125 } 126 127 // Remove the first element with the specified value known to be in the container. 128 template <typename Container, typename T> 129 void RemoveElement(Container& container, const T& value) { 130 auto it = std::find(container.begin(), container.end(), value); 131 DCHECK(it != container.end()); // Must exist. 132 container.erase(it); 133 } 134 135 // Replace the first element with the specified old_value known to be in the container. 136 template <typename Container, typename T> 137 void ReplaceElement(Container& container, const T& old_value, const T& new_value) { 138 auto it = std::find(container.begin(), container.end(), old_value); 139 DCHECK(it != container.end()); // Must exist. 140 *it = new_value; 141 } 142 143 // Search for an element with the specified value and return true if it was found, false otherwise. 144 template <typename Container, typename T> 145 bool ContainsElement(const Container& container, const T& value, size_t start_pos = 0u) { 146 DCHECK_LE(start_pos, container.size()); 147 auto start = container.begin(); 148 std::advance(start, start_pos); 149 auto it = std::find(start, container.end(), value); 150 return it != container.end(); 151 } 152 153 // const char* compare function suitable for std::map or std::set. 154 struct CStringLess { 155 bool operator()(const char* lhs, const char* rhs) const { 156 return strcmp(lhs, rhs) < 0; 157 } 158 }; 159 160 // 32-bit FNV-1a hash function suitable for std::unordered_map. 161 // It can be used with any container which works with range-based for loop. 162 // See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function 163 template <typename Vector> 164 struct FNVHash { 165 size_t operator()(const Vector& vector) const { 166 uint32_t hash = 2166136261u; 167 for (const auto& value : vector) { 168 hash = (hash ^ value) * 16777619u; 169 } 170 return hash; 171 } 172 }; 173 174 // Use to suppress type deduction for a function argument. 175 // See std::identity<> for more background: 176 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1856.html#20.2.2 - move/forward helpers 177 // 178 // e.g. "template <typename X> void bar(identity<X>::type foo); 179 // bar(5); // compilation error 180 // bar<int>(5); // ok 181 // or "template <typename T> void foo(T* x, typename Identity<T*>::type y); 182 // Base b; 183 // Derived d; 184 // foo(&b, &d); // Use implicit Derived* -> Base* conversion. 185 // If T was deduced from both &b and &d, there would be a mismatch, i.e. deduction failure. 186 template <typename T> 187 struct Identity { 188 using type = T; 189 }; 190 191 // Merge `other` entries into `to_update`. 192 template <typename T> 193 static inline void MergeSets(std::set<T>& to_update, const std::set<T>& other) { 194 to_update.insert(other.begin(), other.end()); 195 } 196 197 // Returns a copy of the passed vector that doesn't memory-own its entries. 198 template <typename T> 199 static inline std::vector<T*> MakeNonOwningPointerVector(const std::vector<std::unique_ptr<T>>& src) { 200 std::vector<T*> result; 201 result.reserve(src.size()); 202 for (const std::unique_ptr<T>& t : src) { 203 result.push_back(t.get()); 204 } 205 return result; 206 } 207 208 } // namespace art 209 210 #endif // ART_RUNTIME_BASE_STL_UTIL_H_ 211
