real::detail::backtrack_frame Struct Reference

The bounded backtracker's state for one search, on the caller's stack (see pike_vm::run_bounded_backtrack). More...

#include <pike.hpp>

Classes
struct	job
	One pending branch: explore instruction pc at row row, or – pc negative – restore slot -pc - 1 to row, read as a position or unset. More...

Public Member Functions
void	clear (std::size_t first, std::size_t rows)
	Clears the marks of rows [first, rows), in whole words.
bool	marked (std::int32_t pc, std::size_t row) const
	Whether (pc, row) was entered already.
bool	enter (std::int32_t pc, std::size_t row)
	Marks (pc, row) entered.
void	push (job j)
	Holds a pending branch.
bool	pop (job &j)
	Takes the most recent pending branch.
void	save (std::uint16_t slot, std::size_t value)
	Sets slot slot to value, holding its old value to restore when the branch is left.

Public Attributes
std::array< std::uint64_t, bounded_backtrack_bits/64U >	marks
	Bit row x width + pc: entered already.
std::array< std::size_t, bounded_backtrack_max_slots >	slots
	The explored branch's capture slots.
std::array< job, inline_jobs >	jobs
	Pending branches, most recent last.
std::vector< job >	spill
	Pending branches past inline_jobs.
std::size_t	depth {0}
	Jobs held in jobs.
std::size_t	width {0}
	Instructions per row.

Static Public Attributes
static constexpr std::uint32_t	unset {0xFFFFFFFFU}
	A restored slot's npos (rows stay far below).
static constexpr std::size_t	inline_jobs {256}
	Jobs held before spilling to the heap.

Detailed Description

The bounded backtracker's state for one search, on the caller's stack (see pike_vm::run_bounded_backtrack).

Rows are positions relative to the search's start. Nothing is zeroed on construction: a start clears the rows from it to the subject's end. Clearing each row as the walk reaches it would cost a test per byte.

Member Function Documentation

clear()

void real::detail::backtrack_frame::clear ( std::size_t  first, std::size_t  rows  )

inline

Clears the marks of rows [first, rows), in whole words.

Parameters

[in]	first	The first start's row: no row before it is ever read.
[in]	rows	Rows the search spans.

enter()

bool real::detail::backtrack_frame::enter ( std::int32_t  pc, std::size_t  row  )

inline

Marks (pc, row) entered.

Parameters

[in]	pc	Instruction.
[in]	row	Row.

Returns

False when it was entered already.

marked()

bool real::detail::backtrack_frame::marked ( std::int32_t  pc, std::size_t  row  ) const

inline

Whether (pc, row) was entered already.

Parameters

[in]	pc	Instruction.
[in]	row	Row.

Returns

True when it was.

pop()

bool real::detail::backtrack_frame::pop ( job &  j )

inline

Takes the most recent pending branch.

Parameters

[out]

j

The branch.

Returns

False when none is pending.

push()

void real::detail::backtrack_frame::push ( job  j )

inline

Holds a pending branch.

Parameters

[in]

j

The branch.

save()

void real::detail::backtrack_frame::save ( std::uint16_t  slot, std::size_t  value  )

inline

Sets slot slot to value, holding its old value to restore when the branch is left.

Parameters

[in]	slot	The slot.
[in]	value	Its new value.

---

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

• include/real/engine/pike.hpp