Ipc::Mem::IdSet Class Reference

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 More...

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

Public Attributes
const IdSetMeasurements	measurements

Private Types
typedef uint64_t	Node
	either leaf or intermediate node More...
typedef std::atomic< Node >	StoredNode
	a Node stored in shared memory More...

Private Member Functions
void	fillAllNodes ()
void	truncateExtras ()
	effectively removes IDs that exceed the requested capacity after makeFull() More...
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 More...
void	innerPush (Position, NavigationDirection)
	accounts for an ID added to subtree in the given dir from the given position More...
NavigationDirection	innerPop (Position)
void	leafPush (Position, size_type id)
	adds the given ID to the leaf node at the given position More...
size_type	leafPop (Position)
	extracts and returns an ID from the leaf node at the given position More...
Position	ascend (Position)
Position	descend (Position, NavigationDirection)
StoredNode &	nodeAt (Position)

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

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, max(), 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, Ipc::Mem::BitsPerLeaf, and max().

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:

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