File indexing completed on 2026-09-16 09:21:19
0001
0002
0003
0004
0005 #ifndef QCACHE_H
0006 #define QCACHE_H
0007
0008 #include <QtCore/qhash.h>
0009
0010 QT_BEGIN_NAMESPACE
0011
0012
0013 template <class Key, class T>
0014 class QCache
0015 {
0016 struct Value
0017 {
0018 T *t = nullptr;
0019 qsizetype cost = 0;
0020 Value() noexcept = default;
0021 Value(T *tt, qsizetype c) noexcept
0022 : t(tt), cost(c)
0023 {}
0024 Value(Value &&other) noexcept
0025 : t(other.t),
0026 cost(other.cost)
0027 {
0028 other.t = nullptr;
0029 }
0030 Value &operator=(Value &&other) noexcept
0031 {
0032 qt_ptr_swap(t, other.t);
0033 std::swap(cost, other.cost);
0034 return *this;
0035 }
0036 ~Value() { delete t; }
0037
0038 private:
0039 Q_DISABLE_COPY(Value)
0040 };
0041
0042 struct Chain
0043 {
0044 Chain() noexcept : prev(this), next(this) { }
0045 Chain *prev;
0046 Chain *next;
0047 };
0048
0049 struct Node : public Chain
0050 {
0051 using KeyType = Key;
0052 using ValueType = Value;
0053
0054 Key key;
0055 Value value;
0056
0057 Node(const Key &k, Value &&t) noexcept(std::is_nothrow_move_assignable_v<Key>)
0058 : Chain(),
0059 key(k),
0060 value(std::move(t))
0061 {
0062 }
0063 Node(Key &&k, Value &&t) noexcept(std::is_nothrow_move_assignable_v<Key>)
0064 : Chain(),
0065 key(std::move(k)),
0066 value(std::move(t))
0067 {
0068 }
0069 static void createInPlace(Node *n, const Key &k, T *o, qsizetype cost)
0070 {
0071 new (n) Node{ Key(k), Value(o, cost) };
0072 }
0073 void emplace(T *o, qsizetype cost)
0074 {
0075 value = Value(o, cost);
0076 }
0077
0078 Node(Node &&other)
0079 : Chain(other),
0080 key(std::move(other.key)),
0081 value(std::move(other.value))
0082 {
0083 Q_ASSERT(this->prev);
0084 Q_ASSERT(this->next);
0085 this->prev->next = this;
0086 this->next->prev = this;
0087 }
0088 private:
0089 Q_DISABLE_COPY(Node)
0090 };
0091
0092 using Data = QHashPrivate::Data<Node>;
0093
0094 mutable Chain chain;
0095 Data d;
0096 qsizetype mx = 0;
0097 qsizetype total = 0;
0098
0099 void unlink(Node *n) noexcept(std::is_nothrow_destructible_v<Node>)
0100 {
0101 Q_ASSERT(n->prev);
0102 Q_ASSERT(n->next);
0103 n->prev->next = n->next;
0104 n->next->prev = n->prev;
0105 total -= n->value.cost;
0106 auto it = d.findBucket(n->key);
0107 d.erase(it);
0108 }
0109 T *relink(const Key &key) const noexcept
0110 {
0111 if (isEmpty())
0112 return nullptr;
0113 Node *n = d.findNode(key);
0114 if (!n)
0115 return nullptr;
0116
0117 if (chain.next != n) {
0118 Q_ASSERT(n->prev);
0119 Q_ASSERT(n->next);
0120 n->prev->next = n->next;
0121 n->next->prev = n->prev;
0122 n->next = chain.next;
0123 chain.next->prev = n;
0124 n->prev = &chain;
0125 chain.next = n;
0126 }
0127 return n->value.t;
0128 }
0129
0130 void trim(qsizetype m) noexcept(std::is_nothrow_destructible_v<Node>)
0131 {
0132 while (chain.prev != &chain && total > m) {
0133 Node *n = static_cast<Node *>(chain.prev);
0134 unlink(n);
0135 }
0136 }
0137
0138
0139 Q_DISABLE_COPY(QCache)
0140
0141 public:
0142 inline explicit QCache(qsizetype maxCost = 100) noexcept
0143 : mx(maxCost)
0144 {
0145 }
0146 inline ~QCache()
0147 {
0148 static_assert(std::is_nothrow_destructible_v<Key>, "Types with throwing destructors are not supported in Qt containers.");
0149 static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
0150
0151 clear();
0152 }
0153
0154 inline qsizetype maxCost() const noexcept { return mx; }
0155 void setMaxCost(qsizetype m) noexcept(std::is_nothrow_destructible_v<Node>)
0156 {
0157 mx = m;
0158 trim(mx);
0159 }
0160 inline qsizetype totalCost() const noexcept { return total; }
0161
0162 inline qsizetype size() const noexcept { return qsizetype(d.size); }
0163 inline qsizetype count() const noexcept { return qsizetype(d.size); }
0164 inline bool isEmpty() const noexcept { return !d.size; }
0165 inline QList<Key> keys() const
0166 {
0167 QList<Key> k;
0168 if (size()) {
0169 k.reserve(size());
0170 for (auto it = d.begin(); it != d.end(); ++it)
0171 k << it.node()->key;
0172 }
0173 Q_ASSERT(k.size() == size());
0174 return k;
0175 }
0176
0177 void clear() noexcept(std::is_nothrow_destructible_v<Node>)
0178 {
0179 d.clear();
0180 total = 0;
0181 chain.next = &chain;
0182 chain.prev = &chain;
0183 }
0184
0185 bool insert(const Key &key, T *object, qsizetype cost = 1)
0186 {
0187 if (cost > mx) {
0188 remove(key);
0189 delete object;
0190 return false;
0191 }
0192 trim(mx - cost);
0193 auto result = d.findOrInsert(key);
0194 Node *n = result.it.node();
0195 if (result.initialized) {
0196 auto prevCost = n->value.cost;
0197 result.it.node()->emplace(object, cost);
0198 cost -= prevCost;
0199 relink(key);
0200 } else {
0201 Node::createInPlace(n, key, object, cost);
0202 n->prev = &chain;
0203 n->next = chain.next;
0204 chain.next->prev = n;
0205 chain.next = n;
0206 }
0207 total += cost;
0208 return true;
0209 }
0210 T *object(const Key &key) const noexcept
0211 {
0212 return relink(key);
0213 }
0214 T *operator[](const Key &key) const noexcept
0215 {
0216 return relink(key);
0217 }
0218 inline bool contains(const Key &key) const noexcept
0219 {
0220 return !isEmpty() && d.findNode(key) != nullptr;
0221 }
0222
0223 bool remove(const Key &key) noexcept(std::is_nothrow_destructible_v<Node>)
0224 {
0225 if (isEmpty())
0226 return false;
0227 Node *n = d.findNode(key);
0228 if (!n) {
0229 return false;
0230 } else {
0231 unlink(n);
0232 return true;
0233 }
0234 }
0235
0236 T *take(const Key &key) noexcept(std::is_nothrow_destructible_v<Key>)
0237 {
0238 if (isEmpty())
0239 return nullptr;
0240 Node *n = d.findNode(key);
0241 if (!n)
0242 return nullptr;
0243
0244 T *t = n->value.t;
0245 n->value.t = nullptr;
0246 unlink(n);
0247 return t;
0248 }
0249
0250 };
0251
0252 QT_END_NAMESPACE
0253
0254 #endif
