Help - Dynamic Allocation from array

[blabla1]

Hello,

I need to write 2 functions:

1. MyMalloc
2. MyFree

____________________________

I have a 1000 bytes global array (which did not dynamic allocated).
I need to make "dynamic allocation" from this array.
For example - MyMalloc(50) ---> The program will allocate 50 bytes OF THE ARRAY'S SIZE.

------
MyFree(pointer) ---> I need to check if the pointer is in the array and free
the space.

It should be managed by blocks.
The array should also contain the manage variables (for me).


Thanks.

[vlad from moscow]

Now we all know that you need to write two functions. What else should we know about what you need to do?:)

[blabla1]

I need your help :)
I don't know how to do that.

[D80DSL3A]

This seems like an interesting problem.

I'm approaching it this way.
The array forming the buffer (arr) shall be allocated from in contiguous blocks, starting from the beginning.
We need to embed some data (manage variables) about each allocated block.
I will use 1 byte to indicate if a block is in use or not (inefficient, but simple).
I also need to know where the next block begins. In view of the small buffer size (1,000 bytes) I will use 2 bytes to record the size of the allocated block.

If I typedef:

typedef unsigned char u_char;// one byte = element size
typedef unsigned short int u_16;// 2 bytes = block sizes 

and point to the beginning of the array:

const u_16 buffSz = 1000;
uchar arr[buffSz];
u_char* pArr = arr;

I prepare the buffer (arr) for a first allocation by assigning the 1st 3 bytes
to indicate that the entire buffer is available for allocation:

pArr[0] = 0;// block is unused
// store the available block size = buffSz - 3 in 2 bytes
pArr[1] = (buffSz-3) & 0xFF;// low byte
pArr[2] = ((buffSz-3) >> 8) & 0xFF;// high byte 

The MyMalloc(u_16 size) function would step through arr until an available block of size+3 elements is found (allocation success) or not (allocation failure).
Suppose that u_char* iter is pointing to the beginning of an available block of adequate size (size+3).
I first save the (available) block length from the values stored for this:

u_16 len = iter[1] | (iter[2] << 8);// stored little endian (little byte 1st) 

Then write the new block length (size) and mark it as used:

iter[0] = 1;// in use
iter[1] = size & 0xFF;
iter[2] = (size >> 8) & 0xFF;

Finally, mark the remaining portion of the block that was allocated from:

iter[size+3] = 0;// available
iter[size+4] = (len-(size+3)) & 0xFF;
iter[size+5] = ((len-(size+3)) >> 8) & 0xFF;

disclaimer: I often over-complicate my solution methods.
I do have this working though.
I hope it gives you some ideas to work from.

[JLBorges]

fun2code, +1. Nice.

A small nit: MyMalloc(24) should return a pointer to storage that is aligned so that any object with a size of 24 bytes or less can be safely placed into it.

The simplest way would be to round off (upwards) the number of bytes requested (and the size of the block header) to an integral multiple of alignof(std::max_align_t).

[D80DSL3A]

JLBorges, Thanks!

I have been reflecting upon your "small nit" and I'm afraid I can't see the issues addressed by it clearly enough. I haven't studied memory usage models, but I have heard of the needs for byte alignment and padding in passing.

Where does the 24 byte figure come from?

I googled the undeclared identifier in your post alignof(std::max_align_t) and found a couple of threads at stackoverflow about it.
If you would explain a bit further I'd be glad to consider it more.

For the moment I'm experimenting with the MyFree() function.
I think a very simple version could just change the blocks status from used to available:

bool myFree(u_char* pBlock)
{
    if( is_valid(pBlock) )
    {
        pBlock[-3] = 0;// available now
        return true;
    }
    return false;// to indicate that an invalid pointer was passed
}

I'm also writing one which consolidates adjacent freed blocks into one large block (reducing the number of marked blocks and freeing the 3 byte header spaces as well) each time it is called. I would hope that this version could substantially delay the onset of allocation failures due to fragmentation.

Stepping into la-la land now, I am picturing a defragment() function which would re-arrange the data into adjacent contiguous blocks again. Any pointers to used blocks must be (somehow) "handed in" prior to calling defragment(), (or when calling it - use a variadic parameter list?) so they may be reassigned. Any pointers not handed in will become invalid and the blocks which were pointed to by them will be freed.
But this would be down the road.

