Move std::{trie, hashmap} to libcollections

These two containers are indeed collections, so their 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.

1 files changed, 27 insertions, 11 deletions

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;
                 }