Allocator

From EE312

Written by Amanda Travieso

Contents 1 Allocator 2 Casting 3 Allocator_Valid 4 Allocator_Initialize 5 Allocator_Allocate 6 Allocator_Deallocate 7 One last thing

Allocator

In this project we will be defining a series of functions in order to simulate a heap.

We are going to be constructing arrays of various sizes to simulate how much memory is available for allocation. This array will have sentinel values which indicate how much memory is free and how much memory is being used. A busy block of memory will have a negative sentinel while free blocks will be proceeded by, and followed by, positive sentinels.

The initial call to Allocator is:

   template <typename T, std::size_t N>
   struct Allocator {
   char a[N];};

Notice that the array “a” of size “N” is an array of chars. This is convenient because a char takes up a single byte of memory. The value located in the sentinel will be the number of bytes between the two corresponding sentinel markers.

Casting

As explained previously, the array “a” is an array of chars however sentinel values are integers. An integer takes up four bytes. It is necessary to read the four bytes corresponding to a sentinel as an integer even though that value is stored in an array of chars. This is done with the form:

   Int i= *(reinterpret_cast <type*> (&f)

This creates a view of four bytes as an integer. This view is only temporary and will need to be called each time you are trying to read the value of a sentinel integer.

Allocator_Valid

This function needs to:

1. Add sentinel markers to ensure the sum equals N.

• At the time the function is called, it is possible to have some busy memory as well as some free memory. When accounting for busy memory, remember to take the absolute value as that memory will be marked with a negative value.

2. Check that each marker has a corresponding equivalent marker.

• These markers need to be equivalent in magnitude as well as sign.

Allocator_Initialize

This function should place markers at the beginning and end of the array. These markers will be positive as this function is not responsible for marking any values of memory as busy. The value in these markers, after casting, will be (N-8) because each marker will take up four bytes of memory.

Allocator_Allocate

This function should:

1. Change markers to negative values to reflect the amount of memory the user has asked for is busy

• When this is done, the amount of available memory will need to be recalculated.
• If the amount of available memory remaining is too small to hold two markers and one more space of type T, the remaining memory should be allocated with the current user request.

2. In the event that the user has requested more memory than is available, this function should throw an exception.

3. This function should return a pointer to the first element past the first marker.

Allocator_Deallocate

This function will:

1. Change negative markers to positive markers to indicate more available memory.

2. Combines available blocks of memory.

• This function will need to check if there is available memory to the “left” and to the “right” of the block which is being made available.
• If there is available memory on either side (or both sides) adjacent to the newly free block, the amount of available memory will need to be recalculated.

3. Checks that the call to deallocate was valid.

• The call will be invalid if the pointer given in the call is not immediately preceded by a sentinel
• In the case of an invalid call, an exception should be thrown.

One last thing

Don’t forget…additional documentation is required preceding each function.