From 6c2e0c2046a4c1d01587cc15ea2f59af32743eb4 Mon Sep 17 00:00:00 2001 From: Frank Denis Date: Fri, 1 Jan 2021 00:07:36 +0100 Subject: Year++ --- lib/std/array_hash_map.zig | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/std/array_hash_map.zig') diff --git a/lib/std/array_hash_map.zig b/lib/std/array_hash_map.zig index e5ad26cb45..7c591bed1b 100644 --- a/lib/std/array_hash_map.zig +++ b/lib/std/array_hash_map.zig @@ -1,5 +1,5 @@ // SPDX-License-Identifier: MIT -// Copyright (c) 2015-2020 Zig Contributors +// Copyright (c) 2015-2021 Zig Contributors // This file is part of [zig](https://ziglang.org/), which is MIT licensed. // The MIT license requires this copyright notice to be included in all copies // and substantial portions of the software. -- cgit v1.2.3 From 89286376c627c708e90697cb249a54feb7c827d6 Mon Sep 17 00:00:00 2001 From: Alex Cameron Date: Tue, 29 Dec 2020 16:22:22 +1100 Subject: std: Rename ArrayList shrink => shrinkAndFree --- lib/std/array_hash_map.zig | 2 +- lib/std/array_list.zig | 8 ++++---- lib/std/fs.zig | 2 +- lib/std/io/reader.zig | 6 +++--- lib/std/json.zig | 2 +- lib/std/math/big/int.zig | 2 +- lib/std/net.zig | 4 ++-- src/Compilation.zig | 2 +- src/libc_installation.zig | 6 +++--- src/translate_c.zig | 10 +++++----- 10 files changed, 22 insertions(+), 22 deletions(-) (limited to 'lib/std/array_hash_map.zig') diff --git a/lib/std/array_hash_map.zig b/lib/std/array_hash_map.zig index 7c591bed1b..ddc15666bb 100644 --- a/lib/std/array_hash_map.zig +++ b/lib/std/array_hash_map.zig @@ -323,7 +323,7 @@ pub fn ArrayHashMapUnmanaged( } pub fn clearAndFree(self: *Self, allocator: *Allocator) void { - self.entries.shrink(allocator, 0); + self.entries.shrinkAndFree(allocator, 0); if (self.index_header) |header| { header.free(allocator); self.index_header = null; diff --git a/lib/std/array_list.zig b/lib/std/array_list.zig index 3114d1b744..53580585ad 100644 --- a/lib/std/array_list.zig +++ b/lib/std/array_list.zig @@ -269,7 +269,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { /// Reduce allocated capacity to `new_len`. /// May invalidate element pointers. - pub fn shrink(self: *Self, new_len: usize) void { + pub fn shrinkAndFree(self: *Self, new_len: usize) void { assert(new_len <= self.items.len); self.items = self.allocator.realloc(self.allocatedSlice(), new_len) catch |e| switch (e) { @@ -585,7 +585,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ } /// Reduce allocated capacity to `new_len`. - pub fn shrink(self: *Self, allocator: *Allocator, new_len: usize) void { + pub fn shrinkAndFree(self: *Self, allocator: *Allocator, new_len: usize) void { assert(new_len <= self.items.len); self.items = allocator.realloc(self.allocatedSlice(), new_len) catch |e| switch (e) { @@ -1153,7 +1153,7 @@ test "std.ArrayList/ArrayListUnmanaged.shrink still sets length on error.OutOfMe try list.append(2); try list.append(3); - list.shrink(1); + list.shrinkAndFree(1); testing.expect(list.items.len == 1); } { @@ -1163,7 +1163,7 @@ test "std.ArrayList/ArrayListUnmanaged.shrink still sets length on error.OutOfMe try list.append(a, 2); try list.append(a, 3); - list.shrink(a, 1); + list.shrinkAndFree(a, 1); testing.expect(list.items.len == 1); } } diff --git a/lib/std/fs.zig b/lib/std/fs.zig index 5d11d9f394..89984cda07 100644 --- a/lib/std/fs.zig +++ b/lib/std/fs.zig @@ -2186,7 +2186,7 @@ pub const Walker = struct { var top = &self.stack.items[self.stack.items.len - 1]; const dirname_len = top.dirname_len; if (try top.dir_it.next()) |base| { - self.name_buffer.shrink(dirname_len); + self.name_buffer.shrinkAndFree(dirname_len); try self.name_buffer.append(path.sep); try self.name_buffer.appendSlice(base.name); if (base.kind == .Directory) { diff --git a/lib/std/io/reader.zig b/lib/std/io/reader.zig index 90c1cdac98..705eb9e816 100644 --- a/lib/std/io/reader.zig +++ b/lib/std/io/reader.zig @@ -76,12 +76,12 @@ pub fn Reader( start_index += bytes_read; if (start_index - original_len > max_append_size) { - array_list.shrink(original_len + max_append_size); + array_list.shrinkAndFree(original_len + max_append_size); return error.StreamTooLong; } if (bytes_read != dest_slice.len) { - array_list.shrink(start_index); + array_list.shrinkAndFree(start_index); return; } @@ -111,7 +111,7 @@ pub fn Reader( delimiter: u8, max_size: usize, ) !void { - array_list.shrink(0); + array_list.shrinkAndFree(0); while (true) { var byte: u8 = try self.readByte(); diff --git a/lib/std/json.zig b/lib/std/json.zig index f5be3a2094..87808a7350 100644 --- a/lib/std/json.zig +++ b/lib/std/json.zig @@ -1897,7 +1897,7 @@ pub const Parser = struct { pub fn reset(p: *Parser) void { p.state = .Simple; - p.stack.shrink(0); + p.stack.shrinkAndFree(0); } pub fn parse(p: *Parser, input: []const u8) !ValueTree { diff --git a/lib/std/math/big/int.zig b/lib/std/math/big/int.zig index a151163bdc..504083dcce 100644 --- a/lib/std/math/big/int.zig +++ b/lib/std/math/big/int.zig @@ -607,7 +607,7 @@ pub const Mutable = struct { /// it will have the same length as it had when the function was called. pub fn gcd(rma: *Mutable, x: Const, y: Const, limbs_buffer: *std.ArrayList(Limb)) !void { const prev_len = limbs_buffer.items.len; - defer limbs_buffer.shrink(prev_len); + defer limbs_buffer.shrinkAndFree(prev_len); const x_copy = if (rma.limbs.ptr == x.limbs.ptr) blk: { const start = limbs_buffer.items.len; try limbs_buffer.appendSlice(x.limbs); diff --git a/lib/std/net.zig b/lib/std/net.zig index b8f48b2020..da35bd88b0 100644 --- a/lib/std/net.zig +++ b/lib/std/net.zig @@ -1200,13 +1200,13 @@ fn linuxLookupNameFromDnsSearch( var tok_it = mem.tokenize(search, " \t"); while (tok_it.next()) |tok| { - canon.shrink(canon_name.len + 1); + canon.shrinkAndFree(canon_name.len + 1); try canon.appendSlice(tok); try linuxLookupNameFromDns(addrs, canon, canon.items, family, rc, port); if (addrs.items.len != 0) return; } - canon.shrink(canon_name.len); + canon.shrinkAndFree(canon_name.len); return linuxLookupNameFromDns(addrs, canon, name, family, rc, port); } diff --git a/src/Compilation.zig b/src/Compilation.zig index 9912520437..d42508c995 100644 --- a/src/Compilation.zig +++ b/src/Compilation.zig @@ -735,7 +735,7 @@ pub fn create(gpa: *Allocator, options: InitOptions) !*Compilation { } assert(mem.endsWith(u8, buf.items, ",")); buf.items[buf.items.len - 1] = 0; - buf.shrink(buf.items.len); + buf.shrinkAndFree(buf.items.len); break :blk buf.items[0 .. buf.items.len - 1 :0].ptr; } else null; diff --git a/src/libc_installation.zig b/src/libc_installation.zig index cc96146e0b..bc317869e8 100644 --- a/src/libc_installation.zig +++ b/src/libc_installation.zig @@ -337,7 +337,7 @@ pub const LibCInstallation = struct { defer result_buf.deinit(); for (searches) |search| { - result_buf.shrink(0); + result_buf.shrinkAndFree(0); try result_buf.outStream().print("{s}\\Include\\{s}\\ucrt", .{ search.path, search.version }); var dir = fs.cwd().openDir(result_buf.items, .{}) catch |err| switch (err) { @@ -383,7 +383,7 @@ pub const LibCInstallation = struct { }; for (searches) |search| { - result_buf.shrink(0); + result_buf.shrinkAndFree(0); try result_buf.outStream().print("{s}\\Lib\\{s}\\ucrt\\{s}", .{ search.path, search.version, arch_sub_dir }); var dir = fs.cwd().openDir(result_buf.items, .{}) catch |err| switch (err) { @@ -437,7 +437,7 @@ pub const LibCInstallation = struct { }; for (searches) |search| { - result_buf.shrink(0); + result_buf.shrinkAndFree(0); const stream = result_buf.outStream(); try stream.print("{s}\\Lib\\{s}\\um\\{s}", .{ search.path, search.version, arch_sub_dir }); diff --git a/src/translate_c.zig b/src/translate_c.zig index 7aebcf069b..9369c6d4b8 100644 --- a/src/translate_c.zig +++ b/src/translate_c.zig @@ -2846,7 +2846,7 @@ fn transCase( // take all pending statements try switch_scope.pending_block.statements.appendSlice(block_scope.statements.items); - block_scope.statements.shrink(0); + block_scope.statements.shrinkAndFree(0); const pending_node = try switch_scope.pending_block.complete(rp.c); switch_scope.pending_block.deinit(); @@ -2884,7 +2884,7 @@ fn transDefault( // take all pending statements try switch_scope.pending_block.statements.appendSlice(block_scope.statements.items); - block_scope.statements.shrink(0); + block_scope.statements.shrinkAndFree(0); const pending_node = try switch_scope.pending_block.complete(rp.c); switch_scope.pending_block.deinit(); @@ -4773,9 +4773,9 @@ const RestorePoint = struct { src_buf_index: usize, fn activate(self: RestorePoint) void { - self.c.token_ids.shrink(self.c.gpa, self.token_index); - self.c.token_locs.shrink(self.c.gpa, self.token_index); - self.c.source_buffer.shrink(self.src_buf_index); + self.c.token_ids.shrinkAndFree(self.c.gpa, self.token_index); + self.c.token_locs.shrinkAndFree(self.c.gpa, self.token_index); + self.c.source_buffer.shrinkAndFree(self.src_buf_index); } }; -- cgit v1.2.3 From d92ea56884c4cdc3a0cff8b6ed1e31f959ee0fa8 Mon Sep 17 00:00:00 2001 From: Alex Cameron Date: Sat, 26 Dec 2020 15:30:19 +1100 Subject: std: Support equivalent ArrayList operations in ArrayHashMap --- lib/std/array_hash_map.zig | 365 +++++++++++++++++++++++++++++++++++++++++---- src/Module.zig | 16 +- src/codegen.zig | 2 +- 3 files changed, 341 insertions(+), 42 deletions(-) (limited to 'lib/std/array_hash_map.zig') diff --git a/lib/std/array_hash_map.zig b/lib/std/array_hash_map.zig index ddc15666bb..b6478d4094 100644 --- a/lib/std/array_hash_map.zig +++ b/lib/std/array_hash_map.zig @@ -99,6 +99,16 @@ pub fn ArrayHashMap( }; } + /// `ArrayHashMap` takes ownership of the passed in array list. The array list must have + /// been allocated with `allocator`. + /// Deinitialize with `deinit`. + pub fn fromOwnedArrayList(allocator: *Allocator, entries: std.ArrayListUnmanaged(Entry)) !Self { + return Self{ + .unmanaged = try Unmanaged.fromOwnedArrayList(allocator, entries), + .allocator = allocator, + }; + } + pub fn deinit(self: *Self) void { self.unmanaged.deinit(self.allocator); self.* = undefined; @@ -214,9 +224,19 @@ pub fn ArrayHashMap( } /// If there is an `Entry` with a matching key, it is deleted from - /// the hash map, and then returned from this function. - pub fn remove(self: *Self, key: K) ?Entry { - return self.unmanaged.remove(key); + /// the hash map, and then returned from this function. The entry is + /// removed from the underlying array by swapping it with the last + /// element. + pub fn swapRemove(self: *Self, key: K) ?Entry { + return self.unmanaged.swapRemove(key); + } + + /// If there is an `Entry` with a matching key, it is deleted from + /// the hash map, and then returned from this function. The entry is + /// removed from the underlying array by shifting all elements forward + /// thereby maintaining the current ordering. + pub fn orderedRemove(self: *Self, key: K) ?Entry { + return self.unmanaged.orderedRemove(key); } /// Asserts there is an `Entry` with matching key, deletes it from the hash map, @@ -233,6 +253,29 @@ pub fn ArrayHashMap( var other = try self.unmanaged.clone(self.allocator); return other.promote(self.allocator); } + + /// Rebuilds the key indexes. If the underlying entries has been modified directly, users + /// can call `reIndex` to update the indexes to account for these new entries. + pub fn reIndex(self: *Self) !void { + return self.unmanaged.reIndex(self.allocator); + } + + /// Shrinks the underlying `Entry` array to `new_len` elements and discards any associated + /// index entries. Keeps capacity the same. + pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void { + return self.unmanaged.shrinkRetainingCapacity(new_len); + } + + /// Shrinks the underlying `Entry` array to `new_len` elements and discards any associated + /// index entries. Reduces allocated capacity. + pub fn shrinkAndFree(self: *Self, new_len: usize) void { + return self.unmanaged.shrinkAndFree(self.allocator, new_len); + } + + /// Removes the last inserted `Entry` in the hash map and returns it. + pub fn pop(self: *Self) Entry { + return self.unmanaged.pop(); + } }; } @@ -286,6 +329,7 @@ pub fn ArrayHashMapUnmanaged( pub const GetOrPutResult = struct { entry: *Entry, found_existing: bool, + index: usize, }; pub const Managed = ArrayHashMap(K, V, hash, eql, store_hash); @@ -294,6 +338,12 @@ pub fn ArrayHashMapUnmanaged( const linear_scan_max = 8; + const RemovalType = enum { + swap, + ordered, + index_only, + }; + pub fn promote(self: Self, allocator: *Allocator) Managed { return .{ .unmanaged = self, @@ -301,6 +351,15 @@ pub fn ArrayHashMapUnmanaged( }; } + /// `ArrayHashMapUnmanaged` takes ownership of the passed in array list. The array list must + /// have been allocated with `allocator`. + /// Deinitialize with `deinit`. + pub fn fromOwnedArrayList(allocator: *Allocator, entries: std.ArrayListUnmanaged(Entry)) !Self { + var array_hash_map = Self{ .entries = entries }; + try array_hash_map.reIndex(allocator); + return array_hash_map; + } + pub fn deinit(self: *Self, allocator: *Allocator) void { self.entries.deinit(allocator); if (self.index_header) |header| { @@ -343,9 +402,11 @@ pub fn ArrayHashMapUnmanaged( pub fn getOrPut(self: *Self, allocator: *Allocator, key: K) !GetOrPutResult { self.ensureCapacity(allocator, self.entries.items.len + 1) catch |err| { // "If key exists this function cannot fail." + const index = self.getIndex(key) orelse return err; return GetOrPutResult{ - .entry = self.getEntry(key) orelse return err, + .entry = &self.entries.items[index], .found_existing = true, + .index = index, }; }; return self.getOrPutAssumeCapacity(key); @@ -362,11 +423,12 @@ pub fn ArrayHashMapUnmanaged( const header = self.index_header orelse { // Linear scan. const h = if (store_hash) hash(key) else {}; - for (self.entries.items) |*item| { + for (self.entries.items) |*item, i| { if (item.hash == h and eql(key, item.key)) { return GetOrPutResult{ .entry = item, .found_existing = true, + .index = i, }; } } @@ -379,6 +441,7 @@ pub fn ArrayHashMapUnmanaged( return GetOrPutResult{ .entry = new_entry, .found_existing = false, + .index = self.entries.items.len - 1, }; }; @@ -524,30 +587,25 @@ pub fn ArrayHashMapUnmanaged( } /// If there is an `Entry` with a matching key, it is deleted from - /// the hash map, and then returned from this function. - pub fn remove(self: *Self, key: K) ?Entry { - const header = self.index_header orelse { - // Linear scan. - const h = if (store_hash) hash(key) else {}; - for (self.entries.items) |item, i| { - if (item.hash == h and eql(key, item.key)) { - return self.entries.swapRemove(i); - } - } - return null; - }; - switch (header.capacityIndexType()) { - .u8 => return self.removeInternal(key, header, u8), - .u16 => return self.removeInternal(key, header, u16), - .u32 => return self.removeInternal(key, header, u32), - .usize => return self.removeInternal(key, header, usize), - } + /// the hash map, and then returned from this function. The entry is + /// removed from the underlying array by swapping it with the last + /// element. + pub fn swapRemove(self: *Self, key: K) ?Entry { + return self.removeInternal(key, .swap); + } + + /// If there is an `Entry` with a matching key, it is deleted from + /// the hash map, and then returned from this function. The entry is + /// removed from the underlying array by shifting all elements forward + /// thereby maintaining the current ordering. + pub fn orderedRemove(self: *Self, key: K) ?Entry { + return self.removeInternal(key, .ordered); } /// Asserts there is an `Entry` with matching key, deletes it from the hash map, /// and discards it. pub fn removeAssertDiscard(self: *Self, key: K) void { - assert(self.remove(key) != null); + assert(self.swapRemove(key) != null); } pub fn items(self: Self) []Entry { @@ -566,9 +624,85 @@ pub fn ArrayHashMapUnmanaged( return other; } - fn removeInternal(self: *Self, key: K, header: *IndexHeader, comptime I: type) ?Entry { + /// Rebuilds the key indexes. If the underlying entries has been modified directly, users + /// can call `reIndex` to update the indexes to account for these new entries. + pub fn reIndex(self: *Self, allocator: *Allocator) !void { + if (self.entries.capacity <= linear_scan_max) return; + // We're going to rebuild the index header and replace the existing one (if any). The + // indexes should sized such that they will be at most 60% full. + const needed_len = self.entries.capacity * 5 / 3; + const new_indexes_len = math.ceilPowerOfTwo(usize, needed_len) catch unreachable; + const new_header = try IndexHeader.alloc(allocator, new_indexes_len); + self.insertAllEntriesIntoNewHeader(new_header); + if (self.index_header) |header| + header.free(allocator); + self.index_header = new_header; + } + + /// Shrinks the underlying `Entry` array to `new_len` elements and discards any associated + /// index entries. Keeps capacity the same. + pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void { + // Remove index entries from the new length onwards. + // Explicitly choose to ONLY remove index entries and not the underlying array list + // entries as we're going to remove them in the subsequent shrink call. + var i: usize = new_len; + while (i < self.entries.items.len) : (i += 1) + _ = self.removeWithHash(self.entries.items[i].key, self.entries.items[i].hash, .index_only); + self.entries.shrinkRetainingCapacity(new_len); + } + + /// Shrinks the underlying `Entry` array to `new_len` elements and discards any associated + /// index entries. Reduces allocated capacity. + pub fn shrinkAndFree(self: *Self, allocator: *Allocator, new_len: usize) void { + // Remove index entries from the new length onwards. + // Explicitly choose to ONLY remove index entries and not the underlying array list + // entries as we're going to remove them in the subsequent shrink call. + var i: usize = new_len; + while (i < self.entries.items.len) : (i += 1) + _ = self.removeWithHash(self.entries.items[i].key, self.entries.items[i].hash, .index_only); + self.entries.shrinkAndFree(allocator, new_len); + } + + /// Removes the last inserted `Entry` in the hash map and returns it. + pub fn pop(self: *Self) Entry { + const top = self.entries.pop(); + _ = self.removeWithHash(top.key, top.hash, .index_only); + return top; + } + + fn removeInternal(self: *Self, key: K, comptime removal_type: RemovalType) ?Entry { + const key_hash = if (store_hash) hash(key) else {}; + return self.removeWithHash(key, key_hash, removal_type); + } + + fn removeWithHash(self: *Self, key: K, key_hash: Hash, comptime removal_type: RemovalType) ?Entry { + const header = self.index_header orelse { + // If we're only removing index entries and we have no index header, there's no need + // to continue. + if (removal_type == .index_only) return null; + // Linear scan. + for (self.entries.items) |item, i| { + if (item.hash == key_hash and eql(key, item.key)) { + switch (removal_type) { + .swap => return self.entries.swapRemove(i), + .ordered => return self.entries.orderedRemove(i), + .index_only => unreachable, + } + } + } + return null; + }; + switch (header.capacityIndexType()) { + .u8 => return self.removeWithIndex(key, key_hash, header, u8, removal_type), + .u16 => return self.removeWithIndex(key, key_hash, header, u16, removal_type), + .u32 => return self.removeWithIndex(key, key_hash, header, u32, removal_type), + .usize => return self.removeWithIndex(key, key_hash, header, usize, removal_type), + } + } + + fn removeWithIndex(self: *Self, key: K, key_hash: Hash, header: *IndexHeader, comptime I: type, comptime removal_type: RemovalType) ?Entry { const indexes = header.indexes(I); - const h = hash(key); + const h = if (store_hash) key_hash else hash(key); const start_index = header.constrainIndex(h); var roll_over: usize = 0; while (roll_over <= header.max_distance_from_start_index) : (roll_over += 1) { @@ -583,11 +717,26 @@ pub fn ArrayHashMapUnmanaged( if (!hash_match or !eql(key, entry.key)) continue; - const removed_entry = self.entries.swapRemove(index.entry_index); - if (self.entries.items.len > 0 and self.entries.items.len != index.entry_index) { - // Because of the swap remove, now we need to update the index that was - // pointing to the last entry and is now pointing to this removed item slot. - self.updateEntryIndex(header, self.entries.items.len, index.entry_index, I, indexes); + var removed_entry: ?Entry = undefined; + switch (removal_type) { + .swap => { + removed_entry = self.entries.swapRemove(index.entry_index); + if (self.entries.items.len > 0 and self.entries.items.len != index.entry_index) { + // Because of the swap remove, now we need to update the index that was + // pointing to the last entry and is now pointing to this removed item slot. + self.updateEntryIndex(header, self.entries.items.len, index.entry_index, I, indexes); + } + }, + .ordered => { + removed_entry = self.entries.orderedRemove(index.entry_index); + var i: usize = index.entry_index; + while (i < self.entries.items.len) : (i += 1) { + // Because of the ordered remove, everything from the entry index onwards has + // been shifted forward so we'll need to update the index entries. + self.updateEntryIndex(header, i + 1, i, I, indexes); + } + }, + .index_only => removed_entry = null, } // Now we have to shift over the following indexes. @@ -658,6 +807,7 @@ pub fn ArrayHashMapUnmanaged( return .{ .found_existing = false, .entry = new_entry, + .index = self.entries.items.len - 1, }; } @@ -669,6 +819,7 @@ pub fn ArrayHashMapUnmanaged( return .{ .found_existing = true, .entry = entry, + .index = index.entry_index, }; } if (index.distance_from_start_index < distance_from_start_index) { @@ -710,6 +861,7 @@ pub fn ArrayHashMapUnmanaged( return .{ .found_existing = false, .entry = new_entry, + .index = self.entries.items.len - 1, }; } if (next_index.distance_from_start_index < distance_from_start_index) { @@ -901,11 +1053,13 @@ test "basic hash map usage" { const gop1 = try map.getOrPut(5); testing.expect(gop1.found_existing == true); testing.expect(gop1.entry.value == 55); + testing.expect(gop1.index == 4); gop1.entry.value = 77; testing.expect(map.getEntry(5).?.value == 77); const gop2 = try map.getOrPut(99); testing.expect(gop2.found_existing == false); + testing.expect(gop2.index == 5); gop2.entry.value = 42; testing.expect(map.getEntry(99).?.value == 42); @@ -919,13 +1073,32 @@ test "basic hash map usage" { testing.expect(map.getEntry(2).?.value == 22); testing.expect(map.get(2).? == 22); - const rmv1 = map.remove(2); + const rmv1 = map.swapRemove(2); testing.expect(rmv1.?.key == 2); testing.expect(rmv1.?.value == 22); - testing.expect(map.remove(2) == null); + testing.expect(map.swapRemove(2) == null); testing.expect(map.getEntry(2) == null); testing.expect(map.get(2) == null); + // Since we've used `swapRemove` above, the index of this entry should remain unchanged. + testing.expect(map.getIndex(100).? == 1); + const gop5 = try map.getOrPut(5); + testing.expect(gop5.found_existing == true); + testing.expect(gop5.entry.value == 77); + testing.expect(gop5.index == 4); + + // Whereas, if we do an `orderedRemove`, it should move the index forward one spot. + const rmv2 = map.orderedRemove(100); + testing.expect(rmv2.?.key == 100); + testing.expect(rmv2.?.value == 41); + testing.expect(map.orderedRemove(100) == null); + testing.expect(map.getEntry(100) == null); + testing.expect(map.get(100) == null); + const gop6 = try map.getOrPut(5); + testing.expect(gop6.found_existing == true); + testing.expect(gop6.entry.value == 77); + testing.expect(gop6.index == 3); + map.removeAssertDiscard(3); } @@ -1019,6 +1192,132 @@ test "clone" { } } +test "shrink" { + var map = AutoArrayHashMap(i32, i32).init(std.testing.allocator); + defer map.deinit(); + + // This test is more interesting if we insert enough entries to allocate the index header. + const num_entries = 20; + var i: i32 = 0; + while (i < num_entries) : (i += 1) + testing.expect((try map.fetchPut(i, i * 10)) == null); + + testing.expect(map.unmanaged.index_header != null); + testing.expect(map.count() == num_entries); + + // Test `shrinkRetainingCapacity`. + map.shrinkRetainingCapacity(17); + testing.expect(map.count() == 17); + testing.expect(map.capacity() == 20); + i = 0; + while (i < num_entries) : (i += 1) { + const gop = try map.getOrPut(i); + if (i < 17) { + testing.expect(gop.found_existing == true); + testing.expect(gop.entry.value == i * 10); + } else + testing.expect(gop.found_existing == false); + } + + // Test `shrinkAndFree`. + map.shrinkAndFree(15); + testing.expect(map.count() == 15); + testing.expect(map.capacity() == 15); + i = 0; + while (i < num_entries) : (i += 1) { + const gop = try map.getOrPut(i); + if (i < 15) { + testing.expect(gop.found_existing == true); + testing.expect(gop.entry.value == i * 10); + } else + testing.expect(gop.found_existing == false); + } +} + +test "pop" { + var map = AutoArrayHashMap(i32, i32).init(std.testing.allocator); + defer map.deinit(); + + testing.expect((try map.fetchPut(1, 11)) == null); + testing.expect((try map.fetchPut(2, 22)) == null); + testing.expect((try map.fetchPut(3, 33)) == null); + testing.expect((try map.fetchPut(4, 44)) == null); + + const pop1 = map.pop(); + testing.expect(pop1.key == 4 and pop1.value == 44); + const pop2 = map.pop(); + testing.expect(pop2.key == 3 and pop2.value == 33); + const pop3 = map.pop(); + testing.expect(pop3.key == 2 and pop3.value == 22); + const pop4 = map.pop(); + testing.expect(pop4.key == 1 and pop4.value == 11); +} + +test "reIndex" { + var map = AutoArrayHashMap(i32, i32).init(std.testing.allocator); + defer map.deinit(); + + // Populate via the API. + const num_indexed_entries = 20; + var i: i32 = 0; + while (i < num_indexed_entries) : (i += 1) + testing.expect((try map.fetchPut(i, i * 10)) == null); + + // Make sure we allocated an index header. + testing.expect(map.unmanaged.index_header != null); + + // Now write to the underlying array list directly. + const num_unindexed_entries = 20; + const hash = getAutoHashFn(i32); + var al = &map.unmanaged.entries; + while (i < num_indexed_entries + num_unindexed_entries) : (i += 1) { + try al.append(std.testing.allocator, .{ + .key = i, + .value = i * 10, + .hash = hash(i), + }); + } + + // After reindexing, we should see everything. + try map.reIndex(); + i = 0; + while (i < num_indexed_entries + num_unindexed_entries) : (i += 1) { + const gop = try map.getOrPut(i); + testing.expect(gop.found_existing == true); + testing.expect(gop.entry.value == i * 10); + testing.expect(gop.index == i); + } +} + +test "fromOwnedArrayList" { + comptime const array_hash_map_type = AutoArrayHashMap(i32, i32); + var al = std.ArrayListUnmanaged(array_hash_map_type.Entry){}; + const hash = getAutoHashFn(i32); + + // Populate array list. + const num_entries = 20; + var i: i32 = 0; + while (i < num_entries) : (i += 1) { + try al.append(std.testing.allocator, .{ + .key = i, + .value = i * 10, + .hash = hash(i), + }); + } + + // Now instantiate using `fromOwnedArrayList`. + var map = try array_hash_map_type.fromOwnedArrayList(std.testing.allocator, al); + defer map.deinit(); + + i = 0; + while (i < num_entries) : (i += 1) { + const gop = try map.getOrPut(i); + testing.expect(gop.found_existing == true); + testing.expect(gop.entry.value == i * 10); + testing.expect(gop.index == i); + } +} + pub fn getHashPtrAddrFn(comptime K: type) (fn (K) u32) { return struct { fn hash(key: K) u32 { diff --git a/src/Module.zig b/src/Module.zig index 6a4575394a..59cd4968e5 100644 --- a/src/Module.zig +++ b/src/Module.zig @@ -561,7 +561,7 @@ pub const Scope = struct { } pub fn removeDecl(self: *Container, child: *Decl) void { - _ = self.decls.remove(child); + _ = self.decls.swapRemove(child); } pub fn fullyQualifiedNameHash(self: *Container, name: []const u8) NameHash { @@ -1660,7 +1660,7 @@ pub fn analyzeContainer(self: *Module, container_scope: *Scope.Container) !void // Update the AST Node index of the decl, even if its contents are unchanged, it may // have been re-ordered. decl.src_index = decl_i; - if (deleted_decls.remove(decl) == null) { + if (deleted_decls.swapRemove(decl) == null) { decl.analysis = .sema_failure; const err_msg = try Compilation.ErrorMsg.create(self.gpa, tree.token_locs[name_tok].start, "redefinition of '{s}'", .{decl.name}); errdefer err_msg.destroy(self.gpa); @@ -1702,7 +1702,7 @@ pub fn analyzeContainer(self: *Module, container_scope: *Scope.Container) !void // Update the AST Node index of the decl, even if its contents are unchanged, it may // have been re-ordered. decl.src_index = decl_i; - if (deleted_decls.remove(decl) == null) { + if (deleted_decls.swapRemove(decl) == null) { decl.analysis = .sema_failure; const err_msg = try Compilation.ErrorMsg.create(self.gpa, name_loc.start, "redefinition of '{s}'", .{decl.name}); errdefer err_msg.destroy(self.gpa); @@ -1832,7 +1832,7 @@ pub fn deleteDecl(self: *Module, decl: *Decl) !void { try self.markOutdatedDecl(dep); } } - if (self.failed_decls.remove(decl)) |entry| { + if (self.failed_decls.swapRemove(decl)) |entry| { entry.value.destroy(self.gpa); } self.deleteDeclExports(decl); @@ -1843,7 +1843,7 @@ pub fn deleteDecl(self: *Module, decl: *Decl) !void { /// Delete all the Export objects that are caused by this Decl. Re-analysis of /// this Decl will cause them to be re-created (or not). fn deleteDeclExports(self: *Module, decl: *Decl) void { - const kv = self.export_owners.remove(decl) orelse return; + const kv = self.export_owners.swapRemove(decl) orelse return; for (kv.value) |exp| { if (self.decl_exports.getEntry(exp.exported_decl)) |decl_exports_kv| { @@ -1870,10 +1870,10 @@ fn deleteDeclExports(self: *Module, decl: *Decl) void { if (self.comp.bin_file.cast(link.File.MachO)) |macho| { macho.deleteExport(exp.link.macho); } - if (self.failed_exports.remove(exp)) |entry| { + if (self.failed_exports.swapRemove(exp)) |entry| { entry.value.destroy(self.gpa); } - _ = self.symbol_exports.remove(exp.options.name); + _ = self.symbol_exports.swapRemove(exp.options.name); self.gpa.free(exp.options.name); self.gpa.destroy(exp); } @@ -1918,7 +1918,7 @@ pub fn analyzeFnBody(self: *Module, decl: *Decl, func: *Fn) !void { fn markOutdatedDecl(self: *Module, decl: *Decl) !void { log.debug("mark {s} outdated\n", .{decl.name}); try self.comp.work_queue.writeItem(.{ .analyze_decl = decl }); - if (self.failed_decls.remove(decl)) |entry| { + if (self.failed_decls.swapRemove(decl)) |entry| { entry.value.destroy(self.gpa); } decl.analysis = .outdated; diff --git a/src/codegen.zig b/src/codegen.zig index c2537a1ca0..7f449082f4 100644 --- a/src/codegen.zig +++ b/src/codegen.zig @@ -2123,7 +2123,7 @@ fn Function(comptime arch: std.Target.Cpu.Arch) type { try parent_branch.inst_table.ensureCapacity(self.gpa, parent_branch.inst_table.items().len + else_branch.inst_table.items().len); for (else_branch.inst_table.items()) |else_entry| { - const canon_mcv = if (saved_then_branch.inst_table.remove(else_entry.key)) |then_entry| blk: { + const canon_mcv = if (saved_then_branch.inst_table.swapRemove(else_entry.key)) |then_entry| blk: { // The instruction's MCValue is overridden in both branches. parent_branch.inst_table.putAssumeCapacity(else_entry.key, then_entry.value); if (else_entry.value == .dead) { -- cgit v1.2.3 From 8436134499c623485aeb20374a9928685db4211e Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Sat, 16 Jan 2021 22:49:20 -0700 Subject: std.ArrayHashMap: add "AssertDiscard" function variants * Add `swapRemoveAssertDiscard` * Add `orderedRemoveAssertDiscard` * Deprecate `removeAssertDiscard` --- lib/std/array_hash_map.zig | 30 ++++++++++++++++++++++++++---- 1 file changed, 26 insertions(+), 4 deletions(-) (limited to 'lib/std/array_hash_map.zig') diff --git a/lib/std/array_hash_map.zig b/lib/std/array_hash_map.zig index b6478d4094..5008b3a4af 100644 --- a/lib/std/array_hash_map.zig +++ b/lib/std/array_hash_map.zig @@ -239,12 +239,23 @@ pub fn ArrayHashMap( return self.unmanaged.orderedRemove(key); } - /// Asserts there is an `Entry` with matching key, deletes it from the hash map, - /// and discards it. + /// TODO: deprecated: call swapRemoveAssertDiscard instead. pub fn removeAssertDiscard(self: *Self, key: K) void { return self.unmanaged.removeAssertDiscard(key); } + /// Asserts there is an `Entry` with matching key, deletes it from the hash map + /// by swapping it with the last element, and discards it. + pub fn swapRemoveAssertDiscard(self: *Self, key: K) void { + return self.unmanaged.swapRemoveAssertDiscard(key); + } + + /// Asserts there is an `Entry` with matching key, deletes it from the hash map + /// by by shifting all elements forward thereby maintaining the current ordering. + pub fn orderedRemoveAssertDiscard(self: *Self, key: K) void { + return self.unmanaged.orderedRemoveAssertDiscard(key); + } + pub fn items(self: Self) []Entry { return self.unmanaged.items(); } @@ -602,12 +613,23 @@ pub fn ArrayHashMapUnmanaged( return self.removeInternal(key, .ordered); } - /// Asserts there is an `Entry` with matching key, deletes it from the hash map, - /// and discards it. + /// TODO deprecated: call swapRemoveAssertDiscard instead. pub fn removeAssertDiscard(self: *Self, key: K) void { + return self.swapRemoveAssertDiscard(key); + } + + /// Asserts there is an `Entry` with matching key, deletes it from the hash map + /// by swapping it with the last element, and discards it. + pub fn swapRemoveAssertDiscard(self: *Self, key: K) void { assert(self.swapRemove(key) != null); } + /// Asserts there is an `Entry` with matching key, deletes it from the hash map + /// by by shifting all elements forward thereby maintaining the current ordering. + pub fn orderedRemoveAssertDiscard(self: *Self, key: K) void { + assert(self.orderedRemove(key) != null); + } + pub fn items(self: Self) []Entry { return self.entries.items; } -- cgit v1.2.3 From 5f35dc0c0d0530d5a1d028c56a763def3d1fd250 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Wed, 24 Feb 2021 21:29:01 -0700 Subject: zig fmt the std lib --- lib/std/Thread.zig | 23 ++---- lib/std/Thread/Semaphore.zig | 2 +- lib/std/array_hash_map.zig | 6 +- lib/std/base64.zig | 6 +- lib/std/build.zig | 4 +- lib/std/c/builtins.zig | 136 ++++++++++++++++++++++++++---------- lib/std/c/parse.zig | 3 +- lib/std/coff.zig | 3 +- lib/std/crypto/aegis.zig | 8 +-- lib/std/crypto/bcrypt.zig | 4 +- lib/std/dwarf.zig | 6 +- lib/std/event/batch.zig | 19 ++--- lib/std/fmt.zig | 6 +- lib/std/log.zig | 7 +- lib/std/meta.zig | 21 +++--- lib/std/meta/trait.zig | 8 +-- lib/std/os.zig | 5 +- lib/std/os/bits/netbsd.zig | 16 +++-- lib/std/os/windows/bits.zig | 12 ++-- lib/std/special/compiler_rt/arm.zig | 20 ++---- 20 files changed, 176 insertions(+), 139 deletions(-) (limited to 'lib/std/array_hash_map.zig') diff --git a/lib/std/Thread.zig b/lib/std/Thread.zig index ea878bbdb0..80de19fe19 100644 --- a/lib/std/Thread.zig +++ b/lib/std/Thread.zig @@ -70,16 +70,8 @@ else switch (std.Target.current.os.tag) { /// Signals the processor that it is inside a busy-wait spin-loop ("spin lock"). pub fn spinLoopHint() void { switch (std.Target.current.cpu.arch) { - .i386, .x86_64 => asm volatile ("pause" - : - : - : "memory" - ), - .arm, .aarch64 => asm volatile ("yield" - : - : - : "memory" - ), + .i386, .x86_64 => asm volatile ("pause" ::: "memory"), + .arm, .aarch64 => asm volatile ("yield" ::: "memory"), else => {}, } } @@ -90,12 +82,11 @@ pub fn spinLoopHint() void { pub fn getCurrentId() Id { if (use_pthreads) { return c.pthread_self(); - } else - return switch (std.Target.current.os.tag) { - .linux => os.linux.gettid(), - .windows => windows.kernel32.GetCurrentThreadId(), - else => @compileError("Unsupported OS"), - }; + } else return switch (std.Target.current.os.tag) { + .linux => os.linux.gettid(), + .windows => windows.kernel32.GetCurrentThreadId(), + else => @compileError("Unsupported OS"), + }; } /// Returns the handle of this thread. diff --git a/lib/std/Thread/Semaphore.zig b/lib/std/Thread/Semaphore.zig index a899cd9b6f..169975b362 100644 --- a/lib/std/Thread/Semaphore.zig +++ b/lib/std/Thread/Semaphore.zig @@ -10,7 +10,7 @@ mutex: Mutex = .{}, cond: Condition = .{}, -//! It is OK to initialize this field to any value. +/// It is OK to initialize this field to any value. permits: usize = 0, const Semaphore = @This(); diff --git a/lib/std/array_hash_map.zig b/lib/std/array_hash_map.zig index 5008b3a4af..7b0d9ea4dd 100644 --- a/lib/std/array_hash_map.zig +++ b/lib/std/array_hash_map.zig @@ -1237,8 +1237,7 @@ test "shrink" { if (i < 17) { testing.expect(gop.found_existing == true); testing.expect(gop.entry.value == i * 10); - } else - testing.expect(gop.found_existing == false); + } else testing.expect(gop.found_existing == false); } // Test `shrinkAndFree`. @@ -1251,8 +1250,7 @@ test "shrink" { if (i < 15) { testing.expect(gop.found_existing == true); testing.expect(gop.entry.value == i * 10); - } else - testing.expect(gop.found_existing == false); + } else testing.expect(gop.found_existing == false); } } diff --git a/lib/std/base64.zig b/lib/std/base64.zig index 12066d1175..e6a780c239 100644 --- a/lib/std/base64.zig +++ b/lib/std/base64.zig @@ -222,12 +222,10 @@ pub const Base64DecoderWithIgnore = struct { } else if (decoder_with_ignore.char_is_ignored[c]) { // we can even ignore chars during the padding continue; - } else - return error.InvalidCharacter; + } else return error.InvalidCharacter; } break; - } else - return error.InvalidCharacter; + } else return error.InvalidCharacter; } switch (available_chars) { diff --git a/lib/std/build.zig b/lib/std/build.zig index f52b863d3f..6cd50e7dd8 100644 --- a/lib/std/build.zig +++ b/lib/std/build.zig @@ -2763,7 +2763,9 @@ pub const InstallDirectoryOptions = struct { .install_dir = self.install_dir.dupe(b), .install_subdir = b.dupe(self.install_subdir), .exclude_extensions = if (self.exclude_extensions) |extensions| - b.dupeStrings(extensions) else null, + b.dupeStrings(extensions) + else + null, }; } }; diff --git a/lib/std/c/builtins.zig b/lib/std/c/builtins.zig index 2b386c82f4..c11bf0a391 100644 --- a/lib/std/c/builtins.zig +++ b/lib/std/c/builtins.zig @@ -6,12 +6,22 @@ const std = @import("std"); -pub fn __builtin_bswap16(val: u16) callconv(.Inline) u16 { return @byteSwap(u16, val); } -pub fn __builtin_bswap32(val: u32) callconv(.Inline) u32 { return @byteSwap(u32, val); } -pub fn __builtin_bswap64(val: u64) callconv(.Inline) u64 { return @byteSwap(u64, val); } +pub fn __builtin_bswap16(val: u16) callconv(.Inline) u16 { + return @byteSwap(u16, val); +} +pub fn __builtin_bswap32(val: u32) callconv(.Inline) u32 { + return @byteSwap(u32, val); +} +pub fn __builtin_bswap64(val: u64) callconv(.Inline) u64 { + return @byteSwap(u64, val); +} -pub fn __builtin_signbit(val: f64) callconv(.Inline) c_int { return @boolToInt(std.math.signbit(val)); } -pub fn __builtin_signbitf(val: f32) callconv(.Inline) c_int { return @boolToInt(std.math.signbit(val)); } +pub fn __builtin_signbit(val: f64) callconv(.Inline) c_int { + return @boolToInt(std.math.signbit(val)); +} +pub fn __builtin_signbitf(val: f32) callconv(.Inline) c_int { + return @boolToInt(std.math.signbit(val)); +} pub fn __builtin_popcount(val: c_uint) callconv(.Inline) c_int { // popcount of a c_uint will never exceed the capacity of a c_int @@ -31,40 +41,96 @@ pub fn __builtin_clz(val: c_uint) callconv(.Inline) c_int { return @bitCast(c_int, @as(c_uint, @clz(c_uint, val))); } -pub fn __builtin_sqrt(val: f64) callconv(.Inline) f64 { return @sqrt(val); } -pub fn __builtin_sqrtf(val: f32) callconv(.Inline) f32 { return @sqrt(val); } +pub fn __builtin_sqrt(val: f64) callconv(.Inline) f64 { + return @sqrt(val); +} +pub fn __builtin_sqrtf(val: f32) callconv(.Inline) f32 { + return @sqrt(val); +} -pub fn __builtin_sin(val: f64) callconv(.Inline) f64 { return @sin(val); } -pub fn __builtin_sinf(val: f32) callconv(.Inline) f32 { return @sin(val); } -pub fn __builtin_cos(val: f64) callconv(.Inline) f64 { return @cos(val); } -pub fn __builtin_cosf(val: f32) callconv(.Inline) f32 { return @cos(val); } +pub fn __builtin_sin(val: f64) callconv(.Inline) f64 { + return @sin(val); +} +pub fn __builtin_sinf(val: f32) callconv(.Inline) f32 { + return @sin(val); +} +pub fn __builtin_cos(val: f64) callconv(.Inline) f64 { + return @cos(val); +} +pub fn __builtin_cosf(val: f32) callconv(.Inline) f32 { + return @cos(val); +} -pub fn __builtin_exp(val: f64) callconv(.Inline) f64 { return @exp(val); } -pub fn __builtin_expf(val: f32) callconv(.Inline) f32 { return @exp(val); } -pub fn __builtin_exp2(val: f64) callconv(.Inline) f64 { return @exp2(val); } -pub fn __builtin_exp2f(val: f32) callconv(.Inline) f32 { return @exp2(val); } -pub fn __builtin_log(val: f64) callconv(.Inline) f64 { return @log(val); } -pub fn __builtin_logf(val: f32) callconv(.Inline) f32 { return @log(val); } -pub fn __builtin_log2(val: f64) callconv(.Inline) f64 { return @log2(val); } -pub fn __builtin_log2f(val: f32) callconv(.Inline) f32 { return @log2(val); } -pub fn __builtin_log10(val: f64) callconv(.Inline) f64 { return @log10(val); } -pub fn __builtin_log10f(val: f32) callconv(.Inline) f32 { return @log10(val); } +pub fn __builtin_exp(val: f64) callconv(.Inline) f64 { + return @exp(val); +} +pub fn __builtin_expf(val: f32) callconv(.Inline) f32 { + return @exp(val); +} +pub fn __builtin_exp2(val: f64) callconv(.Inline) f64 { + return @exp2(val); +} +pub fn __builtin_exp2f(val: f32) callconv(.Inline) f32 { + return @exp2(val); +} +pub fn __builtin_log(val: f64) callconv(.Inline) f64 { + return @log(val); +} +pub fn __builtin_logf(val: f32) callconv(.Inline) f32 { + return @log(val); +} +pub fn __builtin_log2(val: f64) callconv(.Inline) f64 { + return @log2(val); +} +pub fn __builtin_log2f(val: f32) callconv(.Inline) f32 { + return @log2(val); +} +pub fn __builtin_log10(val: f64) callconv(.Inline) f64 { + return @log10(val); +} +pub fn __builtin_log10f(val: f32) callconv(.Inline) f32 { + return @log10(val); +} // Standard C Library bug: The absolute value of the most negative integer remains negative. -pub fn __builtin_abs(val: c_int) callconv(.Inline) c_int { return std.math.absInt(val) catch std.math.minInt(c_int); } -pub fn __builtin_fabs(val: f64) callconv(.Inline) f64 { return @fabs(val); } -pub fn __builtin_fabsf(val: f32) callconv(.Inline) f32 { return @fabs(val); } - -pub fn __builtin_floor(val: f64) callconv(.Inline) f64 { return @floor(val); } -pub fn __builtin_floorf(val: f32) callconv(.Inline) f32 { return @floor(val); } -pub fn __builtin_ceil(val: f64) callconv(.Inline) f64 { return @ceil(val); } -pub fn __builtin_ceilf(val: f32) callconv(.Inline) f32 { return @ceil(val); } -pub fn __builtin_trunc(val: f64) callconv(.Inline) f64 { return @trunc(val); } -pub fn __builtin_truncf(val: f32) callconv(.Inline) f32 { return @trunc(val); } -pub fn __builtin_round(val: f64) callconv(.Inline) f64 { return @round(val); } -pub fn __builtin_roundf(val: f32) callconv(.Inline) f32 { return @round(val); } - -pub fn __builtin_strlen(s: [*c]const u8) callconv(.Inline) usize { return std.mem.lenZ(s); } +pub fn __builtin_abs(val: c_int) callconv(.Inline) c_int { + return std.math.absInt(val) catch std.math.minInt(c_int); +} +pub fn __builtin_fabs(val: f64) callconv(.Inline) f64 { + return @fabs(val); +} +pub fn __builtin_fabsf(val: f32) callconv(.Inline) f32 { + return @fabs(val); +} + +pub fn __builtin_floor(val: f64) callconv(.Inline) f64 { + return @floor(val); +} +pub fn __builtin_floorf(val: f32) callconv(.Inline) f32 { + return @floor(val); +} +pub fn __builtin_ceil(val: f64) callconv(.Inline) f64 { + return @ceil(val); +} +pub fn __builtin_ceilf(val: f32) callconv(.Inline) f32 { + return @ceil(val); +} +pub fn __builtin_trunc(val: f64) callconv(.Inline) f64 { + return @trunc(val); +} +pub fn __builtin_truncf(val: f32) callconv(.Inline) f32 { + return @trunc(val); +} +pub fn __builtin_round(val: f64) callconv(.Inline) f64 { + return @round(val); +} +pub fn __builtin_roundf(val: f32) callconv(.Inline) f32 { + return @round(val); +} + +pub fn __builtin_strlen(s: [*c]const u8) callconv(.Inline) usize { + return std.mem.lenZ(s); +} pub fn __builtin_strcmp(s1: [*c]const u8, s2: [*c]const u8) callconv(.Inline) c_int { return @as(c_int, std.cstr.cmp(s1, s2)); } diff --git a/lib/std/c/parse.zig b/lib/std/c/parse.zig index 3d17938d7a..29d4ba2fe1 100644 --- a/lib/std/c/parse.zig +++ b/lib/std/c/parse.zig @@ -300,8 +300,7 @@ const Parser = struct { try node.initializers.push((try parser.initializer(dr)) orelse return parser.err(.{ .ExpectedInitializer = .{ .token = parser.it.index }, })); - } else - try node.initializers.push(&dr.base); + } else try node.initializers.push(&dr.base); if (parser.eatToken(.Comma) != null) break; dr = @fieldParentPtr(Node.Declarator, "base", (try parser.declarator(.Must)) orelse return parser.err(.{ .ExpectedDeclarator = .{ .token = parser.it.index }, diff --git a/lib/std/coff.zig b/lib/std/coff.zig index 85000bf8cb..edeff89cc5 100644 --- a/lib/std/coff.zig +++ b/lib/std/coff.zig @@ -173,8 +173,7 @@ pub const Coff = struct { skip_size = 2 * @sizeOf(u8) + 8 * @sizeOf(u16) + 18 * @sizeOf(u32); } else if (self.pe_header.magic == IMAGE_NT_OPTIONAL_HDR64_MAGIC) { skip_size = 2 * @sizeOf(u8) + 8 * @sizeOf(u16) + 12 * @sizeOf(u32) + 5 * @sizeOf(u64); - } else - return error.InvalidPEMagic; + } else return error.InvalidPEMagic; try self.in_file.seekBy(skip_size); diff --git a/lib/std/crypto/aegis.zig b/lib/std/crypto/aegis.zig index 089dc06be4..2983f68ce8 100644 --- a/lib/std/crypto/aegis.zig +++ b/lib/std/crypto/aegis.zig @@ -81,8 +81,8 @@ const State128L = struct { while (i < 7) : (i += 1) { state.update(tmp, tmp); } - return blocks[0].xorBlocks(blocks[1]).xorBlocks(blocks[2]).xorBlocks(blocks[3]).xorBlocks(blocks[4]). - xorBlocks(blocks[5]).xorBlocks(blocks[6]).toBytes(); + return blocks[0].xorBlocks(blocks[1]).xorBlocks(blocks[2]).xorBlocks(blocks[3]).xorBlocks(blocks[4]) + .xorBlocks(blocks[5]).xorBlocks(blocks[6]).toBytes(); } }; @@ -244,8 +244,8 @@ const State256 = struct { while (i < 7) : (i += 1) { state.update(tmp); } - return blocks[0].xorBlocks(blocks[1]).xorBlocks(blocks[2]).xorBlocks(blocks[3]).xorBlocks(blocks[4]). - xorBlocks(blocks[5]).toBytes(); + return blocks[0].xorBlocks(blocks[1]).xorBlocks(blocks[2]).xorBlocks(blocks[3]).xorBlocks(blocks[4]) + .xorBlocks(blocks[5]).toBytes(); } }; diff --git a/lib/std/crypto/bcrypt.zig b/lib/std/crypto/bcrypt.zig index 6d333c45cb..caceb6d7b9 100644 --- a/lib/std/crypto/bcrypt.zig +++ b/lib/std/crypto/bcrypt.zig @@ -109,9 +109,7 @@ const State = struct { } } - const Halves = struct { - l: u32, r: u32 - }; + const Halves = struct { l: u32, r: u32 }; fn feistelF(state: State, x: u32) u32 { var r = state.sboxes[0][@truncate(u8, x >> 24)]; diff --git a/lib/std/dwarf.zig b/lib/std/dwarf.zig index 6769a139da..7df3a1bff6 100644 --- a/lib/std/dwarf.zig +++ b/lib/std/dwarf.zig @@ -213,13 +213,11 @@ const LineNumberProgram = struct { return error.MissingDebugInfo; } else if (self.prev_file - 1 >= self.file_entries.items.len) { return error.InvalidDebugInfo; - } else - &self.file_entries.items[self.prev_file - 1]; + } else &self.file_entries.items[self.prev_file - 1]; const dir_name = if (file_entry.dir_index >= self.include_dirs.len) { return error.InvalidDebugInfo; - } else - self.include_dirs[file_entry.dir_index]; + } else self.include_dirs[file_entry.dir_index]; const file_name = try fs.path.join(self.file_entries.allocator, &[_][]const u8{ dir_name, file_entry.file_name }); errdefer self.file_entries.allocator.free(file_name); return debug.LineInfo{ diff --git a/lib/std/event/batch.zig b/lib/std/event/batch.zig index 72e0bd13fc..5368c5336d 100644 --- a/lib/std/event/batch.zig +++ b/lib/std/event/batch.zig @@ -98,15 +98,16 @@ pub fn Batch( /// This function is *not* thread-safe. It must be called from one thread at /// a time, however, it need not be the same thread. pub fn wait(self: *Self) CollectedResult { - for (self.jobs) |*job| if (job.frame) |f| { - job.result = if (async_ok) await f else nosuspend await f; - if (CollectedResult != void) { - job.result catch |err| { - self.collected_result = err; - }; - } - job.frame = null; - }; + for (self.jobs) |*job| + if (job.frame) |f| { + job.result = if (async_ok) await f else nosuspend await f; + if (CollectedResult != void) { + job.result catch |err| { + self.collected_result = err; + }; + } + job.frame = null; + }; return self.collected_result; } }; diff --git a/lib/std/fmt.zig b/lib/std/fmt.zig index e5ce457091..fca21000cf 100644 --- a/lib/std/fmt.zig +++ b/lib/std/fmt.zig @@ -646,8 +646,7 @@ pub fn formatIntValue( const int_value = if (@TypeOf(value) == comptime_int) blk: { const Int = math.IntFittingRange(value, value); break :blk @as(Int, value); - } else - value; + } else value; if (fmt.len == 0 or comptime std.mem.eql(u8, fmt, "d")) { radix = 10; @@ -1087,8 +1086,7 @@ pub fn formatInt( const int_value = if (@TypeOf(value) == comptime_int) blk: { const Int = math.IntFittingRange(value, value); break :blk @as(Int, value); - } else - value; + } else value; const value_info = @typeInfo(@TypeOf(int_value)).Int; diff --git a/lib/std/log.zig b/lib/std/log.zig index 43c00a6d0e..215e611bc1 100644 --- a/lib/std/log.zig +++ b/lib/std/log.zig @@ -3,9 +3,6 @@ // This file is part of [zig](https://ziglang.org/), which is MIT licensed. // The MIT license requires this copyright notice to be included in all copies // and substantial portions of the software. -const std = @import("std.zig"); -const builtin = std.builtin; -const root = @import("root"); //! std.log is a standardized interface for logging which allows for the logging //! of programs and libraries using this interface to be formatted and filtered @@ -77,6 +74,10 @@ const root = @import("root"); //! [err] (nice_library): Something went very wrong, sorry //! ``` +const std = @import("std.zig"); +const builtin = std.builtin; +const root = @import("root"); + pub const Level = enum { /// Emergency: a condition that cannot be handled, usually followed by a /// panic. diff --git a/lib/std/meta.zig b/lib/std/meta.zig index 30f69ae9a5..7ec29dcd0e 100644 --- a/lib/std/meta.zig +++ b/lib/std/meta.zig @@ -534,9 +534,7 @@ pub fn fieldNames(comptime T: type) *const [fields(T).len][]const u8 { } test "std.meta.fieldNames" { - const E1 = enum { - A, B - }; + const E1 = enum { A, B }; const E2 = error{A}; const S1 = struct { a: u8, @@ -1002,19 +1000,19 @@ pub fn sizeof(target: anytype) usize { // Note: sizeof(void) is 1 on clang/gcc and 0 on MSVC. return 1; } else { - @compileError("Cannot use C sizeof on opaque type "++@typeName(T)); + @compileError("Cannot use C sizeof on opaque type " ++ @typeName(T)); } }, .Optional => |opt| { if (@typeInfo(opt.child) == .Pointer) { return sizeof(opt.child); } else { - @compileError("Cannot use C sizeof on non-pointer optional "++@typeName(T)); + @compileError("Cannot use C sizeof on non-pointer optional " ++ @typeName(T)); } }, .Pointer => |ptr| { if (ptr.size == .Slice) { - @compileError("Cannot use C sizeof on slice type "++@typeName(T)); + @compileError("Cannot use C sizeof on slice type " ++ @typeName(T)); } // for strings, sizeof("a") returns 2. // normal pointer decay scenarios from C are handled @@ -1024,8 +1022,9 @@ pub fn sizeof(target: anytype) usize { if (ptr.size == .One and ptr.is_const and @typeInfo(ptr.child) == .Array) { const array_info = @typeInfo(ptr.child).Array; if ((array_info.child == u8 or array_info.child == u16) and - array_info.sentinel != null and - array_info.sentinel.? == 0) { + array_info.sentinel != null and + array_info.sentinel.? == 0) + { // length of the string plus one for the null terminator. return (array_info.len + 1) * @sizeOf(array_info.child); } @@ -1067,10 +1066,10 @@ test "sizeof" { testing.expect(sizeof(S) == 4); - testing.expect(sizeof([_]u32{4, 5, 6}) == 12); + testing.expect(sizeof([_]u32{ 4, 5, 6 }) == 12); testing.expect(sizeof([3]u32) == 12); testing.expect(sizeof([3:0]u32) == 16); - testing.expect(sizeof(&[_]u32{4, 5, 6}) == ptr_size); + testing.expect(sizeof(&[_]u32{ 4, 5, 6 }) == ptr_size); testing.expect(sizeof(*u32) == ptr_size); testing.expect(sizeof([*]u32) == ptr_size); @@ -1082,7 +1081,7 @@ test "sizeof" { testing.expect(sizeof(null) == ptr_size); testing.expect(sizeof("foobar") == 7); - testing.expect(sizeof(&[_:0]u16{'f','o','o','b','a','r'}) == 14); + testing.expect(sizeof(&[_:0]u16{ 'f', 'o', 'o', 'b', 'a', 'r' }) == 14); testing.expect(sizeof(*const [4:0]u8) == 5); testing.expect(sizeof(*[4:0]u8) == ptr_size); testing.expect(sizeof([*]const [4:0]u8) == ptr_size); diff --git a/lib/std/meta/trait.zig b/lib/std/meta/trait.zig index 8e54293533..e67f9b9bc4 100644 --- a/lib/std/meta/trait.zig +++ b/lib/std/meta/trait.zig @@ -544,15 +544,11 @@ test "std.meta.trait.hasUniqueRepresentation" { testing.expect(hasUniqueRepresentation(TestStruct3)); - const TestStruct4 = struct { - a: []const u8 - }; + const TestStruct4 = struct { a: []const u8 }; testing.expect(!hasUniqueRepresentation(TestStruct4)); - const TestStruct5 = struct { - a: TestStruct4 - }; + const TestStruct5 = struct { a: TestStruct4 }; testing.expect(!hasUniqueRepresentation(TestStruct5)); diff --git a/lib/std/os.zig b/lib/std/os.zig index c2431ff12c..61d9749415 100644 --- a/lib/std/os.zig +++ b/lib/std/os.zig @@ -3263,8 +3263,9 @@ pub fn connect(sock: socket_t, sock_addr: *const sockaddr, len: socklen_t) Conne .WSAEADDRNOTAVAIL => return error.AddressNotAvailable, .WSAECONNREFUSED => return error.ConnectionRefused, .WSAETIMEDOUT => return error.ConnectionTimedOut, - .WSAEHOSTUNREACH // TODO: should we return NetworkUnreachable in this case as well? - , .WSAENETUNREACH => return error.NetworkUnreachable, + .WSAEHOSTUNREACH, // TODO: should we return NetworkUnreachable in this case as well? + .WSAENETUNREACH, + => return error.NetworkUnreachable, .WSAEFAULT => unreachable, .WSAEINVAL => unreachable, .WSAEISCONN => unreachable, diff --git a/lib/std/os/bits/netbsd.zig b/lib/std/os/bits/netbsd.zig index f8b950ea86..57ae70ddbf 100644 --- a/lib/std/os/bits/netbsd.zig +++ b/lib/std/os/bits/netbsd.zig @@ -836,13 +836,15 @@ pub const ucontext_t = extern struct { sigmask: sigset_t, stack: stack_t, mcontext: mcontext_t, - __pad: [switch (builtin.arch) { - .i386 => 4, - .mips, .mipsel, .mips64, .mips64el => 14, - .arm, .armeb, .thumb, .thumbeb => 1, - .sparc, .sparcel, .sparcv9 => if (@sizeOf(usize) == 4) 43 else 8, - else => 0, - }]u32, + __pad: [ + switch (builtin.arch) { + .i386 => 4, + .mips, .mipsel, .mips64, .mips64el => 14, + .arm, .armeb, .thumb, .thumbeb => 1, + .sparc, .sparcel, .sparcv9 => if (@sizeOf(usize) == 4) 43 else 8, + else => 0, + } + ]u32, }; pub const EPERM = 1; // Operation not permitted diff --git a/lib/std/os/windows/bits.zig b/lib/std/os/windows/bits.zig index 8461378da0..cbeb0b483d 100644 --- a/lib/std/os/windows/bits.zig +++ b/lib/std/os/windows/bits.zig @@ -1315,11 +1315,13 @@ pub const PEB = extern struct { ImageSubSystemMinorVersion: ULONG, // note: there is padding here on 64 bit ActiveProcessAffinityMask: KAFFINITY, - GdiHandleBuffer: [switch (@sizeOf(usize)) { - 4 => 0x22, - 8 => 0x3C, - else => unreachable, - }]ULONG, + GdiHandleBuffer: [ + switch (@sizeOf(usize)) { + 4 => 0x22, + 8 => 0x3C, + else => unreachable, + } + ]ULONG, // Fields appended in 5.0 (Windows 2000): PostProcessInitRoutine: PVOID, diff --git a/lib/std/special/compiler_rt/arm.zig b/lib/std/special/compiler_rt/arm.zig index b958748c4f..f100f8293c 100644 --- a/lib/std/special/compiler_rt/arm.zig +++ b/lib/std/special/compiler_rt/arm.zig @@ -66,10 +66,7 @@ pub fn __aeabi_uidivmod() callconv(.Naked) void { \\ ldr r1, [sp] \\ add sp, #4 \\ pop {pc} - : - : - : "memory" - ); + ::: "memory"); unreachable; } @@ -86,10 +83,7 @@ pub fn __aeabi_uldivmod() callconv(.Naked) void { \\ ldr r3, [sp, #12] \\ add sp, #16 \\ pop {r4, pc} - : - : - : "memory" - ); + ::: "memory"); unreachable; } @@ -104,10 +98,7 @@ pub fn __aeabi_idivmod() callconv(.Naked) void { \\ ldr r1, [sp] \\ add sp, #4 \\ pop {pc} - : - : - : "memory" - ); + ::: "memory"); unreachable; } @@ -124,9 +115,6 @@ pub fn __aeabi_ldivmod() callconv(.Naked) void { \\ ldr r3, [sp, #12] \\ add sp, #16 \\ pop {r4, pc} - : - : - : "memory" - ); + ::: "memory"); unreachable; } -- cgit v1.2.3