linked_list.h File Reference

A (circular) doubly linked list, abstracted over cons cell representations. More...

#include <concepts>
#include <ds/pointer.h>

Go to the source code of this file.

Classes
struct	ds::linked_list::Sentinel< CellTemplateArg >
	Convenience wrapper for a sentinel cons cell, encapsulating some common patterns. More...
class	ds::linked_list::cell::Pointer
	Cons cell using two pointers. More...
class	ds::linked_list::cell::PtrAddr
	Encode a linked list cons cell as a pair of addresses (but present an interface in terms of pointers). More...
class	ds::linked_list::cell::OffsetPtrAddr< Offset >
	Encode a linked list cons cell as a pair of addresses (but present an interface in terms of pointers). More...

Concepts
concept	ds::linked_list::cell::HasCellOperations
	The primitive, required, abstract interface to our cons cells.
concept	ds::linked_list::cell::HasReset
	Reset a cell to a singleton ring.
concept	ds::linked_list::cell::HasCellOperationsReset
concept	ds::linked_list::cell::HasIsSingleton
	Additional, optional overrides available within implementation of cons cells.
concept	ds::linked_list::cell::HasIsSingletonCheck
concept	ds::linked_list::cell::HasIsDoubleton

Functions
template<cell::HasCellOperations T> requires (!cell::HasIsSingletonCheck<T>)
bool	ds::linked_list::is_singleton_check (T *e)
	Like is_singleton(), but checks both edges.
template<cell::HasCellOperations T> requires (cell::HasIsSingletonCheck<T>)
bool	ds::linked_list::is_singleton_check (T *e)
template<cell::HasCellOperations T>
bool	ds::linked_list::is_well_formed (T *e)
	Verify linkage invariants.
template<cell::HasCellOperations Cell>
void	ds::linked_list::insert_before (Cell *curr, Cell *elem)
	Insert a ring of elem-ents (typically, a singleton ring) before the curr-ent element (or sentinel) in the ring.
template<cell::HasCellOperations Cell, typename P> requires std::same_as<P, Cell *> || ds::pointer::proxy::Proxies<P, Cell>
void	ds::linked_list::emplace_before (P curr, Cell *elem)
	Emplacement before.
template<cell::HasCellOperations Cell, typename P> requires std::same_as<P, Cell *> || ds::pointer::proxy::Proxies<P, Cell>
void	ds::linked_list::emplace_after (P curr, Cell *elem)
	Emplacement after.
template<cell::HasCellOperations Cell>
Cell *	ds::linked_list::unsafe_remove (Cell *el, Cell *er)
	Remove from the list without turning the removed span into a well-formed ring.
template<cell::HasCellOperations Cell>
Cell *	ds::linked_list::unsafe_remove (Cell *e)
template<cell::HasCellOperations Cell>
auto	ds::linked_list::unsafe_remove_link (Cell *prev, Cell *rem)
	Remove a particular element rem from the ring, already knowing its adjacent, previous link prev.
template<cell::HasCellOperations Cell>
Cell *	ds::linked_list::remove (Cell *el, Cell *er)
	Remove from the ring, cleaving the ring into two well-formed rings.
template<cell::HasCellOperations Cell>
Cell *	ds::linked_list::remove (Cell *e)
template<cell::HasCellOperations Cell, typename F>
bool	ds::linked_list::search (Cell *from, Cell *to, F f)
	Search through a span of a ring, inclusively from from through exclusively to to, applying f to each cons cell in turn.
template<cell::HasCellOperations Cell, typename F>
bool	ds::linked_list::search (Cell *elem, F f)
	Search through all elements of a ring except elem.
template<cell::HasCellOperations T> requires (!cell::HasIsSingleton<T>)
bool	ds::linked_list::is_singleton (T *e)
	Self-loops indicate either the sentinels of an empty list or, less often, singletons without their sentinels; it's up to the caller to know which is being tested for, here.
