[SOLVED] CS #include

#include
#include
#include
#include

const int minimum_size = 4;
const int minimum_heap_size = 1000;
const int max_possible_occupancy = (0x7FFFFFFF 1) / 2;

const int used= 0x80000000;
const int split = 0x40000000;
const int just_the_bits = 0x3FFFFFFF;

struct heap
{
int data_capacity_at_level[32], memory_occupancy_at_level[32];
int heap_size, heap_max_level;
int * memory;

heap()
{ heap_size = 0;
data_capacity_at_level[0] = minimum_size;
memory_occupancy_at_level[0] = minimum_size + 1;
for (int i=1; i<32; i+=1){ data_capacity_at_level[i] = memory_occupancy_at_level[i-1] * 2;memory_occupancy_at_level[i] = data_capacity_at_level[i] + 1;if (data_capacity_at_level[i] >= minimum_heap_size)
{ heap_size = memory_occupancy_at_level[i];
heap_max_level = i;
break; }
if (memory_occupancy_at_level[i] > max_possible_occupancy)
{ for (int j=i+1; j<32; j+=1){ data_capacity_at_level[j] = 0;memory_occupancy_at_level[j] = 0; }break; } }if (heap_size == 0){ printf(“Impossible heap size
“);exit(1); }memory = new int[heap_size];memory[0] = 1 << heap_max_level;memory[1] = 0;printf(“levelmax_data_sizememory_occupied_by_chunk
“);for (int i=0; i<=heap_max_level; i+=1)printf(“%3d%8d %8d
“, i, data_capacity_at_level[i], memory_occupancy_at_level[i]);printf(”
“); }char * decode_tag(int t){ static char decoding[1000];if ((t & just_the_bits) == 0){ sprintf(decoding, “none “);return decoding; }decoding[0] = 0;for (int i = heap_max_level; i>=0; i-=1)
{ int bit = 1 << i;if (t & bit){ char num[12];sprintf(num, “%d “, data_capacity_at_level[i]);strcat(decoding, num); } }return decoding; }void put_string_in_chunk(int chunk_start, char * s){ if (strlen(s) > 15)
s[15] = 0;
strcpy((char *)(memory + chunk_start + 1), s); }

char * string_from_chunk(int chunk_start)
{ return (char *)(memory + chunk_start + 1); }

void print_map(int chunk_start = 0, int depth = 0)
{ int level = heap_max_level depth, tag = memory[chunk_start];
for (int i = 0; i = size)
{ level_needed = i;
actual_size = data_capacity_at_level[level_needed];
break; } }
if (actual_size == 0)
{ printf(Impossible bigger than whole heap (1)
);
return false; }
printf(will have to use a level %d chunk of capacity %d words
,
level_needed,
data_capacity_at_level[level_needed]);
return allocate(name, level_needed, 0, heap_max_level); }

bool deallocate(int target, int curr_chunk_start, int curr_level)
{ printf(looking for chunk %d in chunk %d, at level %d
,
target, curr_chunk_start, curr_level);
int tag = memory[curr_chunk_start];
if (target == curr_chunk_start)
{ printf(found it, );
if (tag != used)
{ printf(impossible chunk is not in use
);
return false; }
int new_tag = 1 << curr_level;printf(“marking as free, size %s
“, decode_tag(new_tag));memory[curr_chunk_start] = new_tag;return true; }if (! (tag & split)){ printf(“impossible – this is not a split chunk
“);return false; }if (curr_level == 0){ printf(“impossible – no lower levels
“);return false; }int left_chunk_start = curr_chunk_start + 1;int right_chunk_start = curr_chunk_start + 1 + memory_occupancy_at_level[curr_level-1];int right_chunk_end = curr_chunk_start + data_capacity_at_level[curr_level];printf(“split chuck, left %d to %d, right %d to %d
“, left_chunk_start, right_chunk_start-1, right_chunk_start, right_chunk_end);if (target right_chunk_end)
{ printf(impossible target is not in this range
);
return false; }
bool ok;
if (target < right_chunk_start)ok = deallocate(target, left_chunk_start, curr_level-1);elseok = deallocate(target, right_chunk_start, curr_level-1);if (!ok) return false;int left_tag = memory[left_chunk_start];int right_tag = memory[right_chunk_start];bool left_free = (left_tag & (used | split)) == 0;bool right_free = (right_tag & (used | split)) == 0;if (left_free && right_free){ printf(“recombining %d and %d to make %d free
“, left_chunk_start, right_chunk_start, curr_chunk_start);int new_tag = 1 << curr_level;memory[curr_chunk_start] = new_tag;return true; }int new_tag = split | (left_tag & just_the_bits) | (right_tag & just_the_bits);printf(“retagging chunk %d, split with availability %s
“, curr_chunk_start, decode_tag(new_tag));memory[curr_chunk_start] = new_tag;return true; }bool deallocate(int chunk_start){ printf(“requested deallocation of chunk %d
“, chunk_start);return deallocate(chunk_start, 0, heap_max_level); } };bool isnumber(char * s){ for (int i=0; true; i+=1){ char c = s[i];if (c==0) return true;if (c<‘0’ || c>9) return false; } }

int main()
{ heap H;
printf(Just type
);
printf(name sizeto allocate memory
);
printf(free address to free memory

);
while (true)
{ char line[200], name[100], strnum[100];
H.print_map();
printf(> );
fgets(line, 199, stdin);
int n = sscanf(line, %s %s, name, strnum);
if (n!=2)
{ printf(type properly, only %d inputs
, n);
continue; }
if (! isnumber(strnum))
{ printf(type properly, %s is not a number
, strnum);
continue; }
int number = atol(strnum);
bool ok;
if (strcasecmp(name, free) == 0)
ok = H.deallocate(number);
else
ok = H.allocate(name, number);
if (ok)
printf(successful
);
else
printf(failed
); } }