Chameleon

Chameleon Svn Source Tree

Root/branches/xZenu/src/util/doxygen/src/objcache.cpp

Source at commit 1322 created 9 years 5 months ago.
By meklort, Add doxygen to utils folder
1/******************************************************************************
2 *
3 * $Id: classlist.cpp,v 1.14 2001/03/19 19:27:39 root Exp $
4 *
5 * Copyright (C) 1997-2011 by Dimitri van Heesch.
6 *
7 * Permission to use, copy, modify, and distribute this software and its
8 * documentation under the terms of the GNU General Public License is hereby
9 * granted. No representations are made about the suitability of this software
10 * for any purpose. It is provided "as is" without express or implied warranty.
11 * See the GNU General Public License for more details.
12 *
13 * Documents produced by Doxygen are derivative works derived from the
14 * input used in their production; they are not affected by this license.
15 *
16 */
17
18#include <stdio.h>
19#include <assert.h>
20#include <qglobal.h>
21#include "objcache.h"
22
23//----------------------------------------------------------------------
24
25#ifdef CACHE_STATS
26int ObjCache::misses = 0;
27int ObjCache::hits = 0;
28#endif
29
30//----------------------------------------------------------------------
31
32ObjCache::ObjCache(unsigned int logSize)
33 : m_head(-1), m_tail(-1), //m_numEntries(0),
34 m_size(1<<logSize), m_freeHashNodes(0), m_freeCacheNodes(0), m_lastHandle(-1)
35{
36 int i;
37 m_cache = new CacheNode[m_size];
38 m_hash = new HashNode[m_size];
39 // add all items to list of free buckets
40 for (i=0;i<m_size-1;i++)
41 {
42 m_hash[i].nextHash = i+1;
43 m_cache[i].next = i+1;
44 }
45}
46
47ObjCache::~ObjCache()
48{
49 delete[] m_cache;
50 delete[] m_hash;
51}
52
53int ObjCache::add(void *obj,void **victim)
54{
55 *victim=0;
56
57 HashNode *hnode = hashFind(obj);
58 //printf("hnode=%p\n",hnode);
59 if (hnode) // move object to the front of the LRU list, since it is used
60 // most recently
61 {
62 //printf("moveToFront=%d\n",hnode->index);
63 moveToFront(hnode->index);
64#ifdef CACHE_STATS
65 hits++;
66#endif
67 }
68 else // object not in the cache.
69 {
70 void *lruObj=0;
71 if (m_freeCacheNodes!=-1) // cache not full -> add element to the cache
72 {
73 // remove element from free list
74 int index = m_freeCacheNodes;
75 m_freeCacheNodes = m_cache[index].next;
76
77 // add to head of the list
78 if (m_tail==-1)
79 {
80 m_tail = index;
81 }
82 m_cache[index].prev = -1;
83 m_cache[index].next = m_head;
84 if (m_head!=-1)
85 {
86 m_cache[m_head].prev = index;
87 }
88 m_head = index;
89 }
90 else // cache full -> replace element in the cache
91 {
92 //printf("Cache full!\n");
93 lruObj = m_cache[m_tail].obj;
94 hashRemove(lruObj);
95 moveToFront(m_tail); // m_tail indexes the emptied element, which becomes m_head
96 }
97 //printf("numEntries=%d size=%d\n",m_numEntries,m_size);
98 m_cache[m_head].obj = obj;
99 hnode = hashInsert(obj);
100 hnode->index = m_head;
101 *victim = lruObj;
102#ifdef CACHE_STATS
103 misses++;
104#endif
105 }
106 return m_head;
107}
108
109void ObjCache::del(int index)
110{
111 assert(index!=-1);
112 assert(m_cache[index].obj!=0);
113 hashRemove(m_cache[index].obj);
114 moveToFront(index);
115 m_head = m_cache[index].next;
116 if (m_head==-1)
117 m_tail=-1;
118 else
119 m_cache[m_head].prev=-1;
120 m_cache[index].obj=0;
121 m_cache[index].prev=-1;
122 m_cache[index].next = m_freeCacheNodes;
123 m_freeCacheNodes = index;
124}
125
126#ifdef CACHE_DEBUG
127#define cache_debug_printf printf
128void ObjCache::printLRU()
129{
130 cache_debug_printf("MRU->LRU: ");
131 int index = m_head;
132 while (index!=-1)
133 {
134 cache_debug_printf("%d=%p ",index,m_cache[index].obj);
135 index = m_cache[index].next;
136 }
137 cache_debug_printf("\n");
138
139 cache_debug_printf("LRU->MRU: ");
140 index = m_tail;
141 while (index!=-1)
142 {
143 cache_debug_printf("%d=%p ",index,m_cache[index].obj);
144 index = m_cache[index].prev;
145 }
146 cache_debug_printf("\n");
147}
148#endif
149
150#ifdef CACHE_STATS
151#define cache_stats_printf printf
152void ObjCache::printStats()
153{
154 cache_stats_printf("ObjCache: hits=%d misses=%d hit ratio=%f\n",hits,misses,hits*100.0/(hits+misses));
155}
156#endif
157
158void ObjCache::moveToFront(int index)
159{
160 int prev,next;
161 if (m_head!=index)
162 {
163 next = m_cache[index].next;
164 prev = m_cache[index].prev;
165
166 // de-chain node at index
167 m_cache[prev].next = next;
168 if (next!=-1) m_cache[next].prev = prev; else m_tail = prev;
169
170 // add to head
171 m_cache[index].prev = -1;
172 m_cache[index].next = m_head;
173 m_cache[m_head].prev = index;
174 m_head = index;
175 }
176}
177
178unsigned int ObjCache::hash(void *addr)
179{
180 static bool isPtr64 = sizeof(addr)==8;
181 if (isPtr64)
182 {
183 uint64 key = (uint64)addr;
184 // Thomas Wang's 64 bit Mix Function
185 key += ~(key << 32);
186 key ^= (key >> 22);
187 key += ~(key << 13);
188 key ^= (key >> 8);
189 key += (key << 3);
190 key ^= (key >> 15);
191 key += ~(key << 27);
192 key ^= (key >> 31);
193 return key & (m_size-1);
194 }
195 else
196 {
197 // Thomas Wang's 32 bit Mix Function
198 unsigned long key = (unsigned long)addr;
199 key += ~(key << 15);
200 key ^= (key >> 10);
201 key += (key << 3);
202 key ^= (key >> 6);
203 key += ~(key << 11);
204 key ^= (key >> 16);
205 return key & (m_size-1);
206 }
207}
208
209ObjCache::HashNode *ObjCache::hashFind(void *obj)
210{
211 HashNode *node = 0;
212 int index = m_hash[hash(obj)].head;
213 //printf("hashFind: obj=%p index=%d\n",obj,index);
214 while (index!=-1 &&
215 m_hash[index].obj!=obj
216 ) // search for right object in the list
217 {
218 index = m_hash[index].nextHash;
219 }
220 // found the obj at index, so it is in the cache!
221 if (index!=-1)
222 {
223 node = &m_hash[index];
224 }
225 return node;
226}
227
228ObjCache::HashNode *ObjCache::hashInsert(void *obj)
229{
230 int index = hash(obj);
231 //printf("Inserting %p index=%d\n",obj,index);
232
233 // remove element from empty list
234 int newElement = m_freeHashNodes;
235 assert(newElement!=-1);
236 m_freeHashNodes = m_hash[m_freeHashNodes].nextHash;
237
238 if (m_hash[index].head!=-1) // hash collision -> goto end of the list
239 {
240 index = m_hash[index].head;
241 while (m_hash[index].nextHash!=-1)
242 {
243 index = m_hash[index].nextHash;
244 }
245 // add to end of the list
246 m_hash[index].nextHash = newElement;
247 }
248 else // first element in the hash list
249 {
250 m_hash[index].head = newElement;
251 }
252 // add to the end of the list
253 m_hash[newElement].nextHash = -1;
254 m_hash[newElement].obj = obj;
255 return &m_hash[newElement];
256}
257
258void ObjCache::hashRemove(void *obj)
259{
260 int index = hash(obj);
261
262 // find element
263 int curIndex = m_hash[index].head;
264 int prevIndex=-1;
265 while (m_hash[curIndex].obj!=obj)
266 {
267 prevIndex = curIndex;
268 curIndex = m_hash[curIndex].nextHash;
269 }
270
271 if (prevIndex==-1) // remove from start
272 {
273 m_hash[index].head = m_hash[curIndex].nextHash;
274 }
275 else // remove in the middle
276 {
277 m_hash[prevIndex].nextHash = m_hash[curIndex].nextHash;
278 }
279
280 // add curIndex element to empty list
281 m_hash[curIndex].nextHash = m_freeHashNodes;
282 m_hash[curIndex].index = -1;
283 m_hash[curIndex].obj = 0;
284 m_freeHashNodes = curIndex;
285}
286
287#ifdef CACHE_TEST
288int main()
289{
290 int i;
291 struct obj
292 {
293 obj() : handle(-1) {}
294 int handle;
295 };
296 obj *objs = new obj[100];
297 ObjCache c(3);
298 for (i=0;i<32;i++)
299 {
300 int objId=(i%3)+(i>>2)*4;
301 printf("------- use(%d=%p)--------\n",objId,&objs[objId]);
302#ifdef CACHE_DEBUG
303 c.printLRU();
304#endif
305 obj *victim=0;
306 if (objs[objId].handle==-1)
307 {
308 objs[objId].handle = c.add(&objs[objId],(void**)&victim);
309 if (victim) victim->handle=-1;
310 }
311 else
312 {
313 c.use(objs[objId].handle);
314 }
315 printf("i=%d objId=%d using %p victim=%p\n",i,objId,&objs[objId],victim);
316 }
317 for (i=0;i<100;i++)
318 {
319 if (objs[i].handle!=-1)
320 {
321 printf("------ del objId=%d handle=%d ------\n",i,objs[i].handle);
322 c.del(objs[i].handle);
323 objs[i].handle=-1;
324#ifdef CACHE_DEBUG
325 c.printLRU();
326#endif
327 }
328 }
329 c.printStats();
330 return 0;
331}
332#endif
333

Archive Download this file

Revision: 1322