[JLBorges]

> I can't see the issues addressed by it clearly enough. ...
> Where does the 24 byte figure come from?

The 24 byte figure was purely illustrative - it was just a number out of the hat. It could just as well have been: ' MyMalloc(32) should return a pointer to storage that is aligned so that any object with a size of 32 bytes can be safely placed into it.'


Objects in memory have a size; they use up a certain amount of memory. An implementation may also place restrictions on where in memory an object may reside; objects may have implementation-defined alignment requirements.

An object of type double would need sizeof(double) bytes starting at a memory address that is an integral multiple of alignof(double). Why alignment is required is buried deep in the processor architecture - the size of the address and data buses, addressing modes supported by the processor, how cache lines are organised and so forth. For instance, if we have a four byte integer, with one byte in one cache line, and the other three bytes in a different cache line, things would get either impossible or extremely inefficient.
http://msdn.microsoft.com/en-us/library/ms253949(v=vs.120).aspx

For example,

#include <iostream>
#include <type_traits>

#define PRINT(a) ( std::cout << #a << ": " << (a) )

#define PRINT_SZ_ALIGN(t) ( ( PRINT( sizeof(t) ) << "  " ), PRINT( alignof(t) ) << '\n' )

int main()
{
    struct A { char c ; int i ; short x ; double d ; char16_t u ; };
    PRINT_SZ_ALIGN(char) ; // by definition 1, 1
    PRINT_SZ_ALIGN(int) ; // 4, 4 on my implementation
    PRINT_SZ_ALIGN(short) ; // 2, 2 on my implementation
    PRINT_SZ_ALIGN(double) ; // 8, 8 on my implementation
    PRINT_SZ_ALIGN(char16_t) ; // 2, 2 on my implementation
    PRINT_SZ_ALIGN(A) ; // 32, 8 on my implementation
}

on my implementation an object of type A has a size of 32 bytes and an alignment of 8.

std::max_align_t is an implementation-defined type with ...
See: http://en.cppreference.com/w/cpp/types/max_align_t

Allocation functions are expected to return an address that is suitably aligned so that any object of the requested size can be placed into the allocated memory. For example, this code

A* pa = new ( MyMalloc( sizeof(A) ) ) A ;
if(pa) { /* do something */  pa->A::~A() ; MyFree(pa) ; }

requires that MyMalloc() allocate a block of memory which meets the alignment requirements of A.


A type can be over-aligned; its alignment requirement may exceed that of std::max_align_t. For instance:

struct B { alignas(128) char c ; }; // on my implementation, B is an over-aligned type
PRINT_SZ_ALIGN(B) ; // 128, 128 

Such types may be required to meet certain externally imposed constraints - for example, for the use of SSE instructions or for programming a DMA transfer to an external device. Standard allocation functions are not expected to take care of alignment requirements of over-aligned types.



> I'm also writing one which consolidates adjacent freed blocks into one large block...

It is an involved topic.
http://www.memorymanagement.org/articles/alloc.html
http://www.cs.northwestern.edu/~pdinda/icsclass/doc/dsa.pdf

[D80DSL3A]

Thanks for the further explanation.

I get that my present model only supports the storage of 1-byte sized objects.
It may be useful for storing raw character arrays only.

I get the idea of returning a pointer to a memory address that is divisible by 2,4,8 or 16 and I could do it if that were a fixed number (16 for example).
I'm going to give up on trying to identify alignof(std::max_align_t) .

From the links you gave I see it is a strictly C++11 object which returns "a POD type" and somehow takes the name of a type as its "argument".
There are simply too many things I don't know about present here at once, so I'm going to stop working on this problem (a hobbyists luxury).

Thanks again for the complement on the basic method. I'm sorry to have wasted your time on the alignment issue.

EDIT: The article at memorymanagement.org is quite good. It looks like I've implemented something similar to the "First Fit" algorithm described there.

[JLBorges]

> I'm going to give up on trying to identify alignof(std::max_align_t)

With an old Microsoft or GNU compiler, an equivalent expression would be:
__alignof(long double)

