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