HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_CappedCache.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_CappedCache.h ( UT Library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #ifndef __UT_CappedCache__
12 #define __UT_CappedCache__
13 
14 #include "UT_API.h"
15 #include "UT_Cache.h"
16 #include "UT_String.h"
17 #include "UT_IntrusivePtr.h"
18 #include "UT_Lock.h"
19 #include "UT_SpinLock.h"
20 #include "UT_ConcurrentHashMap.h"
21 
23 
25 //typedef UT_Lock UT_CappedLock;
26 
27 /// Base class for search keys for UT_CappedCache
29  : public UT_IntrusiveRefCounter<UT_CappedKey>
30 {
31 public:
32  UT_CappedKey();
33  virtual ~UT_CappedKey();
34 
35  /// The duplicate() method should return a copy of the key.
36  virtual UT_CappedKey *duplicate() const = 0;
37  /// Return a hash for the key
38  virtual unsigned int getHash() const = 0;
39  /// Test equality
40  virtual bool isEqual(const UT_CappedKey &key) const = 0;
41 private:
42 };
44 
45 /// Base class for items in the UT_CappedCache
47  : public UT_IntrusiveRefCounter<UT_CappedItem>
48 {
49 public:
50  UT_CappedItem();
51  virtual ~UT_CappedItem();
52 
53  /// Query the memory used by the cache item. This should be constant over
54  /// the life of the item.
55  virtual int64 getMemoryUsage() const = 0;
56 private:
57 };
59 
60 /// A thread safe memory limited cache
61 ///
62 /// This class stores a map of UT_CappedItem objects which are queried by
63 /// UT_CappedKey objects. In addition, the cache is an LRU, memory limited
64 /// cache. The cache tracks memory used by each UT_CappedItem to keep memory
65 /// usage limited to the given threshold.
66 /// @note This class conforms to the UT_Cache interface.
68 {
69 public:
70  UT_CappedCache(const char *name, int64 size_in_mb=32);
71  ~UT_CappedCache() override;
72 
73  /// Clear the cache
74  void clear();
75 
76  /// Number of entries in the cache
77  exint entries() const { return myMap.size(); }
78 
79  /// Return the number of entries in the list. This should match the
80  /// entries in the map.
81  exint getListEntries() const { return myEntries; }
82 
83  /// Find an item in the cache
84  UT_CappedItemHandle findItem(const UT_CappedKey &key);
85 
86  /// Add an item to the cache. The returned item may not be the item passed
87  /// as an argument. This may happen if two threads attempt to add the same
88  /// item at the same time (i.e. the keys are equivalent, but the items may
89  /// be different).
90  UT_CappedItemHandle addItem(const UT_CappedKey &key,
91  const UT_CappedItemHandle &item);
92 
93  /// Remove an item from the cache
94  void deleteItem(const UT_CappedKey &key);
95 
96  /// @{
97  /// API from UT_Cache
98  const char *utGetCacheName() const override { return myName; }
99  bool utHasMaxSize() const override { return true; }
100  int64 utGetCurrentSize() const override
101  { return myMemUsage; }
102  int64 utGetMaxSize() const override
103  { return myMaxUsage; }
104  void utSetMaxSize(int64 bytes) override;
106  /// @}
107 
108  /// Thread safe iteration over all items in the cache.
109  /// This method takes a templated class that has a () operator to process
110  /// entries from the traversal. The () operator should return a bool, true
111  /// if the iteration should continue, or false if the traversal can stop.
112  /// For example: @code
113  /// class MemoryCounter
114  /// {
115  /// public:
116  /// MemoryCounter() : myMemory(0) {}
117  /// bool operator()(const UT_CappedKeyHandle &key,
118  /// const UT_CappedItemHandle &handle)
119  /// {
120  /// myMemory += item->getMemoryUsage();
121  /// return true;
122  /// }
123  /// int64 getMemoryUsage() const { return myMemory; }
124  /// int64 myMemory;
125  /// };
126  /// static int64 computeStoredMemory(UT_CappedCache &cache)
127  /// {
128  /// MemoryCounter task;
129  /// cache.threadSafeTraversal(task);
130  /// return task.getMemory();
131  /// }
132  /// @endcode
133  /// @note It is possible to call some methods which alter the map.
134  /// However, other methods will result in a corrupt iteration.
135  /// - @c deleteItem @n
136  /// It is safe to call deleteItem on the current item. However, if
137  /// deleteItem is called, and your task takes const-references to the
138  /// keys/items, these may become invalid.
139  /// - @c findItem @c addItem @n
140  /// This may have a side effect of re-ordering the list, meaning
141  /// iteration will be corrupted.
142  template <typename T>
143  void threadSafeTraversal(T &task)
144  {
145  UT_AutoLockType<UT_CappedLock> lock(myLock);
146  ut_CappedBin *curr=myHead;
147  ut_CappedBin *next;
148  exint n = myEntries;
149  for (exint i = 0; i < n; ++i, curr = next)
150  {
151  next = curr->myNext;
152  if (!task(curr->getKey(), curr->getItem()))
153  break;
154  }
155  }
156 
157 private:
158  class ut_CappedBin {
159  public:
160  ut_CappedBin(const UT_CappedKeyHandle &key,
161  const UT_CappedItemHandle &item)
162  : myKey(key)
163  , myItem(item)
164  , myPrev(NULL)
165  , myNext(NULL)
166  , myTimeStamp(0)
167  {
168  }
169  ~ut_CappedBin()
170  {
171  }
172 
173  const UT_CappedKeyHandle &getKey() const { return myKey; }
174  const UT_CappedItemHandle &getItem() const { return myItem; }
175 
176  exint getTimeStamp() const { return myTimeStamp; }
177  void setTimeStamp(exint t) { myTimeStamp = t; }
178 
179  bool isNearHead(exint head, exint watermark) const
180  {
181  return head - myTimeStamp <= watermark;
182  }
183 
184  private:
185  UT_CappedKeyHandle myKey;
186  UT_CappedItemHandle myItem;
187  ut_CappedBin *myPrev;
188  ut_CappedBin *myNext;
189  exint myTimeStamp;
190  friend class UT_CappedCache; // For links
191  };
192  class ut_cappedKeyCompare
193  {
194  public:
195  static size_t hash(const UT_CappedKey *a)
196  { return (size_t)a->getHash(); }
197  static bool equal(const UT_CappedKey *a, const UT_CappedKey *b)
198  { return a->isEqual(*b); }
199  };
200  typedef UT_ConcurrentHashMap<const UT_CappedKey *,
201  ut_CappedBin *,
202  ut_cappedKeyCompare> ut_CappedMap;
203 
204 private:
205  void pruneItems();
206  /// @{
207  /// List maintenance
208  void addItem(ut_CappedBin *bin);
209  void accessItem(ut_CappedBin *bin);
210  void removeAndDeleteItem(ut_CappedBin *bin);
211  void insertItem(ut_CappedBin *bin);
212  void unlinkItem(ut_CappedBin *bin);
213  /// @}
214 
215  UT_CappedLock myLock;
216  UT_CappedLock myPruneLock;
217  ut_CappedMap myMap;
218  UT_String myName;
219  ut_CappedBin *volatile myHead;
220  volatile int64 myMemUsage;
221  int64 myMaxUsage;
222  exint myHeadTime;
223  exint myQuarterEntries;
224  exint myEntries;
225 };
226 
227 #endif
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
exint entries() const
Number of entries in the cache.
UT_RecursiveSpinLock UT_CappedLock
int64 utGetMaxSize() const override
Base class for search keys for UT_CappedCache.
virtual bool isEqual(const UT_CappedKey &key) const =0
Test equality.
int64 exint
Definition: SYS_Types.h:125
#define UT_API
Definition: UT_API.h:14
GLuint const GLchar * name
Definition: glcorearb.h:785
A reference counter base class for use with UT_IntrusivePtr.
GLdouble GLdouble t
Definition: glew.h:1403
virtual int64 utReduceCacheSizeBy(int64 amount)=0
void threadSafeTraversal(T &task)
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
long long int64
Definition: SYS_Types.h:116
virtual unsigned int getHash() const =0
Return a hash for the key.
Common base class for various caches.
Definition: UT_Cache.h:21
GLdouble n
Definition: glcorearb.h:2007
#define UT_ConcurrentHashMap
bool utHasMaxSize() const override
virtual void utSetMaxSize(int64)
Definition: UT_Cache.h:45
bool equal(T1 a, T2 b, T3 t)
Definition: ImathFun.h:143
const char * utGetCacheName() const override
exint getListEntries() const
Base class for items in the UT_CappedCache.
int64 utGetCurrentSize() const override
Definition: format.h:3611