[D80DSL3A]

OK, I've recovered from being discouraged as I have thought of a workaround for the alignof(std::max_align_t) (or __alignof(long double) ) problem.
I can proceed if the user supplies this value.
ie: u_char* MyMalloc( u_16 Size, u_16 align );

@ JLBorges. Thanks again for your input.
Does my new approach here accomplish the desired pointer alignments?

Also, thanks to Framework for this thread: http://www.cplusplus.com/forum/general/89063/
wherein I learned about std::uintptr_t and it's usefulness in performing the necessary % (modulus) operation on an address.

I have modified the encoding for the 3 byte header. h[1], h[2] are still the same but now h[0] = 0 or 1+pad, instead of 0 or 1 only. This allows pointer validation and calculation of the used block size.

I doubt it will hurt to reveal my code for MyMalloc (which I have named Alloc) here.
First, a class declaration. A my buffer object:

template<u_16 myBuffSz>
class myBuffer
{
    public:
    u_16 Nblocks;

    myBuffer();
    u_char* Alloc(u_16 Size);
    u_char* Alloc(u_16 Size, u_16 align);
    u_char* Alloc(const char* data, u_16 Size);
    bool Free(u_char* base);
    bool is_valid(u_char* base);// check if pointing to a block start position
    bool is_valid(u_char* base, u_char& pad);// and return padding amount
    u_16 Size(u_char* base);
    u_char* begin() { return arr; }
    u_char* end() { return arr + myBuffSz; }

    private:
    u_char arr[myBuffSz];
};

//...

template<u_16 myBuffSz>
u_char* myBuffer<myBuffSz>::Alloc(u_16 Size, u_16 align)// returns NULL if no Size block available
{
    u_char* iter = arr;

    while( iter < arr+myBuffSz )
    {
        u_16 len = iter[1] | (iter[2] << 8);// stored little endian (little byte 1st)

        if( iter[0] == 0 )// block is unused
        {
            std::uintptr_t intAddy = (std::uintptr_t)(iter + 3);// address following 3 byte header block
            u_16 pad = align - intAddy%align;// offset to beginning of "usable portion" of block
            if( pad == align ) pad = 0;
            u_16 SizeTotal = Size + pad;// actual needed block size

            if( len >= SizeTotal + 3 )// block is large enough
            {
                iter[ SizeTotal+3 ] = 0;// mark remainder of block as unused
                iter[ SizeTotal+4 ] = (len-(SizeTotal+3)) & 0xFF;// mark start of next block
                iter[ SizeTotal+5 ] = ((len-(SizeTotal+3)) >> 8) & 0xFF;

                iter[0] = 1 + pad;// new coding
                iter[1] = SizeTotal & 0xFF;
                iter[2] = (SizeTotal >> 8) & 0xFF;

                ++Nblocks;
                cout << "pBlock - begin() = " << ( (iter + pad + 3)-begin() ) << endl;
                cout << "pad = " << pad << endl;
                return (iter + pad + 3);
            }
        }
        iter += len + 3;// next block (or end)
    }
    return NULL;
}

I test this by allocating space for arrays of several types, then write to and read from these memory spaces using pointers to these types.

// test struct
struct A
{
    char ch;
    int ix;
    double dx;
};

ostream& operator<<( ostream& os, const A& rA )
{
    os << "ch = " << rA.ch << " ix = " << rA.ix << " dx = " << rA.dx << '\n';
    return os;
}


