Aleph-w: Aleph::CA::Tile_Cache< State, TileSide > Class Template Reference

Aleph-w 3.0

A C++ Library for Data Structures and Algorithms

Loading...

Searching...

No Matches

Out-of-core 2D tile cache with LRU eviction. More...

#include <ca-streaming-storage.H>

Collaboration diagram for Aleph::CA::Tile_Cache< State, TileSide >:

Classes
struct	Tile_Entry

Public Types
using	state_type = State
	Cell value type.

Public Member Functions
	Tile_Cache (const std::array< ca_size_t, 2 > &extents, std::filesystem::path dir, const std::size_t capacity)
	Build a tile cache.

std::array< ca_size_t, 2 >	extents () const noexcept

ca_size_t	tiles_rows () const noexcept

ca_size_t	tiles_cols () const noexcept

std::size_t	capacity () const noexcept

std::size_t	resident () const noexcept

Tile_Cache_Stats	stats () const noexcept

State	at (ca_size_t r, ca_size_t c)
	Read the cell at `(r, c)`.

void	set (ca_size_t r, ca_size_t c, const State &v)
	Write the cell at `(r, c)` and mark its tile dirty.

void	flush ()
	Persist every dirty resident tile to disk and clear the dirty flag.

Static Public Attributes
static constexpr std::size_t	tile_side = TileSide
	Tile side length (in cells).

static constexpr std::size_t	tile_cells = TileSide * TileSide
	Number of cells per tile.

Private Types
using	tile_buffer = std::array< State, tile_cells >

using	lru_list = std::list< Tile_Entry >

using	lru_iter = typename lru_list::iterator

using	key_map = std::unordered_map< std::uint64_t, lru_iter >

Private Member Functions
std::filesystem::path	tile_path (std::uint32_t row, std::uint32_t col) const

void	read_tile_from_disk (std::uint32_t row, std::uint32_t col, tile_buffer &buf)
	Read tile from disk into `buf`.

void	write_tile_to_disk (const Tile_Entry &entry)
	Persist tile to disk.

void	touch (lru_iter it)
	Move `it` to the front of the LRU list (mark as most-recent).

lru_iter	page_in (std::uint32_t row, std::uint32_t col)
	Page a tile in, evicting the LRU when full.

lru_iter	resolve (ca_size_t r, ca_size_t c)
	Locate the tile that owns `(r, c)`, paging it in if absent.

Static Private Member Functions
static std::size_t	local_index (ca_size_t r, ca_size_t c) noexcept

Private Attributes
ca_size_t	rows_ = 0

ca_size_t	cols_ = 0

ca_size_t	tiles_per_row_ = 0

ca_size_t	tiles_per_col_ = 0

std::filesystem::path	dir_

std::size_t	capacity_ = 0

lru_list	cache_

key_map	index_

Tile_Cache_Stats	stats_

Detailed Description

template<typename State, std::size_t TileSide>
class Aleph::CA::Tile_Cache< State, TileSide >

Out-of-core 2D tile cache with LRU eviction.

The cache models a logical rows × cols grid divided into TileSide × TileSide tiles. The grid extents must be multiples of TileSide. Up to capacity tiles are kept resident in RAM; cache misses page the tile in from disk (or zero-initialise it on first touch) and evict the least-recently-used tile if needed.

Template Parameters

State	cell value type. Must be trivially copyable.
TileSide	compile-time tile side length.

Definition at line 133 of file ca-streaming-storage.H.

Member Typedef Documentation

◆ key_map

template<typename State , std::size_t TileSide>

using Aleph::CA::Tile_Cache< State, TileSide >::key_map = std::unordered_map<std::uint64_t, lru_iter>

private

Definition at line 160 of file ca-streaming-storage.H.

◆ lru_iter

template<typename State , std::size_t TileSide>

using Aleph::CA::Tile_Cache< State, TileSide >::lru_iter = typename lru_list::iterator

private

Definition at line 159 of file ca-streaming-storage.H.

◆ lru_list

template<typename State , std::size_t TileSide>

