8
\$\begingroup\$

I just wrote this pool to avoid calling malloc and free when I have some code that frequently allocates and deallocates chunks of same-sized memory. I would like to know if there are any bugs I didn't notice and what would be the best solution to achieve this goal.

I'm using some small functions that aren't really required because I find the abstraction nice when using the code later and because I noticed the compiler will optimize them away when link-time optimization is turned on.

I'm using about the same code I posted before for the stack.

object_pool.h

#ifndef OBJECT_POOL_H
#define OBJECT_POOL_H

#include <stdlib.h>
#include "dynamic_stack.h"

#define OP_SUCCESS 1
#define OP_ERROR 0

typedef struct Memory_Block {
    char *position;
    char *end;
    struct Memory_Block *next;
} Memory_Block;

typedef struct Object_Pool {
    Dynamic_Stack free_blocks;
    size_t object_size;
    size_t big_block_capacity;
    Memory_Block *last_memory_block;
    Memory_Block *first_memory_block;
    size_t total_blocks;
} Object_Pool;

int op_init_custom(Object_Pool *op, size_t object_size, size_t big_block_capacity);
int op_init(Object_Pool *op, size_t object_size);
void op_destroy(Object_Pool *op);

void op_set_big_block_capacity(Object_Pool *op, size_t new_capacity);
size_t op_total_blocks(Object_Pool *op);

void *op_get(Object_Pool *op);
void op_release(Object_Pool *op, void *object);
void op_release_all(Object_Pool *op);

#endif

object_pool.c

#include "object_pool.h"

#define DEFAULT_CAPACITY 128
#define STACK_CAPACITY 128
#define OP_FAIL_SAFE

static char *memory_block_start(Memory_Block *block)
{
    return (char *)(block + 1);
}

static Memory_Block *new_memory_block(Object_Pool *op)
{
    Memory_Block *temp = malloc(sizeof(Memory_Block) + op->object_size * op->big_block_capacity);
    if(temp == NULL)
        return NULL;

    //If the stack can't support the same number of objects created, freeing objects might fail
    #ifdef OP_FAIL_SAFE
    if(dstack_increase_capacity(&op->free_blocks, op->big_block_capacity) == DSTACK_ERROR){
        free(temp);
        return OP_ERROR;
    }   
    #endif

    temp->position = memory_block_start(temp);
    temp->end = temp->position + op->object_size * op->big_block_capacity;
    temp->next = NULL;
    op->total_blocks += op->big_block_capacity;

    return temp;
}

int op_init_custom(Object_Pool *op, size_t object_size, size_t big_block_capacity)
{
    op->object_size = object_size;
    op->big_block_capacity = big_block_capacity;
    op->total_blocks = 0;

    if(dstack_init(&op->free_blocks, STACK_CAPACITY) == DSTACK_ERROR)
        return OP_ERROR;

    op->first_memory_block = op->last_memory_block = new_memory_block(op);
    if(op->first_memory_block == NULL){
        dstack_free(&op->free_blocks);
        return OP_ERROR;
    }

    return OP_SUCCESS;
}

int op_init(Object_Pool *op, size_t object_size)
{
    return op_init_custom(op, object_size, DEFAULT_CAPACITY);
}

void op_destroy(Object_Pool *op)
{
    dstack_free(&op->free_blocks);

    Memory_Block *next;
    for(Memory_Block *ite = op->first_memory_block; ite != NULL; ite = next){
        next = ite->next;
        free(ite);
    }
}

void op_set_big_block_capacity(Object_Pool *op, size_t new_capacity)
{
    if(new_capacity >= op->object_size)
        op->big_block_capacity = new_capacity;
}

size_t op_total_blocks(Object_Pool *op)
{
    return op->total_blocks;
}

void *op_get(Object_Pool *op)
{
    void *block = dstack_pop(&op->free_blocks);
    if(block != DSTACK_EMPTY)
        return block;

    if((block = op->last_memory_block->position) < (void *)op->last_memory_block->end){
        op->last_memory_block->position += op->object_size;
        return block;
    }

    if((op->last_memory_block->next = new_memory_block(op)) == NULL)
        return NULL;

    op->last_memory_block = op->last_memory_block->next;
    block = op->last_memory_block->position;
    op->last_memory_block->position += op->object_size;

    return block;
}

void op_release(Object_Pool *op, void *object)
{
    dstack_push(&op->free_blocks, object);
}

void op_release_all(Object_Pool *op)
{
    for(Memory_Block *ite = op->first_memory_block; ite != NULL; ite = ite->next)
        ite->position = memory_block_start(ite);

    //The stack must be cleared too to avoid handling the same block twice
    dstack_clear(&op->free_blocks);
}

dynamic_stack.h

#ifndef DYNAMIC_STACK
#define DYNAMIC_STACK

#include <stdlib.h>

#define DSTACK_SUCCESS 1
#define DSTACK_ERROR 0
extern void *DSTACK_EMPTY;

//The stack just stores pointers
typedef struct Dynamic_Stack Dynamic_Stack;
struct Dynamic_Stack {
    void **start; //Array of pointer to void
    void **position;
    void **end;
};

//Set up stack
int dstack_init(Dynamic_Stack *stack, size_t slots);

void dstack_free(Dynamic_Stack *stack);
void dstack_clear(Dynamic_Stack *stack);
int dstack_push(Dynamic_Stack *stack, void *new_element);
void *dstack_pop(Dynamic_Stack *stack);

//0 is the top of the stack
void *dstack_peek(Dynamic_Stack *stack, size_t levels);
int dstack_increase_capacity(Dynamic_Stack *stack, size_t new_slots);
int dstack_decrease_capacity(Dynamic_Stack *stack, size_t remove_total);
void dstack_shrink_to_fit(Dynamic_Stack *stack);

