-> New memory allocator for Bmesh
authorGeoffrey Bantle <hairbat@yahoo.com>
Sun, 1 Jun 2008 17:15:03 +0000 (17:15 +0000)
committerGeoffrey Bantle <hairbat@yahoo.com>
Sun, 1 Jun 2008 17:15:03 +0000 (17:15 +0000)
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.

source/blender/blenkernel/BKE_bmesh.h
source/blender/blenkernel/intern/BME_mesh.c
source/blender/blenkernel/intern/BME_structure.c
source/blender/blenkernel/intern/bmesh_private.h
source/blender/blenkernel/intern/modifier.c
source/blender/src/editmesh_tools.c

index 08ad81926887fa07c6ebcaf5547c53770a92a4b6..87202ce047a7bcb7bc8a978afb2001446cab8665 100644 (file)
@@ -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);
index d9d2354ef3602d2519d8618e4d505925164cd33a..307047463cf05b69a17ce2c8c2e8d09bdffa8056 100644 (file)
  *  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);
index d283e1df5ca9cddca74e9fca194aa84bbb91c94d..d261238d1286bf48e19439b3a8bb73e4340d3113 100644 (file)
 #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
  *
index ad90398bf669de2f0139d53c43a2e0c61aad1a7a..ed58421ffb7e9c7dd58ac6c67f2a325f3f0f93e5 100644 (file)
 
 #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);
index f9f17e7762da2b9409b8dd3e4857be8577478909..6185e249b5aeed3317347380e27aab8c1873f3ca 100644 (file)
@@ -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);
index d4ebe181218fee4e1e559d4dcd93992e21a8f8e9..d90a7eb7c168999bc2963f293a5717ae0dc82d4c 100644 (file)
@@ -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);