Root/
Source at commit 1322 created 12 years 7 months ago. By meklort, Add doxygen to utils folder | |
---|---|
1 | /******************************************************************************␊ |
2 | *␊ |
3 | * $Id:$␊ |
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 | #ifndef OBJCACHE_H␊ |
19 | #define OBJCACHE_H␊ |
20 | ␊ |
21 | //#define CACHE_TEST␊ |
22 | //#define CACHE_DEBUG␊ |
23 | #define CACHE_STATS␊ |
24 | ␊ |
25 | /** @brief Cache for objects.␊ |
26 | *␊ |
27 | * This cache is used to decide which objects should remain in␊ |
28 | * memory. It uses a least recently used policy (LRU) to decide␊ |
29 | * which object should make room for a new object when the cache␊ |
30 | * is full. An object should be added using add(), and then use()␊ |
31 | * should be called when the object is used.␊ |
32 | */␊ |
33 | class ObjCache␊ |
34 | {␊ |
35 | private:␊ |
36 | struct CacheNode␊ |
37 | {␊ |
38 | CacheNode() : next(-1), prev(-1), obj(0) {}␊ |
39 | int next;␊ |
40 | int prev;␊ |
41 | void *obj;␊ |
42 | };␊ |
43 | struct HashNode␊ |
44 | {␊ |
45 | HashNode() : head(-1), nextHash(-1), index(-1), obj(0) {}␊ |
46 | int head;␊ |
47 | int nextHash; ␊ |
48 | int index;␊ |
49 | void *obj;␊ |
50 | };␊ |
51 | ␊ |
52 | public:␊ |
53 | /*! Creates the cache. The number of elements in the cache is 2 to ␊ |
54 | * the power of \a logSize. ␊ |
55 | */␊ |
56 | ObjCache(unsigned int logSize);␊ |
57 | ␊ |
58 | /*! Deletes the cache and free all internal data-structures used. */␊ |
59 | ~ObjCache();␊ |
60 | ␊ |
61 | /*! Adds \a obj to the cache. When victim is not null, this object is␊ |
62 | * removed from the cache to make room for \a obj. ␊ |
63 | * Returns a handle to the object, which can be used by the use()␊ |
64 | * function, each time the object is used.␊ |
65 | */␊ |
66 | int add(void *obj,void **victim);␊ |
67 | ␊ |
68 | /*! Indicates that this object is used. This will move the object␊ |
69 | * to the front of the internal LRU list to make sure it is removed last.␊ |
70 | * The parameter \a handle is returned when called add().␊ |
71 | */␊ |
72 | void use(int handle)␊ |
73 | {␊ |
74 | hits++;␊ |
75 | if (handle==m_lastHandle) return;␊ |
76 | m_lastHandle = handle;␊ |
77 | moveToFront(handle);␊ |
78 | }␊ |
79 | ␊ |
80 | /*! Removes the item identified by \a handle from the cache.␊ |
81 | * @see add()␊ |
82 | */␊ |
83 | void del(int handle);␊ |
84 | ␊ |
85 | /*! Debug function. Prints the LRU list */␊ |
86 | void printLRU();␊ |
87 | /*! Print miss/hits statistics */␊ |
88 | void printStats();␊ |
89 | ␊ |
90 | private:␊ |
91 | void moveToFront(int index);␊ |
92 | unsigned int hash(void *addr);␊ |
93 | HashNode *hashFind(void *obj);␊ |
94 | HashNode *hashInsert(void *obj);␊ |
95 | void hashRemove(void *obj);␊ |
96 | ␊ |
97 | CacheNode *m_cache;␊ |
98 | HashNode *m_hash;␊ |
99 | int m_head;␊ |
100 | int m_tail;␊ |
101 | int m_size;␊ |
102 | int m_freeHashNodes;␊ |
103 | int m_freeCacheNodes;␊ |
104 | int m_lastHandle;␊ |
105 | ␊ |
106 | #ifdef CACHE_STATS␊ |
107 | static int misses;␊ |
108 | static int hits;␊ |
109 | #endif␊ |
110 | };␊ |
111 | ␊ |
112 | #endif // OBJCACHE_H␊ |
113 | ␊ |
114 |