mmcfilters::GenerationStampSet Struct Reference

Efficient visited-set implementation based on generation stamps. More...

#include <GenerationStampSet.hpp>

Public Types
using	gen_t = uint32_t
	Integer type used for individual generation stamps.

Public Member Functions
	GenerationStampSet (size_t n)
	Creates a stamp set with n logical entries.
void	resize (size_t newN)
	Resizes the stamp buffer and physically clears all marks.
void	mark (size_t idx) noexcept
	Marks idx in the current generation.
bool	isMarked (size_t idx) const noexcept
	Returns true when idx is marked in the current generation.
void	unmark (size_t idx) noexcept
	Removes one mark from the current logical generation.
void	resetAll ()
	Performs an O(1) logical reset by advancing the generation counter.
void	clearAll ()
	Performs an O(N) physical clear of the whole stamp buffer.
gen_t	generation () const noexcept
	Returns the current generation counter.

Public Attributes
std::unique_ptr< gen_t[]>	stamp
	Stamp buffer with one entry per logical index.
size_t	n {0}
	Number of logical entries in stamp.
gen_t	cur {1}
	Current generation; zero is reserved for physically cleared slots.

Detailed Description

Efficient visited-set implementation based on generation stamps.

GenerationStampSet stores one integer stamp per index. Instead of clearing the whole buffer between traversals, the current generation counter is incremented and used as the logical mark. This keeps the common reset path at O(1) while still allowing a full clear when the counter wraps around.

GenerationStampSet visited(numNodes);
visited.mark(nodeIdx);
 
if (!visited.isMarked(otherIdx)) {
    // process one still-unvisited node
}
 
visited.resetAll();  // O(1) logical reset for the next traversal

Definition at line 29 of file GenerationStampSet.hpp.

Member Typedef Documentation

gen_t

using mmcfilters::GenerationStampSet::gen_t = uint32_t

Integer type used for individual generation stamps.

Definition at line 31 of file GenerationStampSet.hpp.

Constructor & Destructor Documentation

GenerationStampSet()

mmcfilters::GenerationStampSet::GenerationStampSet ( size_t  n )

inlineexplicit

Creates a stamp set with n logical entries.

Definition at line 47 of file GenerationStampSet.hpp.

Member Function Documentation

clearAll()

void mmcfilters::GenerationStampSet::clearAll ( )

inline

Performs an O(N) physical clear of the whole stamp buffer.

Definition at line 89 of file GenerationStampSet.hpp.

generation()

gen_t mmcfilters::GenerationStampSet::generation ( ) const

inlinenoexcept

Returns the current generation counter.

Definition at line 95 of file GenerationStampSet.hpp.

isMarked()

bool mmcfilters::GenerationStampSet::isMarked ( size_t  idx ) const

inlinenoexcept

Returns true when idx is marked in the current generation.

Definition at line 69 of file GenerationStampSet.hpp.

mark()

void mmcfilters::GenerationStampSet::mark ( size_t  idx )

inlinenoexcept

Marks idx in the current generation.

Definition at line 62 of file GenerationStampSet.hpp.

resetAll()

void mmcfilters::GenerationStampSet::resetAll ( )

inline

Performs an O(1) logical reset by advancing the generation counter.

Definition at line 81 of file GenerationStampSet.hpp.

resize()

void mmcfilters::GenerationStampSet::resize ( size_t  newN )

inline

Resizes the stamp buffer and physically clears all marks.

Definition at line 52 of file GenerationStampSet.hpp.

unmark()

void mmcfilters::GenerationStampSet::unmark ( size_t  idx )

inlinenoexcept

Removes one mark from the current logical generation.

Definition at line 74 of file GenerationStampSet.hpp.

Member Data Documentation

cur

gen_t mmcfilters::GenerationStampSet::cur {1}

Current generation; zero is reserved for physically cleared slots.

Definition at line 40 of file GenerationStampSet.hpp.

n

size_t mmcfilters::GenerationStampSet::n {0}

Number of logical entries in stamp.

Definition at line 37 of file GenerationStampSet.hpp.

stamp

std::unique_ptr<gen_t[]> mmcfilters::GenerationStampSet::stamp

Stamp buffer with one entry per logical index.

Definition at line 34 of file GenerationStampSet.hpp.

---

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

• mmcfilters/utils/GenerationStampSet.hpp