template<cell::HasCellOperations T> requires (cell::HasIsSingleton<T>)
bool	ds::linked_list::is_singleton (T *e)
template<cell::HasCellOperations T> requires (!cell::HasIsDoubleton<T>)
bool	ds::linked_list::is_doubleton (T *e)
	Doubletons are either singleton collections (with both the sentinel and the single element satisfying this test) or, less often, a pair of elements without a sentinel.
template<cell::HasCellOperations T> requires (cell::HasIsDoubleton<T>)
bool	ds::linked_list::is_doubleton (T *e)

Detailed Description

A (circular) doubly linked list, abstracted over cons cell representations.

See tests/list-test.cc for additional information on how to use it.

Definition in file linked_list.h.

Function Documentation

emplace_after()

template<cell::HasCellOperations Cell, typename P>
requires std::same_as<P, Cell *> || ds::pointer::proxy::Proxies<P, Cell>

void ds::linked_list::emplace_after	(	P	curr,
		Cell *	elem )

Emplacement after.

This fuses initialization and insertion, so that

emplace_after(c, e);

is semantically equivalent to

e->cell_reset(); insert_before(e, c);

but spelled in a way that the compiler can understand a bit better, with less effort spent in provenance and/or alias analysis.

Definition at line 221 of file linked_list.h.

emplace_before()

template<cell::HasCellOperations Cell, typename P>
requires std::same_as<P, Cell *> || ds::pointer::proxy::Proxies<P, Cell>

void ds::linked_list::emplace_before	(	P	curr,
		Cell *	elem )

Emplacement before.

This fuses initialization and insertion, so that

emplace_before(c, e);

is semantically equivalent to

e->cell_reset(); insert_before(c, e);

but spelled in a way that the compiler can understand a bit better, with less effort spent in provenance and/or alias analysis.

Definition at line 198 of file linked_list.h.

insert_before()

template<cell::HasCellOperations Cell>

void ds::linked_list::insert_before	(	Cell *	curr,
		Cell *	elem )

Insert a ring of elem-ents (typically, a singleton ring) before the curr-ent element (or sentinel) in the ring.

In general, you will probably want to make sure that at most one of elem or curr points to a ring with a sentinel node.

If curr is the sentinel, this is appending to the list, in the sense that the element(s) occupy (or span) the next-most and prev-least position from the sentinel.

By symmetry, if elem is, instead, the sentinel, then curr is prepended to the list in the same sense.

Definition at line 176 of file linked_list.h.

is_doubleton() [1/2]

template<cell::HasCellOperations T>
requires (cell::HasIsDoubleton<T>)

bool ds::linked_list::is_doubleton

(

T *

e

)

Definition at line 144 of file linked_list.h.

is_doubleton() [2/2]

template<cell::HasCellOperations T>
requires (!cell::HasIsDoubleton<T>)

bool ds::linked_list::is_doubleton

(

T *

e

)

Doubletons are either singleton collections (with both the sentinel and the single element satisfying this test) or, less often, a pair of elements without a sentinel.

The caller is expected to know what's meant by this test.

The default implementation decodes and compares both links.

Definition at line 137 of file linked_list.h.

is_singleton() [1/2]

template<cell::HasCellOperations T>
requires (cell::HasIsSingleton<T>)

bool ds::linked_list::is_singleton

(

T *

e

)

Definition at line 99 of file linked_list.h.

is_singleton() [2/2]

template<cell::HasCellOperations T>
requires (!cell::HasIsSingleton<T>)

bool ds::linked_list::is_singleton

(

T *

e

)

Self-loops indicate either the sentinels of an empty list or, less often, singletons without their sentinels; it's up to the caller to know which is being tested for, here.

The default implementation decodes and compares one link; implementations may have more efficient mechanisms.

Definition at line 92 of file linked_list.h.

is_singleton_check() [1/2]

template<cell::HasCellOperations T>
requires (cell::HasIsSingletonCheck<T>)

