Updates to the containers library

Discussion in 'C Programming' started by jacob navia, Jun 1, 2012.

  1. jacob navia

    jacob navia Guest

    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
     
    jacob navia, Jun 1, 2012
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ross Boylan
    Replies:
    12
    Views:
    599
    Ross Boylan
    Feb 13, 2004
  2. Bob
    Replies:
    2
    Views:
    311
  3. Replies:
    7
    Views:
    568
    Pete Becker
    Jan 25, 2008
  4. jacob navia

    Updates to the containers library

    jacob navia, Apr 22, 2012, in forum: C Programming
    Replies:
    0
    Views:
    348
    jacob navia
    Apr 22, 2012
  5. Sebastian Mach
    Replies:
    5
    Views:
    338
Loading...

Share This Page