HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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();
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  virtual const char *utGetCacheName() const { return myName; }
99  virtual bool utHasMaxSize() const { return true; }
100  virtual int64 utGetCurrentSize() const { return myMemUsage; }
101  virtual int64 utGetMaxSize() const { return myMaxUsage; }
102  virtual void utSetMaxSize(int64 bytes);
103  virtual int64 utReduceCacheSizeBy(int64 bytes);
104  /// @}
105 
106  /// Thread safe iteration over all items in the cache.
107  /// This method takes a templated class that has a () operator to process
108  /// entries from the traversal. The () operator should return a bool, true
109  /// if the iteration should continue, or false if the traversal can stop.
110  /// For example: @code
111  /// class MemoryCounter
112  /// {
113  /// public:
114  /// MemoryCounter() : myMemory(0) {}
115  /// bool operator()(const UT_CappedKeyHandle &key,
116  /// const UT_CappedItemHandle &handle)
117  /// {
118  /// myMemory += item->getMemoryUsage();
119  /// return true;
120  /// }
121  /// int64 getMemoryUsage() const { return myMemory; }
122  /// int64 myMemory;
123  /// };
124  /// static int64 computeStoredMemory(UT_CappedCache &cache)
125  /// {
126  /// MemoryCounter task;
127  /// cache.threadSafeTraversal(task);
128  /// return task.getMemory();
129  /// }
130  /// @endcode
131  /// @note It is possible to call some methods which alter the map.
132  /// However, other methods will result in a corrupt iteration.
133  /// - @c deleteItem @n
134  /// It is safe to call deleteItem on the current item. However, if
135  /// deleteItem is called, and your task takes const-references to the
136  /// keys/items, these may become invalid.
137  /// - @c findItem @c addItem @n
138  /// This may have a side effect of re-ordering the list, meaning
139  /// iteration will be corrupted.
140  template <typename T>
141  void threadSafeTraversal(T &task)
142  {
143  UT_AutoLockType<UT_CappedLock> lock(myLock);
144  ut_CappedBin *curr=myHead;
145  ut_CappedBin *next;
146  exint n = myEntries;
147  for (exint i = 0; i < n; ++i, curr = next)
148  {
149  next = curr->myNext;
150  if (!task(curr->getKey(), curr->getItem()))
151  break;
152  }
153  }
154 
155 private:
156  class ut_CappedBin {
157  public:
158  ut_CappedBin(const UT_CappedKeyHandle &key,
159  const UT_CappedItemHandle &item)
160  : myKey(key)
161  , myItem(item)
162  , myPrev(NULL)
163  , myNext(NULL)
164  , myTimeStamp(0)
165  {
166  }
167  ~ut_CappedBin()
168  {
169  }
170 
171  const UT_CappedKeyHandle &getKey() const { return myKey; }
172  const UT_CappedItemHandle &getItem() const { return myItem; }
173 
174  exint getTimeStamp() const { return myTimeStamp; }
175  void setTimeStamp(exint t) { myTimeStamp = t; }
176 
177  bool isNearHead(exint head, exint watermark) const
178  {
179  return head - myTimeStamp <= watermark;
180  }
181 
182  private:
183  UT_CappedKeyHandle myKey;
184  UT_CappedItemHandle myItem;
185  ut_CappedBin *myPrev;
186  ut_CappedBin *myNext;
187  exint myTimeStamp;
188  friend class UT_CappedCache; // For links
189  };
190  class ut_cappedKeyCompare
191  {
192  public:
193  static size_t hash(const UT_CappedKey *a)
194  { return (size_t)a->getHash(); }
195  static bool equal(const UT_CappedKey *a, const UT_CappedKey *b)
196  { return a->isEqual(*b); }
197  };
198  typedef UT_ConcurrentHashMap<const UT_CappedKey *,
199  ut_CappedBin *,
200  ut_cappedKeyCompare> ut_CappedMap;
201 
202 private:
203  void pruneItems();
204  /// @{
205  /// List maintenance
206  void addItem(ut_CappedBin *bin);
207  void accessItem(ut_CappedBin *bin);
208  void removeAndDeleteItem(ut_CappedBin *bin);
209  void insertItem(ut_CappedBin *bin);
210  void unlinkItem(ut_CappedBin *bin);
211  /// @}
212 
213  UT_CappedLock myLock;
214  UT_CappedLock myPruneLock;
215  ut_CappedMap myMap;
216  UT_String myName;
217  ut_CappedBin *volatile myHead;
218  volatile int64 myMemUsage;
219  int64 myMaxUsage;
220  exint myHeadTime;
221  exint myQuarterEntries;
222  exint myEntries;
223 };
224 
225 #endif
virtual int64 utGetMaxSize() const
virtual int64 utGetCurrentSize() const
exint entries() const
Number of entries in the cache.
Base class for search keys for UT_CappedCache.
virtual bool isEqual(const UT_CappedKey &key) const =0
Test equality.
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
#define UT_API
Definition: UT_API.h:12
UT_RecursiveSpinLock UT_CappedLock
A reference counter base class for use with UT_IntrusivePtr.
png_uint_32 i
Definition: png.h:2877
long long int64
Definition: SYS_Types.h:100
virtual int64 utReduceCacheSizeBy(int64 amount)=0
GLdouble n
Definition: glcorearb.h:2007
virtual const char * utGetCacheName() const
void threadSafeTraversal(T &task)
int64 exint
Definition: SYS_Types.h:109
virtual unsigned int getHash() const =0
Return a hash for the key.
GLuint const GLchar * name
Definition: glcorearb.h:785
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
Common base class for various caches.
Definition: UT_Cache.h:21
#define UT_ConcurrentHashMap
virtual void utSetMaxSize(int64)
Definition: UT_Cache.h:45
bool equal(T1 a, T2 b, T3 t)
Definition: ImathFun.h:143
exint getListEntries() const
Base class for items in the UT_CappedCache.
virtual bool utHasMaxSize() const