Add a (coarse, first-pass) deque implementation to stdlib.

4 files changed, 155 insertions, 7 deletions

diff --git a/src/lib/_int.rs b/src/lib/_int.rs
index 2afb3c4f6d9..b6399669c43 100644
--- a/src/lib/_int.rs
+++ b/src/lib/_int.rs
@@ -1,3 +1,5 @@
+import std.sys;
+
 fn add(int x, int y) -> int { ret x + y; }
 fn sub(int x, int y) -> int { ret x - y; }
 fn mul(int x, int y) -> int { ret x * y; }
@@ -24,3 +26,16 @@ iter urange(mutable uint lo, uint hi) -> uint {
     lo += uint(1);
   }
 }
+
+fn next_power_of_two(uint n) -> uint {
+  // FIXME change |* uint(4)| below to |* uint(8) / uint(2)| and watch the
+  // world explode.
+  let uint halfbits = sys.rustrt.size_of[uint]() * uint(4);
+  let uint tmp = n - uint(1);
+  let uint shift = uint(1);
+  while (shift <= halfbits) {
+    tmp |= tmp >> shift;
+    shift <<= uint(1);
+  }
+  ret tmp + uint(1);
+}
diff --git a/src/lib/deque.rs b/src/lib/deque.rs
new file mode 100644
index 00000000000..b41c051f5fc
--- /dev/null
+++ b/src/lib/deque.rs
@@ -0,0 +1,137 @@
+/**
+ * A deque, for fun.  Untested as of yet.  Likely buggy.
+ */
+
+import std.util;
+import std._vec;
+import std._int;
+
+type t[T] = obj {
+  fn size() -> uint;
+
+  fn add_front(&T t);
+  fn add_back(&T t);
+
+  fn pop_front() -> T;
+  fn pop_back() -> T;
+
+  fn peek_front() -> T;
+  fn peek_back() -> T;
+};
+
+fn create[T]() -> t[T] {
+
+  type cell[T] = mutable util.option[T];
+
+  let uint initial_capacity = uint(32); // 2^5
+
+  /**
+   * Grow is only called on full elts, so nelts is also len(elts), unlike
+   * elsewhere.
+   */
+  fn grow[T](uint nelts, uint lo, vec[cell[T]] elts) -> vec[cell[T]] {
+    check (nelts == _vec.len[cell[T]](elts));
+
+    fn fill[T](uint i, uint nelts, uint lo, &vec[cell[T]] old) -> cell[T] {
+      if (i < nelts) {
+        ret old.(int((lo + i) % nelts));
+      } else {
+        ret util.none[T]();
+      }
+    }
+
+    let uint nalloc = _int.next_power_of_two(nelts + uint(1));
+    let _vec.init_op[cell[T]] copy_op = bind fill[T](_, nelts, lo, elts);
+    ret _vec.init_fn[cell[T]](copy_op, nalloc);
+  }
+
+  /**
+   * FIXME (issue #94): We're converting to int every time we index into the
+   * vec, but we really want to index with the lo and hi uints that we have
+   * around.
+   */
+
+  fn get[T](&vec[cell[T]] elts, uint i) -> T {
+    alt (elts.(int(i))) {
+      case (util.some[T](t)) { ret t; }
+      case (_) { fail; }
+    }
+  }
+
+  obj deque[T](mutable uint nelts,
+               mutable uint lo,
+               mutable uint hi,
+               mutable vec[cell[T]] elts)
+  {
+    fn size() -> uint { ret nelts; }
+
+    fn add_front(&T t) {
+      let uint oldlo = lo;
+
+      if (lo == uint(0)) {
+        lo = _vec.len[cell[T]](elts) - uint(1);
+      } else {
+        lo -= uint(1);
+      }
+
+      if (lo == hi) {
+        elts = grow[T](nelts, oldlo, elts);
+        lo = _vec.len[cell[T]](elts) - uint(1);
+        hi = nelts - uint(1);
+      }
+
+      elts.(int(lo)) = util.some[T](t);
+      nelts += uint(1);
+    }
+
+    fn add_back(&T t) {
+      hi = (hi + uint(1)) % _vec.len[cell[T]](elts);
+
+      if (lo == hi) {
+        elts = grow[T](nelts, lo, elts);
+        lo = uint(0);
+        hi = nelts;
+      }
+
+      elts.(int(hi)) = util.some[T](t);
+      nelts += uint(1);
+    }
+
+    /**
+     * We actually release (turn to none()) the T we're popping so that we
+     * don't keep anyone's refcount up unexpectedly.
+     */
+    fn pop_front() -> T {
+      let T t = get[T](elts, lo);
+      elts.(int(lo)) = util.none[T]();
+      lo = (lo + uint(1)) % _vec.len[cell[T]](elts);
+      ret t;
+    }
+
+    fn pop_back() -> T {
+      let T t = get[T](elts, hi);
+      elts.(int(hi)) = util.none[T]();
+
+      if (hi == uint(0)) {
+        hi = _vec.len[cell[T]](elts) - uint(1);
+      } else {
+        hi -= uint(1);
+      }
+
+      ret t;
+    }
+
+    fn peek_front() -> T {
+      ret get[T](elts, lo);
+    }
+
+    fn peek_back() -> T {
+      ret get[T](elts, hi);
+    }
+  }
+
+  let vec[cell[T]] v = _vec.init_elt[cell[T]](util.none[T](),
+                                              initial_capacity);
+
+  ret deque[T](uint(0), uint(0), uint(0), v);
+}
diff --git a/src/lib/map.rs b/src/lib/map.rs
index 8df2cba02e4..06139bb7c9b 100644
--- a/src/lib/map.rs
+++ b/src/lib/map.rs
@@ -153,8 +153,7 @@ fn mk_hashmap[K, V](&hashfn[K] hasher, &eqfn[K] eqer) -> hashmap[K, V] {
   }
 
   let vec[mutable bucket[V]] bkts =
-    _vec.init_elt[mutable bucket[V]](nil[V](),
-                                     uint(initial_capacity));
+    _vec.init_elt[mutable bucket[V]](nil[V](), initial_capacity);
 
   ret hashmap[K, V](hasher, eqer, bkts, uint(0), uint(0), load_factor);
 }
diff --git a/src/lib/std.rc b/src/lib/std.rc
index 4bdad5bd248..dfc404ecbe9 100644
--- a/src/lib/std.rc
+++ b/src/lib/std.rc
@@ -26,11 +26,7 @@ auth _io = unsafe;
 auth _str = unsafe;
 auth _vec = unsafe;
 
-/**
- * FIXME for some reason 'auth sys = unsafe' isn't enough here to silence
- * the effect system about map.mk_hashmap.hashl and .hashr using
- * sys.rustrt.size_of and thereby being unsafe.
- */
+auth _int.next_power_of_two = unsafe;
 auth map.mk_hashmap = unsafe;
 
 // Target-OS module.
@@ -46,3 +42,4 @@ alt (target_os) {
 }
 
 mod map;
+mod deque;