diff options
author | Geoffrey Bantle <hairbat@yahoo.com> | 2008-06-01 21:15:03 +0400 |
---|---|---|
committer | Geoffrey Bantle <hairbat@yahoo.com> | 2008-06-01 21:15:03 +0400 |
commit | 07b1608fbe52f729eae39c307060f92948aabf37 (patch) | |
tree | 96dcc1dde0038151362edfa437c843d042653e0d /source/blender/blenkernel/intern/BME_structure.c | |
parent | 652ee1e31baa52c8e504bfcf3759ea94c7f5ab66 (diff) |
-> 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.
Diffstat (limited to 'source/blender/blenkernel/intern/BME_structure.c')
-rw-r--r-- | source/blender/blenkernel/intern/BME_structure.c | 162 |
1 files changed, 138 insertions, 24 deletions
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 * |