1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/sandbox/chromium/base/stl_util.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,223 @@
1.4 +// Copyright (c) 2011 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 +// Derived from google3/util/gtl/stl_util.h
1.9 +
1.10 +#ifndef BASE_STL_UTIL_H_
1.11 +#define BASE_STL_UTIL_H_
1.12 +
1.13 +#include <algorithm>
1.14 +#include <functional>
1.15 +#include <iterator>
1.16 +#include <string>
1.17 +#include <vector>
1.18 +
1.19 +#include "base/logging.h"
1.20 +
1.21 +// Clears 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>
1.25 +void STLClearObject(T* obj) {
1.26 + T tmp;
1.27 + tmp.swap(*obj);
1.28 + // Sometimes "T tmp" allocates objects with memory (arena implementation?).
1.29 + // Hence using additional reserve(0) even if it doesn't always work.
1.30 + obj->reserve(0);
1.31 +}
1.32 +
1.33 +// For a range within a container of pointers, calls delete (non-array version)
1.34 +// on these pointers.
1.35 +// NOTE: for these three functions, we could just implement a DeleteObject
1.36 +// functor and then call for_each() on the range and functor, but this
1.37 +// requires us to pull in all of algorithm.h, which seems expensive.
1.38 +// For hash_[multi]set, it is important that this deletes behind the iterator
1.39 +// because the hash_set may call the hash function on the iterator when it is
1.40 +// advanced, which could result in the hash function trying to deference a
1.41 +// stale pointer.
1.42 +template <class ForwardIterator>
1.43 +void STLDeleteContainerPointers(ForwardIterator begin, ForwardIterator end) {
1.44 + while (begin != end) {
1.45 + ForwardIterator temp = begin;
1.46 + ++begin;
1.47 + delete *temp;
1.48 + }
1.49 +}
1.50 +
1.51 +// For a range within a container of pairs, calls delete (non-array version) on
1.52 +// BOTH items in the pairs.
1.53 +// NOTE: Like STLDeleteContainerPointers, it is important that this deletes
1.54 +// behind the iterator because if both the key and value are deleted, the
1.55 +// container may call the hash function on the iterator when it is advanced,
1.56 +// which could result in the hash function trying to dereference a stale
1.57 +// pointer.
1.58 +template <class ForwardIterator>
1.59 +void STLDeleteContainerPairPointers(ForwardIterator begin,
1.60 + ForwardIterator end) {
1.61 + while (begin != end) {
1.62 + ForwardIterator temp = begin;
1.63 + ++begin;
1.64 + delete temp->first;
1.65 + delete temp->second;
1.66 + }
1.67 +}
1.68 +
1.69 +// For a range within a container of pairs, calls delete (non-array version) on
1.70 +// the FIRST item in the pairs.
1.71 +// NOTE: Like STLDeleteContainerPointers, deleting behind the iterator.
1.72 +template <class ForwardIterator>
1.73 +void STLDeleteContainerPairFirstPointers(ForwardIterator begin,
1.74 + ForwardIterator end) {
1.75 + while (begin != end) {
1.76 + ForwardIterator temp = begin;
1.77 + ++begin;
1.78 + delete temp->first;
1.79 + }
1.80 +}
1.81 +
1.82 +// For a range within a container of pairs, calls delete.
1.83 +// NOTE: Like STLDeleteContainerPointers, deleting behind the iterator.
1.84 +// Deleting the value does not always invalidate the iterator, but it may
1.85 +// do so if the key is a pointer into the value object.
1.86 +template <class ForwardIterator>
1.87 +void STLDeleteContainerPairSecondPointers(ForwardIterator begin,
1.88 + ForwardIterator end) {
1.89 + while (begin != end) {
1.90 + ForwardIterator temp = begin;
1.91 + ++begin;
1.92 + delete temp->second;
1.93 + }
1.94 +}
1.95 +
1.96 +// To treat a possibly-empty vector as an array, use these functions.
1.97 +// If you know the array will never be empty, you can use &*v.begin()
1.98 +// directly, but that is undefined behaviour if |v| is empty.
1.99 +template<typename T>
1.100 +inline T* vector_as_array(std::vector<T>* v) {
1.101 + return v->empty() ? NULL : &*v->begin();
1.102 +}
1.103 +
1.104 +template<typename T>
1.105 +inline const T* vector_as_array(const std::vector<T>* v) {
1.106 + return v->empty() ? NULL : &*v->begin();
1.107 +}
1.108 +
1.109 +// Return a mutable char* pointing to a string's internal buffer,
1.110 +// which may not be null-terminated. Writing through this pointer will
1.111 +// modify the string.
1.112 +//
1.113 +// string_as_array(&str)[i] is valid for 0 <= i < str.size() until the
1.114 +// next call to a string method that invalidates iterators.
1.115 +//
1.116 +// As of 2006-04, there is no standard-blessed way of getting a
1.117 +// mutable reference to a string's internal buffer. However, issue 530
1.118 +// (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#530)
1.119 +// proposes this as the method. According to Matt Austern, this should
1.120 +// already work on all current implementations.
1.121 +inline char* string_as_array(std::string* str) {
1.122 + // DO NOT USE const_cast<char*>(str->data())
1.123 + return str->empty() ? NULL : &*str->begin();
1.124 +}
1.125 +
1.126 +// The following functions are useful for cleaning up STL containers whose
1.127 +// elements point to allocated memory.
1.128 +
1.129 +// STLDeleteElements() deletes all the elements in an STL container and clears
1.130 +// the container. This function is suitable for use with a vector, set,
1.131 +// hash_set, or any other STL container which defines sensible begin(), end(),
1.132 +// and clear() methods.
1.133 +//
1.134 +// If container is NULL, this function is a no-op.
1.135 +//
1.136 +// As an alternative to calling STLDeleteElements() directly, consider
1.137 +// STLElementDeleter (defined below), which ensures that your container's
1.138 +// elements are deleted when the STLElementDeleter goes out of scope.
1.139 +template <class T>
1.140 +void STLDeleteElements(T* container) {
1.141 + if (!container)
1.142 + return;
1.143 + STLDeleteContainerPointers(container->begin(), container->end());
1.144 + container->clear();
1.145 +}
1.146 +
1.147 +// Given an STL container consisting of (key, value) pairs, STLDeleteValues
1.148 +// deletes all the "value" components and clears the container. Does nothing
1.149 +// in the case it's given a NULL pointer.
1.150 +template <class T>
1.151 +void STLDeleteValues(T* container) {
1.152 + if (!container)
1.153 + return;
1.154 + for (typename T::iterator i(container->begin()); i != container->end(); ++i)
1.155 + delete i->second;
1.156 + container->clear();
1.157 +}
1.158 +
1.159 +
1.160 +// The following classes provide a convenient way to delete all elements or
1.161 +// values from STL containers when they goes out of scope. This greatly
1.162 +// simplifies code that creates temporary objects and has multiple return
1.163 +// statements. Example:
1.164 +//
1.165 +// vector<MyProto *> tmp_proto;
1.166 +// STLElementDeleter<vector<MyProto *> > d(&tmp_proto);
1.167 +// if (...) return false;
1.168 +// ...
1.169 +// return success;
1.170 +
1.171 +// Given a pointer to an STL container this class will delete all the element
1.172 +// pointers when it goes out of scope.
1.173 +template<class T>
1.174 +class STLElementDeleter {
1.175 + public:
1.176 + STLElementDeleter<T>(T* container) : container_(container) {}
1.177 + ~STLElementDeleter<T>() { STLDeleteElements(container_); }
1.178 +
1.179 + private:
1.180 + T* container_;
1.181 +};
1.182 +
1.183 +// Given a pointer to an STL container this class will delete all the value
1.184 +// pointers when it goes out of scope.
1.185 +template<class T>
1.186 +class STLValueDeleter {
1.187 + public:
1.188 + STLValueDeleter<T>(T* container) : container_(container) {}
1.189 + ~STLValueDeleter<T>() { STLDeleteValues(container_); }
1.190 +
1.191 + private:
1.192 + T* container_;
1.193 +};
1.194 +
1.195 +// Test to see if a set, map, hash_set or hash_map contains a particular key.
1.196 +// Returns true if the key is in the collection.
1.197 +template <typename Collection, typename Key>
1.198 +bool ContainsKey(const Collection& collection, const Key& key) {
1.199 + return collection.find(key) != collection.end();
1.200 +}
1.201 +
1.202 +namespace base {
1.203 +
1.204 +// Returns true if the container is sorted.
1.205 +template <typename Container>
1.206 +bool STLIsSorted(const Container& cont) {
1.207 + return std::adjacent_find(cont.begin(), cont.end(),
1.208 + std::greater<typename Container::value_type>())
1.209 + == cont.end();
1.210 +}
1.211 +
1.212 +// Returns a new ResultType containing the difference of two sorted containers.
1.213 +template <typename ResultType, typename Arg1, typename Arg2>
1.214 +ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) {
1.215 + DCHECK(STLIsSorted(a1));
1.216 + DCHECK(STLIsSorted(a2));
1.217 + ResultType difference;
1.218 + std::set_difference(a1.begin(), a1.end(),
1.219 + a2.begin(), a2.end(),
1.220 + std::inserter(difference, difference.end()));
1.221 + return difference;
1.222 +}
1.223 +
1.224 +} // namespace base
1.225 +
1.226 +#endif // BASE_STL_UTIL_H_
