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 
00022 template<class T> class CCache : public CSGObject
00023 {
00025     struct TEntry
00026     {
00028         LONG usage_count;
00030         bool locked;
00032         T* obj;
00033     };
00034 
00035     public:
00046     CCache(LONG cache_size, LONG obj_size, LONG num_entries)
00047     : CSGObject()
00048     {
00049         if (cache_size==0 || obj_size==0 || num_entries==0)
00050         {
00051             SG_INFO("doing without cache.\n");
00052             cache_block=NULL;
00053             lookup_table=NULL;
00054             cache_table=NULL;
00055             cache_is_full=false;
00056             nr_cache_lines=0;
00057             entry_size=0;
00058             return;
00059         }
00060 
00061         entry_size=obj_size;
00062         nr_cache_lines=CMath::min((LONG) (cache_size*1024*1024/obj_size/sizeof(T)), num_entries+1);
00063 
00064         SG_INFO("creating %d cache lines (total size: %ld byte)\n", nr_cache_lines, nr_cache_lines*obj_size*sizeof(T));
00065         cache_block=new T[obj_size*nr_cache_lines];
00066         lookup_table=new TEntry[num_entries];
00067         cache_table=new TEntry*[nr_cache_lines];
00068 
00069         ASSERT(cache_block);
00070         ASSERT(lookup_table);
00071         ASSERT(cache_table);
00072 
00073         LONG i;
00074         for (i=0; i<nr_cache_lines; i++)
00075             cache_table[i]=NULL;
00076 
00077         for (i=0; i<num_entries; i++)
00078         {
00079             lookup_table[i].usage_count=-1;
00080             lookup_table[i].locked=false;
00081             lookup_table[i].obj=NULL;
00082         }
00083         cache_is_full=false;
00084 
00085         //reserve the very last cache line
00086         //as scratch buffer
00087         nr_cache_lines--;
00088     }
00089 
00090     ~CCache()
00091     {
00092         delete[] cache_block;
00093         delete[] lookup_table;
00094         delete[] cache_table;
00095     }
00096 
00102     inline bool is_cached(LONG number)
00103     {
00104         return (lookup_table && lookup_table[number].obj);
00105     }
00106 
00112     inline T* lock_entry(LONG number)
00113     {
00114         if (lookup_table)
00115         {
00116             lookup_table[number].usage_count++;
00117             lookup_table[number].locked=true;
00118             return lookup_table[number].obj;
00119         }
00120         else
00121             return NULL;
00122     }
00123 
00128     inline void unlock_entry(LONG number)
00129     {
00130         if (lookup_table)
00131             lookup_table[number].locked=false;
00132     }
00133 
00141     T* set_entry(LONG number)
00142     {
00143         if (lookup_table)
00144         {
00145             // first look for the element with smallest usage count
00146             //LONG min_idx=((nr_cache_lines-1)*random())/(RAND_MAX+1); //avoid the last elem and the scratch line
00147             LONG min_idx=0;
00148             LONG min=-1;
00149             bool found_free_line=false;
00150 
00151             LONG start=0;
00152             for (start=0; start<nr_cache_lines; start++)
00153             {
00154                 if (!cache_table[start])
00155                 {
00156                     min_idx=start;
00157                     min=-1;
00158                     found_free_line=true;
00159                     break;
00160                 }
00161                 else
00162                 {
00163                     if (!cache_table[start]->locked)
00164                     {
00165                         min=cache_table[start]->usage_count;
00166                         min_idx=start;
00167                         found_free_line=true;
00168                         break;
00169                     }
00170                 }
00171             }
00172 
00173             for (LONG i=start; i<nr_cache_lines; i++)
00174             {
00175                 if (!cache_table[i])
00176                 {
00177                     min_idx=i;
00178                     min=-1;
00179                     found_free_line=true;
00180                     break;
00181                 }
00182                 else
00183                 {
00184                     LONG v=cache_table[i]->usage_count;
00185 
00186                     if (v<min && !cache_table[i]->locked)
00187                     {
00188                         min=v;
00189                         min_idx=i;
00190                         found_free_line=true;
00191                     }
00192                 }
00193             }
00194 
00195             if (cache_table[nr_cache_lines-1]) //since this is an indicator for a full cache
00196                 cache_is_full=true;
00197 
00198             if (found_free_line)
00199             {
00200                 // and overwrite it.
00201                 if ( (lookup_table[number].usage_count-min) < 5 && cache_is_full && ! (cache_table[nr_cache_lines] && cache_table[nr_cache_lines]->locked))
00202                     min_idx=nr_cache_lines; //scratch entry
00203 
00204                 if (cache_table[min_idx])
00205                     cache_table[min_idx]->obj=NULL;
00206 
00207                 cache_table[min_idx]=&lookup_table[number];
00208                 lookup_table[number].obj=&cache_block[entry_size*min_idx];
00209 
00210                 //lock cache entry;
00211                 lookup_table[number].usage_count=0;
00212                 lookup_table[number].locked=true;
00213                 return lookup_table[number].obj;
00214             }
00215             else
00216                 return NULL;
00217         }
00218         else 
00219             return NULL;
00220     }
00221 
00223     bool cache_is_full;
00225     LONG entry_size;
00227     LONG nr_cache_lines;
00229     TEntry* lookup_table;
00231     TEntry** cache_table;
00233     T* cache_block;
00234 };
00235 #endif

SHOGUN Machine Learning Toolbox - Documentation