a shareable set of positive uint32_t IDs with O(1) insertion/removal ops More...

#include <PageStack.h>

Collaboration diagram for Ipc::Mem::IdSet:

Public Types
using	size_type = IdSetMeasurements::size_type

using	Position = IdSetPosition

using	NavigationDirection = IdSetNavigationDirection

Public Member Functions
	IdSet (size_type capacity)

void	makeFullBeforeSharing ()

bool	pop (size_type &id)

void	push (size_type id)
	makes `id` value available to future pop() callers

Static Public Member Functions
static size_t	MemorySize (size_type capacity)
	memory size required to store a tree with the given capacity

Public Attributes
const IdSetMeasurements	measurements

Private Types
typedef uint64_t	Node
	either leaf or intermediate node

typedef std::atomic< Node >	StoredNode
	a Node stored in shared memory

Private Member Functions
void	fillAllNodes ()

void	truncateExtras ()
	effectively removes IDs that exceed the requested capacity after makeFull()

Node *	valueAddress (Position)

size_type	innerTruncate (Position pos, NavigationDirection dir, size_type toSubtract)

void	leafTruncate (Position pos, size_type idsToKeep)
	fill the leaf node at a given position with 0s, leaving only idsToKeep IDs

void	innerPush (Position, NavigationDirection)
	accounts for an ID added to subtree in the given dir from the given position

NavigationDirection	innerPop (Position)

void	leafPush (Position, size_type id)
	adds the given ID to the leaf node at the given position

size_type	leafPop (Position)
	extracts and returns an ID from the leaf node at the given position

Position	ascend (Position)

Position	descend (Position, NavigationDirection)

StoredNode &	nodeAt (Position)

Private Attributes
FlexibleArray< StoredNode >	nodes_
	the entire binary tree flattened into an array

Detailed Description

Definition at line 53 of file PageStack.h.

Member Typedef Documentation

◆ NavigationDirection

using Ipc::Mem::IdSet::NavigationDirection = IdSetNavigationDirection

Definition at line 58 of file PageStack.h.

◆ Node

typedef uint64_t Ipc::Mem::IdSet::Node

private

Definition at line 79 of file PageStack.h.

◆ Position

using Ipc::Mem::IdSet::Position = IdSetPosition

Definition at line 57 of file PageStack.h.

◆ size_type

using Ipc::Mem::IdSet::size_type = IdSetMeasurements::size_type

Definition at line 56 of file PageStack.h.

◆ StoredNode

typedef std::atomic<Node> Ipc::Mem::IdSet::StoredNode

private

Definition at line 80 of file PageStack.h.

Constructor & Destructor Documentation

◆ IdSet()

Ipc::Mem::IdSet::IdSet ( size_type capacity )

explicit

Definition at line 152 of file PageStack.cc.

References assert.

Member Function Documentation

◆ ascend()

Ipc::Mem::IdSet::Position Ipc::Mem::IdSet::ascend ( Position pos )

private

Returns: the position of a parent node of the node at the given position

Definition at line 336 of file PageStack.cc.

References assert, Ipc::Mem::IdSetPosition::level, and Ipc::Mem::IdSetPosition::offset.

◆ descend()

Ipc::Mem::IdSet::Position Ipc::Mem::IdSet::descend	(	Position	pos,
		NavigationDirection	direction
	)

private

Returns: the position of a child node in the given direction of the parent node at the given position

Definition at line 347 of file PageStack.cc.

References assert, Ipc::Mem::dirLeft, Ipc::Mem::dirRight, Ipc::Mem::IdSetPosition::level, and Ipc::Mem::IdSetPosition::offset.

◆ fillAllNodes()

void Ipc::Mem::IdSet::fillAllNodes ( )

private

populates the entire allocated tree with available IDs may exceed the requested capacity;

See also: truncateExtras()

Definition at line 176 of file PageStack.cc.

References Ipc::Mem::BitsPerLeaf, and Ipc::Mem::IdSetInnerNode::pack().

◆ innerPop()

Ipc::Mem::IdSet::NavigationDirection Ipc::Mem::IdSet::innerPop ( Position pos )

private

accounts for future ID removal from a subtree of the given position

Returns: the direction of the subtree chosen to relinquish the ID

Definition at line 270 of file PageStack.cc.

References assert, Ipc::Mem::dirEnd, Ipc::Mem::dirLeft, Ipc::Mem::dirNone, Ipc::Mem::dirRight, Ipc::Mem::IdSetInnerNode::left, Ipc::Mem::IdSetInnerNode::pack(), Ipc::Mem::IdSetInnerNode::right, and Ipc::Mem::IdSetInnerNode::Unpack().

