-> New memory allocator for Bmesh

	
Added a new pooling allocator for Bmesh based upon
the pool allocator availible in the Boost C++ library
as described here:

http://www.boost.org/doc/libs/1_34_0/libs/pool/doc/concepts.html

Each pool allocates elements of a fixed size, so every
element type in a mesh gets its own pool. For instance
verts occupy a different pool than edges. Each pool
is comprised of multiple arrays of a fixed size and allocating
/freeing elements is simple as removing or adding a head 
to a linked list. Since the list of free elements is interleaved
throughout the unused space in the arrays, the overhead
for storing the free list is only 1 pointer total per pool.
	
This makes building/destroying bmesh structures much faster
and saves quite a bit of memory as well.

6 files changed, 184 insertions, 77 deletions

diff --git a/source/blender/blenkernel/BKE_bmesh.h b/source/blender/blenkernel/BKE_bmesh.h
index 08ad8192688..87202ce047a 100644
--- a/source/blender/blenkernel/BKE_bmesh.h
+++ b/source/blender/blenkernel/BKE_bmesh.h
@@ -50,6 +50,9 @@ struct BME_Edge;
 struct BME_Poly;
 struct BME_Loop;
 
+struct BME_mempool;
+typedef struct BME_mempool BME_mempool;
+
 typedef struct BME_CycleNode{
 	struct BME_CycleNode *next, *prev;
 	void *data;
@@ -57,16 +60,21 @@ typedef struct BME_CycleNode{
 
 typedef struct BME_Mesh
 {
-	ListBase verts, edges, polys, loops;
-	int totvert, totedge, totpoly, totloop;			/*record keeping*/
-	int nextv, nexte, nextp, nextl;					/*Next element ID for verts/edges/faces/loops. Never reused*/
-	struct CustomData vdata, edata, pdata, ldata;	/*Custom Data Layer information*/
+	ListBase verts, edges, polys;
+	/*memory pools used for storing mesh elements*/
+	struct BME_mempool *vpool;
+	struct BME_mempool *epool;
+	struct BME_mempool *ppool;
+	struct BME_mempool *lpool;
 	/*some scratch arrays used by eulers*/
 	struct BME_Vert **vtar;
 	struct BME_Edge **edar;
 	struct BME_Loop **lpar;
 	struct BME_Poly **plar;
 	int vtarlen, edarlen, lparlen, plarlen;
+	int totvert, totedge, totpoly, totloop;			/*record keeping*/
+	int nextv, nexte, nextp, nextl;					/*Next element ID for verts/edges/faces/loops. Never reused*/
+	//struct CustomData vdata, edata, pdata, ldata;	/*Custom Data Layer information*/
 } BME_Mesh;
 
 typedef struct BME_Vert
@@ -102,7 +110,6 @@ typedef struct BME_Loop
 	struct BME_Loop *next, *prev;					/*circularly linked list around face*/
 	int EID;
 	struct BME_CycleNode radial;					/*circularly linked list used to find faces around an edge*/
-	struct BME_CycleNode *gref;						/*pointer to loop ref. Nasty.*/
 	struct BME_Vert *v;								/*vertex that this loop starts at.*/
 	struct BME_Edge *e;								/*edge this loop belongs to*/
 	struct BME_Poly *f;								/*face this loop belongs to*/	
@@ -146,7 +153,7 @@ int BME_radial_find_face(struct BME_Edge *e,struct BME_Poly *f);
 struct BME_Loop *BME_loop_find_loop(struct BME_Poly *f, struct BME_Vert *v);
 
 /*MESH CREATION/DESTRUCTION*/
-struct BME_Mesh *BME_make_mesh(void);
+struct BME_Mesh *BME_make_mesh(int valloc, int ealloc, int lalloc, int palloc);
 void BME_free_mesh(struct BME_Mesh *bm);
 /*FULL MESH VALIDATION*/
 int BME_validate_mesh(struct BME_Mesh *bm, int halt);
diff --git a/source/blender/blenkernel/intern/BME_mesh.c b/source/blender/blenkernel/intern/BME_mesh.c
index d9d2354ef36..307047463cf 100644
--- a/source/blender/blenkernel/intern/BME_mesh.c
+++ b/source/blender/blenkernel/intern/BME_mesh.c
@@ -62,11 +62,21 @@
  *  Allocates a new BME_Mesh structure
 */
 
-BME_Mesh *BME_make_mesh(void){
+
+
+BME_Mesh *BME_make_mesh(int valloc, int ealloc, int lalloc, int palloc){
+	/*allocate the structure*/
 	BME_Mesh *bm = MEM_callocN(sizeof(BME_Mesh),"BMesh");
+	/*allocate the memory pools for the mesh elements*/
+	bm->vpool = BME_mempool_create(sizeof(BME_Vert), valloc, valloc);
+	bm->epool = BME_mempool_create(sizeof(BME_Edge), ealloc, ealloc);
+	bm->ppool = BME_mempool_create(sizeof(BME_Poly), palloc, palloc);
+	bm->lpool = BME_mempool_create(sizeof(BME_Loop), lalloc, lalloc);
+	/*allocate the customdata pools*/
 	return bm;
 }
 
+
 /*	
  *	BME FREE MESH
  *
@@ -75,45 +85,13 @@ BME_Mesh *BME_make_mesh(void){
 
 void BME_free_mesh(BME_Mesh *bm)
 {
-	BME_Poly *bf, *nextf;
-	BME_Edge *be, *nexte;
-	BME_Vert *bv, *nextv;
-	BME_CycleNode *loopref;
-	
-	/*destroy polygon data*/
-	bf = bm->polys.first;
-	while(bf){
-		nextf = bf->next;
-		BLI_remlink(&(bm->polys), bf);
-		BME_free_poly(bm, bf);
-		
-		bf = nextf;
-	}
-	/*destroy edge data*/
-	be = bm->edges.first;
-	while(be){
-		nexte = be->next;
-		BLI_remlink(&(bm->edges), be);
-		BME_free_edge(bm, be);
-		be = nexte;
-	}
-	/*destroy vert data*/
-	bv = bm->verts.first;
-	while(bv){
-		nextv = bv->next;
-		BLI_remlink(&(bm->verts), bv);
-		BME_free_vert(bm, bv);
-		bv = nextv; 
-	}
-	
-	for(loopref=bm->loops.first;loopref;loopref=loopref->next) BME_delete_loop(bm,loopref->data);
-	BLI_freelistN(&(bm->loops));
-	
-	//CustomData_free(&bm->vdata, 0);
-	//CustomData_free(&bm->edata, 0);
-	//CustomData_free(&bm->ldata, 0);
-	//CustomData_free(&bm->pdata, 0);
-	
+	/*destroy element pools*/
+	BME_mempool_destroy(bm->vpool);
+	BME_mempool_destroy(bm->epool);
+	BME_mempool_destroy(bm->ppool);
+	BME_mempool_destroy(bm->lpool);
+	/*destroy custom data pools*/
+
 	MEM_freeN(bm);	
 }
 
@@ -156,8 +134,7 @@ void BME_model_end(BME_Mesh *bm){
 	totvert = BLI_countlist(&(bm->verts));
 	totedge = BLI_countlist(&(bm->edges));
 	totpoly = BLI_countlist(&(bm->polys));
-	totloop = BLI_countlist(&(bm->loops));
-	
+
 	if(bm->vtar) MEM_freeN(bm->vtar);
 	if(bm->edar) MEM_freeN(bm->edar);
 	if(bm->lpar) MEM_freeN(bm->lpar);
@@ -167,10 +144,10 @@ void BME_model_end(BME_Mesh *bm){
 	bm->edar = NULL;
 	bm->lpar = NULL;
 	bm->plar = NULL;
-	bm->vtarlen = bm->edarlen = bm->lparlen = bm->plarlen = 1024;
+	bm->vtarlen = bm->edarlen = bm->lparlen = bm->plarlen = 0;
 	
 	
-	if(bm->totvert!=totvert || bm->totedge!=totedge || bm->totpoly!=totpoly || bm->totloop!=totloop)
+	if(bm->totvert!=totvert || bm->totedge!=totedge || bm->totpoly!=totpoly)
 		BME_error();
 	
 	meshok = BME_validate_mesh(bm, 1);
diff --git a/source/blender/blenkernel/intern/BME_structure.c b/source/blender/blenkernel/intern/BME_structure.c
index d283e1df5ca..d261238d128 100644
--- a/source/blender/blenkernel/intern/BME_structure.c
+++ b/source/blender/blenkernel/intern/BME_structure.c
@@ -43,6 +43,105 @@
 #include "BLI_ghash.h"
 
 #include "BKE_customdata.h"
+
+/*
+	Simple, fast memory allocator for allocating many elements of the same size.
+*/
+typedef struct BME_mempool_chunk{
+	struct BME_mempool_chunk *next, *prev;
+	void *data;
+}BME_mempool_chunk;
+
+/*this is just to make things prettier*/
+typedef struct BME_freenode{
+	struct BME_freenode *next;
+}BME_freenode;
+
+typedef struct BME_mempool{
+	struct ListBase chunks;
+	int esize, csize, pchunk;		/*size of elements and chunks in bytes and number of elements per chunk*/
+	struct BME_freenode	*free;		/*free element list. Interleaved into chunk datas.*/
+}BME_mempool;
+
+BME_mempool *BME_mempool_create(int esize, int tote, int pchunk)
+{	BME_mempool  *pool = NULL;
+	BME_freenode *lasttail = NULL, *curnode = NULL;
+	int i,j, maxchunks;
+	char *addr;
+
+	/*allocate the pool structure*/
+	pool = MEM_mallocN(sizeof(BME_mempool),"memory pool");
+	pool->esize = esize;
+	pool->pchunk = pchunk;	
+	pool->csize = esize * pchunk;
+	pool->chunks.first = pool->chunks.last = NULL;
+	
+	maxchunks = tote / pchunk;
+	
+	/*allocate the actual chunks*/
+	for(i=0; i < maxchunks; i++){
+		BME_mempool_chunk *mpchunk = MEM_mallocN(sizeof(BME_mempool_chunk), "BME_Mempool Chunk");
+		mpchunk->next = mpchunk->prev = NULL;
+		mpchunk->data = MEM_mallocN(pool->csize, "BME Mempool Chunk Data");
+		BLI_addtail(&(pool->chunks), mpchunk);
+		
+		if(i==0) pool->free = mpchunk->data; /*start of the list*/
+		/*loop through the allocated data, building the pointer structures*/
+		for(addr = mpchunk->data, j=0; j < pool->pchunk; j++){
+			curnode = ((BME_freenode*)addr);
+			addr += pool->esize;
+			curnode->next = (BME_freenode*)addr;
+		}
+		/*final pointer in the previously allocated chunk is wrong.*/
+		if(lasttail) lasttail->next = mpchunk->data;
+		/*set the end of this chunks memory to the new tail for next iteration*/
+		lasttail = curnode;
+	}
+	/*terminate the list*/
+	curnode->next = NULL;
+	return pool;
+}
+
+void *BME_mempool_alloc(BME_mempool *pool){
+	void *retval=NULL;
+	BME_freenode *curnode=NULL;
+	char *addr=NULL;
+	int j;
+
+	if(!(pool->free)){
+		/*need to allocate a new chunk*/
+		BME_mempool_chunk *mpchunk = MEM_mallocN(sizeof(BME_mempool_chunk), "BME_Mempool Chunk");
+		mpchunk->next = mpchunk->prev = NULL;
+		mpchunk->data = MEM_mallocN(pool->csize, "BME_Mempool Chunk Data");
+		BLI_addtail(&(pool->chunks), mpchunk);
+
+		pool->free = mpchunk->data; /*start of the list*/
+		for(addr = mpchunk->data, j=0; j < pool->pchunk; j++){
+			curnode = ((BME_freenode*)addr);
+			addr += pool->esize;
+			curnode->next = (BME_freenode*)addr;
+		}
+		curnode->next = NULL; /*terminate the list*/
+	}
+
+	retval = pool->free;
+	pool->free = pool->free->next;
+	//memset(retval, 0, pool->esize);
+	return retval;
+}
+
+void BME_mempool_free(BME_mempool *pool, void *addr){ //doesnt protect against double frees, dont be stupid!
+	BME_freenode *newhead = addr;
+	newhead->next = pool->free;
+	pool->free = newhead;
+}
+void BME_mempool_destroy(BME_mempool *pool)
+{
+	BME_mempool_chunk *mpchunk=NULL;
+	for(mpchunk = pool->chunks.first; mpchunk; mpchunk = mpchunk->next) MEM_freeN(mpchunk->data);
+	BLI_freelistN(&(pool->chunks));
+	MEM_freeN(pool);
+}
 /**
  *	MISC utility functions.
  *
@@ -86,9 +185,17 @@ int BME_edge_swapverts(BME_Edge *e, BME_Vert *orig, BME_Vert *new){
 
 BME_Vert *BME_addvertlist(BME_Mesh *bm, BME_Vert *example){
 	BME_Vert *v=NULL;
-	v = MEM_callocN(sizeof(BME_Vert), "BME Vertex");
-	BLI_addtail(&(bm->verts), v);
+	v = BME_mempool_alloc(bm->vpool);
+	v->next = v->prev = NULL;
 	v->EID = bm->nextv;
+	v->co[0] = v->co[1] = v->co[2] = 0.0f;
+	v->no[0] = v->no[1] = v->no[2] = 0.0f;
+	v->edge = NULL;
+	v->data = NULL;
+	v->eflag1 = v->eflag2 = v->tflag1 = v->tflag2 = 0;
+	v->flag = v->h = 0;
+	v->bweight = 0.0f;
+	BLI_addtail(&(bm->verts), v);
 	bm->nextv++;
 	bm->totvert++;
 
@@ -103,12 +210,19 @@ BME_Vert *BME_addvertlist(BME_Mesh *bm, BME_Vert *example){
 }
 BME_Edge *BME_addedgelist(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Edge *example){
 	BME_Edge *e=NULL;
-	e = MEM_callocN(sizeof(BME_Edge), "BME_Edge");
+	e = BME_mempool_alloc(bm->epool);
+	e->next = e->prev = NULL;
+	e->EID = bm->nexte;
 	e->v1 = v1;
 	e->v2 = v2;
+	e->d1.next = e->d1.prev = e->d2.next = e->d2.prev = NULL;
 	e->d1.data = e;
 	e->d2.data = e;
-	e->EID = bm->nexte;
+	e->loop = NULL;
+	e->data = NULL;
+	e->eflag1 = e->eflag2 = e->tflag1 = e->tflag2 = 0;
+	e->flag = e->h = 0;
+	e->crease = e->bweight = 0.0f;
 	bm->nexte++;
 	bm->totedge++;
 	BLI_addtail(&(bm->edges), e);
@@ -124,16 +238,17 @@ BME_Edge *BME_addedgelist(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Edge *ex
 BME_Loop *BME_create_loop(BME_Mesh *bm, BME_Vert *v, BME_Edge *e, BME_Poly *f, BME_Loop *example){
 	/*allocate a BME_Loop and add it to the loophash*/
 	BME_Loop *l=NULL;
-	BME_CycleNode *loopnode = MEM_callocN(sizeof(BME_CycleNode),"BME Loop Reference");
-	l = MEM_callocN(sizeof(BME_Loop), "BME_Loop");
+	l = BME_mempool_alloc(bm->lpool);
+	l->next = l->prev = NULL;
+	l->EID = bm->nextl;
+	l->radial.next = l->radial.prev = NULL;
 	l->radial.data = l;
 	l->v = v;
 	l->e = e;
 	l->f = f;
-	l->EID = bm->nextl;
-	l->gref = loopnode;
-	loopnode->data = l;
-	BLI_addtail(&(bm->loops),loopnode);
+	l->data = NULL;
+	l->eflag1 = l->eflag2 = l->tflag1 = l->tflag2 = 0;
+	l->flag = l->h = 0; //stupid waste!
 	bm->nextl++;
 	bm->totloop++;
 	
@@ -148,9 +263,15 @@ BME_Loop *BME_create_loop(BME_Mesh *bm, BME_Vert *v, BME_Edge *e, BME_Poly *f, B
 
 BME_Poly *BME_addpolylist(BME_Mesh *bm, BME_Poly *example){
 	BME_Poly *f = NULL;
-	f= MEM_callocN(sizeof(BME_Poly),"BME_Poly");
-	BLI_addtail(&(bm->polys),f);
+	f = BME_mempool_alloc(bm->ppool);
+	f->next = f->prev = NULL;
 	f->EID = bm->nextp;
+	f->loopbase = NULL;
+	f->len = 0;
+	f->data = NULL;
+	f->eflag1 = f->eflag2 = f->tflag1 = f->tflag2 = 0;
+	f->flag = f->h = f->mat_nr;
+	BLI_addtail(&(bm->polys),f);
 	bm->nextp++;
 	bm->totpoly++;
 
@@ -169,30 +290,23 @@ BME_Poly *BME_addpolylist(BME_Mesh *bm, BME_Poly *example){
 void BME_free_vert(BME_Mesh *bm, BME_Vert *v){
 	bm->totvert--;
 	//CustomData_em_free_block(&bm->vdata, &v->data);
-	MEM_freeN(v);
+	BME_mempool_free(bm->vpool, v);
 }
 void BME_free_edge(BME_Mesh *bm, BME_Edge *e){
 	bm->totedge--;
 	//CustomData_em_free_block(&bm->edata, &e->data);
-	MEM_freeN(e);
+	BME_mempool_free(bm->epool, e);
 }
 void BME_free_poly(BME_Mesh *bm, BME_Poly *f){
 	bm->totpoly--;
 	//CustomData_em_free_block(&bm->pdata, &f->data);
-	MEM_freeN(f);
+	BME_mempool_free(bm->ppool, f);
 }
-void BME_delete_loop(BME_Mesh *bm, BME_Loop *l){
+void BME_free_loop(BME_Mesh *bm, BME_Loop *l){
 	bm->totloop--;
 	//CustomData_em_free_block(&bm->ldata, &l->data);
-	MEM_freeN(l);
+	BME_mempool_free(bm->lpool, l);
 }
-void BME_free_loop(BME_Mesh *bm, BME_Loop *l){
-	BME_CycleNode *loopref = l->gref;
-	BLI_freelinkN(&(bm->loops),loopref);
-	BME_delete_loop(bm,l);
-}
-
-
 /**
  *	BMESH CYCLES
  *
diff --git a/source/blender/blenkernel/intern/bmesh_private.h b/source/blender/blenkernel/intern/bmesh_private.h
index ad90398bf66..ed58421ffb7 100644
--- a/source/blender/blenkernel/intern/bmesh_private.h
+++ b/source/blender/blenkernel/intern/bmesh_private.h
@@ -39,6 +39,15 @@
 
 #include "BKE_bmesh.h"
 
+/*MEMORY MANAGMENT*/
+struct BME_mempool;
+typedef struct BME_mempool BME_mempool;
+
+struct BME_mempool *BME_mempool_create(int esize, int tote, int pchunk);
+void BME_mempool_destroy(struct BME_mempool *pool);
+void *BME_mempool_alloc(struct BME_mempool *pool);
+void BME_mempool_free(struct BME_mempool *pool, void *address);
+
 /*ALLOCATION/DEALLOCATION*/
 struct BME_Vert *BME_addvertlist(struct BME_Mesh *bm, struct BME_Vert *example);
 struct BME_Edge *BME_addedgelist(struct BME_Mesh *bm, struct BME_Vert *v1, struct BME_Vert *v2, struct BME_Edge *example);
@@ -49,7 +58,7 @@ void BME_free_vert(struct BME_Mesh *bm, struct BME_Vert *v);
 void BME_free_edge(struct BME_Mesh *bm, struct BME_Edge *e);
 void BME_free_poly(struct BME_Mesh *bm, struct BME_Poly *f);
 void BME_free_loop(struct BME_Mesh *bm, struct BME_Loop *l);
-void BME_delete_loop(struct BME_Mesh *bm, struct BME_Loop *l);
+//void BME_delete_loop(struct BME_Mesh *bm, struct BME_Loop *l);
 
 /*DOUBLE CIRCULAR LINKED LIST FUNCTIONS*/
 void BME_cycle_append(void *h, void *nt);
diff --git a/source/blender/blenkernel/intern/modifier.c b/source/blender/blenkernel/intern/modifier.c
index f9f17e7762d..6185e249b5a 100644
--- a/source/blender/blenkernel/intern/modifier.c
+++ b/source/blender/blenkernel/intern/modifier.c
@@ -2754,7 +2754,7 @@ static DerivedMesh *bevelModifier_applyModifier(
 		//~ }
 	//~ }
 
-	bm = BME_make_mesh();
+	bm = BME_make_mesh(512,512,2048,512);
 	bm = BME_derivedmesh_to_bmesh(derivedData, bm);
 	BME_bevel(bm,bmd->value,bmd->res,options,defgrp_index,bmd->bevel_angle,NULL);
 	result = BME_bmesh_to_derivedmesh(bm,derivedData);
diff --git a/source/blender/src/editmesh_tools.c b/source/blender/src/editmesh_tools.c
index d4ebe181218..d90a7eb7c16 100644
--- a/source/blender/src/editmesh_tools.c
+++ b/source/blender/src/editmesh_tools.c
@@ -4497,7 +4497,7 @@ void bevel_menu() {
 	while(G.editBMesh->options & BME_BEVEL_RUNNING) {
 		options = G.editBMesh->options;
 		res = G.editBMesh->res;
-		bm = BME_make_mesh();
+		bm = BME_make_mesh(512,512,2048,512);
 		bm = BME_editmesh_to_bmesh(G.editMesh, bm);
 		BIF_undo_push("Pre-Bevel");
 		free_editMesh(G.editMesh);