Cache.h

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

SHOGUN Machine Learning Toolbox - Documentation