1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/ipc/chromium/src/base/stl_util-inl.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,450 @@
1.4 +// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
1.5 +// Use of this source code is governed by a BSD-style license that can be
1.6 +// found in the LICENSE file.
1.7 +
1.8 +// STL utility functions. Usually, these replace built-in, but slow(!),
1.9 +// STL functions with more efficient versions.
1.10 +
1.11 +#ifndef BASE_STL_UTIL_INL_H_
1.12 +#define BASE_STL_UTIL_INL_H_
1.13 +
1.14 +#include <string.h> // for memcpy
1.15 +#include <functional>
1.16 +#include <set>
1.17 +#include <string>
1.18 +#include <vector>
1.19 +#include <cassert>
1.20 +
1.21 +// Clear internal memory of an STL object.
1.22 +// STL clear()/reserve(0) does not always free internal memory allocated
1.23 +// This function uses swap/destructor to ensure the internal memory is freed.
1.24 +template<class T> void STLClearObject(T* obj) {
1.25 + T tmp;
1.26 + tmp.swap(*obj);
1.27 + obj->reserve(0); // this is because sometimes "T tmp" allocates objects with
1.28 + // memory (arena implementation?). use reserve()
1.29 + // to clear() even if it doesn't always work
1.30 +}
1.31 +
1.32 +// Reduce memory usage on behalf of object if it is using more than
1.33 +// "bytes" bytes of space. By default, we clear objects over 1MB.
1.34 +template <class T> inline void STLClearIfBig(T* obj, size_t limit = 1<<20) {
1.35 + if (obj->capacity() >= limit) {
1.36 + STLClearObject(obj);
1.37 + } else {
1.38 + obj->clear();
1.39 + }
1.40 +}
1.41 +
1.42 +// Reserve space for STL object.
1.43 +// STL's reserve() will always copy.
1.44 +// This function avoid the copy if we already have capacity
1.45 +template<class T> void STLReserveIfNeeded(T* obj, int new_size) {
1.46 + if (obj->capacity() < new_size) // increase capacity
1.47 + obj->reserve(new_size);
1.48 + else if (obj->size() > new_size) // reduce size
1.49 + obj->resize(new_size);
1.50 +}
1.51 +
1.52 +// STLDeleteContainerPointers()
1.53 +// For a range within a container of pointers, calls delete
1.54 +// (non-array version) on these pointers.
1.55 +// NOTE: for these three functions, we could just implement a DeleteObject
1.56 +// functor and then call for_each() on the range and functor, but this
1.57 +// requires us to pull in all of algorithm.h, which seems expensive.
1.58 +// For hash_[multi]set, it is important that this deletes behind the iterator
1.59 +// because the hash_set may call the hash function on the iterator when it is
1.60 +// advanced, which could result in the hash function trying to deference a
1.61 +// stale pointer.
1.62 +template <class ForwardIterator>
1.63 +void STLDeleteContainerPointers(ForwardIterator begin,
1.64 + ForwardIterator end) {
1.65 + while (begin != end) {
1.66 + ForwardIterator temp = begin;
1.67 + ++begin;
1.68 + delete *temp;
1.69 + }
1.70 +}
1.71 +
1.72 +// STLDeleteContainerPairPointers()
1.73 +// For a range within a container of pairs, calls delete
1.74 +// (non-array version) on BOTH items in the pairs.
1.75 +// NOTE: Like STLDeleteContainerPointers, it is important that this deletes
1.76 +// behind the iterator because if both the key and value are deleted, the
1.77 +// container may call the hash function on the iterator when it is advanced,
1.78 +// which could result in the hash function trying to dereference a stale
1.79 +// pointer.
1.80 +template <class ForwardIterator>
1.81 +void STLDeleteContainerPairPointers(ForwardIterator begin,
1.82 + ForwardIterator end) {
1.83 + while (begin != end) {
1.84 + ForwardIterator temp = begin;
1.85 + ++begin;
1.86 + delete temp->first;
1.87 + delete temp->second;
1.88 + }
1.89 +}
1.90 +
1.91 +// STLDeleteContainerPairFirstPointers()
1.92 +// For a range within a container of pairs, calls delete (non-array version)
1.93 +// on the FIRST item in the pairs.
1.94 +// NOTE: Like STLDeleteContainerPointers, deleting behind the iterator.
1.95 +template <class ForwardIterator>
1.96 +void STLDeleteContainerPairFirstPointers(ForwardIterator begin,
1.97 + ForwardIterator end) {
1.98 + while (begin != end) {
1.99 + ForwardIterator temp = begin;
1.100 + ++begin;
1.101 + delete temp->first;
1.102 + }
1.103 +}
1.104 +
1.105 +// STLDeleteContainerPairSecondPointers()
1.106 +// For a range within a container of pairs, calls delete
1.107 +// (non-array version) on the SECOND item in the pairs.
1.108 +template <class ForwardIterator>
1.109 +void STLDeleteContainerPairSecondPointers(ForwardIterator begin,
1.110 + ForwardIterator end) {
1.111 + while (begin != end) {
1.112 + delete begin->second;
1.113 + ++begin;
1.114 + }
1.115 +}
1.116 +
1.117 +template<typename T>
1.118 +inline void STLAssignToVector(std::vector<T>* vec,
1.119 + const T* ptr,
1.120 + size_t n) {
1.121 + vec->resize(n);
1.122 + memcpy(&vec->front(), ptr, n*sizeof(T));
1.123 +}
1.124 +
1.125 +/***** Hack to allow faster assignment to a vector *****/
1.126 +
1.127 +// This routine speeds up an assignment of 32 bytes to a vector from
1.128 +// about 250 cycles per assignment to about 140 cycles.
1.129 +//
1.130 +// Usage:
1.131 +// STLAssignToVectorChar(&vec, ptr, size);
1.132 +// STLAssignToString(&str, ptr, size);
1.133 +
1.134 +inline void STLAssignToVectorChar(std::vector<char>* vec,
1.135 + const char* ptr,
1.136 + size_t n) {
1.137 + STLAssignToVector(vec, ptr, n);
1.138 +}
1.139 +
1.140 +inline void STLAssignToString(std::string* str, const char* ptr, size_t n) {
1.141 + str->resize(n);
1.142 + memcpy(&*str->begin(), ptr, n);
1.143 +}
1.144 +
1.145 +// To treat a possibly-empty vector as an array, use these functions.
1.146 +// If you know the array will never be empty, you can use &*v.begin()
1.147 +// directly, but that is allowed to dump core if v is empty. This
1.148 +// function is the most efficient code that will work, taking into
1.149 +// account how our STL is actually implemented. THIS IS NON-PORTABLE
1.150 +// CODE, so call us instead of repeating the nonportable code
1.151 +// everywhere. If our STL implementation changes, we will need to
1.152 +// change this as well.
1.153 +
1.154 +template<typename T>
1.155 +inline T* vector_as_array(std::vector<T>* v) {
1.156 +# ifdef NDEBUG
1.157 + return &*v->begin();
1.158 +# else
1.159 + return v->empty() ? NULL : &*v->begin();
1.160 +# endif
1.161 +}
1.162 +
1.163 +template<typename T>
1.164 +inline const T* vector_as_array(const std::vector<T>* v) {
1.165 +# ifdef NDEBUG
1.166 + return &*v->begin();
1.167 +# else
1.168 + return v->empty() ? NULL : &*v->begin();
1.169 +# endif
1.170 +}
1.171 +
1.172 +// Return a mutable char* pointing to a string's internal buffer,
1.173 +// which may not be null-terminated. Writing through this pointer will
1.174 +// modify the string.
1.175 +//
1.176 +// string_as_array(&str)[i] is valid for 0 <= i < str.size() until the
1.177 +// next call to a string method that invalidates iterators.
1.178 +//
1.179 +// As of 2006-04, there is no standard-blessed way of getting a
1.180 +// mutable reference to a string's internal buffer. However, issue 530
1.181 +// (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#530)
1.182 +// proposes this as the method. According to Matt Austern, this should
1.183 +// already work on all current implementations.
1.184 +inline char* string_as_array(std::string* str) {
1.185 + // DO NOT USE const_cast<char*>(str->data())! See the unittest for why.
1.186 + return str->empty() ? NULL : &*str->begin();
1.187 +}
1.188 +
1.189 +// These are methods that test two hash maps/sets for equality. These exist
1.190 +// because the == operator in the STL can return false when the maps/sets
1.191 +// contain identical elements. This is because it compares the internal hash
1.192 +// tables which may be different if the order of insertions and deletions
1.193 +// differed.
1.194 +
1.195 +template <class HashSet>
1.196 +inline bool
1.197 +HashSetEquality(const HashSet& set_a,
1.198 + const HashSet& set_b) {
1.199 + if (set_a.size() != set_b.size()) return false;
1.200 + for (typename HashSet::const_iterator i = set_a.begin();
1.201 + i != set_a.end();
1.202 + ++i) {
1.203 + if (set_b.find(*i) == set_b.end())
1.204 + return false;
1.205 + }
1.206 + return true;
1.207 +}
1.208 +
1.209 +template <class HashMap>
1.210 +inline bool
1.211 +HashMapEquality(const HashMap& map_a,
1.212 + const HashMap& map_b) {
1.213 + if (map_a.size() != map_b.size()) return false;
1.214 + for (typename HashMap::const_iterator i = map_a.begin();
1.215 + i != map_a.end(); ++i) {
1.216 + typename HashMap::const_iterator j = map_b.find(i->first);
1.217 + if (j == map_b.end()) return false;
1.218 + if (i->second != j->second) return false;
1.219 + }
1.220 + return true;
1.221 +}
1.222 +
1.223 +// The following functions are useful for cleaning up STL containers
1.224 +// whose elements point to allocated memory.
1.225 +
1.226 +// STLDeleteElements() deletes all the elements in an STL container and clears
1.227 +// the container. This function is suitable for use with a vector, set,
1.228 +// hash_set, or any other STL container which defines sensible begin(), end(),
1.229 +// and clear() methods.
1.230 +//
1.231 +// If container is NULL, this function is a no-op.
1.232 +//
1.233 +// As an alternative to calling STLDeleteElements() directly, consider
1.234 +// STLElementDeleter (defined below), which ensures that your container's
1.235 +// elements are deleted when the STLElementDeleter goes out of scope.
1.236 +template <class T>
1.237 +void STLDeleteElements(T *container) {
1.238 + if (!container) return;
1.239 + STLDeleteContainerPointers(container->begin(), container->end());
1.240 + container->clear();
1.241 +}
1.242 +
1.243 +// Given an STL container consisting of (key, value) pairs, STLDeleteValues
1.244 +// deletes all the "value" components and clears the container. Does nothing
1.245 +// in the case it's given a NULL pointer.
1.246 +
1.247 +template <class T>
1.248 +void STLDeleteValues(T *v) {
1.249 + if (!v) return;
1.250 + for (typename T::iterator i = v->begin(); i != v->end(); ++i) {
1.251 + delete i->second;
1.252 + }
1.253 + v->clear();
1.254 +}
1.255 +
1.256 +
1.257 +// The following classes provide a convenient way to delete all elements or
1.258 +// values from STL containers when they goes out of scope. This greatly
1.259 +// simplifies code that creates temporary objects and has multiple return
1.260 +// statements. Example:
1.261 +//
1.262 +// vector<MyProto *> tmp_proto;
1.263 +// STLElementDeleter<vector<MyProto *> > d(&tmp_proto);
1.264 +// if (...) return false;
1.265 +// ...
1.266 +// return success;
1.267 +
1.268 +// Given a pointer to an STL container this class will delete all the element
1.269 +// pointers when it goes out of scope.
1.270 +
1.271 +template<class STLContainer> class STLElementDeleter {
1.272 + public:
1.273 + STLElementDeleter(STLContainer *ptr) : container_ptr_(ptr) {}
1.274 + ~STLElementDeleter() { STLDeleteElements(container_ptr_); }
1.275 + private:
1.276 + STLContainer *container_ptr_;
1.277 +};
1.278 +
1.279 +// Given a pointer to an STL container this class will delete all the value
1.280 +// pointers when it goes out of scope.
1.281 +
1.282 +template<class STLContainer> class STLValueDeleter {
1.283 + public:
1.284 + STLValueDeleter(STLContainer *ptr) : container_ptr_(ptr) {}
1.285 + ~STLValueDeleter() { STLDeleteValues(container_ptr_); }
1.286 + private:
1.287 + STLContainer *container_ptr_;
1.288 +};
1.289 +
1.290 +
1.291 +// Forward declare some callback classes in callback.h for STLBinaryFunction
1.292 +template <class R, class T1, class T2>
1.293 +class ResultCallback2;
1.294 +
1.295 +// STLBinaryFunction is a wrapper for the ResultCallback2 class in callback.h
1.296 +// It provides an operator () method instead of a Run method, so it may be
1.297 +// passed to STL functions in <algorithm>.
1.298 +//
1.299 +// The client should create callback with NewPermanentCallback, and should
1.300 +// delete callback after it is done using the STLBinaryFunction.
1.301 +
1.302 +template <class Result, class Arg1, class Arg2>
1.303 +class STLBinaryFunction : public std::binary_function<Arg1, Arg2, Result> {
1.304 + public:
1.305 + typedef ResultCallback2<Result, Arg1, Arg2> Callback;
1.306 +
1.307 + STLBinaryFunction(Callback* callback)
1.308 + : callback_(callback) {
1.309 + assert(callback_);
1.310 + }
1.311 +
1.312 + Result operator() (Arg1 arg1, Arg2 arg2) {
1.313 + return callback_->Run(arg1, arg2);
1.314 + }
1.315 +
1.316 + private:
1.317 + Callback* callback_;
1.318 +};
1.319 +
1.320 +// STLBinaryPredicate is a specialized version of STLBinaryFunction, where the
1.321 +// return type is bool and both arguments have type Arg. It can be used
1.322 +// wherever STL requires a StrictWeakOrdering, such as in sort() or
1.323 +// lower_bound().
1.324 +//
1.325 +// templated typedefs are not supported, so instead we use inheritance.
1.326 +
1.327 +template <class Arg>
1.328 +class STLBinaryPredicate : public STLBinaryFunction<bool, Arg, Arg> {
1.329 + public:
1.330 + typedef typename STLBinaryPredicate<Arg>::Callback Callback;
1.331 + STLBinaryPredicate(Callback* callback)
1.332 + : STLBinaryFunction<bool, Arg, Arg>(callback) {
1.333 + }
1.334 +};
1.335 +
1.336 +// Functors that compose arbitrary unary and binary functions with a
1.337 +// function that "projects" one of the members of a pair.
1.338 +// Specifically, if p1 and p2, respectively, are the functions that
1.339 +// map a pair to its first and second, respectively, members, the
1.340 +// table below summarizes the functions that can be constructed:
1.341 +//
1.342 +// * UnaryOperate1st<pair>(f) returns the function x -> f(p1(x))
1.343 +// * UnaryOperate2nd<pair>(f) returns the function x -> f(p2(x))
1.344 +// * BinaryOperate1st<pair>(f) returns the function (x,y) -> f(p1(x),p1(y))
1.345 +// * BinaryOperate2nd<pair>(f) returns the function (x,y) -> f(p2(x),p2(y))
1.346 +//
1.347 +// A typical usage for these functions would be when iterating over
1.348 +// the contents of an STL map. For other sample usage, see the unittest.
1.349 +
1.350 +template<typename Pair, typename UnaryOp>
1.351 +class UnaryOperateOnFirst
1.352 + : public std::unary_function<Pair, typename UnaryOp::result_type> {
1.353 + public:
1.354 + UnaryOperateOnFirst() {
1.355 + }
1.356 +
1.357 + UnaryOperateOnFirst(const UnaryOp& f) : f_(f) {
1.358 + }
1.359 +
1.360 + typename UnaryOp::result_type operator()(const Pair& p) const {
1.361 + return f_(p.first);
1.362 + }
1.363 +
1.364 + private:
1.365 + UnaryOp f_;
1.366 +};
1.367 +
1.368 +template<typename Pair, typename UnaryOp>
1.369 +UnaryOperateOnFirst<Pair, UnaryOp> UnaryOperate1st(const UnaryOp& f) {
1.370 + return UnaryOperateOnFirst<Pair, UnaryOp>(f);
1.371 +}
1.372 +
1.373 +template<typename Pair, typename UnaryOp>
1.374 +class UnaryOperateOnSecond
1.375 + : public std::unary_function<Pair, typename UnaryOp::result_type> {
1.376 + public:
1.377 + UnaryOperateOnSecond() {
1.378 + }
1.379 +
1.380 + UnaryOperateOnSecond(const UnaryOp& f) : f_(f) {
1.381 + }
1.382 +
1.383 + typename UnaryOp::result_type operator()(const Pair& p) const {
1.384 + return f_(p.second);
1.385 + }
1.386 +
1.387 + private:
1.388 + UnaryOp f_;
1.389 +};
1.390 +
1.391 +template<typename Pair, typename UnaryOp>
1.392 +UnaryOperateOnSecond<Pair, UnaryOp> UnaryOperate2nd(const UnaryOp& f) {
1.393 + return UnaryOperateOnSecond<Pair, UnaryOp>(f);
1.394 +}
1.395 +
1.396 +template<typename Pair, typename BinaryOp>
1.397 +class BinaryOperateOnFirst
1.398 + : public std::binary_function<Pair, Pair, typename BinaryOp::result_type> {
1.399 + public:
1.400 + BinaryOperateOnFirst() {
1.401 + }
1.402 +
1.403 + BinaryOperateOnFirst(const BinaryOp& f) : f_(f) {
1.404 + }
1.405 +
1.406 + typename BinaryOp::result_type operator()(const Pair& p1,
1.407 + const Pair& p2) const {
1.408 + return f_(p1.first, p2.first);
1.409 + }
1.410 +
1.411 + private:
1.412 + BinaryOp f_;
1.413 +};
1.414 +
1.415 +template<typename Pair, typename BinaryOp>
1.416 +BinaryOperateOnFirst<Pair, BinaryOp> BinaryOperate1st(const BinaryOp& f) {
1.417 + return BinaryOperateOnFirst<Pair, BinaryOp>(f);
1.418 +}
1.419 +
1.420 +template<typename Pair, typename BinaryOp>
1.421 +class BinaryOperateOnSecond
1.422 + : public std::binary_function<Pair, Pair, typename BinaryOp::result_type> {
1.423 + public:
1.424 + BinaryOperateOnSecond() {
1.425 + }
1.426 +
1.427 + BinaryOperateOnSecond(const BinaryOp& f) : f_(f) {
1.428 + }
1.429 +
1.430 + typename BinaryOp::result_type operator()(const Pair& p1,
1.431 + const Pair& p2) const {
1.432 + return f_(p1.second, p2.second);
1.433 + }
1.434 +
1.435 + private:
1.436 + BinaryOp f_;
1.437 +};
1.438 +
1.439 +template<typename Pair, typename BinaryOp>
1.440 +BinaryOperateOnSecond<Pair, BinaryOp> BinaryOperate2nd(const BinaryOp& f) {
1.441 + return BinaryOperateOnSecond<Pair, BinaryOp>(f);
1.442 +}
1.443 +
1.444 +// Translates a set into a vector.
1.445 +template<typename T>
1.446 +std::vector<T> SetToVector(const std::set<T>& values) {
1.447 + std::vector<T> result;
1.448 + result.reserve(values.size());
1.449 + result.insert(result.begin(), values.begin(), values.end());
1.450 + return result;
1.451 +}
1.452 +
1.453 +#endif // BASE_STL_UTIL_INL_H_
