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