Root/
Source at commit 1322 created 12 years 7 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␊ |
26 | int ObjCache::misses = 0;␊ |
27 | int ObjCache::hits = 0;␊ |
28 | #endif␊ |
29 | ␊ |
30 | //----------------------------------------------------------------------␊ |
31 | ␊ |
32 | ObjCache::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 | ␊ |
47 | ObjCache::~ObjCache()␊ |
48 | {␊ |
49 | delete[] m_cache;␊ |
50 | delete[] m_hash;␊ |
51 | }␊ |
52 | ␊ |
53 | int 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 | ␊ |
109 | void 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␊ |
128 | void 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␊ |
152 | void 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 | ␊ |
158 | void 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 | ␊ |
178 | unsigned 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 | ␊ |
209 | ObjCache::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 | ␊ |
228 | ObjCache::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 | ␊ |
258 | void 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␊ |
288 | int 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 |