1const std = @import("std.zig");
  2const StringHashMap = std.StringHashMap;
  3const mem = @import("mem.zig");
  4const Allocator = mem.Allocator;
  5const testing = std.testing;
  6
  7/// A BufSet is a set of strings.  The BufSet duplicates
  8/// strings internally, and never takes ownership of strings
  9/// which are passed to it.
 10pub const BufSet = struct {
 11    hash_map: BufSetHashMap,
 12
 13    const BufSetHashMap = StringHashMap(void);
 14    pub const Iterator = BufSetHashMap.KeyIterator;
 15
 16    /// Create a BufSet using an allocator.  The allocator will
 17    /// be used internally for both backing allocations and
 18    /// string duplication.
 19    pub fn init(a: Allocator) BufSet {
 20        return .{ .hash_map = BufSetHashMap.init(a) };
 21    }
 22
 23    /// Free a BufSet along with all stored keys.
 24    pub fn deinit(self: *BufSet) void {
 25        var it = self.hash_map.keyIterator();
 26        while (it.next()) |key_ptr| {
 27            self.free(key_ptr.*);
 28        }
 29        self.hash_map.deinit();
 30        self.* = undefined;
 31    }
 32
 33    /// Insert an item into the BufSet.  The item will be
 34    /// copied, so the caller may delete or reuse the
 35    /// passed string immediately.
 36    pub fn insert(self: *BufSet, value: []const u8) !void {
 37        const gop = try self.hash_map.getOrPut(value);
 38        if (!gop.found_existing) {
 39            gop.key_ptr.* = self.copy(value) catch |err| {
 40                _ = self.hash_map.remove(value);
 41                return err;
 42            };
 43        }
 44    }
 45
 46    /// Check if the set contains an item matching the passed string
 47    pub fn contains(self: BufSet, value: []const u8) bool {
 48        return self.hash_map.contains(value);
 49    }
 50
 51    /// Remove an item from the set.
 52    pub fn remove(self: *BufSet, value: []const u8) void {
 53        const kv = self.hash_map.fetchRemove(value) orelse return;
 54        self.free(kv.key);
 55    }
 56
 57    /// Returns the number of items stored in the set
 58    pub fn count(self: *const BufSet) usize {
 59        return self.hash_map.count();
 60    }
 61
 62    /// Returns an iterator over the items stored in the set.
 63    /// Iteration order is arbitrary.
 64    pub fn iterator(self: *const BufSet) Iterator {
 65        return self.hash_map.keyIterator();
 66    }
 67
 68    /// Get the allocator used by this set
 69    pub fn allocator(self: *const BufSet) Allocator {
 70        return self.hash_map.allocator;
 71    }
 72
 73    /// Creates a copy of this BufSet, using a specified allocator.
 74    pub fn cloneWithAllocator(
 75        self: *const BufSet,
 76        new_allocator: Allocator,
 77    ) Allocator.Error!BufSet {
 78        const cloned_hashmap = try self.hash_map.cloneWithAllocator(new_allocator);
 79        const cloned = BufSet{ .hash_map = cloned_hashmap };
 80        var it = cloned.hash_map.keyIterator();
 81        while (it.next()) |key_ptr| {
 82            key_ptr.* = try cloned.copy(key_ptr.*);
 83        }
 84
 85        return cloned;
 86    }
 87
 88    /// Creates a copy of this BufSet, using the same allocator.
 89    pub fn clone(self: *const BufSet) Allocator.Error!BufSet {
 90        return self.cloneWithAllocator(self.allocator());
 91    }
 92
 93    test clone {
 94        var original = BufSet.init(testing.allocator);
 95        defer original.deinit();
 96        try original.insert("x");
 97
 98        var cloned = try original.clone();
 99        defer cloned.deinit();
100        cloned.remove("x");
101        try testing.expect(original.count() == 1);
102        try testing.expect(cloned.count() == 0);
103
104        try testing.expectError(
105            error.OutOfMemory,
106            original.cloneWithAllocator(testing.failing_allocator),
107        );
108    }
109
110    fn free(self: *const BufSet, value: []const u8) void {
111        self.hash_map.allocator.free(value);
112    }
113
114    fn copy(self: *const BufSet, value: []const u8) ![]const u8 {
115        const result = try self.hash_map.allocator.alloc(u8, value.len);
116        @memcpy(result, value);
117        return result;
118    }
119};
120
121test BufSet {
122    var bufset = BufSet.init(std.testing.allocator);
123    defer bufset.deinit();
124
125    try bufset.insert("x");
126    try testing.expect(bufset.count() == 1);
127    bufset.remove("x");
128    try testing.expect(bufset.count() == 0);
129
130    try bufset.insert("x");
131    try bufset.insert("y");
132    try bufset.insert("z");
133}
134
135test "clone with arena" {
136    const allocator = std.testing.allocator;
137    var arena = std.heap.ArenaAllocator.init(allocator);
138    defer arena.deinit();
139
140    var buf = BufSet.init(allocator);
141    defer buf.deinit();
142    try buf.insert("member1");
143    try buf.insert("member2");
144
145    _ = try buf.cloneWithAllocator(arena.allocator());
146}