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 <set> 22 #include <sstream> 23 24 #include <android-base/logging.h> 25 26 namespace art { 27 28 // STLDeleteContainerPointers() 29 // For a range within a container of pointers, calls delete 30 // (non-array version) on these pointers. 31 // NOTE: for these three functions, we could just implement a DeleteObject 32 // functor and then call for_each() on the range and functor, but this 33 // requires us to pull in all of algorithm.h, which seems expensive. 34 // For hash_[multi]set, it is important that this deletes behind the iterator 35 // because the hash_set may call the hash function on the iterator when it is 36 // advanced, which could result in the hash function trying to deference a 37 // stale pointer. 38 template <class ForwardIterator> 39 void STLDeleteContainerPointers(ForwardIterator begin, 40 ForwardIterator end) { 41 while (begin != end) { 42 ForwardIterator temp = begin; 43 ++begin; 44 delete *temp; 45 } 46 } 47 48 // STLDeleteElements() deletes all the elements in an STL container and clears 49 // the container. This function is suitable for use with a vector, set, 50 // hash_set, or any other STL container which defines sensible begin(), end(), 51 // and clear() methods. 52 // 53 // If container is null, this function is a no-op. 54 // 55 // As an alternative to calling STLDeleteElements() directly, consider 56 // using a container of std::unique_ptr, which ensures that your container's 57 // elements are deleted when the container goes out of scope. 58 template <class T> 59 void STLDeleteElements(T *container) { 60 if (container != nullptr) { 61 STLDeleteContainerPointers(container->begin(), container->end()); 62 container->clear(); 63 } 64 } 65 66 // Given an STL container consisting of (key, value) pairs, STLDeleteValues 67 // deletes all the "value" components and clears the container. Does nothing 68 // in the case it's given a null pointer. 69 template <class T> 70 void STLDeleteValues(T *v) { 71 if (v != nullptr) { 72 for (typename T::iterator i = v->begin(); i != v->end(); ++i) { 73 delete i->second; 74 } 75 v->clear(); 76 } 77 } 78 79 // Deleter using free() for use with std::unique_ptr<>. See also UniqueCPtr<> below. 80 struct FreeDelete { 81 // NOTE: Deleting a const object is valid but free() takes a non-const pointer. 82 void operator()(const void* ptr) const { 83 free(const_cast<void*>(ptr)); 84 } 85 }; 86 87 // Alias for std::unique_ptr<> that uses the C function free() to delete objects. 88 template <typename T> 89 using UniqueCPtr = std::unique_ptr<T, FreeDelete>; 90 91 // Find index of the first element with the specified value known to be in the container. 92 template <typename Container, typename T> 93 size_t IndexOfElement(const Container& container, const T& value) { 94 auto it = std::find(container.begin(), container.end(), value); 95 DCHECK(it != container.end()); // Must exist. 96 return std::distance(container.begin(), it); 97 } 98 99 // Remove the first element with the specified value known to be in the container. 100 template <typename Container, typename T> 101 void RemoveElement(Container& container, const T& value) { 102 auto it = std::find(container.begin(), container.end(), value); 103 DCHECK(it != container.end()); // Must exist. 104 container.erase(it); 105 } 106 107 // Replace the first element with the specified old_value known to be in the container. 108 template <typename Container, typename T> 109 void ReplaceElement(Container& container, const T& old_value, const T& new_value) { 110 auto it = std::find(container.begin(), container.end(), old_value); 111 DCHECK(it != container.end()); // Must exist. 112 *it = new_value; 113 } 114 115 // Search for an element with the specified value and return true if it was found, false otherwise. 116 template <typename Container, typename T> 117 bool ContainsElement(const Container& container, const T& value, size_t start_pos = 0u) { 118 DCHECK_LE(start_pos, container.size()); 119 auto start = container.begin(); 120 std::advance(start, start_pos); 121 auto it = std::find(start, container.end(), value); 122 return it != container.end(); 123 } 124 125 // 32-bit FNV-1a hash function suitable for std::unordered_map. 126 // It can be used with any container which works with range-based for loop. 127 // See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function 128 template <typename Vector> 129 struct FNVHash { 130 size_t operator()(const Vector& vector) const { 131 uint32_t hash = 2166136261u; 132 for (const auto& value : vector) { 133 hash = (hash ^ value) * 16777619u; 134 } 135 return hash; 136 } 137 }; 138 139 // Merge `other` entries into `to_update`. 140 template <typename T> 141 static inline void MergeSets(std::set<T>& to_update, const std::set<T>& other) { 142 to_update.insert(other.begin(), other.end()); 143 } 144 145 // Returns a copy of the passed vector that doesn't memory-own its entries. 146 template <typename T> 147 static inline std::vector<T*> MakeNonOwningPointerVector(const std::vector<std::unique_ptr<T>>& src) { 148 std::vector<T*> result; 149 result.reserve(src.size()); 150 for (const std::unique_ptr<T>& t : src) { 151 result.push_back(t.get()); 152 } 153 return result; 154 } 155 156 } // namespace art 157 158 #endif // ART_LIBARTBASE_BASE_STL_UTIL_H_ 159
