Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Updates to the containers library

Thread Tools

Updates to the containers library

jacob navia
Posts: n/a
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

The code size has been reduced: all the heap object takes now
around 1500 bytes of code in a x86.


Reply With Quote

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
Are sequence containers not a subset of general containers? Sebastian Mach C++ 5 10-06-2012 07:54 PM
Updates to the containers library jacob navia C Programming 0 04-22-2012 08:09 PM
Containers of iterators vs. containers of references C++ 7 01-25-2008 01:37 PM
Library exposing STL containers Bob C++ 2 07-26-2006 02:04 AM
Questions about destructors on std library containers Ross Boylan C++ 12 02-13-2004 03:03 AM