dlist: A new implementation of an owned doubly-linked list

This is an owned sendable linked list which allows insertion and
deletion at both ends, with fast traversal through iteration, and fast
append/prepend.

It is indended to replace the previous managed DList with exposed list
nodes. It does not match it feature by feature, but DList could grow
more methods if needed.
dlist: Implement size_hint properly for all iterators
dlist: Introduce a struct Rawlink mimicing Option<T> for a raw pointer

Rawlink<T> holds a *mut T pointer and can convert itself to Option<&mut T>.
The null pointer is of course None.
dlist: Collect a common pattern into link_with_prev()
dlist: Put all tests into a tests module

The exception is the function check_links which needs access to struct
Node (which is not pub).
dlist: Expose ListInsertion trait with insert_before and peek_next

An iterator that allows mutating the list is very useful but needs care
to not be unsound. ListIteration exposes only insert_before (used for
insert_ordered) and peek_next so far.
extra: Add mod container with trait Deque
extra: Rename deque::Deque to ringbuf::RingBuf and impl trait Deque

Let RingBuf have a logical name for a concrete type, and Deque is
used for the Deque trait (implemented by RingBuf and dlist).
dlist: Implement trait Deque
dlist: Fix license header
dlist: Name the type DList for doubly-linked list
extra: Mention extra::container::Deque trait in doc for RingBuf and DList
auto merge of #7652 : blake2-ppc/rust/dlist, r=huonw

This is a new doubly-linked list using owned nodes. In the forward direction, the list is linked with owned pointers, and the backwards direction is linked with &'static Node pointers.

This intends to replace the previous extra::DList that was using managed nodes and also featured freestanding nodes.  The new List does not give access to the nodes, but means to implement all relevant linked-list methods.
 
The list supports pop_back, push_back, pop_front, push_front, front, back, iter, mut_iter, +more iterators,  append, insert_ordered, and merge.

* Add a trait Deque for double ended sequences.

* Both List and Deque implement this trait. Rename Deque to ArrayDeque.

*The text has been updated to summarize resolved items*

## RFC Topics

### Resolved

* Should be in extra
* Representation for the backlinks

### Container Method Names and Trait Names and Type Names

* Location and name of trait `extra::collection::Deque`?
* Name of the ring buffer `extra::deque::ArrayDeque` ?
* Name of the doubly linked list `extra::dlist::List` ?

For container methods I think we have two options:

* Align with the existing methods on the vector. That would be `.push()`, `.pop()`, `.shift()`, `.unshift()`.
* Use the API described in https://github.com/mozilla/rust/wiki/Containers   Obviously that's the way List is written right now.

Should we use `pop_front() -> Option<T>` or `pop_front() -> T` ?

### Benchmarks

Some basic bench numbers for List vs. Vec, Deque and *old DList*

This List implementation's performance is dominated by the allocation of Nodes required when pushing. 

Iterate (by-ref) collection of 128 elements

    test test_bench::bench_iter ... bench: 198 ns/iter (+/- 0)
    test test_bench::bench_iter_mut ... bench: 294 ns/iter (+/- 0)
    test test_bench::bench_iter_rev ... bench: 198 ns/iter (+/- 0)
    test test_bench::bench_iter_mut_rev ... bench: 198 ns/iter (+/- 3)

    test test_bench::bench_iter_vec ... bench: 101 ns/iter (+/- 0)
    test test_bench::bench_iter_deque ... bench: 581 ns/iter (+/- 0)
    test test_bench::bench_iter_dlist ... bench: 9262 ns/iter (+/- 273)

Sequence of `.push(elt)`, `.pop()` or equivalent at the tail end

    test test_bench::bench_push_back_pop_back ... bench: 72 ns/iter (+/- 0)

    test test_bench::bench_push_back_pop_back_vec ... bench: 5 ns/iter (+/- 0)
    test test_bench::bench_push_back_pop_back_deque ... bench: 15 ns/iter (+/- 0)
    test test_bench::bench_push_back_pop_back_dlist ... bench: 234 ns/iter (+/- 0)