SDSL: Succinct Data Structure Library
A C++ template library for succinct data structures
 All Classes Namespaces Files Functions Variables Typedefs Friends
sdsl/include/sdsl/fast_cache.hpp
00001 
00002 #ifndef INCLUDED_SDSL_FAST_CACHE
00003 #define INCLUDED_SDSL_FAST_CACHE
00004 
00005 #include "int_vector.hpp"
00006 
00007 namespace sdsl
00008 {
00009 
00010 #define CACHE_SIZE 0x3FFULL
00011 
00012 struct fast_cache {
00013     typedef int_vector<>::size_type size_type;
00014     size_type m_table[2*(CACHE_SIZE+1)];
00015     // Constructor
00016     fast_cache() {
00017         for (size_type i=0; i < (CACHE_SIZE+1); ++i) {
00018             m_table[i<<1] = (size_type)-1;
00019         }
00020     }
00021     // Returns true if the request i is cached and
00022     // x is set to the answer of request i
00023     bool exists(size_type i, size_type& x) {
00024         if (m_table[(i&CACHE_SIZE)<<1 ] == i) {
00025             x = m_table[((i&CACHE_SIZE)<<1) + 1 ];
00026             return true;
00027         } else
00028             return false;
00029     }
00030     // Writes the answer for request i to the cache
00031     void write(size_type i, size_type x) {
00032         m_table[(i&CACHE_SIZE)<<1 ] = i;
00033         m_table[((i&CACHE_SIZE)<<1) + 1 ] = x;
00034     }
00035 };
00036 
00037 } // end namespace sdsl
00038 
00039 #endif