#include <DiscreteRange.h>

Collaboration diagram for swoc::DiscreteSpace< METRIC, PAYLOAD >:

Classes
class	Node
	A node in the range tree. More...

Public Types
using	iterator = typename decltype(_list)::iterator

using	const_iterator = typename decltype(_list)::const_iterator

Public Member Functions
self_type &	mark_bulk (std::vector< std::pair< range_type, PAYLOAD > > &marks, bool is_sorted=false)

self_type &	mark_bulk (std::pair< range_type, PAYLOAD > *start, size_t n, bool is_sorted=false)

self_type &	mark (range_type const &range, PAYLOAD const &payload, bool update_tree=true)

self_type &	erase (range_type const &range)

template<typename F, typename U = PAYLOAD>
self_type &	blend (range_type const &range, U const &color, F &&blender)

self_type &	fill (range_type const &range, PAYLOAD const &payload)

iterator	find (METRIC const &metric)

const_iterator	find (METRIC const &metric) const

iterator	lower_bound (METRIC const &m)

iterator	upper_bound (METRIC const &m)

std::pair< iterator, iterator >	intersection (range_type const &range)

size_t	count () const

bool	empty () const

iterator	begin ()

iterator	end ()

const_iterator	begin () const

const_iterator	end () const

void	clear ()
	Remove all ranges.

template<typename F, typename U>
auto	blend (DiscreteSpace::range_type const &range, U const &color, F &&blender) -> self_type &

Protected Types
using	metric_type = METRIC
	Export.

using	payload_type = PAYLOAD
	Export.

using	range_type = DiscreteRange<METRIC>

using	Direction = typename Node::Direction

Protected Member Functions
Node *	prev (Node *n)

Node *	next (Node *n)

Node *	left (Node *n)

Node *	right (Node *n)

Node *	lower_node (METRIC const &target)

Node *	upper_node (METRIC const &target)

Node *	head ()

Node *	tail ()

void	insert_before (Node spot, Node node, bool update_tree=true)

void	insert_after (Node spot, Node node, bool update_tree=true)

void	prepend (Node *node, bool update_tree=true)

void	append (Node *node, bool update_tree=true)

void	remove (Node *node, bool update_tree=true)

Protected Attributes
Node *	_root = nullptr
	Root node.

IntrusiveDList< typename Node::Linkage >	_list
	In order list of nodes.

swoc::MemArena	_arena {4000}
	Memory Storage.

swoc::FixedArena< Node >	_fa {_arena}
	Node allocator and free list.

Detailed Description

template<typename METRIC, typename PAYLOAD>
class swoc::DiscreteSpace< METRIC, PAYLOAD >

A space for a discrete METRIC.

Template Parameters

METRIC	Value type for the space.
PAYLOAD	Data stored with values in the space.

This is a range based mapping of all values in METRIC (the "space") to PAYLOAD.

PAYLOAD is presumed to be relatively cheap to construct and copy.

METRIC must be

discrete and finite valued type with increment and decrement operations.

Definition at line 708 of file DiscreteRange.h.

Member Typedef Documentation

◆ const_iterator

template<typename METRIC, typename PAYLOAD>

using swoc::DiscreteSpace< METRIC, PAYLOAD >::const_iterator = typename decltype(_list)::const_iterator

Definition at line 833 of file DiscreteRange.h.

◆ Direction

template<typename METRIC, typename PAYLOAD>

using swoc::DiscreteSpace< METRIC, PAYLOAD >::Direction = typename Node::Direction

protected

Definition at line 803 of file DiscreteRange.h.

◆ iterator

template<typename METRIC, typename PAYLOAD>

using swoc::DiscreteSpace< METRIC, PAYLOAD >::iterator = typename decltype(_list)::iterator

Definition at line 832 of file DiscreteRange.h.

◆ metric_type

template<typename METRIC, typename PAYLOAD>

using swoc::DiscreteSpace< METRIC, PAYLOAD >::metric_type = METRIC

protected

Export.

Definition at line 712 of file DiscreteRange.h.

◆ payload_type

template<typename METRIC, typename PAYLOAD>

using swoc::DiscreteSpace< METRIC, PAYLOAD >::payload_type = PAYLOAD

protected

Export.

Definition at line 713 of file DiscreteRange.h.

◆ range_type

template<typename METRIC, typename PAYLOAD>

using swoc::DiscreteSpace< METRIC, PAYLOAD >::range_type = DiscreteRange<METRIC>

protected

Definition at line 714 of file DiscreteRange.h.

Constructor & Destructor Documentation

◆ ~DiscreteSpace()

template<typename METRIC, typename PAYLOAD>

swoc::DiscreteSpace< METRIC, PAYLOAD >::~DiscreteSpace ( )

Definition at line 1081 of file DiscreteRange.h.

