voroskoi/skiplist.zig - Change L5PE2JYUWXH6KHU7COHEMCHPK7LXFIFTXXCT7GB26S3U5RT5WPKAC

Add refcounting code to free up deleted nodes

Created by voroskoi on January 11, 2025

L5PE2JYUWXH6KHU7COHEMCHPK7LXFIFTXXCT7GB26S3U5RT5WPKAC

Dependencies

In channels

main

Change contents

Insertion in src/lazy.zig at line 50 [4.108]

[3.42]

[4.1073]

            /// Number of runtime references to this node. Removing only allowed when equals 0.
            refs: std.atomic.Value(u8) = std.atomic.Value(u8).init(0),

Insertion in src/lazy.zig at line 156 [4.108]

[5.6059]

[4.4728]

                }
                { // reference counting
                    _ = pred.refs.fetchAdd(1, .monotonic);
                    if (curr != null) {
                        _ = curr.?.refs.fetchAdd(1, .monotonic);
                    }

Insertion in src/lazy.zig at line 181 [4.108]

[6.7772]

[7.1416]

            defer {
                for (preds, succs) |pred, succ| {
                    if (pred != null) {
                        _ = pred.?.refs.fetchSub(1, .monotonic);
                    }
                    if (succ != null) {
                        _ = succ.?.refs.fetchSub(1, .monotonic);
                    }
                }
            }

Insertion in src/lazy.zig at line 217 [4.108]

[8.37]

[7.1703]

                defer {
                    for (preds, succs) |pred, succ| {
                        if (pred != null) {
                            _ = pred.?.refs.fetchSub(1, .monotonic);
                        }
                        if (succ != null) {
                            _ = succ.?.refs.fetchSub(1, .monotonic);
                        }
                    }
                }

Deletion in src/lazy.zig at line 292 [4.108]
B:BD[9.121] → [2.542:564]
```
            _ = self;
```

Insertion in src/lazy.zig at line 295 [4.108]

[4.9382]

[10.1021]

            defer {
                if (node_delete != null) {
                    while (node_delete.?.refs.load(.monotonic) != 0) {}
                    node_delete.?.deinit(self.allocator);
                }
            }

Insertion in src/lazy.zig at line 308 [4.108]

[8.2648]

[11.0]

                defer {
                    for (preds, succs) |pred, succ| {
                        if (pred != null) {
                            _ = pred.?.refs.fetchSub(1, .monotonic);
                        }
                        if (succ != null) {
                            _ = succ.?.refs.fetchSub(1, .monotonic);
                        }
                    }
                }

Deletion in src/lazy.zig at line 369 [4.108]

B:BD[2.866] → [2.866:867]

B:BD[2.867] → [2.867:970]

B:BD[2.970] → [2.970:1082]

B:BD[2.1082] → [2.1082:1147]


                        // TODO: If we free up the memory right here then any findNode() call in other
                        // threads can SIGSEGV. We have to count the references or never free up removed Nodes.
                        // node_delete.?.deinit(self.allocator);