Simple Dynamic Array in Zig
Today I explored dynamic arrays in Zig so I could learn more about memory and slices and just wrap my head around the concepts of allocation and deallocation.
What is a dynamic array?
A dynamic array is a data structure that holds a list of elements of a certain type. The key feature of a dynamic array is that you do not have to think about the underlying space when you're using it.
The array automatically grows when it's element list size will be exceeded, ensuring that there is alway enough capacity to keep adding elements (until of course your system runs out of memory).
Some algorithms also handle shrinking the array memory when enough elements are removed in order to free up some memory. Ours won't do that today, but could be a great exercise for you to try.
Implementing a dynamic array in Zig
We'll start with a generic data type. In zig these are usually done through functions:
dynamic_array.zig
const std = @import("std");
pub fn DynamicArray(comptime T: type) type {
// Implementation
}
This function will return a type that represents a dynamic array of type T. We'll need to define the struct that will hold the data and the metadata about the array:
dynamic_array.zig
const std = @import("std");
pub fn DynamicArray(comptime T: type) type {
return struct {
allocator: std.mem.Allocator,
items: []T,
capacity: usize,
len: usize,
};
}
This anonymous struct is the core 'storage' area of the data of our dynamic array. We allow the implementor to pass an allocator of their choice to do the allocations and deallocations.
The items slice
In order to make more sense of what is happening in a minute, we have to take a quick recap on Zig slices.
I like to think of a slice as an area of memory. Imagine a list of boxes, each containing a value. The slice in Zig is a pointer (a thing telling us where this area of memory is) to the first element in the list and a length (a number telling us how many boxes are in the list).
With these 2 properties, we can easily determine stuff like whether we're at the end of the slice of memory and if we need to allocate more memory, it also helps ensure that we don't try to access invalid memory when reading the elements.
If your are coming from a language like TypeScript and see the Zig slice syntax:
const items: []u32 = undefined;
You may try to think of it as an array of u32 values, but it's not. In fact, an array of values is what we're trying to build on top of the slice.
For example, the only 2 fields on a slice is ptr and len. There is no way to add items to a slice without allocating memory for it first and/or initializing it with a fixed length before adding items [512]u32 for example.
Initializing the dynamic array
We use the common way in Zig - add a init function to the struct:
dynamic_array.zig
const std = @import("std");
pub fn DynamicArray(comptime T: type) type {
return struct {
allocator: std.mem.Allocator,
items: []T,
capacity: usize,
len: usize,
pub fn init(allocator: std.mem.Allocator) Self {
return .{
.allocator = allocator,
.items = &[_]T{},
.capacity = 0,
.len = 0,
};
}
};
}
Empty Slice Initialization
The syntax &[_]T{} looks strange, but here's a rundown of what it means:
The & operator is used to get the address of the value we'll be initializing.
The [_] is a way in Zig to say "determine the length of this slice automatically". And only possible if the compiler can determine the length.
The T{} part is the actual initialization of an empty slice of type T elements.
Appending Items to the Dynamic Array
We'll add a function to append items to the dynamic array, let's do it step by step:
First we need to think of a few cases:
- When we have not added anything to the array yet and need to initialize memory.
- When the array is full and we need to allocate more memory.
dynamic_array.zig
const std = @import("std");
pub fn DynamicArray(comptime T: type) type {
return struct {
allocator: std.mem.Allocator,
items: []T,
capacity: usize,
len: usize,
const Self = @This();
pub fn init(allocator: std.mem.Allocator) Self {
return .{
.allocator = allocator,
.items = &[_]T{},
.capacity = 0,
.len = 0,
};
}
pub fn append(self: *Self, item: T) !void {
// No items have been added to the array yet
if (self.capacity == 0) {
self.capacity = 256;
self.items = try self.allocator.alloc(T, self.capacity);
self.len = 0
}
// TODO
}
};
}
Firstly, the Self type is just a way to refer to the Struct itself. When it's passed as a first parameter to the struct's functions it becomes a member function.
When we have not added anything to the array yet, we'll use an arbitrary number (256) as the initial capacity. Capacity here means "how much memory have we allocated for the array".
We then allocate memory for the array using the allocator and set the length to 0. The allocator automatically takes into consideration the size of T and manages the offsets for us.
Now we have to check the case when the array is full and we need to allocate more memory:
dynamic_array.zig
const std = @import("std");
pub fn DynamicArray(comptime T: type) type {
return struct {
allocator: std.mem.Allocator,
items: []T,
capacity: usize,
len: usize,
const Self = @This();
pub fn init(allocator: std.mem.Allocator) Self {
return .{
.allocator = allocator,
.items = &[_]T{},
.capacity = 0,
.len = 0,
};
}
pub fn append(self: *Self, item: T) !void {
// No items have been added to the array yet
if (self.capacity == 0) {
self.capacity = 256;
self.items = try self.allocator.alloc(T, self.capacity);
self.len = 0
} else if (self.len >= self.capacity) {
self.capacity *= 2;
self.items = try self.allocator.realloc(self.items, self.capacity);
}
// TODO
}
};
}
We can check if the array has enough space left to add an item by checking that it's capacity is greater than or equal to the length of the array. If it's not, we double the capacity and reallocate memory for the array.
In our check we're using >= which is kind of redundant, because len should never be bigger than capacity, but it adds some mental safety for me.
realloc handles a lot under the hood. Like allocating automatically if the memory has no length and also freeing the memory if we give it a new length of 0.
Adding the item to the array
dynamic_array.zig
const std = @import("std");
pub fn DynamicArray(comptime T: type) type {
return struct {
allocator: std.mem.Allocator,
items: []T,
capacity: usize,
len: usize,
const Self = @This();
pub fn init(allocator: std.mem.Allocator) Self {
return .{
.allocator = allocator,
.items = &[_]T{},
.capacity = 0,
.len = 0,
};
}
pub fn append(self: *Self, item: T) !void {
// No items have been added to the array yet
if (self.capacity == 0) {
self.capacity = 256;
self.items = try self.allocator.alloc(T, self.capacity);
self.len = 0
} else if (self.len >= self.capacity) {
self.capacity *= 2;
self.items = try self.allocator.realloc(self.items, self.capacity);
}
self.items[self.len] = item;
self.len += 1;
}
};
}
Finally, now that we know we have enough memory at the end of the slice to add another item, we can add the item and increment the length of the array.
Notice the index is [self.len] that means just after the index of the last element in the array. We then also have to ensure that we increment our own len.
Using the dynamic array
Let's test our dynamic array implementation:
main.zig
const std = @import("std");
const mem = std.mem;
const DynamicArray = @import("dynamic_array.zig").DynamicArray;
pub fn main() !void {
var gpa = mem.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
var array = DynamicArray(u32).init(allocator);
try array.append(1);
try array.append(2);
try array.append(3);
for (array.items) |item| {
std.debug.print("{d}\n", .{item});
}
// Prints:
// 1
// 2
// 3
}
Here we can see the power of using a generic function for our dynamic array. We can just as easily make this an array of strings or structs.
Fixing the memory leak
A keen eye may have noticed that we never clean up the memory we allocated. If we just temporarily wanted to use the array in our program we would never free that memory after being done with the array:
Let's add a deinit function to our struct:
dynamic_array.zig
const std = @import("std");
pub fn DynamicArray(comptime T: type) type {
return struct {
allocator: std.mem.Allocator,
items: []T,
capacity: usize,
len: usize,
const Self = @This();
pub fn init(allocator: std.mem.Allocator) Self {
return .{
.allocator = allocator,
.items = &[_]T{},
.capacity = 0,
.len = 0,
};
}
pub fn deinit(self: *Self) void {
if (self.capacity > 0) {
self.allocator.free(self.items);
}
self.items = &[_]T{};
self.capacity = 0;
self.len = 0;
}
pub fn append(self: *Self, item: T) !void {
// No items have been added to the array yet
if (self.capacity == 0) {
self.capacity = 256;
self.items = try self.allocator.alloc(T, self.capacity);
self.len = 0
} else if (self.len >= self.capacity) {
self.capacity *= 2;
self.items = try self.allocator.realloc(self.items, self.capacity);
}
self.items[self.len] = item;
self.len += 1;
}
};
}
We only free memory if there is any allocated memory. We then reset the fields to their initial values.
Now we can defer the deinit function to clean up the memory after we're done with the array:
main.zig
const std = @import("std");
const mem = std.mem;
const DynamicArray = @import("dynamic_array.zig").DynamicArray;
pub fn main() !void {
var gpa = mem.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
var array = DynamicArray(u32).init(allocator);
defer array.deinit();
try array.append(1);
try array.append(2);
try array.append(3);
for (array.items) |item| {
std.debug.print("{d}\n", .{item});
}
// Prints:
// 1
// 2
// 3
}
Conclusion
This little exercise taught me quite a bit about Arrays, Zig, Memory and Slices. As a further exercise, try and implement the pop() method which removes and returns the last element in the Array.
Interested in working with me? Reach out here