int main()
{
 //   std::cout << alignof(std::max_align_t) << '\n';

    myBuffer<1000> buff_1;
    u_16 i = 0;// for looping

    // allocate space for 6 integers
    int* pBlock_int = (int*)buff_1.Alloc( 6*sizeof(int), 4);
    if( pBlock_int )
    {
        u_char* pBlock_ch = (u_char*)pBlock_int;
        pBlock_int[0] = -3; pBlock_int[1] = 2758942; pBlock_int[2] = -1544; pBlock_int[3] = 7; pBlock_int[4] = 45; pBlock_int[5] = -31;
        cout << "block_1 size = " << buff_1.Size( pBlock_ch  ) << endl;
        std::uintptr_t intAddy = (std::uintptr_t)(pBlock_int);
        cout << "pBlock =  " << intAddy << " pBlock%4 = " << intAddy%4 << endl;// verify alignment
        for( i = 0; i < 6; ++i)
            cout << pBlock_int[i] << " ";
    }
    else
        cout << "Alloc() failed for 6 ints" << endl;

    cout << endl << endl;
    // allocate space for 4 floats
    float* pBlock_f = (float*)buff_1.Alloc( 4*sizeof(float), 4);
    if( pBlock_f )
    {
        u_char* pBlock_ch = (u_char*)pBlock_f;
        pBlock_f[0] = -3.142f; pBlock_f[1] = 275.8942f; pBlock_f[2] = -154.3f; pBlock_f[3] = 0.0046f;
        cout << "block size = " << buff_1.Size( pBlock_ch  ) << endl;
        std::uintptr_t intAddy = (std::uintptr_t)(pBlock_f);
        cout << "pBlock =  " << intAddy << " pBlock%4 = " << intAddy%4 << endl;// verify alignment
        for( i = 0; i < 4; ++i)
            cout << pBlock_f[i] << " ";
    }
    else
        cout << "Alloc() failed for 4 floats" << endl;

    cout << endl << endl;
    // allocate space for 3 A's
    cout << "sizeof(A) = " << sizeof(A) << endl;
    A* pBlock_A = (A*)buff_1.Alloc( 3*sizeof(A), 8);
    if( pBlock_A )
    {
        u_char* pBlock_ch = (u_char*)pBlock_A;
        pBlock_A[0].ch = 'a'; pBlock_A[0].ix = -7; pBlock_A[0].dx = 3.1416;
        pBlock_A[1].ch = 'b'; pBlock_A[1].ix = 72; pBlock_A[1].dx = 55.0;
        pBlock_A[2].ch = 'c'; pBlock_A[2].ix = 49; pBlock_A[2].dx = -0.023;
        cout << "block size = " << buff_1.Size( pBlock_ch  ) << endl;
        std::uintptr_t intAddy = (std::uintptr_t)(pBlock_A);
        cout << "pBlock =  " << intAddy << " pBlock%8 = " << intAddy%8 << endl;// verify alignment
        for( i = 0; i < 3; ++i)
            cout << pBlock_A[i];
    }
    else
        cout << "Alloc() failed for 3 As" << endl;


    cout << endl;
    return 0;
}

Output:

pBlock - begin() = 4
pad = 1
block_1 size = 24
pBlock =  2292572 pBlock%4 = 0
-3 2758942 -1544 7 45 -31

pBlock - begin() = 32
pad = 1
block size = 16
pBlock =  2292600 pBlock%4 = 0
-3.142 275.894 -154.3 0.0046

sizeof(A) = 16
pBlock - begin() = 56
pad = 5
block size = 48
pBlock =  2292624 pBlock%8 = 0
ch = a ix = -7 dx = 3.1416
ch = b ix = 72 dx = 55
ch = c ix = 49 dx = -0.023

Process returned 0 (0x0)   execution time : 0.047 s
Press any key to continue.

Does this testing verify that I'm doing all this right? Or, could this output be generated even if my Alloc() is returning improperly aligned pointers?
EDIT4: Answered my own question (yes). Changing A* pBlock_A = (A*)buff_1.Alloc( 3*sizeof(A), 8); to A* pBlock_A = (A*)buff_1.Alloc( 3*sizeof(A), 2); produces the same output except

pad = 1
pBlock =  2292624 pBlock%8 = 4

the array of 3 A's is aligned to a 4 byte boundary.

EDIT: The 1st 3 numbers output for each type: pBlock-begin(), pad and block size, all indicate that the allocations are occurring exactly as desired:

| 3 |1|       24     | 3 |1|      16      | 3 |  5  |      48...
.......^....................^........................^
.......4....................32.......................56

EDIT2: OK, I feel a bit dumb about this comment now:

...and somehow takes the name of a type as its "argument".

when that is exactly what I'm doing here: sizeof(int). I must have been frustrated.

