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)

0 files changed, 0 insertions, 0 deletions