cranelift_entity/
list.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
//! Small lists of entity references.
use crate::packed_option::ReservedValue;
use crate::EntityRef;
use alloc::vec::Vec;
use core::marker::PhantomData;
use core::mem;

#[cfg(feature = "enable-serde")]
use serde_derive::{Deserialize, Serialize};

/// A small list of entity references allocated from a pool.
///
/// An `EntityList<T>` type provides similar functionality to `Vec<T>`, but with some important
/// differences in the implementation:
///
/// 1. Memory is allocated from a `ListPool<T>` instead of the global heap.
/// 2. The footprint of an entity list is 4 bytes, compared with the 24 bytes for `Vec<T>`.
/// 3. An entity list doesn't implement `Drop`, leaving it to the pool to manage memory.
///
/// The list pool is intended to be used as a LIFO allocator. After building up a larger data
/// structure with many list references, the whole thing can be discarded quickly by clearing the
/// pool.
///
/// # Safety
///
/// Entity lists are not as safe to use as `Vec<T>`, but they never jeopardize Rust's memory safety
/// guarantees. These are the problems to be aware of:
///
/// - If you lose track of an entity list, its memory won't be recycled until the pool is cleared.
///   This can cause the pool to grow very large with leaked lists.
/// - If entity lists are used after their pool is cleared, they may contain garbage data, and
///   modifying them may corrupt other lists in the pool.
/// - If an entity list is used with two different pool instances, both pools are likely to become
///   corrupted.
///
/// Entity lists can be cloned, but that operation should only be used as part of cloning the whole
/// function they belong to. *Cloning an entity list does not allocate new memory for the clone*.
/// It creates an alias of the same memory.
///
/// Entity lists cannot be hashed and compared for equality because it's not possible to compare the
/// contents of the list without the pool reference.
///
/// # Implementation
///
/// The `EntityList` itself is designed to have the smallest possible footprint. This is important
/// because it is used inside very compact data structures like `InstructionData`. The list
/// contains only a 32-bit index into the pool's memory vector, pointing to the first element of
/// the list.
///
/// The pool is just a single `Vec<T>` containing all of the allocated lists. Each list is
/// represented as three contiguous parts:
///
/// 1. The number of elements in the list.
/// 2. The list elements.
/// 3. Excess capacity elements.
///
/// The total size of the three parts is always a power of two, and the excess capacity is always
/// as small as possible. This means that shrinking a list may cause the excess capacity to shrink
/// if a smaller power-of-two size becomes available.
///
/// Both growing and shrinking a list may cause it to be reallocated in the pool vector.
///
/// The index stored in an `EntityList` points to part 2, the list elements. The value 0 is
/// reserved for the empty list which isn't allocated in the vector.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
pub struct EntityList<T: EntityRef + ReservedValue> {
    index: u32,
    unused: PhantomData<T>,
}

/// Create an empty list.
impl<T: EntityRef + ReservedValue> Default for EntityList<T> {
    fn default() -> Self {
        Self {
            index: 0,
            unused: PhantomData,
        }
    }
}

/// A memory pool for storing lists of `T`.
#[derive(Clone, Debug)]
#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
pub struct ListPool<T: EntityRef + ReservedValue> {
    // The main array containing the lists.
    data: Vec<T>,

    // Heads of the free lists, one for each size class.
    free: Vec<usize>,
}

impl<T: EntityRef + ReservedValue> PartialEq for ListPool<T> {
    fn eq(&self, other: &Self) -> bool {
        // ignore the free list
        self.data == other.data
    }
}

impl<T: core::hash::Hash + EntityRef + ReservedValue> core::hash::Hash for ListPool<T> {
    fn hash<H: __core::hash::Hasher>(&self, state: &mut H) {
        // ignore the free list
        self.data.hash(state);
    }
}

impl<T: EntityRef + ReservedValue> Default for ListPool<T> {
    fn default() -> Self {
        Self::new()
    }
}

/// Lists are allocated in sizes that are powers of two, starting from 4.
/// Each power of two is assigned a size class number, so the size is `4 << SizeClass`.
type SizeClass = u8;