using Aleph::CA::Tile_Cache< State, TileSide >::lru_list = std::list<Tile_Entry>

private

Definition at line 158 of file ca-streaming-storage.H.

◆ state_type

template<typename State , std::size_t TileSide>

using Aleph::CA::Tile_Cache< State, TileSide >::state_type = State

Cell value type.

Definition at line 141 of file ca-streaming-storage.H.

◆ tile_buffer

template<typename State , std::size_t TileSide>

using Aleph::CA::Tile_Cache< State, TileSide >::tile_buffer = std::array<State, tile_cells>

private

Definition at line 148 of file ca-streaming-storage.H.

Constructor & Destructor Documentation

◆ Tile_Cache()

template<typename State , std::size_t TileSide>

Aleph::CA::Tile_Cache< State, TileSide >::Tile_Cache	(	const std::array< ca_size_t, 2 > &	extents,
		std::filesystem::path	dir,
		const std::size_t	capacity
	)

inline

Build a tile cache.

Creates dir if it does not exist. Tile files are written into this directory on demand.

Parameters

[in]	extents	`{rows, cols}` of the logical grid. Both must be > 0 and multiples of `TileSide`.
[in]	dir	directory backing the tiles on disk.
[in]	capacity	maximum number of tiles kept resident.

Exceptions

std::domain_error	if `capacity == 0` or extents are not multiples of `TileSide`.
std::filesystem::filesystem_error	if the directory cannot be created.

Definition at line 282 of file ca-streaming-storage.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::CA::Tile_Cache< State, TileSide >::capacity(), Aleph::CA::Tile_Cache< State, TileSide >::cols_, Aleph::CA::Tile_Cache< State, TileSide >::dir_, Aleph::CA::Tile_Cache< State, TileSide >::rows_, Aleph::CA::Tile_Cache< State, TileSide >::tiles_per_col_, and Aleph::CA::Tile_Cache< State, TileSide >::tiles_per_row_.

Member Function Documentation

◆ at()

template<typename State , std::size_t TileSide>

State Aleph::CA::Tile_Cache< State, TileSide >::at	(	ca_size_t	r,
		ca_size_t	c
	)

inline

Read the cell at (r, c).

Pages the owning tile in if it is not resident. Marks the tile as most-recently-used.

Parameters

[in]	r	row index in `[0, rows())`.
[in]	c	column index in `[0, cols())`.

Returns: cell value.

Exceptions

std::out_of_range if (r, c) is outside the grid.

Definition at line 327 of file ca-streaming-storage.H.

References ah_out_of_range_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::CA::Tile_Cache< State, TileSide >::cols_, Aleph::CA::Tile_Cache< State, TileSide >::local_index(), r, Aleph::CA::Tile_Cache< State, TileSide >::resolve(), and Aleph::CA::Tile_Cache< State, TileSide >::rows_.

◆ capacity()

template<typename State , std::size_t TileSide>

std::size_t Aleph::CA::Tile_Cache< State, TileSide >::capacity ( ) const

inlinenoexcept

Returns: resident tile capacity (LRU upper bound).

Definition at line 311 of file ca-streaming-storage.H.

References Aleph::CA::Tile_Cache< State, TileSide >::capacity_.

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::Tile_Cache().

◆ extents()

template<typename State , std::size_t TileSide>

std::array< ca_size_t, 2 > Aleph::CA::Tile_Cache< State, TileSide >::extents ( ) const

inlinenoexcept

Returns: logical grid extents.

Definition at line 301 of file ca-streaming-storage.H.

References Aleph::CA::Tile_Cache< State, TileSide >::cols_, and Aleph::CA::Tile_Cache< State, TileSide >::rows_.

◆ flush()

template<typename State , std::size_t TileSide>

void Aleph::CA::Tile_Cache< State, TileSide >::flush ( )

inline

Persist every dirty resident tile to disk and clear the dirty flag.

After flush the on-disk image is consistent with what the cache currently holds. Resident tiles stay in the cache so the next access remains a hit.

Exceptions

std::runtime_error on stream write failure.

Definition at line 362 of file ca-streaming-storage.H.