#endif

dynamic_stack.c

#include <stdlib.h>
#include "dynamic_stack.h"

#define MULTIPLIER 1.00 //Increase by 100% on every expansion
#define FIXED_EXPANSION 0 //Overrides multiplier

//Signal the stack is empty
char dummy = 'd';
void *DSTACK_EMPTY = &dummy;

//Internal
//Must keep at least 1 slot or it will break
static int dstack_resize(Dynamic_Stack *stack, size_t new_slot_capacity)
{   
    size_t position = stack->position - stack->start;

    void *temp = realloc(stack->start, new_slot_capacity * sizeof(void *));
    if(temp == NULL)
        return DSTACK_ERROR;

    stack->start = temp;
    stack->end = stack->start + new_slot_capacity;

    //Put position back if needed
    stack->position = (position < new_slot_capacity)
                                ? stack->start + position
                                : stack->end;

    return DSTACK_SUCCESS;
}

#if FIXED_EXPANSION >= 1
static int expand(Dynamic_Stack *stack)
{   
    return dstack_resize(stack, stack->end - stack->start + FIXED_EXPANSION);
}

#else
static int expand(Dynamic_Stack *stack)
{
    //Check if multiplier is producing at least 1 new slot
    size_t old_slots = stack->end - stack->start;
    size_t new_slots = old_slots * MULTIPLIER;

    if(new_slots == 0)
        return DSTACK_ERROR;

    return dstack_resize(stack, old_slots + new_slots);
}
#endif


//Public
//Set up stack
int dstack_init(Dynamic_Stack *stack, size_t slots)
{
    if((stack->start = malloc(sizeof(void *) * slots)) == NULL)
        return DSTACK_ERROR;

    stack->position = stack->start;
    stack->end = stack->start + slots;
    return DSTACK_SUCCESS;
}

void dstack_free(Dynamic_Stack *stack)
{
    free(stack->start);
}

void dstack_clear(Dynamic_Stack *stack)
{
    stack->position = stack->start;
}

int dstack_push(Dynamic_Stack *stack, void *new_element)
{
    if(stack->position == stack->end && expand(stack) == DSTACK_ERROR)
        return DSTACK_ERROR;

    *stack->position = new_element;
    ++stack->position;
    return DSTACK_SUCCESS;
}

void *dstack_pop(Dynamic_Stack *stack)
{
    if(stack->position == stack->start)
        return DSTACK_EMPTY;

    return *--stack->position;
}

//0 is the top of the stack
void *dstack_peek(Dynamic_Stack *stack, size_t levels)
{
    if(levels >= (size_t)(stack->position - stack->start))
        return NULL;

    return *(stack->position - 1 - levels);
}

int dstack_increase_capacity(Dynamic_Stack *stack, size_t new_slots)
{
    return dstack_resize(stack, stack->end - stack->start + new_slots);
}

int dstack_decrease_capacity(Dynamic_Stack *stack, size_t remove_total)
{
    if(remove_total >= (size_t)(stack->end - stack->start))
        return DSTACK_ERROR;

    return dstack_resize(stack, stack->end - stack->start - remove_total);
}

//Always leave 1 extra slot so there's no risk of resizing to 0
void dstack_shrink_to_fit(Dynamic_Stack *stack)
{
    dstack_resize(stack, stack->position - stack->start + 1);
}
\$\endgroup\$
  • \$\begingroup\$ Could you also post the contents of "dynamic_stack.h"? \$\endgroup\$ – haneefmubarak Apr 30 '14 at 0:22
  • \$\begingroup\$ @haneefmubarak I added the stack code, I'm looking forward to your review. \$\endgroup\$ – 2013Asker May 2 '14 at 9:00
5
\$\begingroup\$

You should always use curly braces around if statements and for loops. It's the safe thing to do, especially when you are dealing with memory-management.

Something small like this:

if(temp == NULL)
    return NULL;

Can be one lined:

if(temp == NULL) return NULL;

Braces can be omitted on this one, because it is one lined and it's still very obvious that this is the entire if statement, and if someone comes along to add something to this they have to add braces anyway.


Returning in an if statement should always be inside of curly braces:

int dstack_decrease_capacity(Dynamic_Stack *stack, size_t remove_total)
{
    if(remove_total >= (size_t)(stack->end - stack->start))
        return DSTACK_ERROR;

    return dstack_resize(stack, stack->end - stack->start - remove_total);
}

like this:

int dstack_decrease_capacity(Dynamic_Stack *stack, size_t remove_total)
{
    if(remove_total >= (size_t)(stack->end - stack->start))
    {
        return DSTACK_ERROR;
    }
    return dstack_resize(stack, stack->end - stack->start - remove_total);
}

You especially want the fact that this is throwing an error to stick out, this is easier to read in my opinion.


The for loop! UGH!

void op_release_all(Object_Pool *op)
{
    for(Memory_Block *ite = op->first_memory_block; ite != NULL; ite = ite->next)
        ite->position = memory_block_start(ite);

    //The stack must be cleared too to avoid handling the same block twice
    dstack_clear(&op->free_blocks);
}

Don't write it like that, it looks ugly; this is much prettier I think:

void op_release_all(Object_Pool *op)
{
    for(Memory_Block *ite = op->first_memory_block; ite != NULL; ite = ite->next)
    {
        ite->position = memory_block_start(ite);
    }

    //The stack must be cleared too to avoid handling the same block twice
    dstack_clear(&op->free_blocks);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.