chunked-range-alloc 1.0.0

use std::num::NonZeroU32;

use chunked_range_alloc::{Allocation, ChunkedRangeAlloc};

#[test]
fn test_alloc_free() {
    let mut alloc = ChunkedRangeAlloc::new(NonZeroU32::new(4).unwrap());

    let nz_1 = NonZeroU32::MIN;
    let nz_2 = NonZeroU32::new(2).unwrap();
    let nz_3 = NonZeroU32::new(3).unwrap();

    let one = alloc.alloc(nz_1, nz_1);
    assert_eq!(one.chunk_index, 0);
    assert_eq!(one.offset, 0);
    assert_eq!(one.len.get(), 1);

    assert_eq!(alloc.chunk_count(), 1);
    assert_eq!(alloc.active_chunks(), 1);
    assert_eq!(alloc.unused_chunks(), 0);
    assert_eq!(alloc.capacity(), 4);
    assert_eq!(alloc.allocated_memory(), 1);
    assert_eq!(alloc.remaining(), 3);
    assert_eq!(alloc.used_memory(), 4);
    assert_eq!(alloc.unused_memory(), 3);

    // align = 2
    let two = alloc.alloc(nz_1, nz_2);
    assert_eq!(two.chunk_index, 0);
    assert_eq!(two.offset, 2);
    assert_eq!(two.len.get(), 1);

    assert_eq!(alloc.chunk_count(), 1);
    assert_eq!(alloc.active_chunks(), 1);
    assert_eq!(alloc.unused_chunks(), 0);
    assert_eq!(alloc.capacity(), 4);
    assert_eq!(alloc.allocated_memory(), 2);
    assert_eq!(alloc.remaining(), 2);
    assert_eq!(alloc.used_memory(), 4);
    assert_eq!(alloc.unused_memory(), 2);

    // there are holes in first chunk, but align is still 2
    let three = alloc.alloc(nz_1, nz_2);
    assert_eq!(three.chunk_index, 1);
    assert_eq!(three.offset, 0);
    assert_eq!(three.len.get(), 1);

    assert_eq!(alloc.chunk_count(), 2);
    assert_eq!(alloc.active_chunks(), 2);
    assert_eq!(alloc.unused_chunks(), 0);
    assert_eq!(alloc.capacity(), 8);
    assert_eq!(alloc.allocated_memory(), 3);
    assert_eq!(alloc.remaining(), 5);
    assert_eq!(alloc.used_memory(), 8);
    assert_eq!(alloc.unused_memory(), 5);

    // can't fit into 1st chunk holes even with align = 1
    let four = alloc.alloc(nz_2, nz_1);
    assert_eq!(four.chunk_index, 1);
    assert_eq!(four.offset, 1);
    assert_eq!(four.len.get(), 2);

    assert_eq!(alloc.chunk_count(), 2);
    assert_eq!(alloc.active_chunks(), 2);
    assert_eq!(alloc.unused_chunks(), 0);
    assert_eq!(alloc.capacity(), 8);
    assert_eq!(alloc.allocated_memory(), 5);
    assert_eq!(alloc.remaining(), 3);
    assert_eq!(alloc.used_memory(), 8);
    assert_eq!(alloc.unused_memory(), 3);

    let free_chunk = alloc.free(two);
    assert!(!free_chunk);

    assert_eq!(alloc.chunk_count(), 2);
    assert_eq!(alloc.active_chunks(), 2);
    assert_eq!(alloc.unused_chunks(), 0);
    assert_eq!(alloc.capacity(), 8);
    assert_eq!(alloc.allocated_memory(), 4);
    assert_eq!(alloc.remaining(), 4);
    assert_eq!(alloc.used_memory(), 8);
    assert_eq!(alloc.unused_memory(), 4);

    let five = alloc.alloc(nz_3, nz_1);
    assert_eq!(five.chunk_index, 0);
    assert_eq!(five.offset, 1);
    assert_eq!(five.len.get(), 3);

    assert_eq!(alloc.chunk_count(), 2);
    assert_eq!(alloc.active_chunks(), 2);
    assert_eq!(alloc.unused_chunks(), 0);
    assert_eq!(alloc.capacity(), 8);
    assert_eq!(alloc.allocated_memory(), 7);
    assert_eq!(alloc.remaining(), 1);
    assert_eq!(alloc.used_memory(), 8);
    assert_eq!(alloc.unused_memory(), 1);

    let free_chunk = alloc.free(one);
    assert!(!free_chunk);

    assert_eq!(alloc.chunk_count(), 2);
    assert_eq!(alloc.active_chunks(), 2);
    assert_eq!(alloc.unused_chunks(), 0);
    assert_eq!(alloc.capacity(), 8);
    assert_eq!(alloc.allocated_memory(), 6);
    assert_eq!(alloc.remaining(), 2);
    assert_eq!(alloc.used_memory(), 8);
    assert_eq!(alloc.unused_memory(), 2);

    let free_chunk = alloc.free(five);
    assert!(free_chunk);

    assert_eq!(alloc.chunk_count(), 2);
    assert_eq!(alloc.active_chunks(), 1);
    assert_eq!(alloc.unused_chunks(), 1);
    assert_eq!(alloc.capacity(), 8);
    assert_eq!(alloc.allocated_memory(), 3);
    assert_eq!(alloc.remaining(), 5);
    assert_eq!(alloc.used_memory(), 4);
    assert_eq!(alloc.unused_memory(), 1);

    let free_chunk = alloc.free(three);
    assert!(!free_chunk);

    assert_eq!(alloc.chunk_count(), 2);
    assert_eq!(alloc.active_chunks(), 1);
    assert_eq!(alloc.unused_chunks(), 1);
    assert_eq!(alloc.capacity(), 8);
    assert_eq!(alloc.allocated_memory(), 2);
    assert_eq!(alloc.remaining(), 6);
    assert_eq!(alloc.used_memory(), 4);
    assert_eq!(alloc.unused_memory(), 2);

    let free_chunk = alloc.free(four);
    assert!(free_chunk);

    assert_eq!(alloc.chunk_count(), 2);
    assert_eq!(alloc.active_chunks(), 0);
    assert_eq!(alloc.unused_chunks(), 2);
    assert_eq!(alloc.capacity(), 8);
    assert_eq!(alloc.allocated_memory(), 0);
    assert_eq!(alloc.remaining(), 8);
    assert_eq!(alloc.used_memory(), 0);
    assert_eq!(alloc.unused_memory(), 0);
}

