SDSL: Succinct Data Structure Library
A C++ template library for succinct data structures
|
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