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