Member Function Documentation

◆ append()

template<typename METRIC, typename PAYLOAD>

void swoc::DiscreteSpace< METRIC, PAYLOAD >::append	(	DiscreteSpace< METRIC, PAYLOAD >::Node *	node,
		bool	update_tree = true )

protected

Add node to tree as the last node.

Parameters

node	Node to append.
update_tree	`true` to update the RBTree structure.

Invariant - node is last in order.

Definition at line 1259 of file DiscreteRange.h.

◆ begin() [1/2]

template<typename METRIC, typename PAYLOAD>

iterator swoc::DiscreteSpace< METRIC, PAYLOAD >::begin ( )

inline

Returns: Iterator for the first range.

Definition at line 952 of file DiscreteRange.h.

◆ begin() [2/2]

template<typename METRIC, typename PAYLOAD>

const_iterator swoc::DiscreteSpace< METRIC, PAYLOAD >::begin ( ) const

inline

Returns: Iterator for the first range.

Definition at line 962 of file DiscreteRange.h.

◆ blend() [1/2]

template<typename METRIC, typename PAYLOAD>

template<typename F, typename U>

auto swoc::DiscreteSpace< METRIC, PAYLOAD >::blend	(	DiscreteSpace< METRIC, PAYLOAD >::range_type const &	range,
		U const &	color,
		F &&	blender ) -> self_type &

Definition at line 1645 of file DiscreteRange.h.

◆ blend() [2/2]

template<typename METRIC, typename PAYLOAD>

template<typename F, typename U = PAYLOAD>

self_type & swoc::DiscreteSpace< METRIC, PAYLOAD >::blend	(	range_type const &	range,
		U const &	color,
		F &&	blender )

Blend a color to a range.

Template Parameters

F	Functor to blend payloads.
U	type to blend in to payloads.

Parameters

range	Range for blending.
color	Payload to blend.
blender	Functor to compute blended color.

Returns: this

color is blended to values in range. If an address in range does not have a payload, its payload is set a default constructed PAYLOAD blended with color. If such an address does have a payload, color is blended in to that payload using blender. The existing color is passed as the first argument and color as the second argument. The functor is expected to update the first argument to be the blended color. The function must return a bool to indicate whether the blend resulted in a valid color. If false is returned, the blended region is removed from the space.

◆ clear()

template<typename METRIC, typename PAYLOAD>

void swoc::DiscreteSpace< METRIC, PAYLOAD >::clear ( )

Remove all ranges.

Definition at line 1850 of file DiscreteRange.h.

◆ count()

template<typename METRIC, typename PAYLOAD>

size_t swoc::DiscreteSpace< METRIC, PAYLOAD >::count ( ) const

Returns: The number of distinct ranges.

Definition at line 1090 of file DiscreteRange.h.

◆ empty()

template<typename METRIC, typename PAYLOAD>

bool swoc::DiscreteSpace< METRIC, PAYLOAD >::empty ( ) const

Returns: true if there are no ranges in the container, false otherwise.

Definition at line 1096 of file DiscreteRange.h.

◆ end() [1/2]

template<typename METRIC, typename PAYLOAD>

iterator swoc::DiscreteSpace< METRIC, PAYLOAD >::end ( )

inline

Returns: Iterator past the last node.

Definition at line 957 of file DiscreteRange.h.

◆ end() [2/2]

template<typename METRIC, typename PAYLOAD>

const_iterator swoc::DiscreteSpace< METRIC, PAYLOAD >::end ( ) const

inline

Returns: Iterator past the last node.

Definition at line 967 of file DiscreteRange.h.

◆ erase()

template<typename METRIC, typename PAYLOAD>

DiscreteSpace< METRIC, PAYLOAD > & swoc::DiscreteSpace< METRIC, PAYLOAD >::erase ( DiscreteSpace< METRIC, PAYLOAD >::range_type const & range )

Erase a range.

Parameters

range Range to erase.

Returns: this

All values in range are removed from the space.

Definition at line 1330 of file DiscreteRange.h.

◆ fill()

template<typename METRIC, typename PAYLOAD>

DiscreteSpace< METRIC, PAYLOAD > & swoc::DiscreteSpace< METRIC, PAYLOAD >::fill	(	DiscreteSpace< METRIC, PAYLOAD >::range_type const &	range,
		PAYLOAD const &	payload )

Fill range with payload.

Parameters

range	Range to fill.
payload	Payload to use.

Returns: this

Values in range that do not have a payload are set to payload. Values in the space are not changed.

Definition at line 1526 of file DiscreteRange.h.

◆ find() [1/2]

template<typename METRIC, typename PAYLOAD>

auto swoc::DiscreteSpace< METRIC, PAYLOAD >::find ( METRIC const & metric )

Find the payload at metric.

Parameters

metric The metric for which to search.

