Memory Allocation & Release in O(1)

[electroRF]

Thanks guys.

I'm still working on the double linked list implementation - it's very not trivial for me.

 

[electroRF]

guys,

Regarding memory alignment.

I read in some places that memory blocks should be multiples of word size, i.e. 4 bytes for 32-bit systems.

However, in this lecture, I read that:
To simplify memory alignment
o Make all memory blocks a multiple of the header size
o Ensure header is aligned with largest data type (e.g., long)

I thought it is just necessary to have both header and memory block each some multiple of word-size - i.e. the memory block does NOT have to be a multiple of the header.

How does it simpify to increase the header so that all memory blocks will be a multiple of the header?

 

[electroRF]

Hi guys,

I thought of a solution for the 10 / 50 / 200 Bytes problem.

How about this:
1. 10-byte blocks could be allocated on every 10-byte step - i.e. addresses 0, 10, 20, 30, 40, 50, 60, .....
2. 50-byte blocks could be allocated on every 50-byte step - i.e. addresses 0, 50, 100, 150, 200, 250, ...
3. 200-byte blocks could be allocated on every 200-byte step - i.e. addresses 0, 200, 400

struct freelist
{
struct freelist *pprev, *pnext;
} freelist10, freelist50, freelist200;

4. 3 lists will be initialized at first, with all free spaces.


5. each list will point on the available block -> therefore it'd take O(1).

The disadvantages here are:
1. that if say addresses 10 to 60 are available, the algorithm will not count it as an available space for a 50-byte block.

2. the header will be 3 times bigger.

Is there a better way?