SDSL  3.0.0
Succinct Data Structure Library
fast_cache.hpp
Go to the documentation of this file.
1 // Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2 // Please see the AUTHORS file for details. Use of this source code is governed
3 // by a BSD license that can be found in the LICENSE file.
4 #ifndef INCLUDED_SDSL_FAST_CACHE
5 #define INCLUDED_SDSL_FAST_CACHE
6 
7 #include <sdsl/int_vector.hpp>
8 
9 namespace sdsl
10 {
11 
12 #define CACHE_SIZE 0x3FFULL
13 
14 struct fast_cache
15 {
18  // Constructor
20  {
21  for (size_type i = 0; i < (CACHE_SIZE + 1); ++i) { m_table[i << 1] = (size_type)-1; }
22  }
23  // Returns true if the request i is cached and
24  // x is set to the answer of request i
25  bool exists(size_type i, size_type & x)
26  {
27  if (m_table[(i & CACHE_SIZE) << 1] == i)
28  {
29  x = m_table[((i & CACHE_SIZE) << 1) + 1];
30  return true;
31  }
32  else
33  return false;
34  }
35  // Writes the answer for request i to the cache
37  {
38  m_table[(i & CACHE_SIZE) << 1] = i;
39  m_table[((i & CACHE_SIZE) << 1) + 1] = x;
40  }
41 };
42 
43 } // end namespace sdsl
44 
45 #endif
A generic vector class for integers of width .
Definition: int_vector.hpp:253
#define CACHE_SIZE
Definition: fast_cache.hpp:12
int_vector.hpp contains the sdsl::int_vector class.
Namespace for the succinct data structure library.
void write(size_type i, size_type x)
Definition: fast_cache.hpp:36
int_vector ::size_type size_type
Definition: fast_cache.hpp:16
bool exists(size_type i, size_type &x)
Definition: fast_cache.hpp:25
size_type m_table[2 *(CACHE_SIZE+1)]
Definition: fast_cache.hpp:17