/*
 * Copyright (C) 2005 Red Hat, Inc
 * Author Matthias Clasen
 *
 * xmemchunk.c: implementation of lockfree allocation of fixed
 *              size memory chunks.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library 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 Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */
#include <glib.h>

#include "memchunk.h"


typedef struct _Block Block;
typedef struct _Magazine Magazine;

struct _Block 
{
  Block *next;
  Block *next2;
};

struct _Magazine
{
  MemChunk *mem_chunk;

  Block *block[2];
  gint   count[2];
};

struct _MemChunk
{
  Block *depot;
  Block *rest;
  gint rest_count;

  GMutex *lock;

  GPrivate *magazine;

  gint chunk_size;
  gint magazine_size;

  gpointer areas;
};

static inline void
unload_partial (MemChunk *mem_chunk, 
                Block    *block,
                gint      count)
{
  Block *next;
  gint i;

  if (count == 0)
    return;

  g_mutex_lock (mem_chunk->lock);
  
  for (i = 0; i < count; i++)
   {
     next = block->next;
     block->next = mem_chunk->rest;
     mem_chunk->rest = block;
     mem_chunk->rest_count++;
     block = next;

     if (mem_chunk->rest_count == mem_chunk->magazine_size)
      {
        mem_chunk->rest->next2 = mem_chunk->depot;
        mem_chunk->depot = mem_chunk->rest;
        mem_chunk->rest = NULL;
        mem_chunk->rest_count = 0;   
      }
   } 

  g_mutex_unlock (mem_chunk->lock);   
}

static void
free_magazine (gpointer data)
{ 
  Magazine *magazine = (Magazine *)data;

  unload_partial (magazine->mem_chunk, magazine->block[0], magazine->count[0]);
  unload_partial (magazine->mem_chunk, magazine->block[1], magazine->count[1]);

  g_free (magazine);
}

MemChunk *
mem_chunk_new (gint atom_size, 
	       gint magazine_size)
{
  MemChunk *mem_chunk;

  mem_chunk = g_malloc (sizeof (MemChunk));

  mem_chunk->chunk_size = atom_size;
  mem_chunk->magazine_size = magazine_size;

  mem_chunk->depot = NULL;
  mem_chunk->rest = NULL;
  mem_chunk->rest_count = 0;

  mem_chunk->lock = g_mutex_new ();

  mem_chunk->magazine = g_private_new (free_magazine);
  mem_chunk->areas = NULL;

  return mem_chunk;
}

void
mem_chunk_destroy (MemChunk *mem_chunk)
{
  gpointer area, next;

  area = mem_chunk->areas;
  while (area)
   {
     next = (gpointer)((gchar*)area + mem_chunk->chunk_size * mem_chunk->magazine_size);
     g_free (area);  
     area = next;
   }

  g_mutex_free (mem_chunk->lock);
  g_free (mem_chunk);
}

static inline Magazine *
get_magazine (MemChunk *mem_chunk)
{
  Magazine *magazine;

  magazine = g_private_get (mem_chunk->magazine);
  if (!magazine)
    {
      magazine = g_new0 (Magazine, 1);
  
      magazine->mem_chunk = mem_chunk;

      g_private_set (mem_chunk->magazine, magazine);
    }

  return magazine;
}


static inline Block *
reload (MemChunk *mem_chunk)
{
  gpointer area;
  gchar *mem;
  Block *block, *next;
  gint i;

  g_mutex_lock (mem_chunk->lock);
  
  if (!mem_chunk->depot)
    {
      mem = g_malloc (mem_chunk->chunk_size * mem_chunk->magazine_size + sizeof (gpointer));
      next = NULL;
      for (i = 0; i < mem_chunk->magazine_size; i++)
	{
	  block = (Block *) (mem + i * mem_chunk->chunk_size);
	  block->next = next;
	  next = block;
	}

      block->next2 = NULL;
      mem_chunk->depot = block;

      *(gpointer*)(mem + mem_chunk->chunk_size * mem_chunk->magazine_size) = mem_chunk->areas;
      mem_chunk->areas = (gpointer)mem;
    }

  block = mem_chunk->depot;
  mem_chunk->depot = block->next2;
 
  g_mutex_unlock (mem_chunk->lock);

  return block;
}

static inline void
unload (MemChunk *mem_chunk,
	Block    *block)
{
  g_mutex_lock (mem_chunk->lock);

  block->next2 = mem_chunk->depot;
  mem_chunk->depot = block;
 
  g_mutex_unlock (mem_chunk->lock);
}

static inline void
swap_magazine (Magazine *magazine)
{
  Block *block;
  gint count;

  block = magazine->block[0];
  count = magazine->count[0];
  magazine->block[0] = magazine->block[1];
  magazine->count[0] = magazine->count[1];
  magazine->block[1] = block;
  magazine->count[1] = count;
}

gpointer
mem_chunk_alloc (MemChunk *mem_chunk)
{
  Block *block;
  gpointer chunk;
  Magazine *magazine;
  
  magazine = get_magazine (mem_chunk);

  if (magazine->count[0] == 0)
    {
      if (magazine->count[1] > 0)
	{
          swap_magazine (magazine);
	}
      else
	{
	  magazine->block[0] = reload (mem_chunk);
	  magazine->count[0] = mem_chunk->magazine_size;
	}
    }

  block = magazine->block[0];
  magazine->block[0] = block->next;
  magazine->count[0]--;
  
  return block;
}

void
mem_chunk_free (MemChunk *mem_chunk, 
		gpointer  mem)
{
  Block *block;
  gpointer chunk;
  Magazine *magazine;
  
  magazine = get_magazine (mem_chunk);

  if (magazine->count[1] == mem_chunk->magazine_size)
    {
      if (magazine->count[0] < mem_chunk->magazine_size)
	{
          swap_magazine (magazine);
	}
      else
	{
	  unload (mem_chunk, magazine->block[1]);
	  magazine->block[1] = NULL;
	  magazine->count[1] = 0;
	}
    }

  block = (Block *)mem;
  block->next = magazine->block[1];
  magazine->block[1] = block;
  magazine->count[1]++;
}

