1 | /**************************************************************************** |
---|---|

2 | ** |

3 | ** Copyright (C) 2016 The Qt Company Ltd. |

4 | ** Contact: https://www.qt.io/licensing/ |

5 | ** |

6 | ** This file is part of the QtCore module of the Qt Toolkit. |

7 | ** |

8 | ** $QT_BEGIN_LICENSE:LGPL$ |

9 | ** Commercial License Usage |

10 | ** Licensees holding valid commercial Qt licenses may use this file in |

11 | ** accordance with the commercial license agreement provided with the |

12 | ** Software or, alternatively, in accordance with the terms contained in |

13 | ** a written agreement between you and The Qt Company. For licensing terms |

14 | ** and conditions see https://www.qt.io/terms-conditions. For further |

15 | ** information use the contact form at https://www.qt.io/contact-us. |

16 | ** |

17 | ** GNU Lesser General Public License Usage |

18 | ** Alternatively, this file may be used under the terms of the GNU Lesser |

19 | ** General Public License version 3 as published by the Free Software |

20 | ** Foundation and appearing in the file LICENSE.LGPL3 included in the |

21 | ** packaging of this file. Please review the following information to |

22 | ** ensure the GNU Lesser General Public License version 3 requirements |

23 | ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. |

24 | ** |

25 | ** GNU General Public License Usage |

26 | ** Alternatively, this file may be used under the terms of the GNU |

27 | ** General Public License version 2.0 or (at your option) the GNU General |

28 | ** Public license version 3 or any later version approved by the KDE Free |

29 | ** Qt Foundation. The licenses are as published by the Free Software |

30 | ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 |

31 | ** included in the packaging of this file. Please review the following |

32 | ** information to ensure the GNU General Public License requirements will |

33 | ** be met: https://www.gnu.org/licenses/gpl-2.0.html and |

34 | ** https://www.gnu.org/licenses/gpl-3.0.html. |

35 | ** |

36 | ** $QT_END_LICENSE$ |

37 | ** |

38 | ****************************************************************************/ |

39 | |

40 | #ifndef QCACHE_H |

41 | #define QCACHE_H |

42 | |

43 | #include <QtCore/qhash.h> |

44 | |

45 | QT_BEGIN_NAMESPACE |

46 | |

47 | |

48 | template <class Key, class T> |

49 | class QCache |

50 | { |

51 | struct Node { |

52 | inline Node() : keyPtr(0) {} |

53 | inline Node(T *data, int cost) |

54 | : keyPtr(nullptr), t(data), c(cost), p(nullptr), n(nullptr) {} |

55 | const Key *keyPtr; T *t; int c; Node *p,*n; |

56 | }; |

57 | Node *f, *l; |

58 | QHash<Key, Node> hash; |

59 | int mx, total; |

60 | |

61 | inline void unlink(Node &n) { |

62 | if (n.p) n.p->n = n.n; |

63 | if (n.n) n.n->p = n.p; |

64 | if (l == &n) l = n.p; |

65 | if (f == &n) f = n.n; |

66 | total -= n.c; |

67 | T *obj = n.t; |

68 | hash.remove(*n.keyPtr); |

69 | delete obj; |

70 | } |

71 | inline T *relink(const Key &key) { |

72 | typename QHash<Key, Node>::iterator i = hash.find(key); |

73 | if (typename QHash<Key, Node>::const_iterator(i) == hash.constEnd()) |

74 | return nullptr; |

75 | |

76 | Node &n = *i; |

77 | if (f != &n) { |

78 | if (n.p) n.p->n = n.n; |

79 | if (n.n) n.n->p = n.p; |

80 | if (l == &n) l = n.p; |

81 | n.p = nullptr; |

82 | n.n = f; |

83 | f->p = &n; |

84 | f = &n; |

85 | } |

86 | return n.t; |

87 | } |

88 | |

89 | Q_DISABLE_COPY(QCache) |

90 | |

91 | public: |

92 | inline explicit QCache(int maxCost = 100) noexcept; |

93 | inline ~QCache() { clear(); } |

94 | |

95 | inline int maxCost() const { return mx; } |

96 | void setMaxCost(int m); |

97 | inline int totalCost() const { return total; } |

98 | |

99 | inline int size() const { return hash.size(); } |

100 | inline int count() const { return hash.size(); } |

101 | inline bool isEmpty() const { return hash.isEmpty(); } |

102 | inline QList<Key> keys() const { return hash.keys(); } |

103 | |

104 | void clear(); |

105 | |

106 | bool insert(const Key &key, T *object, int cost = 1); |

107 | T *object(const Key &key) const; |

108 | inline bool contains(const Key &key) const { return hash.contains(key); } |

109 | T *operator[](const Key &key) const; |

110 | |

111 | bool remove(const Key &key); |

112 | T *take(const Key &key); |

113 | |

114 | private: |

115 | void trim(int m); |

116 | }; |

