auto merge of #12428 : alexcrichton/rust/move-hashmap, r=brson

These two containers are indeed collections, so there place is in
libcollections, not in libstd. There will always be a hash map as part of the
standard distribution of Rust, but by moving it out of the standard library it
makes libstd that much more portable to more platforms and environments.

This conveniently also removes the stuttering of 'std::hashmap::HashMap',
although 'collections::HashMap' is only one character shorter.

2 files changed, 36 insertions, 17 deletions

diff --git a/src/libnative/io/timer_other.rs b/src/libnative/io/timer_other.rs
index 3a060194a69..9f332adb27b 100644
--- a/src/libnative/io/timer_other.rs
+++ b/src/libnative/io/timer_other.rs
@@ -49,7 +49,6 @@
 #[allow(non_camel_case_types)];
 
 use std::comm::Data;
-use std::hashmap::HashMap;
 use std::libc;
 use std::mem;
 use std::os;
@@ -105,7 +104,7 @@ fn helper(input: libc::c_int, messages: Port<Req>) {
     // sorted list, and dead timers are those which have expired, but ownership
     // hasn't yet been transferred back to the timer itself.
     let mut active: ~[~Inner] = ~[];
-    let mut dead = HashMap::new();
+    let mut dead = ~[];
 
     // inserts a timer into an array of timers (sorted by firing time)
     fn insert(t: ~Inner, active: &mut ~[~Inner]) {
@@ -116,7 +115,7 @@ fn helper(input: libc::c_int, messages: Port<Req>) {
     }
 
     // signals the first requests in the queue, possible re-enqueueing it.
-    fn signal(active: &mut ~[~Inner], dead: &mut HashMap<uint, ~Inner>) {
+    fn signal(active: &mut ~[~Inner], dead: &mut ~[(uint, ~Inner)]) {
         let mut timer = match active.shift() {
             Some(timer) => timer, None => return
         };
@@ -127,7 +126,7 @@ fn helper(input: libc::c_int, messages: Port<Req>) {
             insert(timer, active);
         } else {
             drop(chan);
-            dead.insert(timer.id, timer);
+            dead.push((timer.id, timer));
         }
     }
 
@@ -172,8 +171,12 @@ fn helper(input: libc::c_int, messages: Port<Req>) {
                         Data(NewTimer(timer)) => insert(timer, &mut active),
 
                         Data(RemoveTimer(id, ack)) => {
-                            match dead.pop(&id) {
-                                Some(i) => { ack.send(i); continue }
+                            match dead.iter().position(|&(i, _)| id == i) {
+                                Some(i) => {
+                                    let (_, i) = dead.remove(i).unwrap();
+                                    ack.send(i);
+                                    continue
+                                }
                                 None => {}
                             }
                             let i = active.iter().position(|i| i.id == id);
diff --git a/src/libnative/io/timer_timerfd.rs b/src/libnative/io/timer_timerfd.rs
index b1ae5820888..baafe3f4850 100644
--- a/src/libnative/io/timer_timerfd.rs
+++ b/src/libnative/io/timer_timerfd.rs
@@ -35,7 +35,6 @@ use std::libc;
 use std::ptr;
 use std::os;
 use std::rt::rtio;
-use std::hashmap::HashMap;
 use std::mem;
 
 use io::file::FileDesc;
@@ -78,7 +77,7 @@ fn helper(input: libc::c_int, messages: Port<Req>) {
 
     add(efd, input);
     let events: [imp::epoll_event, ..16] = unsafe { mem::init() };
-    let mut map: HashMap<libc::c_int, (Chan<()>, bool)> = HashMap::new();
+    let mut list: ~[(libc::c_int, Chan<()>, bool)] = ~[];
     'outer: loop {
         let n = match unsafe {
             imp::epoll_wait(efd, events.as_ptr(),
@@ -107,13 +106,17 @@ fn helper(input: libc::c_int, messages: Port<Req>) {
                 // FIXME: should this perform a send() this number of
                 //      times?
                 let _ = FileDesc::new(fd, false).inner_read(bits).unwrap();
-                let remove = {
-                    match map.find(&fd).expect("fd unregistered") {
-                        &(ref c, oneshot) => !c.try_send(()) || oneshot
+                let (remove, i) = {
+                    match list.bsearch(|&(f, _, _)| f.cmp(&fd)) {
+                        Some(i) => {
+                            let (_, ref c, oneshot) = list[i];
+                            (!c.try_send(()) || oneshot, i)
+                        }
+                        None => fail!("fd not active: {}", fd),
                     }
                 };
                 if remove {
-                    map.remove(&fd);
+                    drop(list.remove(i));
                     del(efd, fd);
                 }
             }
@@ -128,8 +131,17 @@ fn helper(input: libc::c_int, messages: Port<Req>) {
 
                     // If we haven't previously seen the file descriptor, then
                     // we need to add it to the epoll set.
-                    if map.insert(fd, (chan, one)) {
-                        add(efd, fd);
+                    match list.bsearch(|&(f, _, _)| f.cmp(&fd)) {
+                        Some(i) => {
+                            drop(mem::replace(&mut list[i], (fd, chan, one)));
+                        }
+                        None => {
+                            match list.iter().position(|&(f, _, _)| f >= fd) {
+                                Some(i) => list.insert(i, (fd, chan, one)),
+                                None => list.push((fd, chan, one)),
+                            }
+                            add(efd, fd);
+                        }
                     }
 
                     // Update the timerfd's time value now that we have control
@@ -141,14 +153,18 @@ fn helper(input: libc::c_int, messages: Port<Req>) {
                 }
 
                 Data(RemoveTimer(fd, chan)) => {
-                    if map.remove(&fd) {
-                        del(efd, fd);
+                    match list.bsearch(|&(f, _, _)| f.cmp(&fd)) {
+                        Some(i) => {
+                            drop(list.remove(i));
+                            del(efd, fd);
+                        }
+                        None => {}
                     }
                     chan.send(());
                 }
 
                 Data(Shutdown) => {
-                    assert!(map.len() == 0);
+                    assert!(list.len() == 0);
                     break 'outer;
                 }