master
1const std = @import("std.zig");
2const debug = std.debug;
3const assert = debug.assert;
4const testing = std.testing;
5const mem = std.mem;
6const math = std.math;
7const Allocator = mem.Allocator;
8const ArrayList = std.ArrayList;
9
10/// Deprecated.
11pub fn Managed(comptime T: type) type {
12 return AlignedManaged(T, null);
13}
14
15/// Deprecated.
16pub fn AlignedManaged(comptime T: type, comptime alignment: ?mem.Alignment) type {
17 if (alignment) |a| {
18 if (a.toByteUnits() == @alignOf(T)) {
19 return AlignedManaged(T, null);
20 }
21 }
22 return struct {
23 const Self = @This();
24 /// Contents of the list. This field is intended to be accessed
25 /// directly.
26 ///
27 /// Pointers to elements in this slice are invalidated by various
28 /// functions of this ArrayList in accordance with the respective
29 /// documentation. In all cases, "invalidated" means that the memory
30 /// has been passed to this allocator's resize or free function.
31 items: Slice,
32 /// How many T values this list can hold without allocating
33 /// additional memory.
34 capacity: usize,
35 allocator: Allocator,
36
37 pub const Slice = if (alignment) |a| ([]align(a.toByteUnits()) T) else []T;
38
39 pub fn SentinelSlice(comptime s: T) type {
40 return if (alignment) |a| ([:s]align(a.toByteUnits()) T) else [:s]T;
41 }
42
43 /// Deinitialize with `deinit` or use `toOwnedSlice`.
44 pub fn init(gpa: Allocator) Self {
45 return Self{
46 .items = &[_]T{},
47 .capacity = 0,
48 .allocator = gpa,
49 };
50 }
51
52 /// Initialize with capacity to hold `num` elements.
53 /// The resulting capacity will equal `num` exactly.
54 /// Deinitialize with `deinit` or use `toOwnedSlice`.
55 pub fn initCapacity(gpa: Allocator, num: usize) Allocator.Error!Self {
56 var self = Self.init(gpa);
57 try self.ensureTotalCapacityPrecise(num);
58 return self;
59 }
60
61 /// Release all allocated memory.
62 pub fn deinit(self: Self) void {
63 if (@sizeOf(T) > 0) {
64 self.allocator.free(self.allocatedSlice());
65 }
66 }
67
68 /// ArrayList takes ownership of the passed in slice. The slice must have been
69 /// allocated with `gpa`.
70 /// Deinitialize with `deinit` or use `toOwnedSlice`.
71 pub fn fromOwnedSlice(gpa: Allocator, slice: Slice) Self {
72 return Self{
73 .items = slice,
74 .capacity = slice.len,
75 .allocator = gpa,
76 };
77 }
78
79 /// ArrayList takes ownership of the passed in slice. The slice must have been
80 /// allocated with `gpa`.
81 /// Deinitialize with `deinit` or use `toOwnedSlice`.
82 pub fn fromOwnedSliceSentinel(gpa: Allocator, comptime sentinel: T, slice: [:sentinel]T) Self {
83 return Self{
84 .items = slice,
85 .capacity = slice.len + 1,
86 .allocator = gpa,
87 };
88 }
89
90 /// Initializes an ArrayList with the `items` and `capacity` fields
91 /// of this ArrayList. Empties this ArrayList.
92 pub fn moveToUnmanaged(self: *Self) Aligned(T, alignment) {
93 const allocator = self.allocator;
94 const result: Aligned(T, alignment) = .{ .items = self.items, .capacity = self.capacity };
95 self.* = init(allocator);
96 return result;
97 }
98
99 /// The caller owns the returned memory. Empties this ArrayList.
100 /// Its capacity is cleared, making `deinit` safe but unnecessary to call.
101 pub fn toOwnedSlice(self: *Self) Allocator.Error!Slice {
102 const allocator = self.allocator;
103
104 const old_memory = self.allocatedSlice();
105 if (allocator.remap(old_memory, self.items.len)) |new_items| {
106 self.* = init(allocator);
107 return new_items;
108 }
109
110 const new_memory = try allocator.alignedAlloc(T, alignment, self.items.len);
111 @memcpy(new_memory, self.items);
112 self.clearAndFree();
113 return new_memory;
114 }
115
116 /// The caller owns the returned memory. Empties this ArrayList.
117 pub fn toOwnedSliceSentinel(self: *Self, comptime sentinel: T) Allocator.Error!SentinelSlice(sentinel) {
118 // This addition can never overflow because `self.items` can never occupy the whole address space
119 try self.ensureTotalCapacityPrecise(self.items.len + 1);
120 self.appendAssumeCapacity(sentinel);
121 const result = try self.toOwnedSlice();
122 return result[0 .. result.len - 1 :sentinel];
123 }
124
125 /// Creates a copy of this ArrayList, using the same allocator.
126 pub fn clone(self: Self) Allocator.Error!Self {
127 var cloned = try Self.initCapacity(self.allocator, self.capacity);
128 cloned.appendSliceAssumeCapacity(self.items);
129 return cloned;
130 }
131
132 /// Insert `item` at index `i`. Moves `list[i .. list.len]` to higher indices to make room.
133 /// If `i` is equal to the length of the list this operation is equivalent to append.
134 /// This operation is O(N).
135 /// Invalidates element pointers if additional memory is needed.
136 /// Asserts that the index is in bounds or equal to the length.
137 pub fn insert(self: *Self, i: usize, item: T) Allocator.Error!void {
138 const dst = try self.addManyAt(i, 1);
139 dst[0] = item;
140 }
141
142 /// Insert `item` at index `i`. Moves `list[i .. list.len]` to higher indices to make room.
143 /// If `i` is equal to the length of the list this operation is
144 /// equivalent to appendAssumeCapacity.
145 /// This operation is O(N).
146 /// Asserts that there is enough capacity for the new item.
147 /// Asserts that the index is in bounds or equal to the length.
148 pub fn insertAssumeCapacity(self: *Self, i: usize, item: T) void {
149 assert(self.items.len < self.capacity);
150 self.items.len += 1;
151
152 @memmove(self.items[i + 1 .. self.items.len], self.items[i .. self.items.len - 1]);
153 self.items[i] = item;
154 }
155
156 /// Add `count` new elements at position `index`, which have
157 /// `undefined` values. Returns a slice pointing to the newly allocated
158 /// elements, which becomes invalid after various `ArrayList`
159 /// operations.
160 /// Invalidates pre-existing pointers to elements at and after `index`.
161 /// Invalidates all pre-existing element pointers if capacity must be
162 /// increased to accommodate the new elements.
163 /// Asserts that the index is in bounds or equal to the length.
164 pub fn addManyAt(self: *Self, index: usize, count: usize) Allocator.Error![]T {
165 const new_len = try addOrOom(self.items.len, count);
166
167 if (self.capacity >= new_len)
168 return addManyAtAssumeCapacity(self, index, count);
169
170 // Here we avoid copying allocated but unused bytes by
171 // attempting a resize in place, and falling back to allocating
172 // a new buffer and doing our own copy. With a realloc() call,
173 // the allocator implementation would pointlessly copy our
174 // extra capacity.
175 const new_capacity = Aligned(T, alignment).growCapacity(new_len);
176 const old_memory = self.allocatedSlice();
177 if (self.allocator.remap(old_memory, new_capacity)) |new_memory| {
178 self.items.ptr = new_memory.ptr;
179 self.capacity = new_memory.len;
180 return addManyAtAssumeCapacity(self, index, count);
181 }
182
183 // Make a new allocation, avoiding `ensureTotalCapacity` in order
184 // to avoid extra memory copies.
185 const new_memory = try self.allocator.alignedAlloc(T, alignment, new_capacity);
186 const to_move = self.items[index..];
187 @memcpy(new_memory[0..index], self.items[0..index]);
188 @memcpy(new_memory[index + count ..][0..to_move.len], to_move);
189 self.allocator.free(old_memory);
190 self.items = new_memory[0..new_len];
191 self.capacity = new_memory.len;
192 // The inserted elements at `new_memory[index..][0..count]` have
193 // already been set to `undefined` by memory allocation.
194 return new_memory[index..][0..count];
195 }
196
197 /// Add `count` new elements at position `index`, which have
198 /// `undefined` values. Returns a slice pointing to the newly allocated
199 /// elements, which becomes invalid after various `ArrayList`
200 /// operations.
201 /// Asserts that there is enough capacity for the new elements.
202 /// Invalidates pre-existing pointers to elements at and after `index`, but
203 /// does not invalidate any before that.
204 /// Asserts that the index is in bounds or equal to the length.
205 pub fn addManyAtAssumeCapacity(self: *Self, index: usize, count: usize) []T {
206 const new_len = self.items.len + count;
207 assert(self.capacity >= new_len);
208 const to_move = self.items[index..];
209 self.items.len = new_len;
210 @memmove(self.items[index + count ..][0..to_move.len], to_move);
211 const result = self.items[index..][0..count];
212 @memset(result, undefined);
213 return result;
214 }
215
216 /// Insert slice `items` at index `i` by moving `list[i .. list.len]` to make room.
217 /// This operation is O(N).
218 /// Invalidates pre-existing pointers to elements at and after `index`.
219 /// Invalidates all pre-existing element pointers if capacity must be
220 /// increased to accommodate the new elements.
221 /// Asserts that the index is in bounds or equal to the length.
222 pub fn insertSlice(
223 self: *Self,
224 index: usize,
225 items: []const T,
226 ) Allocator.Error!void {
227 const dst = try self.addManyAt(index, items.len);
228 @memcpy(dst, items);
229 }
230
231 /// Grows or shrinks the list as necessary.
232 /// Invalidates element pointers if additional capacity is allocated.
233 /// Asserts that the range is in bounds.
234 pub fn replaceRange(self: *Self, start: usize, len: usize, new_items: []const T) Allocator.Error!void {
235 var unmanaged = self.moveToUnmanaged();
236 defer self.* = unmanaged.toManaged(self.allocator);
237 return unmanaged.replaceRange(self.allocator, start, len, new_items);
238 }
239
240 /// Grows or shrinks the list as necessary.
241 /// Never invalidates element pointers.
242 /// Asserts the capacity is enough for additional items.
243 pub fn replaceRangeAssumeCapacity(self: *Self, start: usize, len: usize, new_items: []const T) void {
244 var unmanaged = self.moveToUnmanaged();
245 defer self.* = unmanaged.toManaged(self.allocator);
246 return unmanaged.replaceRangeAssumeCapacity(start, len, new_items);
247 }
248
249 /// Extends the list by 1 element. Allocates more memory as necessary.
250 /// Invalidates element pointers if additional memory is needed.
251 pub fn append(self: *Self, item: T) Allocator.Error!void {
252 const new_item_ptr = try self.addOne();
253 new_item_ptr.* = item;
254 }
255
256 /// Extends the list by 1 element.
257 /// Never invalidates element pointers.
258 /// Asserts that the list can hold one additional item.
259 pub fn appendAssumeCapacity(self: *Self, item: T) void {
260 self.addOneAssumeCapacity().* = item;
261 }
262
263 /// Remove the element at index `i`, shift elements after index
264 /// `i` forward, and return the removed element.
265 /// Invalidates element pointers to end of list.
266 /// This operation is O(N).
267 /// This preserves item order. Use `swapRemove` if order preservation is not important.
268 /// Asserts that the index is in bounds.
269 /// Asserts that the list is not empty.
270 pub fn orderedRemove(self: *Self, i: usize) T {
271 const old_item = self.items[i];
272 self.replaceRangeAssumeCapacity(i, 1, &.{});
273 return old_item;
274 }
275
276 /// Removes the element at the specified index and returns it.
277 /// The empty slot is filled from the end of the list.
278 /// This operation is O(1).
279 /// This may not preserve item order. Use `orderedRemove` if you need to preserve order.
280 /// Asserts that the index is in bounds.
281 pub fn swapRemove(self: *Self, i: usize) T {
282 const val = self.items[i];
283 self.items[i] = self.items[self.items.len - 1];
284 self.items[self.items.len - 1] = undefined;
285 self.items.len -= 1;
286 return val;
287 }
288
289 /// Append the slice of items to the list. Allocates more
290 /// memory as necessary.
291 /// Invalidates element pointers if additional memory is needed.
292 pub fn appendSlice(self: *Self, items: []const T) Allocator.Error!void {
293 try self.ensureUnusedCapacity(items.len);
294 self.appendSliceAssumeCapacity(items);
295 }
296
297 /// Append the slice of items to the list.
298 /// Never invalidates element pointers.
299 /// Asserts that the list can hold the additional items.
300 pub fn appendSliceAssumeCapacity(self: *Self, items: []const T) void {
301 const old_len = self.items.len;
302 const new_len = old_len + items.len;
303 assert(new_len <= self.capacity);
304 self.items.len = new_len;
305 @memcpy(self.items[old_len..][0..items.len], items);
306 }
307
308 /// Append an unaligned slice of items to the list. Allocates more
309 /// memory as necessary. Only call this function if calling
310 /// `appendSlice` instead would be a compile error.
311 /// Invalidates element pointers if additional memory is needed.
312 pub fn appendUnalignedSlice(self: *Self, items: []align(1) const T) Allocator.Error!void {
313 try self.ensureUnusedCapacity(items.len);
314 self.appendUnalignedSliceAssumeCapacity(items);
315 }
316
317 /// Append the slice of items to the list.
318 /// Never invalidates element pointers.
319 /// This function is only needed when calling
320 /// `appendSliceAssumeCapacity` instead would be a compile error due to the
321 /// alignment of the `items` parameter.
322 /// Asserts that the list can hold the additional items.
323 pub fn appendUnalignedSliceAssumeCapacity(self: *Self, items: []align(1) const T) void {
324 const old_len = self.items.len;
325 const new_len = old_len + items.len;
326 assert(new_len <= self.capacity);
327 self.items.len = new_len;
328 @memcpy(self.items[old_len..][0..items.len], items);
329 }
330
331 pub fn print(self: *Self, comptime fmt: []const u8, args: anytype) error{OutOfMemory}!void {
332 const gpa = self.allocator;
333 var unmanaged = self.moveToUnmanaged();
334 defer self.* = unmanaged.toManaged(gpa);
335 try unmanaged.print(gpa, fmt, args);
336 }
337
338 /// Append a value to the list `n` times.
339 /// Allocates more memory as necessary.
340 /// Invalidates element pointers if additional memory is needed.
341 /// The function is inline so that a comptime-known `value` parameter will
342 /// have a more optimal memset codegen in case it has a repeated byte pattern.
343 pub inline fn appendNTimes(self: *Self, value: T, n: usize) Allocator.Error!void {
344 const old_len = self.items.len;
345 try self.resize(try addOrOom(old_len, n));
346 @memset(self.items[old_len..self.items.len], value);
347 }
348
349 /// Append a value to the list `n` times.
350 /// Never invalidates element pointers.
351 /// The function is inline so that a comptime-known `value` parameter will
352 /// have a more optimal memset codegen in case it has a repeated byte pattern.
353 /// Asserts that the list can hold the additional items.
354 pub inline fn appendNTimesAssumeCapacity(self: *Self, value: T, n: usize) void {
355 const new_len = self.items.len + n;
356 assert(new_len <= self.capacity);
357 @memset(self.items.ptr[self.items.len..new_len], value);
358 self.items.len = new_len;
359 }
360
361 /// Adjust the list length to `new_len`.
362 /// Additional elements contain the value `undefined`.
363 /// Invalidates element pointers if additional memory is needed.
364 pub fn resize(self: *Self, new_len: usize) Allocator.Error!void {
365 try self.ensureTotalCapacity(new_len);
366 self.items.len = new_len;
367 }
368
369 /// Reduce allocated capacity to `new_len`.
370 /// May invalidate element pointers.
371 /// Asserts that the new length is less than or equal to the previous length.
372 pub fn shrinkAndFree(self: *Self, new_len: usize) void {
373 var unmanaged = self.moveToUnmanaged();
374 unmanaged.shrinkAndFree(self.allocator, new_len);
375 self.* = unmanaged.toManaged(self.allocator);
376 }
377
378 /// Reduce length to `new_len`.
379 /// Invalidates element pointers for the elements `items[new_len..]`.
380 /// Asserts that the new length is less than or equal to the previous length.
381 pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
382 assert(new_len <= self.items.len);
383 @memset(self.items[new_len..], undefined);
384 self.items.len = new_len;
385 }
386
387 /// Reduce length to 0.
388 /// Invalidates all element pointers.
389 pub fn clearRetainingCapacity(self: *Self) void {
390 @memset(self.items, undefined);
391 self.items.len = 0;
392 }
393
394 /// Invalidates all element pointers.
395 pub fn clearAndFree(self: *Self) void {
396 self.allocator.free(self.allocatedSlice());
397 self.items.len = 0;
398 self.capacity = 0;
399 }
400
401 /// If the current capacity is less than `new_capacity`, this function will
402 /// modify the array so that it can hold at least `new_capacity` items.
403 /// Invalidates element pointers if additional memory is needed.
404 pub fn ensureTotalCapacity(self: *Self, new_capacity: usize) Allocator.Error!void {
405 if (@sizeOf(T) == 0) {
406 self.capacity = math.maxInt(usize);
407 return;
408 }
409
410 // Protects growing unnecessarily since better_capacity will be larger.
411 if (self.capacity >= new_capacity) return;
412
413 const better_capacity = Aligned(T, alignment).growCapacity(new_capacity);
414 return self.ensureTotalCapacityPrecise(better_capacity);
415 }
416
417 /// If the current capacity is less than `new_capacity`, this function will
418 /// modify the array so that it can hold exactly `new_capacity` items.
419 /// Invalidates element pointers if additional memory is needed.
420 pub fn ensureTotalCapacityPrecise(self: *Self, new_capacity: usize) Allocator.Error!void {
421 if (@sizeOf(T) == 0) {
422 self.capacity = math.maxInt(usize);
423 return;
424 }
425
426 if (self.capacity >= new_capacity) return;
427
428 // Here we avoid copying allocated but unused bytes by
429 // attempting a resize in place, and falling back to allocating
430 // a new buffer and doing our own copy. With a realloc() call,
431 // the allocator implementation would pointlessly copy our
432 // extra capacity.
433 const old_memory = self.allocatedSlice();
434 if (self.allocator.remap(old_memory, new_capacity)) |new_memory| {
435 self.items.ptr = new_memory.ptr;
436 self.capacity = new_memory.len;
437 } else {
438 const new_memory = try self.allocator.alignedAlloc(T, alignment, new_capacity);
439 @memcpy(new_memory[0..self.items.len], self.items);
440 self.allocator.free(old_memory);
441 self.items.ptr = new_memory.ptr;
442 self.capacity = new_memory.len;
443 }
444 }
445
446 /// Modify the array so that it can hold at least `additional_count` **more** items.
447 /// Invalidates element pointers if additional memory is needed.
448 pub fn ensureUnusedCapacity(self: *Self, additional_count: usize) Allocator.Error!void {
449 return self.ensureTotalCapacity(try addOrOom(self.items.len, additional_count));
450 }
451
452 /// Increases the array's length to match the full capacity that is already allocated.
453 /// The new elements have `undefined` values.
454 /// Never invalidates element pointers.
455 pub fn expandToCapacity(self: *Self) void {
456 self.items.len = self.capacity;
457 }
458
459 /// Increase length by 1, returning pointer to the new item.
460 /// The returned pointer becomes invalid when the list resized.
461 pub fn addOne(self: *Self) Allocator.Error!*T {
462 // This can never overflow because `self.items` can never occupy the whole address space
463 const newlen = self.items.len + 1;
464 try self.ensureTotalCapacity(newlen);
465 return self.addOneAssumeCapacity();
466 }
467
468 /// Increase length by 1, returning pointer to the new item.
469 /// The returned pointer becomes invalid when the list is resized.
470 /// Never invalidates element pointers.
471 /// Asserts that the list can hold one additional item.
472 pub fn addOneAssumeCapacity(self: *Self) *T {
473 assert(self.items.len < self.capacity);
474 self.items.len += 1;
475 return &self.items[self.items.len - 1];
476 }
477
478 /// Resize the array, adding `n` new elements, which have `undefined` values.
479 /// The return value is an array pointing to the newly allocated elements.
480 /// The returned pointer becomes invalid when the list is resized.
481 /// Resizes list if `self.capacity` is not large enough.
482 pub fn addManyAsArray(self: *Self, comptime n: usize) Allocator.Error!*[n]T {
483 const prev_len = self.items.len;
484 try self.resize(try addOrOom(self.items.len, n));
485 return self.items[prev_len..][0..n];
486 }
487
488 /// Resize the array, adding `n` new elements, which have `undefined` values.
489 /// The return value is an array pointing to the newly allocated elements.
490 /// Never invalidates element pointers.
491 /// The returned pointer becomes invalid when the list is resized.
492 /// Asserts that the list can hold the additional items.
493 pub fn addManyAsArrayAssumeCapacity(self: *Self, comptime n: usize) *[n]T {
494 assert(self.items.len + n <= self.capacity);
495 const prev_len = self.items.len;
496 self.items.len += n;
497 return self.items[prev_len..][0..n];
498 }
499
500 /// Resize the array, adding `n` new elements, which have `undefined` values.
501 /// The return value is a slice pointing to the newly allocated elements.
502 /// The returned pointer becomes invalid when the list is resized.
503 /// Resizes list if `self.capacity` is not large enough.
504 pub fn addManyAsSlice(self: *Self, n: usize) Allocator.Error![]T {
505 const prev_len = self.items.len;
506 try self.resize(try addOrOom(self.items.len, n));
507 return self.items[prev_len..][0..n];
508 }
509
510 /// Resize the array, adding `n` new elements, which have `undefined` values.
511 /// The return value is a slice pointing to the newly allocated elements.
512 /// Never invalidates element pointers.
513 /// The returned pointer becomes invalid when the list is resized.
514 /// Asserts that the list can hold the additional items.
515 pub fn addManyAsSliceAssumeCapacity(self: *Self, n: usize) []T {
516 assert(self.items.len + n <= self.capacity);
517 const prev_len = self.items.len;
518 self.items.len += n;
519 return self.items[prev_len..][0..n];
520 }
521
522 /// Remove and return the last element from the list, or return `null` if list is empty.
523 /// Invalidates element pointers to the removed element, if any.
524 pub fn pop(self: *Self) ?T {
525 if (self.items.len == 0) return null;
526 const val = self.items[self.items.len - 1];
527 self.items[self.items.len - 1] = undefined;
528 self.items.len -= 1;
529 return val;
530 }
531
532 /// Returns a slice of all the items plus the extra capacity, whose memory
533 /// contents are `undefined`.
534 pub fn allocatedSlice(self: Self) Slice {
535 // `items.len` is the length, not the capacity.
536 return self.items.ptr[0..self.capacity];
537 }
538
539 /// Returns a slice of only the extra capacity after items.
540 /// This can be useful for writing directly into an ArrayList.
541 /// Note that such an operation must be followed up with a direct
542 /// modification of `self.items.len`.
543 pub fn unusedCapacitySlice(self: Self) []T {
544 return self.allocatedSlice()[self.items.len..];
545 }
546
547 /// Returns the last element from the list.
548 /// Asserts that the list is not empty.
549 pub fn getLast(self: Self) T {
550 return self.items[self.items.len - 1];
551 }
552
553 /// Returns the last element from the list, or `null` if list is empty.
554 pub fn getLastOrNull(self: Self) ?T {
555 if (self.items.len == 0) return null;
556 return self.getLast();
557 }
558 };
559}
560
561/// A contiguous, growable list of arbitrarily aligned items in memory.
562/// This is a wrapper around an array of T values aligned to `alignment`-byte
563/// addresses. If the specified alignment is `null`, then `@alignOf(T)` is used.
564///
565/// Functions that potentially allocate memory accept an `Allocator` parameter.
566/// Initialize directly or with `initCapacity`, and deinitialize with `deinit`
567/// or use `toOwnedSlice`.
568///
569/// Default initialization of this struct is deprecated; use `.empty` instead.
570pub fn Aligned(comptime T: type, comptime alignment: ?mem.Alignment) type {
571 if (alignment) |a| {
572 if (a.toByteUnits() == @alignOf(T)) {
573 return Aligned(T, null);
574 }
575 }
576 return struct {
577 const Self = @This();
578 /// Contents of the list. This field is intended to be accessed
579 /// directly.
580 ///
581 /// Pointers to elements in this slice are invalidated by various
582 /// functions of this ArrayList in accordance with the respective
583 /// documentation. In all cases, "invalidated" means that the memory
584 /// has been passed to an allocator's resize or free function.
585 items: Slice = &[_]T{},
586 /// How many T values this list can hold without allocating
587 /// additional memory.
588 capacity: usize = 0,
589
590 /// An ArrayList containing no elements.
591 pub const empty: Self = .{
592 .items = &.{},
593 .capacity = 0,
594 };
595
596 pub const Slice = if (alignment) |a| ([]align(a.toByteUnits()) T) else []T;
597
598 pub fn SentinelSlice(comptime s: T) type {
599 return if (alignment) |a| ([:s]align(a.toByteUnits()) T) else [:s]T;
600 }
601
602 /// Initialize with capacity to hold `num` elements.
603 /// The resulting capacity will equal `num` exactly.
604 /// Deinitialize with `deinit` or use `toOwnedSlice`.
605 pub fn initCapacity(gpa: Allocator, num: usize) Allocator.Error!Self {
606 var self = Self{};
607 try self.ensureTotalCapacityPrecise(gpa, num);
608 return self;
609 }
610
611 /// Initialize with externally-managed memory. The buffer determines the
612 /// capacity, and the length is set to zero.
613 ///
614 /// When initialized this way, all functions that accept an Allocator
615 /// argument cause illegal behavior.
616 pub fn initBuffer(buffer: Slice) Self {
617 return .{
618 .items = buffer[0..0],
619 .capacity = buffer.len,
620 };
621 }
622
623 /// Release all allocated memory.
624 pub fn deinit(self: *Self, gpa: Allocator) void {
625 gpa.free(self.allocatedSlice());
626 self.* = undefined;
627 }
628
629 /// Convert this list into an analogous memory-managed one.
630 /// The returned list has ownership of the underlying memory.
631 pub fn toManaged(self: *Self, gpa: Allocator) AlignedManaged(T, alignment) {
632 return .{ .items = self.items, .capacity = self.capacity, .allocator = gpa };
633 }
634
635 /// ArrayList takes ownership of the passed in slice.
636 /// Deinitialize with `deinit` or use `toOwnedSlice`.
637 pub fn fromOwnedSlice(slice: Slice) Self {
638 return Self{
639 .items = slice,
640 .capacity = slice.len,
641 };
642 }
643
644 /// ArrayList takes ownership of the passed in slice.
645 /// Deinitialize with `deinit` or use `toOwnedSlice`.
646 pub fn fromOwnedSliceSentinel(comptime sentinel: T, slice: [:sentinel]T) Self {
647 return Self{
648 .items = slice,
649 .capacity = slice.len + 1,
650 };
651 }
652
653 /// The caller owns the returned memory. Empties this ArrayList.
654 /// Its capacity is cleared, making deinit() safe but unnecessary to call.
655 pub fn toOwnedSlice(self: *Self, gpa: Allocator) Allocator.Error!Slice {
656 const old_memory = self.allocatedSlice();
657 if (gpa.remap(old_memory, self.items.len)) |new_items| {
658 self.* = .empty;
659 return new_items;
660 }
661
662 const new_memory = try gpa.alignedAlloc(T, alignment, self.items.len);
663 @memcpy(new_memory, self.items);
664 self.clearAndFree(gpa);
665 return new_memory;
666 }
667
668 /// The caller owns the returned memory. ArrayList becomes empty.
669 pub fn toOwnedSliceSentinel(self: *Self, gpa: Allocator, comptime sentinel: T) Allocator.Error!SentinelSlice(sentinel) {
670 // This addition can never overflow because `self.items` can never occupy the whole address space.
671 try self.ensureTotalCapacityPrecise(gpa, self.items.len + 1);
672 self.appendAssumeCapacity(sentinel);
673 errdefer self.items.len -= 1;
674 const result = try self.toOwnedSlice(gpa);
675 return result[0 .. result.len - 1 :sentinel];
676 }
677
678 /// Creates a copy of this ArrayList.
679 pub fn clone(self: Self, gpa: Allocator) Allocator.Error!Self {
680 var cloned = try Self.initCapacity(gpa, self.capacity);
681 cloned.appendSliceAssumeCapacity(self.items);
682 return cloned;
683 }
684
685 /// Insert `item` at index `i`. Moves `list[i .. list.len]` to higher indices to make room.
686 /// If `i` is equal to the length of the list this operation is equivalent to append.
687 /// This operation is O(N).
688 /// Invalidates element pointers if additional memory is needed.
689 /// Asserts that the index is in bounds or equal to the length.
690 pub fn insert(self: *Self, gpa: Allocator, i: usize, item: T) Allocator.Error!void {
691 const dst = try self.addManyAt(gpa, i, 1);
692 dst[0] = item;
693 }
694
695 /// Insert `item` at index `i`. Moves `list[i .. list.len]` to higher indices to make room.
696 ///
697 /// If `i` is equal to the length of the list this operation is equivalent to append.
698 ///
699 /// This operation is O(N).
700 ///
701 /// Asserts that the list has capacity for one additional item.
702 ///
703 /// Asserts that the index is in bounds or equal to the length.
704 pub fn insertAssumeCapacity(self: *Self, i: usize, item: T) void {
705 assert(self.items.len < self.capacity);
706 self.items.len += 1;
707
708 @memmove(self.items[i + 1 .. self.items.len], self.items[i .. self.items.len - 1]);
709 self.items[i] = item;
710 }
711
712 /// Insert `item` at index `i`, moving `list[i .. list.len]` to higher indices to make room.
713 ///
714 /// If `i` is equal to the length of the list this operation is equivalent to append.
715 ///
716 /// This operation is O(N).
717 ///
718 /// If the list lacks unused capacity for the additional item, returns
719 /// `error.OutOfMemory`.
720 ///
721 /// Asserts that the index is in bounds or equal to the length.
722 pub fn insertBounded(self: *Self, i: usize, item: T) error{OutOfMemory}!void {
723 if (self.capacity - self.items.len == 0) return error.OutOfMemory;
724 return insertAssumeCapacity(self, i, item);
725 }
726
727 /// Add `count` new elements at position `index`, which have
728 /// `undefined` values. Returns a slice pointing to the newly allocated
729 /// elements, which becomes invalid after various `ArrayList`
730 /// operations.
731 /// Invalidates pre-existing pointers to elements at and after `index`.
732 /// Invalidates all pre-existing element pointers if capacity must be
733 /// increased to accommodate the new elements.
734 /// Asserts that the index is in bounds or equal to the length.
735 pub fn addManyAt(
736 self: *Self,
737 gpa: Allocator,
738 index: usize,
739 count: usize,
740 ) Allocator.Error![]T {
741 var managed = self.toManaged(gpa);
742 defer self.* = managed.moveToUnmanaged();
743 return managed.addManyAt(index, count);
744 }
745
746 /// Add `count` new elements at position `index`, which have
747 /// `undefined` values. Returns a slice pointing to the newly allocated
748 /// elements, which becomes invalid after various `ArrayList`
749 /// operations.
750 /// Invalidates pre-existing pointers to elements at and after `index`, but
751 /// does not invalidate any before that.
752 /// Asserts that the list has capacity for the additional items.
753 /// Asserts that the index is in bounds or equal to the length.
754 pub fn addManyAtAssumeCapacity(self: *Self, index: usize, count: usize) []T {
755 const new_len = self.items.len + count;
756 assert(self.capacity >= new_len);
757 const to_move = self.items[index..];
758 self.items.len = new_len;
759 @memmove(self.items[index + count ..][0..to_move.len], to_move);
760 const result = self.items[index..][0..count];
761 @memset(result, undefined);
762 return result;
763 }
764
765 /// Add `count` new elements at position `index`, which have
766 /// `undefined` values, returning a slice pointing to the newly
767 /// allocated elements, which becomes invalid after various `ArrayList`
768 /// operations.
769 ///
770 /// Invalidates pre-existing pointers to elements at and after `index`, but
771 /// does not invalidate any before that.
772 ///
773 /// If the list lacks unused capacity for the additional items, returns
774 /// `error.OutOfMemory`.
775 ///
776 /// Asserts that the index is in bounds or equal to the length.
777 pub fn addManyAtBounded(self: *Self, index: usize, count: usize) error{OutOfMemory}![]T {
778 if (self.capacity - self.items.len < count) return error.OutOfMemory;
779 return addManyAtAssumeCapacity(self, index, count);
780 }
781
782 /// Insert slice `items` at index `i` by moving `list[i .. list.len]` to make room.
783 /// This operation is O(N).
784 /// Invalidates pre-existing pointers to elements at and after `index`.
785 /// Invalidates all pre-existing element pointers if capacity must be
786 /// increased to accommodate the new elements.
787 /// Asserts that the index is in bounds or equal to the length.
788 pub fn insertSlice(
789 self: *Self,
790 gpa: Allocator,
791 index: usize,
792 items: []const T,
793 ) Allocator.Error!void {
794 const dst = try self.addManyAt(
795 gpa,
796 index,
797 items.len,
798 );
799 @memcpy(dst, items);
800 }
801
802 /// Insert slice `items` at index `i` by moving `list[i .. list.len]` to make room.
803 /// This operation is O(N).
804 /// Invalidates pre-existing pointers to elements at and after `index`.
805 /// Asserts that the list has capacity for the additional items.
806 /// Asserts that the index is in bounds or equal to the length.
807 pub fn insertSliceAssumeCapacity(
808 self: *Self,
809 index: usize,
810 items: []const T,
811 ) void {
812 const dst = self.addManyAtAssumeCapacity(index, items.len);
813 @memcpy(dst, items);
814 }
815
816 /// Insert slice `items` at index `i` by moving `list[i .. list.len]` to make room.
817 /// This operation is O(N).
818 /// Invalidates pre-existing pointers to elements at and after `index`.
819 /// If the list lacks unused capacity for the additional items, returns
820 /// `error.OutOfMemory`.
821 /// Asserts that the index is in bounds or equal to the length.
822 pub fn insertSliceBounded(
823 self: *Self,
824 index: usize,
825 items: []const T,
826 ) error{OutOfMemory}!void {
827 const dst = try self.addManyAtBounded(index, items.len);
828 @memcpy(dst, items);
829 }
830
831 /// Grows or shrinks the list as necessary.
832 /// Invalidates element pointers if additional capacity is allocated.
833 /// Asserts that the range is in bounds.
834 pub fn replaceRange(
835 self: *Self,
836 gpa: Allocator,
837 start: usize,
838 len: usize,
839 new_items: []const T,
840 ) Allocator.Error!void {
841 const after_range = start + len;
842 const range = self.items[start..after_range];
843 if (range.len < new_items.len) {
844 const first = new_items[0..range.len];
845 const rest = new_items[range.len..];
846 @memcpy(range[0..first.len], first);
847 try self.insertSlice(gpa, after_range, rest);
848 } else {
849 self.replaceRangeAssumeCapacity(start, len, new_items);
850 }
851 }
852
853 /// Grows or shrinks the list as necessary.
854 ///
855 /// Never invalidates element pointers.
856 ///
857 /// Asserts the capacity is enough for additional items.
858 pub fn replaceRangeAssumeCapacity(self: *Self, start: usize, len: usize, new_items: []const T) void {
859 const after_range = start + len;
860 const range = self.items[start..after_range];
861
862 if (range.len == new_items.len)
863 @memcpy(range[0..new_items.len], new_items)
864 else if (range.len < new_items.len) {
865 const first = new_items[0..range.len];
866 const rest = new_items[range.len..];
867 @memcpy(range[0..first.len], first);
868 const dst = self.addManyAtAssumeCapacity(after_range, rest.len);
869 @memcpy(dst, rest);
870 } else {
871 const extra = range.len - new_items.len;
872 @memcpy(range[0..new_items.len], new_items);
873 const src = self.items[after_range..];
874 @memmove(self.items[after_range - extra ..][0..src.len], src);
875 @memset(self.items[self.items.len - extra ..], undefined);
876 self.items.len -= extra;
877 }
878 }
879
880 /// Grows or shrinks the list as necessary.
881 ///
882 /// Never invalidates element pointers.
883 ///
884 /// If the unused capacity is insufficient for additional items,
885 /// returns `error.OutOfMemory`.
886 pub fn replaceRangeBounded(self: *Self, start: usize, len: usize, new_items: []const T) error{OutOfMemory}!void {
887 if (self.capacity - self.items.len < new_items.len -| len) return error.OutOfMemory;
888 return replaceRangeAssumeCapacity(self, start, len, new_items);
889 }
890
891 /// Extend the list by 1 element. Allocates more memory as necessary.
892 /// Invalidates element pointers if additional memory is needed.
893 pub fn append(self: *Self, gpa: Allocator, item: T) Allocator.Error!void {
894 const new_item_ptr = try self.addOne(gpa);
895 new_item_ptr.* = item;
896 }
897
898 /// Extend the list by 1 element.
899 ///
900 /// Never invalidates element pointers.
901 ///
902 /// Asserts that the list can hold one additional item.
903 pub fn appendAssumeCapacity(self: *Self, item: T) void {
904 self.addOneAssumeCapacity().* = item;
905 }
906
907 /// Extend the list by 1 element.
908 ///
909 /// Never invalidates element pointers.
910 ///
911 /// If the list lacks unused capacity for the additional item, returns
912 /// `error.OutOfMemory`.
913 pub fn appendBounded(self: *Self, item: T) error{OutOfMemory}!void {
914 if (self.capacity - self.items.len == 0) return error.OutOfMemory;
915 return appendAssumeCapacity(self, item);
916 }
917
918 /// Remove the element at index `i` from the list and return its value.
919 /// Invalidates pointers to the last element.
920 /// This operation is O(N).
921 /// Asserts that the index is in bounds.
922 pub fn orderedRemove(self: *Self, i: usize) T {
923 const old_item = self.items[i];
924 self.replaceRangeAssumeCapacity(i, 1, &.{});
925 return old_item;
926 }
927
928 /// Remove the elements indexed by `sorted_indexes`. The indexes to be
929 /// removed correspond to the array list before deletion.
930 ///
931 /// Asserts:
932 /// * Each index to be removed is in bounds.
933 /// * The indexes to be removed are sorted ascending.
934 ///
935 /// Duplicates in `sorted_indexes` are allowed.
936 ///
937 /// This operation is O(N).
938 ///
939 /// Invalidates element pointers beyond the first deleted index.
940 pub fn orderedRemoveMany(self: *Self, sorted_indexes: []const usize) void {
941 if (sorted_indexes.len == 0) return;
942 var shift: usize = 1;
943 for (sorted_indexes[0 .. sorted_indexes.len - 1], sorted_indexes[1..]) |removed, end| {
944 if (removed == end) continue; // allows duplicates in `sorted_indexes`
945 const start = removed + 1;
946 const len = end - start; // safety checks `sorted_indexes` are sorted
947 @memmove(self.items[start - shift ..][0..len], self.items[start..][0..len]); // safety checks initial `sorted_indexes` are in range
948 shift += 1;
949 }
950 const start = sorted_indexes[sorted_indexes.len - 1] + 1;
951 const end = self.items.len;
952 const len = end - start; // safety checks final `sorted_indexes` are in range
953 @memmove(self.items[start - shift ..][0..len], self.items[start..][0..len]);
954 self.items.len = end - shift;
955 }
956
957 /// Removes the element at the specified index and returns it.
958 /// The empty slot is filled from the end of the list.
959 /// Invalidates pointers to last element.
960 /// This operation is O(1).
961 /// Asserts that the index is in bounds.
962 pub fn swapRemove(self: *Self, i: usize) T {
963 const val = self.items[i];
964 self.items[i] = self.items[self.items.len - 1];
965 self.items[self.items.len - 1] = undefined;
966 self.items.len -= 1;
967 return val;
968 }
969
970 /// Append the slice of items to the list. Allocates more
971 /// memory as necessary.
972 /// Invalidates element pointers if additional memory is needed.
973 pub fn appendSlice(self: *Self, gpa: Allocator, items: []const T) Allocator.Error!void {
974 try self.ensureUnusedCapacity(gpa, items.len);
975 self.appendSliceAssumeCapacity(items);
976 }
977
978 /// Append the slice of items to the list.
979 ///
980 /// Asserts that the list can hold the additional items.
981 pub fn appendSliceAssumeCapacity(self: *Self, items: []const T) void {
982 const old_len = self.items.len;
983 const new_len = old_len + items.len;
984 assert(new_len <= self.capacity);
985 self.items.len = new_len;
986 @memcpy(self.items[old_len..][0..items.len], items);
987 }
988
989 /// Append the slice of items to the list.
990 ///
991 /// If the list lacks unused capacity for the additional items, returns `error.OutOfMemory`.
992 pub fn appendSliceBounded(self: *Self, items: []const T) error{OutOfMemory}!void {
993 if (self.capacity - self.items.len < items.len) return error.OutOfMemory;
994 return appendSliceAssumeCapacity(self, items);
995 }
996
997 /// Append the slice of items to the list. Allocates more
998 /// memory as necessary. Only call this function if a call to `appendSlice` instead would
999 /// be a compile error.
1000 /// Invalidates element pointers if additional memory is needed.
1001 pub fn appendUnalignedSlice(self: *Self, gpa: Allocator, items: []align(1) const T) Allocator.Error!void {
1002 try self.ensureUnusedCapacity(gpa, items.len);
1003 self.appendUnalignedSliceAssumeCapacity(items);
1004 }
1005
1006 /// Append an unaligned slice of items to the list.
1007 ///
1008 /// Intended to be used only when `appendSliceAssumeCapacity` would be
1009 /// a compile error.
1010 ///
1011 /// Asserts that the list can hold the additional items.
1012 pub fn appendUnalignedSliceAssumeCapacity(self: *Self, items: []align(1) const T) void {
1013 const old_len = self.items.len;
1014 const new_len = old_len + items.len;
1015 assert(new_len <= self.capacity);
1016 self.items.len = new_len;
1017 @memcpy(self.items[old_len..][0..items.len], items);
1018 }
1019
1020 /// Append an unaligned slice of items to the list.
1021 ///
1022 /// Intended to be used only when `appendSliceAssumeCapacity` would be
1023 /// a compile error.
1024 ///
1025 /// If the list lacks unused capacity for the additional items, returns
1026 /// `error.OutOfMemory`.
1027 pub fn appendUnalignedSliceBounded(self: *Self, items: []align(1) const T) error{OutOfMemory}!void {
1028 if (self.capacity - self.items.len < items.len) return error.OutOfMemory;
1029 return appendUnalignedSliceAssumeCapacity(self, items);
1030 }
1031
1032 pub fn print(self: *Self, gpa: Allocator, comptime fmt: []const u8, args: anytype) error{OutOfMemory}!void {
1033 comptime assert(T == u8);
1034 try self.ensureUnusedCapacity(gpa, fmt.len);
1035 var aw: std.Io.Writer.Allocating = .fromArrayList(gpa, self);
1036 defer self.* = aw.toArrayList();
1037 return aw.writer.print(fmt, args) catch |err| switch (err) {
1038 error.WriteFailed => return error.OutOfMemory,
1039 };
1040 }
1041
1042 pub fn printAssumeCapacity(self: *Self, comptime fmt: []const u8, args: anytype) void {
1043 comptime assert(T == u8);
1044 var w: std.Io.Writer = .fixed(self.unusedCapacitySlice());
1045 w.print(fmt, args) catch unreachable;
1046 self.items.len += w.end;
1047 }
1048
1049 pub fn printBounded(self: *Self, comptime fmt: []const u8, args: anytype) error{OutOfMemory}!void {
1050 comptime assert(T == u8);
1051 var w: std.Io.Writer = .fixed(self.unusedCapacitySlice());
1052 w.print(fmt, args) catch return error.OutOfMemory;
1053 self.items.len += w.end;
1054 }
1055
1056 /// Append a value to the list `n` times.
1057 /// Allocates more memory as necessary.
1058 /// Invalidates element pointers if additional memory is needed.
1059 /// The function is inline so that a comptime-known `value` parameter will
1060 /// have a more optimal memset codegen in case it has a repeated byte pattern.
1061 pub inline fn appendNTimes(self: *Self, gpa: Allocator, value: T, n: usize) Allocator.Error!void {
1062 const old_len = self.items.len;
1063 try self.resize(gpa, try addOrOom(old_len, n));
1064 @memset(self.items[old_len..self.items.len], value);
1065 }
1066
1067 /// Append a value to the list `n` times.
1068 ///
1069 /// Never invalidates element pointers.
1070 ///
1071 /// The function is inline so that a comptime-known `value` parameter will
1072 /// have better memset codegen in case it has a repeated byte pattern.
1073 ///
1074 /// Asserts that the list can hold the additional items.
1075 pub inline fn appendNTimesAssumeCapacity(self: *Self, value: T, n: usize) void {
1076 const new_len = self.items.len + n;
1077 assert(new_len <= self.capacity);
1078 @memset(self.items.ptr[self.items.len..new_len], value);
1079 self.items.len = new_len;
1080 }
1081
1082 /// Append a value to the list `n` times.
1083 ///
1084 /// Never invalidates element pointers.
1085 ///
1086 /// The function is inline so that a comptime-known `value` parameter will
1087 /// have better memset codegen in case it has a repeated byte pattern.
1088 ///
1089 /// If the list lacks unused capacity for the additional items, returns
1090 /// `error.OutOfMemory`.
1091 pub inline fn appendNTimesBounded(self: *Self, value: T, n: usize) error{OutOfMemory}!void {
1092 const new_len = self.items.len + n;
1093 if (self.capacity < new_len) return error.OutOfMemory;
1094 @memset(self.items.ptr[self.items.len..new_len], value);
1095 self.items.len = new_len;
1096 }
1097
1098 /// Adjust the list length to `new_len`.
1099 /// Additional elements contain the value `undefined`.
1100 /// Invalidates element pointers if additional memory is needed.
1101 pub fn resize(self: *Self, gpa: Allocator, new_len: usize) Allocator.Error!void {
1102 try self.ensureTotalCapacity(gpa, new_len);
1103 self.items.len = new_len;
1104 }
1105
1106 /// Reduce allocated capacity to `new_len`.
1107 /// May invalidate element pointers.
1108 /// Asserts that the new length is less than or equal to the previous length.
1109 pub fn shrinkAndFree(self: *Self, gpa: Allocator, new_len: usize) void {
1110 assert(new_len <= self.items.len);
1111
1112 if (@sizeOf(T) == 0) {
1113 self.items.len = new_len;
1114 return;
1115 }
1116
1117 const old_memory = self.allocatedSlice();
1118 if (gpa.remap(old_memory, new_len)) |new_items| {
1119 self.capacity = new_items.len;
1120 self.items = new_items;
1121 return;
1122 }
1123
1124 const new_memory = gpa.alignedAlloc(T, alignment, new_len) catch |e| switch (e) {
1125 error.OutOfMemory => {
1126 // No problem, capacity is still correct then.
1127 self.items.len = new_len;
1128 return;
1129 },
1130 };
1131
1132 @memcpy(new_memory, self.items[0..new_len]);
1133 gpa.free(old_memory);
1134 self.items = new_memory;
1135 self.capacity = new_memory.len;
1136 }
1137
1138 /// Reduce length to `new_len`.
1139 /// Invalidates pointers to elements `items[new_len..]`.
1140 /// Keeps capacity the same.
1141 /// Asserts that the new length is less than or equal to the previous length.
1142 pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
1143 assert(new_len <= self.items.len);
1144 @memset(self.items[new_len..], undefined);
1145 self.items.len = new_len;
1146 }
1147
1148 /// Reduce length to 0.
1149 /// Invalidates all element pointers.
1150 pub fn clearRetainingCapacity(self: *Self) void {
1151 @memset(self.items, undefined);
1152 self.items.len = 0;
1153 }
1154
1155 /// Invalidates all element pointers.
1156 pub fn clearAndFree(self: *Self, gpa: Allocator) void {
1157 gpa.free(self.allocatedSlice());
1158 self.items.len = 0;
1159 self.capacity = 0;
1160 }
1161
1162 /// Modify the array so that it can hold at least `new_capacity` items.
1163 /// Implements super-linear growth to achieve amortized O(1) append operations.
1164 /// Invalidates element pointers if additional memory is needed.
1165 pub fn ensureTotalCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
1166 if (self.capacity >= new_capacity) return;
1167 return self.ensureTotalCapacityPrecise(gpa, growCapacity(new_capacity));
1168 }
1169
1170 /// If the current capacity is less than `new_capacity`, this function will
1171 /// modify the array so that it can hold exactly `new_capacity` items.
1172 /// Invalidates element pointers if additional memory is needed.
1173 pub fn ensureTotalCapacityPrecise(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
1174 if (@sizeOf(T) == 0) {
1175 self.capacity = math.maxInt(usize);
1176 return;
1177 }
1178
1179 if (self.capacity >= new_capacity) return;
1180
1181 // Here we avoid copying allocated but unused bytes by
1182 // attempting a resize in place, and falling back to allocating
1183 // a new buffer and doing our own copy. With a realloc() call,
1184 // the allocator implementation would pointlessly copy our
1185 // extra capacity.
1186 const old_memory = self.allocatedSlice();
1187 if (gpa.remap(old_memory, new_capacity)) |new_memory| {
1188 self.items.ptr = new_memory.ptr;
1189 self.capacity = new_memory.len;
1190 } else {
1191 const new_memory = try gpa.alignedAlloc(T, alignment, new_capacity);
1192 @memcpy(new_memory[0..self.items.len], self.items);
1193 gpa.free(old_memory);
1194 self.items.ptr = new_memory.ptr;
1195 self.capacity = new_memory.len;
1196 }
1197 }
1198
1199 /// Modify the array so that it can hold at least `additional_count` **more** items.
1200 /// Invalidates element pointers if additional memory is needed.
1201 pub fn ensureUnusedCapacity(
1202 self: *Self,
1203 gpa: Allocator,
1204 additional_count: usize,
1205 ) Allocator.Error!void {
1206 return self.ensureTotalCapacity(gpa, try addOrOom(self.items.len, additional_count));
1207 }
1208
1209 /// Increases the array's length to match the full capacity that is already allocated.
1210 /// The new elements have `undefined` values.
1211 /// Never invalidates element pointers.
1212 pub fn expandToCapacity(self: *Self) void {
1213 self.items.len = self.capacity;
1214 }
1215
1216 /// Increase length by 1, returning pointer to the new item.
1217 /// The returned element pointer becomes invalid when the list is resized.
1218 pub fn addOne(self: *Self, gpa: Allocator) Allocator.Error!*T {
1219 // This can never overflow because `self.items` can never occupy the whole address space
1220 const newlen = self.items.len + 1;
1221 try self.ensureTotalCapacity(gpa, newlen);
1222 return self.addOneAssumeCapacity();
1223 }
1224
1225 /// Increase length by 1, returning pointer to the new item.
1226 ///
1227 /// Never invalidates element pointers.
1228 ///
1229 /// The returned element pointer becomes invalid when the list is resized.
1230 ///
1231 /// Asserts that the list can hold one additional item.
1232 pub fn addOneAssumeCapacity(self: *Self) *T {
1233 assert(self.items.len < self.capacity);
1234
1235 self.items.len += 1;
1236 return &self.items[self.items.len - 1];
1237 }
1238
1239 /// Increase length by 1, returning pointer to the new item.
1240 ///
1241 /// Never invalidates element pointers.
1242 ///
1243 /// The returned element pointer becomes invalid when the list is resized.
1244 ///
1245 /// If the list lacks unused capacity for the additional item, returns `error.OutOfMemory`.
1246 pub fn addOneBounded(self: *Self) error{OutOfMemory}!*T {
1247 if (self.capacity - self.items.len < 1) return error.OutOfMemory;
1248 return addOneAssumeCapacity(self);
1249 }
1250
1251 /// Resize the array, adding `n` new elements, which have `undefined` values.
1252 /// The return value is an array pointing to the newly allocated elements.
1253 /// The returned pointer becomes invalid when the list is resized.
1254 pub fn addManyAsArray(self: *Self, gpa: Allocator, comptime n: usize) Allocator.Error!*[n]T {
1255 const prev_len = self.items.len;
1256 try self.resize(gpa, try addOrOom(self.items.len, n));
1257 return self.items[prev_len..][0..n];
1258 }
1259
1260 /// Resize the array, adding `n` new elements, which have `undefined` values.
1261 ///
1262 /// The return value is an array pointing to the newly allocated elements.
1263 ///
1264 /// Never invalidates element pointers.
1265 ///
1266 /// The returned pointer becomes invalid when the list is resized.
1267 ///
1268 /// Asserts that the list can hold the additional items.
1269 pub fn addManyAsArrayAssumeCapacity(self: *Self, comptime n: usize) *[n]T {
1270 assert(self.items.len + n <= self.capacity);
1271 const prev_len = self.items.len;
1272 self.items.len += n;
1273 return self.items[prev_len..][0..n];
1274 }
1275
1276 /// Resize the array, adding `n` new elements, which have `undefined` values.
1277 ///
1278 /// The return value is an array pointing to the newly allocated elements.
1279 ///
1280 /// Never invalidates element pointers.
1281 ///
1282 /// The returned pointer becomes invalid when the list is resized.
1283 ///
1284 /// If the list lacks unused capacity for the additional items, returns
1285 /// `error.OutOfMemory`.
1286 pub fn addManyAsArrayBounded(self: *Self, comptime n: usize) error{OutOfMemory}!*[n]T {
1287 if (self.capacity - self.items.len < n) return error.OutOfMemory;
1288 return addManyAsArrayAssumeCapacity(self, n);
1289 }
1290
1291 /// Resize the array, adding `n` new elements, which have `undefined` values.
1292 /// The return value is a slice pointing to the newly allocated elements.
1293 /// The returned pointer becomes invalid when the list is resized.
1294 /// Resizes list if `self.capacity` is not large enough.
1295 pub fn addManyAsSlice(self: *Self, gpa: Allocator, n: usize) Allocator.Error![]T {
1296 const prev_len = self.items.len;
1297 try self.resize(gpa, try addOrOom(self.items.len, n));
1298 return self.items[prev_len..][0..n];
1299 }
1300
1301 /// Resizes the array, adding `n` new elements, which have `undefined`
1302 /// values, returning a slice pointing to the newly allocated elements.
1303 ///
1304 /// Never invalidates element pointers. The returned pointer becomes
1305 /// invalid when the list is resized.
1306 ///
1307 /// Asserts that the list can hold the additional items.
1308 pub fn addManyAsSliceAssumeCapacity(self: *Self, n: usize) []T {
1309 assert(self.items.len + n <= self.capacity);
1310 const prev_len = self.items.len;
1311 self.items.len += n;
1312 return self.items[prev_len..][0..n];
1313 }
1314
1315 /// Resizes the array, adding `n` new elements, which have `undefined`
1316 /// values, returning a slice pointing to the newly allocated elements.
1317 ///
1318 /// Never invalidates element pointers. The returned pointer becomes
1319 /// invalid when the list is resized.
1320 ///
1321 /// If the list lacks unused capacity for the additional items, returns
1322 /// `error.OutOfMemory`.
1323 pub fn addManyAsSliceBounded(self: *Self, n: usize) error{OutOfMemory}![]T {
1324 if (self.capacity - self.items.len < n) return error.OutOfMemory;
1325 return addManyAsSliceAssumeCapacity(self, n);
1326 }
1327
1328 /// Remove and return the last element from the list.
1329 /// If the list is empty, returns `null`.
1330 /// Invalidates pointers to last element.
1331 pub fn pop(self: *Self) ?T {
1332 if (self.items.len == 0) return null;
1333 const val = self.items[self.items.len - 1];
1334 self.items[self.items.len - 1] = undefined;
1335 self.items.len -= 1;
1336 return val;
1337 }
1338
1339 /// Returns a slice of all the items plus the extra capacity, whose memory
1340 /// contents are `undefined`.
1341 pub fn allocatedSlice(self: Self) Slice {
1342 return self.items.ptr[0..self.capacity];
1343 }
1344
1345 /// Returns a slice of only the extra capacity after items.
1346 /// This can be useful for writing directly into an ArrayList.
1347 /// Note that such an operation must be followed up with a direct
1348 /// modification of `self.items.len`.
1349 pub fn unusedCapacitySlice(self: Self) []T {
1350 return self.allocatedSlice()[self.items.len..];
1351 }
1352
1353 /// Return the last element from the list.
1354 /// Asserts that the list is not empty.
1355 pub fn getLast(self: Self) T {
1356 return self.items[self.items.len - 1];
1357 }
1358
1359 /// Return the last element from the list, or
1360 /// return `null` if list is empty.
1361 pub fn getLastOrNull(self: Self) ?T {
1362 if (self.items.len == 0) return null;
1363 return self.getLast();
1364 }
1365
1366 const init_capacity: comptime_int = @max(1, std.atomic.cache_line / @sizeOf(T));
1367
1368 /// Called when memory growth is necessary. Returns a capacity larger than
1369 /// minimum that grows super-linearly.
1370 pub fn growCapacity(minimum: usize) usize {
1371 return minimum +| (minimum / 2 + init_capacity);
1372 }
1373 };
1374}
1375
1376/// Integer addition returning `error.OutOfMemory` on overflow.
1377fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize {
1378 const result, const overflow = @addWithOverflow(a, b);
1379 if (overflow != 0) return error.OutOfMemory;
1380 return result;
1381}
1382
1383test "init" {
1384 {
1385 var list = Managed(i32).init(testing.allocator);
1386 defer list.deinit();
1387
1388 try testing.expect(list.items.len == 0);
1389 try testing.expect(list.capacity == 0);
1390 }
1391
1392 {
1393 const list: ArrayList(i32) = .empty;
1394
1395 try testing.expect(list.items.len == 0);
1396 try testing.expect(list.capacity == 0);
1397 }
1398}
1399
1400test "initCapacity" {
1401 const a = testing.allocator;
1402 {
1403 var list = try Managed(i8).initCapacity(a, 200);
1404 defer list.deinit();
1405 try testing.expect(list.items.len == 0);
1406 try testing.expect(list.capacity >= 200);
1407 }
1408 {
1409 var list = try ArrayList(i8).initCapacity(a, 200);
1410 defer list.deinit(a);
1411 try testing.expect(list.items.len == 0);
1412 try testing.expect(list.capacity >= 200);
1413 }
1414}
1415
1416test "clone" {
1417 const a = testing.allocator;
1418 {
1419 var array = Managed(i32).init(a);
1420 try array.append(-1);
1421 try array.append(3);
1422 try array.append(5);
1423
1424 const cloned = try array.clone();
1425 defer cloned.deinit();
1426
1427 try testing.expectEqualSlices(i32, array.items, cloned.items);
1428 try testing.expectEqual(array.allocator, cloned.allocator);
1429 try testing.expect(cloned.capacity >= array.capacity);
1430
1431 array.deinit();
1432
1433 try testing.expectEqual(@as(i32, -1), cloned.items[0]);
1434 try testing.expectEqual(@as(i32, 3), cloned.items[1]);
1435 try testing.expectEqual(@as(i32, 5), cloned.items[2]);
1436 }
1437 {
1438 var array: ArrayList(i32) = .empty;
1439 try array.append(a, -1);
1440 try array.append(a, 3);
1441 try array.append(a, 5);
1442
1443 var cloned = try array.clone(a);
1444 defer cloned.deinit(a);
1445
1446 try testing.expectEqualSlices(i32, array.items, cloned.items);
1447 try testing.expect(cloned.capacity >= array.capacity);
1448
1449 array.deinit(a);
1450
1451 try testing.expectEqual(@as(i32, -1), cloned.items[0]);
1452 try testing.expectEqual(@as(i32, 3), cloned.items[1]);
1453 try testing.expectEqual(@as(i32, 5), cloned.items[2]);
1454 }
1455}
1456
1457test "basic" {
1458 const a = testing.allocator;
1459 {
1460 var list = Managed(i32).init(a);
1461 defer list.deinit();
1462
1463 {
1464 var i: usize = 0;
1465 while (i < 10) : (i += 1) {
1466 list.append(@as(i32, @intCast(i + 1))) catch unreachable;
1467 }
1468 }
1469
1470 {
1471 var i: usize = 0;
1472 while (i < 10) : (i += 1) {
1473 try testing.expect(list.items[i] == @as(i32, @intCast(i + 1)));
1474 }
1475 }
1476
1477 for (list.items, 0..) |v, i| {
1478 try testing.expect(v == @as(i32, @intCast(i + 1)));
1479 }
1480
1481 try testing.expect(list.pop() == 10);
1482 try testing.expect(list.items.len == 9);
1483
1484 list.appendSlice(&[_]i32{ 1, 2, 3 }) catch unreachable;
1485 try testing.expect(list.items.len == 12);
1486 try testing.expect(list.pop() == 3);
1487 try testing.expect(list.pop() == 2);
1488 try testing.expect(list.pop() == 1);
1489 try testing.expect(list.items.len == 9);
1490
1491 var unaligned: [3]i32 align(1) = [_]i32{ 4, 5, 6 };
1492 list.appendUnalignedSlice(&unaligned) catch unreachable;
1493 try testing.expect(list.items.len == 12);
1494 try testing.expect(list.pop() == 6);
1495 try testing.expect(list.pop() == 5);
1496 try testing.expect(list.pop() == 4);
1497 try testing.expect(list.items.len == 9);
1498
1499 list.appendSlice(&[_]i32{}) catch unreachable;
1500 try testing.expect(list.items.len == 9);
1501
1502 // can only set on indices < self.items.len
1503 list.items[7] = 33;
1504 list.items[8] = 42;
1505
1506 try testing.expect(list.pop() == 42);
1507 try testing.expect(list.pop() == 33);
1508 }
1509 {
1510 var list: ArrayList(i32) = .empty;
1511 defer list.deinit(a);
1512
1513 {
1514 var i: usize = 0;
1515 while (i < 10) : (i += 1) {
1516 list.append(a, @as(i32, @intCast(i + 1))) catch unreachable;
1517 }
1518 }
1519
1520 {
1521 var i: usize = 0;
1522 while (i < 10) : (i += 1) {
1523 try testing.expect(list.items[i] == @as(i32, @intCast(i + 1)));
1524 }
1525 }
1526
1527 for (list.items, 0..) |v, i| {
1528 try testing.expect(v == @as(i32, @intCast(i + 1)));
1529 }
1530
1531 try testing.expect(list.pop() == 10);
1532 try testing.expect(list.items.len == 9);
1533
1534 list.appendSlice(a, &[_]i32{ 1, 2, 3 }) catch unreachable;
1535 try testing.expect(list.items.len == 12);
1536 try testing.expect(list.pop() == 3);
1537 try testing.expect(list.pop() == 2);
1538 try testing.expect(list.pop() == 1);
1539 try testing.expect(list.items.len == 9);
1540
1541 var unaligned: [3]i32 align(1) = [_]i32{ 4, 5, 6 };
1542 list.appendUnalignedSlice(a, &unaligned) catch unreachable;
1543 try testing.expect(list.items.len == 12);
1544 try testing.expect(list.pop() == 6);
1545 try testing.expect(list.pop() == 5);
1546 try testing.expect(list.pop() == 4);
1547 try testing.expect(list.items.len == 9);
1548
1549 list.appendSlice(a, &[_]i32{}) catch unreachable;
1550 try testing.expect(list.items.len == 9);
1551
1552 // can only set on indices < self.items.len
1553 list.items[7] = 33;
1554 list.items[8] = 42;
1555
1556 try testing.expect(list.pop() == 42);
1557 try testing.expect(list.pop() == 33);
1558 }
1559}
1560
1561test "appendNTimes" {
1562 const a = testing.allocator;
1563 {
1564 var list = Managed(i32).init(a);
1565 defer list.deinit();
1566
1567 try list.appendNTimes(2, 10);
1568 try testing.expectEqual(@as(usize, 10), list.items.len);
1569 for (list.items) |element| {
1570 try testing.expectEqual(@as(i32, 2), element);
1571 }
1572 }
1573 {
1574 var list: ArrayList(i32) = .empty;
1575 defer list.deinit(a);
1576
1577 try list.appendNTimes(a, 2, 10);
1578 try testing.expectEqual(@as(usize, 10), list.items.len);
1579 for (list.items) |element| {
1580 try testing.expectEqual(@as(i32, 2), element);
1581 }
1582 }
1583}
1584
1585test "appendNTimes with failing allocator" {
1586 const a = testing.failing_allocator;
1587 {
1588 var list = Managed(i32).init(a);
1589 defer list.deinit();
1590 try testing.expectError(error.OutOfMemory, list.appendNTimes(2, 10));
1591 }
1592 {
1593 var list: ArrayList(i32) = .empty;
1594 defer list.deinit(a);
1595 try testing.expectError(error.OutOfMemory, list.appendNTimes(a, 2, 10));
1596 }
1597}
1598
1599test "orderedRemove" {
1600 const a = testing.allocator;
1601 {
1602 var list = Managed(i32).init(a);
1603 defer list.deinit();
1604
1605 try list.append(1);
1606 try list.append(2);
1607 try list.append(3);
1608 try list.append(4);
1609 try list.append(5);
1610 try list.append(6);
1611 try list.append(7);
1612
1613 //remove from middle
1614 try testing.expectEqual(@as(i32, 4), list.orderedRemove(3));
1615 try testing.expectEqual(@as(i32, 5), list.items[3]);
1616 try testing.expectEqual(@as(usize, 6), list.items.len);
1617
1618 //remove from end
1619 try testing.expectEqual(@as(i32, 7), list.orderedRemove(5));
1620 try testing.expectEqual(@as(usize, 5), list.items.len);
1621
1622 //remove from front
1623 try testing.expectEqual(@as(i32, 1), list.orderedRemove(0));
1624 try testing.expectEqual(@as(i32, 2), list.items[0]);
1625 try testing.expectEqual(@as(usize, 4), list.items.len);
1626 }
1627 {
1628 var list: ArrayList(i32) = .empty;
1629 defer list.deinit(a);
1630
1631 try list.append(a, 1);
1632 try list.append(a, 2);
1633 try list.append(a, 3);
1634 try list.append(a, 4);
1635 try list.append(a, 5);
1636 try list.append(a, 6);
1637 try list.append(a, 7);
1638
1639 //remove from middle
1640 try testing.expectEqual(@as(i32, 4), list.orderedRemove(3));
1641 try testing.expectEqual(@as(i32, 5), list.items[3]);
1642 try testing.expectEqual(@as(usize, 6), list.items.len);
1643
1644 //remove from end
1645 try testing.expectEqual(@as(i32, 7), list.orderedRemove(5));
1646 try testing.expectEqual(@as(usize, 5), list.items.len);
1647
1648 //remove from front
1649 try testing.expectEqual(@as(i32, 1), list.orderedRemove(0));
1650 try testing.expectEqual(@as(i32, 2), list.items[0]);
1651 try testing.expectEqual(@as(usize, 4), list.items.len);
1652 }
1653 {
1654 // remove last item
1655 var list = Managed(i32).init(a);
1656 defer list.deinit();
1657 try list.append(1);
1658 try testing.expectEqual(@as(i32, 1), list.orderedRemove(0));
1659 try testing.expectEqual(@as(usize, 0), list.items.len);
1660 }
1661 {
1662 // remove last item
1663 var list: ArrayList(i32) = .empty;
1664 defer list.deinit(a);
1665 try list.append(a, 1);
1666 try testing.expectEqual(@as(i32, 1), list.orderedRemove(0));
1667 try testing.expectEqual(@as(usize, 0), list.items.len);
1668 }
1669}
1670
1671test "swapRemove" {
1672 const a = testing.allocator;
1673 {
1674 var list = Managed(i32).init(a);
1675 defer list.deinit();
1676
1677 try list.append(1);
1678 try list.append(2);
1679 try list.append(3);
1680 try list.append(4);
1681 try list.append(5);
1682 try list.append(6);
1683 try list.append(7);
1684
1685 //remove from middle
1686 try testing.expect(list.swapRemove(3) == 4);
1687 try testing.expect(list.items[3] == 7);
1688 try testing.expect(list.items.len == 6);
1689
1690 //remove from end
1691 try testing.expect(list.swapRemove(5) == 6);
1692 try testing.expect(list.items.len == 5);
1693
1694 //remove from front
1695 try testing.expect(list.swapRemove(0) == 1);
1696 try testing.expect(list.items[0] == 5);
1697 try testing.expect(list.items.len == 4);
1698 }
1699 {
1700 var list: ArrayList(i32) = .empty;
1701 defer list.deinit(a);
1702
1703 try list.append(a, 1);
1704 try list.append(a, 2);
1705 try list.append(a, 3);
1706 try list.append(a, 4);
1707 try list.append(a, 5);
1708 try list.append(a, 6);
1709 try list.append(a, 7);
1710
1711 //remove from middle
1712 try testing.expect(list.swapRemove(3) == 4);
1713 try testing.expect(list.items[3] == 7);
1714 try testing.expect(list.items.len == 6);
1715
1716 //remove from end
1717 try testing.expect(list.swapRemove(5) == 6);
1718 try testing.expect(list.items.len == 5);
1719
1720 //remove from front
1721 try testing.expect(list.swapRemove(0) == 1);
1722 try testing.expect(list.items[0] == 5);
1723 try testing.expect(list.items.len == 4);
1724 }
1725}
1726
1727test "insert" {
1728 const a = testing.allocator;
1729 {
1730 var list = Managed(i32).init(a);
1731 defer list.deinit();
1732
1733 try list.insert(0, 1);
1734 try list.append(2);
1735 try list.insert(2, 3);
1736 try list.insert(0, 5);
1737 try testing.expect(list.items[0] == 5);
1738 try testing.expect(list.items[1] == 1);
1739 try testing.expect(list.items[2] == 2);
1740 try testing.expect(list.items[3] == 3);
1741 }
1742 {
1743 var list: ArrayList(i32) = .empty;
1744 defer list.deinit(a);
1745
1746 try list.insert(a, 0, 1);
1747 try list.append(a, 2);
1748 try list.insert(a, 2, 3);
1749 try list.insert(a, 0, 5);
1750 try testing.expect(list.items[0] == 5);
1751 try testing.expect(list.items[1] == 1);
1752 try testing.expect(list.items[2] == 2);
1753 try testing.expect(list.items[3] == 3);
1754 }
1755}
1756
1757test "insertSlice" {
1758 const a = testing.allocator;
1759 {
1760 var list = Managed(i32).init(a);
1761 defer list.deinit();
1762
1763 try list.append(1);
1764 try list.append(2);
1765 try list.append(3);
1766 try list.append(4);
1767 try list.insertSlice(1, &[_]i32{ 9, 8 });
1768 try testing.expect(list.items[0] == 1);
1769 try testing.expect(list.items[1] == 9);
1770 try testing.expect(list.items[2] == 8);
1771 try testing.expect(list.items[3] == 2);
1772 try testing.expect(list.items[4] == 3);
1773 try testing.expect(list.items[5] == 4);
1774
1775 const items = [_]i32{1};
1776 try list.insertSlice(0, items[0..0]);
1777 try testing.expect(list.items.len == 6);
1778 try testing.expect(list.items[0] == 1);
1779 }
1780 {
1781 var list: ArrayList(i32) = .empty;
1782 defer list.deinit(a);
1783
1784 try list.append(a, 1);
1785 try list.append(a, 2);
1786 try list.append(a, 3);
1787 try list.append(a, 4);
1788 try list.insertSlice(a, 1, &[_]i32{ 9, 8 });
1789 try testing.expect(list.items[0] == 1);
1790 try testing.expect(list.items[1] == 9);
1791 try testing.expect(list.items[2] == 8);
1792 try testing.expect(list.items[3] == 2);
1793 try testing.expect(list.items[4] == 3);
1794 try testing.expect(list.items[5] == 4);
1795
1796 const items = [_]i32{1};
1797 try list.insertSlice(a, 0, items[0..0]);
1798 try testing.expect(list.items.len == 6);
1799 try testing.expect(list.items[0] == 1);
1800 }
1801}
1802
1803test "Managed.replaceRange" {
1804 const a = testing.allocator;
1805
1806 {
1807 var list = Managed(i32).init(a);
1808 defer list.deinit();
1809 try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
1810
1811 try list.replaceRange(1, 0, &[_]i32{ 0, 0, 0 });
1812
1813 try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 2, 3, 4, 5 }, list.items);
1814 }
1815 {
1816 var list = Managed(i32).init(a);
1817 defer list.deinit();
1818 try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
1819
1820 try list.replaceRange(1, 1, &[_]i32{ 0, 0, 0 });
1821
1822 try testing.expectEqualSlices(
1823 i32,
1824 &[_]i32{ 1, 0, 0, 0, 3, 4, 5 },
1825 list.items,
1826 );
1827 }
1828 {
1829 var list = Managed(i32).init(a);
1830 defer list.deinit();
1831 try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
1832
1833 try list.replaceRange(1, 2, &[_]i32{ 0, 0, 0 });
1834
1835 try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 4, 5 }, list.items);
1836 }
1837 {
1838 var list = Managed(i32).init(a);
1839 defer list.deinit();
1840 try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
1841
1842 try list.replaceRange(1, 3, &[_]i32{ 0, 0, 0 });
1843
1844 try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 5 }, list.items);
1845 }
1846 {
1847 var list = Managed(i32).init(a);
1848 defer list.deinit();
1849 try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
1850
1851 try list.replaceRange(1, 4, &[_]i32{ 0, 0, 0 });
1852
1853 try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0 }, list.items);
1854 }
1855}
1856
1857test "Managed.replaceRangeAssumeCapacity" {
1858 const a = testing.allocator;
1859
1860 {
1861 var list = Managed(i32).init(a);
1862 defer list.deinit();
1863 try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
1864
1865 list.replaceRangeAssumeCapacity(1, 0, &[_]i32{ 0, 0, 0 });
1866
1867 try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 2, 3, 4, 5 }, list.items);
1868 }
1869 {
1870 var list = Managed(i32).init(a);
1871 defer list.deinit();
1872 try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
1873
1874 list.replaceRangeAssumeCapacity(1, 1, &[_]i32{ 0, 0, 0 });
1875
1876 try testing.expectEqualSlices(
1877 i32,
1878 &[_]i32{ 1, 0, 0, 0, 3, 4, 5 },
1879 list.items,
1880 );
1881 }
1882 {
1883 var list = Managed(i32).init(a);
1884 defer list.deinit();
1885 try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
1886
1887 list.replaceRangeAssumeCapacity(1, 2, &[_]i32{ 0, 0, 0 });
1888
1889 try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 4, 5 }, list.items);
1890 }
1891 {
1892 var list = Managed(i32).init(a);
1893 defer list.deinit();
1894 try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
1895
1896 list.replaceRangeAssumeCapacity(1, 3, &[_]i32{ 0, 0, 0 });
1897
1898 try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 5 }, list.items);
1899 }
1900 {
1901 var list = Managed(i32).init(a);
1902 defer list.deinit();
1903 try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
1904
1905 list.replaceRangeAssumeCapacity(1, 4, &[_]i32{ 0, 0, 0 });
1906
1907 try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0 }, list.items);
1908 }
1909}
1910
1911test "ArrayList.replaceRange" {
1912 const a = testing.allocator;
1913
1914 {
1915 var list: ArrayList(i32) = .empty;
1916 defer list.deinit(a);
1917 try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
1918
1919 try list.replaceRange(a, 1, 0, &[_]i32{ 0, 0, 0 });
1920
1921 try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 2, 3, 4, 5 }, list.items);
1922 }
1923 {
1924 var list: ArrayList(i32) = .empty;
1925 defer list.deinit(a);
1926 try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
1927
1928 try list.replaceRange(a, 1, 1, &[_]i32{ 0, 0, 0 });
1929
1930 try testing.expectEqualSlices(
1931 i32,
1932 &[_]i32{ 1, 0, 0, 0, 3, 4, 5 },
1933 list.items,
1934 );
1935 }
1936 {
1937 var list: ArrayList(i32) = .empty;
1938 defer list.deinit(a);
1939 try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
1940
1941 try list.replaceRange(a, 1, 2, &[_]i32{ 0, 0, 0 });
1942
1943 try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 4, 5 }, list.items);
1944 }
1945 {
1946 var list: ArrayList(i32) = .empty;
1947 defer list.deinit(a);
1948 try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
1949
1950 try list.replaceRange(a, 1, 3, &[_]i32{ 0, 0, 0 });
1951
1952 try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 5 }, list.items);
1953 }
1954 {
1955 var list: ArrayList(i32) = .empty;
1956 defer list.deinit(a);
1957 try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
1958
1959 try list.replaceRange(a, 1, 4, &[_]i32{ 0, 0, 0 });
1960
1961 try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0 }, list.items);
1962 }
1963}
1964
1965test "ArrayList.replaceRangeAssumeCapacity" {
1966 const a = testing.allocator;
1967
1968 {
1969 var list: ArrayList(i32) = .empty;
1970 defer list.deinit(a);
1971 try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
1972
1973 list.replaceRangeAssumeCapacity(1, 0, &[_]i32{ 0, 0, 0 });
1974
1975 try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 2, 3, 4, 5 }, list.items);
1976 }
1977 {
1978 var list: ArrayList(i32) = .empty;
1979 defer list.deinit(a);
1980 try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
1981
1982 list.replaceRangeAssumeCapacity(1, 1, &[_]i32{ 0, 0, 0 });
1983
1984 try testing.expectEqualSlices(
1985 i32,
1986 &[_]i32{ 1, 0, 0, 0, 3, 4, 5 },
1987 list.items,
1988 );
1989 }
1990 {
1991 var list: ArrayList(i32) = .empty;
1992 defer list.deinit(a);
1993 try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
1994
1995 list.replaceRangeAssumeCapacity(1, 2, &[_]i32{ 0, 0, 0 });
1996
1997 try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 4, 5 }, list.items);
1998 }
1999 {
2000 var list: ArrayList(i32) = .empty;
2001 defer list.deinit(a);
2002 try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
2003
2004 list.replaceRangeAssumeCapacity(1, 3, &[_]i32{ 0, 0, 0 });
2005
2006 try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 5 }, list.items);
2007 }
2008 {
2009 var list: ArrayList(i32) = .empty;
2010 defer list.deinit(a);
2011 try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
2012
2013 list.replaceRangeAssumeCapacity(1, 4, &[_]i32{ 0, 0, 0 });
2014
2015 try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0 }, list.items);
2016 }
2017}
2018
2019const Item = struct {
2020 integer: i32,
2021 sub_items: Managed(Item),
2022};
2023
2024const ItemUnmanaged = struct {
2025 integer: i32,
2026 sub_items: ArrayList(ItemUnmanaged),
2027};
2028
2029test "Managed(T) of struct T" {
2030 const a = std.testing.allocator;
2031 {
2032 var root = Item{ .integer = 1, .sub_items = .init(a) };
2033 defer root.sub_items.deinit();
2034 try root.sub_items.append(Item{ .integer = 42, .sub_items = .init(a) });
2035 try testing.expect(root.sub_items.items[0].integer == 42);
2036 }
2037 {
2038 var root = ItemUnmanaged{ .integer = 1, .sub_items = .empty };
2039 defer root.sub_items.deinit(a);
2040 try root.sub_items.append(a, ItemUnmanaged{ .integer = 42, .sub_items = .empty });
2041 try testing.expect(root.sub_items.items[0].integer == 42);
2042 }
2043}
2044
2045test "shrink still sets length when resizing is disabled" {
2046 var failing_allocator = testing.FailingAllocator.init(testing.allocator, .{ .resize_fail_index = 0 });
2047 const a = failing_allocator.allocator();
2048
2049 {
2050 var list = Managed(i32).init(a);
2051 defer list.deinit();
2052
2053 try list.append(1);
2054 try list.append(2);
2055 try list.append(3);
2056
2057 list.shrinkAndFree(1);
2058 try testing.expect(list.items.len == 1);
2059 }
2060 {
2061 var list: ArrayList(i32) = .empty;
2062 defer list.deinit(a);
2063
2064 try list.append(a, 1);
2065 try list.append(a, 2);
2066 try list.append(a, 3);
2067
2068 list.shrinkAndFree(a, 1);
2069 try testing.expect(list.items.len == 1);
2070 }
2071}
2072
2073test "shrinkAndFree with a copy" {
2074 var failing_allocator = testing.FailingAllocator.init(testing.allocator, .{ .resize_fail_index = 0 });
2075 const a = failing_allocator.allocator();
2076
2077 var list = Managed(i32).init(a);
2078 defer list.deinit();
2079
2080 try list.appendNTimes(3, 16);
2081 list.shrinkAndFree(4);
2082 try testing.expect(mem.eql(i32, list.items, &.{ 3, 3, 3, 3 }));
2083}
2084
2085test "addManyAsArray" {
2086 const a = std.testing.allocator;
2087 {
2088 var list = Managed(u8).init(a);
2089 defer list.deinit();
2090
2091 (try list.addManyAsArray(4)).* = "aoeu".*;
2092 try list.ensureTotalCapacity(8);
2093 list.addManyAsArrayAssumeCapacity(4).* = "asdf".*;
2094
2095 try testing.expectEqualSlices(u8, list.items, "aoeuasdf");
2096 }
2097 {
2098 var list: ArrayList(u8) = .empty;
2099 defer list.deinit(a);
2100
2101 (try list.addManyAsArray(a, 4)).* = "aoeu".*;
2102 try list.ensureTotalCapacity(a, 8);
2103 list.addManyAsArrayAssumeCapacity(4).* = "asdf".*;
2104
2105 try testing.expectEqualSlices(u8, list.items, "aoeuasdf");
2106 }
2107}
2108
2109test "growing memory preserves contents" {
2110 // Shrink the list after every insertion to ensure that a memory growth
2111 // will be triggered in the next operation.
2112 const a = std.testing.allocator;
2113 {
2114 var list = Managed(u8).init(a);
2115 defer list.deinit();
2116
2117 (try list.addManyAsArray(4)).* = "abcd".*;
2118 list.shrinkAndFree(4);
2119
2120 try list.appendSlice("efgh");
2121 try testing.expectEqualSlices(u8, list.items, "abcdefgh");
2122 list.shrinkAndFree(8);
2123
2124 try list.insertSlice(4, "ijkl");
2125 try testing.expectEqualSlices(u8, list.items, "abcdijklefgh");
2126 }
2127 {
2128 var list: ArrayList(u8) = .empty;
2129 defer list.deinit(a);
2130
2131 (try list.addManyAsArray(a, 4)).* = "abcd".*;
2132 list.shrinkAndFree(a, 4);
2133
2134 try list.appendSlice(a, "efgh");
2135 try testing.expectEqualSlices(u8, list.items, "abcdefgh");
2136 list.shrinkAndFree(a, 8);
2137
2138 try list.insertSlice(a, 4, "ijkl");
2139 try testing.expectEqualSlices(u8, list.items, "abcdijklefgh");
2140 }
2141}
2142
2143test "fromOwnedSlice" {
2144 const a = testing.allocator;
2145 {
2146 var orig_list = Managed(u8).init(a);
2147 defer orig_list.deinit();
2148 try orig_list.appendSlice("foobar");
2149
2150 const slice = try orig_list.toOwnedSlice();
2151 var list = Managed(u8).fromOwnedSlice(a, slice);
2152 defer list.deinit();
2153 try testing.expectEqualStrings(list.items, "foobar");
2154 }
2155 {
2156 var list = Managed(u8).init(a);
2157 defer list.deinit();
2158 try list.appendSlice("foobar");
2159
2160 const slice = try list.toOwnedSlice();
2161 var unmanaged = ArrayList(u8).fromOwnedSlice(slice);
2162 defer unmanaged.deinit(a);
2163 try testing.expectEqualStrings(unmanaged.items, "foobar");
2164 }
2165}
2166
2167test "fromOwnedSliceSentinel" {
2168 const a = testing.allocator;
2169 {
2170 var orig_list = Managed(u8).init(a);
2171 defer orig_list.deinit();
2172 try orig_list.appendSlice("foobar");
2173
2174 const sentinel_slice = try orig_list.toOwnedSliceSentinel(0);
2175 var list = Managed(u8).fromOwnedSliceSentinel(a, 0, sentinel_slice);
2176 defer list.deinit();
2177 try testing.expectEqualStrings(list.items, "foobar");
2178 }
2179 {
2180 var list = Managed(u8).init(a);
2181 defer list.deinit();
2182 try list.appendSlice("foobar");
2183
2184 const sentinel_slice = try list.toOwnedSliceSentinel(0);
2185 var unmanaged = ArrayList(u8).fromOwnedSliceSentinel(0, sentinel_slice);
2186 defer unmanaged.deinit(a);
2187 try testing.expectEqualStrings(unmanaged.items, "foobar");
2188 }
2189}
2190
2191test "toOwnedSliceSentinel" {
2192 const a = testing.allocator;
2193 {
2194 var list = Managed(u8).init(a);
2195 defer list.deinit();
2196
2197 try list.appendSlice("foobar");
2198
2199 const result = try list.toOwnedSliceSentinel(0);
2200 defer a.free(result);
2201 try testing.expectEqualStrings(result, mem.sliceTo(result.ptr, 0));
2202 }
2203 {
2204 var list: ArrayList(u8) = .empty;
2205 defer list.deinit(a);
2206
2207 try list.appendSlice(a, "foobar");
2208
2209 const result = try list.toOwnedSliceSentinel(a, 0);
2210 defer a.free(result);
2211 try testing.expectEqualStrings(result, mem.sliceTo(result.ptr, 0));
2212 }
2213}
2214
2215test "accepts unaligned slices" {
2216 const a = testing.allocator;
2217 {
2218 var list = AlignedManaged(u8, .@"8").init(a);
2219 defer list.deinit();
2220
2221 try list.appendSlice(&.{ 0, 1, 2, 3 });
2222 try list.insertSlice(2, &.{ 4, 5, 6, 7 });
2223 try list.replaceRange(1, 3, &.{ 8, 9 });
2224
2225 try testing.expectEqualSlices(u8, list.items, &.{ 0, 8, 9, 6, 7, 2, 3 });
2226 }
2227 {
2228 var list: Aligned(u8, .@"8") = .empty;
2229 defer list.deinit(a);
2230
2231 try list.appendSlice(a, &.{ 0, 1, 2, 3 });
2232 try list.insertSlice(a, 2, &.{ 4, 5, 6, 7 });
2233 try list.replaceRange(a, 1, 3, &.{ 8, 9 });
2234
2235 try testing.expectEqualSlices(u8, list.items, &.{ 0, 8, 9, 6, 7, 2, 3 });
2236 }
2237}
2238
2239test "Managed(u0)" {
2240 // An Managed on zero-sized types should not need to allocate
2241 const a = testing.failing_allocator;
2242
2243 var list = Managed(u0).init(a);
2244 defer list.deinit();
2245
2246 try list.append(0);
2247 try list.append(0);
2248 try list.append(0);
2249 try testing.expectEqual(list.items.len, 3);
2250
2251 var count: usize = 0;
2252 for (list.items) |x| {
2253 try testing.expectEqual(x, 0);
2254 count += 1;
2255 }
2256 try testing.expectEqual(count, 3);
2257}
2258
2259test "Managed(?u32).pop()" {
2260 const a = testing.allocator;
2261
2262 var list = Managed(?u32).init(a);
2263 defer list.deinit();
2264
2265 try list.append(null);
2266 try list.append(1);
2267 try list.append(2);
2268 try testing.expectEqual(list.items.len, 3);
2269
2270 try testing.expect(list.pop().? == @as(u32, 2));
2271 try testing.expect(list.pop().? == @as(u32, 1));
2272 try testing.expect(list.pop().? == null);
2273 try testing.expect(list.pop() == null);
2274}
2275
2276test "Managed(u32).getLast()" {
2277 const a = testing.allocator;
2278
2279 var list = Managed(u32).init(a);
2280 defer list.deinit();
2281
2282 try list.append(2);
2283 const const_list = list;
2284 try testing.expectEqual(const_list.getLast(), 2);
2285}
2286
2287test "Managed(u32).getLastOrNull()" {
2288 const a = testing.allocator;
2289
2290 var list = Managed(u32).init(a);
2291 defer list.deinit();
2292
2293 try testing.expectEqual(list.getLastOrNull(), null);
2294
2295 try list.append(2);
2296 const const_list = list;
2297 try testing.expectEqual(const_list.getLastOrNull().?, 2);
2298}
2299
2300test "return OutOfMemory when capacity would exceed maximum usize integer value" {
2301 const a = testing.allocator;
2302 const new_item: u32 = 42;
2303 const items = &.{ 42, 43 };
2304
2305 {
2306 var list: ArrayList(u32) = .{
2307 .items = undefined,
2308 .capacity = math.maxInt(usize) - 1,
2309 };
2310 list.items.len = math.maxInt(usize) - 1;
2311
2312 try testing.expectError(error.OutOfMemory, list.appendSlice(a, items));
2313 try testing.expectError(error.OutOfMemory, list.appendNTimes(a, new_item, 2));
2314 try testing.expectError(error.OutOfMemory, list.appendUnalignedSlice(a, &.{ new_item, new_item }));
2315 try testing.expectError(error.OutOfMemory, list.addManyAt(a, 0, 2));
2316 try testing.expectError(error.OutOfMemory, list.addManyAsArray(a, 2));
2317 try testing.expectError(error.OutOfMemory, list.addManyAsSlice(a, 2));
2318 try testing.expectError(error.OutOfMemory, list.insertSlice(a, 0, items));
2319 try testing.expectError(error.OutOfMemory, list.ensureUnusedCapacity(a, 2));
2320 }
2321
2322 {
2323 var list: Managed(u32) = .{
2324 .items = undefined,
2325 .capacity = math.maxInt(usize) - 1,
2326 .allocator = a,
2327 };
2328 list.items.len = math.maxInt(usize) - 1;
2329
2330 try testing.expectError(error.OutOfMemory, list.appendSlice(items));
2331 try testing.expectError(error.OutOfMemory, list.appendNTimes(new_item, 2));
2332 try testing.expectError(error.OutOfMemory, list.appendUnalignedSlice(&.{ new_item, new_item }));
2333 try testing.expectError(error.OutOfMemory, list.addManyAt(0, 2));
2334 try testing.expectError(error.OutOfMemory, list.addManyAsArray(2));
2335 try testing.expectError(error.OutOfMemory, list.addManyAsSlice(2));
2336 try testing.expectError(error.OutOfMemory, list.insertSlice(0, items));
2337 try testing.expectError(error.OutOfMemory, list.ensureUnusedCapacity(2));
2338 }
2339}
2340
2341test "orderedRemoveMany" {
2342 const gpa = testing.allocator;
2343
2344 var list: Aligned(usize, null) = .empty;
2345 defer list.deinit(gpa);
2346
2347 for (0..10) |n| {
2348 try list.append(gpa, n);
2349 }
2350
2351 list.orderedRemoveMany(&.{ 1, 5, 5, 7, 9 });
2352 try testing.expectEqualSlices(usize, &.{ 0, 2, 3, 4, 6, 8 }, list.items);
2353
2354 list.orderedRemoveMany(&.{0});
2355 try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, list.items);
2356
2357 list.orderedRemoveMany(&.{});
2358 try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, list.items);
2359
2360 list.orderedRemoveMany(&.{ 1, 2, 3, 4 });
2361 try testing.expectEqualSlices(usize, &.{2}, list.items);
2362
2363 list.orderedRemoveMany(&.{0});
2364 try testing.expectEqualSlices(usize, &.{}, list.items);
2365}
2366
2367test "insertSlice*" {
2368 var buf: [10]u8 = undefined;
2369 var list: ArrayList(u8) = .initBuffer(&buf);
2370
2371 list.appendSliceAssumeCapacity("abcd");
2372
2373 list.insertSliceAssumeCapacity(2, "ef");
2374 try testing.expectEqualStrings("abefcd", list.items);
2375
2376 try list.insertSliceBounded(4, "gh");
2377 try testing.expectEqualStrings("abefghcd", list.items);
2378
2379 try testing.expectError(error.OutOfMemory, list.insertSliceBounded(6, "ijkl"));
2380 try testing.expectEqualStrings("abefghcd", list.items); // ensure no elements were changed before the return of error.OutOfMemory
2381
2382 list.insertSliceAssumeCapacity(6, "ij");
2383 try testing.expectEqualStrings("abefghijcd", list.items);
2384}