SHOGUN  3.2.1
 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/config.h>
15 
16 #include <shogun/lib/common.h>
17 #include <shogun/io/SGIO.h>
19 #include <shogun/base/SGObject.h>
20 
21 #include <stdlib.h>
22 
23 namespace shogun
24 {
33 template<class T> class CCache : public CSGObject
34 {
36  struct TEntry
37  {
39  int64_t usage_count;
41  bool locked;
43  T* obj;
44  };
45 
46  public:
49  {
50  SG_UNSTABLE("CCache::CCache()", "\n")
51 
52  cache_block=NULL;
53  lookup_table=NULL;
54  cache_table=NULL;
55  cache_is_full=false;
57  entry_size=0;
58 
59  set_generic<T>();
60  }
61 
72  CCache(int64_t cache_size, int64_t obj_size, int64_t num_entries)
73  : CSGObject()
74  {
75  if (cache_size==0 || obj_size==0 || num_entries==0)
76  {
77  SG_INFO("doing without cache.\n")
78  cache_block=NULL;
79  lookup_table=NULL;
80  cache_table=NULL;
81  cache_is_full=false;
83  entry_size=0;
84  return;
85  }
86 
87  entry_size=obj_size;
88  nr_cache_lines=CMath::min((int64_t) (cache_size*1024*1024/obj_size/sizeof(T)), num_entries+1);
89 
90  SG_INFO("creating %d cache lines (total size: %ld byte)\n", nr_cache_lines, nr_cache_lines*obj_size*sizeof(T))
91  cache_block=SG_MALLOC(T, obj_size*nr_cache_lines);
92  lookup_table=SG_MALLOC(TEntry, num_entries);
93  cache_table=SG_MALLOC(TEntry*, nr_cache_lines);
94 
98 
99  int64_t i;
100  for (i=0; i<nr_cache_lines; i++)
101  cache_table[i]=NULL;
102 
103  for (i=0; i<num_entries; i++)
104  {
105  lookup_table[i].usage_count=-1;
106  lookup_table[i].locked=false;
107  lookup_table[i].obj=NULL;
108  }
109  cache_is_full=false;
110 
111  //reserve the very last cache line
112  //as scratch buffer
113  nr_cache_lines--;
114 
115  set_generic<T>();
116  }
117 
118  virtual ~CCache()
119  {
120  SG_FREE(cache_block);
121  SG_FREE(lookup_table);
122  SG_FREE(cache_table);
123  }
124 
130  inline bool is_cached(int64_t number)
131  {
132  return (lookup_table && lookup_table[number].obj);
133  }
134 
140  inline T* lock_entry(int64_t number)
141  {
142  if (lookup_table)
143  {
144  lookup_table[number].usage_count++;
145  lookup_table[number].locked=true;
146  return lookup_table[number].obj;
147  }
148  else
149  return NULL;
150  }
151 
156  inline void unlock_entry(int64_t number)
157  {
158  if (lookup_table)
159  lookup_table[number].locked=false;
160  }
161 
169  T* set_entry(int64_t number)
170  {
171  if (lookup_table)
172  {
173  // first look for the element with smallest usage count
174  int64_t min_idx=0;
175  int64_t min=-1;
176  bool found_free_line=false;
177 
178  int64_t start=0;
179  for (start=0; start<nr_cache_lines; start++)
180  {
181  if (!cache_table[start])
182  {
183  min_idx=start;
184  min=-1;
185  found_free_line=true;
186  break;
187  }
188  else
189  {
190  if (!cache_table[start]->locked)
191  {
192  min=cache_table[start]->usage_count;
193  min_idx=start;
194  found_free_line=true;
195  break;
196  }
197  }
198  }
199 
200  for (int64_t i=start; i<nr_cache_lines; i++)
201  {
202  if (!cache_table[i])
203  {
204  min_idx=i;
205  min=-1;
206  found_free_line=true;
207  break;
208  }
209  else
210  {
211  int64_t v=cache_table[i]->usage_count;
212 
213  if (v<min && !cache_table[i]->locked)
214  {
215  min=v;
216  min_idx=i;
217  found_free_line=true;
218  }
219  }
220  }
221 
222  if (cache_table[nr_cache_lines-1]) //since this is an indicator for a full cache
223  cache_is_full=true;
224 
225  if (found_free_line)
226  {
227  // and overwrite it.
228  if ( (lookup_table[number].usage_count-min) < 5 && cache_is_full && ! (cache_table[nr_cache_lines] && cache_table[nr_cache_lines]->locked))
229  min_idx=nr_cache_lines; //scratch entry
230 
231  if (cache_table[min_idx])
232  cache_table[min_idx]->obj=NULL;
233 
234  cache_table[min_idx]=&lookup_table[number];
235  lookup_table[number].obj=&cache_block[entry_size*min_idx];
236 
237  //lock cache entry;
238  lookup_table[number].usage_count=0;
239  lookup_table[number].locked=true;
240  return lookup_table[number].obj;
241  }
242  else
243  return NULL;
244  }
245  else
246  return NULL;
247  }
248 
250  virtual const char* get_name() const { return "Cache"; }
251 
252  protected:
256  int64_t entry_size;
258  int64_t nr_cache_lines;
260  TEntry* lookup_table;
262  TEntry** cache_table;
265 };
266 }
267 #endif

SHOGUN Machine Learning Toolbox - Documentation