From c551f43206405019121bd2b2c93714319a0a3300 Mon Sep 17 00:00:00 2001 From: Allan Sandfeld Jensen Date: Thu, 23 Jan 2020 17:21:03 +0100 Subject: BASELINE: Update Chromium to 79.0.3945.139 Change-Id: I336b7182fab9bca80b709682489c07db112eaca5 Reviewed-by: Allan Sandfeld Jensen --- chromium/base/containers/flat_tree.h | 125 +++++++---------------------------- 1 file changed, 24 insertions(+), 101 deletions(-) (limited to 'chromium/base/containers/flat_tree.h') diff --git a/chromium/base/containers/flat_tree.h b/chromium/base/containers/flat_tree.h index 5222e388ea9..89c75d70692 100644 --- a/chromium/base/containers/flat_tree.h +++ b/chromium/base/containers/flat_tree.h @@ -14,11 +14,6 @@ namespace base { -enum FlatContainerDupes { - KEEP_FIRST_OF_DUPES, - KEEP_LAST_OF_DUPES, -}; - namespace internal { // This is a convenience method returning true if Iterator is at least a @@ -30,34 +25,6 @@ constexpr bool is_multipass() { typename std::iterator_traits::iterator_category>::value; } -// This algorithm is like unique() from the standard library except it -// selects only the last of consecutive values instead of the first. -template -Iterator LastUnique(Iterator first, Iterator last, BinaryPredicate compare) { - Iterator replacable = std::adjacent_find(first, last, compare); - - // No duplicate elements found. - if (replacable == last) - return last; - - first = std::next(replacable); - - // Last element is a duplicate but all others are unique. - if (first == last) - return replacable; - - // This loop is based on std::adjacent_find but std::adjacent_find doesn't - // quite cut it. - for (Iterator next = std::next(first); next != last; ++next, ++first) { - if (!compare(*first, *next)) - *replacable++ = std::move(*first); - } - - // Last element should be copied unconditionally. - *replacable++ = std::move(*first); - return replacable; -} - // Uses SFINAE to detect whether type has is_transparent member. template struct IsTransparentCompare : std::false_type {}; @@ -136,18 +103,15 @@ class flat_tree { template flat_tree(InputIterator first, InputIterator last, - FlatContainerDupes dupe_handling = KEEP_FIRST_OF_DUPES, const key_compare& comp = key_compare()); flat_tree(const flat_tree&); flat_tree(flat_tree&&) noexcept = default; flat_tree(std::vector items, - FlatContainerDupes dupe_handling = KEEP_FIRST_OF_DUPES, const key_compare& comp = key_compare()); flat_tree(std::initializer_list ilist, - FlatContainerDupes dupe_handling = KEEP_FIRST_OF_DUPES, const key_compare& comp = key_compare()); ~flat_tree(); @@ -222,12 +186,9 @@ class flat_tree { iterator insert(const_iterator position_hint, value_type&& x); // This method inserts the values from the range [first, last) into the - // current tree. In case of KEEP_LAST_OF_DUPES newly added elements can - // overwrite existing values. + // current tree. template - void insert(InputIterator first, - InputIterator last, - FlatContainerDupes dupes = KEEP_FIRST_OF_DUPES); + void insert(InputIterator first, InputIterator last); template std::pair emplace(Args&&... args); @@ -447,28 +408,17 @@ class flat_tree { return {position, false}; } - void sort_and_unique(iterator first, - iterator last, - FlatContainerDupes dupes) { + void sort_and_unique(iterator first, iterator last) { // Preserve stability for the unique code below. - std::stable_sort(first, last, impl_.get_value_comp()); + std::stable_sort(first, last, value_comp()); - auto comparator = [this](const value_type& lhs, const value_type& rhs) { + auto equal_comp = [this](const value_type& lhs, const value_type& rhs) { // lhs is already <= rhs due to sort, therefore // !(lhs < rhs) <=> lhs == rhs. - return !impl_.get_value_comp()(lhs, rhs); + return !value_comp()(lhs, rhs); }; - iterator erase_after; - switch (dupes) { - case KEEP_FIRST_OF_DUPES: - erase_after = std::unique(first, last, comparator); - break; - case KEEP_LAST_OF_DUPES: - erase_after = LastUnique(first, last, comparator); - break; - } - erase(erase_after, last); + erase(std::unique(first, last, equal_comp), last); } // To support comparators that may not be possible to default-construct, we @@ -512,10 +462,9 @@ template flat_tree::flat_tree( InputIterator first, InputIterator last, - FlatContainerDupes dupe_handling, const KeyCompare& comp) : impl_(comp, first, last) { - sort_and_unique(begin(), end(), dupe_handling); + sort_and_unique(begin(), end()); } template @@ -525,18 +474,16 @@ flat_tree::flat_tree( template flat_tree::flat_tree( std::vector items, - FlatContainerDupes dupe_handling, const KeyCompare& comp) : impl_(comp, std::move(items)) { - sort_and_unique(begin(), end(), dupe_handling); + sort_and_unique(begin(), end()); } template flat_tree::flat_tree( std::initializer_list ilist, - FlatContainerDupes dupe_handling, const KeyCompare& comp) - : flat_tree(std::begin(ilist), std::end(ilist), dupe_handling, comp) {} + : flat_tree(std::begin(ilist), std::end(ilist), comp) {} template flat_tree::~flat_tree() = default; @@ -556,7 +503,7 @@ template auto flat_tree::operator=( std::initializer_list ilist) -> flat_tree& { impl_.body_ = ilist; - sort_and_unique(begin(), end(), KEEP_FIRST_OF_DUPES); + sort_and_unique(begin(), end()); return *this; } @@ -717,62 +664,38 @@ template template void flat_tree::insert( InputIterator first, - InputIterator last, - FlatContainerDupes dupes) { + InputIterator last) { if (first == last) return; - // Cache results whether existing elements should be overwritten and whether - // inserting new elements happens immediately or will be done in a batch. - const bool overwrite_existing = dupes == KEEP_LAST_OF_DUPES; - const bool insert_inplace = - is_multipass() && std::next(first) == last; - - if (insert_inplace) { - if (overwrite_existing) { - for (; first != last; ++first) - insert_or_assign(*first); - } else - std::copy(first, last, std::inserter(*this, end())); + // Dispatch to single element insert if the input range contains a single + // element. + if (is_multipass() && std::next(first) == last) { + insert(end(), *first); return; } // Provide a convenience lambda to obtain an iterator pointing past the last // old element. This needs to be dymanic due to possible re-allocations. - const size_type original_size = size(); - auto middle = [this, original_size]() { - return std::next(begin(), original_size); - }; + auto middle = [this, size = size()] { return std::next(begin(), size); }; // For batch updates initialize the first insertion point. - difference_type pos_first_new = original_size; + difference_type pos_first_new = size(); // Loop over the input range while appending new values and overwriting // existing ones, if applicable. Keep track of the first insertion point. - if (overwrite_existing) { - for (; first != last; ++first) { - std::pair result = - append_or_assign(begin(), middle(), *first); - if (result.second) { - pos_first_new = - std::min(pos_first_new, std::distance(begin(), result.first)); - } - } - } else { - for (; first != last; ++first) { - std::pair result = - append_unique(begin(), middle(), *first); - if (result.second) { - pos_first_new = - std::min(pos_first_new, std::distance(begin(), result.first)); - } + for (; first != last; ++first) { + std::pair result = append_unique(begin(), middle(), *first); + if (result.second) { + pos_first_new = + std::min(pos_first_new, std::distance(begin(), result.first)); } } // The new elements might be unordered and contain duplicates, so post-process // the just inserted elements and merge them with the rest, inserting them at // the previously found spot. - sort_and_unique(middle(), end(), dupes); + sort_and_unique(middle(), end()); std::inplace_merge(std::next(begin(), pos_first_new), middle(), end(), value_comp()); } -- cgit v1.2.1