Improve zig's skiplist implementation

4 files changed, 371 insertions, 186 deletions

diff --git a/SkipList.zig b/SkipList.zig
deleted file mode 100644
index 9d9fc94..0000000
--- a/SkipList.zig
+++ /dev/null
@@ -1,185 +0,0 @@
-const std = @import("std");
-
-const Allocator = std.mem.Allocator;
-const DefaultPrng = std.rand.DefaultPrng;
-const Error = error{OutOfMemory};
-const MAXLVL = 32;
-
-pub fn SkipList(comptime T: type) type {
-    return struct {
-        pub const Node = struct {
-            key: u64,
-            value: T,
-            forward: []?*Node,
-            backward: ?*Node,
-
-            pub inline fn next(self: Node) ?*Node {
-                return self.forward[0];
-            }
-
-            pub inline fn prev(self: Node) ?*Node {
-                return self.backward;
-            }
-        };
-
-        const Self = @This();
-
-        header: *Node,
-        count: usize = 0,
-        level: usize = 1,
-
-        allocator: Allocator,
-        prng: DefaultPrng,
-
-        pub fn init(allocator: Allocator, seed: u64) Error!Self {
-            const node = try allocator.create(Node);
-            node.forward = try allocator.alloc(?*Node, MAXLVL);
-            @memset(node.forward, null);
-            return Self{
-                .header = node,
-                .allocator = allocator,
-                .prng = DefaultPrng.init(seed),
-            };
-        }
-
-        pub fn deinit(self: Self) void {
-            var node: ?*Node = self.header;
-            while (node) |n| {
-                node = n.next();
-                self.allocator.free(n.forward);
-                self.allocator.destroy(n);
-            }
-        }
-
-        fn find(self: *Self, key: u64, update: ?[]*Node) ?*Node {
-            var node: *Node = self.header;
-            var lvl = self.level - 1;
-
-            while (true) : (lvl -= 1) {
-                while (node.forward[lvl]) |next| {
-                    if (next.key >= key) break;
-                    node = next;
-                }
-                if (update) |u| u[lvl] = node;
-
-                if (lvl == 0) break;
-            }
-
-            return node.next();
-        }
-
-        pub fn insert(self: *Self, key: u64, val: T) Error!*Node {
-            var update: [MAXLVL]*Node = undefined;
-            const maybe_node = self.find(key, &update);
-
-            if (maybe_node) |node| {
-                if (node.key == key) {
-                    node.value = val;
-                    return node;
-                }
-            }
-
-            var lvl: usize = 1;
-            while (self.prng.random().int(u2) == 0) lvl += 1;
-            if (lvl > self.level) {
-                if (lvl > MAXLVL) lvl = MAXLVL;
-                for (self.level..lvl) |i| {
-                    update[i] = self.header;
-                }
-                self.level = lvl;
-            }
-
-            var node = try self.allocator.create(Node);
-            node.key = key;
-            node.value = val;
-            node.forward = try self.allocator.alloc(?*Node, lvl);
-
-            for (0..lvl) |i| {
-                node.forward[i] = update[i].forward[i];
-                update[i].forward[i] = node;
-            }
-
-            node.backward = if (update[0] == self.header) null else update[0];
-
-            if (node.next()) |next| {
-                next.backward = node;
-            } else {
-                self.header.backward = node;
-            }
-
-            self.count += 1;
-
-            return node;
-        }
-
-        fn delnode(self: *Self, node: *Node, update: []*Node) void {
-            for (0..self.level) |lvl| {
-                if (update[lvl].forward[lvl] != node) break;
-                update[lvl].forward[lvl] = node.forward[lvl];
-            }
-
-            while (self.level > 1) {
-                if (self.header.forward[self.level - 1] != null) break;
-
-                self.level -= 1;
-            }
-
-            if (node.next()) |next| {
-                next.backward = node.backward;
-            } else {
-                self.header.backward = node.backward;
-            }
-
-            self.count -= 1;
-            self.allocator.free(node.forward);
-            self.allocator.destroy(node);
-        }
-
-        pub fn delete(self: *Self, key: u64) bool {
-            var update: [MAXLVL]*Node = undefined;
-            const maybe_node = self.find(key, &update);
-
-            if (maybe_node) |node| {
-                if (node.key == key) {
-                    self.delnode(node, &update);
-                    return true;
-                }
-            }
-            return false;
-        }
-
-        pub fn delrange(self: *Self, from: u64, to: u64) usize {
-            var update: [MAXLVL]*Node = undefined;
-            var maybe_node = self.find(from, &update);
-            var total: usize = 0;
-
-            while (maybe_node) |node| {
-                if (node.key >= to) break;
-
-                maybe_node = node.next();
-                self.delnode(node, &update);
-                total += 1;
-            }
-
-            return total;
-        }
-
-        pub fn search(self: *Self, key: u64) ?*Node {
-            const maybe_node = self.find(key, null);
-            if (maybe_node) |node| {
-                if (node.key == key) {
-                    return node;
-                }
-            }
-            return null;
-        }
-
-        pub inline fn first(self: Self) ?*Node {
-            return self.header.forward[0];
-        }
-
-        pub inline fn last(self: Self) ?*Node {
-            return self.header.backward;
-        }
-    };
-}
diff --git a/examples/dump.zig b/examples/dump.zig
index 3ce422b..8200a06 100644
--- a/examples/dump.zig
+++ b/examples/dump.zig
@@ -1,7 +1,11 @@
 const std = @import("std");