117 | |

118 | template <class Key, class T> |

119 | inline QCache<Key, T>::QCache(int amaxCost) noexcept |

120 | : f(nullptr), l(nullptr), mx(amaxCost), total(0) {} |

121 | |

122 | template <class Key, class T> |

123 | inline void QCache<Key,T>::clear() |

124 | { while (f) { delete f->t; f = f->n; } |

125 | hash.clear(); l = nullptr; total = 0; } |

126 | |

127 | template <class Key, class T> |

128 | inline void QCache<Key,T>::setMaxCost(int m) |

129 | { mx = m; trim(mx); } |

130 | |

131 | template <class Key, class T> |

132 | inline T *QCache<Key,T>::object(const Key &key) const |

133 | { return const_cast<QCache<Key,T>*>(this)->relink(key); } |

134 | |

135 | template <class Key, class T> |

136 | inline T *QCache<Key,T>::operator[](const Key &key) const |

137 | { return object(key); } |

138 | |

139 | template <class Key, class T> |

140 | inline bool QCache<Key,T>::remove(const Key &key) |

141 | { |

142 | typename QHash<Key, Node>::iterator i = hash.find(key); |

143 | if (typename QHash<Key, Node>::const_iterator(i) == hash.constEnd()) { |

144 | return false; |

145 | } else { |

146 | unlink(*i); |

147 | return true; |

148 | } |

149 | } |

150 | |

151 | template <class Key, class T> |

152 | inline T *QCache<Key,T>::take(const Key &key) |

153 | { |

154 | typename QHash<Key, Node>::iterator i = hash.find(key); |

155 | if (i == hash.end()) |

156 | return nullptr; |

157 | |

158 | Node &n = *i; |

159 | T *t = n.t; |

160 | n.t = nullptr; |

161 | unlink(n); |

162 | return t; |

163 | } |

164 | |

165 | template <class Key, class T> |

166 | bool QCache<Key,T>::insert(const Key &akey, T *aobject, int acost) |

167 | { |

168 | remove(akey); |

169 | if (acost > mx) { |

170 | delete aobject; |

171 | return false; |

172 | } |

173 | trim(mx - acost); |

174 | Node sn(aobject, acost); |

175 | typename QHash<Key, Node>::iterator i = hash.insert(akey, sn); |

176 | total += acost; |

177 | Node *n = &i.value(); |

178 | n->keyPtr = &i.key(); |

179 | if (f) f->p = n; |

180 | n->n = f; |

181 | f = n; |

182 | if (!l) l = f; |

183 | return true; |

184 | } |

185 | |

186 | template <class Key, class T> |

187 | void QCache<Key,T>::trim(int m) |

188 | { |

189 | Node *n = l; |

190 | while (n && total > m) { |

191 | Node *u = n; |

192 | n = n->p; |

193 | unlink(*u); |

194 | } |

195 | } |

196 | |

197 | QT_END_NAMESPACE |

198 | |

199 | #endif // QCACHE_H |

200 |