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