See the crate-level documentatio for a discussion of whether to use this crate.
Your data structure is a collection of
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
None. It is used whenever
a pointer might be null.
The nodes are not mutable, since they are inside
(The dlist implementation uses
std::cell:Cell for interior mutability.)
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
T is your own data type. A
Node1 is simply your
T plus the
T will be, or contain, a
Cell, since the nodes
themselves are not mutable.
Pointer1<T> then represents a pointer to a node. It is a newtype
Rc<Node1<T>>. Its type indicates its use as a list
List1<T>. Also relevant is
(also known as
Cursor1<T>) which is used for pointers which might
If you want to do something more sophisticated, you should
use the types
You should define your own node type
N containing one or more
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
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
Debug,Copy,Clone,PartialEq,Eq,Default. Use the
DlistImplSelector macro. Then the corresponding types
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
Link to use.
S must implement
Selector. It can still be helpful to use the
DlistImplSelector helper macro to provide the trait
The selector value may be different in different nodes on the same
list. (Ie, the link contains not only the Rc references to the
Pointers, including both
S must be
Most of the useful functions are methods on
with a few on
Many of the methods take a parameter like
rev : bool or
tail : bool
after : bool. These are bidirectional methods: they can
operate in either direction, as specified. Generally
means forwards, or at the beginning.
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
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.
In a node, its potential membership of a list.
The general list type.
Selector type for simple List1/Node1
Iterator (forwards) through the list.
Node on a simple list.
Reference to a node, with respect to its potential membership of a list.
It is not often necessary to implement this directly.
Should write a suffix suitable for printing after