#[test]
fn test_from_allocations() {
    let nz_1 = NonZeroU32::MIN;
    let nz_4 = NonZeroU32::new(4).unwrap();

    let one = Allocation {
        chunk_index: 1,
        offset: 3,
        len: nz_1,
    };

    let two = Allocation {
        chunk_index: 1,
        offset: 1,
        len: nz_1,
    };

    let mut alloc = ChunkedRangeAlloc::from_allocations(nz_4, &[one, two]).unwrap();

    assert_eq!(alloc.chunk_count(), 2);
    assert_eq!(alloc.active_chunks(), 1);
    assert_eq!(alloc.unused_chunks(), 1);
    assert_eq!(alloc.capacity(), 8);
    assert_eq!(alloc.allocated_memory(), 2);
    assert_eq!(alloc.remaining(), 6);
    assert_eq!(alloc.used_memory(), 4);
    assert_eq!(alloc.unused_memory(), 2);

    let free_chunk = alloc.free(one);
    assert!(!free_chunk);

    assert_eq!(alloc.chunk_count(), 2);
    assert_eq!(alloc.active_chunks(), 1);
    assert_eq!(alloc.unused_chunks(), 1);
    assert_eq!(alloc.capacity(), 8);
    assert_eq!(alloc.allocated_memory(), 1);
    assert_eq!(alloc.remaining(), 7);
    assert_eq!(alloc.used_memory(), 4);
    assert_eq!(alloc.unused_memory(), 3);

    let free_chunk = alloc.free(two);
    assert!(free_chunk);
}

