483 lines
15 KiB
C
483 lines
15 KiB
C
#include "mem_range.h"
|
|
#include "test.h"
|
|
|
|
void test_range_end(void) {
|
|
uint64_t start = 5;
|
|
uint64_t size = 4;
|
|
struct mem_range rng = {
|
|
.start = start,
|
|
.size = size,
|
|
};
|
|
TEST_ASSERT(range_end(&rng) == start + size);
|
|
rng.size = 0;
|
|
TEST_ASSERT(range_end(&rng) == start);
|
|
}
|
|
|
|
void test_range_contains(void) {
|
|
uint64_t start = 5;
|
|
uint64_t size = 4;
|
|
struct mem_range rng = {
|
|
.start = start,
|
|
.size = size,
|
|
};
|
|
// test at start of range
|
|
TEST_ASSERT(range_contains(&rng, start));
|
|
// test inside range
|
|
TEST_ASSERT(range_contains(&rng, start + size/2));
|
|
// test at end of range -- should not be in!
|
|
TEST_ASSERT(!range_contains(&rng, range_end(&rng)));
|
|
}
|
|
|
|
// a range with size 0 can never intersect with anything!
|
|
void test_range_intersects_range(void) {
|
|
// as, ae, bs, be
|
|
struct mem_range a = {
|
|
.start = 1000,
|
|
.size = 50,
|
|
};
|
|
struct mem_range b = {
|
|
.start = 1020,
|
|
.size = 0,
|
|
};
|
|
TEST_ASSERT(!range_intersects_range(&a, &b));
|
|
TEST_ASSERT(!range_intersects_range(&b, &a));
|
|
}
|
|
|
|
// TODO test_cover_intersects_range
|
|
|
|
// ranges:
|
|
// - 10..15
|
|
// - 20..25
|
|
// - 30..35
|
|
// - 40..45
|
|
void test_cover_add_initialize(struct mem_cover *cov) {
|
|
cov->num_ranges = 4;
|
|
cov->cap_ranges = 10;
|
|
for (int i = 0; i < 4; i++) {
|
|
cov->ranges[i] = (struct mem_range) {
|
|
.start = 10 * (i+1),
|
|
.size = 5
|
|
};
|
|
}
|
|
}
|
|
|
|
void test_cover_add(void) {
|
|
struct mem_range ranges[10];
|
|
struct mem_cover cov = {
|
|
.ranges = ranges
|
|
};
|
|
|
|
// test: range before cover
|
|
test_cover_add_initialize(&cov);
|
|
struct mem_range range = {
|
|
.start = 5,
|
|
.size = 3
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 5);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 3);
|
|
for (unsigned int i = 1; i < 5; i++) {
|
|
TEST_ASSERT(ranges[i].start == 10*i && ranges[i].size == 5);
|
|
}
|
|
|
|
// test: connect to lowest range exactly
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 5,
|
|
.size = 5,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 4);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 10);
|
|
for (unsigned int i = 1; i < 4; i++) {
|
|
TEST_ASSERT(ranges[i].start == 10*(i+1) && ranges[i].size == 5);
|
|
}
|
|
|
|
// test: connect to lowest range with some overlap
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 5,
|
|
.size = 7,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 4);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 10);
|
|
for (unsigned int i = 1; i < 4; i++) {
|
|
TEST_ASSERT(ranges[i].start == 10*(i+1) && ranges[i].size == 5);
|
|
}
|
|
|
|
// test: connect to lowest range with exact overlap
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 5,
|
|
.size = 10,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 4);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 10);
|
|
for (unsigned int i = 1; i < 4; i++) {
|
|
TEST_ASSERT(ranges[i].start == 10*(i+1) && ranges[i].size == 5);
|
|
}
|
|
|
|
// test: connect to lowest range and reach over it, but not into next
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 5,
|
|
.size = 13,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 4);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 13);
|
|
for (unsigned int i = 1; i < 4; i++) {
|
|
TEST_ASSERT(ranges[i].start == 10*(i+1) && ranges[i].size == 5);
|
|
}
|
|
|
|
// test: connect to lowest range and reach over it, connecting exactly to next
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 5,
|
|
.size = 15,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 3);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 20);
|
|
for (unsigned int i = 1; i < 3; i++) {
|
|
TEST_ASSERT(ranges[i].start == 10*(i+2) && ranges[i].size == 5);
|
|
}
|
|
|
|
// test: connect to lowest range and reach over it, connecting to next with overlap
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 5,
|
|
.size = 17,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 3);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 20);
|
|
for (unsigned int i = 1; i < 3; i++) {
|
|
TEST_ASSERT(ranges[i].start == 10*(i+2) && ranges[i].size == 5);
|
|
}
|
|
|
|
// test: connect to lowest range and reach over it, connecting to end of next
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 5,
|
|
.size = 20,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 3);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 20);
|
|
for (unsigned int i = 1; i < 3; i++) {
|
|
TEST_ASSERT(ranges[i].start == 10*(i+2) && ranges[i].size == 5);
|
|
}
|
|
|
|
// test: connect to lowest range and reach over it, reaching over next
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 5,
|
|
.size = 22,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 3);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 22);
|
|
for (unsigned int i = 1; i < 3; i++) {
|
|
TEST_ASSERT(ranges[i].start == 10*(i+2) && ranges[i].size == 5);
|
|
}
|
|
|
|
// test: connect to lowest range and reach over it, reaching to 2 further
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 5,
|
|
.size = 25,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 2);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 30);
|
|
TEST_ASSERT(ranges[1].start == 40 && ranges[1].size == 5);
|
|
|
|
// test: connect to lowest range and reach over it, reaching to 2 further with overlap
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 5,
|
|
.size = 27,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 2);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 30);
|
|
TEST_ASSERT(ranges[1].start == 40 && ranges[1].size == 5);
|
|
|
|
// test: connect to lowest range and reach over it, reaching to end of 2 further
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 5,
|
|
.size = 30,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 2);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 30);
|
|
TEST_ASSERT(ranges[1].start == 40 && ranges[1].size == 5);
|
|
|
|
// test: connect to lowest range and reach over it, reaching over end of 2 further
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 5,
|
|
.size = 31,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 2);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 31);
|
|
TEST_ASSERT(ranges[1].start == 40 && ranges[1].size == 5);
|
|
|
|
// test: connect to bottom of last range
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 5,
|
|
.size = 35,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 1);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 40);
|
|
|
|
// test: connect to center of last range
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 5,
|
|
.size = 36,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 1);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 40);
|
|
|
|
// test: connect to end of last range
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 5,
|
|
.size = 40,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 1);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 40);
|
|
|
|
// test: move over end of last range
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 5,
|
|
.size = 42,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 1);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 5 && ranges[0].size == 42);
|
|
|
|
// --- start exactly at beginning of a range ---
|
|
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 10,
|
|
.size = 3,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 4);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
for (unsigned int i = 0; i < 4; i++) {
|
|
TEST_ASSERT(ranges[i].start == 10*(i+1) && ranges[i].size == 5);
|
|
}
|
|
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 10,
|
|
.size = 6,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 4);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 10 && ranges[0].size == 6);
|
|
for (unsigned int i = 1; i < 4; i++) {
|
|
TEST_ASSERT(ranges[i].start == 10*(i+1) && ranges[i].size == 5);
|
|
}
|
|
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 10,
|
|
.size = 10,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 3);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 10 && ranges[0].size == 15);
|
|
for (unsigned int i = 1; i < 3; i++) {
|
|
TEST_ASSERT(ranges[i].start == 10*(i+2) && ranges[i].size == 5);
|
|
}
|
|
|
|
// --- start inside a range ---
|
|
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 12,
|
|
.size = 3,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 4);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
for (unsigned int i = 0; i < 4; i++) {
|
|
TEST_ASSERT(ranges[i].start == 10*(i+1) && ranges[i].size == 5);
|
|
}
|
|
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 12,
|
|
.size = 4,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 4);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 10 && ranges[0].size == 6);
|
|
for (unsigned int i = 1; i < 4; i++) {
|
|
TEST_ASSERT(ranges[i].start == 10*(i+1) && ranges[i].size == 5);
|
|
}
|
|
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 12,
|
|
.size = 8,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 3);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 10 && ranges[0].size == 15);
|
|
for (unsigned int i = 1; i < 3; i++) {
|
|
TEST_ASSERT(ranges[i].start == 10*(i+2) && ranges[i].size == 5);
|
|
}
|
|
|
|
// --- range in between ---
|
|
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 26,
|
|
.size = 2,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 5);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 10 && ranges[0].size == 5);
|
|
TEST_ASSERT(ranges[1].start == 20 && ranges[1].size == 5);
|
|
TEST_ASSERT(ranges[2].start == 26 && ranges[2].size == 2);
|
|
TEST_ASSERT(ranges[3].start == 30 && ranges[3].size == 5);
|
|
TEST_ASSERT(ranges[4].start == 40 && ranges[4].size == 5);
|
|
|
|
test_cover_add_initialize(&cov);
|
|
range = (struct mem_range) {
|
|
.start = 26,
|
|
.size = 4,
|
|
};
|
|
cover_add(&cov, range);
|
|
TEST_ASSERT(cov.num_ranges == 4);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 10 && ranges[0].size == 5);
|
|
TEST_ASSERT(ranges[1].start == 20 && ranges[1].size == 5);
|
|
TEST_ASSERT(ranges[2].start == 26 && ranges[2].size == 9);
|
|
TEST_ASSERT(ranges[3].start == 40 && ranges[3].size == 5);
|
|
}
|
|
|
|
#define MEM_RANGE(the_start, the_size) (struct mem_range) { \
|
|
.start = the_start, \
|
|
.size = the_size \
|
|
}
|
|
|
|
void test_cover_align(void) {
|
|
struct mem_range ranges[10];
|
|
struct mem_cover cov = {
|
|
.num_ranges = 5,
|
|
.cap_ranges = 10,
|
|
.ranges = ranges
|
|
};
|
|
ranges[0] = MEM_RANGE(16, 16); // stays
|
|
ranges[1] = MEM_RANGE(33, 16); // removed because unaligned
|
|
ranges[2] = MEM_RANGE(64, 15); // removed because < 16
|
|
ranges[3] = MEM_RANGE(127, 18); // aligned to 128..+16
|
|
ranges[4] = MEM_RANGE(257, 30); // perfectly bad case (disappears)
|
|
cover_align(&cov, 4);
|
|
|
|
TEST_ASSERT(cov.num_ranges == 2);
|
|
TEST_ASSERT(cov.cap_ranges == 10);
|
|
TEST_ASSERT(ranges[0].start == 16 && ranges[0].size == 16);
|
|
TEST_ASSERT(ranges[1].start == 128 && ranges[1].size == 16);
|
|
}
|
|
|
|
#define TEST_RANGE_REMOVE(rs, re, xs, xe) do { \
|
|
range.start = rs; \
|
|
range.size = re - rs; \
|
|
remove.start = xs; \
|
|
remove.size = xe - xs; \
|
|
n = range_remove(&range, remove, new_ranges); \
|
|
} while (0)
|
|
void test_range_remove() {
|
|
struct mem_range range;
|
|
struct mem_range remove;
|
|
struct mem_range new_ranges[2];
|
|
int n;
|
|
TEST_RANGE_REMOVE(5, 10, 10, 15);
|
|
TEST_ASSERT(n == 1);
|
|
TEST_ASSERT(new_ranges[0].start == 5 && new_ranges[0].size == 5);
|
|
|
|
TEST_RANGE_REMOVE(5, 15, 10, 15);
|
|
TEST_ASSERT(n == 1);
|
|
TEST_ASSERT(new_ranges[0].start == 5 && new_ranges[0].size == 5);
|
|
|
|
TEST_RANGE_REMOVE(5, 20, 10, 15);
|
|
TEST_ASSERT(n == 2);
|
|
TEST_ASSERT(new_ranges[0].start == 5 && new_ranges[0].size == 5);
|
|
TEST_ASSERT(new_ranges[1].start == 15 && new_ranges[0].size == 5);
|
|
|
|
// ---
|
|
|
|
TEST_RANGE_REMOVE(5, 10, 5, 15);
|
|
TEST_ASSERT(n == 0);
|
|
|
|
TEST_RANGE_REMOVE(5, 20, 5, 15);
|
|
TEST_ASSERT(n == 1);
|
|
TEST_ASSERT(new_ranges[0].start == 15 && new_ranges[0].size == 5);
|
|
|
|
// ---
|
|
TEST_RANGE_REMOVE(20, 25, 10, 20);
|
|
TEST_ASSERT(n == 1);
|
|
TEST_ASSERT(new_ranges[0].start == 20 && new_ranges[0].size == 5);
|
|
|
|
TEST_RANGE_REMOVE(20, 30, 10, 25);
|
|
TEST_ASSERT(n == 1);
|
|
TEST_ASSERT(new_ranges[0].start == 25 && new_ranges[0].size == 5);
|
|
|
|
TEST_RANGE_REMOVE(20, 30, 10, 40);
|
|
TEST_ASSERT(n == 0);
|
|
|
|
// null test
|
|
TEST_RANGE_REMOVE(10, 20, 15, 15);
|
|
TEST_ASSERT(n == 1);
|
|
TEST_ASSERT(new_ranges[0].start == 10 && new_ranges[0].size == 10);
|
|
}
|
|
|
|
int main() {
|
|
test_range_end();
|
|
test_range_contains();
|
|
test_range_intersects_range();
|
|
test_cover_add();
|
|
test_cover_align();
|
|
test_range_remove();
|
|
return 0;
|
|
}
|