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(void) :CSGObject() 00047 { 00048 SG_UNSTABLE("CCache::CCache(void)", "\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 00068 CCache(int64_t cache_size, int64_t obj_size, int64_t num_entries) 00069 : CSGObject() 00070 { 00071 if (cache_size==0 || obj_size==0 || num_entries==0) 00072 { 00073 SG_INFO("doing without cache.\n"); 00074 cache_block=NULL; 00075 lookup_table=NULL; 00076 cache_table=NULL; 00077 cache_is_full=false; 00078 nr_cache_lines=0; 00079 entry_size=0; 00080 return; 00081 } 00082 00083 entry_size=obj_size; 00084 nr_cache_lines=CMath::min((int64_t) (cache_size*1024*1024/obj_size/sizeof(T)), num_entries+1); 00085 00086 SG_INFO("creating %d cache lines (total size: %ld byte)\n", nr_cache_lines, nr_cache_lines*obj_size*sizeof(T)); 00087 cache_block=SG_MALLOC(T, obj_size*nr_cache_lines); 00088 lookup_table=SG_MALLOC(TEntry, num_entries); 00089 cache_table=SG_MALLOC(TEntry*, nr_cache_lines); 00090 00091 ASSERT(cache_block); 00092 ASSERT(lookup_table); 00093 ASSERT(cache_table); 00094 00095 int64_t i; 00096 for (i=0; i<nr_cache_lines; i++) 00097 cache_table[i]=NULL; 00098 00099 for (i=0; i<num_entries; i++) 00100 { 00101 lookup_table[i].usage_count=-1; 00102 lookup_table[i].locked=false; 00103 lookup_table[i].obj=NULL; 00104 } 00105 cache_is_full=false; 00106 00107 //reserve the very last cache line 00108 //as scratch buffer 00109 nr_cache_lines--; 00110 } 00111 00112 virtual ~CCache() 00113 { 00114 SG_FREE(cache_block); 00115 SG_FREE(lookup_table); 00116 SG_FREE(cache_table); 00117 } 00118 00124 inline bool is_cached(int64_t number) 00125 { 00126 return (lookup_table && lookup_table[number].obj); 00127 } 00128 00134 inline T* lock_entry(int64_t number) 00135 { 00136 if (lookup_table) 00137 { 00138 lookup_table[number].usage_count++; 00139 lookup_table[number].locked=true; 00140 return lookup_table[number].obj; 00141 } 00142 else 00143 return NULL; 00144 } 00145 00150 inline void unlock_entry(int64_t number) 00151 { 00152 if (lookup_table) 00153 lookup_table[number].locked=false; 00154 } 00155 00163 T* set_entry(int64_t number) 00164 { 00165 if (lookup_table) 00166 { 00167 // first look for the element with smallest usage count 00168 //int64_t min_idx=((nr_cache_lines-1)*random())/(RAND_MAX+1); //avoid the last elem and the scratch line 00169 int64_t min_idx=0; 00170 int64_t min=-1; 00171 bool found_free_line=false; 00172 00173 int64_t start=0; 00174 for (start=0; start<nr_cache_lines; start++) 00175 { 00176 if (!cache_table[start]) 00177 { 00178 min_idx=start; 00179 min=-1; 00180 found_free_line=true; 00181 break; 00182 } 00183 else 00184 { 00185 if (!cache_table[start]->locked) 00186 { 00187 min=cache_table[start]->usage_count; 00188 min_idx=start; 00189 found_free_line=true; 00190 break; 00191 } 00192 } 00193 } 00194 00195 for (int64_t i=start; i<nr_cache_lines; i++) 00196 { 00197 if (!cache_table[i]) 00198 { 00199 min_idx=i; 00200 min=-1; 00201 found_free_line=true; 00202 break; 00203 } 00204 else 00205 { 00206 int64_t v=cache_table[i]->usage_count; 00207 00208 if (v<min && !cache_table[i]->locked) 00209 { 00210 min=v; 00211 min_idx=i; 00212 found_free_line=true; 00213 } 00214 } 00215 } 00216 00217 if (cache_table[nr_cache_lines-1]) //since this is an indicator for a full cache 00218 cache_is_full=true; 00219 00220 if (found_free_line) 00221 { 00222 // and overwrite it. 00223 if ( (lookup_table[number].usage_count-min) < 5 && cache_is_full && ! (cache_table[nr_cache_lines] && cache_table[nr_cache_lines]->locked)) 00224 min_idx=nr_cache_lines; //scratch entry 00225 00226 if (cache_table[min_idx]) 00227 cache_table[min_idx]->obj=NULL; 00228 00229 cache_table[min_idx]=&lookup_table[number]; 00230 lookup_table[number].obj=&cache_block[entry_size*min_idx]; 00231 00232 //lock cache entry; 00233 lookup_table[number].usage_count=0; 00234 lookup_table[number].locked=true; 00235 return lookup_table[number].obj; 00236 } 00237 else 00238 return NULL; 00239 } 00240 else 00241 return NULL; 00242 } 00243 00245 inline virtual const char* get_name() const { return "Cache"; } 00246 00247 protected: 00249 bool cache_is_full; 00251 int64_t entry_size; 00253 int64_t nr_cache_lines; 00255 TEntry* lookup_table; 00257 TEntry** cache_table; 00259 T* cache_block; 00260 }; 00261 } 00262 #endif