J
jacob navia
I have been reworking the heap allocation module. This module should be
the base of many containers since it is specialized in allocating a lot
of objects all of the same size.
I have discarded the bitmap I maintained to track the free list for a
slightly more sophisticated approach.
I allocate a table of pointers to pages of CHUNK_SIZE objects. Since one
of the constraints is that no active object can be moved, it is not
possible to just allocate a single strip of objects and reallocate it
later. The reason for maintaining active objects fixed is that user
pointers to those objects could exist and that there is no way to
update those if the object is moved.
The organization is then :
A resizable vector of pointers that holds the start addresses of pages
of a fixed quantity of allocated objects.
When an object is freed, its "Next" pointer will be updated to
contain INVALID_POINTER_VALUE, that for the time being I have defined
as ((void *)~0ULL). This allows me to distinguish active objects
from freed ones, assuming that all client objects have a pointer at
their first position. This is always true for the containers, but limits
the interest of this schema for other uses.
The heap contans an implementation of iterators, that allow a client
program to visit all objects in the heap. Since all complex containers
like trees, (scapegoat trees) and others use a heap, I get an
implementation of iterators in all those containers for free without
having to write an iterator for each one.
The source code is available at
http://code.google.com/p/ccl/
The code size has been reduced: all the heap object takes now
around 1500 bytes of code in a x86.
jacob
the base of many containers since it is specialized in allocating a lot
of objects all of the same size.
I have discarded the bitmap I maintained to track the free list for a
slightly more sophisticated approach.
I allocate a table of pointers to pages of CHUNK_SIZE objects. Since one
of the constraints is that no active object can be moved, it is not
possible to just allocate a single strip of objects and reallocate it
later. The reason for maintaining active objects fixed is that user
pointers to those objects could exist and that there is no way to
update those if the object is moved.
The organization is then :
A resizable vector of pointers that holds the start addresses of pages
of a fixed quantity of allocated objects.
When an object is freed, its "Next" pointer will be updated to
contain INVALID_POINTER_VALUE, that for the time being I have defined
as ((void *)~0ULL). This allows me to distinguish active objects
from freed ones, assuming that all client objects have a pointer at
their first position. This is always true for the containers, but limits
the interest of this schema for other uses.
The heap contans an implementation of iterators, that allow a client
program to visit all objects in the heap. Since all complex containers
like trees, (scapegoat trees) and others use a heap, I get an
implementation of iterators in all those containers for free without
having to write an iterator for each one.
The source code is available at
http://code.google.com/p/ccl/
The code size has been reduced: all the heap object takes now
around 1500 bytes of code in a x86.
jacob