SHOGUN  v3.0.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Cache.h
Go to the documentation of this file.
1 /*
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 3 of the License, or
5  * (at your option) any later version.
6  *
7  * Written (W) 1999-2009 Soeren Sonnenburg
8  * Copyright (C) 1999-2009 Fraunhofer Institute FIRST and Max-Planck-Society
9  */
10 
11 #ifndef _CACHE_H__
12 #define _CACHE_H__
13 
14 #include <shogun/lib/common.h>
15 #include <shogun/io/SGIO.h>
17 #include <shogun/base/SGObject.h>
18 
19 #include <stdlib.h>
20 
21 namespace shogun
22 {
31 template<class T> class CCache : public CSGObject
32 {
34  struct TEntry
35  {
37  int64_t usage_count;
39  bool locked;
41  T* obj;
42  };
43 
44  public:
47  {
48  SG_UNSTABLE("CCache::CCache()", "\n")
49 
50  cache_block=NULL;
51  lookup_table=NULL;
52  cache_table=NULL;
53  cache_is_full=false;
55  entry_size=0;
56 
57  set_generic<T>();
58  }
59 
70  CCache(int64_t cache_size, int64_t obj_size, int64_t num_entries)
71  : CSGObject()
72  {
73  if (cache_size==0 || obj_size==0 || num_entries==0)
74  {
75  SG_INFO("doing without cache.\n")
76  cache_block=NULL;
77  lookup_table=NULL;
78  cache_table=NULL;
79  cache_is_full=false;
81  entry_size=0;
82  return;
83  }
84 
85  entry_size=obj_size;
86  nr_cache_lines=CMath::min((int64_t) (cache_size*1024*1024/obj_size/sizeof(T)), num_entries+1);
87 
88  SG_INFO("creating %d cache lines (total size: %ld byte)\n", nr_cache_lines, nr_cache_lines*obj_size*sizeof(T))
89  cache_block=SG_MALLOC(T, obj_size*nr_cache_lines);
90  lookup_table=SG_MALLOC(TEntry, num_entries);
91  cache_table=SG_MALLOC(TEntry*, nr_cache_lines);
92 
96 
97  int64_t i;
98  for (i=0; i<nr_cache_lines; i++)
99  cache_table[i]=NULL;
100 
101  for (i=0; i<num_entries; i++)
102  {
103  lookup_table[i].usage_count=-1;
104  lookup_table[i].locked=false;
105  lookup_table[i].obj=NULL;
106  }
107  cache_is_full=false;
108 
109  //reserve the very last cache line
110  //as scratch buffer
111  nr_cache_lines--;
112 
113  set_generic<T>();
114  }
115 
116  virtual ~CCache()
117  {
118  SG_FREE(cache_block);
119  SG_FREE(lookup_table);
120  SG_FREE(cache_table);
121  }
122 
128  inline bool is_cached(int64_t number)
129  {
130  return (lookup_table && lookup_table[number].obj);
131  }
132 
138  inline T* lock_entry(int64_t number)
139  {
140  if (lookup_table)
141  {
142  lookup_table[number].usage_count++;
143  lookup_table[number].locked=true;
144  return lookup_table[number].obj;
145  }
146  else
147  return NULL;
148  }
149 
154  inline void unlock_entry(int64_t number)
155  {
156  if (lookup_table)
157  lookup_table[number].locked=false;
158  }
159 
167  T* set_entry(int64_t number)
168  {
169  if (lookup_table)
170  {
171  // first look for the element with smallest usage count
172  int64_t min_idx=0;
173  int64_t min=-1;
174  bool found_free_line=false;
175 
176  int64_t start=0;
177  for (start=0; start<nr_cache_lines; start++)
178  {
179  if (!cache_table[start])
180  {
181  min_idx=start;
182  min=-1;
183  found_free_line=true;
184  break;
185  }
186  else
187  {
188  if (!cache_table[start]->locked)
189  {
190  min=cache_table[start]->usage_count;
191  min_idx=start;
192  found_free_line=true;
193  break;
194  }
195  }
196  }
197 
198  for (int64_t i=start; i<nr_cache_lines; i++)
199  {
200  if (!cache_table[i])
201  {
202  min_idx=i;
203  min=-1;
204  found_free_line=true;
205  break;
206  }
207  else
208  {
209  int64_t v=cache_table[i]->usage_count;
210 
211  if (v<min && !cache_table[i]->locked)
212  {
213  min=v;
214  min_idx=i;
215  found_free_line=true;
216  }
217  }
218  }
219 
220  if (cache_table[nr_cache_lines-1]) //since this is an indicator for a full cache
221  cache_is_full=true;
222 
223  if (found_free_line)
224  {
225  // and overwrite it.
226  if ( (lookup_table[number].usage_count-min) < 5 && cache_is_full && ! (cache_table[nr_cache_lines] && cache_table[nr_cache_lines]->locked))
227  min_idx=nr_cache_lines; //scratch entry
228 
229  if (cache_table[min_idx])
230  cache_table[min_idx]->obj=NULL;
231 
232  cache_table[min_idx]=&lookup_table[number];
233  lookup_table[number].obj=&cache_block[entry_size*min_idx];
234 
235  //lock cache entry;
236  lookup_table[number].usage_count=0;
237  lookup_table[number].locked=true;
238  return lookup_table[number].obj;
239  }
240  else
241  return NULL;
242  }
243  else
244  return NULL;
245  }
246 
248  virtual const char* get_name() const { return "Cache"; }
249 
250  protected:
254  int64_t entry_size;
256  int64_t nr_cache_lines;
258  TEntry* lookup_table;
260  TEntry** cache_table;
263 };
264 }
265 #endif

SHOGUN Machine Learning Toolbox - Documentation