SDSL 3.0.1
Succinct Data Structure Library
Loading...
Searching...
No Matches
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
9namespace sdsl
10{
11
12#define CACHE_SIZE 0x3FFULL
13
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
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:216
#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