#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdarg.h>
#include <stdbool.h>
#define SIZE 9
int pa[SIZE];
void printarray() {
printf("Array [");
for (int i=0; i<SIZE-1; i+=1) {
printf("%d, ", pa[i]);
}
printf("%d]\n",pa[SIZE-1]);
}
void printsegments() {
printf("Segments ");
for (int i=0; pa[i+1] != 0; i+=2) {
int start = pa[i];
int end = pa[i+1] - 1;
int size = pa[i+1] - pa[i];
printf("%d: %d-%d (%d), ", i/2, start, end, size);
}
printf("\n");
}
void initarray() {
pa[0] = 0; // seg 0 start
pa[1] = 100; // seg 0 end
pa[2] = 200; // seg 1 start
pa[3] = 300; // seg 1 end
pa[4] = 400; // seg 2 start
pa[5] = 500; // seg 2 end
pa[6] = 0;
pa[7] = 0;
pa[8] = 0;
}
void insert_at(int index, int val) {
int j = SIZE-2;
while (j >= index) {
pa[j+1] = pa[j];
j--;
}
pa[j+1] = val;
}
void delete_at(int index) {
int j = index;
while (j < SIZE-1) {
pa[j] = pa[j+1];
j++;
}
}
// Assumes that the array of segments is ordered.
void makehole(int hole_start, int hole_end) {
int i = 0;
/* Check if before the first segment */
if (hole_end <= pa[0])
return;
/* Check if inside a hole. */
while (pa[i+2] != 0) {
if (hole_start >= pa[i+1] && hole_end <= pa[i+2])
return;
i += 2;
}
/* Check if new hole is after last segment end (i+1). */
if (hole_start >= pa[i+1])
return;
/* Check if inside a segment */
i=0;
while (pa[i+1] != 0) {
if (hole_start > pa[i] && hole_end < pa[i+1]) {
insert_at(i+1, hole_end);
insert_at(i+1, hole_start);
return;
}
i += 2;
}
/* Other cases */
i=0;
while (pa[i] < hole_start && i < SIZE) {
i++;
}
/* The new hole starts in the last segment and ends after. */
if (pa[i+1] == 0) {
pa[i] = hole_start;
return;
}
/* At th7 index located on or after the new hole start. */
if (i % 2 == 0) {
/*
* Even index mean beginning of a segment. If hole ends in segment,
* shrink the segment. If exact match, delete the segment. Other
* cases are handled below.
*/
if (hole_start == pa[i]) {
if (hole_end < pa[i+1]) {
pa[i] = hole_end;
return;
} else if (hole_end == pa[i+1]) {
delete_at(i);
delete_at(i);
return;
}
}
} else {
/*
* Odd index mean the hole starts inside a memory segment.
* Shrink segment to hole start.
*/
pa[i] = hole_start;
i++;
}
int deleted = 0;
while (pa[i] <= hole_end && pa[i+1] != 0) {
delete_at(i);
deleted++;
}
/* At the index located after the new hole end. */
if (i % 2 == 0 && deleted % 2 == 1) {
/*
* If index is even and odd number of entries have been deleted,
* we are at the end of a segment. Insert hole end before this
* segment.
*/
insert_at(i, hole_end);
} else if (i % 2 == 1) {
/*
* Odd index mean our hole ends in the previous segment,
* change segment start to new hole end.
*/
pa[i-1] = hole_start;
}
}
void test(const char *test, int hole_start, int hole_end, int expect[SIZE]) {
printf("Test: %s. (%d-%d)", test, hole_start, hole_end);
makehole(hole_start,hole_end);
if (memcmp(pa, expect, sizeof(int)*SIZE) != 0) {
printf(" - MISMATCH. ");
printarray();
exit(EXIT_FAILURE);
}
printf(" - OK. ");
printsegments();
initarray();
}
int main() {
printf("\nInitialized array\n");
initarray();
printarray();
printsegments();
printf("\n");
test("Exact match hole", 100, 200, (int []) {0,100,200,300,400,500,0,0,0});
test("Exact match segment first", 0, 100, (int []) {200,300,400,500,0,0,0,0,0});
test("Exact match segment middle", 200, 300, (int []) {0,100,400,500,0,0,0,0,0});
test("Exact match segment last", 400, 500, (int []) {0,100,200,300,0,0,0,0,0});
test("Inside hole", 120, 130, (int []) {0,100,200,300,400,500,0,0,0});
test("Inside segment", 220, 230, (int []) {0,100,200,220,230,300,400,500,0});
test("Start in hole, end in segment", 150, 250, (int []) {0,100,250,300,400,500,0,0,0});
test("Start in segment, end in hole", 250, 350, (int []) {0,100,200,250,400,500,0,0,0});
test("Start in hole, skip segment, end in segment", 150, 450, (int []) {0,100,450,500,0,0,0,0,0});
test("Start in segment, skip segment, end in hole", 50, 350, (int []) {0,50,400,500,0,0,0,0,0});
test("Start in hole, skip segment, end in hole", 150, 350, (int []) {0,100,400,500,0,0,0,0,0});
test("Start in segment, skip segment, end in segment", 50, 450, (int []) {0,50,450,500,0,0,0,0,0});
test("Exact match segment+hole", 0, 200, (int []) {200,300,400,500,0,0,0,0,0});
test("Exact match hole+segment", 100, 300, (int []) {0,100,400,500,0,0,0,0,0});
test("Start in segment, end on segment end", 50, 100, (int []) {0,50,200,300,400,500,0,0,0});
test("Start on segment start, end in same segment", 0, 50, (int []) {50,100,200,300,400,500,0,0,0});
test("Almost exact match hole", 101, 199, (int []) {0,100,200,300,400,500,0,0,0});
test("Almost exact match segment", 99, 201, (int []) {0,99,201,300,400,500,0,0,0});
test("Hole starting in last segment, ending after", 450, 600, (int []) {0,100,200,300,400,450,0,0,0});
test("Hole after last segment", 700, 800, (int []) {0,100,200,300,400,500,0,0,0});
pa[5] = 0;
test("Hole after last segment", 700, 800, (int []) {0,100,200,300,400,0,0,0,0});
pa[6] = 600;
test("Hole after last segment", 700, 800, (int []) {0,100,200,300,400,500,600,0,0});
pa[0] = 50;
test("Hole before first segment", 0, 40, (int []) {50,100,200,300,400,500,0,0,0});
pa[0] = 50;
test("Hole start before first segment, end in segment", 0, 80, (int []) {80,100,200,300,400,500,0,0,0});
return 0;
}