---

chunkallocator.c

Go to the documentation of this file.

/***************************************************************************
 *  @file  chunkallocator.c
 *  @brief chunkallocator Implementation.
 *
 *  @date   : 15-08-03 00:45
 *  @author : Pedro Ortega C. <peortega@dcc.uchile.cl>
 *  Copyright  2003  Pedro Ortega C.
 ****************************************************************************/
/*
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Library General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */



/**
 * @brief An efficient memory chunk allocator.
 * @defgroup chunkallocator_doc chunkallocator : A Memory Chunk Allocator.
 *
 * The chunkallocator is a little and simple memory manager for "chunks" or
 * bins of constant size. It it designed to be efficient: it allocates and
 * frees theese memory bins very fast. On the other side, it isn't as flexible
 * the C memory manager (provided by \p malloc() and Co.).
 *
 * The chunkallocator is a good alternative to \p malloc() for structures such
 * as linked list, whose elements are of constant size and are frequently
 * allocated and freed.
 *
 * You can have many different chunkallocators in your application for
 * different purposes: they all handle independent memory blocks.
 *
 * Example usage:
   \code

   chunkallocator *c;
   List *lst;
   
   // Allocate a new Memory Chunk Allocator for handling list items.
   c = chunkallocator_new (sizeof (List));
   
   // Allocate memory.
   lst = chunkallocator_alloc (c);
   
   // Free allocated memory.
   chunkallocator_free (c, lst);
   
   // Do more complicated things....
   ...
   
   // After using the memory allocator, free it.
   chunkallocator_destroy (c);
   
   \endcode
 */



/******************************************/
/* Include Files                          */
/******************************************/

#include <stdio.h>
#include <assert.h>
#include <limits.h>
#include <stdlib.h>
#include "chunkallocator.h"



/******************************************/
/* Static Declaration                     */
/******************************************/

static int
chunkallocator_increase (chunkallocator *a);



/******************************************/
/* Static Implementation                  */
/******************************************/

/**
 * @brief Allocate a new chunkblock.
 * @ingroup chunkallocator_doc
 *
 * This function allocates a new chunkblock that doubles the size of its
 * previous block (in the memblock array) and sets the corresponding boundary
 * pointer beginptr and endptr.
 *
 * @param  a A pointer to a chunkallocator.
 * @return 0 if O.K., 1 if failed to allocate new chunkblock.
 */
static int
chunkallocator_increase (chunkallocator *a)
{
    size_t blocksize;

    assert (a->cblock->beginptr == NULL);

    /* compute blocksize */
    a->cblock--;
    blocksize = 2 * (a->cblock->endptr - a->cblock->beginptr);
    a->cblock++;

    /* allocate memory block */
    a->cblock->beginptr = (unsigned char *) malloc (blocksize);
    if (a->cblock->beginptr == NULL)
    {
        fprintf (stderr, "chunkallocator: out of memory\n");
            return 1;
    }

    a->cblock->endptr = a->cblock->beginptr + blocksize;

    return 0;
}



/******************************************/
/* Public Interface Implementation        */
/******************************************/

/**
 * @brief Create a new chunkallocator.
 * @ingroup chunkallocator_doc
 *
 * This function creates a new chunkallocator for bins of the given size.
 *
 * @param  binsize The size of the bins that the allocator should allocate.
 * @return A pointer to a new created chunkallocator.
 */
chunkallocator *
chunkallocator_new (size_t binsize)
{
    chunkallocator *a;
    
    /* make sufficient big chunks */
    if (binsize < sizeof (unsigned char *))
        binsize = sizeof (unsigned char *);
    
    /* alloc chunkallocator */
    a = (chunkallocator *) malloc (sizeof (*a));
    if (a == NULL)
        return NULL;
        
    /* set fields */
    a->allocated   = 0L;
    a->binsize     = binsize;
    a->deallocated = 0L;
    
    /* alloc chunk block array */
    a->memblocks =
               (chunkblock *) calloc (8 * sizeof (size_t), sizeof (chunkblock));
    if (a->memblocks == NULL)
    {
        free (a);
        return NULL;
    }
    
    /* set current memblock pointer */
    a->cblock = a->memblocks;
    
    /* alloc first chunk block */
    a->cblock->beginptr =
                    (unsigned char *) malloc (CHUNKBLOCK_MINSIZE * a->binsize);
    if (a->cblock->beginptr == NULL)
    {
        free (a->memblocks);
        free (a);
        return NULL;
    }
    
    /* set block end pointer */
    a->cblock->endptr  = a->cblock->beginptr + CHUNKBLOCK_MINSIZE * a->binsize;
    
    /* set pointer to free chunk */
    a->nextfree = a->cblock->beginptr;
    
    return a;
}

