Help - Dynamic Allocation from array

Pages: 12
I waited for you... ;)

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).

 1234567891011121314151617181920212223242526 short* MyMalloc( unsigned short n ) { unsigned short 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 } unsigned short length = (unsigned short)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 };
Last edited on
closed account (D80DSL3A)

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:
 12 #include using namespace std;// probably OK this case
Last edited on
It's not working:

What do I miss?

 1234567891011121314151617181920212223242526 short* MyMalloc( unsigned short n ) { unsigned short 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 } unsigned short length = (unsigned short)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
Last edited on
I tried to write MyFree()

 1234567891011121314151617181920212223242526272829303132333435363738394041 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]; 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]; pointLastBlock[0] = sum; pBlock[-1] = 0; } } } last = i; i += count + 1; } return; }
closed account (D80DSL3A)
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).
I would like to see what you got.

Here is the entire solution.
It works fine but may not work with some parameters.

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192 #include #include const unsigned short size = 500; short buff[size] = {0};// 500*2 = 1000 bytes short* MyMalloc( unsigned short n ) { if (buff[0] == 0) { buff[0] = (-1) * size; } unsigned short 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 } unsigned short length = (unsigned short)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; }
closed account (D80DSL3A)
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:
 12345678910111213141516171819202122232425262728293031 short* MyMalloc( unsigned short n ) { unsigned short i = 0; while( i < size ) { short data = buff[i]; bool available = false; if( data < 0 ) { available = true; data *= -1; } unsigned short length = (unsigned short)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).
 123456789101112131415161718192021222324252627282930313233343536373839 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 } else if( (i>0) && (buff[iPrev]<0) )// free prev + this block buff[iPrev] = (iPrev - iNext) + 1; else if( 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; return true; } iPrev = i; i = iNext; } return false; }

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?