5
\$\begingroup\$

I've borrowed the idea from the internet and I would like to know if my implementation is all right and what could be improved.

It uses the free memory to store links to each node, so there's no extra memory being used.

memory_pool.h

#ifndef MEMORY_POOL_H
#define MEMORY_POOL_H

#include <stdlib.h>

#define MEMORY_POOL_SUCCESS 1
#define MEMORY_POOL_ERROR 0
#define MEMORY_POOL_MINIMUM_SIZE sizeof(void *)

typedef struct {
    void **head;
    void *memory;
} Memory_Pool;

//size must be greater than or equal to MEMORY_POOL_MINIMUM_SIZE
int mp_init(Memory_Pool *mp, size_t size, size_t slots);
void mp_destroy(Memory_Pool *mp);

void *mp_get(Memory_Pool *mp);
void mp_release(Memory_Pool *mp, void *mem);

#endif

memory_pool.c

#include "memory_pool.h"

int mp_init(Memory_Pool *mp, size_t size, size_t slots)
{
    //allocate memory
    if((mp->memory = malloc(size * slots)) == NULL)
        return MEMORY_POOL_ERROR;

    //initialize
    mp->head = NULL;

    //add every slot to the list
    char *end = (char *)mp->memory + size * slots;
    for(char *ite = mp->memory; ite < end; ite += size)
        mp_release(mp, ite);

    return MEMORY_POOL_SUCCESS;
}

void mp_destroy(Memory_Pool *mp)
{
    free(mp->memory);
}

void *mp_get(Memory_Pool *mp)
{
    if(mp->head == NULL)
        return NULL;

    //store first address
    void *temp = mp->head;

    //link one past it
    mp->head = *mp->head;

    //return the first address
    return temp;
}

void mp_release(Memory_Pool *mp, void *mem)
{
    //store first address
    void *temp = mp->head;

    //link new node
    mp->head = mem;

    //link to the list from new node
    *mp->head = temp;
}
\$\endgroup\$
7
\$\begingroup\$

I see a few things that might be changed.

mp_init

First, consider checking the passed *mp variable to see if it's NULL at least within the mp_init call. Alternatively, you could also allocate that structure within the mp_init routine and return a pointer to it or NULL on error.

The initialization is more complex than it needs to be. Rather than make repeated calls to mp_release and do all of that pointer manipulation, you could use this:

char *ptr;
for (ptr = mp->memory; --slots; ptr+=size) 
    *(void **)ptr = ptr+size;
*(void **)ptr = NULL;
mp->head = mp->memory;

mp_release

Within mp_release, there is no error checking. This might be OK if we're looking for extreme performance, but it might be nice to have at least a debug version that checks that mem actually points to a slot. For that to work, of course, you'll have to add at least one more variable to the structure to contain the size parameter.

mp_destroy

In mp_destroy it might be prudent to set mp->head = NULL so that any subsequent mp_get attempts will fail.

\$\endgroup\$
  • \$\begingroup\$ Wouldn't setting mp->head = NULL potentially hide a programmer's error? \$\endgroup\$ – 2013Asker May 4 '14 at 13:28
  • 2
    \$\begingroup\$ @2013Asker: Rather than hiding the error, it seems to me that the proposed change would make such an error easier to find and it costs nearly nothing. \$\endgroup\$ – Edward May 4 '14 at 13:40
4
\$\begingroup\$

The only addition I would make is:

int mp_init(Memory_Pool *mp, size_t size, size_t slots)
{
    if (size < MEMORY_POOL_MINIMUM_SIZE)
    {   return MEMORY_POOL_ERROR;
    }

But note: There is extra memory being used.

typedef struct {
    void **head;
    void *memory;
} Memory_Pool;

You need space to store the above structure.

How it is implemented:

A call to mp_init() allocated a chunk of memory. This chunk of memory is slots count number of items each of size size.

 // Let's examine this specific call:
 Memory_Pool  memory;
 if (mp_init(&memory, sizeof(void*) * 4, 5) != MEMORY_POOL_SUCCESS)
 {
     exit(1);
 }


    if((mp->memory = malloc(size * slots)) == NULL)
        return MEMORY_POOL_ERROR;
      mp->head----->Random
      mp->memory--->        ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
    mp->head = NULL;
      mp->head-----|
      mp->memory--->        ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
    char *end = (char *)mp->memory + size * slots;
      mp->head-----|
      mp->memory----------->***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
 char *end----------------->
    for(char *ite = mp->memory; ite < end; ite += size)
        mp_release(mp, ite);
 // Iteration 1:
      mp->head----------------|
                              \/
      mp->memory----------->**( null )*
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
 char *end----------------->
   // Iteration 2:
      mp->memory----------->**( null )*
                            *     /\  *
                            *     |   *
      mp->head--------------*-|   |   *
                            * \/  |   *
                            **(   *  )*
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
 char *end----------------->
   // Iteration 3:
      mp->memory----------->**( null )*
                            *     /\  *
                            *     |   *
                            *         *
                            *     |   *
                            **(   *  )*
                            *     /\  *
                            *     |   *
      mp->head--------------*-|   |   *
                            * \/  |   *
                            **(   *  )*
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
 char *end----------------->
   // Iteration 4:
      mp->memory----------->**( null )*
                            *     /\  *
                            *     |   *
                            *     |   *
                            *     |   *
                            **(   *  )*
                            *     /\  *
                            *     |   *
                            *     |   *
                            *     |   *
                            **(   *  )*
                            *     /\  *
                            *     |   *
      mp->head--------------*-|   |   *
                            * \/  |   *
                            **(   *  )*
                            *         *
                            *         *
                            *         *
                            *         *
                            ***********
 char *end----------------->
   // Iteration 5:
      mp->memory----------->**( null )*
                            *     /\  *
                            *     |   *
                            *     |   *
                            *     |   *
                            **(   *  )*
                            *     /\  *
                            *     |   *
                            *     |   *
                            *     |   *
                            **(   *  )*
                            *     /\  *
                            *     |   *
                            *     |   *
                            *     |   *
                            **(   *  )*
                            *     /\  *
                            *     |   *
      mp->head--------------*-|   |   *
                            * \/  |   *
                            **(   *  )*
 char *end----------------->
    return MEMORY_POOL_SUCCESS;
}
\$\endgroup\$
  • \$\begingroup\$ can you explain how the node linking works? The OP was last seen 4 years ago. Why is the head **void and not just *void? Why in the release function, void* mem is being assigned to void** head. I can't seem to understand the underlying logic, thanks. \$\endgroup\$ – susdu Mar 26 at 21:20
  • \$\begingroup\$ @susdu Hope the diagram helps. \$\endgroup\$ – Martin York Mar 27 at 4:33
  • \$\begingroup\$ Thanks a lot, it definitely helped. So each cell basically functions both as a free block and holds a pointer to the previous block. Any reason why the last node is at the start of the block and not vice versa? \$\endgroup\$ – susdu Mar 27 at 6:56
  • \$\begingroup\$ it looks like the get/release operations could all this be done with void *head? I still don't understand the necessity of using a double head pointer \$\endgroup\$ – susdu Mar 27 at 8:50
  • \$\begingroup\$ @susdu Any reason why the last node is at the start Just the way it was implemented. There is no significance to it. \$\endgroup\$ – Martin York Mar 27 at 14:52

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.