References Aleph::CA::Tile_Cache< State, TileSide >::cache_, and Aleph::CA::Tile_Cache< State, TileSide >::write_tile_to_disk().

◆ local_index()

template<typename State , std::size_t TileSide>

static std::size_t Aleph::CA::Tile_Cache< State, TileSide >::local_index	(	ca_size_t	r,
		ca_size_t	c
	)

inlinestaticprivatenoexcept

Definition at line 260 of file ca-streaming-storage.H.

References Aleph::blossom_maximum_cardinality_matching(), and r.

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::at(), and Aleph::CA::Tile_Cache< State, TileSide >::set().

◆ page_in()

template<typename State , std::size_t TileSide>

lru_iter Aleph::CA::Tile_Cache< State, TileSide >::page_in	(	std::uint32_t	row,
		std::uint32_t	col
	)

inlineprivate

Page a tile in, evicting the LRU when full.

Definition at line 223 of file ca-streaming-storage.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::CA::Tile_Cache< State, TileSide >::cache_, Aleph::CA::Tile_Cache< State, TileSide >::capacity_, col, Aleph::CA::Tile_Cache< State, TileSide >::Tile_Entry::col, Aleph::CA::Tile_Cache< State, TileSide >::Tile_Entry::data, Aleph::CA::Tile_Cache_Stats::evictions, Aleph::CA::Tile_Cache< State, TileSide >::index_, Aleph::CA::Tile_Cache< State, TileSide >::read_tile_from_disk(), row, Aleph::CA::Tile_Cache< State, TileSide >::Tile_Entry::row, Aleph::CA::Tile_Cache< State, TileSide >::stats_, Aleph::CA::ca_stream_detail::tile_key(), and Aleph::CA::Tile_Cache< State, TileSide >::write_tile_to_disk().

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::resolve().

◆ read_tile_from_disk()

template<typename State , std::size_t TileSide>

void Aleph::CA::Tile_Cache< State, TileSide >::read_tile_from_disk	(	std::uint32_t	row,
		std::uint32_t	col,
		tile_buffer &	buf
	)

inlineprivate

Read tile from disk into buf.

Initialises buf to State{} when the file does not yet exist (first touch).

Definition at line 180 of file ca-streaming-storage.H.

References ah_runtime_error_if, Aleph::blossom_maximum_cardinality_matching(), col, Aleph::CA::Tile_Cache_Stats::reads, row, Aleph::CA::Tile_Cache< State, TileSide >::stats_, Aleph::CA::Tile_Cache< State, TileSide >::tile_cells, and Aleph::CA::Tile_Cache< State, TileSide >::tile_path().

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::page_in().

◆ resident()

template<typename State , std::size_t TileSide>

std::size_t Aleph::CA::Tile_Cache< State, TileSide >::resident ( ) const

inlinenoexcept

Returns: number of tiles currently resident.

Definition at line 313 of file ca-streaming-storage.H.

References Aleph::CA::Tile_Cache< State, TileSide >::cache_.

◆ resolve()

template<typename State , std::size_t TileSide>

lru_iter Aleph::CA::Tile_Cache< State, TileSide >::resolve	(	ca_size_t	r,
		ca_size_t	c
	)

inlineprivate

Locate the tile that owns (r, c), paging it in if absent.

Definition at line 245 of file ca-streaming-storage.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::CA::Tile_Cache_Stats::hits, Aleph::CA::Tile_Cache< State, TileSide >::index_, Aleph::CA::Tile_Cache_Stats::misses, Aleph::CA::Tile_Cache< State, TileSide >::page_in(), r, Aleph::CA::Tile_Cache< State, TileSide >::stats_, Aleph::CA::ca_stream_detail::tile_key(), and Aleph::CA::Tile_Cache< State, TileSide >::touch().

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::at(), and Aleph::CA::Tile_Cache< State, TileSide >::set().

◆ set()

template<typename State , std::size_t TileSide>

void Aleph::CA::Tile_Cache< State, TileSide >::set	(	ca_size_t	r,
		ca_size_t	c,
		const State &	v
	)

