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-2009 Soeren Sonnenburg 00008 * Copyright (C) 1999-2009 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 00029 template<class T> class CCache : public CSGObject 00030 { 00032 struct TEntry 00033 { 00035 int64_t usage_count; 00037 bool locked; 00039 T* obj; 00040 }; 00041 00042 public: 00053 CCache(int64_t cache_size, int64_t obj_size, int64_t num_entries) 00054 : CSGObject() 00055 { 00056 if (cache_size==0 || obj_size==0 || num_entries==0) 00057 { 00058 SG_INFO("doing without cache.\n"); 00059 cache_block=NULL; 00060 lookup_table=NULL; 00061 cache_table=NULL; 00062 cache_is_full=false; 00063 nr_cache_lines=0; 00064 entry_size=0; 00065 return; 00066 } 00067 00068 entry_size=obj_size; 00069 nr_cache_lines=CMath::min((int64_t) (cache_size*1024*1024/obj_size/sizeof(T)), num_entries+1); 00070 00071 SG_INFO("creating %d cache lines (total size: %ld byte)\n", nr_cache_lines, nr_cache_lines*obj_size*sizeof(T)); 00072 cache_block=new T[obj_size*nr_cache_lines]; 00073 lookup_table=new TEntry[num_entries]; 00074 cache_table=new TEntry*[nr_cache_lines]; 00075 00076 ASSERT(cache_block); 00077 ASSERT(lookup_table); 00078 ASSERT(cache_table); 00079 00080 int64_t i; 00081 for (i=0; i<nr_cache_lines; i++) 00082 cache_table[i]=NULL; 00083 00084 for (i=0; i<num_entries; i++) 00085 { 00086 lookup_table[i].usage_count=-1; 00087 lookup_table[i].locked=false; 00088 lookup_table[i].obj=NULL; 00089 } 00090 cache_is_full=false; 00091 00092 //reserve the very last cache line 00093 //as scratch buffer 00094 nr_cache_lines--; 00095 } 00096 00097 virtual ~CCache() 00098 { 00099 delete[] cache_block; 00100 delete[] lookup_table; 00101 delete[] cache_table; 00102 } 00103 00109 inline bool is_cached(int64_t number) 00110 { 00111 return (lookup_table && lookup_table[number].obj); 00112 } 00113 00119 inline T* lock_entry(int64_t number) 00120 { 00121 if (lookup_table) 00122 { 00123 lookup_table[number].usage_count++; 00124 lookup_table[number].locked=true; 00125 return lookup_table[number].obj; 00126 } 00127 else 00128 return NULL; 00129 } 00130 00135 inline void unlock_entry(int64_t number) 00136 { 00137 if (lookup_table) 00138 lookup_table[number].locked=false; 00139 } 00140 00148 T* set_entry(int64_t number) 00149 { 00150 if (lookup_table) 00151 { 00152 // first look for the element with smallest usage count 00153 //int64_t min_idx=((nr_cache_lines-1)*random())/(RAND_MAX+1); //avoid the last elem and the scratch line 00154 int64_t min_idx=0; 00155 int64_t min=-1; 00156 bool found_free_line=false; 00157 00158 int64_t start=0; 00159 for (start=0; start<nr_cache_lines; start++) 00160 { 00161 if (!cache_table[start]) 00162 { 00163 min_idx=start; 00164 min=-1; 00165 found_free_line=true; 00166 break; 00167 } 00168 else 00169 { 00170 if (!cache_table[start]->locked) 00171 { 00172 min=cache_table[start]->usage_count; 00173 min_idx=start; 00174 found_free_line=true; 00175 break; 00176 } 00177 } 00178 } 00179 00180 for (int64_t i=start; i<nr_cache_lines; i++) 00181 { 00182 if (!cache_table[i]) 00183 { 00184 min_idx=i; 00185 min=-1; 00186 found_free_line=true; 00187 break; 00188 } 00189 else 00190 { 00191 int64_t v=cache_table[i]->usage_count; 00192 00193 if (v<min && !cache_table[i]->locked) 00194 { 00195 min=v; 00196 min_idx=i; 00197 found_free_line=true; 00198 } 00199 } 00200 } 00201 00202 if (cache_table[nr_cache_lines-1]) //since this is an indicator for a full cache 00203 cache_is_full=true; 00204 00205 if (found_free_line) 00206 { 00207 // and overwrite it. 00208 if ( (lookup_table[number].usage_count-min) < 5 && cache_is_full && ! (cache_table[nr_cache_lines] && cache_table[nr_cache_lines]->locked)) 00209 min_idx=nr_cache_lines; //scratch entry 00210 00211 if (cache_table[min_idx]) 00212 cache_table[min_idx]->obj=NULL; 00213 00214 cache_table[min_idx]=&lookup_table[number]; 00215 lookup_table[number].obj=&cache_block[entry_size*min_idx]; 00216 00217 //lock cache entry; 00218 lookup_table[number].usage_count=0; 00219 lookup_table[number].locked=true; 00220 return lookup_table[number].obj; 00221 } 00222 else 00223 return NULL; 00224 } 00225 else 00226 return NULL; 00227 } 00228 00230 inline virtual const char* get_name() const { return "Cache"; } 00231 00232 protected: 00234 bool cache_is_full; 00236 int64_t entry_size; 00238 int64_t nr_cache_lines; 00240 TEntry* lookup_table; 00242 TEntry** cache_table; 00244 T* cache_block; 00245 }; 00246 #endif