OLD | NEW |
| (Empty) |
1 // Copyright (c) 2010 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 // STL utility functions. Usually, these replace built-in, but slow(!), | |
6 // STL functions with more efficient versions. | |
7 | |
8 #ifndef BASE_STL_UTIL_INL_H_ | |
9 #define BASE_STL_UTIL_INL_H_ | |
10 #pragma once | |
11 | |
12 #include <string.h> // for memcpy | |
13 #include <functional> | |
14 #include <set> | |
15 #include <string> | |
16 #include <vector> | |
17 #include <cassert> | |
18 | |
19 // Clear internal memory of an STL object. | |
20 // STL clear()/reserve(0) does not always free internal memory allocated | |
21 // This function uses swap/destructor to ensure the internal memory is freed. | |
22 template<class T> void STLClearObject(T* obj) { | |
23 T tmp; | |
24 tmp.swap(*obj); | |
25 obj->reserve(0); // this is because sometimes "T tmp" allocates objects with | |
26 // memory (arena implementation?). use reserve() | |
27 // to clear() even if it doesn't always work | |
28 } | |
29 | |
30 // Reduce memory usage on behalf of object if it is using more than | |
31 // "bytes" bytes of space. By default, we clear objects over 1MB. | |
32 template <class T> inline void STLClearIfBig(T* obj, size_t limit = 1<<20) { | |
33 if (obj->capacity() >= limit) { | |
34 STLClearObject(obj); | |
35 } else { | |
36 obj->clear(); | |
37 } | |
38 } | |
39 | |
40 // Reserve space for STL object. | |
41 // STL's reserve() will always copy. | |
42 // This function avoid the copy if we already have capacity | |
43 template<class T> void STLReserveIfNeeded(T* obj, int new_size) { | |
44 if (obj->capacity() < new_size) // increase capacity | |
45 obj->reserve(new_size); | |
46 else if (obj->size() > new_size) // reduce size | |
47 obj->resize(new_size); | |
48 } | |
49 | |
50 // STLDeleteContainerPointers() | |
51 // For a range within a container of pointers, calls delete | |
52 // (non-array version) on these pointers. | |
53 // NOTE: for these three functions, we could just implement a DeleteObject | |
54 // functor and then call for_each() on the range and functor, but this | |
55 // requires us to pull in all of algorithm.h, which seems expensive. | |
56 // For hash_[multi]set, it is important that this deletes behind the iterator | |
57 // because the hash_set may call the hash function on the iterator when it is | |
58 // advanced, which could result in the hash function trying to deference a | |
59 // stale pointer. | |
60 template <class ForwardIterator> | |
61 void STLDeleteContainerPointers(ForwardIterator begin, ForwardIterator end) { | |
62 while (begin != end) { | |
63 ForwardIterator temp = begin; | |
64 ++begin; | |
65 delete *temp; | |
66 } | |
67 } | |
68 | |
69 // STLDeleteContainerPairPointers() | |
70 // For a range within a container of pairs, calls delete | |
71 // (non-array version) on BOTH items in the pairs. | |
72 // NOTE: Like STLDeleteContainerPointers, it is important that this deletes | |
73 // behind the iterator because if both the key and value are deleted, the | |
74 // container may call the hash function on the iterator when it is advanced, | |
75 // which could result in the hash function trying to dereference a stale | |
76 // pointer. | |
77 template <class ForwardIterator> | |
78 void STLDeleteContainerPairPointers(ForwardIterator begin, | |
79 ForwardIterator end) { | |
80 while (begin != end) { | |
81 ForwardIterator temp = begin; | |
82 ++begin; | |
83 delete temp->first; | |
84 delete temp->second; | |
85 } | |
86 } | |
87 | |
88 // STLDeleteContainerPairFirstPointers() | |
89 // For a range within a container of pairs, calls delete (non-array version) | |
90 // on the FIRST item in the pairs. | |
91 // NOTE: Like STLDeleteContainerPointers, deleting behind the iterator. | |
92 template <class ForwardIterator> | |
93 void STLDeleteContainerPairFirstPointers(ForwardIterator begin, | |
94 ForwardIterator end) { | |
95 while (begin != end) { | |
96 ForwardIterator temp = begin; | |
97 ++begin; | |
98 delete temp->first; | |
99 } | |
100 } | |
101 | |
102 // STLDeleteContainerPairSecondPointers() | |
103 // For a range within a container of pairs, calls delete | |
104 // (non-array version) on the SECOND item in the pairs. | |
105 template <class ForwardIterator> | |
106 void STLDeleteContainerPairSecondPointers(ForwardIterator begin, | |
107 ForwardIterator end) { | |
108 while (begin != end) { | |
109 delete begin->second; | |
110 ++begin; | |
111 } | |
112 } | |
113 | |
114 template<typename T> | |
115 inline void STLAssignToVector(std::vector<T>* vec, | |
116 const T* ptr, | |
117 size_t n) { | |
118 vec->resize(n); | |
119 memcpy(&vec->front(), ptr, n*sizeof(T)); | |
120 } | |
121 | |
122 /***** Hack to allow faster assignment to a vector *****/ | |
123 | |
124 // This routine speeds up an assignment of 32 bytes to a vector from | |
125 // about 250 cycles per assignment to about 140 cycles. | |
126 // | |
127 // Usage: | |
128 // STLAssignToVectorChar(&vec, ptr, size); | |
129 // STLAssignToString(&str, ptr, size); | |
130 | |
131 inline void STLAssignToVectorChar(std::vector<char>* vec, | |
132 const char* ptr, | |
133 size_t n) { | |
134 STLAssignToVector(vec, ptr, n); | |
135 } | |
136 | |
137 inline void STLAssignToString(std::string* str, const char* ptr, size_t n) { | |
138 str->resize(n); | |
139 memcpy(&*str->begin(), ptr, n); | |
140 } | |
141 | |
142 // To treat a possibly-empty vector as an array, use these functions. | |
143 // If you know the array will never be empty, you can use &*v.begin() | |
144 // directly, but that is allowed to dump core if v is empty. This | |
145 // function is the most efficient code that will work, taking into | |
146 // account how our STL is actually implemented. THIS IS NON-PORTABLE | |
147 // CODE, so call us instead of repeating the nonportable code | |
148 // everywhere. If our STL implementation changes, we will need to | |
149 // change this as well. | |
150 | |
151 template<typename T> | |
152 inline T* vector_as_array(std::vector<T>* v) { | |
153 # ifdef NDEBUG | |
154 return &*v->begin(); | |
155 # else | |
156 return v->empty() ? NULL : &*v->begin(); | |
157 # endif | |
158 } | |
159 | |
160 template<typename T> | |
161 inline const T* vector_as_array(const std::vector<T>* v) { | |
162 # ifdef NDEBUG | |
163 return &*v->begin(); | |
164 # else | |
165 return v->empty() ? NULL : &*v->begin(); | |
166 # endif | |
167 } | |
168 | |
169 // Return a mutable char* pointing to a string's internal buffer, | |
170 // which may not be null-terminated. Writing through this pointer will | |
171 // modify the string. | |
172 // | |
173 // string_as_array(&str)[i] is valid for 0 <= i < str.size() until the | |
174 // next call to a string method that invalidates iterators. | |
175 // | |
176 // As of 2006-04, there is no standard-blessed way of getting a | |
177 // mutable reference to a string's internal buffer. However, issue 530 | |
178 // (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#530) | |
179 // proposes this as the method. According to Matt Austern, this should | |
180 // already work on all current implementations. | |
181 inline char* string_as_array(std::string* str) { | |
182 // DO NOT USE const_cast<char*>(str->data())! See the unittest for why. | |
183 return str->empty() ? NULL : &*str->begin(); | |
184 } | |
185 | |
186 // These are methods that test two hash maps/sets for equality. These exist | |
187 // because the == operator in the STL can return false when the maps/sets | |
188 // contain identical elements. This is because it compares the internal hash | |
189 // tables which may be different if the order of insertions and deletions | |
190 // differed. | |
191 | |
192 template <class HashSet> | |
193 inline bool HashSetEquality(const HashSet& set_a, const HashSet& set_b) { | |
194 if (set_a.size() != set_b.size()) return false; | |
195 for (typename HashSet::const_iterator i = set_a.begin(); | |
196 i != set_a.end(); ++i) { | |
197 if (set_b.find(*i) == set_b.end()) | |
198 return false; | |
199 } | |
200 return true; | |
201 } | |
202 | |
203 template <class HashMap> | |
204 inline bool HashMapEquality(const HashMap& map_a, const HashMap& map_b) { | |
205 if (map_a.size() != map_b.size()) return false; | |
206 for (typename HashMap::const_iterator i = map_a.begin(); | |
207 i != map_a.end(); ++i) { | |
208 typename HashMap::const_iterator j = map_b.find(i->first); | |
209 if (j == map_b.end()) return false; | |
210 if (i->second != j->second) return false; | |
211 } | |
212 return true; | |
213 } | |
214 | |
215 // The following functions are useful for cleaning up STL containers | |
216 // whose elements point to allocated memory. | |
217 | |
218 // STLDeleteElements() deletes all the elements in an STL container and clears | |
219 // the container. This function is suitable for use with a vector, set, | |
220 // hash_set, or any other STL container which defines sensible begin(), end(), | |
221 // and clear() methods. | |
222 // | |
223 // If container is NULL, this function is a no-op. | |
224 // | |
225 // As an alternative to calling STLDeleteElements() directly, consider | |
226 // STLElementDeleter (defined below), which ensures that your container's | |
227 // elements are deleted when the STLElementDeleter goes out of scope. | |
228 template <class T> | |
229 void STLDeleteElements(T *container) { | |
230 if (!container) return; | |
231 STLDeleteContainerPointers(container->begin(), container->end()); | |
232 container->clear(); | |
233 } | |
234 | |
235 // Given an STL container consisting of (key, value) pairs, STLDeleteValues | |
236 // deletes all the "value" components and clears the container. Does nothing | |
237 // in the case it's given a NULL pointer. | |
238 | |
239 template <class T> | |
240 void STLDeleteValues(T *v) { | |
241 if (!v) return; | |
242 for (typename T::iterator i = v->begin(); i != v->end(); ++i) { | |
243 delete i->second; | |
244 } | |
245 v->clear(); | |
246 } | |
247 | |
248 | |
249 // The following classes provide a convenient way to delete all elements or | |
250 // values from STL containers when they goes out of scope. This greatly | |
251 // simplifies code that creates temporary objects and has multiple return | |
252 // statements. Example: | |
253 // | |
254 // vector<MyProto *> tmp_proto; | |
255 // STLElementDeleter<vector<MyProto *> > d(&tmp_proto); | |
256 // if (...) return false; | |
257 // ... | |
258 // return success; | |
259 | |
260 // Given a pointer to an STL container this class will delete all the element | |
261 // pointers when it goes out of scope. | |
262 | |
263 template<class STLContainer> class STLElementDeleter { | |
264 public: | |
265 STLElementDeleter<STLContainer>(STLContainer *ptr) : container_ptr_(ptr) {} | |
266 ~STLElementDeleter<STLContainer>() { STLDeleteElements(container_ptr_); } | |
267 private: | |
268 STLContainer *container_ptr_; | |
269 }; | |
270 | |
271 // Given a pointer to an STL container this class will delete all the value | |
272 // pointers when it goes out of scope. | |
273 | |
274 template<class STLContainer> class STLValueDeleter { | |
275 public: | |
276 STLValueDeleter<STLContainer>(STLContainer *ptr) : container_ptr_(ptr) {} | |
277 ~STLValueDeleter<STLContainer>() { STLDeleteValues(container_ptr_); } | |
278 private: | |
279 STLContainer *container_ptr_; | |
280 }; | |
281 | |
282 | |
283 // Forward declare some callback classes in callback.h for STLBinaryFunction | |
284 template <class R, class T1, class T2> | |
285 class ResultCallback2; | |
286 | |
287 // STLBinaryFunction is a wrapper for the ResultCallback2 class in callback.h | |
288 // It provides an operator () method instead of a Run method, so it may be | |
289 // passed to STL functions in <algorithm>. | |
290 // | |
291 // The client should create callback with NewPermanentCallback, and should | |
292 // delete callback after it is done using the STLBinaryFunction. | |
293 | |
294 template <class Result, class Arg1, class Arg2> | |
295 class STLBinaryFunction : public std::binary_function<Arg1, Arg2, Result> { | |
296 public: | |
297 typedef ResultCallback2<Result, Arg1, Arg2> Callback; | |
298 | |
299 STLBinaryFunction(Callback* callback) | |
300 : callback_(callback) { | |
301 assert(callback_); | |
302 } | |
303 | |
304 Result operator() (Arg1 arg1, Arg2 arg2) { | |
305 return callback_->Run(arg1, arg2); | |
306 } | |
307 | |
308 private: | |
309 Callback* callback_; | |
310 }; | |
311 | |
312 // STLBinaryPredicate is a specialized version of STLBinaryFunction, where the | |
313 // return type is bool and both arguments have type Arg. It can be used | |
314 // wherever STL requires a StrictWeakOrdering, such as in sort() or | |
315 // lower_bound(). | |
316 // | |
317 // templated typedefs are not supported, so instead we use inheritance. | |
318 | |
319 template <class Arg> | |
320 class STLBinaryPredicate : public STLBinaryFunction<bool, Arg, Arg> { | |
321 public: | |
322 typedef typename STLBinaryPredicate<Arg>::Callback Callback; | |
323 STLBinaryPredicate(Callback* callback) | |
324 : STLBinaryFunction<bool, Arg, Arg>(callback) { | |
325 } | |
326 }; | |
327 | |
328 // Functors that compose arbitrary unary and binary functions with a | |
329 // function that "projects" one of the members of a pair. | |
330 // Specifically, if p1 and p2, respectively, are the functions that | |
331 // map a pair to its first and second, respectively, members, the | |
332 // table below summarizes the functions that can be constructed: | |
333 // | |
334 // * UnaryOperate1st<pair>(f) returns the function x -> f(p1(x)) | |
335 // * UnaryOperate2nd<pair>(f) returns the function x -> f(p2(x)) | |
336 // * BinaryOperate1st<pair>(f) returns the function (x,y) -> f(p1(x),p1(y)) | |
337 // * BinaryOperate2nd<pair>(f) returns the function (x,y) -> f(p2(x),p2(y)) | |
338 // | |
339 // A typical usage for these functions would be when iterating over | |
340 // the contents of an STL map. For other sample usage, see the unittest. | |
341 | |
342 template<typename Pair, typename UnaryOp> | |
343 class UnaryOperateOnFirst | |
344 : public std::unary_function<Pair, typename UnaryOp::result_type> { | |
345 public: | |
346 UnaryOperateOnFirst() { | |
347 } | |
348 | |
349 UnaryOperateOnFirst(const UnaryOp& f) : f_(f) { | |
350 } | |
351 | |
352 typename UnaryOp::result_type operator()(const Pair& p) const { | |
353 return f_(p.first); | |
354 } | |
355 | |
356 private: | |
357 UnaryOp f_; | |
358 }; | |
359 | |
360 template<typename Pair, typename UnaryOp> | |
361 UnaryOperateOnFirst<Pair, UnaryOp> UnaryOperate1st(const UnaryOp& f) { | |
362 return UnaryOperateOnFirst<Pair, UnaryOp>(f); | |
363 } | |
364 | |
365 template<typename Pair, typename UnaryOp> | |
366 class UnaryOperateOnSecond | |
367 : public std::unary_function<Pair, typename UnaryOp::result_type> { | |
368 public: | |
369 UnaryOperateOnSecond() { | |
370 } | |
371 | |
372 UnaryOperateOnSecond(const UnaryOp& f) : f_(f) { | |
373 } | |
374 | |
375 typename UnaryOp::result_type operator()(const Pair& p) const { | |
376 return f_(p.second); | |
377 } | |
378 | |
379 private: | |
380 UnaryOp f_; | |
381 }; | |
382 | |
383 template<typename Pair, typename UnaryOp> | |
384 UnaryOperateOnSecond<Pair, UnaryOp> UnaryOperate2nd(const UnaryOp& f) { | |
385 return UnaryOperateOnSecond<Pair, UnaryOp>(f); | |
386 } | |
387 | |
388 template<typename Pair, typename BinaryOp> | |
389 class BinaryOperateOnFirst | |
390 : public std::binary_function<Pair, Pair, typename BinaryOp::result_type> { | |
391 public: | |
392 BinaryOperateOnFirst() { | |
393 } | |
394 | |
395 BinaryOperateOnFirst(const BinaryOp& f) : f_(f) { | |
396 } | |
397 | |
398 typename BinaryOp::result_type operator()(const Pair& p1, | |
399 const Pair& p2) const { | |
400 return f_(p1.first, p2.first); | |
401 } | |
402 | |
403 private: | |
404 BinaryOp f_; | |
405 }; | |
406 | |
407 template<typename Pair, typename BinaryOp> | |
408 BinaryOperateOnFirst<Pair, BinaryOp> BinaryOperate1st(const BinaryOp& f) { | |
409 return BinaryOperateOnFirst<Pair, BinaryOp>(f); | |
410 } | |
411 | |
412 template<typename Pair, typename BinaryOp> | |
413 class BinaryOperateOnSecond | |
414 : public std::binary_function<Pair, Pair, typename BinaryOp::result_type> { | |
415 public: | |
416 BinaryOperateOnSecond() { | |
417 } | |
418 | |
419 BinaryOperateOnSecond(const BinaryOp& f) : f_(f) { | |
420 } | |
421 | |
422 typename BinaryOp::result_type operator()(const Pair& p1, | |
423 const Pair& p2) const { | |
424 return f_(p1.second, p2.second); | |
425 } | |
426 | |
427 private: | |
428 BinaryOp f_; | |
429 }; | |
430 | |
431 template<typename Pair, typename BinaryOp> | |
432 BinaryOperateOnSecond<Pair, BinaryOp> BinaryOperate2nd(const BinaryOp& f) { | |
433 return BinaryOperateOnSecond<Pair, BinaryOp>(f); | |
434 } | |
435 | |
436 // Translates a set into a vector. | |
437 template<typename T> | |
438 std::vector<T> SetToVector(const std::set<T>& values) { | |
439 std::vector<T> result; | |
440 result.reserve(values.size()); | |
441 result.insert(result.begin(), values.begin(), values.end()); | |
442 return result; | |
443 } | |
444 | |
445 // Test to see if a set, map, hash_set or hash_map contains a particular key. | |
446 // Returns true if the key is in the collection. | |
447 template <typename Collection, typename Key> | |
448 bool ContainsKey(const Collection& collection, const Key& key) { | |
449 return collection.find(key) != collection.end(); | |
450 } | |
451 | |
452 #endif // BASE_STL_UTIL_INL_H_ | |
OLD | NEW |