EDIT3: I realize now that lines 41-43 in Alloc() may overwrite the header for the following block if the remainder of the just allocated block is < 3 bytes.
Although this doesn't affect the current testing, I will modify Alloc() soon to deal with a uselessly short remainder block.

EDIT5:
@blabla1. This is your thread. Any comments or questions so far?

[blabla1]

Hi - Thank you all, thank you very much!
fun2code - thanks for your intersting answers.

But - it's a bit complicated for me.

I found this on the internet - I don't know if it's good enough for me... what do you think? Is the allocated areas are really "On the 1000 bytes array" ?

#define MAXMEMBLOCKS 1000

typedef struct 
{
    int BlockSize;
    void* BlockPointer;
} Block;

typedef struct 
{
    int totalSize;
    int current;
    Block arrBlocks[MAXMEMBLOCKS];
} currentMemory;


currentMemory mem;


void *MyMalloc(int AllocateSize)
{
    if (mem.current < MAXMEMBLOCKS) 
	{
        mem.current += AllocateSize;
		mem.arrBlocks[mem.current].BlockSize = AllocateSize;
        mem.arrBlocks[mem.current].BlockPointer = malloc(AllocateSize);
        return mem.arrBlocks[mem.current++].BlockPointer;
    } 
	else {
        // you needed more memblocks than estimated
        return NULL;
    }
};

int MyFree(void *pointer) 
{
    int i;
    for (i = 0; i < mem.current; i++) 
	{
        if (mem.arrBlocks[i].BlockPointer == pointer) 
		{
			mem.totalSize -= mem.arrBlocks[i].BlockSize;
            free(mem.arrBlocks[i].BlockPointer);
            mem.current--;
            return 0;
        }
    }
    // you tried to free a block wich hasn't been allocated through MyMalloc()
    return -1;
}

[D80DSL3A]

I'm glad you found the answers interesting. Yes, it's a bit complicated.

The code you found online may work (quite Well!) but I think it misses the point of the exercise, which is to allocate memory "dynamically" from a given statically declared array.

I have a 1000 bytes global array (which did not dynamic allocated).
I need to make "dynamic allocation" from this array.

The code you found is calling malloc() and free() (the "real" versions of them) and so it is making allocations from "the free store" as usual.

I read the requirement:

The array should also contain the manage variables (for me).

to mean that any "manage data" must be stored in the static array itself, hence my method with the 3 byte header spaces for each block in the array.

I'm sorry it got more complicated with my move making a template class out of the array.

[blabla1]

Hello,
I have something to add - I need to save two bytes for "management" of an array.
For instance, if I got MyMalloc(50) ---> I should save two bytes (int) in order to save the number 50!
It's not a smart idea but it's also not the point of the exercise.

How can I do that?
Any suggesttions?


Thanks.

[D80DSL3A]

I did it above using 3 bytes per allocated block instead of 2.

Do you have a complete problem statement (as given to you for the assignment) that you could post so I can understand it more clearly?

[blabla1]

Nope.. it's not in english.

It should be simpler.


1) Negative number = a dynamic allocated memory in the size of the number.
2) Positive number = a dynamic allocated memory which has been freed (aka: "Block").

In MyMalloc --- Run over the global array and search for negative number.
If the allocatesize (the number which MyMalloc gets) is smaller than the free space --- you should return a pointer.
If not --- return null.

I don't know how to write it in C. It's a bit complicated for me.
I hope you can help me.


Thanks!!!

[D80DSL3A]

That sounds good, using the sign to indicate if a block is available (negative) or has been allocated already (positive).

I have worked out a possible solution. I went for simple as possible, but I must know if it will meet your assignments requirements.

Allocation would be from a static array of short int (2 bytes each)

const unsigned short size = 500;
    short buff[size] = {0};// 500*2 = 1000 bytes 

.
Using type short integer makes reading and writing the manage data to the array easy.

To begin with, MyMalloc(n) allocates space for n shorts and returns a short* (pointer to short) to the start of the allocated block. If it must return a pointer to one byte objects (ie char), this could be changed.

MyFree(short* pBlock) simply changes the sign of that blocks manage variable (to negative) so it is marked as free again.

The basic idea in MyMalloc(n) would be this:
Start at buff[0] where the first manage variable is. Check if this block is available (buff[0] < 0) and if it is big enough ( n+1 < -buff[0] ).

