/Users/deen/code/yugabyte-db/src/yb/gutil/stl_util.h
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright 2002 Google Inc. |
2 | | // |
3 | | // Licensed to the Apache Software Foundation (ASF) under one |
4 | | // or more contributor license agreements. See the NOTICE file |
5 | | // distributed with this work for additional information |
6 | | // regarding copyright ownership. The ASF licenses this file |
7 | | // to you under the Apache License, Version 2.0 (the |
8 | | // "License"); you may not use this file except in compliance |
9 | | // with the License. You may obtain a copy of the License at |
10 | | // |
11 | | // http://www.apache.org/licenses/LICENSE-2.0 |
12 | | // |
13 | | // Unless required by applicable law or agreed to in writing, |
14 | | // software distributed under the License is distributed on an |
15 | | // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
16 | | // KIND, either express or implied. See the License for the |
17 | | // specific language governing permissions and limitations |
18 | | // under the License. |
19 | | // |
20 | | // The following only applies to changes made to this file as part of YugaByte development. |
21 | | // |
22 | | // Portions Copyright (c) YugaByte, Inc. |
23 | | // |
24 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
25 | | // in compliance with the License. You may obtain a copy of the License at |
26 | | // |
27 | | // http://www.apache.org/licenses/LICENSE-2.0 |
28 | | // |
29 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
30 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
31 | | // or implied. See the License for the specific language governing permissions and limitations |
32 | | // under the License. |
33 | | // |
34 | | // --- |
35 | | // |
36 | | // |
37 | | // STL utility functions. Usually, these replace built-in, but slow(!), |
38 | | // STL functions with more efficient versions or provide a more convenient |
39 | | // and Google friendly API. |
40 | | // |
41 | | |
42 | | #ifndef YB_GUTIL_STL_UTIL_H |
43 | | #define YB_GUTIL_STL_UTIL_H |
44 | | |
45 | | #include <stddef.h> |
46 | | #include <string.h> // for memcpy |
47 | | |
48 | | #include <algorithm> |
49 | | #include <cassert> |
50 | | #include <deque> |
51 | | #include <functional> |
52 | | #include <set> |
53 | | #include <vector> |
54 | | |
55 | | #include "yb/gutil/integral_types.h" |
56 | | #include "yb/gutil/macros.h" |
57 | | #include "yb/gutil/port.h" |
58 | | |
59 | | using std::copy; |
60 | | using std::max; |
61 | | using std::min; |
62 | | using std::reverse; |
63 | | using std::sort; |
64 | | using std::swap; |
65 | | using std::deque; |
66 | | using std::binary_function; |
67 | | using std::less; |
68 | | using std::back_insert_iterator; |
69 | | using std::iterator_traits; |
70 | | using std::string; |
71 | | using std::vector; |
72 | | |
73 | | |
74 | | namespace yb { |
75 | | |
76 | | // Sort and remove duplicates of an STL vector or deque. |
77 | | template<class T> |
78 | | void STLSortAndRemoveDuplicates(T *v) { |
79 | | sort(v->begin(), v->end()); |
80 | | v->erase(unique(v->begin(), v->end()), v->end()); |
81 | | } |
82 | | |
83 | | // Clear internal memory of an STL object. |
84 | | // STL clear()/reserve(0) does not always free internal memory allocated |
85 | | // This function uses swap/destructor to ensure the internal memory is freed. |
86 | | template<class T> void STLClearObject(T* obj) { |
87 | | T tmp; |
88 | | tmp.swap(*obj); |
89 | | obj->reserve(0); // this is because sometimes "T tmp" allocates objects with |
90 | | // memory (arena implementation?). use reserve() |
91 | | // to clear() even if it doesn't always work |
92 | | } |
93 | | |
94 | | // Specialization for deque. Same as STLClearObject but doesn't call reserve |
95 | | // since deque doesn't have reserve. |
96 | | template <class T, class A> |
97 | | void STLClearObject(deque<T, A>* obj) { |
98 | | deque<T, A> tmp; |
99 | | tmp.swap(*obj); |
100 | | } |
101 | | |
102 | | // Reduce memory usage on behalf of object if its capacity is greater |
103 | | // than or equal to "limit", which defaults to 2^20. |
104 | | template <class T> inline void STLClearIfBig(T* obj, size_t limit = 1<<20) { |
105 | | if (obj->capacity() >= limit) { |
106 | | STLClearObject(obj); |
107 | | } else { |
108 | | obj->clear(); |
109 | | } |
110 | | } |
111 | | |
112 | | // Specialization for deque, which doesn't implement capacity(). |
113 | | template <class T, class A> |
114 | | inline void STLClearIfBig(deque<T, A>* obj, size_t limit = 1<<20) { |
115 | | if (obj->size() >= limit) { |
116 | | STLClearObject(obj); |
117 | | } else { |
118 | | obj->clear(); |
119 | | } |
120 | | } |
121 | | |
122 | | // Reduce the number of buckets in a hash_set or hash_map back to the |
123 | | // default if the current number of buckets is "limit" or more. |
124 | | // |
125 | | // Suppose you repeatedly fill and clear a hash_map or hash_set. If |
126 | | // you ever insert a lot of items, then your hash table will have lots |
127 | | // of buckets thereafter. (The number of buckets is not reduced when |
128 | | // the table is cleared.) Having lots of buckets is good if you |
129 | | // insert comparably many items in every iteration, because you'll |
130 | | // reduce collisions and table resizes. But having lots of buckets is |
131 | | // bad if you insert few items in most subsequent iterations, because |
132 | | // repeatedly clearing out all those buckets can get expensive. |
133 | | // |
134 | | // One solution is to call STLClearHashIfBig() with a "limit" value |
135 | | // that is a small multiple of the typical number of items in your |
136 | | // table. In the common case, this is equivalent to an ordinary |
137 | | // clear. In the rare case where you insert a lot of items, the |
138 | | // number of buckets is reset to the default to keep subsequent clear |
139 | | // operations cheap. Note that the default number of buckets is 193 |
140 | | // in the Gnu library implementation as of Jan '08. |
141 | | template <class T> inline void STLClearHashIfBig(T *obj, size_t limit) { |
142 | | if (obj->bucket_count() >= limit) { |
143 | | T tmp; |
144 | | tmp.swap(*obj); |
145 | | } else { |
146 | | obj->clear(); |
147 | | } |
148 | | } |
149 | | |
150 | | // Reserve space for STL object. |
151 | | // STL's reserve() will always copy. |
152 | | // This function avoid the copy if we already have capacity |
153 | | template<class T> void STLReserveIfNeeded(T* obj, int new_size) { |
154 | | if (obj->capacity() < new_size) // increase capacity |
155 | | obj->reserve(new_size); |
156 | | else if (obj->size() > new_size) // reduce size |
157 | | obj->resize(new_size); |
158 | | } |
159 | | |
160 | | // STLDeleteContainerPointers() |
161 | | // For a range within a container of pointers, calls delete |
162 | | // (non-array version) on these pointers. |
163 | | // NOTE: for these three functions, we could just implement a DeleteObject |
164 | | // functor and then call for_each() on the range and functor, but this |
165 | | // requires us to pull in all of <algorithm>, which seems expensive. |
166 | | // For hash_[multi]set, it is important that this deletes behind the iterator |
167 | | // because the hash_set may call the hash function on the iterator when it is |
168 | | // advanced, which could result in the hash function trying to deference a |
169 | | // stale pointer. |
170 | | // NOTE: If you're calling this on an entire container, you probably want |
171 | | // to call STLDeleteElements(&container) instead, or use an ElementDeleter. |
172 | | template <class ForwardIterator> |
173 | | void STLDeleteContainerPointers(ForwardIterator begin, |
174 | 32 | ForwardIterator end) { |
175 | 5.01k | while (begin != end) { |
176 | 4.98k | ForwardIterator temp = begin; |
177 | 4.98k | ++begin; |
178 | 4.98k | delete *temp; |
179 | 4.98k | } |
180 | 32 | } |
181 | | |
182 | | // STLDeleteContainerPairPointers() |
183 | | // For a range within a container of pairs, calls delete |
184 | | // (non-array version) on BOTH items in the pairs. |
185 | | // NOTE: Like STLDeleteContainerPointers, it is important that this deletes |
186 | | // behind the iterator because if both the key and value are deleted, the |
187 | | // container may call the hash function on the iterator when it is advanced, |
188 | | // which could result in the hash function trying to dereference a stale |
189 | | // pointer. |
190 | | template <class ForwardIterator> |
191 | | void STLDeleteContainerPairPointers(ForwardIterator begin, |
192 | | ForwardIterator end) { |
193 | | while (begin != end) { |
194 | | ForwardIterator temp = begin; |
195 | | ++begin; |
196 | | delete temp->first; |
197 | | delete temp->second; |
198 | | } |
199 | | } |
200 | | |
201 | | // STLDeleteContainerPairFirstPointers() |
202 | | // For a range within a container of pairs, calls delete (non-array version) |
203 | | // on the FIRST item in the pairs. |
204 | | // NOTE: Like STLDeleteContainerPointers, deleting behind the iterator. |
205 | | template <class ForwardIterator> |
206 | | void STLDeleteContainerPairFirstPointers(ForwardIterator begin, |
207 | | ForwardIterator end) { |
208 | | while (begin != end) { |
209 | | ForwardIterator temp = begin; |
210 | | ++begin; |
211 | | delete temp->first; |
212 | | } |
213 | | } |
214 | | |
215 | | // STLDeleteContainerPairSecondPointers() |
216 | | // For a range within a container of pairs, calls delete |
217 | | // (non-array version) on the SECOND item in the pairs. |
218 | | // NOTE: Like STLDeleteContainerPointers, deleting behind the iterator. |
219 | | // Deleting the value does not always invalidate the iterator, but it may |
220 | | // do so if the key is a pointer into the value object. |
221 | | // NOTE: If you're calling this on an entire container, you probably want |
222 | | // to call STLDeleteValues(&container) instead, or use ValueDeleter. |
223 | | template <class ForwardIterator> |
224 | | void STLDeleteContainerPairSecondPointers(ForwardIterator begin, |
225 | 151k | ForwardIterator end) { |
226 | 234k | while (begin != end) { |
227 | 83.3k | ForwardIterator temp = begin; |
228 | 83.3k | ++begin; |
229 | 83.3k | delete temp->second; |
230 | 83.3k | } |
231 | 151k | } void yb::STLDeleteContainerPairSecondPointers<std::__1::__hash_map_iterator<std::__1::__hash_iterator<std::__1::__hash_node<std::__1::__hash_value_type<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::consensus::PeerMessageQueue::TrackedPeer*>, void*>*> > >(std::__1::__hash_map_iterator<std::__1::__hash_iterator<std::__1::__hash_node<std::__1::__hash_value_type<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::consensus::PeerMessageQueue::TrackedPeer*>, void*>*> >, std::__1::__hash_map_iterator<std::__1::__hash_iterator<std::__1::__hash_node<std::__1::__hash_value_type<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::consensus::PeerMessageQueue::TrackedPeer*>, void*>*> >) Line | Count | Source | 225 | 151k | ForwardIterator end) { | 226 | 227k | while (begin != end) { | 227 | 75.6k | ForwardIterator temp = begin; | 228 | 75.6k | ++begin; | 229 | 75.6k | delete temp->second; | 230 | 75.6k | } | 231 | 151k | } |
void yb::STLDeleteContainerPairSecondPointers<std::__1::__map_iterator<std::__1::__tree_iterator<std::__1::__value_type<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::Webserver::PathHandler*>, std::__1::__tree_node<std::__1::__value_type<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::Webserver::PathHandler*>, void*>*, long> > >(std::__1::__map_iterator<std::__1::__tree_iterator<std::__1::__value_type<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::Webserver::PathHandler*>, std::__1::__tree_node<std::__1::__value_type<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::Webserver::PathHandler*>, void*>*, long> >, std::__1::__map_iterator<std::__1::__tree_iterator<std::__1::__value_type<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::Webserver::PathHandler*>, std::__1::__tree_node<std::__1::__value_type<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::Webserver::PathHandler*>, void*>*, long> >) Line | Count | Source | 225 | 257 | ForwardIterator end) { | 226 | 7.89k | while (begin != end) { | 227 | 7.63k | ForwardIterator temp = begin; | 228 | 7.63k | ++begin; | 229 | 7.63k | delete temp->second; | 230 | 7.63k | } | 231 | 257 | } |
void yb::STLDeleteContainerPairSecondPointers<std::__1::__hash_map_iterator<std::__1::__hash_iterator<std::__1::__hash_node<std::__1::__hash_value_type<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::TimedFailureDetector::Node*>, void*>*> > >(std::__1::__hash_map_iterator<std::__1::__hash_iterator<std::__1::__hash_node<std::__1::__hash_value_type<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::TimedFailureDetector::Node*>, void*>*> >, std::__1::__hash_map_iterator<std::__1::__hash_iterator<std::__1::__hash_node<std::__1::__hash_value_type<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::TimedFailureDetector::Node*>, void*>*> >) Line | Count | Source | 225 | 1 | ForwardIterator end) { | 226 | 1 | while (begin != end) { | 227 | 0 | ForwardIterator temp = begin; | 228 | 0 | ++begin; | 229 | 0 | delete temp->second; | 230 | 0 | } | 231 | 1 | } |
|
232 | | |
233 | | template<typename T> |
234 | | inline void STLAssignToVector(vector<T>* vec, |
235 | | const T* ptr, |
236 | 0 | size_t n) { |
237 | 0 | vec->resize(n); |
238 | 0 | if (n == 0) return; |
239 | 0 | memcpy(&vec->front(), ptr, n*sizeof(T)); |
240 | 0 | } |
241 | | |
242 | | // Not faster; but we need the specialization so the function works at all |
243 | | // on the vector<bool> specialization. |
244 | | template<> |
245 | | inline void STLAssignToVector(vector<bool>* vec, |
246 | | const bool* ptr, |
247 | 0 | size_t n) { |
248 | 0 | vec->clear(); |
249 | 0 | if (n == 0) return; |
250 | 0 | vec->insert(vec->begin(), ptr, ptr + n); |
251 | 0 | } |
252 | | |
253 | | /***** Hack to allow faster assignment to a vector *****/ |
254 | | |
255 | | // This routine speeds up an assignment of 32 bytes to a vector from |
256 | | // about 250 cycles per assignment to about 140 cycles. |
257 | | // |
258 | | // Usage: |
259 | | // STLAssignToVectorChar(&vec, ptr, size); |
260 | | // STLAssignToString(&str, ptr, size); |
261 | | |
262 | | inline void STLAssignToVectorChar(vector<char>* vec, |
263 | | const char* ptr, |
264 | 0 | size_t n) { |
265 | 0 | STLAssignToVector(vec, ptr, n); |
266 | 0 | } |
267 | | |
268 | | // A struct that mirrors the GCC4 implementation of a string. See: |
269 | | // /usr/crosstool/v8/gcc-4.1.0-glibc-2.2.2/i686-unknown-linux-gnu/include/c++/4.1.0/ext/sso_string_base.h |
270 | | struct InternalStringRepGCC4 { |
271 | | char* _M_data; |
272 | | size_t _M_string_length; |
273 | | |
274 | | enum { _S_local_capacity = 15 }; |
275 | | |
276 | | union { |
277 | | char _M_local_data[_S_local_capacity + 1]; |
278 | | size_t _M_allocated_capacity; |
279 | | }; |
280 | | }; |
281 | | |
282 | | // Like str->resize(new_size), except any new characters added to |
283 | | // "*str" as a result of resizing may be left uninitialized, rather |
284 | | // than being filled with '0' bytes. Typically used when code is then |
285 | | // going to overwrite the backing store of the string with known data. |
286 | 237M | inline void STLStringResizeUninitialized(string* s, size_t new_size) { |
287 | 237M | if (sizeof(*s) == sizeof(InternalStringRepGCC4)) { |
288 | 0 | if (new_size > s->capacity()) { |
289 | 0 | s->reserve(new_size); |
290 | 0 | } |
291 | | // The line below depends on the layout of 'string'. THIS IS |
292 | | // NON-PORTABLE CODE. If our STL implementation changes, we will |
293 | | // need to change this as well. |
294 | 0 | InternalStringRepGCC4* rep = reinterpret_cast<InternalStringRepGCC4*>(s); |
295 | 0 | assert(rep->_M_data == s->data()); |
296 | 0 | assert(rep->_M_string_length == s->size()); |
297 | | |
298 | | // We have to null-terminate the string for c_str() to work properly. |
299 | | // So we leave the actual contents of the string uninitialized, but |
300 | | // we set the byte one past the new end of the string to '\0' |
301 | 0 | const_cast<char*>(s->data())[new_size] = '\0'; |
302 | 0 | rep->_M_string_length = new_size; |
303 | 237M | } else { |
304 | | // Slow path: have to reallocate stuff, or an unknown string rep |
305 | 237M | s->resize(new_size); |
306 | 237M | } |
307 | 237M | } |
308 | | |
309 | | // Returns true if the string implementation supports a resize where |
310 | | // the new characters added to the string are left untouched. |
311 | 0 | inline bool STLStringSupportsNontrashingResize(const string& s) { |
312 | 0 | return (sizeof(s) == sizeof(InternalStringRepGCC4)); |
313 | 0 | } |
314 | | |
315 | 0 | inline void STLAssignToString(string* str, const char* ptr, size_t n) { |
316 | 0 | STLStringResizeUninitialized(str, n); |
317 | 0 | if (n == 0) return; |
318 | 0 | memcpy(&*str->begin(), ptr, n); |
319 | 0 | } |
320 | | |
321 | 0 | inline void STLAppendToString(string* str, const char* ptr, size_t n) { |
322 | 0 | if (n == 0) return; |
323 | 0 | size_t old_size = str->size(); |
324 | 0 | STLStringResizeUninitialized(str, old_size + n); |
325 | 0 | memcpy(&*str->begin() + old_size, ptr, n); |
326 | 0 | } |
327 | | |
328 | | // To treat a possibly-empty vector as an array, use these functions. |
329 | | // If you know the array will never be empty, you can use &*v.begin() |
330 | | // directly, but that is allowed to dump core if v is empty. This |
331 | | // function is the most efficient code that will work, taking into |
332 | | // account how our STL is actually implemented. THIS IS NON-PORTABLE |
333 | | // CODE, so call us instead of repeating the nonportable code |
334 | | // everywhere. If our STL implementation changes, we will need to |
335 | | // change this as well. |
336 | | |
337 | | template<typename T, typename Allocator> |
338 | | inline T* vector_as_array(vector<T, Allocator>* v) { |
339 | | # ifdef NDEBUG |
340 | | return &*v->begin(); |
341 | | # else |
342 | | return v->empty() ? NULL : &*v->begin(); |
343 | | # endif |
344 | | } |
345 | | |
346 | | template<typename T, typename Allocator> |
347 | | inline const T* vector_as_array(const vector<T, Allocator>* v) { |
348 | | # ifdef NDEBUG |
349 | | return &*v->begin(); |
350 | | # else |
351 | | return v->empty() ? NULL : &*v->begin(); |
352 | | # endif |
353 | | } |
354 | | |
355 | | // Return a mutable char* pointing to a string's internal buffer, |
356 | | // which may not be null-terminated. Writing through this pointer will |
357 | | // modify the string. |
358 | | // |
359 | | // string_as_array(&str)[i] is valid for 0 <= i < str.size() until the |
360 | | // next call to a string method that invalidates iterators. |
361 | | // |
362 | | // Prior to C++11, there was no standard-blessed way of getting a mutable |
363 | | // reference to a string's internal buffer. The requirement that string be |
364 | | // contiguous is officially part of the C++11 standard [string.require]/5. |
365 | | // According to Matt Austern, this should already work on all current C++98 |
366 | | // implementations. |
367 | 236M | inline char* string_as_array(string* str) { |
368 | | // DO NOT USE const_cast<char*>(str->data())! See the unittest for why. |
369 | 236M | return str->empty() ? NULL : &*str->begin(); |
370 | 236M | } |
371 | | |
372 | | // These are methods that test two hash maps/sets for equality. These exist |
373 | | // because the == operator in the STL can return false when the maps/sets |
374 | | // contain identical elements. This is because it compares the internal hash |
375 | | // tables which may be different if the order of insertions and deletions |
376 | | // differed. |
377 | | |
378 | | template <class HashSet> |
379 | | inline bool |
380 | | HashSetEquality(const HashSet& set_a, |
381 | | const HashSet& set_b) { |
382 | | if (set_a.size() != set_b.size()) return false; |
383 | | for (typename HashSet::const_iterator i = set_a.begin(); |
384 | | i != set_a.end(); |
385 | | ++i) |
386 | | if (set_b.find(*i) == set_b.end()) return false; |
387 | | return true; |
388 | | } |
389 | | |
390 | | template <class HashMap> |
391 | | inline bool |
392 | | HashMapEquality(const HashMap& map_a, |
393 | | const HashMap& map_b) { |
394 | | if (map_a.size() != map_b.size()) return false; |
395 | | for (typename HashMap::const_iterator i = map_a.begin(); |
396 | | i != map_a.end(); ++i) { |
397 | | typename HashMap::const_iterator j = map_b.find(i->first); |
398 | | if (j == map_b.end()) return false; |
399 | | if (i->second != j->second) return false; |
400 | | } |
401 | | return true; |
402 | | } |
403 | | |
404 | | // The following functions are useful for cleaning up STL containers |
405 | | // whose elements point to allocated memory. |
406 | | |
407 | | // STLDeleteElements() deletes all the elements in an STL container and clears |
408 | | // the container. This function is suitable for use with a vector, set, |
409 | | // hash_set, or any other STL container which defines sensible begin(), end(), |
410 | | // and clear() methods. |
411 | | // |
412 | | // If container is NULL, this function is a no-op. |
413 | | // |
414 | | // As an alternative to calling STLDeleteElements() directly, consider |
415 | | // ElementDeleter (defined below), which ensures that your container's elements |
416 | | // are deleted when the ElementDeleter goes out of scope. |
417 | | template <class T> |
418 | 32 | void STLDeleteElements(T *container) { |
419 | 32 | if (!container) return0 ; |
420 | 32 | STLDeleteContainerPointers(container->begin(), container->end()); |
421 | 32 | container->clear(); |
422 | 32 | } |
423 | | |
424 | | // Given an STL container consisting of (key, value) pairs, STLDeleteValues |
425 | | // deletes all the "value" components and clears the container. Does nothing |
426 | | // in the case it's given a NULL pointer. |
427 | | template <class T> |
428 | 151k | void STLDeleteValues(T *v) { |
429 | 151k | if (!v) return0 ; |
430 | 151k | STLDeleteContainerPairSecondPointers(v->begin(), v->end()); |
431 | 151k | v->clear(); |
432 | 151k | } void yb::STLDeleteValues<std::__1::unordered_map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::consensus::PeerMessageQueue::TrackedPeer*, std::__1::hash<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::equal_to<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, yb::consensus::PeerMessageQueue::TrackedPeer*> > > >(std::__1::unordered_map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::consensus::PeerMessageQueue::TrackedPeer*, std::__1::hash<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::equal_to<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, yb::consensus::PeerMessageQueue::TrackedPeer*> > >*) Line | Count | Source | 428 | 151k | void STLDeleteValues(T *v) { | 429 | 151k | if (!v) return0 ; | 430 | 151k | STLDeleteContainerPairSecondPointers(v->begin(), v->end()); | 431 | 151k | v->clear(); | 432 | 151k | } |
void yb::STLDeleteValues<std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::Webserver::PathHandler*, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, yb::Webserver::PathHandler*> > > >(std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::Webserver::PathHandler*, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, yb::Webserver::PathHandler*> > >*) Line | Count | Source | 428 | 257 | void STLDeleteValues(T *v) { | 429 | 257 | if (!v) return0 ; | 430 | 257 | STLDeleteContainerPairSecondPointers(v->begin(), v->end()); | 431 | 257 | v->clear(); | 432 | 257 | } |
void yb::STLDeleteValues<std::__1::unordered_map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::TimedFailureDetector::Node*, std::__1::hash<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::equal_to<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, yb::TimedFailureDetector::Node*> > > >(std::__1::unordered_map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, yb::TimedFailureDetector::Node*, std::__1::hash<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::equal_to<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, yb::TimedFailureDetector::Node*> > >*) Line | Count | Source | 428 | 1 | void STLDeleteValues(T *v) { | 429 | 1 | if (!v) return0 ; | 430 | 1 | STLDeleteContainerPairSecondPointers(v->begin(), v->end()); | 431 | 1 | v->clear(); | 432 | 1 | } |
|
433 | | |
434 | | |
435 | | // ElementDeleter and ValueDeleter provide a convenient way to delete all |
436 | | // elements or values from STL containers when they go out of scope. This |
437 | | // greatly simplifies code that creates temporary objects and has multiple |
438 | | // return statements. Example: |
439 | | // |
440 | | // vector<MyProto *> tmp_proto; |
441 | | // ElementDeleter d(&tmp_proto); |
442 | | // if (...) return false; |
443 | | // ... |
444 | | // return success; |
445 | | |
446 | | // A very simple interface that simply provides a virtual destructor. It is |
447 | | // used as a non-templated base class for the TemplatedElementDeleter and |
448 | | // TemplatedValueDeleter classes. Clients should not typically use this class |
449 | | // directly. |
450 | | class BaseDeleter { |
451 | | public: |
452 | | virtual ~BaseDeleter() {} |
453 | | |
454 | | protected: |
455 | | BaseDeleter() {} |
456 | | |
457 | | private: |
458 | | DISALLOW_EVIL_CONSTRUCTORS(BaseDeleter); |
459 | | }; |
460 | | |
461 | | // Given a pointer to an STL container, this class will delete all the element |
462 | | // pointers when it goes out of scope. Clients should typically use |
463 | | // ElementDeleter rather than invoking this class directly. |
464 | | template<class STLContainer> |
465 | | class TemplatedElementDeleter : public BaseDeleter { |
466 | | public: |
467 | | explicit TemplatedElementDeleter<STLContainer>(STLContainer *ptr) |
468 | | : container_ptr_(ptr) { |
469 | | } |
470 | | |
471 | | virtual ~TemplatedElementDeleter<STLContainer>() { |
472 | | STLDeleteElements(container_ptr_); |
473 | | } |
474 | | |
475 | | private: |
476 | | STLContainer *container_ptr_; |
477 | | |
478 | | DISALLOW_EVIL_CONSTRUCTORS(TemplatedElementDeleter); |
479 | | }; |
480 | | |
481 | | // Like TemplatedElementDeleter, this class will delete element pointers from a |
482 | | // container when it goes out of scope. However, it is much nicer to use, |
483 | | // since the class itself is not templated. |
484 | | class ElementDeleter { |
485 | | public: |
486 | | template <class STLContainer> |
487 | | explicit ElementDeleter(STLContainer *ptr) |
488 | | : deleter_(new TemplatedElementDeleter<STLContainer>(ptr)) { |
489 | | } |
490 | | |
491 | | ~ElementDeleter() { |
492 | | delete deleter_; |
493 | | } |
494 | | |
495 | | private: |
496 | | BaseDeleter *deleter_; |
497 | | |
498 | | DISALLOW_EVIL_CONSTRUCTORS(ElementDeleter); |
499 | | }; |
500 | | |
501 | | // Given a pointer to an STL container this class will delete all the value |
502 | | // pointers when it goes out of scope. Clients should typically use |
503 | | // ValueDeleter rather than invoking this class directly. |
504 | | template<class STLContainer> |
505 | | class TemplatedValueDeleter : public BaseDeleter { |
506 | | public: |
507 | | explicit TemplatedValueDeleter<STLContainer>(STLContainer *ptr) |
508 | | : container_ptr_(ptr) { |
509 | | } |
510 | | |
511 | | virtual ~TemplatedValueDeleter<STLContainer>() { |
512 | | STLDeleteValues(container_ptr_); |
513 | | } |
514 | | |
515 | | private: |
516 | | STLContainer *container_ptr_; |
517 | | |
518 | | DISALLOW_EVIL_CONSTRUCTORS(TemplatedValueDeleter); |
519 | | }; |
520 | | |
521 | | // Similar to ElementDeleter, but wraps a TemplatedValueDeleter rather than an |
522 | | // TemplatedElementDeleter. |
523 | | class ValueDeleter { |
524 | | public: |
525 | | template <class STLContainer> |
526 | | explicit ValueDeleter(STLContainer *ptr) |
527 | | : deleter_(new TemplatedValueDeleter<STLContainer>(ptr)) { |
528 | | } |
529 | | |
530 | 0 | ~ValueDeleter() { |
531 | 0 | delete deleter_; |
532 | 0 | } |
533 | | |
534 | | private: |
535 | | BaseDeleter *deleter_; |
536 | | |
537 | | DISALLOW_EVIL_CONSTRUCTORS(ValueDeleter); |
538 | | }; |
539 | | |
540 | | |
541 | | // STLElementDeleter and STLValueDeleter are similar to ElementDeleter and |
542 | | // ValueDeleter, except that: |
543 | | // - The classes are templated, making them less convenient to use. |
544 | | // - Their destructors are not virtual, making them potentially more efficient. |
545 | | // New code should typically use ElementDeleter and ValueDeleter unless |
546 | | // efficiency is a large concern. |
547 | | |
548 | | template<class STLContainer> class STLElementDeleter { |
549 | | public: |
550 | | STLElementDeleter<STLContainer>(STLContainer *ptr) : container_ptr_(ptr) {} |
551 | | ~STLElementDeleter<STLContainer>() { STLDeleteElements(container_ptr_); } |
552 | | private: |
553 | | STLContainer *container_ptr_; |
554 | | }; |
555 | | |
556 | | template<class STLContainer> class STLValueDeleter { |
557 | | public: |
558 | | STLValueDeleter<STLContainer>(STLContainer *ptr) : container_ptr_(ptr) {} |
559 | | ~STLValueDeleter<STLContainer>() { STLDeleteValues(container_ptr_); } |
560 | | private: |
561 | | STLContainer *container_ptr_; |
562 | | }; |
563 | | |
564 | | |
565 | | // STLSet{Difference,SymmetricDifference,Union,Intersection}(A a, B b, C *c) |
566 | | // *APPEND* the set {difference, symmetric difference, union, intersection} of |
567 | | // the two sets a and b to c. |
568 | | // STLSet{Difference,SymmetricDifference,Union,Intersection}(T a, T b) do the |
569 | | // same but return the result by value rather than by the third pointer |
570 | | // argument. The result type is the same as both of the inputs in the two |
571 | | // argument case. |
572 | | // |
573 | | // Requires: |
574 | | // a and b must be STL like containers that contain sorted data (as defined |
575 | | // by the < operator). |
576 | | // For the 3 argument version &a == c or &b == c are disallowed. In those |
577 | | // cases the 2 argument version is probably what you want anyway: |
578 | | // a = STLSetDifference(a, b); |
579 | | // |
580 | | // These function are convenience functions. The code they implement is |
581 | | // trivial (at least for now). The STL incantations they wrap are just too |
582 | | // verbose for programmers to use then and they are unpleasant to the eye. |
583 | | // Without these convenience versions people will simply keep writing one-off |
584 | | // for loops which are harder to read and more error prone. |
585 | | // |
586 | | // Note that for initial construction of an object it is just as efficient to |
587 | | // use the 2 argument version as the 3 version due to RVO (return value |
588 | | // optimization) of modern C++ compilers: |
589 | | // set<int> c = STLSetDifference(a, b); |
590 | | // is an example of where RVO comes into play. |
591 | | |
592 | | template<typename SortedSTLContainerA, |
593 | | typename SortedSTLContainerB, |
594 | | typename SortedSTLContainerC> |
595 | | void STLSetDifference(const SortedSTLContainerA &a, |
596 | | const SortedSTLContainerB &b, |
597 | | SortedSTLContainerC *c) { |
598 | | // The qualified name avoids an ambiguity error, particularly with C++11: |
599 | | assert(std::is_sorted(a.begin(), a.end())); |
600 | | assert(std::is_sorted(b.begin(), b.end())); |
601 | | assert(static_cast<const void *>(&a) != |
602 | | static_cast<const void *>(c)); |
603 | | assert(static_cast<const void *>(&b) != |
604 | | static_cast<const void *>(c)); |
605 | | std::set_difference(a.begin(), a.end(), b.begin(), b.end(), |
606 | | std::inserter(*c, c->end())); |
607 | | } |
608 | | |
609 | | template<typename SortedSTLContainer> |
610 | | SortedSTLContainer STLSetDifference(const SortedSTLContainer &a, |
611 | | const SortedSTLContainer &b) { |
612 | | SortedSTLContainer c; |
613 | | STLSetDifference(a, b, &c); |
614 | | return c; |
615 | | } |
616 | | |
617 | | template<typename SortedSTLContainerA, |
618 | | typename SortedSTLContainerB, |
619 | | typename SortedSTLContainerC> |
620 | | void STLSetUnion(const SortedSTLContainerA &a, |
621 | | const SortedSTLContainerB &b, |
622 | | SortedSTLContainerC *c) { |
623 | | assert(std::is_sorted(a.begin(), a.end())); |
624 | | assert(std::is_sorted(b.begin(), b.end())); |
625 | | assert(static_cast<const void *>(&a) != |
626 | | static_cast<const void *>(c)); |
627 | | assert(static_cast<const void *>(&b) != |
628 | | static_cast<const void *>(c)); |
629 | | std::set_union(a.begin(), a.end(), b.begin(), b.end(), |
630 | | std::inserter(*c, c->end())); |
631 | | } |
632 | | |
633 | | template<typename SortedSTLContainerA, |
634 | | typename SortedSTLContainerB, |
635 | | typename SortedSTLContainerC> |
636 | | void STLSetSymmetricDifference(const SortedSTLContainerA &a, |
637 | | const SortedSTLContainerB &b, |
638 | | SortedSTLContainerC *c) { |
639 | | assert(std::is_sorted(a.begin(), a.end())); |
640 | | assert(std::is_sorted(b.begin(), b.end())); |
641 | | assert(static_cast<const void *>(&a) != |
642 | | static_cast<const void *>(c)); |
643 | | assert(static_cast<const void *>(&b) != |
644 | | static_cast<const void *>(c)); |
645 | | std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), |
646 | | std::inserter(*c, c->end())); |
647 | | } |
648 | | |
649 | | template<typename SortedSTLContainer> |
650 | | SortedSTLContainer STLSetSymmetricDifference(const SortedSTLContainer &a, |
651 | | const SortedSTLContainer &b) { |
652 | | SortedSTLContainer c; |
653 | | STLSetSymmetricDifference(a, b, &c); |
654 | | return c; |
655 | | } |
656 | | |
657 | | template<typename SortedSTLContainer> |
658 | | SortedSTLContainer STLSetUnion(const SortedSTLContainer &a, |
659 | | const SortedSTLContainer &b) { |
660 | | SortedSTLContainer c; |
661 | | STLSetUnion(a, b, &c); |
662 | | return c; |
663 | | } |
664 | | |
665 | | template<typename SortedSTLContainerA, |
666 | | typename SortedSTLContainerB, |
667 | | typename SortedSTLContainerC> |
668 | | void STLSetIntersection(const SortedSTLContainerA &a, |
669 | | const SortedSTLContainerB &b, |
670 | | SortedSTLContainerC *c) { |
671 | | assert(std::is_sorted(a.begin(), a.end())); |
672 | | assert(std::is_sorted(b.begin(), b.end())); |
673 | | assert(static_cast<const void *>(&a) != |
674 | | static_cast<const void *>(c)); |
675 | | assert(static_cast<const void *>(&b) != |
676 | | static_cast<const void *>(c)); |
677 | | std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), |
678 | | std::inserter(*c, c->end())); |
679 | | } |
680 | | |
681 | | template<typename SortedSTLContainer> |
682 | | SortedSTLContainer STLSetIntersection(const SortedSTLContainer &a, |
683 | | const SortedSTLContainer &b) { |
684 | | SortedSTLContainer c; |
685 | | STLSetIntersection(a, b, &c); |
686 | | return c; |
687 | | } |
688 | | |
689 | | // Similar to STLSet{Union,Intesection,etc}, but simpler because the result is |
690 | | // always bool. |
691 | | template<typename SortedSTLContainerA, |
692 | | typename SortedSTLContainerB> |
693 | | bool STLIncludes(const SortedSTLContainerA &a, |
694 | | const SortedSTLContainerB &b) { |
695 | | assert(std::is_sorted(a.begin(), a.end())); |
696 | | assert(std::is_sorted(b.begin(), b.end())); |
697 | | return std::includes(a.begin(), a.end(), |
698 | | b.begin(), b.end()); |
699 | | } |
700 | | |
701 | | // Functors that compose arbitrary unary and binary functions with a |
702 | | // function that "projects" one of the members of a pair. |
703 | | // Specifically, if p1 and p2, respectively, are the functions that |
704 | | // map a pair to its first and second, respectively, members, the |
705 | | // table below summarizes the functions that can be constructed: |
706 | | // |
707 | | // * UnaryOperate1st<pair>(f) returns the function x -> f(p1(x)) |
708 | | // * UnaryOperate2nd<pair>(f) returns the function x -> f(p2(x)) |
709 | | // * BinaryOperate1st<pair>(f) returns the function (x,y) -> f(p1(x),p1(y)) |
710 | | // * BinaryOperate2nd<pair>(f) returns the function (x,y) -> f(p2(x),p2(y)) |
711 | | // |
712 | | // A typical usage for these functions would be when iterating over |
713 | | // the contents of an STL map. For other sample usage, see the unittest. |
714 | | |
715 | | template<typename Pair, typename UnaryOp> |
716 | | class UnaryOperateOnFirst |
717 | | : public std::unary_function<Pair, typename UnaryOp::result_type> { |
718 | | public: |
719 | | UnaryOperateOnFirst() { |
720 | | } |
721 | | |
722 | | explicit UnaryOperateOnFirst(const UnaryOp& f) : f_(f) { |
723 | | } |
724 | | |
725 | | typename UnaryOp::result_type operator()(const Pair& p) const { |
726 | | return f_(p.first); |
727 | | } |
728 | | |
729 | | private: |
730 | | UnaryOp f_; |
731 | | }; |
732 | | |
733 | | template<typename Pair, typename UnaryOp> |
734 | | UnaryOperateOnFirst<Pair, UnaryOp> UnaryOperate1st(const UnaryOp& f) { |
735 | | return UnaryOperateOnFirst<Pair, UnaryOp>(f); |
736 | | } |
737 | | |
738 | | template<typename Pair, typename UnaryOp> |
739 | | class UnaryOperateOnSecond |
740 | | : public std::unary_function<Pair, typename UnaryOp::result_type> { |
741 | | public: |
742 | | UnaryOperateOnSecond() { |
743 | | } |
744 | | |
745 | | explicit UnaryOperateOnSecond(const UnaryOp& f) : f_(f) { |
746 | | } |
747 | | |
748 | | typename UnaryOp::result_type operator()(const Pair& p) const { |
749 | | return f_(p.second); |
750 | | } |
751 | | |
752 | | private: |
753 | | UnaryOp f_; |
754 | | }; |
755 | | |
756 | | template<typename Pair, typename UnaryOp> |
757 | | UnaryOperateOnSecond<Pair, UnaryOp> UnaryOperate2nd(const UnaryOp& f) { |
758 | | return UnaryOperateOnSecond<Pair, UnaryOp>(f); |
759 | | } |
760 | | |
761 | | template<typename Pair, typename BinaryOp> |
762 | | class BinaryOperateOnFirst |
763 | | : public std::binary_function<Pair, Pair, typename BinaryOp::result_type> { |
764 | | public: |
765 | | BinaryOperateOnFirst() { |
766 | | } |
767 | | |
768 | | explicit BinaryOperateOnFirst(const BinaryOp& f) : f_(f) { |
769 | | } |
770 | | |
771 | | typename BinaryOp::result_type operator()(const Pair& p1, |
772 | | const Pair& p2) const { |
773 | | return f_(p1.first, p2.first); |
774 | | } |
775 | | |
776 | | private: |
777 | | BinaryOp f_; |
778 | | }; |
779 | | |
780 | | // TODO(user): explicit? |
781 | | template<typename Pair, typename BinaryOp> |
782 | | BinaryOperateOnFirst<Pair, BinaryOp> BinaryOperate1st(const BinaryOp& f) { |
783 | | return BinaryOperateOnFirst<Pair, BinaryOp>(f); |
784 | | } |
785 | | |
786 | | template<typename Pair, typename BinaryOp> |
787 | | class BinaryOperateOnSecond |
788 | | : public std::binary_function<Pair, Pair, typename BinaryOp::result_type> { |
789 | | public: |
790 | | BinaryOperateOnSecond() { |
791 | | } |
792 | | |
793 | | explicit BinaryOperateOnSecond(const BinaryOp& f) : f_(f) { |
794 | | } |
795 | | |
796 | | typename BinaryOp::result_type operator()(const Pair& p1, |
797 | | const Pair& p2) const { |
798 | | return f_(p1.second, p2.second); |
799 | | } |
800 | | |
801 | | private: |
802 | | BinaryOp f_; |
803 | | }; |
804 | | |
805 | | template<typename Pair, typename BinaryOp> |
806 | | BinaryOperateOnSecond<Pair, BinaryOp> BinaryOperate2nd(const BinaryOp& f) { |
807 | | return BinaryOperateOnSecond<Pair, BinaryOp>(f); |
808 | | } |
809 | | |
810 | | // Functor that composes a binary functor h from an arbitrary binary functor |
811 | | // f and two unary functors g1, g2, so that: |
812 | | // |
813 | | // BinaryCompose1(f, g) returns function (x, y) -> f(g(x), g(y)) |
814 | | // BinaryCompose2(f, g1, g2) returns function (x, y) -> f(g1(x), g2(y)) |
815 | | // |
816 | | // This is a generalization of the BinaryOperate* functors for types other |
817 | | // than pairs. |
818 | | // |
819 | | // For sample usage, see the unittest. |
820 | | // |
821 | | // F has to be a model of AdaptableBinaryFunction. |
822 | | // G1 and G2 have to be models of AdabtableUnaryFunction. |
823 | | template<typename F, typename G1, typename G2> |
824 | | class BinaryComposeBinary : public binary_function<typename G1::argument_type, |
825 | | typename G2::argument_type, |
826 | | typename F::result_type> { |
827 | | public: |
828 | | BinaryComposeBinary(F f, G1 g1, G2 g2) : f_(f), g1_(g1), g2_(g2) { } |
829 | | |
830 | | typename F::result_type operator()(typename G1::argument_type x, |
831 | | typename G2::argument_type y) const { |
832 | | return f_(g1_(x), g2_(y)); |
833 | | } |
834 | | |
835 | | private: |
836 | | F f_; |
837 | | G1 g1_; |
838 | | G2 g2_; |
839 | | }; |
840 | | |
841 | | template<typename F, typename G> |
842 | | BinaryComposeBinary<F, G, G> BinaryCompose1(F f, G g) { |
843 | | return BinaryComposeBinary<F, G, G>(f, g, g); |
844 | | } |
845 | | |
846 | | template<typename F, typename G1, typename G2> |
847 | | BinaryComposeBinary<F, G1, G2> BinaryCompose2(F f, G1 g1, G2 g2) { |
848 | | return BinaryComposeBinary<F, G1, G2>(f, g1, g2); |
849 | | } |
850 | | |
851 | | // This is a wrapper for an STL allocator which keeps a count of the |
852 | | // active bytes allocated by this class of allocators. This is NOT |
853 | | // THREAD SAFE. This should only be used in situations where you can |
854 | | // ensure that only a single thread performs allocation and |
855 | | // deallocation. |
856 | | template <typename T, typename Alloc = std::allocator<T> > |
857 | | class STLCountingAllocator : public Alloc { |
858 | | public: |
859 | | typedef typename Alloc::pointer pointer; |
860 | | typedef typename Alloc::size_type size_type; |
861 | | |
862 | | STLCountingAllocator() : bytes_used_(NULL) { } |
863 | 45.3M | explicit STLCountingAllocator(int64* b) : bytes_used_(b) {} |
864 | | |
865 | | // Constructor used for rebinding |
866 | | template <class U> |
867 | | STLCountingAllocator(const STLCountingAllocator<U>& x) |
868 | | : Alloc(x), |
869 | 136M | bytes_used_(x.bytes_used()) { |
870 | 136M | } yb::STLCountingAllocator<std::__1::__hash_value_type<GStringPiece, unsigned long>, std::__1::allocator<std::__1::__hash_value_type<GStringPiece, unsigned long> > >::STLCountingAllocator<std::__1::pair<GStringPiece const, unsigned long> >(yb::STLCountingAllocator<std::__1::pair<GStringPiece const, unsigned long>, std::__1::allocator<std::__1::pair<GStringPiece const, unsigned long> > > const&) Line | Count | Source | 869 | 45.4M | bytes_used_(x.bytes_used()) { | 870 | 45.4M | } |
yb::STLCountingAllocator<std::__1::__hash_node_base<std::__1::__hash_node<std::__1::__hash_value_type<GStringPiece, unsigned long>, void*>*>*, std::__1::allocator<std::__1::__hash_node_base<std::__1::__hash_node<std::__1::__hash_value_type<GStringPiece, unsigned long>, void*>*>*> >::STLCountingAllocator<std::__1::__hash_value_type<GStringPiece, unsigned long> >(yb::STLCountingAllocator<std::__1::__hash_value_type<GStringPiece, unsigned long>, std::__1::allocator<std::__1::__hash_value_type<GStringPiece, unsigned long> > > const&) Line | Count | Source | 869 | 45.3M | bytes_used_(x.bytes_used()) { | 870 | 45.3M | } |
yb::STLCountingAllocator<std::__1::__hash_node<std::__1::__hash_value_type<GStringPiece, unsigned long>, void*>, std::__1::allocator<std::__1::__hash_node<std::__1::__hash_value_type<GStringPiece, unsigned long>, void*> > >::STLCountingAllocator<std::__1::__hash_value_type<GStringPiece, unsigned long> >(yb::STLCountingAllocator<std::__1::__hash_value_type<GStringPiece, unsigned long>, std::__1::allocator<std::__1::__hash_value_type<GStringPiece, unsigned long> > > const&) Line | Count | Source | 869 | 45.3M | bytes_used_(x.bytes_used()) { | 870 | 45.3M | } |
|
871 | | |
872 | 148M | pointer allocate(size_type n, std::allocator<void>::const_pointer hint = 0) { |
873 | 148M | assert(bytes_used_ != NULL); |
874 | 0 | *bytes_used_ += n * sizeof(T); |
875 | 148M | return Alloc::allocate(n, hint); |
876 | 148M | } yb::STLCountingAllocator<std::__1::__hash_node_base<std::__1::__hash_node<std::__1::__hash_value_type<GStringPiece, unsigned long>, void*>*>*, std::__1::allocator<std::__1::__hash_node_base<std::__1::__hash_node<std::__1::__hash_value_type<GStringPiece, unsigned long>, void*>*>*> >::allocate(unsigned long, void const*) Line | Count | Source | 872 | 47.1M | pointer allocate(size_type n, std::allocator<void>::const_pointer hint = 0) { | 873 | 47.1M | assert(bytes_used_ != NULL); | 874 | 0 | *bytes_used_ += n * sizeof(T); | 875 | 47.1M | return Alloc::allocate(n, hint); | 876 | 47.1M | } |
yb::STLCountingAllocator<std::__1::__hash_node<std::__1::__hash_value_type<GStringPiece, unsigned long>, void*>, std::__1::allocator<std::__1::__hash_node<std::__1::__hash_value_type<GStringPiece, unsigned long>, void*> > >::allocate(unsigned long, void const*) Line | Count | Source | 872 | 101M | pointer allocate(size_type n, std::allocator<void>::const_pointer hint = 0) { | 873 | 101M | assert(bytes_used_ != NULL); | 874 | 0 | *bytes_used_ += n * sizeof(T); | 875 | 101M | return Alloc::allocate(n, hint); | 876 | 101M | } |
|
877 | | |
878 | 138M | void deallocate(pointer p, size_type n) { |
879 | 138M | Alloc::deallocate(p, n); |
880 | 138M | assert(bytes_used_ != NULL); |
881 | 0 | *bytes_used_ -= n * sizeof(T); |
882 | 138M | } yb::STLCountingAllocator<std::__1::__hash_node_base<std::__1::__hash_node<std::__1::__hash_value_type<GStringPiece, unsigned long>, void*>*>*, std::__1::allocator<std::__1::__hash_node_base<std::__1::__hash_node<std::__1::__hash_value_type<GStringPiece, unsigned long>, void*>*>*> >::deallocate(std::__1::__hash_node_base<std::__1::__hash_node<std::__1::__hash_value_type<GStringPiece, unsigned long>, void*>*>**, unsigned long) Line | Count | Source | 878 | 45.6M | void deallocate(pointer p, size_type n) { | 879 | 45.6M | Alloc::deallocate(p, n); | 880 | 45.6M | assert(bytes_used_ != NULL); | 881 | 0 | *bytes_used_ -= n * sizeof(T); | 882 | 45.6M | } |
yb::STLCountingAllocator<std::__1::__hash_node<std::__1::__hash_value_type<GStringPiece, unsigned long>, void*>, std::__1::allocator<std::__1::__hash_node<std::__1::__hash_value_type<GStringPiece, unsigned long>, void*> > >::deallocate(std::__1::__hash_node<std::__1::__hash_value_type<GStringPiece, unsigned long>, void*>*, unsigned long) Line | Count | Source | 878 | 92.5M | void deallocate(pointer p, size_type n) { | 879 | 92.5M | Alloc::deallocate(p, n); | 880 | 92.5M | assert(bytes_used_ != NULL); | 881 | 0 | *bytes_used_ -= n * sizeof(T); | 882 | 92.5M | } |
|
883 | | |
884 | | // Rebind allows an allocator<T> to be used for a different type |
885 | | template <class U> struct rebind { |
886 | | typedef STLCountingAllocator<U, |
887 | | typename Alloc::template |
888 | | rebind<U>::other> other; |
889 | | }; |
890 | | |
891 | 136M | int64* bytes_used() const { return bytes_used_; } yb::STLCountingAllocator<std::__1::pair<GStringPiece const, unsigned long>, std::__1::allocator<std::__1::pair<GStringPiece const, unsigned long> > >::bytes_used() const Line | Count | Source | 891 | 45.4M | int64* bytes_used() const { return bytes_used_; } |
yb::STLCountingAllocator<std::__1::__hash_value_type<GStringPiece, unsigned long>, std::__1::allocator<std::__1::__hash_value_type<GStringPiece, unsigned long> > >::bytes_used() const Line | Count | Source | 891 | 90.7M | int64* bytes_used() const { return bytes_used_; } |
|
892 | | |
893 | | private: |
894 | | int64* bytes_used_; |
895 | | }; |
896 | | |
897 | | // Even though a struct has no data members, it cannot have zero size |
898 | | // according to the standard. However, "empty base-class |
899 | | // optimization" allows an empty parent class to add no additional |
900 | | // size to the object. STLEmptyBaseHandle is a handy way to "stuff" |
901 | | // objects that are typically empty (e.g., allocators, compare |
902 | | // objects) into other fields of an object without increasing the size |
903 | | // of the object. |
904 | | // |
905 | | // struct Empty { |
906 | | // void Method() { } |
907 | | // }; |
908 | | // struct OneInt { |
909 | | // STLEmptyBaseHandle<Empty, int> i; |
910 | | // }; |
911 | | // |
912 | | // In the example above, "i.data" refers to the integer field, whereas |
913 | | // "i" refers to the empty base class. sizeof(OneInt) == sizeof(int) |
914 | | // despite the fact that sizeof(Empty) > 0. |
915 | | template <typename Base, typename Data> |
916 | | struct STLEmptyBaseHandle : public Base { |
917 | | template <typename U> |
918 | | STLEmptyBaseHandle(const U &b, const Data &d) |
919 | | : Base(b), |
920 | | data(d) { |
921 | | } |
922 | | Data data; |
923 | | }; |
924 | | |
925 | | // These functions return true if there is some element in the sorted range |
926 | | // [begin1, end) which is equal to some element in the sorted range [begin2, |
927 | | // end2). The iterators do not have to be of the same type, but the value types |
928 | | // must be less-than comparable. (Two elements a,b are considered equal if |
929 | | // !(a < b) && !(b < a). |
930 | | template<typename InputIterator1, typename InputIterator2> |
931 | | bool SortedRangesHaveIntersection(InputIterator1 begin1, InputIterator1 end1, |
932 | | InputIterator2 begin2, InputIterator2 end2) { |
933 | | assert(std::is_sorted(begin1, end1)); |
934 | | assert(std::is_sorted(begin2, end2)); |
935 | | while (begin1 != end1 && begin2 != end2) { |
936 | | if (*begin1 < *begin2) { |
937 | | ++begin1; |
938 | | } else if (*begin2 < *begin1) { |
939 | | ++begin2; |
940 | | } else { |
941 | | return true; |
942 | | } |
943 | | } |
944 | | return false; |
945 | | } |
946 | | |
947 | | // This is equivalent to the function above, but using a custom comparison |
948 | | // function. |
949 | | template<typename InputIterator1, typename InputIterator2, typename Comp> |
950 | | bool SortedRangesHaveIntersection(InputIterator1 begin1, InputIterator1 end1, |
951 | | InputIterator2 begin2, InputIterator2 end2, |
952 | | Comp comparator) { |
953 | | assert(std::is_sorted(begin1, end1, comparator)); |
954 | | assert(std::is_sorted(begin2, end2, comparator)); |
955 | | while (begin1 != end1 && begin2 != end2) { |
956 | | if (comparator(*begin1, *begin2)) { |
957 | | ++begin1; |
958 | | } else if (comparator(*begin2, *begin1)) { |
959 | | ++begin2; |
960 | | } else { |
961 | | return true; |
962 | | } |
963 | | } |
964 | | return false; |
965 | | } |
966 | | |
967 | | // release_ptr is intended to help remove systematic use of std::unique_ptr |
968 | | // in cases like: |
969 | | // |
970 | | // vector<Foo *> v; |
971 | | // ElementDeleter d(&v); |
972 | | // ... { |
973 | | // int remove_idx = f(v); |
974 | | // std::unique_ptr<Foo> t(v[remove_idx]); |
975 | | // v[remove_idx] = NULL; // Save from deleter. |
976 | | // return t.release(); |
977 | | // } |
978 | | // |
979 | | // This would be replaced by: |
980 | | // ... { |
981 | | // int remove_idx = f(v); |
982 | | // return release_ptr(&v[remove_idx]); |
983 | | // } |
984 | | template<typename T> T* release_ptr(T **ptr) MUST_USE_RESULT; |
985 | | template<typename T> T* release_ptr(T **ptr) { |
986 | | assert(ptr); |
987 | | T *tmp = *ptr; |
988 | | *ptr = NULL; |
989 | | return tmp; |
990 | | } |
991 | | |
992 | | template<typename T> |
993 | | std::set<T> VectorToSet(const std::vector<T>& v) { |
994 | | return std::set<T>(v.begin(), v.end()); |
995 | | } |
996 | | |
997 | | template <class Predicate, class Collection> |
998 | 404k | void EraseIf(const Predicate& predicate, Collection* collection) { |
999 | 404k | collection->erase(std::remove_if(collection->begin(), collection->end(), predicate), |
1000 | 404k | collection->end()); |
1001 | 404k | } catalog_manager.cc:void yb::EraseIf<yb::master::CatalogManager::GetTables(yb::master::GetTablesMode)::$_11, std::__1::vector<scoped_refptr<yb::master::TableInfo>, std::__1::allocator<scoped_refptr<yb::master::TableInfo> > > >(yb::master::CatalogManager::GetTables(yb::master::GetTablesMode)::$_11 const&, std::__1::vector<scoped_refptr<yb::master::TableInfo>, std::__1::allocator<scoped_refptr<yb::master::TableInfo> > >*) Line | Count | Source | 998 | 160 | void EraseIf(const Predicate& predicate, Collection* collection) { | 999 | 160 | collection->erase(std::remove_if(collection->begin(), collection->end(), predicate), | 1000 | 160 | collection->end()); | 1001 | 160 | } |
catalog_manager.cc:void yb::EraseIf<yb::master::CatalogManager::GetTables(yb::master::GetTablesMode)::$_12, std::__1::vector<scoped_refptr<yb::master::TableInfo>, std::__1::allocator<scoped_refptr<yb::master::TableInfo> > > >(yb::master::CatalogManager::GetTables(yb::master::GetTablesMode)::$_12 const&, std::__1::vector<scoped_refptr<yb::master::TableInfo>, std::__1::allocator<scoped_refptr<yb::master::TableInfo> > >*) Line | Count | Source | 998 | 47.4k | void EraseIf(const Predicate& predicate, Collection* collection) { | 999 | 47.4k | collection->erase(std::remove_if(collection->begin(), collection->end(), predicate), | 1000 | 47.4k | collection->end()); | 1001 | 47.4k | } |
catalog_manager_ent.cc:void yb::EraseIf<yb::master::enterprise::CatalogManager::CleanupHiddenTables(std::__1::vector<scoped_refptr<yb::master::TableInfo>, std::__1::allocator<scoped_refptr<yb::master::TableInfo> > >)::$_4, std::__1::vector<scoped_refptr<yb::master::TableInfo>, std::__1::allocator<scoped_refptr<yb::master::TableInfo> > > >(yb::master::enterprise::CatalogManager::CleanupHiddenTables(std::__1::vector<scoped_refptr<yb::master::TableInfo>, std::__1::allocator<scoped_refptr<yb::master::TableInfo> > >)::$_4 const&, std::__1::vector<scoped_refptr<yb::master::TableInfo>, std::__1::allocator<scoped_refptr<yb::master::TableInfo> > >*) Line | Count | Source | 998 | 310k | void EraseIf(const Predicate& predicate, Collection* collection) { | 999 | 310k | collection->erase(std::remove_if(collection->begin(), collection->end(), predicate), | 1000 | 310k | collection->end()); | 1001 | 310k | } |
batcher.cc:void yb::EraseIf<yb::client::internal::Batcher::AllLookupsDone()::$_0, std::__1::vector<yb::client::internal::InFlightOp, std::__1::allocator<yb::client::internal::InFlightOp> > >(yb::client::internal::Batcher::AllLookupsDone()::$_0 const&, std::__1::vector<yb::client::internal::InFlightOp, std::__1::allocator<yb::client::internal::InFlightOp> >*) Line | Count | Source | 998 | 170 | void EraseIf(const Predicate& predicate, Collection* collection) { | 999 | 170 | collection->erase(std::remove_if(collection->begin(), collection->end(), predicate), | 1000 | 170 | collection->end()); | 1001 | 170 | } |
compaction.cc:void yb::EraseIf<rocksdb::Compaction::Create(rocksdb::VersionStorageInfo*, rocksdb::MutableCFOptions const&, std::__1::vector<rocksdb::CompactionInputFiles, std::__1::allocator<rocksdb::CompactionInputFiles> >, int, unsigned long long, unsigned long long, unsigned int, rocksdb::CompressionType, std::__1::vector<rocksdb::FileMetaData*, std::__1::allocator<rocksdb::FileMetaData*> >, rocksdb::Logger*, bool, double, bool, rocksdb::CompactionReason)::$_0, std::__1::vector<rocksdb::FileMetaData*, std::__1::allocator<rocksdb::FileMetaData*> > >(rocksdb::Compaction::Create(rocksdb::VersionStorageInfo*, rocksdb::MutableCFOptions const&, std::__1::vector<rocksdb::CompactionInputFiles, std::__1::allocator<rocksdb::CompactionInputFiles> >, int, unsigned long long, unsigned long long, unsigned int, rocksdb::CompressionType, std::__1::vector<rocksdb::FileMetaData*, std::__1::allocator<rocksdb::FileMetaData*> >, rocksdb::Logger*, bool, double, bool, rocksdb::CompactionReason)::$_0 const&, std::__1::vector<rocksdb::FileMetaData*, std::__1::allocator<rocksdb::FileMetaData*> >*) Line | Count | Source | 998 | 46.2k | void EraseIf(const Predicate& predicate, Collection* collection) { | 999 | 46.2k | collection->erase(std::remove_if(collection->begin(), collection->end(), predicate), | 1000 | 46.2k | collection->end()); | 1001 | 46.2k | } |
|
1002 | | |
1003 | | template <class Value, class Collection> |
1004 | 30 | bool Erase(const Value& value, Collection* collection) { |
1005 | 30 | auto it = std::find(collection->begin(), collection->end(), value); |
1006 | 30 | if (it == collection->end()) { |
1007 | 3 | return false; |
1008 | 3 | } |
1009 | | |
1010 | 27 | collection->erase(it); |
1011 | 27 | return true; |
1012 | 30 | } |
1013 | | |
1014 | | template <class Collection1, class Collection2> |
1015 | 6.61k | void MoveCollection(Collection1* source, Collection2* destination) { |
1016 | 6.61k | destination->reserve(destination->size() + source->size()); |
1017 | 6.61k | std::move(source->begin(), source->end(), std::back_inserter(*destination)); |
1018 | 6.61k | } |
1019 | | |
1020 | | template <class Collection> |
1021 | 0 | void Unique(Collection* collection) { |
1022 | 0 | collection->erase(std::unique(collection->begin(), collection->end()), collection->end()); |
1023 | 0 | } |
1024 | | |
1025 | | } // namespace yb |
1026 | | |
1027 | | // For backward compatibility |
1028 | | using yb::STLAppendToString; |
1029 | | using yb::STLAssignToString; |
1030 | | using yb::STLStringResizeUninitialized; |
1031 | | using yb::string_as_array; |
1032 | | |
1033 | | #endif // YB_GUTIL_STL_UTIL_H |