LeechCraft  0.6.70-10870-g558588d6ec
Modular cross-platform feature rich live environment.
assoccache.h
Go to the documentation of this file.
1 /**********************************************************************
2  * LeechCraft - modular cross-platform feature rich internet client.
3  * Copyright (C) 2006-2014 Georg Rudoy
4  *
5  * Boost Software License - Version 1.0 - August 17th, 2003
6  *
7  * Permission is hereby granted, free of charge, to any person or organization
8  * obtaining a copy of the software and accompanying documentation covered by
9  * this license (the "Software") to use, reproduce, display, distribute,
10  * execute, and transmit the Software, and to prepare derivative works of the
11  * Software, and to permit third-parties to whom the Software is furnished to
12  * do so, all subject to the following:
13  *
14  * The copyright notices in the Software and this entire statement, including
15  * the above license grant, this restriction and the following disclaimer,
16  * must be included in all copies of the Software, in whole or in part, and
17  * all derivative works of the Software, unless such copies or derivative
18  * works are solely in the form of machine-executable object code generated by
19  * a source language processor.
20  *
21  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23  * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
24  * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
25  * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
26  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
27  * DEALINGS IN THE SOFTWARE.
28  **********************************************************************/
29 
30 #pragma once
31 
32 #include <algorithm>
33 #include <QHash>
34 
35 namespace LeechCraft
36 {
37 namespace Util
38 {
39  namespace CacheStrat
40  {
41  class LRU
42  {
43  size_t Current_ = 0;
44  public:
45  struct ValueAddon
46  {
47  size_t LastAccess_ = 0;
48 
49  ValueAddon () = default;
50 
51  ValueAddon (size_t la)
52  : LastAccess_ { la }
53  {
54  }
55  };
56 
58  {
59  return { ++Current_ };
60  }
61 
62  void Clear ()
63  {
64  Current_ = 0;
65  }
66 
67  void Touch (ValueAddon& add)
68  {
69  add.LastAccess_ = ++Current_;
70  }
71  };
72 
73  inline bool operator< (const LRU::ValueAddon& v1, const LRU::ValueAddon& v2)
74  {
75  return v1.LastAccess_ < v2.LastAccess_;
76  }
77  }
78 
79  template<typename K, typename V, typename CS = CacheStrat::LRU>
80  class AssocCache
81  {
82  struct ValueHolder
83  {
84  V V_;
85  size_t Cost_;
86  typename CS::ValueAddon CacheInfo_;
87  };
88 
89  QHash<K, ValueHolder> Hash_;
90 
91  size_t CurrentCost_ = 0;
92  const size_t MaxCost_;
93 
94  CS CacheStratState_;
95  public:
96  AssocCache (size_t maxCost)
97  : MaxCost_ { maxCost }
98  {
99  }
100 
101  size_t size () const;
102  void clear ();
103  bool contains (const K&) const;
104 
105  V& operator[] (const K&);
106  private:
107  void CheckShrink ();
108  };
109 
110  template<typename K, typename V, typename CS>
112  {
113  return Hash_.size ();
114  }
115 
116  template<typename K, typename V, typename CS>
118  {
119  Hash_.clear ();
120  CacheStratState_.Clear ();
121  }
122 
123  template<typename K, typename V, typename CS>
124  bool AssocCache<K, V, CS>::contains (const K& k) const
125  {
126  return Hash_.contains (k);
127  }
128 
129  template<typename K, typename V, typename CS>
131  {
132  if (!Hash_.contains (key))
133  {
134  Hash_.insert (key, { {}, 1, CacheStratState_.CreateInfo () });
135  ++CurrentCost_;
136 
137  CheckShrink ();
138  }
139  else
140  CacheStratState_.Touch (Hash_ [key].CacheInfo_);
141 
142  return Hash_ [key].V_;
143  }
144 
145  template<typename K, typename V, typename CS>
147  {
148  while (CurrentCost_ > MaxCost_)
149  {
150  const auto pos = std::min_element (Hash_.begin (), Hash_.end (),
151  [] (const ValueHolder& left, const ValueHolder& right)
152  { return left.CacheInfo_ < right.CacheInfo_; });
153  CurrentCost_ -= pos->Cost_;
154  Hash_.erase (pos);
155  }
156  }
157 }
158 }
detail::ExprTree< detail::ExprType::LeafStaticPlaceholder, boost::mpl::int_< Idx > > pos
Definition: oral.h:922
bool operator<(const LRU::ValueAddon &v1, const LRU::ValueAddon &v2)
Definition: assoccache.h:73
void Touch(ValueAddon &add)
Definition: assoccache.h:67
bool contains(const K &) const
Definition: assoccache.h:124
AssocCache(size_t maxCost)
Definition: assoccache.h:96