If so, this block can be allocated from. To do this assign buff[0] = n (the new block size) to mark it as used. You will return (buff+1) as the pointer to the block (one past the manage variable for that block) but there is one more thing to do. You must mark the start of the next block, n+1 elements ahead.
The next block is leftover from the big block we just allocated from. The big block had length = buff[0] before we allocated n+1 shorts from it, so the remaining block size, newSize = length - (n+1).
Assign buff[n+1] = -newSize (negative for available).

If the first block is not available we use buff[0] to jump straight to the next blocks manage variable. If a block has its manage variable at buff[i] and length = buff[i], the next blocks manage variable is at buff[i+length+1].

Does this seem close to what you're seeking?

[blabla1]

First of all - I really appriciate your help, you are working very hard in order to find me an appropriate solution. In that context I would like to mention that this exercise is one of the hardest exercises I have ever had given in the university.

Back to your solution -
1. I would have had to prefer using an int statically allocated 1000 bytes array rather using unsigned short.

2. MyFree(int* pBlock) should be a very simple method but a bit tricky for the following reasons: When you want to free a dynamiclly allocated area you must check the following things respectively:
2a. Check if the given pointer is a "real pointer" which means that you have to check that the given pointer points to the statically array area (1000 bytes). [If not - do nothing].
2b. You can assume that the given pointer points to the beginning of one of the allocated blocks and free it.
2c. If the freed block closes to another empty block, those two blocks will consolidate into one big block (pay attention that the freed block can be between two freed blocks - in that case you should consolidate the three of them into one big block).

3. The areas (dynamiclly allocated arrays) should be given by "first-fit" method.

4. I agree with your solution idea.

I hope you can help me one more time to write this solution in C, it's a bit complicated to me but I think it's very easy to you to write this.

Thanks again.

[D80DSL3A]

You're welcome for the help. It is an interesting exercise. That's why it caught my attention.

I think we agree down to one thing then - the data type for the buffer array as
int (you propose) versus short (my idea). I propose using a signed type (short). The unsigned short was the array size.

const unsigned short int size = 500;// array size
short int buff[size] = {0};// 500*2 = 1000 bytes 

I want short because that is the size (2 bytes) which the manage variable is. Choosing a compatible size (2 bytes=short) for the array elements will make the task somewhat easier.

I program almost exclusively in C++ so you may have to help take me back to c.
I'm fine with a solution involving one global array (the allocation buffer) and two global functions.

I shall try to help, which is a lot harder than just giving away code (a big no-no).

I will start by showing some test code from my main function. This will demonstrate usage (to see if it fits what you expect), but mostly it demonstrates what's going on in the allocation array (buff).

In the code below I initialize buff for a first allocation, then allocate 3 blocks in a row from it (10, 15 and 20 elements). These should be allocated one after another from buff, as the "first fit" algorithm would require.
I write values to the allocated block, a count from 1 to n.
I then call printBuff(80) to display the first 80 elements of buff.

Next, I free the 2nd (middle 15 element) block using a simple version of MyFree which only marks the block as free - no coalescence yet.

Next, I allocate a 4th block, but make it too big (18 elements) to fit in the just freed block. Block 4 should be allocated to follow block 3. I printBuff(80) again so we can see this.

Finally, I allocate for a 5th block, making it small enough (9 elements) to fit into the previously freed 15 element block. I printBuff(80) once more so the final result can be seen. Look carefully to see the 15 element block split into 9 elements and 5 elements (1 element lost to new manage variable). Notice that the 5 element block is marked as available (as it should be).

Here's the code:

const unsigned short size = 500;
short buff[size] = {0};

// definition of short* MyMalloc( unsigned short n )

// super simple for now
void MyFree( short* pBlock )
{
    pBlock[-1] *= -1;// marked as free
    return;
}

void printBuff( unsigned short numEle )
{
    for( unsigned short i = 0; i < numEle; ++i )
    {
        cout << buff[i] << " ";
        if( i%20 == 19 ) cout << endl;// 20 elements per line
    }
    cout << endl;
}

