Module rc_dlist_deque::dlist
source · Expand description
See the crate-level documentation for a discussion of whether to use this crate.
Concepts
Your data structure is a collection of Rc<N>, where N is the
node type. The node type N contain the list link(s).
The link type is defined by rc_dlist_deque (and, inside,
contains the back/next pointers). Each link may be on one
list, or on none.
A pointer is a reference to a node, qua one of its potential list memberships. I.e., it specifies both the node and the link. It is not null. Another way to look at it is that it is a reference to a specific link within a specific node.
A cursor is Some(pointer) or None. It is used whenever
a pointer might be null.
The nodes are not mutable, since they are inside Rc.
(The dlist implementation uses std::cell:Cell for interior mutability.)
When each node can only be on one list (at once)
If all you need is a simple list where each node is on at most one list
at once, you can use the convenience types Node1<T> and List1<T>
where T is your own data type. A Node1 is simply your T plus the
list link.
Often T will be, or contain, a RefCell or Cell, since the nodes
themselves are not mutable.
Pointer1<T> then represents a pointer to a node. It is a newtype
wrapper for Rc<Node1<T>>. Its type indicates its use as a list
pointer with
Node1<T> and List1<T>. Also relevant is Option<Pointer1<T>>
(also known as Cursor1<T>) which is used for pointers which might
be null.
When each node can be on multiple lists
If you want to do something more sophisticated, you should
use the types List<N,S> and Node<N,S>.
You should define your own node type N containing one or more
Link<N,S>.
You also need to define a type S, the selector. Its type
and value identifies one of the links in a node.
Simple, static, link selection
Suppose at each point you know statically which Link is to be
operated on, and it’s the same in in all involved nodes. Ie,
while you have different classes of list, and multiple links in
each node, each link in each node belongs to one of the list
classes.
Then you want the different links and the corresponding lists to have distinct types. The intended link node is then identified by the type system.
In this case: for each link which appears in your node, define a
empty struct type (let us call it FooSelector). It should
derive Debug,Copy,Clone,PartialEq,Eq,Default. Use the
DlistImplSelector macro. Then the corresponding types
are List<N,FooSelector>, Pointer<N,FooSelector> and
Link<N,FooSelector>.
Run-time dynamic link selection
If you need to specify at run-time which link to use, you must
provide a nontrivial selector type S, which is the actual value
indicating which Link to use.
S must implement Selector. It can still be helpful to use the
DlistImplSelector helper macro to provide the trait
implementation.
The selector value may be different in different nodes on the same
list. (Ie, the link contains not only the Rc references to the
nodes, but Pointers, including both
Selectors.) S must be Copy.
Entrypoints
Most of the useful functions are methods on List,
with a few on Pointer and ListIterator.
Many of the methods take a parameter like rev : bool or tail : bool
or after : bool. These are bidirectional methods: they can
operate in either direction, as specified. Generally false
means forwards, or at the beginning.
Ownership
A node which is on a list has a (strong) Rc reference owned by
the list. Dropping a list will implictly remove all the items and
drop those references; whether that drops the nodes depends on
whether there are other references, as would be expected for Rc.
Tangling and panics
Linked lists can get tangled, for example if you put a node on a list and then, without removing it from the first list, insert it into another list. It is the user’s responsibility to know whether a node is on a list, and what list it is on, and only to make appropriate calls.
The specific requirements are indicated in each case a section like this in each relevant function description:
Panics, or tangles the list(s)
Any operation on a tangled list may panic; tangled lists can also result in infinite loops.
When debug assertions are enabled, the library will nearly always detect when a list is about to be tangled and panic immediately. When debug assertions are disabled the additional records needed for this are compiled out, and tangling a list may go undetected, and result in panics some considerable time later.
However, this library contains only safe Rust. So while tangled lists can result in panics and algorithmic malfunctions, they cannot result in undefined behaviour.
Structs
Traits
List1, Node1 etc. if you can.
If your nodes need to a member of multiple lists,
use DlistImplSelector!{:p}.
Used when Pointer is printed with {:p}.