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