/*------------------------------------------------------------------------*/
/*--- A simple pool (memory) allocator implementation. m_poolalloc.c ---  */
/*------------------------------------------------------------------------*/
/*
   This file is part of Valgrind, a dynamic binary instrumentation
   framework.

   Copyright (C) 2011-2012 OpenWorks LLP info@open-works.co.uk,
                           Philippe Waroquiers philippe.waroquiers@skynet.be

   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
   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.

   The GNU General Public License is contained in the file COPYING.
*/

#include "pub_core_basics.h"
#include "pub_core_libcbase.h"
#include "pub_core_libcassert.h"
#include "pub_tool_xarray.h"
#include "pub_tool_poolalloc.h" /* self */

struct _PoolAlloc {
   UWord   nrRef;         /* nr reference to this pool allocator */
   UWord   elemSzB;       /* element size */
   UWord   nPerPool;      /* # elems per pool */
   void*   (*alloc)(HChar*, SizeT); /* pool allocator */
   HChar*  cc; /* pool allocator's cc */
   void    (*free)(void*); /* pool allocator's free-er */
   /* XArray of void* (pointers to pools).  The pools themselves.
      Each element is a pointer to a block of size (elemSzB *
      nPerPool) bytes. */
   XArray* pools;
   /* next free element.  Is a pointer to an element in one of the
      pools pointed to by .pools */
   void* nextFree;
};

PoolAlloc* VG_(newPA) ( UWord  elemSzB,
                        UWord  nPerPool,
                        void*  (*alloc)(HChar*, SizeT),
                        HChar* cc,
                        void   (*free_fn)(void*) )
{
   PoolAlloc* pa;
   vg_assert(0 == (elemSzB % sizeof(UWord)));
   vg_assert(elemSzB >= sizeof(UWord));
   vg_assert(nPerPool >= 100); /* let's say */
   vg_assert(alloc);
   vg_assert(cc);
   vg_assert(free_fn);
   pa = alloc(cc, sizeof(*pa));
   vg_assert(pa);
   VG_(memset)(pa, 0, sizeof(*pa));
   pa->nrRef    = 0;
   pa->elemSzB  = elemSzB;
   pa->nPerPool = nPerPool;
   pa->pools    = NULL;
   pa->alloc    = alloc;
   pa->cc       = cc;
   pa->free     = free_fn;
   pa->pools    = VG_(newXA)( alloc, cc, free_fn, sizeof(void*) );
   pa->nextFree = NULL;
   vg_assert(pa->pools);
   return pa;
}

void VG_(deletePA) ( PoolAlloc* pa)
{
   Word i;
   vg_assert(pa->nrRef == 0);
   for (i = 0; i < VG_(sizeXA) (pa->pools); i++)
      pa->free (*(UWord **)VG_(indexXA) ( pa->pools, i ));
   VG_(deleteXA) (pa->pools);
   pa->free (pa);
}

/* The freelist is empty.  Allocate a new pool and put all the new
   elements in it onto the freelist. */
__attribute__((noinline))
static void pal_add_new_pool ( PoolAlloc* pa ) 
{
   Word   i;
   UWord* pool;
   vg_assert(pa);
   vg_assert(pa->nextFree == NULL);
   pool = pa->alloc( pa->cc, pa->elemSzB * pa->nPerPool );
   vg_assert(pool);
   /* extend the freelist through the new pool.  Place the freelist
      pointer in the first word of each element.  That's why the
      element size must be at least one word. */
   for (i = pa->nPerPool-1; i >= 0; i--) {
      UChar* elemC = ((UChar*)pool) + i * pa->elemSzB;
      UWord* elem  = (UWord*)elemC;
      vg_assert(0 == (((UWord)elem) % sizeof(UWord)));
      *elem = (UWord)pa->nextFree;
      pa->nextFree = elem;
   }
   /* and add to our collection of pools */
   VG_(addToXA)( pa->pools, &pool );
}

void* VG_(allocEltPA) ( PoolAlloc* pa)
{
   UWord* elem;
   if (UNLIKELY(pa->nextFree == NULL)) {
      pal_add_new_pool(pa);
   }
   elem = pa->nextFree;
   pa->nextFree = (void*)*elem;
   *elem = 0; /* unnecessary, but just to be on the safe side */
   return elem;
}

void VG_(freeEltPA) ( PoolAlloc* pa, void* p)
{
   UWord* elem = (UWord*)p;
   *elem = (UWord)pa->nextFree;
   pa->nextFree = elem;
}


void VG_(addRefPA) ( PoolAlloc* pa)
{
   pa->nrRef++;
}

UWord VG_(releasePA)(PoolAlloc* pa)
{
   UWord nrRef;

   vg_assert(pa->nrRef > 0);
   nrRef = --pa->nrRef;
   if (nrRef == 0)
      VG_(deletePA)(pa);
   return nrRef;
}