/// Get the size of a given size class. The size includes the length field, so the maximum list
/// length is one less than the class size.
#[inline]
fn sclass_size(sclass: SizeClass) -> usize {
    4 << sclass
}

/// Get the size class to use for a given list length.
/// This always leaves room for the length element in addition to the list elements.
#[inline]
fn sclass_for_length(len: usize) -> SizeClass {
    30 - (len as u32 | 3).leading_zeros() as SizeClass
}

/// Is `len` the minimum length in its size class?
#[inline]
fn is_sclass_min_length(len: usize) -> bool {
    len > 3 && len.is_power_of_two()
}

impl<T: EntityRef + ReservedValue> ListPool<T> {
    /// Create a new list pool.
    pub fn new() -> Self {
        Self {
            data: Vec::new(),
            free: Vec::new(),
        }
    }

    /// Create a new list pool with the given capacity for data pre-allocated.
    pub fn with_capacity(len: usize) -> Self {
        Self {
            data: Vec::with_capacity(len),
            free: Vec::new(),
        }
    }

    /// Get the capacity of this pool. This will be somewhat higher
    /// than the total length of lists that can be stored without
    /// reallocating, because of internal metadata overheads. It is
    /// mostly useful to allow another pool to be allocated that is
    /// likely to hold data transferred from this one without the need
    /// to grow.
    pub fn capacity(&self) -> usize {
        self.data.capacity()
    }

    /// Clear the pool, forgetting about all lists that use it.
    ///
    /// This invalidates any existing entity lists that used this pool to allocate memory.
    ///
    /// The pool's memory is not released to the operating system, but kept around for faster
    /// allocation in the future.
    pub fn clear(&mut self) {
        self.data.clear();
        self.free.clear();
    }

    /// Read the length of a list field, if it exists.
    fn len_of(&self, list: &EntityList<T>) -> Option<usize> {
        let idx = list.index as usize;
        // `idx` points at the list elements. The list length is encoded in the element immediately
        // before the list elements.
        //
        // The `wrapping_sub` handles the special case 0, which is the empty list. This way, the
        // cost of the bounds check that we have to pay anyway is co-opted to handle the special
        // case of the empty list.
        self.data.get(idx.wrapping_sub(1)).map(|len| len.index())
    }

    /// Allocate a storage block with a size given by `sclass`.
    ///
    /// Returns the first index of an available segment of `self.data` containing
    /// `sclass_size(sclass)` elements. The allocated memory is filled with reserved
    /// values.
    fn alloc(&mut self, sclass: SizeClass) -> usize {
        // First try the free list for this size class.
        match self.free.get(sclass as usize).cloned() {
            Some(head) if head > 0 => {
                // The free list pointers are offset by 1, using 0 to terminate the list.
                // A block on the free list has two entries: `[ 0, next ]`.
                // The 0 is where the length field would be stored for a block in use.
                // The free list heads and the next pointer point at the `next` field.
                self.free[sclass as usize] = self.data[head].index();
                head - 1
            }
            _ => {
                // Nothing on the free list. Allocate more memory.
                let offset = self.data.len();
                self.data
                    .resize(offset + sclass_size(sclass), T::reserved_value());
                offset
            }
        }
    }

    /// Free a storage block with a size given by `sclass`.
    ///
    /// This must be a block that was previously allocated by `alloc()` with the same size class.
    fn free(&mut self, block: usize, sclass: SizeClass) {
        let sclass = sclass as usize;

        // Make sure we have a free-list head for `sclass`.
        if self.free.len() <= sclass {
            self.free.resize(sclass + 1, 0);
        }

        // Make sure the length field is cleared.
        self.data[block] = T::new(0);
        // Insert the block on the free list which is a single linked list.
        self.data[block + 1] = T::new(self.free[sclass]);
        self.free[sclass] = block + 1
    }

    /// Returns two mutable slices representing the two requested blocks.
    ///
    /// The two returned slices can be longer than the blocks. Each block is located at the front
    /// of the respective slice.
    fn mut_slices(&mut self, block0: usize, block1: usize) -> (&mut [T], &mut [T]) {
        if block0 < block1 {
            let (s0, s1) = self.data.split_at_mut(block1);
            (&mut s0[block0..], s1)
        } else {
            let (s1, s0) = self.data.split_at_mut(block0);
            (s0, &mut s1[block1..])
        }
    }

