1 /* 2 * Copyright (c) 2014 The WebRTC project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 // Borrowed from Chromium's src/base/stl_util.h. 12 13 #ifndef WEBRTC_SYSTEM_WRAPPERS_INTERFACE_STL_UTIL_H_ 14 #define WEBRTC_SYSTEM_WRAPPERS_INTERFACE_STL_UTIL_H_ 15 16 #include <assert.h> 17 #include <algorithm> 18 #include <functional> 19 #include <iterator> 20 #include <string> 21 #include <vector> 22 23 namespace webrtc { 24 25 // Clears internal memory of an STL object. 26 // STL clear()/reserve(0) does not always free internal memory allocated 27 // This function uses swap/destructor to ensure the internal memory is freed. 28 template<class T> 29 void STLClearObject(T* obj) { 30 T tmp; 31 tmp.swap(*obj); 32 // Sometimes "T tmp" allocates objects with memory (arena implementation?). 33 // Hence using additional reserve(0) even if it doesn't always work. 34 obj->reserve(0); 35 } 36 37 // For a range within a container of pointers, calls delete (non-array version) 38 // on these pointers. 39 // NOTE: for these three functions, we could just implement a DeleteObject 40 // functor and then call for_each() on the range and functor, but this 41 // requires us to pull in all of algorithm.h, which seems expensive. 42 // For hash_[multi]set, it is important that this deletes behind the iterator 43 // because the hash_set may call the hash function on the iterator when it is 44 // advanced, which could result in the hash function trying to deference a 45 // stale pointer. 46 template <class ForwardIterator> 47 void STLDeleteContainerPointers(ForwardIterator begin, ForwardIterator end) { 48 while (begin != end) { 49 ForwardIterator temp = begin; 50 ++begin; 51 delete *temp; 52 } 53 } 54 55 // For a range within a container of pairs, calls delete (non-array version) on 56 // BOTH items in the pairs. 57 // NOTE: Like STLDeleteContainerPointers, it is important that this deletes 58 // behind the iterator because if both the key and value are deleted, the 59 // container may call the hash function on the iterator when it is advanced, 60 // which could result in the hash function trying to dereference a stale 61 // pointer. 62 template <class ForwardIterator> 63 void STLDeleteContainerPairPointers(ForwardIterator begin, 64 ForwardIterator end) { 65 while (begin != end) { 66 ForwardIterator temp = begin; 67 ++begin; 68 delete temp->first; 69 delete temp->second; 70 } 71 } 72 73 // For a range within a container of pairs, calls delete (non-array version) on 74 // the FIRST item in the pairs. 75 // NOTE: Like STLDeleteContainerPointers, deleting behind the iterator. 76 template <class ForwardIterator> 77 void STLDeleteContainerPairFirstPointers(ForwardIterator begin, 78 ForwardIterator end) { 79 while (begin != end) { 80 ForwardIterator temp = begin; 81 ++begin; 82 delete temp->first; 83 } 84 } 85 86 // For a range within a container of pairs, calls delete. 87 // NOTE: Like STLDeleteContainerPointers, deleting behind the iterator. 88 // Deleting the value does not always invalidate the iterator, but it may 89 // do so if the key is a pointer into the value object. 90 template <class ForwardIterator> 91 void STLDeleteContainerPairSecondPointers(ForwardIterator begin, 92 ForwardIterator end) { 93 while (begin != end) { 94 ForwardIterator temp = begin; 95 ++begin; 96 delete temp->second; 97 } 98 } 99 100 // To treat a possibly-empty vector as an array, use these functions. 101 // If you know the array will never be empty, you can use &*v.begin() 102 // directly, but that is undefined behaviour if |v| is empty. 103 template<typename T> 104 inline T* vector_as_array(std::vector<T>* v) { 105 return v->empty() ? NULL : &*v->begin(); 106 } 107 108 template<typename T> 109 inline const T* vector_as_array(const std::vector<T>* v) { 110 return v->empty() ? NULL : &*v->begin(); 111 } 112 113 // Return a mutable char* pointing to a string's internal buffer, 114 // which may not be null-terminated. Writing through this pointer will 115 // modify the string. 116 // 117 // string_as_array(&str)[i] is valid for 0 <= i < str.size() until the 118 // next call to a string method that invalidates iterators. 119 // 120 // As of 2006-04, there is no standard-blessed way of getting a 121 // mutable reference to a string's internal buffer. However, issue 530 122 // (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#530) 123 // proposes this as the method. According to Matt Austern, this should 124 // already work on all current implementations. 125 inline char* string_as_array(std::string* str) { 126 // DO NOT USE const_cast<char*>(str->data()) 127 return str->empty() ? NULL : &*str->begin(); 128 } 129 130 // The following functions are useful for cleaning up STL containers whose 131 // elements point to allocated memory. 132 133 // STLDeleteElements() deletes all the elements in an STL container and clears 134 // the container. This function is suitable for use with a vector, set, 135 // hash_set, or any other STL container which defines sensible begin(), end(), 136 // and clear() methods. 137 // 138 // If container is NULL, this function is a no-op. 139 // 140 // As an alternative to calling STLDeleteElements() directly, consider 141 // STLElementDeleter (defined below), which ensures that your container's 142 // elements are deleted when the STLElementDeleter goes out of scope. 143 template <class T> 144 void STLDeleteElements(T* container) { 145 if (!container) 146 return; 147 STLDeleteContainerPointers(container->begin(), container->end()); 148 container->clear(); 149 } 150 151 // Given an STL container consisting of (key, value) pairs, STLDeleteValues 152 // deletes all the "value" components and clears the container. Does nothing 153 // in the case it's given a NULL pointer. 154 template <class T> 155 void STLDeleteValues(T* container) { 156 if (!container) 157 return; 158 for (typename T::iterator i(container->begin()); i != container->end(); ++i) 159 delete i->second; 160 container->clear(); 161 } 162 163 164 // The following classes provide a convenient way to delete all elements or 165 // values from STL containers when they goes out of scope. This greatly 166 // simplifies code that creates temporary objects and has multiple return 167 // statements. Example: 168 // 169 // vector<MyProto *> tmp_proto; 170 // STLElementDeleter<vector<MyProto *> > d(&tmp_proto); 171 // if (...) return false; 172 // ... 173 // return success; 174 175 // Given a pointer to an STL container this class will delete all the element 176 // pointers when it goes out of scope. 177 template<class T> 178 class STLElementDeleter { 179 public: 180 STLElementDeleter<T>(T* container) : container_(container) {} 181 ~STLElementDeleter<T>() { STLDeleteElements(container_); } 182 183 private: 184 T* container_; 185 }; 186 187 // Given a pointer to an STL container this class will delete all the value 188 // pointers when it goes out of scope. 189 template<class T> 190 class STLValueDeleter { 191 public: 192 STLValueDeleter<T>(T* container) : container_(container) {} 193 ~STLValueDeleter<T>() { STLDeleteValues(container_); } 194 195 private: 196 T* container_; 197 }; 198 199 // Test to see if a set, map, hash_set or hash_map contains a particular key. 200 // Returns true if the key is in the collection. 201 template <typename Collection, typename Key> 202 bool ContainsKey(const Collection& collection, const Key& key) { 203 return collection.find(key) != collection.end(); 204 } 205 206 // Returns true if the container is sorted. 207 template <typename Container> 208 bool STLIsSorted(const Container& cont) { 209 // Note: Use reverse iterator on container to ensure we only require 210 // value_type to implement operator<. 211 return std::adjacent_find(cont.rbegin(), cont.rend(), 212 std::less<typename Container::value_type>()) 213 == cont.rend(); 214 } 215 216 // Returns a new ResultType containing the difference of two sorted containers. 217 template <typename ResultType, typename Arg1, typename Arg2> 218 ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) { 219 assert(STLIsSorted(a1)); 220 assert(STLIsSorted(a2)); 221 ResultType difference; 222 std::set_difference(a1.begin(), a1.end(), 223 a2.begin(), a2.end(), 224 std::inserter(difference, difference.end())); 225 return difference; 226 } 227 228 // Returns a new ResultType containing the union of two sorted containers. 229 template <typename ResultType, typename Arg1, typename Arg2> 230 ResultType STLSetUnion(const Arg1& a1, const Arg2& a2) { 231 assert(STLIsSorted(a1)); 232 assert(STLIsSorted(a2)); 233 ResultType result; 234 std::set_union(a1.begin(), a1.end(), 235 a2.begin(), a2.end(), 236 std::inserter(result, result.end())); 237 return result; 238 } 239 240 // Returns a new ResultType containing the intersection of two sorted 241 // containers. 242 template <typename ResultType, typename Arg1, typename Arg2> 243 ResultType STLSetIntersection(const Arg1& a1, const Arg2& a2) { 244 assert(STLIsSorted(a1)); 245 assert(STLIsSorted(a2)); 246 ResultType result; 247 std::set_intersection(a1.begin(), a1.end(), 248 a2.begin(), a2.end(), 249 std::inserter(result, result.end())); 250 return result; 251 } 252 253 // Returns true if the sorted container |a1| contains all elements of the sorted 254 // container |a2|. 255 template <typename Arg1, typename Arg2> 256 bool STLIncludes(const Arg1& a1, const Arg2& a2) { 257 assert(STLIsSorted(a1)); 258 assert(STLIsSorted(a2)); 259 return std::includes(a1.begin(), a1.end(), 260 a2.begin(), a2.end()); 261 } 262 263 } // namespace webrtc 264 265 #endif // WEBRTC_SYSTEM_WRAPPERS_INTERFACE_STL_UTIL_H_ 266