bool ds::linked_list::is_singleton_check

(

T *

e

)

Definition at line 120 of file linked_list.h.

is_singleton_check() [2/2]

template<cell::HasCellOperations T>
requires (!cell::HasIsSingletonCheck<T>)

bool ds::linked_list::is_singleton_check

(

T *

e

)

Like is_singleton(), but checks both edges.

Useful only for testing invariants.

The default implementation decodes and compares both links.

Definition at line 113 of file linked_list.h.

is_well_formed()

template<cell::HasCellOperations T>

bool ds::linked_list::is_well_formed

(

T *

e

)

Verify linkage invariants.

Again, useful only for testing.

The default implementation decodes all four relevant links.

Definition at line 156 of file linked_list.h.

remove() [1/2]

template<cell::HasCellOperations Cell>

Cell * ds::linked_list::remove

(

Cell *

e

)

Definition at line 320 of file linked_list.h.

remove() [2/2]

template<cell::HasCellOperations Cell>

Cell * ds::linked_list::remove	(	Cell *	el,
		Cell *	er )

Remove from the ring, cleaving the ring into two well-formed rings.

This can be used to remove...

• a single element (el == er)
• the sentinel (el == er), leaving the rest of the ring, if any, as a sentinel-free collection
• a span of elements from el to er via next links; the removed span is made into a ring and the residual ring is left well-formed.

In all cases, el's previous element is returned as a handle to the residual ring. (The caller must already have a reference to the span being removed). This is especially useful when remove-ing elements during a search, below: overwriting the callback's Cell pointer (passed by reference) will continue the iteration, calling back at the removed node's successor.

Removing a singleton from its ring from itself causes no change, as any would-be residual ring is empty. This corner case requires some care on occasion.

Definition at line 311 of file linked_list.h.

search() [1/2]

template<cell::HasCellOperations Cell, typename F>

bool ds::linked_list::search	(	Cell *	elem,
		F	f )

Search through all elements of a ring except elem.

If elem is the sentinel of a ring, then this is, as one expects, a search over all non-sentinel members of the ring.

Definition at line 352 of file linked_list.h.

search() [2/2]

template<cell::HasCellOperations Cell, typename F>

bool ds::linked_list::search	(	Cell *	from,
		Cell *	to,
		F	f )

Search through a span of a ring, inclusively from from through exclusively to to, applying f to each cons cell in turn.

If f returns true, the search stops early and returns true; otherwise, search returns false. To (side-effectfully) visit every node in the span, have f always return false.

Definition at line 333 of file linked_list.h.

unsafe_remove() [1/2]

template<cell::HasCellOperations Cell>

Cell * ds::linked_list::unsafe_remove

(

Cell *

e

)

Definition at line 264 of file linked_list.h.

unsafe_remove() [2/2]

template<cell::HasCellOperations Cell>

Cell * ds::linked_list::unsafe_remove	(	Cell *	el,
		Cell *	er )

Remove from the list without turning the removed span into a well-formed ring.

This is useful only if that invariant will be restored later (prior to insertion, at the very least).

The removed element or span instead retains links into the ring whence it was removed, but is no longer well-formed, since that ring no longer references the removed element or span.

This can be used to remove...

• a single element (el == er)
• the sentinel (el == er), leaving the rest of the ring, if any, as a sentinel-free ring
• a span of elements from el to er via the next links; the removed span is damaged and must be corrected, while the residual ring remains well-formed.

In all cases, el's previous element is returned as a handle to the residual ring.

Definition at line 254 of file linked_list.h.

unsafe_remove_link()

template<cell::HasCellOperations Cell>

auto ds::linked_list::unsafe_remove_link	(	Cell *	prev,
		Cell *	rem )

Remove a particular element rem from the ring, already knowing its adjacent, previous link prev.

prev remains connected to the ring but rem will no longer be well-formed. Returns a proxy to prev's next field.

Definition at line 276 of file linked_list.h.