    /// Reallocate a block to a different size class.
    ///
    /// Copy `elems_to_copy` elements from the old to the new block.
    fn realloc(
        &mut self,
        block: usize,
        from_sclass: SizeClass,
        to_sclass: SizeClass,
        elems_to_copy: usize,
    ) -> usize {
        debug_assert!(elems_to_copy <= sclass_size(from_sclass));
        debug_assert!(elems_to_copy <= sclass_size(to_sclass));
        let new_block = self.alloc(to_sclass);

        if elems_to_copy > 0 {
            let (old, new) = self.mut_slices(block, new_block);
            (&mut new[0..elems_to_copy]).copy_from_slice(&old[0..elems_to_copy]);
        }

        self.free(block, from_sclass);
        new_block
    }
}

impl<T: EntityRef + ReservedValue> EntityList<T> {
    /// Create a new empty list.
    pub fn new() -> Self {
        Default::default()
    }

    /// Create a new list with the contents initialized from a slice.
    pub fn from_slice(slice: &[T], pool: &mut ListPool<T>) -> Self {
        let len = slice.len();
        if len == 0 {
            return Self::new();
        }

        let block = pool.alloc(sclass_for_length(len));
        pool.data[block] = T::new(len);
        pool.data[block + 1..=block + len].copy_from_slice(slice);

        Self {
            index: (block + 1) as u32,
            unused: PhantomData,
        }
    }

    /// Returns `true` if the list has a length of 0.
    pub fn is_empty(&self) -> bool {
        // 0 is a magic value for the empty list. Any list in the pool array must have a positive
        // length.
        self.index == 0
    }

    /// Get the number of elements in the list.
    pub fn len(&self, pool: &ListPool<T>) -> usize {
        // Both the empty list and any invalidated old lists will return `None`.
        pool.len_of(self).unwrap_or(0)
    }

    /// Returns `true` if the list is valid
    pub fn is_valid(&self, pool: &ListPool<T>) -> bool {
        // We consider an empty list to be valid
        self.is_empty() || pool.len_of(self) != None
    }

