#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
{ 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 (target
{ 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”); } }