summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qflatmap_p.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/corelib/tools/qflatmap_p.h')
-rw-r--r--src/corelib/tools/qflatmap_p.h482
1 files changed, 303 insertions, 179 deletions
diff --git a/src/corelib/tools/qflatmap_p.h b/src/corelib/tools/qflatmap_p.h
index 1b3eaea01c..7fce7c43af 100644
--- a/src/corelib/tools/qflatmap_p.h
+++ b/src/corelib/tools/qflatmap_p.h
@@ -1,41 +1,5 @@
-/****************************************************************************
-**
-** Copyright (C) 2020 The Qt Company Ltd.
-** Contact: https://www.qt.io/licensing/
-**
-** This file is part of the QtCore module of the Qt Toolkit.
-**
-** $QT_BEGIN_LICENSE:LGPL$
-** Commercial License Usage
-** Licensees holding valid commercial Qt licenses may use this file in
-** accordance with the commercial license agreement provided with the
-** Software or, alternatively, in accordance with the terms contained in
-** a written agreement between you and The Qt Company. For licensing terms
-** and conditions see https://www.qt.io/terms-conditions. For further
-** information use the contact form at https://www.qt.io/contact-us.
-**
-** GNU Lesser General Public License Usage
-** Alternatively, this file may be used under the terms of the GNU Lesser
-** General Public License version 3 as published by the Free Software
-** Foundation and appearing in the file LICENSE.LGPL3 included in the
-** packaging of this file. Please review the following information to
-** ensure the GNU Lesser General Public License version 3 requirements
-** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
-**
-** GNU General Public License Usage
-** Alternatively, this file may be used under the terms of the GNU
-** General Public License version 2.0 or (at your option) the GNU General
-** Public license version 3 or any later version approved by the KDE Free
-** Qt Foundation. The licenses are as published by the Free Software
-** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
-** included in the packaging of this file. Please review the following
-** information to ensure the GNU General Public License requirements will
-** be met: https://www.gnu.org/licenses/gpl-2.0.html and
-** https://www.gnu.org/licenses/gpl-3.0.html.
-**
-** $QT_END_LICENSE$
-**
-****************************************************************************/
+// Copyright (C) 2022 The Qt Company Ltd.
+// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
#ifndef QFLATMAP_P_H
#define QFLATMAP_P_H
@@ -52,6 +16,7 @@
//
#include "qlist.h"
+#include "private/qglobal_p.h"
#include <algorithm>
#include <functional>
@@ -77,6 +42,19 @@ QT_BEGIN_NAMESPACE
QFlatMap<float, int, std::less<float>, std::vector<float>, std::vector<int>>
*/
+// Qt 6.4:
+// - removed QFlatMap API which was incompatible with STL semantics
+// - will be released with said API disabled, to catch any out-of-tree users
+// - also allows opting in to the new API using QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT
+// Qt 6.5
+// - will make QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT the default:
+
+#ifndef QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT
+# if QT_VERSION >= QT_VERSION_CHECK(6, 5, 0)
+# define QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT
+# endif
+#endif
+
namespace Qt {
struct OrderedUniqueRange_t {};
@@ -96,7 +74,7 @@ public:
using value_type = std::pair<const Key, T>;
static constexpr bool is_comparator_noexcept = noexcept(
- std::declval<Compare>()(std::declval<Key>(), std::declval<Key>()));
+ std::declval<Compare>()(std::declval<const Key &>(), std::declval<const Key &>()));
bool operator()(const value_type &lhs, const value_type &rhs) const
noexcept(is_comparator_noexcept)
@@ -105,29 +83,34 @@ public:
}
};
+namespace qflatmap {
+namespace detail {
+template <class T>
+class QFlatMapMockPointer
+{
+ T ref;
+public:
+ QFlatMapMockPointer(T r)
+ : ref(r)
+ {
+ }
+
+ T *operator->()
+ {
+ return &ref;
+ }
+};
+} // namespace detail
+} // namespace qflatmap
+
template<class Key, class T, class Compare = std::less<Key>, class KeyContainer = QList<Key>,
class MappedContainer = QList<T>>
class QFlatMap : private QFlatMapValueCompare<Key, T, Compare>
{
static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
- using full_map_t = QFlatMap<Key, T, Compare, KeyContainer, MappedContainer>;
-
- template <class U>
- class mock_pointer
- {
- U ref;
- public:
- mock_pointer(U r)
- : ref(r)
- {
- }
-
- U *operator->()
- {
- return &ref;
- }
- };
+ template<class U>
+ using mock_pointer = qflatmap::detail::QFlatMapMockPointer<U>;
public:
using key_type = Key;
@@ -161,12 +144,12 @@ public:
{
}
- reference operator*()
+ reference operator*() const
{
return { c->keys[i], c->values[i] };
}
- pointer operator->()
+ pointer operator->() const
{
return { operator*() };
}
@@ -191,7 +174,7 @@ public:
{
iterator r = *this;
- i++;
+ ++*this;
return r;
}
@@ -204,7 +187,7 @@ public:
iterator operator--(int)
{
iterator r = *this;
- i--;
+ --*this;
return r;
}
@@ -242,7 +225,7 @@ public:
return b.i - a.i;
}
- reference operator[](size_type n)
+ reference operator[](size_type n) const
{
size_type k = i + n;
return { c->keys[k], c->values[k] };
@@ -269,12 +252,12 @@ public:
}
const Key &key() const { return c->keys[i]; }
- T &value() { return c->values[i]; }
+ T &value() const { return c->values[i]; }
private:
containers *c = nullptr;
size_type i = 0;
- friend full_map_t;
+ friend QFlatMap;
};
class const_iterator
@@ -298,12 +281,12 @@ public:
{
}
- reference operator*()
+ reference operator*() const
{
return { c->keys[i], c->values[i] };
}
- pointer operator->()
+ pointer operator->() const
{
return { operator*() };
}
@@ -328,7 +311,7 @@ public:
{
const_iterator r = *this;
- i++;
+ ++*this;
return r;
}
@@ -341,7 +324,7 @@ public:
const_iterator operator--(int)
{
const_iterator r = *this;
- i--;
+ --*this;
return r;
}
@@ -379,7 +362,7 @@ public:
return b.i - a.i;
}
- reference operator[](size_type n)
+ reference operator[](size_type n) const
{
size_type k = i + n;
return { c->keys[k], c->values[k] };
@@ -406,12 +389,12 @@ public:
}
const Key &key() const { return c->keys[i]; }
- const T &value() { return c->values[i]; }
+ const T &value() const { return c->values[i]; }
private:
const containers *c = nullptr;
size_type i = 0;
- friend full_map_t;
+ friend QFlatMap;
};
private:
@@ -419,7 +402,7 @@ private:
struct is_marked_transparent_type : std::false_type { };
template <class X>
- struct is_marked_transparent_type<X, typename X::is_transparent> : std::true_type { };
+ struct is_marked_transparent_type<X, std::void_t<typename X::is_transparent>> : std::true_type { };
template <class X>
using is_marked_transparent = typename std::enable_if<
@@ -432,6 +415,7 @@ private:
public:
QFlatMap() = default;
+#ifdef QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT
explicit QFlatMap(const key_container_type &keys, const mapped_container_type &values)
: c{keys, values}
{
@@ -439,23 +423,20 @@ public:
}
explicit QFlatMap(key_container_type &&keys, const mapped_container_type &values)
+ : c{std::move(keys), values}
{
- c.keys = std::move(keys);
- c.values = values;
ensureOrderedUnique();
}
explicit QFlatMap(const key_container_type &keys, mapped_container_type &&values)
+ : c{keys, std::move(values)}
{
- c.keys = keys;
- c.values = std::move(values);
ensureOrderedUnique();
}
explicit QFlatMap(key_container_type &&keys, mapped_container_type &&values)
+ : c{std::move(keys), std::move(values)}
{
- c.keys = std::move(keys);
- c.values = std::move(values);
ensureOrderedUnique();
}
@@ -470,37 +451,34 @@ public:
initWithRange(first, last);
ensureOrderedUnique();
}
+#endif
explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys,
const mapped_container_type &values)
+ : c{keys, values}
{
- c.keys = keys;
- c.values = values;
}
explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys,
const mapped_container_type &values)
+ : c{std::move(keys), values}
{
- c.keys = std::move(keys);
- c.values = values;
}
explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys,
mapped_container_type &&values)
+ : c{keys, std::move(values)}
{
- c.keys = keys;
- c.values = std::move(values);
}
explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys,
mapped_container_type &&values)
+ : c{std::move(keys), std::move(values)}
{
- c.keys = std::move(keys);
- c.values = std::move(values);
}
explicit QFlatMap(Qt::OrderedUniqueRange_t, std::initializer_list<value_type> lst)
- : QFlatMap(lst.begin(), lst.end())
+ : QFlatMap(Qt::OrderedUniqueRange, lst.begin(), lst.end())
{
}
@@ -515,6 +493,7 @@ public:
{
}
+#ifdef QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT
explicit QFlatMap(const key_container_type &keys, const mapped_container_type &values,
const Compare &compare)
: value_compare(compare), c{keys, values}
@@ -555,6 +534,7 @@ public:
initWithRange(first, last);
ensureOrderedUnique();
}
+#endif
explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys,
const mapped_container_type &values, const Compare &compare)
@@ -616,13 +596,13 @@ public:
bool remove(const Key &key)
{
- auto it = binary_find(key);
- if (it != end()) {
- c.keys.erase(toKeysIterator(it));
- c.values.erase(toValuesIterator(it));
- return true;
- }
- return false;
+ return do_remove(find(key));
+ }
+
+ template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr>
+ bool remove(const X &key)
+ {
+ return do_remove(find(key));
}
iterator erase(iterator it)
@@ -633,50 +613,60 @@ public:
T take(const Key &key)
{
- auto it = binary_find(key);
- if (it != end()) {
- T result = std::move(it.value());
- erase(it);
- return result;
- }
- return {};
+ return do_take(find(key));
+ }
+
+ template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr>
+ T take(const X &key)
+ {
+ return do_take(find(key));
}
bool contains(const Key &key) const
{
- return binary_find(key) != end();
+ return find(key) != end();
+ }
+
+ template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr>
+ bool contains(const X &key) const
+ {
+ return find(key) != end();
}
T value(const Key &key, const T &defaultValue) const
{
- auto it = binary_find(key);
+ auto it = find(key);
+ return it == end() ? defaultValue : it.value();
+ }
+
+ template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr>
+ T value(const X &key, const T &defaultValue) const
+ {
+ auto it = find(key);
return it == end() ? defaultValue : it.value();
}
T value(const Key &key) const
{
- auto it = binary_find(key);
+ auto it = find(key);
+ return it == end() ? T() : it.value();
+ }
+
+ template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr>
+ T value(const X &key) const
+ {
+ auto it = find(key);
return it == end() ? T() : it.value();
}
T &operator[](const Key &key)
{
- auto it = lower_bound(key);
- if (it == end() || key_compare::operator()(key, it.key())) {
- c.keys.insert(toKeysIterator(it), key);
- return *c.values.insert(toValuesIterator(it), T());
- }
- return it.value();
+ return try_emplace(key).first.value();
}
T &operator[](Key &&key)
{
- auto it = lower_bound(key);
- if (it == end() || key_compare::operator()(key, it.key())) {
- c.keys.insert(toKeysIterator(it), key);
- return *c.values.insert(toValuesIterator(it), T());
- }
- return it.value();
+ return try_emplace(std::move(key)).first.value();
}
T operator[](const Key &key) const
@@ -684,55 +674,71 @@ public:
return value(key);
}
+#ifdef QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT
std::pair<iterator, bool> insert(const Key &key, const T &value)
{
- auto it = lower_bound(key);
- if (it == end() || key_compare::operator()(key, it.key())) {
- c.values.insert(toValuesIterator(it), value);
- auto k = c.keys.insert(toKeysIterator(it), key);
- return { fromKeysIterator(k), true };
- } else {
- it.value() = value;
- return {it, false};
- }
+ return try_emplace(key, value);
}
std::pair<iterator, bool> insert(Key &&key, const T &value)
{
- auto it = lower_bound(key);
- if (it == end() || key_compare::operator()(key, it.key())) {
- c.values.insert(toValuesIterator(it), value);
- return { c.keys.insert(it, std::move(key)), true };
- } else {
- *toValuesIterator(it) = value;
- return {it, false};
- }
+ return try_emplace(std::move(key), value);
}
std::pair<iterator, bool> insert(const Key &key, T &&value)
{
+ return try_emplace(key, std::move(value));
+ }
+
+ std::pair<iterator, bool> insert(Key &&key, T &&value)
+ {
+ return try_emplace(std::move(key), std::move(value));
+ }
+#endif
+
+ template <typename...Args>
+ std::pair<iterator, bool> try_emplace(const Key &key, Args&&...args)
+ {
auto it = lower_bound(key);
if (it == end() || key_compare::operator()(key, it.key())) {
- c.values.insert(toValuesIterator(it), std::move(value));
- return { c.keys.insert(it, key), true };
+ c.values.emplace(toValuesIterator(it), std::forward<Args>(args)...);
+ return { fromKeysIterator(c.keys.insert(toKeysIterator(it), key)), true };
} else {
- *toValuesIterator(it) = std::move(value);
return {it, false};
}
}
- std::pair<iterator, bool> insert(Key &&key, T &&value)
+ template <typename...Args>
+ std::pair<iterator, bool> try_emplace(Key &&key, Args&&...args)
{
auto it = lower_bound(key);
if (it == end() || key_compare::operator()(key, it.key())) {
- c.values.insert(toValuesIterator(it), std::move(value));
+ c.values.emplace(toValuesIterator(it), std::forward<Args>(args)...);
return { fromKeysIterator(c.keys.insert(toKeysIterator(it), std::move(key))), true };
} else {
- *toValuesIterator(it) = std::move(value);
return {it, false};
}
}
+ template <typename M>
+ std::pair<iterator, bool> insert_or_assign(const Key &key, M &&obj)
+ {
+ auto r = try_emplace(key, std::forward<M>(obj));
+ if (!r.second)
+ *toValuesIterator(r.first) = std::forward<M>(obj);
+ return r;
+ }
+
+ template <typename M>
+ std::pair<iterator, bool> insert_or_assign(Key &&key, M &&obj)
+ {
+ auto r = try_emplace(std::move(key), std::forward<M>(obj));
+ if (!r.second)
+ *toValuesIterator(r.first) = std::forward<M>(obj);
+ return r;
+ }
+
+#ifdef QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT
template <class InputIt, is_compatible_iterator<InputIt> = nullptr>
void insert(InputIt first, InputIt last)
{
@@ -758,6 +764,7 @@ public:
{
insertOrderedUniqueRange(first, last);
}
+#endif
iterator begin() { return { &c, 0 }; }
const_iterator begin() const { return { &c, 0 }; }
@@ -784,14 +791,14 @@ public:
iterator lower_bound(const Key &key)
{
- auto cit = const_cast<const full_map_t *>(this)->lower_bound(key);
+ auto cit = std::as_const(*this).lower_bound(key);
return { &c, cit.i };
}
template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr>
iterator lower_bound(const X &key)
{
- auto cit = const_cast<const full_map_t *>(this)->lower_bound(key);
+ auto cit = std::as_const(*this).lower_bound(key);
return { &c, cit.i };
}
@@ -806,14 +813,112 @@ public:
return fromKeysIterator(std::lower_bound(c.keys.begin(), c.keys.end(), key, key_comp()));
}
- iterator find(const key_type &k)
+ iterator find(const Key &key)
+ {
+ return { &c, std::as_const(*this).find(key).i };
+ }
+
+ template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr>
+ iterator find(const X &key)
+ {
+ return { &c, std::as_const(*this).find(key).i };
+ }
+
+ const_iterator find(const Key &key) const
{
- return binary_find(k);
+ auto it = lower_bound(key);
+ if (it != end()) {
+ if (!key_compare::operator()(key, it.key()))
+ return it;
+ it = end();
+ }
+ return it;
}
- const_iterator find(const key_type &k) const
+ template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr>
+ const_iterator find(const X &key) const
{
- return binary_find(k);
+ auto it = lower_bound(key);
+ if (it != end()) {
+ if (!key_compare::operator()(key, it.key()))
+ return it;
+ it = end();
+ }
+ return it;
+ }
+
+ template <typename Predicate>
+ size_type remove_if(Predicate pred)
+ {
+ const auto indirect_call_to_pred = [pred = std::move(pred)](iterator it) {
+ using Pair = decltype(*it);
+ using K = decltype(it.key());
+ using V = decltype(it.value());
+ using P = Predicate;
+ if constexpr (std::is_invocable_v<P, K, V>) {
+ return pred(it.key(), it.value());
+ } else if constexpr (std::is_invocable_v<P, Pair> && !std::is_invocable_v<P, K>) {
+ return pred(*it);
+ } else if constexpr (std::is_invocable_v<P, K> && !std::is_invocable_v<P, Pair>) {
+ return pred(it.key());
+ } else {
+ static_assert(QtPrivate::type_dependent_false<Predicate>(),
+ "Don't know how to call the predicate.\n"
+ "Options:\n"
+ "- pred(*it)\n"
+ "- pred(it.key(), it.value())\n"
+ "- pred(it.key())");
+ }
+ };
+
+ auto first = begin();
+ const auto last = end();
+
+ // find_if prefix loop
+ while (first != last && !indirect_call_to_pred(first))
+ ++first;
+
+ if (first == last)
+ return 0; // nothing to do
+
+ // we know that we need to remove *first
+
+ auto kdest = toKeysIterator(first);
+ auto vdest = toValuesIterator(first);
+
+ ++first;
+
+ auto k = std::next(kdest);
+ auto v = std::next(vdest);
+
+ // Main Loop
+ // - first is used only for indirect_call_to_pred
+ // - operations are done on k, v
+ // Loop invariants:
+ // - first, k, v are pointing to the same element
+ // - [begin(), first[, [c.keys.begin(), k[, [c.values.begin(), v[: already processed
+ // - [first, end()[, [k, c.keys.end()[, [v, c.values.end()[: still to be processed
+ // - [c.keys.begin(), kdest[ and [c.values.begin(), vdest[ are keepers
+ // - [kdest, k[, [vdest, v[ are considered removed
+ // - kdest is not c.keys.end()
+ // - vdest is not v.values.end()
+ while (first != last) {
+ if (!indirect_call_to_pred(first)) {
+ // keep *first, aka {*k, *v}
+ *kdest = std::move(*k);
+ *vdest = std::move(*v);
+ ++kdest;
+ ++vdest;
+ }
+ ++k;
+ ++v;
+ ++first;
+ }
+
+ const size_type r = std::distance(kdest, c.keys.end());
+ c.keys.erase(kdest, c.keys.end());
+ c.values.erase(vdest, c.values.end());
+ return r;
}
key_compare key_comp() const noexcept
@@ -827,6 +932,25 @@ public:
}
private:
+ bool do_remove(iterator it)
+ {
+ if (it != end()) {
+ erase(it);
+ return true;
+ }
+ return false;
+ }
+
+ T do_take(iterator it)
+ {
+ if (it != end()) {
+ T result = std::move(it.value());
+ erase(it);
+ return result;
+ }
+ return {};
+ }
+
template <class InputIt, is_compatible_iterator<InputIt> = nullptr>
void initWithRange(InputIt first, InputIt last)
{
@@ -874,7 +998,7 @@ private:
class IndexedKeyComparator
{
public:
- IndexedKeyComparator(const full_map_t *am)
+ IndexedKeyComparator(const QFlatMap *am)
: m(am)
{
}
@@ -885,7 +1009,7 @@ private:
}
private:
- const full_map_t *m;
+ const QFlatMap *m;
};
template <class InputIt>
@@ -906,22 +1030,6 @@ private:
makeUnique();
}
- iterator binary_find(const Key &key)
- {
- return { &c, const_cast<const full_map_t *>(this)->binary_find(key).i };
- }
-
- const_iterator binary_find(const Key &key) const
- {
- auto it = lower_bound(key);
- if (it != end()) {
- if (!key_compare::operator()(key, it.key()))
- return it;
- it = end();
- }
- return it;
- }
-
void ensureOrderedUnique()
{
std::vector<size_type> p(size_t(c.keys.size()));
@@ -953,31 +1061,47 @@ private:
void makeUnique()
{
- if (c.keys.size() < 2)
+ // std::unique, but over two ranges
+ auto equivalent = [this](const auto &lhs, const auto &rhs) {
+ return !key_compare::operator()(lhs, rhs) && !key_compare::operator()(rhs, lhs);
+ };
+ const auto kb = c.keys.begin();
+ const auto ke = c.keys.end();
+ auto k = std::adjacent_find(kb, ke, equivalent);
+ if (k == ke)
return;
- auto k = std::end(c.keys) - 1;
- auto i = k - 1;
- for (;;) {
- if (key_compare::operator()(*i, *k) || key_compare::operator()(*k, *i)) {
- if (i == std::begin(c.keys))
- break;
- --i;
- --k;
- } else {
- c.values.erase(std::begin(c.values) + std::distance(std::begin(c.keys), i));
- i = c.keys.erase(i);
- if (i == std::begin(c.keys))
- break;
- k = i + 1;
+
+ // equivalent keys found, we need to do actual work:
+ auto v = std::next(c.values.begin(), std::distance(kb, k));
+
+ auto kdest = k;
+ auto vdest = v;
+
+ ++k;
+ ++v;
+
+ // Loop Invariants:
+ //
+ // - [keys.begin(), kdest] and [values.begin(), vdest] are unique
+ // - k is not keys.end(), v is not values.end()
+ // - [next(k), keys.end()[ and [next(v), values.end()[ still need to be checked
+ while ((++v, ++k) != ke) {
+ if (!equivalent(*kdest, *k)) {
+ *++kdest = std::move(*k);
+ *++vdest = std::move(*v);
}
}
- c.keys.shrink_to_fit();
- c.values.shrink_to_fit();
+
+ c.keys.erase(std::next(kdest), ke);
+ c.values.erase(std::next(vdest), c.values.end());
}
containers c;
};
+template<class Key, class T, qsizetype N = 256, class Compare = std::less<Key>>
+using QVarLengthFlatMap = QFlatMap<Key, T, Compare, QVarLengthArray<Key, N>, QVarLengthArray<T, N>>;
+
QT_END_NAMESPACE
#endif // QFLATMAP_P_H
generated by cgit v1.2.3 (git 2.25.1) at 2023-06-01 08:54:48 +0000