00001 /* 00002 * This program is free software; you can redistribute it and/or modify 00003 * it under the terms of the GNU General Public License as published by 00004 * the Free Software Foundation; either version 3 of the License, or 00005 * (at your option) any later version. 00006 * 00007 * Written (W) 1999-2008 Soeren Sonnenburg 00008 * Copyright (C) 1999-2008 Fraunhofer Institute FIRST and Max-Planck-Society 00009 */ 00010 00011 #ifndef _CACHE_H__ 00012 #define _CACHE_H__ 00013 00014 #include "lib/common.h" 00015 #include "lib/io.h" 00016 #include "lib/Mathematics.h" 00017 #include "base/SGObject.h" 00018 00019 #include <stdlib.h> 00020 00022 template<class T> class CCache : public CSGObject 00023 { 00025 struct TEntry 00026 { 00028 LONG usage_count; 00030 bool locked; 00032 T* obj; 00033 }; 00034 00035 public: 00046 CCache(LONG cache_size, LONG obj_size, LONG num_entries) 00047 : CSGObject() 00048 { 00049 if (cache_size==0 || obj_size==0 || num_entries==0) 00050 { 00051 SG_INFO("doing without cache.\n"); 00052 cache_block=NULL; 00053 lookup_table=NULL; 00054 cache_table=NULL; 00055 cache_is_full=false; 00056 nr_cache_lines=0; 00057 entry_size=0; 00058 return; 00059 } 00060 00061 entry_size=obj_size; 00062 nr_cache_lines=CMath::min((LONG) (cache_size*1024*1024/obj_size/sizeof(T)), num_entries+1); 00063 00064 SG_INFO("creating %d cache lines (total size: %ld byte)\n", nr_cache_lines, nr_cache_lines*obj_size*sizeof(T)); 00065 cache_block=new T[obj_size*nr_cache_lines]; 00066 lookup_table=new TEntry[num_entries]; 00067 cache_table=new TEntry*[nr_cache_lines]; 00068 00069 ASSERT(cache_block); 00070 ASSERT(lookup_table); 00071 ASSERT(cache_table); 00072 00073 LONG i; 00074 for (i=0; i<nr_cache_lines; i++) 00075 cache_table[i]=NULL; 00076 00077 for (i=0; i<num_entries; i++) 00078 { 00079 lookup_table[i].usage_count=-1; 00080 lookup_table[i].locked=false; 00081 lookup_table[i].obj=NULL; 00082 } 00083 cache_is_full=false; 00084 00085 //reserve the very last cache line 00086 //as scratch buffer 00087 nr_cache_lines--; 00088 } 00089 00090 ~CCache() 00091 { 00092 delete[] cache_block; 00093 delete[] lookup_table; 00094 delete[] cache_table; 00095 } 00096 00102 inline bool is_cached(LONG number) 00103 { 00104 return (lookup_table && lookup_table[number].obj); 00105 } 00106 00112 inline T* lock_entry(LONG number) 00113 { 00114 if (lookup_table) 00115 { 00116 lookup_table[number].usage_count++; 00117 lookup_table[number].locked=true; 00118 return lookup_table[number].obj; 00119 } 00120 else 00121 return NULL; 00122 } 00123 00128 inline void unlock_entry(LONG number) 00129 { 00130 if (lookup_table) 00131 lookup_table[number].locked=false; 00132 } 00133 00141 T* set_entry(LONG number) 00142 { 00143 if (lookup_table) 00144 { 00145 // first look for the element with smallest usage count 00146 //LONG min_idx=((nr_cache_lines-1)*random())/(RAND_MAX+1); //avoid the last elem and the scratch line 00147 LONG min_idx=0; 00148 LONG min=-1; 00149 bool found_free_line=false; 00150 00151 LONG start=0; 00152 for (start=0; start<nr_cache_lines; start++) 00153 { 00154 if (!cache_table[start]) 00155 { 00156 min_idx=start; 00157 min=-1; 00158 found_free_line=true; 00159 break; 00160 } 00161 else 00162 { 00163 if (!cache_table[start]->locked) 00164 { 00165 min=cache_table[start]->usage_count; 00166 min_idx=start; 00167 found_free_line=true; 00168 break; 00169 } 00170 } 00171 } 00172 00173 for (LONG i=start; i<nr_cache_lines; i++) 00174 { 00175 if (!cache_table[i]) 00176 { 00177 min_idx=i; 00178 min=-1; 00179 found_free_line=true; 00180 break; 00181 } 00182 else 00183 { 00184 LONG v=cache_table[i]->usage_count; 00185 00186 if (v<min && !cache_table[i]->locked) 00187 { 00188 min=v; 00189 min_idx=i; 00190 found_free_line=true; 00191 } 00192 } 00193 } 00194 00195 if (cache_table[nr_cache_lines-1]) //since this is an indicator for a full cache 00196 cache_is_full=true; 00197 00198 if (found_free_line) 00199 { 00200 // and overwrite it. 00201 if ( (lookup_table[number].usage_count-min) < 5 && cache_is_full && ! (cache_table[nr_cache_lines] && cache_table[nr_cache_lines]->locked)) 00202 min_idx=nr_cache_lines; //scratch entry 00203 00204 if (cache_table[min_idx]) 00205 cache_table[min_idx]->obj=NULL; 00206 00207 cache_table[min_idx]=&lookup_table[number]; 00208 lookup_table[number].obj=&cache_block[entry_size*min_idx]; 00209 00210 //lock cache entry; 00211 lookup_table[number].usage_count=0; 00212 lookup_table[number].locked=true; 00213 return lookup_table[number].obj; 00214 } 00215 else 00216 return NULL; 00217 } 00218 else 00219 return NULL; 00220 } 00221 00223 bool cache_is_full; 00225 LONG entry_size; 00227 LONG nr_cache_lines; 00229 TEntry* lookup_table; 00231 TEntry** cache_table; 00233 T* cache_block; 00234 }; 00235 #endif