[][src]Module rc_dlist_deque::dlist

See the crate-level documentatio for a discussion of whether to use this crate.


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.


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.


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.



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. Use List1, Node1 etc. if you can. If your nodes need to a member of multiple lists, use DlistImplSelector!


Should write a suffix suitable for printing after {:p}. Used when Pointer is printed with {:p}.

Type Definitions


Simple list