libcore: Implement an `Equiv` trait and use it on hashmaps.

7.3x speedup in string map search speed on a microbenchmark of pure hashmap
searching against a constant string, due to the lack of allocations.

I ran into a few snags.

1. The way the coherence check is set up, I can't implement `Equiv<@str>` and
   `Equiv<~str>` for `&str` simultaneously.

2. I wanted to implement `Equiv<T>` for all `T:Eq` (i.e. every type can be
   compared to itself if it implements `Eq`), but the coherence check didn't
   like that either.

3. I couldn't add this to the `Map` trait because `LinearMap` needs special
   handling for its `Q` type parameter: it must not only implement `Equiv<T>`
   but also `Hash` and `Eq`.

4. `find_equiv(&&"foo")` doesn't parse, because of the double ampersand. It has
   to be written `find_equiv(& &"foo")`. We can probably just fix this.

Nevertheless, this is a huge win; it should address a major source of
performance problems, including the one here:

http://maniagnosis.crsr.net/2013/02/creating-letterpress-cheating-program.html

1 files changed, 7 insertions, 1 deletions

diff --git a/src/libcore/str.rs b/src/libcore/str.rs
index 471e1ae5396..24b2d8b5813 100644
--- a/src/libcore/str.rs
+++ b/src/libcore/str.rs
@@ -20,7 +20,7 @@
 use at_vec;
 use cast;
 use char;
-use cmp::{TotalOrd, Ordering, Less, Equal, Greater};
+use cmp::{Equiv, TotalOrd, Ordering, Less, Equal, Greater};
 use libc;
 use option::{None, Option, Some};
 use ptr;
@@ -898,6 +898,12 @@ impl Ord for @str {
     pure fn gt(&self, other: &@str) -> bool { gt((*self), (*other)) }
 }
 
+#[cfg(notest)]
+impl Equiv<~str> for &str {
+    #[inline(always)]
+    pure fn equiv(&self, other: &~str) -> bool { eq_slice(*self, *other) }
+}
+
 /*
 Section: Iterating through strings
 */