    /// Get the list as a slice.
    pub fn as_slice<'a>(&self, pool: &'a ListPool<T>) -> &'a [T] {
        let idx = self.index as usize;
        match pool.len_of(self) {
            None => &[],
            Some(len) => &pool.data[idx..idx + len],
        }
    }

    /// Get a single element from the list.
    pub fn get(&self, index: usize, pool: &ListPool<T>) -> Option<T> {
        self.as_slice(pool).get(index).cloned()
    }

    /// Get the first element from the list.
    pub fn first(&self, pool: &ListPool<T>) -> Option<T> {
        if self.is_empty() {
            None
        } else {
            Some(pool.data[self.index as usize])
        }
    }

    /// Get the list as a mutable slice.
    pub fn as_mut_slice<'a>(&'a mut self, pool: &'a mut ListPool<T>) -> &'a mut [T] {
        let idx = self.index as usize;
        match pool.len_of(self) {
            None => &mut [],
            Some(len) => &mut pool.data[idx..idx + len],
        }
    }

    /// Get a mutable reference to a single element from the list.
    pub fn get_mut<'a>(&'a mut self, index: usize, pool: &'a mut ListPool<T>) -> Option<&'a mut T> {
        self.as_mut_slice(pool).get_mut(index)
    }

    /// Create a deep clone of the list, which does not alias the original list.
    pub fn deep_clone(&self, pool: &mut ListPool<T>) -> Self {
        match pool.len_of(self) {
            None => return Self::new(),
            Some(len) => {
                let src = self.index as usize;
                let block = pool.alloc(sclass_for_length(len));
                pool.data[block] = T::new(len);
                pool.data.copy_within(src..src + len, block + 1);

                Self {
                    index: (block + 1) as u32,
                    unused: PhantomData,
                }
            }
        }
    }

    /// Removes all elements from the list.
    ///
    /// The memory used by the list is put back in the pool.
    pub fn clear(&mut self, pool: &mut ListPool<T>) {
        let idx = self.index as usize;
        match pool.len_of(self) {
            None => debug_assert_eq!(idx, 0, "Invalid pool"),
            Some(len) => pool.free(idx - 1, sclass_for_length(len)),
        }
        // Switch back to the empty list representation which has no storage.
        self.index = 0;
    }

    /// Take all elements from this list and return them as a new list. Leave this list empty.
    ///
    /// This is the equivalent of `Option::take()`.
    pub fn take(&mut self) -> Self {
        mem::replace(self, Default::default())
    }

    /// Appends an element to the back of the list.
    /// Returns the index where the element was inserted.
    pub fn push(&mut self, element: T, pool: &mut ListPool<T>) -> usize {
        let idx = self.index as usize;
        match pool.len_of(self) {
            None => {
                // This is an empty list. Allocate a block and set length=1.
                debug_assert_eq!(idx, 0, "Invalid pool");
                let block = pool.alloc(sclass_for_length(1));
                pool.data[block] = T::new(1);
                pool.data[block + 1] = element;
                self.index = (block + 1) as u32;
                0
            }
            Some(len) => {
                // Do we need to reallocate?
                let new_len = len + 1;
                let block;
                if is_sclass_min_length(new_len) {
                    // Reallocate, preserving length + all old elements.
                    let sclass = sclass_for_length(len);
                    block = pool.realloc(idx - 1, sclass, sclass + 1, len + 1);
                    self.index = (block + 1) as u32;
                } else {
                    block = idx - 1;
                }
                pool.data[block + new_len] = element;
                pool.data[block] = T::new(new_len);
                len
            }
        }
    }

    /// Grow list by adding `count` reserved-value elements at the end.
    ///
    /// Returns a mutable slice representing the whole list.
    fn grow<'a>(&'a mut self, count: usize, pool: &'a mut ListPool<T>) -> &'a mut [T] {
        let idx = self.index as usize;
        let new_len;
        let block;
        match pool.len_of(self) {
            None => {
                // This is an empty list. Allocate a block.
                debug_assert_eq!(idx, 0, "Invalid pool");
                if count == 0 {
                    return &mut [];
                }
                new_len = count;
                block = pool.alloc(sclass_for_length(new_len));
                self.index = (block + 1) as u32;
            }
            Some(len) => {
                // Do we need to reallocate?
                let sclass = sclass_for_length(len);
                new_len = len + count;
                let new_sclass = sclass_for_length(new_len);
                if new_sclass != sclass {
                    block = pool.realloc(idx - 1, sclass, new_sclass, len + 1);
                    self.index = (block + 1) as u32;
                } else {
                    block = idx - 1;
                }
            }
        }
        pool.data[block] = T::new(new_len);
        &mut pool.data[block + 1..block + 1 + new_len]
    }

    /// Constructs a list from an iterator.
    pub fn from_iter<I>(elements: I, pool: &mut ListPool<T>) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let mut list = Self::new();
        list.extend(elements, pool);
        list
    }

    /// Appends multiple elements to the back of the list.
    pub fn extend<I>(&mut self, elements: I, pool: &mut ListPool<T>)
    where
        I: IntoIterator<Item = T>,
    {
        let iterator = elements.into_iter();
        let (len, upper) = iterator.size_hint();
        // On most iterators this check is optimized down to `true`.
        if upper == Some(len) {
            let data = self.grow(len, pool);
            let offset = data.len() - len;
            for (src, dst) in iterator.zip(data[offset..].iter_mut()) {
                *dst = src;
            }
        } else {
            for x in iterator {
                self.push(x, pool);
            }
        }
    }

    /// Copies a slice from an entity list in the same pool to a position in this one.
    ///
    /// Will panic if `self` is the same list as `other`.
    pub fn copy_from(
        &mut self,
        other: &Self,
        slice: impl core::ops::RangeBounds<usize>,
        index: usize,
        pool: &mut ListPool<T>,
    ) {
        assert!(
            index <= self.len(pool),
            "attempted to copy a slice out of bounds of `self`"
        );
        assert_ne!(
            self.index, other.index,
            "cannot copy within one `EntityList`"
        );

        let (other_index, other_len) = (other.index, other.len(pool));

        let start = match slice.start_bound() {
            core::ops::Bound::Included(&x) => x,
            core::ops::Bound::Excluded(&x) => x + 1,
            core::ops::Bound::Unbounded => 0,
        } + other_index as usize;
        let end = match slice.end_bound() {
            core::ops::Bound::Included(&x) => x + 1,
            core::ops::Bound::Excluded(&x) => x,
            core::ops::Bound::Unbounded => other_len,
        } + other_index as usize;
        let count = end - start;
        assert!(
            count <= other_len,
            "attempted to copy a slice from out of bounds of `other`"
        );

        self.grow_at(index, count, pool);
        pool.data
            .copy_within(start..end, index + self.index as usize);
    }

    /// Inserts an element as position `index` in the list, shifting all elements after it to the
    /// right.
    pub fn insert(&mut self, index: usize, element: T, pool: &mut ListPool<T>) {
        // Increase size by 1.
        self.push(element, pool);

        // Move tail elements.
        let seq = self.as_mut_slice(pool);
        if index < seq.len() {
            let tail = &mut seq[index..];
            for i in (1..tail.len()).rev() {
                tail[i] = tail[i - 1];
            }
            tail[0] = element;
        } else {
            debug_assert_eq!(index, seq.len());
        }
    }

    /// Removes the last element from the list.
    fn remove_last(&mut self, len: usize, pool: &mut ListPool<T>) {
        // Check if we deleted the last element.
        if len == 1 {
            self.clear(pool);
            return;
        }

        // Do we need to reallocate to a smaller size class?
        let mut block = self.index as usize - 1;
        if is_sclass_min_length(len) {
            let sclass = sclass_for_length(len);
            block = pool.realloc(block, sclass, sclass - 1, len);
            self.index = (block + 1) as u32;
        }

        // Finally adjust the length.
        pool.data[block] = T::new(len - 1);
    }

    /// Removes the element at position `index` from the list. Potentially linear complexity.
    pub fn remove(&mut self, index: usize, pool: &mut ListPool<T>) {
        let len;
        {
            let seq = self.as_mut_slice(pool);
            len = seq.len();
            debug_assert!(index < len);

            // Copy elements down.
            for i in index..len - 1 {
                seq[i] = seq[i + 1];
            }
        }

        self.remove_last(len, pool);
    }

    /// Removes the element at `index` in constant time by switching it with the last element of
    /// the list.
    pub fn swap_remove(&mut self, index: usize, pool: &mut ListPool<T>) {
        let seq = self.as_mut_slice(pool);
        let len = seq.len();
        debug_assert!(index < len);
        if index != len - 1 {
            seq.swap(index, len - 1);
        }

        self.remove_last(len, pool);
    }

    /// Shortens the list down to `len` elements.
    ///
    /// Does nothing if the list is already shorter than `len`.
    pub fn truncate(&mut self, new_len: usize, pool: &mut ListPool<T>) {
        if new_len == 0 {
            self.clear(pool);
            return;
        }

        match pool.len_of(self) {
            None => return,
            Some(len) => {
                if len <= new_len {
                    return;
                }

                let block;
                let idx = self.index as usize;
                let sclass = sclass_for_length(len);
                let new_sclass = sclass_for_length(new_len);
                if sclass != new_sclass {
                    block = pool.realloc(idx - 1, sclass, new_sclass, new_len + 1);
                    self.index = (block + 1) as u32;
                } else {
                    block = idx - 1;
                }
                pool.data[block] = T::new(new_len);
            }
        }
    }

    /// Grow the list by inserting `count` elements at `index`.
    ///
    /// The new elements are not initialized, they will contain whatever happened to be in memory.
    /// Since the memory comes from the pool, this will be either zero entity references or
    /// whatever where in a previously deallocated list.
    pub fn grow_at(&mut self, index: usize, count: usize, pool: &mut ListPool<T>) {
        let data = self.grow(count, pool);

        // Copy elements after `index` up.
        for i in (index + count..data.len()).rev() {
            data[i] = data[i - count];
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// An opaque reference to an instruction in a function.
    #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
    pub struct Inst(u32);
    entity_impl!(Inst, "inst");

    #[test]
    fn size_classes() {
        assert_eq!(sclass_size(0), 4);
        assert_eq!(sclass_for_length(0), 0);
        assert_eq!(sclass_for_length(1), 0);
        assert_eq!(sclass_for_length(2), 0);
        assert_eq!(sclass_for_length(3), 0);
        assert_eq!(sclass_for_length(4), 1);
        assert_eq!(sclass_for_length(7), 1);
        assert_eq!(sclass_for_length(8), 2);
        assert_eq!(sclass_size(1), 8);
        for l in 0..300 {
            assert!(sclass_size(sclass_for_length(l)) >= l + 1);
        }
    }

    #[test]
    fn block_allocator() {
        let mut pool = ListPool::<Inst>::new();
        let b1 = pool.alloc(0);
        let b2 = pool.alloc(1);
        let b3 = pool.alloc(0);
        assert_ne!(b1, b2);
        assert_ne!(b1, b3);
        assert_ne!(b2, b3);
        pool.free(b2, 1);
        let b2a = pool.alloc(1);
        let b2b = pool.alloc(1);
        assert_ne!(b2a, b2b);
        // One of these should reuse the freed block.
        assert!(b2a == b2 || b2b == b2);

        // Check the free lists for a size class smaller than the largest seen so far.
        pool.free(b1, 0);
        pool.free(b3, 0);
        let b1a = pool.alloc(0);
        let b3a = pool.alloc(0);
        assert_ne!(b1a, b3a);
        assert!(b1a == b1 || b1a == b3);
        assert!(b3a == b1 || b3a == b3);
    }

    #[test]
    fn empty_list() {
        let pool = &mut ListPool::<Inst>::new();
        let mut list = EntityList::<Inst>::default();
        {
            let ilist = &list;
            assert!(ilist.is_empty());
            assert_eq!(ilist.len(pool), 0);
            assert_eq!(ilist.as_slice(pool), &[]);
            assert_eq!(ilist.get(0, pool), None);
            assert_eq!(ilist.get(100, pool), None);
        }
        assert_eq!(list.as_mut_slice(pool), &[]);
        assert_eq!(list.get_mut(0, pool), None);
        assert_eq!(list.get_mut(100, pool), None);

        list.clear(pool);
        assert!(list.is_empty());
        assert_eq!(list.len(pool), 0);
        assert_eq!(list.as_slice(pool), &[]);
        assert_eq!(list.first(pool), None);
    }

    #[test]
    fn from_slice() {
        let pool = &mut ListPool::<Inst>::new();

        let list = EntityList::<Inst>::from_slice(&[Inst(0), Inst(1)], pool);
        assert!(!list.is_empty());
        assert_eq!(list.len(pool), 2);
        assert_eq!(list.as_slice(pool), &[Inst(0), Inst(1)]);
        assert_eq!(list.get(0, pool), Some(Inst(0)));
        assert_eq!(list.get(100, pool), None);

        let list = EntityList::<Inst>::from_slice(&[], pool);
        assert!(list.is_empty());
        assert_eq!(list.len(pool), 0);
        assert_eq!(list.as_slice(pool), &[]);
        assert_eq!(list.get(0, pool), None);
        assert_eq!(list.get(100, pool), None);
    }

    #[test]
    fn push() {
        let pool = &mut ListPool::<Inst>::new();
        let mut list = EntityList::<Inst>::default();

        let i1 = Inst::new(1);
        let i2 = Inst::new(2);
        let i3 = Inst::new(3);
        let i4 = Inst::new(4);

        assert_eq!(list.push(i1, pool), 0);
        assert_eq!(list.len(pool), 1);
        assert!(!list.is_empty());
        assert_eq!(list.as_slice(pool), &[i1]);
        assert_eq!(list.first(pool), Some(i1));
        assert_eq!(list.get(0, pool), Some(i1));
        assert_eq!(list.get(1, pool), None);

        assert_eq!(list.push(i2, pool), 1);
        assert_eq!(list.len(pool), 2);
        assert!(!list.is_empty());
        assert_eq!(list.as_slice(pool), &[i1, i2]);
        assert_eq!(list.first(pool), Some(i1));
        assert_eq!(list.get(0, pool), Some(i1));
        assert_eq!(list.get(1, pool), Some(i2));
        assert_eq!(list.get(2, pool), None);

        assert_eq!(list.push(i3, pool), 2);
        assert_eq!(list.len(pool), 3);
        assert!(!list.is_empty());
        assert_eq!(list.as_slice(pool), &[i1, i2, i3]);
        assert_eq!(list.first(pool), Some(i1));
        assert_eq!(list.get(0, pool), Some(i1));
        assert_eq!(list.get(1, pool), Some(i2));
        assert_eq!(list.get(2, pool), Some(i3));
        assert_eq!(list.get(3, pool), None);

        // This triggers a reallocation.
        assert_eq!(list.push(i4, pool), 3);
        assert_eq!(list.len(pool), 4);
        assert!(!list.is_empty());
        assert_eq!(list.as_slice(pool), &[i1, i2, i3, i4]);
        assert_eq!(list.first(pool), Some(i1));
        assert_eq!(list.get(0, pool), Some(i1));
        assert_eq!(list.get(1, pool), Some(i2));
        assert_eq!(list.get(2, pool), Some(i3));
        assert_eq!(list.get(3, pool), Some(i4));
        assert_eq!(list.get(4, pool), None);

        list.extend([i1, i1, i2, i2, i3, i3, i4, i4].iter().cloned(), pool);
        assert_eq!(list.len(pool), 12);
        assert_eq!(
            list.as_slice(pool),
            &[i1, i2, i3, i4, i1, i1, i2, i2, i3, i3, i4, i4]
        );

        let list2 = EntityList::from_iter([i1, i1, i2, i2, i3, i3, i4, i4].iter().cloned(), pool);
        assert_eq!(list2.len(pool), 8);
        assert_eq!(list2.as_slice(pool), &[i1, i1, i2, i2, i3, i3, i4, i4]);
    }

    #[test]
    fn insert_remove() {
        let pool = &mut ListPool::<Inst>::new();
        let mut list = EntityList::<Inst>::default();

        let i1 = Inst::new(1);
        let i2 = Inst::new(2);
        let i3 = Inst::new(3);
        let i4 = Inst::new(4);

        list.insert(0, i4, pool);
        assert_eq!(list.as_slice(pool), &[i4]);

        list.insert(0, i3, pool);
        assert_eq!(list.as_slice(pool), &[i3, i4]);

        list.insert(2, i2, pool);
        assert_eq!(list.as_slice(pool), &[i3, i4, i2]);

        list.insert(2, i1, pool);
        assert_eq!(list.as_slice(pool), &[i3, i4, i1, i2]);

        list.remove(3, pool);
        assert_eq!(list.as_slice(pool), &[i3, i4, i1]);

        list.remove(2, pool);
        assert_eq!(list.as_slice(pool), &[i3, i4]);

        list.remove(0, pool);
        assert_eq!(list.as_slice(pool), &[i4]);

        list.remove(0, pool);
        assert_eq!(list.as_slice(pool), &[]);
        assert!(list.is_empty());
    }

    #[test]
    fn growing() {
        let pool = &mut ListPool::<Inst>::new();
        let mut list = EntityList::<Inst>::default();

        let i1 = Inst::new(1);
        let i2 = Inst::new(2);
        let i3 = Inst::new(3);
        let i4 = Inst::new(4);

        // This is not supposed to change the list.
        list.grow_at(0, 0, pool);
        assert_eq!(list.len(pool), 0);
        assert!(list.is_empty());

        list.grow_at(0, 2, pool);
        assert_eq!(list.len(pool), 2);

        list.as_mut_slice(pool).copy_from_slice(&[i2, i3]);

        list.grow_at(1, 0, pool);
        assert_eq!(list.as_slice(pool), &[i2, i3]);

        list.grow_at(1, 1, pool);
        list.as_mut_slice(pool)[1] = i1;
        assert_eq!(list.as_slice(pool), &[i2, i1, i3]);

        // Append nothing at the end.
        list.grow_at(3, 0, pool);
        assert_eq!(list.as_slice(pool), &[i2, i1, i3]);

        // Append something at the end.
        list.grow_at(3, 1, pool);
        list.as_mut_slice(pool)[3] = i4;
        assert_eq!(list.as_slice(pool), &[i2, i1, i3, i4]);
    }

    #[test]
    fn deep_clone() {
        let pool = &mut ListPool::<Inst>::new();

        let i1 = Inst::new(1);
        let i2 = Inst::new(2);
        let i3 = Inst::new(3);
        let i4 = Inst::new(4);

        let mut list1 = EntityList::from_slice(&[i1, i2, i3], pool);
        let list2 = list1.deep_clone(pool);
        assert_eq!(list1.as_slice(pool), &[i1, i2, i3]);
        assert_eq!(list2.as_slice(pool), &[i1, i2, i3]);

        list1.as_mut_slice(pool)[0] = i4;
        assert_eq!(list1.as_slice(pool), &[i4, i2, i3]);
        assert_eq!(list2.as_slice(pool), &[i1, i2, i3]);
    }

    #[test]
    fn truncate() {
        let pool = &mut ListPool::<Inst>::new();

        let i1 = Inst::new(1);
        let i2 = Inst::new(2);
        let i3 = Inst::new(3);
        let i4 = Inst::new(4);

        let mut list = EntityList::from_slice(&[i1, i2, i3, i4, i1, i2, i3, i4], pool);
        assert_eq!(list.as_slice(pool), &[i1, i2, i3, i4, i1, i2, i3, i4]);
        list.truncate(6, pool);
        assert_eq!(list.as_slice(pool), &[i1, i2, i3, i4, i1, i2]);
        list.truncate(9, pool);
        assert_eq!(list.as_slice(pool), &[i1, i2, i3, i4, i1, i2]);
        list.truncate(2, pool);
        assert_eq!(list.as_slice(pool), &[i1, i2]);
        list.truncate(0, pool);
        assert!(list.is_empty());
    }

    #[test]
    fn copy_from() {
        let pool = &mut ListPool::<Inst>::new();

        let i1 = Inst::new(1);
        let i2 = Inst::new(2);
        let i3 = Inst::new(3);
        let i4 = Inst::new(4);

        let mut list = EntityList::from_slice(&[i1, i2, i3, i4], pool);
        assert_eq!(list.as_slice(pool), &[i1, i2, i3, i4]);
        let list2 = EntityList::from_slice(&[i4, i3, i2, i1], pool);
        assert_eq!(list2.as_slice(pool), &[i4, i3, i2, i1]);
        list.copy_from(&list2, 0..0, 0, pool);
        assert_eq!(list.as_slice(pool), &[i1, i2, i3, i4]);
        list.copy_from(&list2, 0..4, 0, pool);
        assert_eq!(list.as_slice(pool), &[i4, i3, i2, i1, i1, i2, i3, i4]);
    }

    #[test]
    #[should_panic]
    fn copy_from_self() {
        let pool = &mut ListPool::<Inst>::new();

        let i1 = Inst::new(1);
        let i2 = Inst::new(2);
        let i3 = Inst::new(3);
        let i4 = Inst::new(4);

        let mut list = EntityList::from_slice(&[i4, i3, i2, i1, i1, i2, i3, i4], pool);
        let list_again = list;
        assert_eq!(list.as_slice(pool), &[i4, i3, i2, i1, i1, i2, i3, i4]);
        // Panic should occur on the line below because `list.index == other.index`
        list.copy_from(&list_again, 0..=1, 8, pool);
        assert_eq!(
            list.as_slice(pool),
            &[i4, i3, i2, i1, i1, i2, i3, i4, i4, i3]
        );
        list.copy_from(&list_again, .., 7, pool);
        assert_eq!(
            list.as_slice(pool),
            &[i4, i3, i2, i1, i1, i2, i4, i3, i2, i1, i1, i2, i3, i4, i4, i3, i3, i4, i4, i3]
        )
    }
}