Linked list complexity redivivus

Because fast doesn't always mean simpler, sometimes we have to get very very dirty.

Yesterday we left the problem of the memory allocation in suspense. Today we will try to get deeper in the muddy waters of O(1) allocation. And then, some unicorns.

Since we know that we cannot dream of constant time memory allocation (unless unicorns are involved) the best idea would be to preallocate the items in a single batch. So, let's say that we need maximum 10.000 elements, we allocate space for those maximum 10.000 elements from the beginning with a single malloc.

Good, but how do we actually take from that memory pool elements in constant time? Well... Theory has it that we could use a linked list for that ;)

Nobody tells us that the creation time has to be small, right? So when we allocate the space for those elements we can link together those elements, right?

node *mem_pool_create (int maxelem)

{

   node *head = malloc (sizeof (node)*maxelem);

   int i;

   if (!head) return NULL;

   for (i=0; i= 1 */

      head[i]->next = head+(i+1);

   head[maxelem-1]->next = NULL;

   return head;

}

/* bingo! Constant time! */

node *mem_pool_extract (node **pool_head)

{

   node *ptr;

   if (!pool_head || !*pool_head) return NULL;

   ptr = *pool_head;

   *pool_head = ptr->next;

   return ptr;

}

/* by re-adding the node in front we make sure the nodes

 * won't get too scattered in memory - and we might take

 * advantage of the processor cache */

void mem_pool_retake (node **pool_head, node *ptr)

{

   if (!ptr || !pool_head) return;

   ptr->next = *pool_head;

   *pool_head = ptr;

}

Use these calls instead of malloc/free. When memory gets thin... well, that's a discussion for tomorrow, maybe. :)

What we could do is see how we can optimize the memory pool creation. A simple idea could be used: Instead of writing the next pointer for all the elements in the beginning, we can keep a mark of 'how much we have written so far', in the pool definition. One example of such modification below:

typedef struct {

   node *initial_head;

   node *head;

   int maxelem;

   int maxused;

} mem_pool_t;

mem_pool_t *mem_pool_create (int maxelem)

{

   mem_pool_t *pool;

   int i;

   pool = (mem_pool_t *)malloc (sizeof (mem_pool_t));

   pool->head = (node *)malloc (sizeof (node)*maxelem);

   pool->initial_head = pool->head;

   pool->maxelem = maxelem;

   pool->maxused = 0;

   if (!pool->head) {

      free (pool);

      return NULL;

   }

   pool->head->next = pool->head + 1;

   return pool;

}

node *mem_pool_extract (mem_pool_t *pool)

{

   node *ptr;

   if (!pool_head || !*pool_head) return NULL;

   ptr = pool->head;

   pool->head = ptr->next;

   ptr->next = NULL;

   if (pool->head && pool->head - pool->initial_head >= pool->maxused) {

      pool->maxused ++;

      if (pool->maxelem>pool->maxused)

         pool->head->next = pool->head + 1;

      else

         pool->head->next = NULL;

   }

   return ptr;

}

void mem_pool_retake (mem_pool_t *pool, node *ptr)

{

   if (!ptr || !pool) return;

   ptr->next = pool->head;

   pool->head = ptr;

}

Update: I got a bit sloppier with the retake, updated the right code :)