Returns: An iterator for the item or the end iterator if not.

Definition at line 1114 of file DiscreteRange.h.

◆ find() [2/2]

template<typename METRIC, typename PAYLOAD>

auto swoc::DiscreteSpace< METRIC, PAYLOAD >::find ( METRIC const & metric ) const

Find the payload at metric.

Parameters

metric The metric for which to search.

Returns: An iterator for the item or the end iterator if not.

Definition at line 1138 of file DiscreteRange.h.

◆ head()

template<typename METRIC, typename PAYLOAD>

auto swoc::DiscreteSpace< METRIC, PAYLOAD >::head ( )

protected

Returns: First node in the tree.

Definition at line 1102 of file DiscreteRange.h.

◆ insert_after()

template<typename METRIC, typename PAYLOAD>

void swoc::DiscreteSpace< METRIC, PAYLOAD >::insert_after	(	DiscreteSpace< METRIC, PAYLOAD >::Node *	spot,
		DiscreteSpace< METRIC, PAYLOAD >::Node *	node,
		bool	update_tree = true )

protected

Insert node after spot.

Parameters

spot	Target node.
node	Node to insert.
update_tree	`true` to update the RBTree structure.

Definition at line 1308 of file DiscreteRange.h.

◆ insert_before()

template<typename METRIC, typename PAYLOAD>

void swoc::DiscreteSpace< METRIC, PAYLOAD >::insert_before	(	DiscreteSpace< METRIC, PAYLOAD >::Node *	spot,
		DiscreteSpace< METRIC, PAYLOAD >::Node *	node,
		bool	update_tree = true )

protected

Insert node before spot.

Parameters

spot	Target node.
node	Node to insert.
update_tree	`true` to update the RBTree structure.

Definition at line 1286 of file DiscreteRange.h.

◆ intersection()

template<typename METRIC, typename PAYLOAD>

auto swoc::DiscreteSpace< METRIC, PAYLOAD >::intersection ( DiscreteSpace< METRIC, PAYLOAD >::range_type const & range )

Intersection of range with container.

Parameters

range Search range.

Returns: Iterator pair that contains all ranges that intersect with range.

See also: lower_bound; upper_bound

Definition at line 1216 of file DiscreteRange.h.

◆ left()

template<typename METRIC, typename PAYLOAD>

Node * swoc::DiscreteSpace< METRIC, PAYLOAD >::left ( Node * n )

inlineprotected

Definition at line 822 of file DiscreteRange.h.

◆ lower_bound()

template<typename METRIC, typename PAYLOAD>

auto swoc::DiscreteSpace< METRIC, PAYLOAD >::lower_bound ( METRIC const & m )

Lower bound.

Parameters

m	Search value.

Returns: Rightmost range that starts at or before m.

Definition at line 1202 of file DiscreteRange.h.

◆ lower_node()

template<typename METRIC, typename PAYLOAD>

auto swoc::DiscreteSpace< METRIC, PAYLOAD >::lower_node ( METRIC const & target )

protected

Find the lower bounding node.

Parameters

target Search value.

Returns: The rightmost range that starts at or before target, or nullptr if all ranges start after target.

Definition at line 1144 of file DiscreteRange.h.

◆ mark()

template<typename METRIC, typename PAYLOAD>

DiscreteSpace< METRIC, PAYLOAD > & swoc::DiscreteSpace< METRIC, PAYLOAD >::mark	(	DiscreteSpace< METRIC, PAYLOAD >::range_type const &	range,
		PAYLOAD const &	payload,
		bool	update_tree = true )

Set the payload for a range

Parameters

range	Range to mark.
payload	Payload to set.
update_tree	`true` to update the RBTree structure.

Returns: this

Values in range are set to payload regardless of the current state.

Definition at line 1401 of file DiscreteRange.h.

◆ mark_bulk() [1/2]

template<typename METRIC, typename PAYLOAD>

DiscreteSpace< METRIC, PAYLOAD > & swoc::DiscreteSpace< METRIC, PAYLOAD >::mark_bulk	(	std::pair< range_type, PAYLOAD > *	start,
		size_t	n,
		bool	is_sorted = false )

Mark ranges in one operation.

Parameters

start	Pointer to the first range/payload pair.
n	Number of pairs.
is_sorted	`true` if input is sorted, `false` if not. Assumes not sorted.

Returns: this

Definition at line 1367 of file DiscreteRange.h.

◆ mark_bulk() [2/2]

template<typename METRIC, typename PAYLOAD>

DiscreteSpace< METRIC, PAYLOAD > & swoc::DiscreteSpace< METRIC, PAYLOAD >::mark_bulk	(	std::vector< std::pair< range_type, PAYLOAD > > &	marks,
		bool	is_sorted = false )

Mark ranges in one operation.

Parameters

