Line data Source code
1 : // Protocol Buffers - Google's data interchange format
2 : // Copyright 2014 Google Inc. All rights reserved.
3 : // https://developers.google.com/protocol-buffers/
4 : //
5 : // Redistribution and use in source and binary forms, with or without
6 : // modification, are permitted provided that the following conditions are
7 : // met:
8 : //
9 : // * Redistributions of source code must retain the above copyright
10 : // notice, this list of conditions and the following disclaimer.
11 : // * Redistributions in binary form must reproduce the above
12 : // copyright notice, this list of conditions and the following disclaimer
13 : // in the documentation and/or other materials provided with the
14 : // distribution.
15 : // * Neither the name of Google Inc. nor the names of its
16 : // contributors may be used to endorse or promote products derived from
17 : // this software without specific prior written permission.
18 : //
19 : // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 : // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 : // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 : // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 : // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 : // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 : // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 : // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 : // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 : // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 : // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 :
31 : // from google3/util/gtl/map_util.h
32 : // Author: Anton Carver
33 :
34 : #ifndef GOOGLE_PROTOBUF_STUBS_MAP_UTIL_H__
35 : #define GOOGLE_PROTOBUF_STUBS_MAP_UTIL_H__
36 :
37 : #include <stddef.h>
38 : #include <iterator>
39 : #include <string>
40 : #include <utility>
41 : #include <vector>
42 :
43 : #include <google/protobuf/stubs/common.h>
44 :
45 : namespace google {
46 : namespace protobuf {
47 : namespace internal {
48 : // Local implementation of RemoveConst to avoid including base/type_traits.h.
49 : template <class T> struct RemoveConst { typedef T type; };
50 : template <class T> struct RemoveConst<const T> : RemoveConst<T> {};
51 : } // namespace internal
52 :
53 : //
54 : // Find*()
55 : //
56 :
57 : // Returns a const reference to the value associated with the given key if it
58 : // exists. Crashes otherwise.
59 : //
60 : // This is intended as a replacement for operator[] as an rvalue (for reading)
61 : // when the key is guaranteed to exist.
62 : //
63 : // operator[] for lookup is discouraged for several reasons:
64 : // * It has a side-effect of inserting missing keys
65 : // * It is not thread-safe (even when it is not inserting, it can still
66 : // choose to resize the underlying storage)
67 : // * It invalidates iterators (when it chooses to resize)
68 : // * It default constructs a value object even if it doesn't need to
69 : //
70 : // This version assumes the key is printable, and includes it in the fatal log
71 : // message.
72 : template <class Collection>
73 : const typename Collection::value_type::second_type&
74 : FindOrDie(const Collection& collection,
75 : const typename Collection::value_type::first_type& key) {
76 : typename Collection::const_iterator it = collection.find(key);
77 : GOOGLE_CHECK(it != collection.end()) << "Map key not found: " << key;
78 : return it->second;
79 : }
80 :
81 : // Same as above, but returns a non-const reference.
82 : template <class Collection>
83 : typename Collection::value_type::second_type&
84 : FindOrDie(Collection& collection, // NOLINT
85 : const typename Collection::value_type::first_type& key) {
86 : typename Collection::iterator it = collection.find(key);
87 : GOOGLE_CHECK(it != collection.end()) << "Map key not found: " << key;
88 : return it->second;
89 : }
90 :
91 : // Same as FindOrDie above, but doesn't log the key on failure.
92 : template <class Collection>
93 : const typename Collection::value_type::second_type&
94 : FindOrDieNoPrint(const Collection& collection,
95 : const typename Collection::value_type::first_type& key) {
96 : typename Collection::const_iterator it = collection.find(key);
97 : GOOGLE_CHECK(it != collection.end()) << "Map key not found";
98 : return it->second;
99 : }
100 :
101 : // Same as above, but returns a non-const reference.
102 : template <class Collection>
103 : typename Collection::value_type::second_type&
104 : FindOrDieNoPrint(Collection& collection, // NOLINT
105 : const typename Collection::value_type::first_type& key) {
106 : typename Collection::iterator it = collection.find(key);
107 : GOOGLE_CHECK(it != collection.end()) << "Map key not found";
108 : return it->second;
109 : }
110 :
111 : // Returns a const reference to the value associated with the given key if it
112 : // exists, otherwise returns a const reference to the provided default value.
113 : //
114 : // WARNING: If a temporary object is passed as the default "value,"
115 : // this function will return a reference to that temporary object,
116 : // which will be destroyed at the end of the statement. A common
117 : // example: if you have a map with string values, and you pass a char*
118 : // as the default "value," either use the returned value immediately
119 : // or store it in a string (not string&).
120 : // Details: http://go/findwithdefault
121 : template <class Collection>
122 : const typename Collection::value_type::second_type&
123 0 : FindWithDefault(const Collection& collection,
124 : const typename Collection::value_type::first_type& key,
125 : const typename Collection::value_type::second_type& value) {
126 0 : typename Collection::const_iterator it = collection.find(key);
127 0 : if (it == collection.end()) {
128 0 : return value;
129 : }
130 0 : return it->second;
131 : }
132 :
133 : // Returns a pointer to the const value associated with the given key if it
134 : // exists, or NULL otherwise.
135 : template <class Collection>
136 : const typename Collection::value_type::second_type*
137 0 : FindOrNull(const Collection& collection,
138 : const typename Collection::value_type::first_type& key) {
139 0 : typename Collection::const_iterator it = collection.find(key);
140 0 : if (it == collection.end()) {
141 0 : return 0;
142 : }
143 0 : return &it->second;
144 : }
145 :
146 : // Same as above but returns a pointer to the non-const value.
147 : template <class Collection>
148 : typename Collection::value_type::second_type*
149 0 : FindOrNull(Collection& collection, // NOLINT
150 : const typename Collection::value_type::first_type& key) {
151 0 : typename Collection::iterator it = collection.find(key);
152 0 : if (it == collection.end()) {
153 0 : return 0;
154 : }
155 0 : return &it->second;
156 : }
157 :
158 : // Returns the pointer value associated with the given key. If none is found,
159 : // NULL is returned. The function is designed to be used with a map of keys to
160 : // pointers.
161 : //
162 : // This function does not distinguish between a missing key and a key mapped
163 : // to a NULL value.
164 : template <class Collection>
165 : typename Collection::value_type::second_type
166 0 : FindPtrOrNull(const Collection& collection,
167 : const typename Collection::value_type::first_type& key) {
168 0 : typename Collection::const_iterator it = collection.find(key);
169 0 : if (it == collection.end()) {
170 0 : return typename Collection::value_type::second_type();
171 : }
172 0 : return it->second;
173 : }
174 :
175 : // Same as above, except takes non-const reference to collection.
176 : //
177 : // This function is needed for containers that propagate constness to the
178 : // pointee, such as boost::ptr_map.
179 : template <class Collection>
180 : typename Collection::value_type::second_type
181 0 : FindPtrOrNull(Collection& collection, // NOLINT
182 : const typename Collection::value_type::first_type& key) {
183 0 : typename Collection::iterator it = collection.find(key);
184 0 : if (it == collection.end()) {
185 0 : return typename Collection::value_type::second_type();
186 : }
187 0 : return it->second;
188 : }
189 :
190 : // Finds the pointer value associated with the given key in a map whose values
191 : // are linked_ptrs. Returns NULL if key is not found.
192 : template <class Collection>
193 : typename Collection::value_type::second_type::element_type*
194 : FindLinkedPtrOrNull(const Collection& collection,
195 : const typename Collection::value_type::first_type& key) {
196 : typename Collection::const_iterator it = collection.find(key);
197 : if (it == collection.end()) {
198 : return 0;
199 : }
200 : // Since linked_ptr::get() is a const member returning a non const,
201 : // we do not need a version of this function taking a non const collection.
202 : return it->second.get();
203 : }
204 :
205 : // Same as above, but dies if the key is not found.
206 : template <class Collection>
207 : typename Collection::value_type::second_type::element_type&
208 : FindLinkedPtrOrDie(const Collection& collection,
209 : const typename Collection::value_type::first_type& key) {
210 : typename Collection::const_iterator it = collection.find(key);
211 : CHECK(it != collection.end()) << "key not found: " << key;
212 : // Since linked_ptr::operator*() is a const member returning a non const,
213 : // we do not need a version of this function taking a non const collection.
214 : return *it->second;
215 : }
216 :
217 : // Finds the value associated with the given key and copies it to *value (if not
218 : // NULL). Returns false if the key was not found, true otherwise.
219 : template <class Collection, class Key, class Value>
220 : bool FindCopy(const Collection& collection,
221 : const Key& key,
222 : Value* const value) {
223 : typename Collection::const_iterator it = collection.find(key);
224 : if (it == collection.end()) {
225 : return false;
226 : }
227 : if (value) {
228 : *value = it->second;
229 : }
230 : return true;
231 : }
232 :
233 : //
234 : // Contains*()
235 : //
236 :
237 : // Returns true if and only if the given collection contains the given key.
238 : template <class Collection, class Key>
239 : bool ContainsKey(const Collection& collection, const Key& key) {
240 : return collection.find(key) != collection.end();
241 : }
242 :
243 : // Returns true if and only if the given collection contains the given key-value
244 : // pair.
245 : template <class Collection, class Key, class Value>
246 : bool ContainsKeyValuePair(const Collection& collection,
247 : const Key& key,
248 : const Value& value) {
249 : typedef typename Collection::const_iterator const_iterator;
250 : std::pair<const_iterator, const_iterator> range = collection.equal_range(key);
251 : for (const_iterator it = range.first; it != range.second; ++it) {
252 : if (it->second == value) {
253 : return true;
254 : }
255 : }
256 : return false;
257 : }
258 :
259 : //
260 : // Insert*()
261 : //
262 :
263 : // Inserts the given key-value pair into the collection. Returns true if and
264 : // only if the key from the given pair didn't previously exist. Otherwise, the
265 : // value in the map is replaced with the value from the given pair.
266 : template <class Collection>
267 : bool InsertOrUpdate(Collection* const collection,
268 : const typename Collection::value_type& vt) {
269 : std::pair<typename Collection::iterator, bool> ret = collection->insert(vt);
270 : if (!ret.second) {
271 : // update
272 : ret.first->second = vt.second;
273 : return false;
274 : }
275 : return true;
276 : }
277 :
278 : // Same as above, except that the key and value are passed separately.
279 : template <class Collection>
280 : bool InsertOrUpdate(Collection* const collection,
281 : const typename Collection::value_type::first_type& key,
282 : const typename Collection::value_type::second_type& value) {
283 : return InsertOrUpdate(
284 : collection, typename Collection::value_type(key, value));
285 : }
286 :
287 : // Inserts/updates all the key-value pairs from the range defined by the
288 : // iterators "first" and "last" into the given collection.
289 : template <class Collection, class InputIterator>
290 : void InsertOrUpdateMany(Collection* const collection,
291 : InputIterator first, InputIterator last) {
292 : for (; first != last; ++first) {
293 : InsertOrUpdate(collection, *first);
294 : }
295 : }
296 :
297 : // Change the value associated with a particular key in a map or hash_map
298 : // of the form map<Key, Value*> which owns the objects pointed to by the
299 : // value pointers. If there was an existing value for the key, it is deleted.
300 : // True indicates an insert took place, false indicates an update + delete.
301 : template <class Collection>
302 : bool InsertAndDeleteExisting(
303 : Collection* const collection,
304 : const typename Collection::value_type::first_type& key,
305 : const typename Collection::value_type::second_type& value) {
306 : std::pair<typename Collection::iterator, bool> ret =
307 : collection->insert(typename Collection::value_type(key, value));
308 : if (!ret.second) {
309 : delete ret.first->second;
310 : ret.first->second = value;
311 : return false;
312 : }
313 : return true;
314 : }
315 :
316 : // Inserts the given key and value into the given collection if and only if the
317 : // given key did NOT already exist in the collection. If the key previously
318 : // existed in the collection, the value is not changed. Returns true if the
319 : // key-value pair was inserted; returns false if the key was already present.
320 : template <class Collection>
321 12 : bool InsertIfNotPresent(Collection* const collection,
322 : const typename Collection::value_type& vt) {
323 12 : return collection->insert(vt).second;
324 : }
325 :
326 : // Same as above except the key and value are passed separately.
327 : template <class Collection>
328 12 : bool InsertIfNotPresent(
329 : Collection* const collection,
330 : const typename Collection::value_type::first_type& key,
331 : const typename Collection::value_type::second_type& value) {
332 24 : return InsertIfNotPresent(
333 24 : collection, typename Collection::value_type(key, value));
334 : }
335 :
336 : // Same as above except dies if the key already exists in the collection.
337 : template <class Collection>
338 : void InsertOrDie(Collection* const collection,
339 : const typename Collection::value_type& value) {
340 : CHECK(InsertIfNotPresent(collection, value)) << "duplicate value: " << value;
341 : }
342 :
343 : // Same as above except doesn't log the value on error.
344 : template <class Collection>
345 : void InsertOrDieNoPrint(Collection* const collection,
346 : const typename Collection::value_type& value) {
347 : CHECK(InsertIfNotPresent(collection, value)) << "duplicate value.";
348 : }
349 :
350 : // Inserts the key-value pair into the collection. Dies if key was already
351 : // present.
352 : template <class Collection>
353 : void InsertOrDie(Collection* const collection,
354 : const typename Collection::value_type::first_type& key,
355 : const typename Collection::value_type::second_type& data) {
356 : typedef typename Collection::value_type value_type;
357 : GOOGLE_CHECK(InsertIfNotPresent(collection, key, data))
358 : << "duplicate key: " << key;
359 : }
360 :
361 : // Same as above except doesn't log the key on error.
362 : template <class Collection>
363 : void InsertOrDieNoPrint(
364 : Collection* const collection,
365 : const typename Collection::value_type::first_type& key,
366 : const typename Collection::value_type::second_type& data) {
367 : typedef typename Collection::value_type value_type;
368 : GOOGLE_CHECK(InsertIfNotPresent(collection, key, data)) << "duplicate key.";
369 : }
370 :
371 : // Inserts a new key and default-initialized value. Dies if the key was already
372 : // present. Returns a reference to the value. Example usage:
373 : //
374 : // map<int, SomeProto> m;
375 : // SomeProto& proto = InsertKeyOrDie(&m, 3);
376 : // proto.set_field("foo");
377 : template <class Collection>
378 : typename Collection::value_type::second_type& InsertKeyOrDie(
379 : Collection* const collection,
380 : const typename Collection::value_type::first_type& key) {
381 : typedef typename Collection::value_type value_type;
382 : std::pair<typename Collection::iterator, bool> res =
383 : collection->insert(value_type(key, typename value_type::second_type()));
384 : GOOGLE_CHECK(res.second) << "duplicate key: " << key;
385 : return res.first->second;
386 : }
387 :
388 : //
389 : // Lookup*()
390 : //
391 :
392 : // Looks up a given key and value pair in a collection and inserts the key-value
393 : // pair if it's not already present. Returns a reference to the value associated
394 : // with the key.
395 : template <class Collection>
396 : typename Collection::value_type::second_type&
397 : LookupOrInsert(Collection* const collection,
398 : const typename Collection::value_type& vt) {
399 : return collection->insert(vt).first->second;
400 : }
401 :
402 : // Same as above except the key-value are passed separately.
403 : template <class Collection>
404 : typename Collection::value_type::second_type&
405 : LookupOrInsert(Collection* const collection,
406 : const typename Collection::value_type::first_type& key,
407 : const typename Collection::value_type::second_type& value) {
408 : return LookupOrInsert(
409 : collection, typename Collection::value_type(key, value));
410 : }
411 :
412 : // Counts the number of equivalent elements in the given "sequence", and stores
413 : // the results in "count_map" with element as the key and count as the value.
414 : //
415 : // Example:
416 : // vector<string> v = {"a", "b", "c", "a", "b"};
417 : // map<string, int> m;
418 : // AddTokenCounts(v, 1, &m);
419 : // assert(m["a"] == 2);
420 : // assert(m["b"] == 2);
421 : // assert(m["c"] == 1);
422 : template <typename Sequence, typename Collection>
423 : void AddTokenCounts(
424 : const Sequence& sequence,
425 : const typename Collection::value_type::second_type& increment,
426 : Collection* const count_map) {
427 : for (typename Sequence::const_iterator it = sequence.begin();
428 : it != sequence.end(); ++it) {
429 : typename Collection::value_type::second_type& value =
430 : LookupOrInsert(count_map, *it,
431 : typename Collection::value_type::second_type());
432 : value += increment;
433 : }
434 : }
435 :
436 : // Returns a reference to the value associated with key. If not found, a value
437 : // is default constructed on the heap and added to the map.
438 : //
439 : // This function is useful for containers of the form map<Key, Value*>, where
440 : // inserting a new key, value pair involves constructing a new heap-allocated
441 : // Value, and storing a pointer to that in the collection.
442 : template <class Collection>
443 : typename Collection::value_type::second_type&
444 : LookupOrInsertNew(Collection* const collection,
445 : const typename Collection::value_type::first_type& key) {
446 : typedef typename std::iterator_traits<
447 : typename Collection::value_type::second_type>::value_type Element;
448 : std::pair<typename Collection::iterator, bool> ret =
449 : collection->insert(typename Collection::value_type(
450 : key,
451 : static_cast<typename Collection::value_type::second_type>(NULL)));
452 : if (ret.second) {
453 : ret.first->second = new Element();
454 : }
455 : return ret.first->second;
456 : }
457 :
458 : // Same as above but constructs the value using the single-argument constructor
459 : // and the given "arg".
460 : template <class Collection, class Arg>
461 : typename Collection::value_type::second_type&
462 : LookupOrInsertNew(Collection* const collection,
463 : const typename Collection::value_type::first_type& key,
464 : const Arg& arg) {
465 : typedef typename std::iterator_traits<
466 : typename Collection::value_type::second_type>::value_type Element;
467 : std::pair<typename Collection::iterator, bool> ret =
468 : collection->insert(typename Collection::value_type(
469 : key,
470 : static_cast<typename Collection::value_type::second_type>(NULL)));
471 : if (ret.second) {
472 : ret.first->second = new Element(arg);
473 : }
474 : return ret.first->second;
475 : }
476 :
477 : // Lookup of linked/shared pointers is used in two scenarios:
478 : //
479 : // Use LookupOrInsertNewLinkedPtr if the container owns the elements.
480 : // In this case it is fine working with the raw pointer as long as it is
481 : // guaranteed that no other thread can delete/update an accessed element.
482 : // A mutex will need to lock the container operation as well as the use
483 : // of the returned elements. Finding an element may be performed using
484 : // FindLinkedPtr*().
485 : //
486 : // Use LookupOrInsertNewSharedPtr if the container does not own the elements
487 : // for their whole lifetime. This is typically the case when a reader allows
488 : // parallel updates to the container. In this case a Mutex only needs to lock
489 : // container operations, but all element operations must be performed on the
490 : // shared pointer. Finding an element must be performed using FindPtr*() and
491 : // cannot be done with FindLinkedPtr*() even though it compiles.
492 :
493 : // Lookup a key in a map or hash_map whose values are linked_ptrs. If it is
494 : // missing, set collection[key].reset(new Value::element_type) and return that.
495 : // Value::element_type must be default constructable.
496 : template <class Collection>
497 : typename Collection::value_type::second_type::element_type*
498 : LookupOrInsertNewLinkedPtr(
499 : Collection* const collection,
500 : const typename Collection::value_type::first_type& key) {
501 : typedef typename Collection::value_type::second_type Value;
502 : std::pair<typename Collection::iterator, bool> ret =
503 : collection->insert(typename Collection::value_type(key, Value()));
504 : if (ret.second) {
505 : ret.first->second.reset(new typename Value::element_type);
506 : }
507 : return ret.first->second.get();
508 : }
509 :
510 : // A variant of LookupOrInsertNewLinkedPtr where the value is constructed using
511 : // a single-parameter constructor. Note: the constructor argument is computed
512 : // even if it will not be used, so only values cheap to compute should be passed
513 : // here. On the other hand it does not matter how expensive the construction of
514 : // the actual stored value is, as that only occurs if necessary.
515 : template <class Collection, class Arg>
516 : typename Collection::value_type::second_type::element_type*
517 : LookupOrInsertNewLinkedPtr(
518 : Collection* const collection,
519 : const typename Collection::value_type::first_type& key,
520 : const Arg& arg) {
521 : typedef typename Collection::value_type::second_type Value;
522 : std::pair<typename Collection::iterator, bool> ret =
523 : collection->insert(typename Collection::value_type(key, Value()));
524 : if (ret.second) {
525 : ret.first->second.reset(new typename Value::element_type(arg));
526 : }
527 : return ret.first->second.get();
528 : }
529 :
530 : // Lookup a key in a map or hash_map whose values are shared_ptrs. If it is
531 : // missing, set collection[key].reset(new Value::element_type). Unlike
532 : // LookupOrInsertNewLinkedPtr, this function returns the shared_ptr instead of
533 : // the raw pointer. Value::element_type must be default constructable.
534 : template <class Collection>
535 : typename Collection::value_type::second_type&
536 : LookupOrInsertNewSharedPtr(
537 : Collection* const collection,
538 : const typename Collection::value_type::first_type& key) {
539 : typedef typename Collection::value_type::second_type SharedPtr;
540 : typedef typename Collection::value_type::second_type::element_type Element;
541 : std::pair<typename Collection::iterator, bool> ret =
542 : collection->insert(typename Collection::value_type(key, SharedPtr()));
543 : if (ret.second) {
544 : ret.first->second.reset(new Element());
545 : }
546 : return ret.first->second;
547 : }
548 :
549 : // A variant of LookupOrInsertNewSharedPtr where the value is constructed using
550 : // a single-parameter constructor. Note: the constructor argument is computed
551 : // even if it will not be used, so only values cheap to compute should be passed
552 : // here. On the other hand it does not matter how expensive the construction of
553 : // the actual stored value is, as that only occurs if necessary.
554 : template <class Collection, class Arg>
555 : typename Collection::value_type::second_type&
556 : LookupOrInsertNewSharedPtr(
557 : Collection* const collection,
558 : const typename Collection::value_type::first_type& key,
559 : const Arg& arg) {
560 : typedef typename Collection::value_type::second_type SharedPtr;
561 : typedef typename Collection::value_type::second_type::element_type Element;
562 : std::pair<typename Collection::iterator, bool> ret =
563 : collection->insert(typename Collection::value_type(key, SharedPtr()));
564 : if (ret.second) {
565 : ret.first->second.reset(new Element(arg));
566 : }
567 : return ret.first->second;
568 : }
569 :
570 : //
571 : // Misc Utility Functions
572 : //
573 :
574 : // Updates the value associated with the given key. If the key was not already
575 : // present, then the key-value pair are inserted and "previous" is unchanged. If
576 : // the key was already present, the value is updated and "*previous" will
577 : // contain a copy of the old value.
578 : //
579 : // InsertOrReturnExisting has complementary behavior that returns the
580 : // address of an already existing value, rather than updating it.
581 : template <class Collection>
582 : bool UpdateReturnCopy(Collection* const collection,
583 : const typename Collection::value_type::first_type& key,
584 : const typename Collection::value_type::second_type& value,
585 : typename Collection::value_type::second_type* previous) {
586 : std::pair<typename Collection::iterator, bool> ret =
587 : collection->insert(typename Collection::value_type(key, value));
588 : if (!ret.second) {
589 : // update
590 : if (previous) {
591 : *previous = ret.first->second;
592 : }
593 : ret.first->second = value;
594 : return true;
595 : }
596 : return false;
597 : }
598 :
599 : // Same as above except that the key and value are passed as a pair.
600 : template <class Collection>
601 : bool UpdateReturnCopy(Collection* const collection,
602 : const typename Collection::value_type& vt,
603 : typename Collection::value_type::second_type* previous) {
604 : std::pair<typename Collection::iterator, bool> ret = collection->insert(vt);
605 : if (!ret.second) {
606 : // update
607 : if (previous) {
608 : *previous = ret.first->second;
609 : }
610 : ret.first->second = vt.second;
611 : return true;
612 : }
613 : return false;
614 : }
615 :
616 : // Tries to insert the given key-value pair into the collection. Returns NULL if
617 : // the insert succeeds. Otherwise, returns a pointer to the existing value.
618 : //
619 : // This complements UpdateReturnCopy in that it allows to update only after
620 : // verifying the old value and still insert quickly without having to look up
621 : // twice. Unlike UpdateReturnCopy this also does not come with the issue of an
622 : // undefined previous* in case new data was inserted.
623 : template <class Collection>
624 : typename Collection::value_type::second_type* const
625 : InsertOrReturnExisting(Collection* const collection,
626 : const typename Collection::value_type& vt) {
627 : std::pair<typename Collection::iterator, bool> ret = collection->insert(vt);
628 : if (ret.second) {
629 : return NULL; // Inserted, no existing previous value.
630 : } else {
631 : return &ret.first->second; // Return address of already existing value.
632 : }
633 : }
634 :
635 : // Same as above, except for explicit key and data.
636 : template <class Collection>
637 : typename Collection::value_type::second_type* const
638 : InsertOrReturnExisting(
639 : Collection* const collection,
640 : const typename Collection::value_type::first_type& key,
641 : const typename Collection::value_type::second_type& data) {
642 : return InsertOrReturnExisting(collection,
643 : typename Collection::value_type(key, data));
644 : }
645 :
646 : // Erases the collection item identified by the given key, and returns the value
647 : // associated with that key. It is assumed that the value (i.e., the
648 : // mapped_type) is a pointer. Returns NULL if the key was not found in the
649 : // collection.
650 : //
651 : // Examples:
652 : // map<string, MyType*> my_map;
653 : //
654 : // One line cleanup:
655 : // delete EraseKeyReturnValuePtr(&my_map, "abc");
656 : //
657 : // Use returned value:
658 : // scoped_ptr<MyType> value_ptr(EraseKeyReturnValuePtr(&my_map, "abc"));
659 : // if (value_ptr.get())
660 : // value_ptr->DoSomething();
661 : //
662 : template <class Collection>
663 : typename Collection::value_type::second_type EraseKeyReturnValuePtr(
664 : Collection* const collection,
665 : const typename Collection::value_type::first_type& key) {
666 : typename Collection::iterator it = collection->find(key);
667 : if (it == collection->end()) {
668 : return NULL;
669 : }
670 : typename Collection::value_type::second_type v = it->second;
671 : collection->erase(it);
672 : return v;
673 : }
674 :
675 : // Inserts all the keys from map_container into key_container, which must
676 : // support insert(MapContainer::key_type).
677 : //
678 : // Note: any initial contents of the key_container are not cleared.
679 : template <class MapContainer, class KeyContainer>
680 : void InsertKeysFromMap(const MapContainer& map_container,
681 : KeyContainer* key_container) {
682 : GOOGLE_CHECK(key_container != NULL);
683 : for (typename MapContainer::const_iterator it = map_container.begin();
684 : it != map_container.end(); ++it) {
685 : key_container->insert(it->first);
686 : }
687 : }
688 :
689 : // Appends all the keys from map_container into key_container, which must
690 : // support push_back(MapContainer::key_type).
691 : //
692 : // Note: any initial contents of the key_container are not cleared.
693 : template <class MapContainer, class KeyContainer>
694 : void AppendKeysFromMap(const MapContainer& map_container,
695 : KeyContainer* key_container) {
696 : GOOGLE_CHECK(key_container != NULL);
697 : for (typename MapContainer::const_iterator it = map_container.begin();
698 : it != map_container.end(); ++it) {
699 : key_container->push_back(it->first);
700 : }
701 : }
702 :
703 : // A more specialized overload of AppendKeysFromMap to optimize reallocations
704 : // for the common case in which we're appending keys to a vector and hence can
705 : // (and sometimes should) call reserve() first.
706 : //
707 : // (It would be possible to play SFINAE games to call reserve() for any
708 : // container that supports it, but this seems to get us 99% of what we need
709 : // without the complexity of a SFINAE-based solution.)
710 : template <class MapContainer, class KeyType>
711 : void AppendKeysFromMap(const MapContainer& map_container,
712 : vector<KeyType>* key_container) {
713 : GOOGLE_CHECK(key_container != NULL);
714 : // We now have the opportunity to call reserve(). Calling reserve() every
715 : // time is a bad idea for some use cases: libstdc++'s implementation of
716 : // vector<>::reserve() resizes the vector's backing store to exactly the
717 : // given size (unless it's already at least that big). Because of this,
718 : // the use case that involves appending a lot of small maps (total size
719 : // N) one by one to a vector would be O(N^2). But never calling reserve()
720 : // loses the opportunity to improve the use case of adding from a large
721 : // map to an empty vector (this improves performance by up to 33%). A
722 : // number of heuristics are possible; see the discussion in
723 : // cl/34081696. Here we use the simplest one.
724 : if (key_container->empty()) {
725 : key_container->reserve(map_container.size());
726 : }
727 : for (typename MapContainer::const_iterator it = map_container.begin();
728 : it != map_container.end(); ++it) {
729 : key_container->push_back(it->first);
730 : }
731 : }
732 :
733 : // Inserts all the values from map_container into value_container, which must
734 : // support push_back(MapContainer::mapped_type).
735 : //
736 : // Note: any initial contents of the value_container are not cleared.
737 : template <class MapContainer, class ValueContainer>
738 : void AppendValuesFromMap(const MapContainer& map_container,
739 : ValueContainer* value_container) {
740 : GOOGLE_CHECK(value_container != NULL);
741 : for (typename MapContainer::const_iterator it = map_container.begin();
742 : it != map_container.end(); ++it) {
743 : value_container->push_back(it->second);
744 : }
745 : }
746 :
747 : // A more specialized overload of AppendValuesFromMap to optimize reallocations
748 : // for the common case in which we're appending values to a vector and hence
749 : // can (and sometimes should) call reserve() first.
750 : //
751 : // (It would be possible to play SFINAE games to call reserve() for any
752 : // container that supports it, but this seems to get us 99% of what we need
753 : // without the complexity of a SFINAE-based solution.)
754 : template <class MapContainer, class ValueType>
755 : void AppendValuesFromMap(const MapContainer& map_container,
756 : vector<ValueType>* value_container) {
757 : GOOGLE_CHECK(value_container != NULL);
758 : // See AppendKeysFromMap for why this is done.
759 : if (value_container->empty()) {
760 : value_container->reserve(map_container.size());
761 : }
762 : for (typename MapContainer::const_iterator it = map_container.begin();
763 : it != map_container.end(); ++it) {
764 : value_container->push_back(it->second);
765 : }
766 : }
767 :
768 : } // namespace protobuf
769 : } // namespace google
770 :
771 : #endif // GOOGLE_PROTOBUF_STUBS_MAP_UTIL_H__
|
