← Back to branch summary

~alinuxninja/nginx-edge/trunk

« back to all changes in this revision

Viewing changes to debian/modules/ngx_pagespeed/psol/include/third_party/chromium/src/base/stl_util.h

  • Committer: Vivian
  • Date: 2015-12-04 18:20:11 UTC
  • Revision ID: git-v1:a36f2bc32e884f7473b3a47040e5411306144d7d
* Do not extract psol.tar.gz

Show diffs side-by-side

added added

removed removed

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