int main()
{
    // prepare the buffer for a first allocation
    buff[0] = -1*(size-1);// The first "manage" variable. Marks entire buffer as available (minus 1st element)
    cout << "buff = " << buff << endl;// beginning address

    // allocate 3 blocks
    unsigned short N = 10;
    short* pBlock_1 = MyMalloc(N);
    cout << "pBlock_1 = " << pBlock_1 << endl;
    unsigned short i = 0;
    for( i = 0; i < N; ++i ) pBlock_1[i] = i+1;

    N = 15;
    short* pBlock_2 = MyMalloc(N);
    cout << "pBlock_2 = " << pBlock_2 << endl;
    for( i = 0; i < N; ++i ) pBlock_2[i] = i+1;

    N = 20;
    short* pBlock_3 = MyMalloc(N);
    cout << "pBlock_3 = " << pBlock_3 << endl;
    for( i = 0; i < N; ++i ) pBlock_3[i] = i+1;

    printBuff(80);// following 3 allocations

    MyFree( pBlock_2 );// free the middle 15 element block

    // allocate 2 more blocks
    N = 18;
    short* pBlock_4 = MyMalloc(N);
    cout << "pBlock_4 = " << pBlock_4 << endl;
    for( i = 0; i < N; ++i ) pBlock_4[i] = i+1;

    printBuff(80);// block 4 at end?

    N = 9;
    short* pBlock_5 = MyMalloc(N);
    cout << "pBlock_5 = " << pBlock_5 << endl;
    for( i = 0; i < N; ++i ) pBlock_5[i] = i+1;

    printBuff(80);// middle block split?

    cout << endl;
    return 0;
}

And, the resulting output:

buff = 0x406020
pBlock_1 = 0x406022
pBlock_2 = 0x406038
pBlock_3 = 0x406058
10 1 2 3 4 5 6 7 8 9 10 15 1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 20 1 2 3 4 5 6 7 8 9 10 11 12
13 14 15 16 17 18 19 20 -452 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

pBlock_4 = 0x406082
10 1 2 3 4 5 6 7 8 9 10 -15 1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 20 1 2 3 4 5 6 7 8 9 10 11 12
13 14 15 16 17 18 19 20 18 1 2 3 4 5 6 7 8 9 10 11
12 13 14 15 16 17 18 -433 0 0 0 0 0 0 0 0 0 0 0 0

pBlock_5 = 0x406038
10 1 2 3 4 5 6 7 8 9 10 9 1 2 3 4 5 6 7 8
9 -5 11 12 13 14 15 20 1 2 3 4 5 6 7 8 9 10 11 12
13 14 15 16 17 18 19 20 18 1 2 3 4 5 6 7 8 9 10 11
12 13 14 15 16 17 18 -433 0 0 0 0 0 0 0 0 0 0 0 0

Can you see that all of the allocation were made as expected?
Let me know if we're still in agreement about the solution.
Array of short int OK?

[blabla1]

Can you see that all of the allocation were made as expected? - YES
Let me know if we're still in agreement about the solution. - YES
Array of short int OK? - YES

Two things:
1. Where is MyMalloc in your solution?
2. You should extend MyFree method as I said before.

[D80DSL3A]

I'm glad the solution method seems good to you.

About those two missing items...
I'll be attempting to guide you to those two things. So,
1) MyMalloc is deliberately hidden. It would be the 1st function to develop.
2) I'm aware of the further requirements which MyFree will need to meet, as you have explained them well.
Some things, like verifying that a pointer ( pBlock) points to someplace in the array should be as easy as checking that pBlock >= buff and < (buff+size). We could even easily verify if pBlock is pointing to the beginning of an actual block.

Other things, like coalescence of adjacent freed nodes I don't even have worked out yet. But I feel that I see a clear solution.

I hope you're OK with this.
Can you take a stab at MyMalloc yourself given all that's been written above describing the solution method?

I will show a shell of the function I have. Maybe you can complete it?

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!
        {
            // assign next blocks manage variable (reread posts)
            // assign this blocks manage variable
            return // pointer to one element past this blocks manage variable
        }
        i += length + 1;// otherwise, try the next block
    }
    return NULL;// no suitable block found
}

Please feel free to ask questions.