1 //! Small lists of entity references.
2 use crate::packed_option::ReservedValue;
3 use crate::EntityRef;
4 use alloc::vec::Vec;
5 use core::marker::PhantomData;
6 use core::mem;
7
8 #[cfg(feature = "enable-serde")]
9 use serde::{Deserialize, Serialize};
10
11 /// A small list of entity references allocated from a pool.
12 ///
13 /// An `EntityList<T>` type provides similar functionality to `Vec<T>`, but with some important
14 /// differences in the implementation:
15 ///
16 /// 1. Memory is allocated from a `ListPool<T>` instead of the global heap.
17 /// 2. The footprint of an entity list is 4 bytes, compared with the 24 bytes for `Vec<T>`.
18 /// 3. An entity list doesn't implement `Drop`, leaving it to the pool to manage memory.
19 ///
20 /// The list pool is intended to be used as a LIFO allocator. After building up a larger data
21 /// structure with many list references, the whole thing can be discarded quickly by clearing the
22 /// pool.
23 ///
24 /// # Safety
25 ///
26 /// Entity lists are not as safe to use as `Vec<T>`, but they never jeopardize Rust's memory safety
27 /// guarantees. These are the problems to be aware of:
28 ///
29 /// - If you lose track of an entity list, its memory won't be recycled until the pool is cleared.
30 /// This can cause the pool to grow very large with leaked lists.
31 /// - If entity lists are used after their pool is cleared, they may contain garbage data, and
32 /// modifying them may corrupt other lists in the pool.
33 /// - If an entity list is used with two different pool instances, both pools are likely to become
34 /// corrupted.
35 ///
36 /// Entity lists can be cloned, but that operation should only be used as part of cloning the whole
37 /// function they belong to. *Cloning an entity list does not allocate new memory for the clone*.
38 /// It creates an alias of the same memory.
39 ///
40 /// Entity lists cannot be hashed and compared for equality because it's not possible to compare the
41 /// contents of the list without the pool reference.
42 ///
43 /// # Implementation
44 ///
45 /// The `EntityList` itself is designed to have the smallest possible footprint. This is important
46 /// because it is used inside very compact data structures like `InstructionData`. The list
47 /// contains only a 32-bit index into the pool's memory vector, pointing to the first element of
48 /// the list.
49 ///
50 /// The pool is just a single `Vec<T>` containing all of the allocated lists. Each list is
51 /// represented as three contiguous parts:
52 ///
53 /// 1. The number of elements in the list.
54 /// 2. The list elements.
55 /// 3. Excess capacity elements.
56 ///
57 /// The total size of the three parts is always a power of two, and the excess capacity is always
58 /// as small as possible. This means that shrinking a list may cause the excess capacity to shrink
59 /// if a smaller power-of-two size becomes available.
60 ///
61 /// Both growing and shrinking a list may cause it to be reallocated in the pool vector.
62 ///
63 /// The index stored in an `EntityList` points to part 2, the list elements. The value 0 is
64 /// reserved for the empty list which isn't allocated in the vector.
65 #[derive(Clone, Debug, PartialEq)]
66 #[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
67 pub struct EntityList<T: EntityRef + ReservedValue> {
68 index: u32,
69 unused: PhantomData<T>,
70 }
71
72 /// Create an empty list.
73 impl<T: EntityRef + ReservedValue> Default for EntityList<T> {
default() -> Self74 fn default() -> Self {
75 Self {
76 index: 0,
77 unused: PhantomData,
78 }
79 }
80 }
81
82 /// A memory pool for storing lists of `T`.
83 #[derive(Clone, Debug)]
84 #[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
85 pub struct ListPool<T: EntityRef + ReservedValue> {
86 // The main array containing the lists.
87 data: Vec<T>,
88
89 // Heads of the free lists, one for each size class.
90 free: Vec<usize>,
91 }
92
93 /// Lists are allocated in sizes that are powers of two, starting from 4.
94 /// Each power of two is assigned a size class number, so the size is `4 << SizeClass`.
95 type SizeClass = u8;
96
97 /// Get the size of a given size class. The size includes the length field, so the maximum list
98 /// length is one less than the class size.
99 #[inline]
sclass_size(sclass: SizeClass) -> usize100 fn sclass_size(sclass: SizeClass) -> usize {
101 4 << sclass
102 }
103
104 /// Get the size class to use for a given list length.
105 /// This always leaves room for the length element in addition to the list elements.
106 #[inline]
sclass_for_length(len: usize) -> SizeClass107 fn sclass_for_length(len: usize) -> SizeClass {
108 30 - (len as u32 | 3).leading_zeros() as SizeClass
109 }
110
111 /// Is `len` the minimum length in its size class?
112 #[inline]
is_sclass_min_length(len: usize) -> bool113 fn is_sclass_min_length(len: usize) -> bool {
114 len > 3 && len.is_power_of_two()
115 }
116
117 impl<T: EntityRef + ReservedValue> ListPool<T> {
118 /// Create a new list pool.
new() -> Self119 pub fn new() -> Self {
120 Self {
121 data: Vec::new(),
122 free: Vec::new(),
123 }
124 }
125
126 /// Clear the pool, forgetting about all lists that use it.
127 ///
128 /// This invalidates any existing entity lists that used this pool to allocate memory.
129 ///
130 /// The pool's memory is not released to the operating system, but kept around for faster
131 /// allocation in the future.
clear(&mut self)132 pub fn clear(&mut self) {
133 self.data.clear();
134 self.free.clear();
135 }
136
137 /// Read the length of a list field, if it exists.
len_of(&self, list: &EntityList<T>) -> Option<usize>138 fn len_of(&self, list: &EntityList<T>) -> Option<usize> {
139 let idx = list.index as usize;
140 // `idx` points at the list elements. The list length is encoded in the element immediately
141 // before the list elements.
142 //
143 // The `wrapping_sub` handles the special case 0, which is the empty list. This way, the
144 // cost of the bounds check that we have to pay anyway is co-opted to handle the special
145 // case of the empty list.
146 self.data.get(idx.wrapping_sub(1)).map(|len| len.index())
147 }
148
149 /// Allocate a storage block with a size given by `sclass`.
150 ///
151 /// Returns the first index of an available segment of `self.data` containing
152 /// `sclass_size(sclass)` elements. The allocated memory is filled with reserved
153 /// values.
alloc(&mut self, sclass: SizeClass) -> usize154 fn alloc(&mut self, sclass: SizeClass) -> usize {
155 // First try the free list for this size class.
156 match self.free.get(sclass as usize).cloned() {
157 Some(head) if head > 0 => {
158 // The free list pointers are offset by 1, using 0 to terminate the list.
159 // A block on the free list has two entries: `[ 0, next ]`.
160 // The 0 is where the length field would be stored for a block in use.
161 // The free list heads and the next pointer point at the `next` field.
162 self.free[sclass as usize] = self.data[head].index();
163 head - 1
164 }
165 _ => {
166 // Nothing on the free list. Allocate more memory.
167 let offset = self.data.len();
168 self.data
169 .resize(offset + sclass_size(sclass), T::reserved_value());
170 offset
171 }
172 }
173 }
174
175 /// Free a storage block with a size given by `sclass`.
176 ///
177 /// This must be a block that was previously allocated by `alloc()` with the same size class.
free(&mut self, block: usize, sclass: SizeClass)178 fn free(&mut self, block: usize, sclass: SizeClass) {
179 let sclass = sclass as usize;
180
181 // Make sure we have a free-list head for `sclass`.
182 if self.free.len() <= sclass {
183 self.free.resize(sclass + 1, 0);
184 }
185
186 // Make sure the length field is cleared.
187 self.data[block] = T::new(0);
188 // Insert the block on the free list which is a single linked list.
189 self.data[block + 1] = T::new(self.free[sclass]);
190 self.free[sclass] = block + 1
191 }
192
193 /// Returns two mutable slices representing the two requested blocks.
194 ///
195 /// The two returned slices can be longer than the blocks. Each block is located at the front
196 /// of the respective slice.
mut_slices(&mut self, block0: usize, block1: usize) -> (&mut [T], &mut [T])197 fn mut_slices(&mut self, block0: usize, block1: usize) -> (&mut [T], &mut [T]) {
198 if block0 < block1 {
199 let (s0, s1) = self.data.split_at_mut(block1);
200 (&mut s0[block0..], s1)
201 } else {
202 let (s1, s0) = self.data.split_at_mut(block0);
203 (s0, &mut s1[block1..])
204 }
205 }
206
207 /// Reallocate a block to a different size class.
208 ///
209 /// Copy `elems_to_copy` elements from the old to the new block.
realloc( &mut self, block: usize, from_sclass: SizeClass, to_sclass: SizeClass, elems_to_copy: usize, ) -> usize210 fn realloc(
211 &mut self,
212 block: usize,
213 from_sclass: SizeClass,
214 to_sclass: SizeClass,
215 elems_to_copy: usize,
216 ) -> usize {
217 debug_assert!(elems_to_copy <= sclass_size(from_sclass));
218 debug_assert!(elems_to_copy <= sclass_size(to_sclass));
219 let new_block = self.alloc(to_sclass);
220
221 if elems_to_copy > 0 {
222 let (old, new) = self.mut_slices(block, new_block);
223 (&mut new[0..elems_to_copy]).copy_from_slice(&old[0..elems_to_copy]);
224 }
225
226 self.free(block, from_sclass);
227 new_block
228 }
229 }
230
231 impl<T: EntityRef + ReservedValue> EntityList<T> {
232 /// Create a new empty list.
new() -> Self233 pub fn new() -> Self {
234 Default::default()
235 }
236
237 /// Create a new list with the contents initialized from a slice.
from_slice(slice: &[T], pool: &mut ListPool<T>) -> Self238 pub fn from_slice(slice: &[T], pool: &mut ListPool<T>) -> Self {
239 let len = slice.len();
240 if len == 0 {
241 return Self::new();
242 }
243
244 let block = pool.alloc(sclass_for_length(len));
245 pool.data[block] = T::new(len);
246 pool.data[block + 1..=block + len].copy_from_slice(slice);
247
248 Self {
249 index: (block + 1) as u32,
250 unused: PhantomData,
251 }
252 }
253
254 /// Returns `true` if the list has a length of 0.
is_empty(&self) -> bool255 pub fn is_empty(&self) -> bool {
256 // 0 is a magic value for the empty list. Any list in the pool array must have a positive
257 // length.
258 self.index == 0
259 }
260
261 /// Get the number of elements in the list.
len(&self, pool: &ListPool<T>) -> usize262 pub fn len(&self, pool: &ListPool<T>) -> usize {
263 // Both the empty list and any invalidated old lists will return `None`.
264 pool.len_of(self).unwrap_or(0)
265 }
266
267 /// Returns `true` if the list is valid
is_valid(&self, pool: &ListPool<T>) -> bool268 pub fn is_valid(&self, pool: &ListPool<T>) -> bool {
269 // We consider an empty list to be valid
270 self.is_empty() || pool.len_of(self) != None
271 }
272
273 /// Get the list as a slice.
as_slice<'a>(&'a self, pool: &'a ListPool<T>) -> &'a [T]274 pub fn as_slice<'a>(&'a self, pool: &'a ListPool<T>) -> &'a [T] {
275 let idx = self.index as usize;
276 match pool.len_of(self) {
277 None => &[],
278 Some(len) => &pool.data[idx..idx + len],
279 }
280 }
281
282 /// Get a single element from the list.
get(&self, index: usize, pool: &ListPool<T>) -> Option<T>283 pub fn get(&self, index: usize, pool: &ListPool<T>) -> Option<T> {
284 self.as_slice(pool).get(index).cloned()
285 }
286
287 /// Get the first element from the list.
first(&self, pool: &ListPool<T>) -> Option<T>288 pub fn first(&self, pool: &ListPool<T>) -> Option<T> {
289 if self.is_empty() {
290 None
291 } else {
292 Some(pool.data[self.index as usize])
293 }
294 }
295
296 /// Get the list as a mutable slice.
as_mut_slice<'a>(&'a mut self, pool: &'a mut ListPool<T>) -> &'a mut [T]297 pub fn as_mut_slice<'a>(&'a mut self, pool: &'a mut ListPool<T>) -> &'a mut [T] {
298 let idx = self.index as usize;
299 match pool.len_of(self) {
300 None => &mut [],
301 Some(len) => &mut pool.data[idx..idx + len],
302 }
303 }
304
305 /// Get a mutable reference to a single element from the list.
get_mut<'a>(&'a mut self, index: usize, pool: &'a mut ListPool<T>) -> Option<&'a mut T>306 pub fn get_mut<'a>(&'a mut self, index: usize, pool: &'a mut ListPool<T>) -> Option<&'a mut T> {
307 self.as_mut_slice(pool).get_mut(index)
308 }
309
310 /// Create a deep clone of the list, which does not alias the original list.
deep_clone(&self, pool: &mut ListPool<T>) -> Self311 pub fn deep_clone(&self, pool: &mut ListPool<T>) -> Self {
312 match pool.len_of(self) {
313 None => return Self::new(),
314 Some(len) => {
315 let src = self.index as usize;
316 let block = pool.alloc(sclass_for_length(len));
317 pool.data[block] = T::new(len);
318 pool.data.copy_within(src..src + len, block + 1);
319
320 Self {
321 index: (block + 1) as u32,
322 unused: PhantomData,
323 }
324 }
325 }
326 }
327
328 /// Removes all elements from the list.
329 ///
330 /// The memory used by the list is put back in the pool.
clear(&mut self, pool: &mut ListPool<T>)331 pub fn clear(&mut self, pool: &mut ListPool<T>) {
332 let idx = self.index as usize;
333 match pool.len_of(self) {
334 None => debug_assert_eq!(idx, 0, "Invalid pool"),
335 Some(len) => pool.free(idx - 1, sclass_for_length(len)),
336 }
337 // Switch back to the empty list representation which has no storage.
338 self.index = 0;
339 }
340
341 /// Take all elements from this list and return them as a new list. Leave this list empty.
342 ///
343 /// This is the equivalent of `Option::take()`.
take(&mut self) -> Self344 pub fn take(&mut self) -> Self {
345 mem::replace(self, Default::default())
346 }
347
348 /// Appends an element to the back of the list.
349 /// Returns the index where the element was inserted.
push(&mut self, element: T, pool: &mut ListPool<T>) -> usize350 pub fn push(&mut self, element: T, pool: &mut ListPool<T>) -> usize {
351 let idx = self.index as usize;
352 match pool.len_of(self) {
353 None => {
354 // This is an empty list. Allocate a block and set length=1.
355 debug_assert_eq!(idx, 0, "Invalid pool");
356 let block = pool.alloc(sclass_for_length(1));
357 pool.data[block] = T::new(1);
358 pool.data[block + 1] = element;
359 self.index = (block + 1) as u32;
360 0
361 }
362 Some(len) => {
363 // Do we need to reallocate?
364 let new_len = len + 1;
365 let block;
366 if is_sclass_min_length(new_len) {
367 // Reallocate, preserving length + all old elements.
368 let sclass = sclass_for_length(len);
369 block = pool.realloc(idx - 1, sclass, sclass + 1, len + 1);
370 self.index = (block + 1) as u32;
371 } else {
372 block = idx - 1;
373 }
374 pool.data[block + new_len] = element;
375 pool.data[block] = T::new(new_len);
376 len
377 }
378 }
379 }
380
381 /// Grow list by adding `count` reserved-value elements at the end.
382 ///
383 /// Returns a mutable slice representing the whole list.
grow<'a>(&'a mut self, count: usize, pool: &'a mut ListPool<T>) -> &'a mut [T]384 fn grow<'a>(&'a mut self, count: usize, pool: &'a mut ListPool<T>) -> &'a mut [T] {
385 let idx = self.index as usize;
386 let new_len;
387 let block;
388 match pool.len_of(self) {
389 None => {
390 // This is an empty list. Allocate a block.
391 debug_assert_eq!(idx, 0, "Invalid pool");
392 if count == 0 {
393 return &mut [];
394 }
395 new_len = count;
396 block = pool.alloc(sclass_for_length(new_len));
397 self.index = (block + 1) as u32;
398 }
399 Some(len) => {
400 // Do we need to reallocate?
401 let sclass = sclass_for_length(len);
402 new_len = len + count;
403 let new_sclass = sclass_for_length(new_len);
404 if new_sclass != sclass {
405 block = pool.realloc(idx - 1, sclass, new_sclass, len + 1);
406 self.index = (block + 1) as u32;
407 } else {
408 block = idx - 1;
409 }
410 }
411 }
412 pool.data[block] = T::new(new_len);
413 &mut pool.data[block + 1..block + 1 + new_len]
414 }
415
416 /// Constructs a list from an iterator.
from_iter<I>(elements: I, pool: &mut ListPool<T>) -> Self where I: IntoIterator<Item = T>,417 pub fn from_iter<I>(elements: I, pool: &mut ListPool<T>) -> Self
418 where
419 I: IntoIterator<Item = T>,
420 {
421 let mut list = Self::new();
422 list.extend(elements, pool);
423 list
424 }
425
426 /// Appends multiple elements to the back of the list.
extend<I>(&mut self, elements: I, pool: &mut ListPool<T>) where I: IntoIterator<Item = T>,427 pub fn extend<I>(&mut self, elements: I, pool: &mut ListPool<T>)
428 where
429 I: IntoIterator<Item = T>,
430 {
431 let iterator = elements.into_iter();
432 let (len, upper) = iterator.size_hint();
433 // On most iterators this check is optimized down to `true`.
434 if upper == Some(len) {
435 let data = self.grow(len, pool);
436 let offset = data.len() - len;
437 for (src, dst) in iterator.zip(data[offset..].iter_mut()) {
438 *dst = src;
439 }
440 } else {
441 for x in iterator {
442 self.push(x, pool);
443 }
444 }
445 }
446
447 /// Inserts an element as position `index` in the list, shifting all elements after it to the
448 /// right.
insert(&mut self, index: usize, element: T, pool: &mut ListPool<T>)449 pub fn insert(&mut self, index: usize, element: T, pool: &mut ListPool<T>) {
450 // Increase size by 1.
451 self.push(element, pool);
452
453 // Move tail elements.
454 let seq = self.as_mut_slice(pool);
455 if index < seq.len() {
456 let tail = &mut seq[index..];
457 for i in (1..tail.len()).rev() {
458 tail[i] = tail[i - 1];
459 }
460 tail[0] = element;
461 } else {
462 debug_assert_eq!(index, seq.len());
463 }
464 }
465
466 /// Removes the last element from the list.
remove_last(&mut self, len: usize, pool: &mut ListPool<T>)467 fn remove_last(&mut self, len: usize, pool: &mut ListPool<T>) {
468 // Check if we deleted the last element.
469 if len == 1 {
470 self.clear(pool);
471 return;
472 }
473
474 // Do we need to reallocate to a smaller size class?
475 let mut block = self.index as usize - 1;
476 if is_sclass_min_length(len) {
477 let sclass = sclass_for_length(len);
478 block = pool.realloc(block, sclass, sclass - 1, len);
479 self.index = (block + 1) as u32;
480 }
481
482 // Finally adjust the length.
483 pool.data[block] = T::new(len - 1);
484 }
485
486 /// Removes the element at position `index` from the list. Potentially linear complexity.
remove(&mut self, index: usize, pool: &mut ListPool<T>)487 pub fn remove(&mut self, index: usize, pool: &mut ListPool<T>) {
488 let len;
489 {
490 let seq = self.as_mut_slice(pool);
491 len = seq.len();
492 debug_assert!(index < len);
493
494 // Copy elements down.
495 for i in index..len - 1 {
496 seq[i] = seq[i + 1];
497 }
498 }
499
500 self.remove_last(len, pool);
501 }
502
503 /// Removes the element at `index` in constant time by switching it with the last element of
504 /// the list.
swap_remove(&mut self, index: usize, pool: &mut ListPool<T>)505 pub fn swap_remove(&mut self, index: usize, pool: &mut ListPool<T>) {
506 let seq = self.as_mut_slice(pool);
507 let len = seq.len();
508 debug_assert!(index < len);
509 if index != len - 1 {
510 seq.swap(index, len - 1);
511 }
512
513 self.remove_last(len, pool);
514 }
515
516 /// Shortens the list down to `len` elements.
517 ///
518 /// Does nothing if the list is already shorter than `len`.
truncate(&mut self, new_len: usize, pool: &mut ListPool<T>)519 pub fn truncate(&mut self, new_len: usize, pool: &mut ListPool<T>) {
520 if new_len == 0 {
521 self.clear(pool);
522 return;
523 }
524
525 match pool.len_of(self) {
526 None => return,
527 Some(len) => {
528 if len <= new_len {
529 return;
530 }
531
532 let block;
533 let idx = self.index as usize;
534 let sclass = sclass_for_length(len);
535 let new_sclass = sclass_for_length(new_len);
536 if sclass != new_sclass {
537 block = pool.realloc(idx - 1, sclass, new_sclass, new_len + 1);
538 self.index = (block + 1) as u32;
539 } else {
540 block = idx - 1;
541 }
542 pool.data[block] = T::new(new_len);
543 }
544 }
545 }
546
547 /// Grow the list by inserting `count` elements at `index`.
548 ///
549 /// The new elements are not initialized, they will contain whatever happened to be in memory.
550 /// Since the memory comes from the pool, this will be either zero entity references or
551 /// whatever where in a previously deallocated list.
grow_at(&mut self, index: usize, count: usize, pool: &mut ListPool<T>)552 pub fn grow_at(&mut self, index: usize, count: usize, pool: &mut ListPool<T>) {
553 let data = self.grow(count, pool);
554
555 // Copy elements after `index` up.
556 for i in (index + count..data.len()).rev() {
557 data[i] = data[i - count];
558 }
559 }
560 }
561
562 #[cfg(test)]
563 mod tests {
564 use super::*;
565 use super::{sclass_for_length, sclass_size};
566 use crate::EntityRef;
567
568 /// An opaque reference to an instruction in a function.
569 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
570 pub struct Inst(u32);
571 entity_impl!(Inst, "inst");
572
573 #[test]
size_classes()574 fn size_classes() {
575 assert_eq!(sclass_size(0), 4);
576 assert_eq!(sclass_for_length(0), 0);
577 assert_eq!(sclass_for_length(1), 0);
578 assert_eq!(sclass_for_length(2), 0);
579 assert_eq!(sclass_for_length(3), 0);
580 assert_eq!(sclass_for_length(4), 1);
581 assert_eq!(sclass_for_length(7), 1);
582 assert_eq!(sclass_for_length(8), 2);
583 assert_eq!(sclass_size(1), 8);
584 for l in 0..300 {
585 assert!(sclass_size(sclass_for_length(l)) >= l + 1);
586 }
587 }
588
589 #[test]
block_allocator()590 fn block_allocator() {
591 let mut pool = ListPool::<Inst>::new();
592 let b1 = pool.alloc(0);
593 let b2 = pool.alloc(1);
594 let b3 = pool.alloc(0);
595 assert_ne!(b1, b2);
596 assert_ne!(b1, b3);
597 assert_ne!(b2, b3);
598 pool.free(b2, 1);
599 let b2a = pool.alloc(1);
600 let b2b = pool.alloc(1);
601 assert_ne!(b2a, b2b);
602 // One of these should reuse the freed block.
603 assert!(b2a == b2 || b2b == b2);
604
605 // Check the free lists for a size class smaller than the largest seen so far.
606 pool.free(b1, 0);
607 pool.free(b3, 0);
608 let b1a = pool.alloc(0);
609 let b3a = pool.alloc(0);
610 assert_ne!(b1a, b3a);
611 assert!(b1a == b1 || b1a == b3);
612 assert!(b3a == b1 || b3a == b3);
613 }
614
615 #[test]
empty_list()616 fn empty_list() {
617 let pool = &mut ListPool::<Inst>::new();
618 let mut list = EntityList::<Inst>::default();
619 {
620 let ilist = &list;
621 assert!(ilist.is_empty());
622 assert_eq!(ilist.len(pool), 0);
623 assert_eq!(ilist.as_slice(pool), &[]);
624 assert_eq!(ilist.get(0, pool), None);
625 assert_eq!(ilist.get(100, pool), None);
626 }
627 assert_eq!(list.as_mut_slice(pool), &[]);
628 assert_eq!(list.get_mut(0, pool), None);
629 assert_eq!(list.get_mut(100, pool), None);
630
631 list.clear(pool);
632 assert!(list.is_empty());
633 assert_eq!(list.len(pool), 0);
634 assert_eq!(list.as_slice(pool), &[]);
635 assert_eq!(list.first(pool), None);
636 }
637
638 #[test]
from_slice()639 fn from_slice() {
640 let pool = &mut ListPool::<Inst>::new();
641
642 let list = EntityList::<Inst>::from_slice(&[Inst(0), Inst(1)], pool);
643 assert!(!list.is_empty());
644 assert_eq!(list.len(pool), 2);
645 assert_eq!(list.as_slice(pool), &[Inst(0), Inst(1)]);
646 assert_eq!(list.get(0, pool), Some(Inst(0)));
647 assert_eq!(list.get(100, pool), None);
648
649 let list = EntityList::<Inst>::from_slice(&[], pool);
650 assert!(list.is_empty());
651 assert_eq!(list.len(pool), 0);
652 assert_eq!(list.as_slice(pool), &[]);
653 assert_eq!(list.get(0, pool), None);
654 assert_eq!(list.get(100, pool), None);
655 }
656
657 #[test]
push()658 fn push() {
659 let pool = &mut ListPool::<Inst>::new();
660 let mut list = EntityList::<Inst>::default();
661
662 let i1 = Inst::new(1);
663 let i2 = Inst::new(2);
664 let i3 = Inst::new(3);
665 let i4 = Inst::new(4);
666
667 assert_eq!(list.push(i1, pool), 0);
668 assert_eq!(list.len(pool), 1);
669 assert!(!list.is_empty());
670 assert_eq!(list.as_slice(pool), &[i1]);
671 assert_eq!(list.first(pool), Some(i1));
672 assert_eq!(list.get(0, pool), Some(i1));
673 assert_eq!(list.get(1, pool), None);
674
675 assert_eq!(list.push(i2, pool), 1);
676 assert_eq!(list.len(pool), 2);
677 assert!(!list.is_empty());
678 assert_eq!(list.as_slice(pool), &[i1, i2]);
679 assert_eq!(list.first(pool), Some(i1));
680 assert_eq!(list.get(0, pool), Some(i1));
681 assert_eq!(list.get(1, pool), Some(i2));
682 assert_eq!(list.get(2, pool), None);
683
684 assert_eq!(list.push(i3, pool), 2);
685 assert_eq!(list.len(pool), 3);
686 assert!(!list.is_empty());
687 assert_eq!(list.as_slice(pool), &[i1, i2, i3]);
688 assert_eq!(list.first(pool), Some(i1));
689 assert_eq!(list.get(0, pool), Some(i1));
690 assert_eq!(list.get(1, pool), Some(i2));
691 assert_eq!(list.get(2, pool), Some(i3));
692 assert_eq!(list.get(3, pool), None);
693
694 // This triggers a reallocation.
695 assert_eq!(list.push(i4, pool), 3);
696 assert_eq!(list.len(pool), 4);
697 assert!(!list.is_empty());
698 assert_eq!(list.as_slice(pool), &[i1, i2, i3, i4]);
699 assert_eq!(list.first(pool), Some(i1));
700 assert_eq!(list.get(0, pool), Some(i1));
701 assert_eq!(list.get(1, pool), Some(i2));
702 assert_eq!(list.get(2, pool), Some(i3));
703 assert_eq!(list.get(3, pool), Some(i4));
704 assert_eq!(list.get(4, pool), None);
705
706 list.extend([i1, i1, i2, i2, i3, i3, i4, i4].iter().cloned(), pool);
707 assert_eq!(list.len(pool), 12);
708 assert_eq!(
709 list.as_slice(pool),
710 &[i1, i2, i3, i4, i1, i1, i2, i2, i3, i3, i4, i4]
711 );
712
713 let list2 = EntityList::from_iter([i1, i1, i2, i2, i3, i3, i4, i4].iter().cloned(), pool);
714 assert_eq!(list2.len(pool), 8);
715 assert_eq!(list2.as_slice(pool), &[i1, i1, i2, i2, i3, i3, i4, i4]);
716 }
717
718 #[test]
insert_remove()719 fn insert_remove() {
720 let pool = &mut ListPool::<Inst>::new();
721 let mut list = EntityList::<Inst>::default();
722
723 let i1 = Inst::new(1);
724 let i2 = Inst::new(2);
725 let i3 = Inst::new(3);
726 let i4 = Inst::new(4);
727
728 list.insert(0, i4, pool);
729 assert_eq!(list.as_slice(pool), &[i4]);
730
731 list.insert(0, i3, pool);
732 assert_eq!(list.as_slice(pool), &[i3, i4]);
733
734 list.insert(2, i2, pool);
735 assert_eq!(list.as_slice(pool), &[i3, i4, i2]);
736
737 list.insert(2, i1, pool);
738 assert_eq!(list.as_slice(pool), &[i3, i4, i1, i2]);
739
740 list.remove(3, pool);
741 assert_eq!(list.as_slice(pool), &[i3, i4, i1]);
742
743 list.remove(2, pool);
744 assert_eq!(list.as_slice(pool), &[i3, i4]);
745
746 list.remove(0, pool);
747 assert_eq!(list.as_slice(pool), &[i4]);
748
749 list.remove(0, pool);
750 assert_eq!(list.as_slice(pool), &[]);
751 assert!(list.is_empty());
752 }
753
754 #[test]
growing()755 fn growing() {
756 let pool = &mut ListPool::<Inst>::new();
757 let mut list = EntityList::<Inst>::default();
758
759 let i1 = Inst::new(1);
760 let i2 = Inst::new(2);
761 let i3 = Inst::new(3);
762 let i4 = Inst::new(4);
763
764 // This is not supposed to change the list.
765 list.grow_at(0, 0, pool);
766 assert_eq!(list.len(pool), 0);
767 assert!(list.is_empty());
768
769 list.grow_at(0, 2, pool);
770 assert_eq!(list.len(pool), 2);
771
772 list.as_mut_slice(pool).copy_from_slice(&[i2, i3]);
773
774 list.grow_at(1, 0, pool);
775 assert_eq!(list.as_slice(pool), &[i2, i3]);
776
777 list.grow_at(1, 1, pool);
778 list.as_mut_slice(pool)[1] = i1;
779 assert_eq!(list.as_slice(pool), &[i2, i1, i3]);
780
781 // Append nothing at the end.
782 list.grow_at(3, 0, pool);
783 assert_eq!(list.as_slice(pool), &[i2, i1, i3]);
784
785 // Append something at the end.
786 list.grow_at(3, 1, pool);
787 list.as_mut_slice(pool)[3] = i4;
788 assert_eq!(list.as_slice(pool), &[i2, i1, i3, i4]);
789 }
790
791 #[test]
deep_clone()792 fn deep_clone() {
793 let pool = &mut ListPool::<Inst>::new();
794
795 let i1 = Inst::new(1);
796 let i2 = Inst::new(2);
797 let i3 = Inst::new(3);
798 let i4 = Inst::new(4);
799
800 let mut list1 = EntityList::from_slice(&[i1, i2, i3], pool);
801 let list2 = list1.deep_clone(pool);
802 assert_eq!(list1.as_slice(pool), &[i1, i2, i3]);
803 assert_eq!(list2.as_slice(pool), &[i1, i2, i3]);
804
805 list1.as_mut_slice(pool)[0] = i4;
806 assert_eq!(list1.as_slice(pool), &[i4, i2, i3]);
807 assert_eq!(list2.as_slice(pool), &[i1, i2, i3]);
808 }
809
810 #[test]
truncate()811 fn truncate() {
812 let pool = &mut ListPool::<Inst>::new();
813
814 let i1 = Inst::new(1);
815 let i2 = Inst::new(2);
816 let i3 = Inst::new(3);
817 let i4 = Inst::new(4);
818
819 let mut list = EntityList::from_slice(&[i1, i2, i3, i4, i1, i2, i3, i4], pool);
820 assert_eq!(list.as_slice(pool), &[i1, i2, i3, i4, i1, i2, i3, i4]);
821 list.truncate(6, pool);
822 assert_eq!(list.as_slice(pool), &[i1, i2, i3, i4, i1, i2]);
823 list.truncate(9, pool);
824 assert_eq!(list.as_slice(pool), &[i1, i2, i3, i4, i1, i2]);
825 list.truncate(2, pool);
826 assert_eq!(list.as_slice(pool), &[i1, i2]);
827 list.truncate(0, pool);
828 assert!(list.is_empty());
829 }
830 }
831