inline

Write the cell at (r, c) and mark its tile dirty.

Parameters

[in]	r	row index in `[0, rows())`.
[in]	c	column index in `[0, cols())`.
[in]	v	new cell value.

Exceptions

std::out_of_range if (r, c) is outside the grid.

Definition at line 343 of file ca-streaming-storage.H.

References ah_out_of_range_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::CA::Tile_Cache< State, TileSide >::cols_, Aleph::CA::Tile_Cache< State, TileSide >::local_index(), r, Aleph::CA::Tile_Cache< State, TileSide >::resolve(), and Aleph::CA::Tile_Cache< State, TileSide >::rows_.

Referenced by TEST().

◆ stats()

template<typename State , std::size_t TileSide>

Tile_Cache_Stats Aleph::CA::Tile_Cache< State, TileSide >::stats ( ) const

inlinenoexcept

Returns: cache statistics snapshot.

Definition at line 315 of file ca-streaming-storage.H.

References Aleph::CA::Tile_Cache< State, TileSide >::stats_.

◆ tile_path()

template<typename State , std::size_t TileSide>

std::filesystem::path Aleph::CA::Tile_Cache< State, TileSide >::tile_path	(	std::uint32_t	row,
		std::uint32_t	col
	)		const

inlineprivate

Definition at line 172 of file ca-streaming-storage.H.

References col, Aleph::CA::Tile_Cache< State, TileSide >::dir_, and row.

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::read_tile_from_disk(), and Aleph::CA::Tile_Cache< State, TileSide >::write_tile_to_disk().

◆ tiles_cols()

template<typename State , std::size_t TileSide>

ca_size_t Aleph::CA::Tile_Cache< State, TileSide >::tiles_cols ( ) const

inlinenoexcept

Returns: number of tiles along axis 1.

Definition at line 309 of file ca-streaming-storage.H.

References Aleph::CA::Tile_Cache< State, TileSide >::tiles_per_col_.

◆ tiles_rows()

template<typename State , std::size_t TileSide>

ca_size_t Aleph::CA::Tile_Cache< State, TileSide >::tiles_rows ( ) const

inlinenoexcept

Returns: number of tiles along axis 0.

Definition at line 307 of file ca-streaming-storage.H.

References Aleph::CA::Tile_Cache< State, TileSide >::tiles_per_row_.

◆ touch()

template<typename State , std::size_t TileSide>

void Aleph::CA::Tile_Cache< State, TileSide >::touch ( lru_iter it )

inlineprivate

Move it to the front of the LRU list (mark as most-recent).

Definition at line 216 of file ca-streaming-storage.H.

References Aleph::CA::Tile_Cache< State, TileSide >::cache_.

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::resolve().

◆ write_tile_to_disk()

template<typename State , std::size_t TileSide>

void Aleph::CA::Tile_Cache< State, TileSide >::write_tile_to_disk ( const Tile_Entry & entry )

inlineprivate

Persist tile to disk.

Definition at line 200 of file ca-streaming-storage.H.

References ah_runtime_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::CA::Tile_Cache< State, TileSide >::Tile_Entry::col, Aleph::CA::Tile_Cache< State, TileSide >::Tile_Entry::data, out, Aleph::CA::Tile_Cache< State, TileSide >::Tile_Entry::row, Aleph::CA::Tile_Cache< State, TileSide >::stats_, Aleph::CA::Tile_Cache< State, TileSide >::tile_cells, Aleph::CA::Tile_Cache< State, TileSide >::tile_path(), and Aleph::CA::Tile_Cache_Stats::writes.

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::flush(), and Aleph::CA::Tile_Cache< State, TileSide >::page_in().

Member Data Documentation

◆ cache_

template<typename State , std::size_t TileSide>

lru_list Aleph::CA::Tile_Cache< State, TileSide >::cache_

private

Definition at line 168 of file ca-streaming-storage.H.

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::flush(), Aleph::CA::Tile_Cache< State, TileSide >::page_in(), Aleph::CA::Tile_Cache< State, TileSide >::resident(), and Aleph::CA::Tile_Cache< State, TileSide >::touch().

