[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15081] trunk/blender/source/blender: -> New memory allocator for Bmesh
Geoffrey Bantle
hairbat at yahoo.com
Sun Jun 1 19:15:09 CEST 2008
Revision: 15081
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15081
Author: briggs
Date: 2008-06-01 19:15:03 +0200 (Sun, 01 Jun 2008)
Log Message:
-----------
-> 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.
Modified Paths:
--------------
trunk/blender/source/blender/blenkernel/BKE_bmesh.h
trunk/blender/source/blender/blenkernel/intern/BME_mesh.c
trunk/blender/source/blender/blenkernel/intern/BME_structure.c
trunk/blender/source/blender/blenkernel/intern/bmesh_private.h
trunk/blender/source/blender/blenkernel/intern/modifier.c
trunk/blender/source/blender/src/editmesh_tools.c
Modified: trunk/blender/source/blender/blenkernel/BKE_bmesh.h
===================================================================
--- trunk/blender/source/blender/blenkernel/BKE_bmesh.h 2008-06-01 16:13:04 UTC (rev 15080)
+++ trunk/blender/source/blender/blenkernel/BKE_bmesh.h 2008-06-01 17:15:03 UTC (rev 15081)
@@ -49,6 +49,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;
@@ -57,16 +60,21 @@
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 @@
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 @@
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);
Modified: trunk/blender/source/blender/blenkernel/intern/BME_mesh.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/BME_mesh.c 2008-06-01 16:13:04 UTC (rev 15080)
+++ trunk/blender/source/blender/blenkernel/intern/BME_mesh.c 2008-06-01 17:15:03 UTC (rev 15081)
@@ -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 @@
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 @@
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 @@
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);
Modified: trunk/blender/source/blender/blenkernel/intern/BME_structure.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/BME_structure.c 2008-06-01 16:13:04 UTC (rev 15080)
+++ trunk/blender/source/blender/blenkernel/intern/BME_structure.c 2008-06-01 17:15:03 UTC (rev 15081)
@@ -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 @@
BME_Vert *BME_addvertlist(BME_Mesh *bm, BME_Vert *example){
BME_Vert *v=NULL;
- v = MEM_callocN(sizeof(BME_Vert), "BME Vertex");
+ 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);
- v->EID = bm->nextv;
bm->nextv++;
bm->totvert++;
@@ -103,12 +210,19 @@
}
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_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;
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list