Merge pull request #992 from zig-lang/segmented-list

Segmented list implementation
ziglang · May 7, 2018 · 78ba3b8 · 78ba3b8
2 parents 7fdbaec + 81007d0
commit 78ba3b8
Show file tree

Hide file tree

Showing 5 changed files with 334 additions and 34 deletions.
diff --git a/CMakeLists.txt b/CMakeLists.txt
@@ -416,8 +416,8 @@ set(ZIG_CPP_SOURCES
 set(ZIG_STD_FILES
     "array_list.zig"
     "atomic/index.zig"
-    "atomic/stack.zig"
     "atomic/queue.zig"
+    "atomic/stack.zig"
     "base64.zig"
     "buf_map.zig"
     "buf_set.zig"
@@ -427,13 +427,13 @@ set(ZIG_STD_FILES
     "c/index.zig"
     "c/linux.zig"
     "c/windows.zig"
+    "crypto/blake2.zig"
+    "crypto/hmac.zig"
     "crypto/index.zig"
     "crypto/md5.zig"
     "crypto/sha1.zig"
     "crypto/sha2.zig"
     "crypto/sha3.zig"
-    "crypto/blake2.zig"
-    "crypto/hmac.zig"
     "cstr.zig"
     "debug/failing_allocator.zig"
     "debug/index.zig"
@@ -445,12 +445,12 @@ set(ZIG_STD_FILES
     "fmt/errol/index.zig"
     "fmt/errol/lookup.zig"
     "fmt/index.zig"
-    "hash_map.zig"
-    "hash/index.zig"
     "hash/adler.zig"
     "hash/crc.zig"
     "hash/fnv.zig"
+    "hash/index.zig"
     "hash/siphash.zig"
+    "hash_map.zig"
     "heap.zig"
     "index.zig"
     "io.zig"
@@ -466,6 +466,28 @@ set(ZIG_STD_FILES
     "math/atanh.zig"
     "math/cbrt.zig"
     "math/ceil.zig"
+    "math/complex/abs.zig"
+    "math/complex/acos.zig"
+    "math/complex/acosh.zig"
+    "math/complex/arg.zig"
+    "math/complex/asin.zig"
+    "math/complex/asinh.zig"
+    "math/complex/atan.zig"
+    "math/complex/atanh.zig"
+    "math/complex/conj.zig"
+    "math/complex/cos.zig"
+    "math/complex/cosh.zig"
+    "math/complex/exp.zig"
+    "math/complex/index.zig"
+    "math/complex/ldexp.zig"
+    "math/complex/log.zig"
+    "math/complex/pow.zig"
+    "math/complex/proj.zig"
+    "math/complex/sin.zig"
+    "math/complex/sinh.zig"
+    "math/complex/sqrt.zig"
+    "math/complex/tan.zig"
+    "math/complex/tanh.zig"
     "math/copysign.zig"
     "math/cos.zig"
     "math/cosh.zig"
@@ -502,33 +524,12 @@ set(ZIG_STD_FILES
     "math/tan.zig"
     "math/tanh.zig"
     "math/trunc.zig"
-    "math/complex/abs.zig"
-    "math/complex/acosh.zig"
-    "math/complex/acos.zig"
-    "math/complex/arg.zig"
-    "math/complex/asinh.zig"
-    "math/complex/asin.zig"
-    "math/complex/atanh.zig"
-    "math/complex/atan.zig"
-    "math/complex/conj.zig"
-    "math/complex/cosh.zig"
-    "math/complex/cos.zig"
-    "math/complex/exp.zig"
-    "math/complex/index.zig"
-    "math/complex/ldexp.zig"
-    "math/complex/log.zig"
-    "math/complex/pow.zig"
-    "math/complex/proj.zig"
-    "math/complex/sinh.zig"
-    "math/complex/sin.zig"
-    "math/complex/sqrt.zig"
-    "math/complex/tanh.zig"
-    "math/complex/tan.zig"
     "mem.zig"
     "net.zig"
     "os/child_process.zig"
     "os/darwin.zig"
     "os/darwin_errno.zig"
+    "os/epoch.zig"
     "os/file.zig"
     "os/get_user_id.zig"
     "os/index.zig"
@@ -538,13 +539,13 @@ set(ZIG_STD_FILES
     "os/linux/x86_64.zig"
     "os/path.zig"
     "os/time.zig"
-    "os/epoch.zig"
     "os/windows/error.zig"
     "os/windows/index.zig"
     "os/windows/util.zig"
     "os/zen.zig"
     "rand/index.zig"
     "rand/ziggurat.zig"
+    "segmented_list.zig"
     "sort.zig"
     "special/bootstrap.zig"
     "special/bootstrap_lib.zig"

diff --git a/std/index.zig b/std/index.zig
@@ -7,6 +7,7 @@ pub const BufferOutStream = @import("buffer.zig").BufferOutStream;
 pub const HashMap = @import("hash_map.zig").HashMap;
 pub const LinkedList = @import("linked_list.zig").LinkedList;
 pub const IntrusiveLinkedList = @import("linked_list.zig").IntrusiveLinkedList;
+pub const SegmentedList = @import("segmented_list.zig").SegmentedList;
 
 pub const atomic = @import("atomic/index.zig");
 pub const base64 = @import("base64.zig");
@@ -43,6 +44,7 @@ test "std" {
     _ = @import("buffer.zig");
     _ = @import("hash_map.zig");
     _ = @import("linked_list.zig");
+    _ = @import("segmented_list.zig");
 
     _ = @import("base64.zig");
     _ = @import("build.zig");

diff --git a/std/math/index.zig b/std/math/index.zig
@@ -558,6 +558,32 @@ test "math.floorPowerOfTwo" {
     comptime testFloorPowerOfTwo();
 }
 
+pub fn log2_int(comptime T: type, x: T) Log2Int(T) {
+    assert(x != 0);
+    return Log2Int(T)(T.bit_count - 1 - @clz(x));
+}
+
+pub fn log2_int_ceil(comptime T: type, x: T) Log2Int(T) {
+    assert(x != 0);
+    const log2_val = log2_int(T, x);
+    if (T(1) << log2_val == x)
+        return log2_val;
+    return log2_val + 1;
+}
+
+test "std.math.log2_int_ceil" {
+    assert(log2_int_ceil(u32, 1) == 0);
+    assert(log2_int_ceil(u32, 2) == 1);
+    assert(log2_int_ceil(u32, 3) == 2);
+    assert(log2_int_ceil(u32, 4) == 2);
+    assert(log2_int_ceil(u32, 5) == 3);
+    assert(log2_int_ceil(u32, 6) == 3);
+    assert(log2_int_ceil(u32, 7) == 3);
+    assert(log2_int_ceil(u32, 8) == 3);
+    assert(log2_int_ceil(u32, 9) == 4);
+    assert(log2_int_ceil(u32, 10) == 4);
+}
+
 fn testFloorPowerOfTwo() void {
     assert(floorPowerOfTwo(u32, 63) == 32);
     assert(floorPowerOfTwo(u32, 64) == 64);

diff --git a/std/math/log2.zig b/std/math/log2.zig
@@ -31,17 +31,12 @@ pub fn log2(x: var) @typeOf(x) {
             return result;
         },
         TypeId.Int => {
-            return log2_int(T, x);
+            return math.log2_int(T, x);
         },
         else => @compileError("log2 not implemented for " ++ @typeName(T)),
     }
 }
 
-pub fn log2_int(comptime T: type, x: T) T {
-    assert(x != 0);
-    return T.bit_count - 1 - T(@clz(x));
-}
-
 pub fn log2_32(x_: f32) f32 {
     const ivln2hi: f32 =  1.4428710938e+00;
     const ivln2lo: f32 = -1.7605285393e-04;