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 23namespace 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. 28template<class T> 29void 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. 46template <class ForwardIterator> 47void 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. 62template <class ForwardIterator> 63void 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. 76template <class ForwardIterator> 77void 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. 90template <class ForwardIterator> 91void 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. 103template<typename T> 104inline T* vector_as_array(std::vector<T>* v) { 105 return v->empty() ? NULL : &*v->begin(); 106} 107 108template<typename T> 109inline 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. 125inline 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. 143template <class T> 144void 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. 154template <class T> 155void 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. 177template<class T> 178class 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. 189template<class T> 190class 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. 201template <typename Collection, typename Key> 202bool ContainsKey(const Collection& collection, const Key& key) { 203 return collection.find(key) != collection.end(); 204} 205 206// Returns true if the container is sorted. 207template <typename Container> 208bool 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. 217template <typename ResultType, typename Arg1, typename Arg2> 218ResultType 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. 229template <typename ResultType, typename Arg1, typename Arg2> 230ResultType 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. 242template <typename ResultType, typename Arg1, typename Arg2> 243ResultType 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|. 255template <typename Arg1, typename Arg2> 256bool 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