real::detail::pc_set_cache Struct Reference

A tiny open-chaining hash set of interned PC-set state ids, keyed by their pc-set. Replaces a std::unordered_map so the DFAs stay literal types (a constexpr real::regex embeds one in its scratch state); all-std::vector storage is constexpr-constructible in C++20. Maps a candidate pc-set to its existing state id, or not_found, comparing against the owner's pcs. More...

#include <lazy_dfa.hpp>

Public Member Functions
constexpr	pc_set_cache ()
	An empty cache with all bucket_count chains allocated.
constexpr std::uint32_t	find (const std::vector< std::int32_t > &pcs, const std::vector< std::vector< std::int32_t > > &state_pcs) const
	The state already interned for pcs, if any.
constexpr void	insert (const std::vector< std::int32_t > &pcs, std::uint32_t id)
	Records id under pcs. The caller guarantees pcs is not already interned.
constexpr void	clear ()
	Empties every chain, keeping the bucket array allocated (paired with a state-cache flush).

Static Public Member Functions
static constexpr std::size_t	hash (const std::vector< std::int32_t > &v)
	FNV-1a over the pc-set, truncated to size_t.

Public Attributes
std::vector< std::vector< std::uint32_t > >	buckets
	One chain of state ids per bucket.

Static Public Attributes
static constexpr std::size_t	bucket_count {2048}
	Fixed bucket count; chaining absorbs the load.
static constexpr std::uint32_t	not_found {0xFFFFFFFFU}
	find's miss answer (never a valid state id).

Detailed Description

A tiny open-chaining hash set of interned PC-set state ids, keyed by their pc-set. Replaces a std::unordered_map so the DFAs stay literal types (a constexpr real::regex embeds one in its scratch state); all-std::vector storage is constexpr-constructible in C++20. Maps a candidate pc-set to its existing state id, or not_found, comparing against the owner's pcs.

Member Function Documentation

find()

constexpr std::uint32_t real::detail::pc_set_cache::find ( const std::vector< std::int32_t > &  pcs, const std::vector< std::vector< std::int32_t > > &  state_pcs  ) const

inlineconstexpr

The state already interned for pcs, if any.

Parameters

[in]	pcs	The candidate pc-set.
[in]	state_pcs	The owner's per-state pc-sets, compared against on a bucket hit.

Returns

The matching state id, or not_found.

hash()

static constexpr std::size_t real::detail::pc_set_cache::hash ( const std::vector< std::int32_t > &  v )

inlinestaticconstexpr

FNV-1a over the pc-set, truncated to size_t.

Parameters

[in]

v

The pc-set to hash.

Returns

Its hash; the caller takes it modulo bucket_count.

insert()

constexpr void real::detail::pc_set_cache::insert ( const std::vector< std::int32_t > &  pcs, std::uint32_t  id  )

inlineconstexpr

Records id under pcs. The caller guarantees pcs is not already interned.

Parameters

[in]	pcs	The state's pc-set.
[in]	id	The state id to record.

---

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

• include/real/automata/lazy_dfa.hpp