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

SHOGUN Machine Learning Toolbox - Documentation