/**
 * @brief Destroy chunkallocator.
 * @ingroup chunkallocator_doc
 *
 * This function frees the memory of the chunkallocator, freeing the structure
 * and all its chunk/memory blocks.
 *
 * @param a A pointer to a chunkallocator.
 */
void
chunkallocator_destroy (chunkallocator *a)
{
    chunkblock *ptr;
    
    /* free all memory blocks */
    for (ptr = a->memblocks; ptr->beginptr != NULL; ptr++);
        free (ptr->beginptr);

    /* free block array */
    free (a->memblocks);
    free (a);
}

/**
 * @brief Allocate chunk.
 * @ingroup chunkallocator_doc
 *
 * This function returns a pointer to a new allocated memory chunk. The
 * chunkallocator handles the memory management to do so, and of course,
 * to allocate a chunk of the correct size efficiently.
 *
 * Internally, the allocator checks if there are dead chunks, that is,
 * previously deallocated chunks that lie fragmented in the memory. If so
 * it assigns its memory. If not, then it returns new memory from the
 * memory pool. If there isn't any memory available either, then it
 * creates a new chunkblock.
 *
 * @param  a A pointer to a chunkallocator.
 * @return A pointer to new memory.
 */
void *
chunkallocator_alloc (chunkallocator *a)
{
    void *memblock;
    
    assert ((a->nextfree - a->cblock->beginptr) % a->binsize == 0);
    assert ((a->cblock->endptr - a->nextfree) % a->binsize == 0);
    assert (a->cblock->beginptr <= a->nextfree);
    assert (a->nextfree <= a->cblock->endptr);

    /* get if there are recyclable dead chunks */
    if (a->deallocated > 0)
    {
        memblock = a->nextdealloc;
        a->nextdealloc = (unsigned char **) *(a->nextdealloc);
        a->deallocated--;
    }
    else
    {
        /* get free memory block */
        memblock = a->nextfree;
    
        /* point to next free block */
        a->nextfree += a->binsize;

        /* jump to next memory block if current is full */
        if (a->nextfree == a->cblock->endptr)
        {
            a->cblock++;
        
            /* increase memory pool if full */
            if (a->cblock->beginptr == NULL)
                if (chunkallocator_increase (a))
                {
                    a->cblock--;
                    a->nextfree = a->cblock->endptr;
                    return NULL;
                }

            a->nextfree = a->cblock->beginptr;
        }
    }

    /* increase chunk counter */
    a->allocated++;

    return memblock;
}

/**
 * @brief Free a chunk.
 * @ingroup chunkallocator_doc
 *
 * This function deallocates the chunk/memory block pointed by the argument.
 *
 * Internally, the allocator just returns it to the memory pool by linking
 * the bin to the list of deallocated (and recyclable) memory chunks.
 *
 * @param a        A pointer to a chunkallocator.
 * @param memblock A pointer to a memory chunk to be freed.
 */
void
chunkallocator_free (chunkallocator *a, void *memblock)
{
    unsigned char **chunk;
    
    assert (a->allocated > 0);
    assert ((a->nextfree - a->cblock->beginptr) % a->binsize == 0);
    assert ((a->cblock->endptr - a->nextfree) % a->binsize == 0);
    assert (a->cblock->beginptr <= a->nextfree);
    assert (a->nextfree <= a->cblock->endptr);

    /* register dead chunk */
    chunk  = memblock;
    *chunk = (unsigned char *) a->nextdealloc;
    a->nextdealloc = chunk;
    a->deallocated++;
    a->allocated--;
}

---