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

1 files changed, 15 insertions, 0 deletions

diff --git a/src/lib/_int.rs b/src/lib/_int.rs
index 2afb3c4f..b6399669 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);
+}