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}