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\n"); exit(1); } memory = new int[heap_size]; memory[0] = 1 << heap_max_level; memory[1] = 0; printf("level max_data_size memory_occupied_by_chunk\n"); for (int i=0; i<=heap_max_level; i+=1) printf("%3d %8d %8d\n", i, data_capacity_at_level[i], memory_occupancy_at_level[i]); printf("\n"); } 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)\n”);
return false; }
printf(” will have to use a level %d chunk of capacity %d words\n”,
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\n”,
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\n”);
return false; }
int new_tag = 1 << curr_level; printf("marking as free, size %s\n", decode_tag(new_tag)); memory[curr_chunk_start] = new_tag; return true; } if (! (tag & split)) { printf("impossible - this is not a split chunk\n"); return false; } if (curr_level == 0) { printf("impossible - no lower levels\n"); 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\n", left_chunk_start, right_chunk_start-1, right_chunk_start, right_chunk_end); if (targetright_chunk_end)
{ printf(“impossible – target is not in this range\n”);
return false; }
bool ok;
if (target < right_chunk_start) ok = deallocate(target, left_chunk_start, curr_level-1); else ok = 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\n", 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\n", 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\n", 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\n”);
printf(” name size to allocate memory\n”);
printf(” free address to free memory\n\n”);
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”, n);
continue; }
if (! isnumber(strnum))
{ printf(“type properly, ‘%s’ is not a number\n”, 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\n”);
else
printf(“failed\n”); } }