Wednesday, August 31, 2016

What "malloc" does ?

the word "malloc" derived from the term "memory allocation"

Again, imagine you have a computer that has 16 bit memory like follow.

| 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

What malloc does is reserve certain part of a memory that we requested.

Imagine about a situation where you need to create an array with 5 char type elements.

For the work you are going to use malloc
----------------------------------------------------------

First you need to tell what type of the elements that you are going to store

In our case its "char"

Why we need to tell it to computer ?

you know that hardware works with bites not with high level types like char/string/int .. those are some terms that we made for our ease.

so convert our thoughts to bites we need to tell that this is the data type we are going to use.. Then program can convert it to bites and tell it to computer

for our case we can do it like this

return_we_expect = (char*) .....

ok.........

then we need to use malloc for allocation for malloc we should give number of bytes that it should allocate from memory

if you know the exact bite value of your data type you can do it like this.

1char = 1bit
#of elements = 5
malloc(5 * 1)

but when it comes to the complex data types it is hard to memories the bit values.. so we can do a trick ..

as i toled, program knows bit values per each data type. why not we ask help from it :)

malloc(5 * sizeof(char))

yes..... now we can combine this thing

return_we_expect = (char*)malloc(5*sizeof(char))

Then what mallock does ?

----------------------------------------------------------------------
it simply allocates memory according to our scenario.

in our case malloc need to allocate 5*1 = 5 bits.

Unfortunately, meantime we are discussing above, 5 of our 16 bit memory has occupied by a nother program :( . you can identify them by X marks


| X | 0 | X | 0 |

| 0 | X | 0 | 0 |

| 0 | 0 | 0 | X |

| 0 | X | 0 | 0 |

But malloc dose not give up ..

In the basics of array it should do a adjacent memory locations.

so malloc need to find out a better place that has 5 empty slots..

| X | 0 | X | 0 |

| 0 | X | 1 | 1 |

| 1 | 1 | 1 | X |

| 0 | X | 0 | 0 |

Ok done ....

now malloc done its work .. but how we can identify the location malloc allocated... That's why it returns the address of start point and size of the allocation.

Than we can use the location



linked list are not stored in adjacent memory locations as in array

Imagine that your computer has a 16 bit memory which is initially nil, like follow

|  0  |  0  |  0  |  0  |

|  0  |  0  |  0  |  0  |

|  0  |  0  |  0  |  0  |

|  0  |  0  |  0  |  0  |

0 represents the free spaces
1 represents the occupied spaces
* represents the filed spaces

If you define a array with 5 elements whare 1 element takes 1 bit of memory it will allocate the memory as follow.

|  1  |  1  |  1  |  1  |

|  1  |  0  |  0  |  0  |

|  0  |  0  |  0  |  0  |

|  0  |  0  |  0  |  0  |

When you fill the array with first elements it will fill the 0th allocation

| * | 1 | 1 | 1 |

| 1 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

and when its second

| * | * | 1 | 1 |

| 1 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

But if you define an linked list for the same perpose, allocation is one at the initiation. That allocation is for the details of "Where to start".

| 1 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

When you fill the first element it uses the allocated space as follow. Additionaly it allocates a free space for next element

| * | 1 | 0 | 0 |

| 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

Then we can add second element

|  *  |  *  |  1 |  0  |

|  0  |  0  |  0  |  0 |

|  0  |  0  |  0  |  0 |

|  0  |  0  |  0  |  0 |

Think that while we adding the 3rd element 4th and 5th location were allocated by a nother process.

We use x for the locations allocated by third party

|  *  |  *  |  1  |  X |

|  X |  0  |  0  |  0 |

|  0  |  0  |  0  |  0 |

|  0  |  0  |  0  |  0 |

No Problem with that ... When we fill the 3rd element it will allocate 5th space for the 4th element of array list as follow


|  *  |  *  |  *  |  X |

|  X |  1  |  0  |  0  |

|  0  |  0  |  0  |  0  |

|  0  |  0  |  0  |  0  |

This is ok becase linked list keeps the location of next element as metadata..

As you see in Linked list we don't need any order for memory allocation. so we can say that  linked list are not stored in adjacent memory locations as in array.