Debian Codegraph @

srtcore/cache.h

raw
1 /*****************************************************************************
2 Copyright (c) 2001 - 2011, The Board of Trustees of the University of Illinois.
3 All rights reserved.
4
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are
7 met:
8
9 * Redistributions of source code must retain the above
10 copyright notice, this list of conditions and the
11 following disclaimer.
12
13 * Redistributions in binary form must reproduce the
14 above copyright notice, this list of conditions
15 and the following disclaimer in the documentation
16 and/or other materials provided with the distribution.
17
18 * Neither the name of the University of Illinois
19 nor the names of its contributors may be used to
20 endorse or promote products derived from this
21 software without specific prior written permission.
22
23 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
24 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
25 THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
26 PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
27 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
28 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
29 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 *****************************************************************************/
35
36 /*****************************************************************************
37 written by
38 Yunhong Gu, last updated 01/27/2011
39 *****************************************************************************/
40
41 #ifndef INC_SRT_CACHE_H
42 #define INC_SRT_CACHE_H
43
44 #include <list>
45 #include <vector>
46
47 #include "sync.h"
48 #include "netinet_any.h"
49 #include "udt.h"
50
51 namespace srt
52 {
53
54 class CCacheItem
55 {
56 public:
57 virtual ~CCacheItem() {}
58
59 public:
60 virtual CCacheItem& operator=(const CCacheItem&) = 0;
61
62 // The "==" operator SHOULD only compare key values.
63 virtual bool operator==(const CCacheItem&) = 0;
64
65 /// get a deep copy clone of the current item
66 /// @return Pointer to the new item, or NULL if failed.
67
68 virtual CCacheItem* clone() = 0;
69
70 /// get a random key value between 0 and MAX_INT to be used for the hash in cache
71 /// @return A random hash key.
72
73 virtual int getKey() = 0;
74
75 // If there is any shared resources between the cache item and its clone,
76 // the shared resource should be released by this function.
77 virtual void release() {}
78 };
79
80 template <typename T>
81 class CCache
82 {
83 public:
84 CCache(int size = 1024)
85 : m_iMaxSize(size)
86 , m_iHashSize(size * 3)
87 , m_iCurrSize(0)
88 {
89 m_vHashPtr.resize(m_iHashSize);
90 // Exception: -> CUDTUnited ctor
91 srt::sync::setupMutex(m_Lock, "Cache");
92 }
93
94 ~CCache() { clear(); }
95
96 public:
97 /// find the matching item in the cache.
98 /// @param [in,out] data storage for the retrieved item; initially it must carry the key information
99 /// @return 0 if found a match, otherwise -1.
100
101 int lookup(T* data)
102 {
103 srt::sync::ScopedLock cacheguard(m_Lock);
104
105 int key = data->getKey();
106 if (key < 0)
107 return -1;
108 if (key >= m_iMaxSize)
109 key %= m_iHashSize;
110
111 const ItemPtrList& item_list = m_vHashPtr[key];
112 for (typename ItemPtrList::const_iterator i = item_list.begin(); i != item_list.end(); ++i)
113 {
114 if (*data == ***i)
115 {
116 // copy the cached info
117 *data = ***i;
118 return 0;
119 }
120 }
121
122 return -1;
123 }
124
125 /// update an item in the cache, or insert one if it doesn't exist; oldest item may be removed
126 /// @param [in] data the new item to updated/inserted to the cache
127 /// @return 0 if success, otherwise -1.
128
129 int update(T* data)
130 {
131 srt::sync::ScopedLock cacheguard(m_Lock);
132
133 int key = data->getKey();
134 if (key < 0)
135 return -1;
136 if (key >= m_iMaxSize)
137 key %= m_iHashSize;
138
139 T* curr = NULL;
140
141 ItemPtrList& item_list = m_vHashPtr[key];
142 for (typename ItemPtrList::iterator i = item_list.begin(); i != item_list.end(); ++i)
143 {
144 if (*data == ***i)
145 {
146 // update the existing entry with the new value
147 ***i = *data;
148 curr = **i;
149
150 // remove the current entry
151 m_StorageList.erase(*i);
152 item_list.erase(i);
153
154 // re-insert to the front
155 m_StorageList.push_front(curr);
156 item_list.push_front(m_StorageList.begin());
157
158 return 0;
159 }
160 }
161
162 // create new entry and insert to front
163 curr = data->clone();
164 m_StorageList.push_front(curr);
165 item_list.push_front(m_StorageList.begin());
166
167 ++m_iCurrSize;
168 if (m_iCurrSize >= m_iMaxSize)
169 {
170 // Cache overflow, remove oldest entry.
171 T* last_data = m_StorageList.back();
172 int last_key = last_data->getKey() % m_iHashSize;
173
174 ItemPtrList& last_item_list = m_vHashPtr[last_key];
175 for (typename ItemPtrList::iterator i = last_item_list.begin(); i != last_item_list.end(); ++i)
176 {
177 if (*last_data == ***i)
178 {
179 last_item_list.erase(i);
180 break;
181 }
182 }
183
184 last_data->release();
185 delete last_data;
186 m_StorageList.pop_back();
187 --m_iCurrSize;
188 }
189
190 return 0;
191 }
192
193 private:
194 /// Specify the cache size (i.e., max number of items).
195 /// Private or else must be protected by a lock.
196 /// @param [in] size max cache size.
197 void setSizeLimit(int size)
198 {
199 m_iMaxSize = size;
200 m_iHashSize = size * 3;
201 m_vHashPtr.resize(m_iHashSize);
202 }
203
204 /// Clear all entries in the cache, restore to initialization state.
205 /// Private or else must be protected by a lock.
206 void clear()
207 {
208 for (typename std::list<T*>::iterator i = m_StorageList.begin(); i != m_StorageList.end(); ++i)
209 {
210 (*i)->release();
211 delete *i;
212 }
213 m_StorageList.clear();
214 for (typename std::vector<ItemPtrList>::iterator i = m_vHashPtr.begin(); i != m_vHashPtr.end(); ++i)
215 i->clear();
216 m_iCurrSize = 0;
217 }
218
219 private:
220 std::list<T*> m_StorageList;
221 typedef typename std::list<T*>::iterator ItemPtr;
222 typedef std::list<ItemPtr> ItemPtrList;
223 std::vector<ItemPtrList> m_vHashPtr;
224
225 int m_iMaxSize;
226 int m_iHashSize;
227 int m_iCurrSize;
228
229 srt::sync::Mutex m_Lock;
230
231 private:
232 CCache(const CCache&);
233 CCache& operator=(const CCache&);
234 };
235
236 class CInfoBlock
237 {
238 public:
239 uint32_t m_piIP[4]; // IP address, machine read only, not human readable format.
240 int m_iIPversion; // Address family: AF_INET or AF_INET6.
241 uint64_t m_ullTimeStamp; // Last update time.
242 int m_iSRTT; // Smoothed RTT.
243 int m_iBandwidth; // Estimated link bandwidth.
244 int m_iLossRate; // Average loss rate.
245 int m_iReorderDistance; // Packet reordering distance.
246 double m_dInterval; // Inter-packet time (Congestion Control).
247 double m_dCWnd; // Congestion window size (Congestion Control).
248
249 public:
250 CInfoBlock() {} // NOTE: leaves uninitialized
251 CInfoBlock& copyFrom(const CInfoBlock& obj);
252 CInfoBlock(const CInfoBlock& src) { copyFrom(src); }
253 CInfoBlock& operator=(const CInfoBlock& src) { return copyFrom(src); }
254 bool operator==(const CInfoBlock& obj) const;
255 CInfoBlock* clone();
256 int getKey();
257 void release() {}
258
259 public:
260 /// convert sockaddr structure to an integer array
261 /// @param [in] addr network address
262 /// @param [in] ver IP version
263 /// @param [out] ip the result machine readable IP address in integer array
264
265 static void convert(const sockaddr_any& addr, uint32_t ip[4]);
266 };
267
268 } // namespace srt
269
270 #endif