Monday, March 19, 2012

Memory management in C++ syntax directed editor

The "buddy system" has been implemented in C++ syntax directed editor using C language (To enlarge the text of the program click on it).

The size of reserved blocks is limited to 1, 2, 4, 8, 16 bytes, … that is a power of two. If the requested block size is not a power of two then the next higher power of 2 is chosen and extra unused space is allocated.

Let the size of the memory pool will be 2**n.
We keep separate lists of available blocks of each size 2**k, 0 <= k <= n. When a block of 2**k bytes is desired, and if nothing of this size is available, a larger available block is split into two equal parts; ultimately, a block of the right size 2**k will appear.

When one block splits into two (each of which is half as large as the original), these two blocks are called buddies. Later when both buddies are available again, they coalesce back into a single block.

The practical value of the method is determined by the possibility to calculate the address of the buddy. For example, the buddy of the block of size 2 beginning in binary location 100 is a block starting in binary location 110.
For block with size 2**k and the address x there will be the buddy with the address:
x+2**k if x mod 2**(k+1) = 0
x-2**k if x mod 2**(k+1) = 2**k
See the text of the program for details. First of all you execute the following code.

// Give segments of RAM
if( GiveSegments() == -1 ){PostQuitMessage(0);return FALSE;}
else InitSegments();

After that, call “GiveRAM” or “FreeRam” functions to allocate or free the blocks of memory. At the end of your program call “FreeSegments” function.