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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
I'm sorry you pushed your deadline so close.

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

What do I miss?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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()

Take a look please.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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;
}
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdio.h>
#include <stdlib.h>


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;
}
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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?
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.
Last edited on
Topic archived. No new replies allowed.
Pages: 12