auto merge of #18287 : michaelsproul/rust/triemap-collection-views, r=bstrie

I've implemented the new collection views API for TrieMap. I more or less followed the approach set out by @Gankro in BTreeMap, by using a `SearchStack`. There's quite a bit of unsafe code, but I've wrapped it safely where I think is appropriate. I've added tests to ensure everything works, and performance seems quite good.

```
test trie::bench_map::bench_find                           ... bench:     67879 ns/iter (+/- 4192)
test trie::bench_map::bench_find_entry                     ... bench:    186814 ns/iter (+/- 18748)
test trie::bench_map::bench_insert_large                   ... bench:    716612 ns/iter (+/- 160121)
test trie::bench_map::bench_insert_large_entry             ... bench:    851219 ns/iter (+/- 20331)
test trie::bench_map::bench_remove                         ... bench:    838856 ns/iter (+/- 27998)
test trie::bench_map::bench_remove_entry                   ... bench:    981711 ns/iter (+/- 53046)
```

Using an entry is slow compared to a plain find, but is only ~15% slower for inserts and removes, which is where this API is most useful. I'm tempted to remove the standalone `remove` function in favour of an entry-based approach (to cut down on complexity).

I've added some more comments to the general part of the code-base, which will hopefully help the next person looking over this. I moved the three key structures to the top of the file so that the nesting structure is clearly visible, and renamed `Child<T>` to `TrieNode<T>` and `TrieNode<T>` to `InternalNode<T>` to improve clarity. If these changes are creeping, I'm happy to revert them.

Let me know if my use of `fail!` is ok, I was a little unsure of how specific to be. Some of the data-structures have various invariants that shouldn't be broken, so using `fail!` seemed appropriate.

## Still to do

* Modernise iterators (make them double-ended).
* Make the keys generic, or rename this data-structure (see: https://github.com/rust-lang/rust/issues/14902).
* Possibly move this code out of libcollections. [Searching Github for TrieMap turns up very few real results.][triemap-search]

Related issues: https://github.com/rust-lang/rust/issues/18009 and https://github.com/rust-lang/rust/issues/17320

[triemap-search]: https://github.com/search?utf8=%E2%9C%93&q=TrieMap+language%3ARust&type=Code&ref=searchresults

0 files changed, 0 insertions, 0 deletions