◆ innerPush()

void Ipc::Mem::IdSet::innerPush	(	Position	pos,
		NavigationDirection	dir
	)

private

Definition at line 258 of file PageStack.cc.

References assert, Ipc::Mem::dirLeft, Ipc::Mem::dirRight, and Ipc::Mem::IdSetInnerNode::pack().

◆ innerTruncate()

Ipc::Mem::IdSet::size_type Ipc::Mem::IdSet::innerTruncate	(	Position	pos,
		NavigationDirection	dir,
		size_type	toSubtract
	)

private

accounts for toSubtract IDs removal from a subtree in the given direction of the given position

Returns: the number of IDs to subtract from the parent node

Definition at line 235 of file PageStack.cc.

References assert, Ipc::Mem::dirLeft, Ipc::Mem::dirRight, and Ipc::Mem::IdSetInnerNode::Unpack().

◆ leafPop()

Ipc::Mem::IdSet::size_type Ipc::Mem::IdSet::leafPop ( Position pos )

private

Definition at line 320 of file PageStack.cc.

References assert, Ipc::Mem::BitsPerLeaf, Ipc::Mem::IdSetPosition::offset, and trailingZeros().

◆ leafPush()

void Ipc::Mem::IdSet::leafPush	(	Position	pos,
		size_type	id
	)

private

Definition at line 296 of file PageStack.cc.

References assert, and Ipc::Mem::BitsPerLeaf.

◆ leafTruncate()

void Ipc::Mem::IdSet::leafTruncate	(	Position	pos,
		size_type	idsToKeep
	)

private

Definition at line 222 of file PageStack.cc.

References assert, and Ipc::Mem::BitsPerLeaf.

◆ makeFullBeforeSharing()

void Ipc::Mem::IdSet::makeFullBeforeSharing ( )

populates the allocated tree with the requested capacity IDs optimized to run without atomic protection

Definition at line 163 of file PageStack.cc.

References Ipc::Mem::BitsPerLeaf.

Referenced by Ipc::Mem::PageStack::PageStack().

◆ MemorySize()

size_t Ipc::Mem::IdSet::MemorySize ( size_type capacity )

static

Definition at line 419 of file PageStack.cc.

References Ipc::Mem::IdSetMeasurements::nodeCount().

Referenced by Ipc::Mem::PageStack::StackSize().

◆ nodeAt()

Ipc::Mem::IdSet::StoredNode & Ipc::Mem::IdSet::nodeAt ( Position pos )

private

Returns: the atomic node (either inner or leaf) at the given position

Definition at line 363 of file PageStack.cc.

References assert, Ipc::Mem::IdSetPosition::atRoot(), Ipc::Mem::IdSetPosition::level, and Ipc::Mem::IdSetPosition::offset.

◆ pop()

bool Ipc::Mem::IdSet::pop ( size_type & id )

finds/extracts (into the given id) an ID value and returns true

Return values

false no IDs are left

Definition at line 387 of file PageStack.cc.

References Ipc::Mem::dirEnd.

◆ push()

void Ipc::Mem::IdSet::push ( size_type id )

Definition at line 405 of file PageStack.cc.

References Ipc::Mem::BitsPerLeaf.

◆ truncateExtras()

void Ipc::Mem::IdSet::truncateExtras ( )

private

Definition at line 197 of file PageStack.cc.

References Ipc::Mem::BitsPerLeaf.

◆ valueAddress()

Ipc::Mem::IdSet::Node * Ipc::Mem::IdSet::valueAddress ( Position pos )

private

Returns: the location of the raw (inner or leaf) node at the given position

Definition at line 380 of file PageStack.cc.

Member Data Documentation

◆ measurements

const IdSetMeasurements Ipc::Mem::IdSet::measurements

Definition at line 76 of file PageStack.h.

◆ nodes_

FlexibleArray<StoredNode> Ipc::Mem::IdSet::nodes_

private

Definition at line 101 of file PageStack.h.

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

squid/src/ipc/mem/PageStack.h
squid/src/ipc/mem/PageStack.cc

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ NavigationDirection

◆ Node

◆ Position

◆ size_type

◆ StoredNode

Constructor & Destructor Documentation

◆ IdSet()

Member Function Documentation

◆ ascend()

◆ descend()

◆ fillAllNodes()

◆ innerPop()

◆ innerPush()

◆ innerTruncate()

◆ leafPop()

◆ leafPush()

◆ leafTruncate()

◆ makeFullBeforeSharing()

◆ MemorySize()

◆ nodeAt()

◆ pop()

◆ push()

◆ truncateExtras()

◆ valueAddress()

Member Data Documentation

◆ measurements

◆ nodes_