I want to tell you that you're really help me and I think I wouldn't had done this.
I tried to complete MyMalloc (which is actually yoursMalloc :))
I need to send/mail it to my teacher in a few hours so I don't have much time to think about solution for MyFree (I hope you can share your solution of MyFree).
short* MyMalloc( unsignedshort n )
{
unsignedshort i = 0;// for stepping through array
while( i < size )
{
short data = buff[i];// save value of the "manage" variable for this block
bool available = false;// presuming block unavailable
if( data < 0 )// this block is available
{
available = true;
data *= -1;// we need this to be positive now
}
unsignedshort length = (unsignedshort)data;
if( available && (length > n) )// allocate!
{
buff[length + n + 1] = length - (n+1); // assign next blocks manage variable
// assign this blocks manage variable
buff[i] = length;
return (&(buff[i]));// pointer to one element past this blocks manage variable
}
i += length + 1;// otherwise, try the next block
}
return NULL;// no suitable block found
};
I don't HAVE anything more written for MyFree right now. I was going to do that when it looked like this was going to go that far.
Sorry! Christmas was last week :)
As for MyMalloc, I wish you had more time to examine the program output (I think it's really clear there). The values you have filled in are all off.
Line 16 is very close. You are marking the "remainder portion" of the block, which is still free, so its manage variable should be negative: -1*(length - (n+1));<_ I just noticed this could be 0 (bad).
It should be (length > n+1) on line 14.
EDIT: Or better yet, check it for zero because this is an exact fit and no new manage variable need be created. It can just be "reclaimed" with buff[i] *= -1;
There's really a bit of detail left here.
Line 19. How large is the block being allocated? This is the value for buff[i] (and positive-this block is taken).
Line 21. &buff[i] points to the manage variable. Point one more element toward the end of buff.
That would give you a functional MyMalloc(). You should be able to compile and use my main code with it.
You will need to also add:
1 2
#include<iostream>
usingnamespace std;// probably OK this case
short* MyMalloc( unsignedshort n )
{
unsignedshort i = 0;// for stepping through array
while( i < size )
{
short data = buff[i];// save value of the "manage" variable for this block
bool available = false;// presuming block unavailable
if( data < 0 )// this block is available
{
available = true;
data *= -1;// we need this to be positive now
}
unsignedshort length = (unsignedshort)data;
if( available && (length > n+1) )// allocate!
{
buff[n + 1] = -1 * (length - (n+1)); // assign next blocks manage variable
// assign this blocks manage variable
buff[i] = n;
return (&(buff[i+1]));// pointer to one element past this blocks manage variable
}
i += length + 1;// otherwise, try the next block
}
return NULL;// no suitable block found
};
EDIT:
What do I need in order to prevent using " buff[0] = size " in main().
I need to send only MyMalloc and MyFree without main(), so what can I do in order to manage the first cell?
EDIT2: In line 16 I think I fixed it:
buff[(length * (-1) + size) + n + 1] = -1 * (length - (n+1)); // assign next blocks manage variable
I'm continuing with this, so post back if your next assignment leaves room for finishing this one.
I have MyFree coalescing well for all cases.
I fixed details of MyMalloc so that allocations are not made from a block if its length < n + 2 (length=n+2 leaves a remainder block with length=1), unless length = n (perfect fit) when it just reclaims the block (no new manage variable, the number of blocks stays constant).
#include <stdio.h>
#include <stdlib.h>
constunsignedshort size = 500;
short buff[size] = {0};// 500*2 = 1000 bytes
short* MyMalloc( unsignedshort n )
{
if (buff[0] == 0)
{
buff[0] = (-1) * size;
}
unsignedshort i = 0;// for stepping through array
while( i < size )
{
short data = buff[i];// save value of the "manage" variable for this block
bool available = false;// presuming block unavailable
if( data < 0 )// this block is available
{
available = true;
data *= -1;// we need this to be positive now
}
unsignedshort length = (unsignedshort)data;
if( available && (length > n+1) )// allocate!
{
buff[(length * (-1) + size) + n + 1] = -1 * (length - (n+1)); // assign next blocks manage variable
// assign this blocks manage variable
buff[i] = n;
return (&(buff[i+1]));// pointer to one element past this blocks manage variable
}
i += length + 1;// otherwise, try the next block
}
return NULL;// no suitable block found
};
void MyFree( short* pBlock )
{
bool isValid = false;
short i = 0;
short count;
short last = 0;
while ((!isValid) && (i < size))
{
count = abs(buff[i]);
if ((&(buff[i+1])) == pBlock)
{
isValid = true;
pBlock[-1] *= -1;// marked as free
short* pointNextBlock = &(buff[1 + i + ((-1) * pBlock[-1])]);
if (pointNextBlock[0] < 0)
{
int sum = pointNextBlock[0] + pBlock[-1] - 1;
pBlock[-1] = sum;
pointNextBlock[0] = 0;
}
if ((i != 0) && (last >= 0))
{
short* pointLastBlock = &(buff[last]);
if (pointLastBlock[0] < 0)
{
int sum = pointLastBlock[0] + pBlock[-1] - 1;
pointLastBlock[0] = sum;
pBlock[-1] = 0;
}
}
}
last = i;
i += count + 1;
}
return;
}
int main()
{
short* bla = MyMalloc(3);
MyFree(bla);
short b;
scanf("%a");
return 0;
}
My functions are working pretty good.
MyMalloc checks that an allocation is either a perfect fit (length=n), or that any remainder block length will be >= 1 (don't want any zero length blocks, or to overwrite next manage variable). This version handles that:
short* MyMalloc( unsignedshort n )
{
unsignedshort i = 0;
while( i < size )
{
short data = buff[i];
bool available = false;
if( data < 0 )
{
available = true;
data *= -1;
}
unsignedshort length = (unsignedshort)data;
if( available && (length >= n) )// allocate!
{
if( length > n + 1 )// so that remaining block length >= 1
{
buff[i+n+1] = -1*(length - (n+1));
buff[i] = (short)n;
return buff+i+1;
}
if( length == n )// exact fit. Merely reclaim
{
buff[i] *= -1;
return buff+i+1;
}
}
i += length + 1;
}
return NULL;
}
MyFree is doing free block coalescence well, but I think I have an off-by-one error when freeing the last allocated block (which is actually a coalescence operation with the remainder of buff. Lines 25 to 27 below execute). More testing needed. Freeing all blocks leaves buff[0] = -500 but should = -499 (initial value).
bool MyFree( short* pBlock )
{
short i = 0;
short iPrev = 0;
short iNext = 0;
while( i < size )
{
short length = buff[i]<0 ? -buff[i] : buff[i];
iNext = i + length + 1;
if( (buff[i] > 0) && (pBlock == (buff+i+1)) )// free this block
{
// 4 cases
if( (i>0) && (buff[iPrev]<0) && (buff[iNext]<0) )// free all 3 blocks
{
buff[iPrev] = -1*( (iNext - iPrev) - buff[iNext] + 1 );
if( (iNext - buff[iNext]) >= size )
buff[iPrev] += 1;// due to coalescence with end
}
elseif( (i>0) && (buff[iPrev]<0) )// free prev + this block
buff[iPrev] = (iPrev - iNext) + 1;
elseif( buff[iNext] < 0 )// free this + next block
{
buff[i] = buff[iNext] + i - iNext;
if( (iNext - buff[iNext]) >= size )
buff[i] += 1;// due to coalescence with end
}
else// free this block only
buff[i] *= -1;
returntrue;
}
iPrev = i;
i = iNext;
}
returnfalse;
}
EDIT 1: Lines 6 through 13 in MyMalloc are embarrassing. I won't try to fix it here, but I'm struggling with combining usage of signed and unsigned types there.
Edit 2: I have arrived at an answer to this question of yours from several posts ago:
What do I need in order to prevent using " buff[0] = size " in main().
I need to send only MyMalloc and MyFree without main(), so what can I do in order to manage the first cell?
At first I was confused about the issue, but I think I see it now.
Answer: Switch to C++ so you can use objects which have constructors.
HAH!
EDIT 3: Some further musings about C++.
My technical background started via a youthful interest in physics. I was (forcibly) introduced to programming in two intro courses (Pascal) required for my B.S. in physics.
Hobbying took me to c for years. I like nice clean procedural programming too. Consider the overall simplicity of the current solution method vs. the template class based solution I was working on earlier in this thread.
That said however (here comes the C++ pitch),...
Virtual functions?
Template classes?
Function overloading?
Operator overloading?
OOP, in general?
...and so on...
I am astounded at the depth (and beauty) of the abstraction present in the language model.
I never expected to encounter this outside the fields of mathematics and physics.
