/**
* BME_Mem.c jan 2007
*
* BMesh memory allocator
*
* $Id: BME_eulers.c,v 1.00 2007/01/17 17:42:01 Briggs Exp $
*
* ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
*
* 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. The Blender
* Foundation also sells licenses for use in proprietary software under
* the Blender License. See http://www.blender.org/BL/ for information
* about this.
*
* 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 Original Code is Copyright (C) 2004 Blender Foundation.
* All rights reserved.
*
* The Original Code is: all of this file.
*
* Contributor(s): Geoffrey Bantle.
*
* ***** END GPL/BL DUAL LICENSE BLOCK *****
*/
#include "MEM_guardedalloc.h"
#include "DNA_listBase.h"
#include "BKE_utildefines.h"
#include "BLI_blenlib.h"
/*********************************************************
* BMesh Memory Managment *
* *
* *
* Simple memory allocator *
* *
**********************************************************/
/*
Mesh memory allocation is handled through a series of 'pools'
each of which contains a linked list of 'chunks' of a uniform
size. For each type of mesh data a seperate pool is used. So
for example there will be a vertex pool, an edge pool, a face
pool, a loop pool, and any number of custom data pools.
To delay memory defrag after freeing chunks, each header contains
an 'index' field which informs the allocator where to insert new
headers. If for instance the first memory header has an index of 0
and the second memory header has an index of 2, the allocator knows
to insert a new header between the two and give it an index of 1.
In this way deleting chunks will not invalidate any index references
to data in the pool.
It should be noted that this affects the size of the lookup table,
which is equal to pointersize * highest index. For indices with no
associated chunk header the entry in the lookup table is set to NULL.
When the caller decides that the pool has become too fragmented it
can decide to merge chunks and free the excess using BMEMpool_defrag.
This will also return an array showing the new indices for all changed
elements so that the caller can then fix all index references.
*/
#define BMEM_chunksize 8192
/**
* BMEMheader
*
* Header structure for memory chunks.
*
* Returns -
* A BMEMpool pointer
*/
typedef struct BMEMheader{
struct BMEMheader *next, *prev; /*linked list*/
int free; /*number of free elements in this chunk */
int index; /*chunk index*/
}BMEMheader;
/**
* BMEMpool
*
* Memory .
*
* Returns -
* A BMEMpool pointer
*/
typedef struct BMEMpool{
struct Listbase chunks; /*Linked list of chunks. Should never be stepped through directly*/
int chunksize; /*In bytes, multiples of 8*/
int elemsize; /*In bytes, multiples of 8*/
int totchunks; /*Total number of chunks*/
struct BMEMheader *lookup /*Quick lookup table for chunks. Rebuilt whenever chunks listbase is modified.*/
}BMEMpool;
/**
* BMEMpool_create
*
* Creates a new memory pool
*
* Returns -
* A BMEMpool pointer
*/
BMEM_pool *BMEMpool_create(int elemsize, int totelements, int chunksize)
{
BMEMpool *pool = NULL;
BMEMheader *chunk = NULL;
int elembytes, chunkbytes,i;
int totchunks, padbytes = 0;
/*do error checking to make sure sizes are multiples of eight*/
if(chunksize%8 || elemsize%8) return NULL;
elembytes = totelements * elemsize;
if(elembytes % chunksize)
padbytes = chunksize - (elembytes % chunksize);
totchunks = ((elembytes + padbytes) / chunksize);
pool = MEM_callocN(sizeof(BMEMpool),"BMEMpool");
pool->chunksize = chunksize;
pool->elemsize = elemsize;
pool->totchunks = totchunks;
pool->lookup = MEM_callocN(sizeof(BMEMheader*)*totchunk);
/*now go through and add chunks to block->chunks*/
for(i=0; i < pool->totchunks; i++){
chunk = MEM_callocN(sizeof(BMEMheader) + pool->chunksize,"BMEMchunk");
chunk->free = pool->chunksize / pool->elemsize;
chunk->index = i;
BLI_addtail(&(pool->chunks),chunk);
pool->lookup[i] = chunk;
}
return pool;
}
/**
* BMEMpool_destroy
*
* Destroys an existing BMEMpool and deallocates its chunks
*
* Returns -
* A BMEMpool pointer
*/
void BMEMpool_destroy(BMEMem_pool *pool){
int i;
for(i=0; i<pool->totchunks; i++){
if(pool->lookup[i]) MEM_freeN(pool->lookup[i]);
}
MEM_freeN(pool->lookup);
MEM_freeN(pool);
}
/**
* BMEMpool_defrag
*
* Defragments a pools chunks. Note that any
* pointers to the elements stored in chunks will now
* be invalid.
*
* Returns -
* Nothing
*/
/*
void BMEMpool_defrag(BME_Block *block, int free)
{
}
*/
/**
* BMEM_pool_free_unused
*
* Frees unused chunks
*
* Returns -
* Nothing
*/
/*void BMEMpool_free_unused(BMEMpool *pool){
}*/
/**
* BMEMpool_alloc
*
* Allocates a new element in the pool.
* It does this by searching first for a chunk with
* free elements, then searching through
* the memory in that chunk. If no chunks
* have free elements, a new chunk is allocated
* and appended to the pool's list.
*
* Returns -
* void pointer to the beginning of the element.
*/
void *BMEMpool_alloc(BMEMpool *pool)
{
BMEMheader *chunkheader, *newheader;
int i,j, addtail, maxindex;
/*See if any chunks have free elements*/
for(i=0; i < pool->totchunks; i++){
if(pool->lookup[i] && pool->lookup[i]->free){
char *chunkp = pool->lookup[i][1];
for(j=0; j < pool->chunksize; j+= pool->elemsize){
if(chunkp[j] == 0){
pool->lookup[i]->free--;
return &(chunkp[j]);
}
}
}
/* Steps to allocate a new chunk
1: Run through chunks listbase and see if there is a missing 'gap' for indices.
If so, insert new chunk there. Then realloc and populate lookup table.
2: Else insert new chunk at the end of the chunks listbase.
*/
newheader = MEM_callocN(sizeof(BMEMheader) + pool->chunksize, "BMEMpool chunk");
newheader->free = (pool->chunksize / pool->elemsize)-1;
addtail = 1;
for(i = 0, chunkheader = pool->chunks.first; i < (pool->totchunks-1); i++, chunkheader=chunkheader->next){
if(chunkheader->next->index != chunkheader->index+1){
/*found a place to insert our new chunk*/
newheader->index = chunkheader->index+1;
BLI_insertlink(&(pool->chunks),chunkheader,newheader);
addtail = 0;
break;
}
}
maxindex = ((BMEMheader*)pool->chunks.last)->index;
if(addtail){
maxindex++;
newheader->index = maxindex;
BLI_addtail(&(pool->chunks),newheader);
}
pool->totchunks++;
/* Reallocate the lookup table.
Note should be taken that the lookup table itself can represent several hundred kilobytes
of wasted memory depending upon how the mesh has changed. The only way to fix this is through
defragmentation.
*/
MEM_freeN(pool->lookup);
pool->lookup = MEM_callocN(sizeof(BMEMheader*)*maxindex,"BMEMheader lookup");
for(chunkheader = pool->chunks.first; chunkheader; chunkheader=chunkheader.next) pool->lookup[chunkheader->index] = chunkheader;
return ++newheader;
}
/**
* BMEMpool_free
*
* Frees the memory used by an element
*
* Returns -
* Nothing
*/
void BMEMpool_free(BMEMpool *pool, int index)
{
int i;
char *elem = BMEMpool_get_elem(pool,index);
for(i=0; i < elemsize; i++) elem[i] = 0;
}
/**
* BMEMpool_get_elem
*
* Takes an index and returns the address for it.
*
* Returns -
* void pointer
*/
void *BMEMpool_get_elem(BMEMpool *pool, int index)
{
BMEMheader *chunkheader = NULL;
char *chunkp;
int header_index,elem_index,elem_bytes;
elem_bytes = index * pool->elemsize;
/*do some error checking to make sure index is valid!*/
header_index = elembytes / pool->chunksize;
if(pool->lookup[header_index] == NULL) return NULL;
elem_index = (elembytes % pool->chunksize) / pool->elemsize;
chunkheader = pool->lookup[header_index];
chunkp = &(chunkheader[1]);
return &(chunkp[elem_index]);
}