◆ capacity_

template<typename State , std::size_t TileSide>

std::size_t Aleph::CA::Tile_Cache< State, TileSide >::capacity_ = 0

private

Definition at line 167 of file ca-streaming-storage.H.

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::capacity(), and Aleph::CA::Tile_Cache< State, TileSide >::page_in().

◆ cols_

template<typename State , std::size_t TileSide>

ca_size_t Aleph::CA::Tile_Cache< State, TileSide >::cols_ = 0

private

Definition at line 163 of file ca-streaming-storage.H.

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::Tile_Cache(), Aleph::CA::Tile_Cache< State, TileSide >::at(), Aleph::CA::Tile_Cache< State, TileSide >::extents(), and Aleph::CA::Tile_Cache< State, TileSide >::set().

◆ dir_

template<typename State , std::size_t TileSide>

std::filesystem::path Aleph::CA::Tile_Cache< State, TileSide >::dir_

private

Definition at line 166 of file ca-streaming-storage.H.

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::Tile_Cache(), and Aleph::CA::Tile_Cache< State, TileSide >::tile_path().

◆ index_

template<typename State , std::size_t TileSide>

key_map Aleph::CA::Tile_Cache< State, TileSide >::index_

private

Definition at line 169 of file ca-streaming-storage.H.

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::page_in(), and Aleph::CA::Tile_Cache< State, TileSide >::resolve().

◆ rows_

template<typename State , std::size_t TileSide>

ca_size_t Aleph::CA::Tile_Cache< State, TileSide >::rows_ = 0

private

Definition at line 162 of file ca-streaming-storage.H.

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::Tile_Cache(), Aleph::CA::Tile_Cache< State, TileSide >::at(), Aleph::CA::Tile_Cache< State, TileSide >::extents(), and Aleph::CA::Tile_Cache< State, TileSide >::set().

◆ stats_

template<typename State , std::size_t TileSide>

Tile_Cache_Stats Aleph::CA::Tile_Cache< State, TileSide >::stats_

private

Definition at line 170 of file ca-streaming-storage.H.

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::page_in(), Aleph::CA::Tile_Cache< State, TileSide >::read_tile_from_disk(), Aleph::CA::Tile_Cache< State, TileSide >::resolve(), Aleph::CA::Tile_Cache< State, TileSide >::stats(), and Aleph::CA::Tile_Cache< State, TileSide >::write_tile_to_disk().

◆ tile_cells

template<typename State , std::size_t TileSide>

constexpr std::size_t Aleph::CA::Tile_Cache< State, TileSide >::tile_cells = TileSide * TileSide

staticconstexpr

Number of cells per tile.

Definition at line 145 of file ca-streaming-storage.H.

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::read_tile_from_disk(), and Aleph::CA::Tile_Cache< State, TileSide >::write_tile_to_disk().

◆ tile_side

template<typename State , std::size_t TileSide>

constexpr std::size_t Aleph::CA::Tile_Cache< State, TileSide >::tile_side = TileSide

staticconstexpr

Tile side length (in cells).

Definition at line 143 of file ca-streaming-storage.H.

◆ tiles_per_col_

template<typename State , std::size_t TileSide>

ca_size_t Aleph::CA::Tile_Cache< State, TileSide >::tiles_per_col_ = 0

private

Definition at line 165 of file ca-streaming-storage.H.

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::Tile_Cache(), and Aleph::CA::Tile_Cache< State, TileSide >::tiles_cols().

◆ tiles_per_row_

template<typename State , std::size_t TileSide>

ca_size_t Aleph::CA::Tile_Cache< State, TileSide >::tiles_per_row_ = 0

private

Definition at line 164 of file ca-streaming-storage.H.

Referenced by Aleph::CA::Tile_Cache< State, TileSide >::Tile_Cache(), and Aleph::CA::Tile_Cache< State, TileSide >::tiles_rows().

The documentation for this class was generated from the following file:

ca-streaming-storage.H

Aleph
CA
Tile_Cache
Generated by 1.9.8