#[test]
fn test_from_allocations_exceeds_chunk_size() {
    let nz_1 = NonZeroU32::MIN;
    let nz_2 = NonZeroU32::new(2).unwrap();

    let alloc = ChunkedRangeAlloc::from_allocations(
        nz_2,
        &[Allocation {
            chunk_index: 1,
            offset: 1,
            len: nz_2, // offset + len > chunk size
        }],
    );
    assert!(alloc.is_none());

    let alloc = ChunkedRangeAlloc::from_allocations(
        nz_2,
        &[Allocation {
            chunk_index: 1,
            offset: 2,
            len: nz_1, // offset + len > chunk size
        }],
    );
    assert!(alloc.is_none());

    let alloc = ChunkedRangeAlloc::from_allocations(
        nz_2,
        &[Allocation {
            chunk_index: 1,
            offset: 4,
            len: nz_1, // offset + len > chunk size
        }],
    );
    assert!(alloc.is_none());
}

#[test]
fn test_from_allocations_overlapping() {
    let nz_1 = NonZeroU32::MIN;
    let nz_2 = NonZeroU32::new(2).unwrap();

    let alloc = ChunkedRangeAlloc::from_allocations(
        nz_2,
        &[
            Allocation {
                chunk_index: 0,
                offset: 0,
                len: nz_2,
            },
            Allocation {
                chunk_index: 0,
                offset: 0,
                len: nz_1,
            },
        ],
    );
    assert!(alloc.is_none());

    let alloc = ChunkedRangeAlloc::from_allocations(
        nz_2,
        &[
            Allocation {
                chunk_index: 0,
                offset: 0,
                len: nz_2,
            },
            Allocation {
                chunk_index: 0,
                offset: 1,
                len: nz_1,
            },
        ],
    );
    assert!(alloc.is_none());

    let alloc = ChunkedRangeAlloc::from_allocations(
        nz_2,
        &[
            Allocation {
                chunk_index: 0,
                offset: 0,
                len: nz_1,
            },
            Allocation {
                chunk_index: 0,
                offset: 0,
                len: nz_2,
            },
        ],
    );
    assert!(alloc.is_none());

    let alloc = ChunkedRangeAlloc::from_allocations(
        nz_2,
        &[
            Allocation {
                chunk_index: 0,
                offset: 1,
                len: nz_1,
            },
            Allocation {
                chunk_index: 0,
                offset: 0,
                len: nz_2,
            },
        ],
    );
    assert!(alloc.is_none());
}

#[test]
#[should_panic(expected = "double free")]
fn test_double_free_overlap_left() {
    let nz_2 = NonZeroU32::new(2).unwrap();
    let nz_4 = NonZeroU32::new(4).unwrap();

    let mut alloc = ChunkedRangeAlloc::from_allocations(
        nz_4,
        &[Allocation {
            chunk_index: 0,
            offset: 0,
            len: nz_2,
        }],
    )
    .unwrap();

    _ = alloc.free(Allocation {
        chunk_index: 0,
        offset: 1,
        len: nz_2,
    });
}

#[test]
#[should_panic(expected = "double free")]
fn test_double_free_overlap_right() {
    let nz_2 = NonZeroU32::new(2).unwrap();
    let nz_4 = NonZeroU32::new(4).unwrap();

    let mut alloc = ChunkedRangeAlloc::from_allocations(
        nz_4,
        &[Allocation {
            chunk_index: 0,
            offset: 2,
            len: nz_2,
        }],
    )
    .unwrap();

    _ = alloc.free(Allocation {
        chunk_index: 0,
        offset: 1,
        len: nz_2,
    });
}