Chameleon

Chameleon Svn Source Tree

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

Source at commit 1322 created 12 years 8 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