SHOGUN
v3.2.0
|
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 <shogun/lib/common.h> 00015 #include <shogun/io/SGIO.h> 00016 #include <shogun/mathematics/Math.h> 00017 #include <shogun/base/SGObject.h> 00018 00019 #include <stdlib.h> 00020 00021 namespace shogun 00022 { 00031 template<class T> class CCache : public CSGObject 00032 { 00034 struct TEntry 00035 { 00037 int64_t usage_count; 00039 bool locked; 00041 T* obj; 00042 }; 00043 00044 public: 00046 CCache() :CSGObject() 00047 { 00048 SG_UNSTABLE("CCache::CCache()", "\n") 00049 00050 cache_block=NULL; 00051 lookup_table=NULL; 00052 cache_table=NULL; 00053 cache_is_full=false; 00054 nr_cache_lines=0; 00055 entry_size=0; 00056 00057 set_generic<T>(); 00058 } 00059 00070 CCache(int64_t cache_size, int64_t obj_size, int64_t num_entries) 00071 : CSGObject() 00072 { 00073 if (cache_size==0 || obj_size==0 || num_entries==0) 00074 { 00075 SG_INFO("doing without cache.\n") 00076 cache_block=NULL; 00077 lookup_table=NULL; 00078 cache_table=NULL; 00079 cache_is_full=false; 00080 nr_cache_lines=0; 00081 entry_size=0; 00082 return; 00083 } 00084 00085 entry_size=obj_size; 00086 nr_cache_lines=CMath::min((int64_t) (cache_size*1024*1024/obj_size/sizeof(T)), num_entries+1); 00087 00088 SG_INFO("creating %d cache lines (total size: %ld byte)\n", nr_cache_lines, nr_cache_lines*obj_size*sizeof(T)) 00089 cache_block=SG_MALLOC(T, obj_size*nr_cache_lines); 00090 lookup_table=SG_MALLOC(TEntry, num_entries); 00091 cache_table=SG_MALLOC(TEntry*, nr_cache_lines); 00092 00093 ASSERT(cache_block) 00094 ASSERT(lookup_table) 00095 ASSERT(cache_table) 00096 00097 int64_t i; 00098 for (i=0; i<nr_cache_lines; i++) 00099 cache_table[i]=NULL; 00100 00101 for (i=0; i<num_entries; i++) 00102 { 00103 lookup_table[i].usage_count=-1; 00104 lookup_table[i].locked=false; 00105 lookup_table[i].obj=NULL; 00106 } 00107 cache_is_full=false; 00108 00109 //reserve the very last cache line 00110 //as scratch buffer 00111 nr_cache_lines--; 00112 00113 set_generic<T>(); 00114 } 00115 00116 virtual ~CCache() 00117 { 00118 SG_FREE(cache_block); 00119 SG_FREE(lookup_table); 00120 SG_FREE(cache_table); 00121 } 00122 00128 inline bool is_cached(int64_t number) 00129 { 00130 return (lookup_table && lookup_table[number].obj); 00131 } 00132 00138 inline T* lock_entry(int64_t number) 00139 { 00140 if (lookup_table) 00141 { 00142 lookup_table[number].usage_count++; 00143 lookup_table[number].locked=true; 00144 return lookup_table[number].obj; 00145 } 00146 else 00147 return NULL; 00148 } 00149 00154 inline void unlock_entry(int64_t number) 00155 { 00156 if (lookup_table) 00157 lookup_table[number].locked=false; 00158 } 00159 00167 T* set_entry(int64_t number) 00168 { 00169 if (lookup_table) 00170 { 00171 // first look for the element with smallest usage count 00172 int64_t min_idx=0; 00173 int64_t min=-1; 00174 bool found_free_line=false; 00175 00176 int64_t start=0; 00177 for (start=0; start<nr_cache_lines; start++) 00178 { 00179 if (!cache_table[start]) 00180 { 00181 min_idx=start; 00182 min=-1; 00183 found_free_line=true; 00184 break; 00185 } 00186 else 00187 { 00188 if (!cache_table[start]->locked) 00189 { 00190 min=cache_table[start]->usage_count; 00191 min_idx=start; 00192 found_free_line=true; 00193 break; 00194 } 00195 } 00196 } 00197 00198 for (int64_t i=start; i<nr_cache_lines; i++) 00199 { 00200 if (!cache_table[i]) 00201 { 00202 min_idx=i; 00203 min=-1; 00204 found_free_line=true; 00205 break; 00206 } 00207 else 00208 { 00209 int64_t v=cache_table[i]->usage_count; 00210 00211 if (v<min && !cache_table[i]->locked) 00212 { 00213 min=v; 00214 min_idx=i; 00215 found_free_line=true; 00216 } 00217 } 00218 } 00219 00220 if (cache_table[nr_cache_lines-1]) //since this is an indicator for a full cache 00221 cache_is_full=true; 00222 00223 if (found_free_line) 00224 { 00225 // and overwrite it. 00226 if ( (lookup_table[number].usage_count-min) < 5 && cache_is_full && ! (cache_table[nr_cache_lines] && cache_table[nr_cache_lines]->locked)) 00227 min_idx=nr_cache_lines; //scratch entry 00228 00229 if (cache_table[min_idx]) 00230 cache_table[min_idx]->obj=NULL; 00231 00232 cache_table[min_idx]=&lookup_table[number]; 00233 lookup_table[number].obj=&cache_block[entry_size*min_idx]; 00234 00235 //lock cache entry; 00236 lookup_table[number].usage_count=0; 00237 lookup_table[number].locked=true; 00238 return lookup_table[number].obj; 00239 } 00240 else 00241 return NULL; 00242 } 00243 else 00244 return NULL; 00245 } 00246 00248 virtual const char* get_name() const { return "Cache"; } 00249 00250 protected: 00252 bool cache_is_full; 00254 int64_t entry_size; 00256 int64_t nr_cache_lines; 00258 TEntry* lookup_table; 00260 TEntry** cache_table; 00262 T* cache_block; 00263 }; 00264 } 00265 #endif