marks	Vector of ranges and payloads to mark.
is_sorted	`true` if input is sorted, `false` if not. Assumes not sorted.

Returns: this

Definition at line 1361 of file DiscreteRange.h.

◆ next()

template<typename METRIC, typename PAYLOAD>

Node * swoc::DiscreteSpace< METRIC, PAYLOAD >::next ( Node * n )

inlineprotected

Definition at line 817 of file DiscreteRange.h.

◆ prepend()

template<typename METRIC, typename PAYLOAD>

void swoc::DiscreteSpace< METRIC, PAYLOAD >::prepend	(	DiscreteSpace< METRIC, PAYLOAD >::Node *	node,
		bool	update_tree = true )

protected

Add node to tree as the first element.

Parameters

node	Node to prepend.
update_tree	`true` to update the RBTree structure.

Invariant - node is first in order.

Definition at line 1244 of file DiscreteRange.h.

◆ prev()

template<typename METRIC, typename PAYLOAD>

Node * swoc::DiscreteSpace< METRIC, PAYLOAD >::prev ( Node * n )

inlineprotected

Definition at line 812 of file DiscreteRange.h.

◆ remove()

template<typename METRIC, typename PAYLOAD>

void swoc::DiscreteSpace< METRIC, PAYLOAD >::remove	(	DiscreteSpace< METRIC, PAYLOAD >::Node *	node,
		bool	update_tree = true )

protected

Remove node from container and update container.

Parameters

node	Node to remove.
update_tree	`true` to update the RBTree structure.

Definition at line 1275 of file DiscreteRange.h.

◆ right()

template<typename METRIC, typename PAYLOAD>

Node * swoc::DiscreteSpace< METRIC, PAYLOAD >::right ( Node * n )

inlineprotected

Definition at line 827 of file DiscreteRange.h.

◆ tail()

template<typename METRIC, typename PAYLOAD>

auto swoc::DiscreteSpace< METRIC, PAYLOAD >::tail ( )

protected

Returns: Last node in the tree.

Definition at line 1108 of file DiscreteRange.h.

◆ upper_bound()

template<typename METRIC, typename PAYLOAD>

auto swoc::DiscreteSpace< METRIC, PAYLOAD >::upper_bound ( METRIC const & m )

Upper bound.

Parameters

m	search value

Returns: Leftmost range that starts after m.

Definition at line 1209 of file DiscreteRange.h.

◆ upper_node()

template<typename METRIC, typename PAYLOAD>

auto swoc::DiscreteSpace< METRIC, PAYLOAD >::upper_node ( METRIC const & target )

protected

Find the upper bound node.

Parameters

target Search value.

Returns: The leftmoswt range that starts after target, or nullptr if all ranges start before target.

Definition at line 1170 of file DiscreteRange.h.

Member Data Documentation

◆ _arena

template<typename METRIC, typename PAYLOAD>

swoc::MemArena swoc::DiscreteSpace< METRIC, PAYLOAD >::_arena {4000}

protected

Memory Storage.

Definition at line 807 of file DiscreteRange.h.

◆ _fa

template<typename METRIC, typename PAYLOAD>

swoc::FixedArena<Node> swoc::DiscreteSpace< METRIC, PAYLOAD >::_fa {_arena}

protected

Node allocator and free list.

Definition at line 808 of file DiscreteRange.h.

◆ _list

template<typename METRIC, typename PAYLOAD>

IntrusiveDList<typename Node::Linkage> swoc::DiscreteSpace< METRIC, PAYLOAD >::_list

protected

In order list of nodes.

Definition at line 806 of file DiscreteRange.h.

◆ _root

template<typename METRIC, typename PAYLOAD>

Node* swoc::DiscreteSpace< METRIC, PAYLOAD >::_root = nullptr

protected

Root node.

Definition at line 805 of file DiscreteRange.h.

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

DiscreteRange.h

Classes

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ Direction

◆ iterator

◆ metric_type

◆ payload_type

◆ range_type

Constructor & Destructor Documentation

◆ ~DiscreteSpace()

Member Function Documentation

◆ append()

◆ begin() [1/2]

◆ begin() [2/2]

◆ blend() [1/2]

◆ blend() [2/2]

◆ clear()

◆ count()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase()

◆ fill()

◆ find() [1/2]

◆ find() [2/2]

◆ head()

◆ insert_after()

◆ insert_before()

◆ intersection()

◆ left()

◆ lower_bound()

◆ lower_node()

◆ mark()

◆ mark_bulk() [1/2]

◆ mark_bulk() [2/2]

◆ next()

◆ prepend()

◆ prev()

◆ remove()

◆ right()

◆ tail()

◆ upper_bound()

◆ upper_node()

Member Data Documentation

◆ _arena

◆ _fa

◆ _list

◆ _root