-const SkipList = @import("../SkipList.zig").SkipList(u64);
+const SkipList = @import("skiplist.zig").EasySkipList(u64, u64, compare);
 const print = std.debug.print;
 
+fn compare(a: u64, b: u64) std.math.Order {
+    return std.math.order(a, b);
+}
+
 fn dump(list: SkipList) void {
     var lvl: usize = list.level - 1;
 
diff --git a/examples/skiplist.zig b/examples/skiplist.zig
new file mode 120000
index 0000000..d771fcb
--- /dev/null
+++ b/examples/skiplist.zig
@@ -0,0 +1 @@
+../skiplist.zig
\ No newline at end of file
diff --git a/skiplist.zig b/skiplist.zig
new file mode 100644
index 0000000..323d324
--- /dev/null
+++ b/skiplist.zig
@@ -0,0 +1,365 @@
+const std = @import("std");
+const Allocator = std.mem.Allocator;
+const Error = Allocator.Error;
+const Order = std.math.Order;
+
+pub const default_max_level = 32;
+
+pub fn EasySkipList(
+    comptime K: type,
+    comptime V: type,
+    comptime compareFn: fn (K, K) Order,
+) type {
+    return SkipList(K, V, std.rand.Pcg, compareFn, default_max_level);
+}
+
+pub fn SkipList(
+    comptime K: type,
+    comptime V: type,
+    comptime Prng: type,
+    comptime compareFn: fn (K, K) Order,
+    comptime maximum_level: usize,
+) type {
+    return struct {
+        const Self = @This();
+
+        header: *Node,
+        count: usize = 0,
+        level: usize = 1,
+
+        allocator: Allocator,
+        prng: Prng,
+
+        pub const max_level = maximum_level;
+
+        pub const Node = struct {
+            key: K,
+            value: V,
+            forward: []?*Node,
+
+            pub inline fn next(self: Node) ?*Node {
+                return self.forward[0];
+            }
+        };
+
+        pub fn init(allocator: Allocator, seed: u64) Error!Self {
+            const node = try allocator.create(Node);
+            node.forward = try allocator.alloc(?*Node, max_level);
+            @memset(node.forward, null);
+            return .{
+                .header = node,
+                .allocator = allocator,
+                .prng = Prng.init(seed),
+            };
+        }
+
+        pub fn deinit(self: Self) void {
+            var node: ?*Node = self.header;
+            while (node) |n| {
+                node = n.next();
+                self.allocator.free(n.forward);
+                self.allocator.destroy(n);
+            }
+        }
+
+        fn find(self: *Self, key: K, update: ?[]*Node) ?*Node {
+            var node: *Node = self.header;
+            var lvl = self.level - 1;
+
+            while (true) : (lvl -= 1) {
+                while (node.forward[lvl]) |next| {
+                    if (compareFn(next.key, key).compare(.gte)) break;
+                    node = next;
+                }
+                if (update) |u| u[lvl] = node;
+
+                if (lvl == 0) break;
+            }
+
+            return node.next();
+        }
+
+        pub fn insert(self: *Self, key: K, val: V) Error!*Node {
+            var update: [max_level]*Node = undefined;
+            const maybe_node = self.find(key, &update);
+
+            if (maybe_node) |node| {
+                if (compareFn(node.key, key).compare(.eq)) {
+                    node.value = val;
+                    return node;
+                }
+            }
+
+            var lvl: usize = 1;
+            while (self.prng.random().int(u2) == 0) lvl += 1;
+            if (lvl > self.level) {
+                if (lvl > max_level) lvl = max_level;
+                for (self.level..lvl) |i| {
+                    update[i] = self.header;
+                }
+                self.level = lvl;
+            }
+
+            var node = try self.allocator.create(Node);
+            node.key = key;
+            node.value = val;
+            node.forward = try self.allocator.alloc(?*Node, lvl);
+
+            for (0..lvl) |i| {
+                node.forward[i] = update[i].forward[i];
+                update[i].forward[i] = node;
+            }
+
+            self.count += 1;
+
+            return node;
+        }
+
+        fn deleteNode(self: *Self, node: *Node, update: []*Node) void {
+            for (0..self.level) |lvl| {
+                if (update[lvl].forward[lvl] != node) break;
+                update[lvl].forward[lvl] = node.forward[lvl];
+            }
+
+            while (self.level > 1) : (self.level -= 1) {
+                if (self.header.forward[self.level - 1] != null) break;
+            }
+
+            self.count -= 1;
+            self.allocator.free(node.forward);
+            self.allocator.destroy(node);
+        }
+
+        pub fn delete(self: *Self, key: K) bool {
+            var update: [max_level]*Node = undefined;
+            const maybe_node = self.find(key, &update);
+
+            if (maybe_node) |node| {
+                if (compareFn(node.key, key).compare(.eq)) {
+                    self.deleteNode(node, &update);
+                    return true;
+                }
+            }
+            return false;
+        }
+
+        pub fn deleteRange(self: *Self, from: K, to: K) usize {
+            var update: [max_level]*Node = undefined;
+            var maybe_node = self.find(from, &update);
+            var total: usize = 0;
+
+            while (maybe_node) |node| : (total += 1) {
+                if (compareFn(node.key, to).compare(.gte)) break;
+                maybe_node = node.next();
+                self.deleteNode(node, &update);
+            }
+
+            return total;
+        }
+
+        pub fn search(self: *Self, key: u64) ?*Node {
+            const maybe_node = self.find(key, null);
+            if (maybe_node) |node| {
+                if (compareFn(node.key, key).compare(.eq)) {
+                    return node;
+                }
+            }
+            return null;
+        }
+
+        pub inline fn first(self: Self) ?*Node {
+            return self.header.forward[0];
+        }
+    };
+}
+
+pub fn EasyDoublySkipList(
+    comptime K: type,
+    comptime V: type,
+    comptime compareFn: fn (K, K) Order,
+) type {
+    return DoublySkipList(K, V, std.rand.Pcg, compareFn, default_max_level);
+}
+
+pub fn DoublySkipList(
+    comptime K: type,
+    comptime V: type,
+    comptime Prng: type,
+    comptime compareFn: fn (K, K) Order,
+    comptime maximum_level: usize,
+) type {
+    return struct {
+        const Self = @This();
+
+        header: *Node,
+        count: usize = 0,
+        level: usize = 1,
+
+        allocator: Allocator,
+        prng: Prng,
+
+        pub const max_level = maximum_level;
+
+        pub const Node = struct {
+            key: K,
+            value: V,
+            forward: []?*Node,
+            backward: ?*Node,
+
+            pub inline fn next(self: Node) ?*Node {
+                return self.forward[0];
+            }
+
+            pub inline fn prev(self: Node) ?*Node {
+                return self.backward;
+            }
+        };
+
+        pub fn init(allocator: Allocator, seed: u64) Error!Self {
+            const node = try allocator.create(Node);
+            node.forward = try allocator.alloc(?*Node, max_level);
+            @memset(node.forward, null);
+            return .{
+                .header = node,
+                .allocator = allocator,
+                .prng = Prng.init(seed),
+            };
+        }
+
+        pub fn deinit(self: Self) void {
+            var node: ?*Node = self.header;
+            while (node) |n| {
+                node = n.next();
+                self.allocator.free(n.forward);
+                self.allocator.destroy(n);
+            }
+        }
+
+        fn find(self: *Self, key: K, update: ?[]*Node) ?*Node {
+            var node: *Node = self.header;
+            var lvl = self.level - 1;
+
+            while (true) : (lvl -= 1) {
+                while (node.forward[lvl]) |next| {
+                    if (compareFn(next.key, key).compare(.gte)) break;
+                    node = next;
+                }
+                if (update) |u| u[lvl] = node;
+
+                if (lvl == 0) break;
+            }
+
+            return node.next();
+        }
+
+        pub fn insert(self: *Self, key: K, val: V) Error!*Node {
+            var update: [max_level]*Node = undefined;
+            const maybe_node = self.find(key, &update);
+
+            if (maybe_node) |node| {
+                if (compareFn(node.key, key).compare(.eq)) {
+                    node.value = val;
+                    return node;
+                }
+            }
+
+            var lvl: usize = 1;
+            while (self.prng.random().int(u2) == 0) lvl += 1;
+            if (lvl > self.level) {
+                if (lvl > max_level) lvl = max_level;
+                for (self.level..lvl) |i| {
+                    update[i] = self.header;
+                }
+                self.level = lvl;
+            }
+
+            var node = try self.allocator.create(Node);
+            node.key = key;
+            node.value = val;
+            node.forward = try self.allocator.alloc(?*Node, lvl);
+
+            for (0..lvl) |i| {
+                node.forward[i] = update[i].forward[i];
+                update[i].forward[i] = node;
+            }
+
+            node.backward = if (update[0] == self.header) null else update[0];
+
+            if (node.next()) |next| {
+                next.backward = node;
+            } else {
+                self.header.backward = node;
+            }
+
+            self.count += 1;
+
+            return node;
+        }
+
+        fn deleteNode(self: *Self, node: *Node, update: []*Node) void {
+            for (0..self.level) |lvl| {
+                if (update[lvl].forward[lvl] != node) break;
+                update[lvl].forward[lvl] = node.forward[lvl];
+            }
+
+            while (self.level > 1) : (self.level -= 1) {
+                if (self.header.forward[self.level - 1] != null) break;
+            }
+
+            if (node.next()) |next| {
+                next.backward = node.backward;
+            } else {
+                self.header.backward = node.backward;
+            }
+
+            self.count -= 1;
+            self.allocator.free(node.forward);
+            self.allocator.destroy(node);
+        }
+
+        pub fn delete(self: *Self, key: K) bool {
+            var update: [max_level]*Node = undefined;
+            const maybe_node = self.find(key, &update);
+
+            if (maybe_node) |node| {
+                if (compareFn(node.key, key).compare(.eq)) {
+                    self.deleteNode(node, &update);
+                    return true;
+                }
+            }
+            return false;
+        }
+
+        pub fn deleteRange(self: *Self, from: K, to: K) usize {
+            var update: [max_level]*Node = undefined;
+            var maybe_node = self.find(from, &update);
+            var total: usize = 0;
+
+            while (maybe_node) |node| : (total += 1) {
+                if (compareFn(node.key, to).compare(.gte)) break;
+                maybe_node = node.next();
+                self.deleteNode(node, &update);
+            }
+
+            return total;
+        }
+
+        pub fn search(self: *Self, key: u64) ?*Node {
+            const maybe_node = self.find(key, null);
+            if (maybe_node) |node| {
+                if (compareFn(node.key, key).compare(.eq)) {
+                    return node;
+                }
+            }
+            return null;
+        }
+
+        pub inline fn first(self: Self) ?*Node {
+            return self.header.forward[0];
+        }
+
+        pub inline fn last(self: Self) ?*Node {
+            return self.header.backward;
+        }
+    };
+}