diff options
Diffstat (limited to 'source/blender/blenlib')
25 files changed, 1172 insertions, 150 deletions
diff --git a/source/blender/blenlib/BLI_array.h b/source/blender/blenlib/BLI_array.h new file mode 100644 index 00000000000..3f5c2cc9d48 --- /dev/null +++ b/source/blender/blenlib/BLI_array.h @@ -0,0 +1,102 @@ +/** + * Array Library + * + * ***** BEGIN GPL 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. + * + * 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) 2008 Blender Foundation. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): Joseph Eagar. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/* +this library needs to be changed to not use macros quite so heavily, +and to be more of a complete array API. The way arrays are +exposed to client code as normal C arrays is very useful though, imho. +it does require some use of macros, however. + +anyway, it's used a bit too heavily to simply rewrite as a +more "correct" solution without macros entirely. I originally wrote this +to be very easy to use, without the normal pain of most array libraries. +This was especially helpful when it came to the massive refactors necessary for +bmesh, and really helped to speed the process up. - joeedh + +little array macro library. example of usage: + +int *arr = NULL; +BLI_array_declare(arr); +int i; + +for (i=0; i<10; i++) { + BLI_array_growone(arr); + arr[i] = something; +} +BLI_array_free(arr); + +arrays are buffered, using double-buffering (so on each reallocation, +the array size is doubled). supposedly this should give good Big Oh +behaviour, though it may not be the best in practice. +*/ + +#define BLI_array_declare(arr) int _##arr##_count=0; void *_##arr##_tmp; void *_##arr##_static = NULL + +/*this will use stack space, up to maxstatic array elements, befoe + switching to dynamic heap allocation*/ +#define BLI_array_staticdeclare(arr, maxstatic) int _##arr##_count=0; void *_##arr##_tmp; char _##arr##_static[maxstatic*sizeof(arr)] + +/*this returns the entire size of the array, including any buffering.*/ +#define BLI_array_totalsize_dyn(arr) ((arr)==NULL ? 0 : MEM_allocN_len(arr) / sizeof(*arr)) +#define BLI_array_totalsize(arr) ((signed int)(((void *)(arr) == (void *)_##arr##_static && (void *)(arr) != NULL) ? (sizeof(_##arr##_static) / sizeof(*arr)) : BLI_array_totalsize_dyn(arr))) + +/*this returns the logical size of the array, not including buffering.*/ +#define BLI_array_count(arr) _##arr##_count + +/*grow the array by one. zeroes the new elements.*/ +#define _BLI_array_growone(arr) \ + BLI_array_totalsize(arr) > _##arr##_count ? ++_##arr##_count : \ + ((_##arr##_tmp = MEM_callocN(sizeof(*arr)*(_##arr##_count*2+2), #arr " " __FILE__ " ")),\ + (arr && memcpy(_##arr##_tmp, arr, sizeof(*arr) * _##arr##_count)),\ + (arr && ((void *)(arr) != (void*)_##arr##_static ? (MEM_freeN(arr), arr) : arr)),\ + (arr = _##arr##_tmp),\ + _##arr##_count++) + +/*returns length of array*/ +#define BLI_array_growone(arr) ((void *)(arr)==NULL && (void *)(_##arr##_static) != NULL ? ((arr=(void*)_##arr##_static), ++_##arr##_count) : _BLI_array_growone(arr)) + + /*appends an item to the array and returns a pointer to the item in the array. + item is not a pointer, but actual data value.*/ +#define BLI_array_append(arr, item) (BLI_array_growone(arr), (arr[_##arr##_count-1] = item), (arr+(_##arr##_count-1))) + +/*grow an array by a specified number of items.*/ +#define BLI_array_growitems(arr, num) {int _i; for (_i=0; _i<(num); _i++) {BLI_array_growone(arr);}} +#define BLI_array_free(arr) if (arr && (char *)arr != _##arr##_static) { BLI_array_fake_user(arr); MEM_freeN(arr); } + +#define BLI_array_pop(arr) ((arr&&_##arr##_count) ? arr[--_##arr##_count] : 0) +/*resets the logical size of an array to zero, but doesn't + free the memory.*/ +#define BLI_array_empty(arr) _##arr##_count=0 + +/*set the count of the array, doesn't actually increase the allocated array + size. don't use this unless you know what you're doing.*/ +#define BLI_array_set_length(arr, count) _##arr##_count = (count) + +/*only to prevent unused warnings*/ +#define BLI_array_fake_user(arr) (void)_##arr##_count, (void)_##arr##_tmp, (void)_##arr##_static diff --git a/source/blender/blenlib/BLI_cellalloc.h b/source/blender/blenlib/BLI_cellalloc.h new file mode 100644 index 00000000000..a6e779d5990 --- /dev/null +++ b/source/blender/blenlib/BLI_cellalloc.h @@ -0,0 +1,57 @@ +/** + * + * ***** BEGIN GPL 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. + * + * 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) 2008 by Blender Foundation. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): none yet. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/* + this evil bit of code is necassary for vgroups and multires to run fast + enough. it is surprisingly tricky allocate MDeformWeights and MDisps in + a way that doesn't cause severe performance problems. once a better solution + is found we can get rid of this code, but until then this is necassary + (though, disabling it if jedmalloc is in use might be feasible). + + ideas for replacement: + ok, mdisps could store a mempool in CustomDataLayer. there might be + one there already? vgroups, uh. . .not sure what to do with vgroups, + they do cause a significant performance problem. + + it's tempting to split vgroups into lots of little customdata layers, + but that would waste a LOT of memory. ugh. can we plug in jemalloc + to guardedalloc, on all platforms? that would work. + + I really hate this little library; it really should be replaced before trunk + reintegration. + + - joeedh +*/ + +void *BLI_cellalloc_malloc(long size, const char *tag); +void *BLI_cellalloc_calloc(long size, const char *tag); +void BLI_cellalloc_free(void *mem); +void BLI_cellalloc_printleaks(void); +int BLI_cellalloc_get_totblock(void); +void BLI_cellalloc_destroy(void); +void *BLI_cellalloc_dupalloc(void *mem); diff --git a/source/blender/blenlib/BLI_edgehash.h b/source/blender/blenlib/BLI_edgehash.h index fba13035f02..1827d69dcab 100644 --- a/source/blender/blenlib/BLI_edgehash.h +++ b/source/blender/blenlib/BLI_edgehash.h @@ -36,6 +36,10 @@ * \brief A general unordered 2-int pair hash table ADT. */ +#include "MEM_guardedalloc.h" +#include "BKE_utildefines.h" +#include "BLI_mempool.h" + struct EdgeHash; struct EdgeHashIterator; typedef struct EdgeHash EdgeHash; @@ -49,22 +53,22 @@ void BLI_edgehash_free (EdgeHash *eh, EdgeHashFreeFP valfreefp); /* Insert edge (v0,v1) into hash with given value, does * not check for duplicates. */ -void BLI_edgehash_insert (EdgeHash *eh, int v0, int v1, void *val); +//void BLI_edgehash_insert (EdgeHash *eh, int v0, int v1, void *val); /* Return value for given edge (v0,v1), or NULL if * if key does not exist in hash. (If need exists * to differentiate between key-value being NULL and * lack of key then see BLI_edgehash_lookup_p(). */ -void* BLI_edgehash_lookup (EdgeHash *eh, int v0, int v1); +//void* BLI_edgehash_lookup (EdgeHash *eh, int v0, int v1); /* Return pointer to value for given edge (v0,v1), * or NULL if key does not exist in hash. */ -void** BLI_edgehash_lookup_p (EdgeHash *eh, int v0, int v1); +//void** BLI_edgehash_lookup_p (EdgeHash *eh, int v0, int v1); /* Return boolean true/false if edge (v0,v1) in hash. */ -int BLI_edgehash_haskey (EdgeHash *eh, int v0, int v1); +//int BLI_edgehash_haskey (EdgeHash *eh, int v0, int v1); /* Return number of keys in hash. */ int BLI_edgehash_size (EdgeHash *eh); @@ -99,5 +103,99 @@ void BLI_edgehashIterator_step (EdgeHashIterator *ehi); /* Determine if an iterator is done. */ int BLI_edgehashIterator_isDone (EdgeHashIterator *ehi); +/**************inlined code************/ +static unsigned int _ehash_hashsizes[]= { + 1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, + 16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, + 4194319, 8388617, 16777259, 33554467, 67108879, 134217757, + 268435459 +}; + +#define EDGEHASH(v0,v1) ((v0*39)^(v1*31)) + +/***/ + +typedef struct EdgeEntry EdgeEntry; +struct EdgeEntry { + EdgeEntry *next; + int v0, v1; + void *val; +}; + +struct EdgeHash { + EdgeEntry **buckets; + BLI_mempool *epool; + int nbuckets, nentries, cursize; +}; + + +BM_INLINE void BLI_edgehash_insert(EdgeHash *eh, int v0, int v1, void *val) { + unsigned int hash; + EdgeEntry *e= BLI_mempool_alloc(eh->epool); + + if (v1<v0) { + v0 ^= v1; + v1 ^= v0; + v0 ^= v1; + } + hash = EDGEHASH(v0,v1)%eh->nbuckets; + + e->v0 = v0; + e->v1 = v1; + e->val = val; + e->next= eh->buckets[hash]; + eh->buckets[hash]= e; + + if (++eh->nentries>eh->nbuckets*3) { + EdgeEntry *e, **old= eh->buckets; + int i, nold= eh->nbuckets; + + eh->nbuckets= _ehash_hashsizes[++eh->cursize]; + eh->buckets= MEM_mallocN(eh->nbuckets*sizeof(*eh->buckets), "eh buckets"); + BMEMSET(eh->buckets, 0, eh->nbuckets*sizeof(*eh->buckets)); + + for (i=0; i<nold; i++) { + for (e= old[i]; e;) { + EdgeEntry *n= e->next; + + hash= EDGEHASH(e->v0,e->v1)%eh->nbuckets; + e->next= eh->buckets[hash]; + eh->buckets[hash]= e; + + e= n; + } + } + + MEM_freeN(old); + } +} + +BM_INLINE void** BLI_edgehash_lookup_p(EdgeHash *eh, int v0, int v1) { + unsigned int hash; + EdgeEntry *e; + + if (v1<v0) { + v0 ^= v1; + v1 ^= v0; + v0 ^= v1; + } + hash = EDGEHASH(v0,v1)%eh->nbuckets; + for (e= eh->buckets[hash]; e; e= e->next) + if (v0==e->v0 && v1==e->v1) + return &e->val; + + return NULL; +} + +BM_INLINE void* BLI_edgehash_lookup(EdgeHash *eh, int v0, int v1) { + void **value_p = BLI_edgehash_lookup_p(eh,v0,v1); + + return value_p?*value_p:NULL; +} + +BM_INLINE int BLI_edgehash_haskey(EdgeHash *eh, int v0, int v1) { + return BLI_edgehash_lookup_p(eh, v0, v1)!=NULL; +} + #endif diff --git a/source/blender/blenlib/BLI_editVert.h b/source/blender/blenlib/BLI_editVert.h index ba745af5a0b..d94d3cd0652 100644 --- a/source/blender/blenlib/BLI_editVert.h +++ b/source/blender/blenlib/BLI_editVert.h @@ -45,6 +45,7 @@ struct DerivedMesh; struct RetopoPaintData; +struct BLI_mempool; /* note; changing this also might affect the undo copy in editmesh.c */ typedef struct EditVert @@ -158,6 +159,8 @@ typedef struct EditMesh HashEdge *hashedgetab; /* this is for the editmesh_fastmalloc */ + struct BLI_mempool *vertpool, *edgepool, *facepool; + EditVert *allverts, *curvert; EditEdge *alledges, *curedge; EditFace *allfaces, *curface; diff --git a/source/blender/blenlib/BLI_fileops.h b/source/blender/blenlib/BLI_fileops.h index 59c01348c07..f32e6bacdc3 100644 --- a/source/blender/blenlib/BLI_fileops.h +++ b/source/blender/blenlib/BLI_fileops.h @@ -47,7 +47,7 @@ int BLI_link(const char *file, const char *to); int BLI_is_writable(const char *filename); /** - * @attention Do not confuse with BLI_exist + * @attention Do not confuse with BLI_exist [joeedh--yet, it calls BLI_exist?] */ int BLI_exists(const char *file); int BLI_copy_fileops(const char *file, const char *to); diff --git a/source/blender/blenlib/BLI_math_color.h b/source/blender/blenlib/BLI_math_color.h index fe09706cb3d..cc443621fa9 100644 --- a/source/blender/blenlib/BLI_math_color.h +++ b/source/blender/blenlib/BLI_math_color.h @@ -87,6 +87,12 @@ void linearrgb_to_srgb_rgba_buf(float *col, int tot); void srgb_to_linearrgb_rgba_rgba_buf(float *col_to, float *col_from, int tot); void linearrgb_to_srgb_rgba_rgba_buf(float *col_to, float *col_from, int tot); +/* rgba buffer convenience functions */ +void srgb_to_linearrgb_rgba_buf(float *col, int tot); +void linearrgb_to_srgb_rgba_buf(float *col, int tot); +void srgb_to_linearrgb_rgba_rgba_buf(float *col_to, float *col_from, int tot); +void linearrgb_to_srgb_rgba_rgba_buf(float *col_to, float *col_from, int tot); + /************************** Other *************************/ int constrain_rgb(float *r, float *g, float *b); diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index 4a7d749842d..16684b0d84a 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -56,6 +56,8 @@ float area_tri_v3(const float a[3], const float b[3], const float c[3]); float area_quad_v3(const float a[3], const float b[3], const float c[3], const float d[3]); float area_poly_v3(int nr, float verts[][3], const float normal[3]); +int is_quad_convex_v3(const float *v1, const float *v2, const float *v3, const float *v4); + /********************************* Distance **********************************/ float dist_to_line_v2(const float p[2], const float l1[2], const float l2[2]); diff --git a/source/blender/blenlib/BLI_math_vector.h b/source/blender/blenlib/BLI_math_vector.h index 5f26bff0ad9..1f56694f85b 100644 --- a/source/blender/blenlib/BLI_math_vector.h +++ b/source/blender/blenlib/BLI_math_vector.h @@ -40,6 +40,8 @@ extern "C" { #ifdef BLI_MATH_INLINE_H #include "intern/math_vector_inline.c" +#else +#define MINLINE #endif /************************************* Init ***********************************/ diff --git a/source/blender/blenlib/BLI_mempool.h b/source/blender/blenlib/BLI_mempool.h index 4ea48929efb..5aa9c196b39 100644 --- a/source/blender/blenlib/BLI_mempool.h +++ b/source/blender/blenlib/BLI_mempool.h @@ -29,18 +29,120 @@ #ifndef BLI_MEMPOOL_H #define BLI_MEMPOOL_H -/** \file BLI_storage.h +/** \file BLI_mempool.h * \ingroup bli * \author Geoffrey Bantle * \brief Simple fast memory allocator. */ +#ifdef __cplusplus +extern "C" +{ +#endif + struct BLI_mempool; -struct BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk, int use_sysmalloc); -void *BLI_mempool_alloc(struct BLI_mempool *pool); -void *BLI_mempool_calloc(struct BLI_mempool *pool); -void BLI_mempool_free(struct BLI_mempool *pool, void *addr); -void BLI_mempool_destroy(struct BLI_mempool *pool); +#include "BKE_utildefines.h" +#include "BLI_listbase.h" +#include "BLI_blenlib.h" +#include <string.h> + +typedef struct BLI_freenode{ + struct BLI_freenode *next; + int freeword; /*used to identify this as a freed node*/ +}BLI_freenode; + +typedef struct BLI_mempool_chunk{ + struct BLI_mempool_chunk *next, *prev; + void *data; +}BLI_mempool_chunk; + +typedef struct BLI_mempool{ + struct ListBase chunks; + int esize, csize, pchunk; /*size of elements and chunks in bytes and number of elements per chunk*/ + BLI_freenode *free; /*free element list. Interleaved into chunk datas.*/ + int totalloc, totused; /*total number of elements allocated in total, and currently in use*/ + int use_sysmalloc, allow_iter; +}BLI_mempool; + +/*allow_iter allows iteration on this mempool. note: this requires that the + first four bytes of the elements never contain the character string + 'free'. use with care.*/ + +BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk, + int use_sysmalloc, int allow_iter); +//void *BLI_mempool_alloc(BLI_mempool *pool); +void *BLI_mempool_calloc(BLI_mempool *pool); +void BLI_mempool_free(BLI_mempool *pool, void *addr); +void BLI_mempool_destroy(BLI_mempool *pool); +int BLI_mempool_count(BLI_mempool *pool); + +/** iteration stuff. note: this may easy to produce bugs with **/ +/*private structure*/ +typedef struct BLI_mempool_iter { + BLI_mempool *pool; + struct BLI_mempool_chunk *curchunk; + int curindex; +} BLI_mempool_iter; + +/*allow iteration on this mempool. note: this requires that the + first four bytes of the elements never contain the character string + 'free'. use with care.*/ +void BLI_mempool_allow_iter(BLI_mempool *pool); +void BLI_mempool_iternew(BLI_mempool *pool, BLI_mempool_iter *iter); +void *BLI_mempool_iterstep(BLI_mempool_iter *iter); + +/************ inlined stuff ***********/ +#define FREEWORD MAKE_ID('f', 'r', 'e', 'e') +#include "MEM_guardedalloc.h" + +BM_INLINE void *BLI_mempool_alloc(BLI_mempool *pool) { + void *retval=NULL; + BLI_freenode *curnode=NULL; + char *addr=NULL; + int j; + + if (!pool) return NULL; + + pool->totused++; + + if(!(pool->free)){ + /*need to allocate a new chunk*/ + BLI_mempool_chunk *mpchunk = pool->use_sysmalloc ? (BLI_mempool_chunk*)malloc(sizeof(BLI_mempool_chunk)) : (BLI_mempool_chunk*)MEM_mallocN(sizeof(BLI_mempool_chunk), "BLI_Mempool Chunk"); + mpchunk->next = mpchunk->prev = NULL; + mpchunk->data = pool->use_sysmalloc ? malloc(pool->csize) : MEM_mallocN(pool->csize, "BLI_Mempool Chunk Data"); + BLI_addtail(&(pool->chunks), mpchunk); + + pool->free = (BLI_freenode*)mpchunk->data; /*start of the list*/ + if (pool->allow_iter) + pool->free->freeword = FREEWORD; + for(addr = (char*)mpchunk->data, j=0; j < pool->pchunk; j++){ + curnode = ((BLI_freenode*)addr); + addr += pool->esize; + curnode->next = (BLI_freenode*)addr; + + if (pool->allow_iter) { + curnode->freeword = FREEWORD; + if (j != pool->pchunk-1) + curnode->next->freeword = FREEWORD; + } + } + curnode->next = NULL; /*terminate the list*/ + + pool->totalloc += pool->pchunk; + } + + retval = pool->free; + if (pool->allow_iter) + pool->free->freeword = 0x7FFFFFFF; + + pool->free = pool->free->next; + //memset(retval, 0, pool->esize); + return retval; +} + +#ifdef __cplusplus +} +#endif #endif diff --git a/source/blender/blenlib/BLI_scanfill.h b/source/blender/blenlib/BLI_scanfill.h index c5acf7b7f70..0c5e6db1826 100644 --- a/source/blender/blenlib/BLI_scanfill.h +++ b/source/blender/blenlib/BLI_scanfill.h @@ -53,6 +53,8 @@ extern "C" { /* scanfill.c: used in displist only... */ struct EditVert *BLI_addfillvert(float *vec); struct EditEdge *BLI_addfilledge(struct EditVert *v1, struct EditVert *v2); + +int BLI_begin_edgefill(void); int BLI_edgefill(short mat_nr); void BLI_end_edgefill(void); diff --git a/source/blender/blenlib/BLI_smallhash.h b/source/blender/blenlib/BLI_smallhash.h new file mode 100755 index 00000000000..1c1cd2a0ed3 --- /dev/null +++ b/source/blender/blenlib/BLI_smallhash.h @@ -0,0 +1,246 @@ +/** + * ***** BEGIN GPL 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. + * + * 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) 2008 Blender Foundation. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): Joseph Eagar. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef BLI_SMALLHASH_H +#define BLI_SMALLHASH_H + +/*******a light stack-friendly hash library****** + * (it uses stack space for smallish hash tables) */ + +/*based on a doubling non-chaining approach */ + +#include "MEM_guardedalloc.h" +#include "BLO_sys_types.h" +#include "BLI_utildefines.h" +#include <string.h> + +extern unsigned int hashsizes[]; +#define NONHASH -25436536 +typedef struct entry {uintptr_t key; void *val;} entry; + +/*how much stack space to use before dynamically allocating memory*/ +#define SMSTACKSIZE 521 +typedef struct SmallHash { + entry *table, _stacktable[SMSTACKSIZE], _copytable[SMSTACKSIZE]; + entry *stacktable, *copytable; + int used; + int curhash; + int size; +} SmallHash; + +typedef struct SmallHashIter { + SmallHash *hash; + int i; +} SmallHashIter; + +/*CELL_UNUSED means this cell is inside a key series, while CELL_FREE + means this cell terminates a key series. + + no chance of anyone shoving INT32_MAX-2 into a *val pointer, I + imagine. hopefully. */ +#define CELL_UNUSED ((void*)0x7FFFFFFF) +#define CELL_FREE ((void*)0x7FFFFFFD) + +#define NONZERO(n) ((n) + !(n)) +#define HASHNEXT(h, hoff) ABS(((h) + ((hoff=NONZERO(hoff*2)+1), hoff))) + +BM_INLINE void BLI_smallhash_init(SmallHash *hash) +{ + int i; + + memset(hash, 0, sizeof(*hash)); + + hash->table = hash->_stacktable; + hash->curhash = 2; + hash->size = hashsizes[hash->curhash]; + + hash->copytable = hash->_copytable; + hash->stacktable = hash->_stacktable; + + for (i=0; i<hash->size; i++) { + hash->table[i].val = CELL_FREE; + } +} + +/*NOTE: does *not* free *hash itself! only the direct data!*/ +BM_INLINE void BLI_smallhash_release(SmallHash *hash) +{ + if (!hash) + return; + + if (hash->table != hash->stacktable) + MEM_freeN(hash->table); +} + +BM_INLINE void BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item) +{ + int h, hoff=1; + + key = ABS(key); + + if (hash->size < hash->used*3) { + int newsize = hashsizes[++hash->curhash]; + entry *tmp; + int i = 0; + + if (hash->table != hash->stacktable || newsize > SMSTACKSIZE) { + tmp = MEM_callocN(sizeof(*hash->table)*newsize, "new hashkeys"); + } else { + SWAP(entry*, hash->stacktable, hash->copytable); + tmp = hash->stacktable; + } + + SWAP(entry*, tmp, hash->table); + + hash->size = newsize; + + for (i=0; i<hash->size; i++) { + hash->table[i].val = CELL_FREE; + } + + for (i=0; i<hashsizes[hash->curhash-1]; i++) { + if (ELEM(tmp[i].val, CELL_UNUSED, CELL_FREE)) + continue; + + h = tmp[i].key; hoff = 1; + while (!ELEM(hash->table[h % newsize].val, CELL_UNUSED, CELL_FREE)) + h = HASHNEXT(h, hoff); + + h %= newsize; + + hash->table[h].key = tmp[i].key; + hash->table[h].val = tmp[i].val; + } + + if (tmp != hash->stacktable && tmp != hash->copytable) { + MEM_freeN(tmp); + } + } + + h = key; hoff = 1; + while (!ELEM(hash->table[h % hash->size].val, CELL_UNUSED, CELL_FREE)) + h = HASHNEXT(h, hoff); + + h %= hash->size; + hash->table[h].key = key; + hash->table[h].val = item; + + hash->used++; +} + +BM_INLINE void BLI_smallhash_remove(SmallHash *hash, uintptr_t key) +{ + int h, hoff=1; + + key = ABS(key); + h = key; + + while (hash->table[h % hash->size].key != key + || hash->table[h % hash->size].val == CELL_UNUSED) + { + if (hash->table[h % hash->size].val == CELL_FREE) + return; + h = HASHNEXT(h, hoff); + } + + h %= hash->size; + hash->table[h].key = 0; + hash->table[h].val = CELL_UNUSED; +} + +BM_INLINE void *BLI_smallhash_lookup(SmallHash *hash, uintptr_t key) +{ + int h, hoff=1; + + key = ABS(key); + h = key; + + if (!hash->table) + return NULL; + + while (hash->table[h % hash->size].key != key + || hash->table[h % hash->size].val == CELL_UNUSED) + { + if (hash->table[h % hash->size].val == CELL_FREE) + return NULL; + h = HASHNEXT(h, hoff); + } + + return hash->table[h % hash->size].val; +} + + +BM_INLINE int BLI_smallhash_haskey(SmallHash *hash, uintptr_t key) +{ + int h = ABS(key), hoff=1; + key = ABS(key); + + if (!hash->table) + return 0; + + while (hash->table[h % hash->size].key != key + || hash->table[h % hash->size].val == CELL_UNUSED) + { + if (hash->table[h % hash->size].val == CELL_FREE) + return 0; + h = HASHNEXT(h, hoff); + } + + return 1; +} + +BM_INLINE int BLI_smallhash_count(SmallHash *hash) +{ + return hash->used; +} + +BM_INLINE void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key) +{ + while (iter->i < iter->hash->size) { + if (iter->hash->table[iter->i].val != CELL_UNUSED && iter->hash->table[iter->i].val != CELL_FREE) { + if (key) + *key = iter->hash->table[iter->i].key; + + iter->i++; + return iter->hash->table[iter->i-1].val; + } + + iter->i++; + } + + return NULL; +} + +BM_INLINE void *BLI_smallhash_iternew(SmallHash *hash, SmallHashIter *iter, uintptr_t *key) +{ + iter->hash = hash; + iter->i = 0; + + return BLI_smallhash_iternext(iter, key); +} + +#endif // BLI_SMALLHASH_H diff --git a/source/blender/blenlib/BLI_sparsemap.h b/source/blender/blenlib/BLI_sparsemap.h new file mode 100755 index 00000000000..0c892997dd4 --- /dev/null +++ b/source/blender/blenlib/BLI_sparsemap.h @@ -0,0 +1,73 @@ +#if 0 +/** + * $Id: + * + * ***** BEGIN GPL 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. + * + * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung + * All rights reserved. + * + * Contributor(s): Joseph Eagar (original author) + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#include "BLI_math_inline.h" + +typedef struct SparseMap { + int max; + int blocksize; + void **blocks; + int totblock; +} SparseMap; + +MALWAYS_INLINE SparseMap *BLI_sparsemap_new(int blocksize, char *name) +{ + SparseMap *sm = MEM_callocN(sizeof(SparseMap), name); + + sm->blocksize = blocksize; + return sm; +} + +MALWAYS_INLINE void BLI_sparsemap_free(SparseMap *sm) +{ + if (sm->blocks) + MEM_freeN(sm->blocks); + + MEM_freeN(sm); +} + +MALWAYS_INLINE void BLI_sparsemap_set(SparseMap *sm, int index, void *ptr) +{ + if (index >= sm->max || (sm->blocks && !sm->blocks[index/sm->blocksize])) { + int totblock = MAX2((index+1)/sm->blocksize, 2); + void *blocks = MEM_callocN(sizeof(void*)*totblock); + + if (sm->blocks) + memcpy(blocks, sm->blocks, sizeof(void*)*sm->totblock); + sm->totblock = totblock; + MEM_freeN(sm->blocks); + sm->blocks = blocks; + } + + if (!sm->blocks[index/sm->blocksize]) { + sm->blocks[index/sm->blocksize] = MEM_mallocN(sizeof(void*)*sm->blocksize); + } + + sm->blocks[index/sm->blocksize] = ptr; +} +#endif diff --git a/source/blender/blenlib/BLI_threads.h b/source/blender/blenlib/BLI_threads.h index 5bf5423d312..e0959b88a5f 100644 --- a/source/blender/blenlib/BLI_threads.h +++ b/source/blender/blenlib/BLI_threads.h @@ -71,6 +71,7 @@ int BLI_system_thread_count(void); /* gets the number of threads the system can #define LOCK_CUSTOM1 3 #define LOCK_RCACHE 4 #define LOCK_OPENGL 5 +#define LOCK_SCANFILL 6 void BLI_lock_thread(int type); void BLI_unlock_thread(int type); diff --git a/source/blender/blenlib/BLI_utildefines.h b/source/blender/blenlib/BLI_utildefines.h index a376d048412..2a2583b1cc2 100644 --- a/source/blender/blenlib/BLI_utildefines.h +++ b/source/blender/blenlib/BLI_utildefines.h @@ -112,7 +112,8 @@ #define VECADD(v1,v2,v3) {*(v1)= *(v2) + *(v3); *(v1+1)= *(v2+1) + *(v3+1); *(v1+2)= *(v2+2) + *(v3+2);} #define VECSUB(v1,v2,v3) {*(v1)= *(v2) - *(v3); *(v1+1)= *(v2+1) - *(v3+1); *(v1+2)= *(v2+2) - *(v3+2);} -#define VECSUB2D(v1,v2,v3) {*(v1)= *(v2) - *(v3); *(v1+1)= *(v2+1) - *(v3+1);} +#define VECSUB2D(v1,v2,v3, fac) {*(v1)= *(v2) - *(v3); *(v1+1)= *(v2+1) - *(v3+1);} +#define VECINTERP(v1,v2,v3, fac) {*(v1) = *(v2) + (*(v3)-*(v2))*(fac); *(v1+1) = *(v2+1) + (*(v3+1)-*(v2+1))*(fac); *(v1+2) = *(v2+2) + (*(v3+2)-*(v2+2))*(fac);} #define VECADDFAC(v1,v2,v3,fac) {*(v1)= *(v2) + *(v3)*(fac); *(v1+1)= *(v2+1) + *(v3+1)*(fac); *(v1+2)= *(v2+2) + *(v3+2)*(fac);} #define VECSUBFAC(v1,v2,v3,fac) {*(v1)= *(v2) - *(v3)*(fac); *(v1+1)= *(v2+1) - *(v3+1)*(fac); *(v1+2)= *(v2+2) - *(v3+2)*(fac);} #define QUATADDFAC(v1,v2,v3,fac) {*(v1)= *(v2) + *(v3)*(fac); *(v1+1)= *(v2+1) + *(v3+1)*(fac); *(v1+2)= *(v2+2) + *(v3+2)*(fac); *(v1+3)= *(v2+3) + *(v3+3)*(fac);} diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index b7827d62851..833449aaf24 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -46,6 +46,7 @@ set(SRC intern/BLI_linklist.c intern/BLI_memarena.c intern/BLI_mempool.c + intern/BLI_cellalloc.c intern/DLRB_tree.c intern/boxpack2d.c intern/bpath.c @@ -82,6 +83,10 @@ set(SRC intern/voxel.c intern/winstuff.c + BLI_array.h + BLI_cellalloc.h + BLI_smallhash.h + BLI_sparsemap.h BLI_args.h BLI_blenlib.h BLI_boxpack2d.h diff --git a/source/blender/blenlib/SConscript b/source/blender/blenlib/SConscript index 00caf8cd01d..c8172439167 100644 --- a/source/blender/blenlib/SConscript +++ b/source/blender/blenlib/SConscript @@ -5,6 +5,8 @@ sources = env.Glob('intern/*.c') cflags='' incs = '. ../makesdna ../blenkernel #/intern/guardedalloc #/intern/ghost ../editors/include ../gpu ../blenloader' +incs += ' ../windowmanager ../bmesh #/extern/glew/include' + incs += ' ' + env['BF_FREETYPE_INC'] incs += ' ' + env['BF_ZLIB_INC'] defs = [] diff --git a/source/blender/blenlib/intern/BLI_cellalloc.c b/source/blender/blenlib/intern/BLI_cellalloc.c new file mode 100644 index 00000000000..47013535ce3 --- /dev/null +++ b/source/blender/blenlib/intern/BLI_cellalloc.c @@ -0,0 +1,203 @@ +/** + * + * ***** BEGIN GPL 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. + * + * 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) 2008 by Blender Foundation. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): Joseph Eagar + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/* + Simple, fast memory allocator that uses many BLI_mempools for allocation. + this is meant to be used by lots of relatively small objects. + + this is a temporary and imperfect fix for performance issues caused + by vgroups. it needs to be replaced with something better, preferably + integrated into guardedalloc. + + Basically, it's a quick fix for vgroups and MDisps (both of which + are major performance hitters). +*/ + +#include "MEM_guardedalloc.h" + +#include "BLI_utildefines.h" + +#include "BLI_blenlib.h" +#include "BLI_linklist.h" + +#include "DNA_listBase.h" +#include "BLI_mempool.h" + +#include "BLI_cellalloc.h" /* own include */ + +#include <string.h> + +static BLI_mempool **pools; +static int totpool = 0; +static ListBase active_mem = {NULL, NULL}; +static int celltotblock = 0; + +#define MEMIDCHECK ('a' | ('b' << 4) | ('c' << 8) | ('d' << 12)) + +typedef struct MemHeader { + struct MemHeader *next, *prev; + + int size; + const char *tag; + int idcheck; +} MemHeader; + +//#define USE_GUARDEDALLOC + +void *BLI_cellalloc_malloc(long size, const char *tag) +{ + MemHeader *memh; + int slot = size + sizeof(MemHeader); + +#ifdef USE_GUARDEDALLOC + return MEM_mallocN(size, tag); +#endif + if (!slot) + return NULL; + + /*stupid optimization trick. + round up to nearest 16 bytes boundary. + this is to reduce the number of potential + pools. hopefully it'll help.*/ + slot += 16 - (slot & 15); + + if (slot >= totpool) { + void *tmp; + + tmp = calloc(1, sizeof(void*)*(slot+1)); + if (pools) { + memcpy(tmp, pools, totpool*sizeof(void*)); + } + + pools = tmp; + totpool = slot+1; + } + + if (!pools[slot]) { + pools[slot] = BLI_mempool_create(slot, 1, 128, 1, 0); + } + + memh = BLI_mempool_alloc(pools[slot]); + memh->size = size; + memh->idcheck = MEMIDCHECK; + memh->tag = tag; + BLI_addtail(&active_mem, memh); + celltotblock++; + + return memh + 1; +} + +void *BLI_cellalloc_calloc(long size, const char *tag) +{ + void *mem = BLI_cellalloc_malloc(size, tag); + BMEMSET(mem, 0, size); + + return mem; +} + +void BLI_cellalloc_free(void *mem) +{ + MemHeader *memh = mem; + int slot; + +#ifdef USE_GUARDEDALLOC + MEM_freeN(mem); + return; +#endif + if (!memh) + return; + + memh--; + if (memh->idcheck != MEMIDCHECK) { + printf("Error in BLI_cellalloc: attempt to free invalid block.\n"); + return; + } + + slot = memh->size + sizeof(MemHeader); + slot += 16 - (slot & 15); + + if (memh->size > 0 && slot < totpool) { + BLI_remlink(&active_mem, memh); + BLI_mempool_free(pools[slot], memh); + celltotblock--; + } else { + printf("Error in BLI_cellalloc: attempt to free corrupted block.\n"); + } +} + +void *BLI_cellalloc_dupalloc(void *mem) +{ + MemHeader *memh = mem; + void *tmp; + +#ifdef USE_GUARDEDALLOC + MEM_freeN(mem); + return NULL; +#endif + if (!memh) + return NULL; + + memh--; + if (memh->idcheck != MEMIDCHECK) { + printf("Error in BLI_cellalloc: attempt to free invalid block.\n"); + return NULL; + } + + tmp = BLI_cellalloc_malloc(memh->size, memh->tag); + memcpy(tmp, mem, memh->size); + + return tmp; +} + +void BLI_cellalloc_printleaks(void) +{ + MemHeader *memh; + + if (!active_mem.first) return; + + for (memh=active_mem.first; memh; memh=memh->next) { + printf("%s %d %p\n", memh->tag, memh->size, memh+1); + } +} + +int BLI_cellalloc_get_totblock(void) +{ + return celltotblock; +} + +void BLI_cellalloc_destroy(void) +{ + int i; + + for (i=0; i<totpool; i++) { + if (pools[i]) { + BLI_mempool_destroy(pools[i]); + pools[i] = NULL; + } + } +} diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index ff08ef4dba9..0c9d6230f1e 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -55,7 +55,7 @@ GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) { GHash *gh= MEM_mallocN(sizeof(*gh), info); gh->hashfp= hashfp; gh->cmpfp= cmpfp; - gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, 0); + gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, 1, 0); gh->cursize= 0; gh->nentries= 0; diff --git a/source/blender/blenlib/intern/BLI_mempool.c b/source/blender/blenlib/intern/BLI_mempool.c index 84e6151abaa..bf635042140 100644 --- a/source/blender/blenlib/intern/BLI_mempool.c +++ b/source/blender/blenlib/intern/BLI_mempool.c @@ -21,7 +21,7 @@ * * The Original Code is: all of this file. * - * Contributor(s): none yet. + * Contributor(s): Geoffery Bantle * * ***** END GPL LICENSE BLOCK ***** */ @@ -36,47 +36,48 @@ */ #include "MEM_guardedalloc.h" + +#include "BLI_utildefines.h" + #include "BLI_blenlib.h" +#include "BLI_linklist.h" #include "BLI_mempool.h" -#include <string.h> +#include "BLI_utildefines.h" -typedef struct BLI_freenode{ - struct BLI_freenode *next; -}BLI_freenode; +#include "DNA_listBase.h" +#include "DNA_ID.h" -typedef struct BLI_mempool_chunk{ - struct BLI_mempool_chunk *next, *prev; - void *data; -}BLI_mempool_chunk; +#include <string.h> -typedef struct BLI_mempool{ - struct ListBase chunks; - int esize, csize, pchunk; /*size of elements and chunks in bytes and number of elements per chunk*/ - struct BLI_freenode *free; /*free element list. Interleaved into chunk datas.*/ - int totalloc, totused; /*total number of elements allocated in total, and currently in use*/ - int use_sysmalloc; -}BLI_mempool; +#define BLI_MEMPOOL_INTERN +#include "BLI_mempool.h" -BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk, int use_sysmalloc) +BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk, + int use_sysmalloc, int allow_iter) { BLI_mempool *pool = NULL; BLI_freenode *lasttail = NULL, *curnode = NULL; int i,j, maxchunks; char *addr; - if (esize < sizeof(void*)) - esize = sizeof(void*); + if (esize < sizeof(void*)*2) + esize = sizeof(void*)*2; + if (esize < sizeof(void*)*2) + esize = sizeof(void*)*2; + /*allocate the pool structure*/ pool = use_sysmalloc ? malloc(sizeof(BLI_mempool)) : MEM_mallocN(sizeof(BLI_mempool), "memory pool"); - pool->esize = esize; + pool->esize = allow_iter ? MAX2(esize, sizeof(BLI_freenode)) : esize; pool->use_sysmalloc = use_sysmalloc; pool->pchunk = pchunk; pool->csize = esize * pchunk; pool->chunks.first = pool->chunks.last = NULL; pool->totused= 0; + pool->allow_iter= allow_iter; maxchunks = tote / pchunk + 1; - + if (maxchunks==0) maxchunks = 1; + /*allocate the actual chunks*/ for(i=0; i < maxchunks; i++){ BLI_mempool_chunk *mpchunk = use_sysmalloc ? malloc(sizeof(BLI_mempool_chunk)) : MEM_mallocN(sizeof(BLI_mempool_chunk), "BLI_Mempool Chunk"); @@ -84,30 +85,49 @@ BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk, int use_sysmall mpchunk->data = use_sysmalloc ? malloc(pool->csize) : MEM_mallocN(pool->csize, "BLI Mempool Chunk Data"); BLI_addtail(&(pool->chunks), mpchunk); - if(i==0) pool->free = mpchunk->data; /*start of the list*/ + if(i==0) { + pool->free = mpchunk->data; /*start of the list*/ + if (pool->allow_iter) + pool->free->freeword = FREEWORD; + } + /*loop through the allocated data, building the pointer structures*/ for(addr = mpchunk->data, j=0; j < pool->pchunk; j++){ curnode = ((BLI_freenode*)addr); addr += pool->esize; curnode->next = (BLI_freenode*)addr; + if (pool->allow_iter) { + if (j != pool->pchunk-1) + curnode->next->freeword = FREEWORD; + curnode->freeword = FREEWORD; + } } /*final pointer in the previously allocated chunk is wrong.*/ - if(lasttail) lasttail->next = mpchunk->data; + if(lasttail) { + lasttail->next = mpchunk->data; + if (pool->allow_iter) + lasttail->freeword = FREEWORD; + } + /*set the end of this chunks memoryy to the new tail for next iteration*/ lasttail = curnode; pool->totalloc += pool->pchunk; } + /*terminate the list*/ curnode->next = NULL; return pool; } +#if 0 void *BLI_mempool_alloc(BLI_mempool *pool){ void *retval=NULL; BLI_freenode *curnode=NULL; char *addr=NULL; int j; - + + if (!pool) return NULL; + pool->totused++; if(!(pool->free)){ @@ -118,10 +138,18 @@ void *BLI_mempool_alloc(BLI_mempool *pool){ BLI_addtail(&(pool->chunks), mpchunk); pool->free = mpchunk->data; /*start of the list*/ + if (pool->allow_iter) + pool->free->freeword = FREEWORD; for(addr = mpchunk->data, j=0; j < pool->pchunk; j++){ curnode = ((BLI_freenode*)addr); addr += pool->esize; curnode->next = (BLI_freenode*)addr; + + if (pool->allow_iter) { + curnode->freeword = FREEWORD; + if (j != pool->pchunk-1) + curnode->next->freeword = FREEWORD; + } } curnode->next = NULL; /*terminate the list*/ @@ -129,15 +157,19 @@ void *BLI_mempool_alloc(BLI_mempool *pool){ } retval = pool->free; + if (pool->allow_iter) + pool->free->freeword = 0x7FFFFFFF; + pool->free = pool->free->next; //memset(retval, 0, pool->esize); return retval; } +#endif void *BLI_mempool_calloc(BLI_mempool *pool){ void *retval=NULL; retval = BLI_mempool_alloc(pool); - memset(retval, 0, pool->esize); + BMEMSET(retval, 0, pool->esize); return retval; } @@ -147,7 +179,9 @@ void BLI_mempool_free(BLI_mempool *pool, void *addr){ //doesnt protect against d BLI_freenode *curnode=NULL; char *tmpaddr=NULL; int i; - + + if (pool->allow_iter) + newhead->freeword = FREEWORD; newhead->next = pool->free; pool->free = newhead; @@ -180,6 +214,50 @@ void BLI_mempool_free(BLI_mempool *pool, void *addr){ //doesnt protect against d } } +void BLI_mempool_iternew(BLI_mempool *pool, BLI_mempool_iter *iter) +{ + if (!pool->allow_iter) { + fprintf(stderr, "evil! you can't iterate over this mempool!\n"); + iter->curchunk = NULL; + iter->curindex = 0; + + return; + } + + iter->pool = pool; + iter->curchunk = pool->chunks.first; + iter->curindex = 0; +} + +static void *bli_mempool_iternext(BLI_mempool_iter *iter) +{ + void *ret = NULL; + + if (!iter->curchunk || !iter->pool->totused) return NULL; + + ret = ((char*)iter->curchunk->data) + iter->pool->esize*iter->curindex; + + iter->curindex++; + + if (iter->curindex >= iter->pool->pchunk) { + iter->curchunk = iter->curchunk->next; + iter->curindex = 0; + } + + return ret; +} + +void *BLI_mempool_iterstep(BLI_mempool_iter *iter) +{ + BLI_freenode *ret; + + do { + ret = bli_mempool_iternext(iter); + } while (ret && ret->freeword == FREEWORD); + + return ret; +} + void BLI_mempool_destroy(BLI_mempool *pool) { BLI_mempool_chunk *mpchunk=NULL; diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c index bcd6855f272..f98d01099b3 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -22,7 +22,7 @@ * * The Original Code is: none of this file. * - * Contributor(s): Daniel Dunbar + * Contributor(s): Daniel Dunbar, Joseph Eagar * * ***** END GPL LICENSE BLOCK ***** * A general (pointer -> pointer) hash table ADT @@ -37,113 +37,23 @@ #include <string.h> #include "MEM_guardedalloc.h" -#include "BLI_edgehash.h" - -/***/ - -static unsigned int hashsizes[]= { - 1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, - 16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, - 4194319, 8388617, 16777259, 33554467, 67108879, 134217757, - 268435459 -}; - -#define EDGEHASH(v0,v1) ((v0*39)^(v1*31)) - -/***/ - -typedef struct Entry Entry; -struct Entry { - Entry *next; - int v0, v1; - void *val; -}; -struct EdgeHash { - Entry **buckets; - int nbuckets, nentries, cursize; -}; +#include "BLI_utildefines.h" +#include "BLI_edgehash.h" +#include "BLI_mempool.h" /***/ EdgeHash *BLI_edgehash_new(void) { - EdgeHash *eh= MEM_mallocN(sizeof(*eh), "EdgeHash"); + EdgeHash *eh= MEM_callocN(sizeof(*eh), "EdgeHash"); eh->cursize= 0; eh->nentries= 0; - eh->nbuckets= hashsizes[eh->cursize]; - - eh->buckets= malloc(eh->nbuckets*sizeof(*eh->buckets)); - memset(eh->buckets, 0, eh->nbuckets*sizeof(*eh->buckets)); - - return eh; -} - -void BLI_edgehash_insert(EdgeHash *eh, int v0, int v1, void *val) { - unsigned int hash; - Entry *e= malloc(sizeof(*e)); - - if (v1<v0) { - v0 ^= v1; - v1 ^= v0; - v0 ^= v1; - } - hash = EDGEHASH(v0,v1)%eh->nbuckets; - - e->v0 = v0; - e->v1 = v1; - e->val = val; - e->next= eh->buckets[hash]; - eh->buckets[hash]= e; + eh->nbuckets= _ehash_hashsizes[eh->cursize]; - if (++eh->nentries>eh->nbuckets*3) { - Entry *e, **old= eh->buckets; - int i, nold= eh->nbuckets; - - eh->nbuckets= hashsizes[++eh->cursize]; - eh->buckets= malloc(eh->nbuckets*sizeof(*eh->buckets)); - memset(eh->buckets, 0, eh->nbuckets*sizeof(*eh->buckets)); - - for (i=0; i<nold; i++) { - for (e= old[i]; e;) { - Entry *n= e->next; - - hash= EDGEHASH(e->v0,e->v1)%eh->nbuckets; - e->next= eh->buckets[hash]; - eh->buckets[hash]= e; - - e= n; - } - } - - free(old); - } -} - -void** BLI_edgehash_lookup_p(EdgeHash *eh, int v0, int v1) { - unsigned int hash; - Entry *e; + eh->buckets= MEM_callocN(eh->nbuckets*sizeof(*eh->buckets), "eh buckets 2"); + eh->epool = BLI_mempool_create(sizeof(EdgeEntry), 512, 512, 1, 0); - if (v1<v0) { - v0 ^= v1; - v1 ^= v0; - v0 ^= v1; - } - hash = EDGEHASH(v0,v1)%eh->nbuckets; - for (e= eh->buckets[hash]; e; e= e->next) - if (v0==e->v0 && v1==e->v1) - return &e->val; - - return NULL; -} - -void* BLI_edgehash_lookup(EdgeHash *eh, int v0, int v1) { - void **value_p = BLI_edgehash_lookup_p(eh,v0,v1); - - return value_p?*value_p:NULL; -} - -int BLI_edgehash_haskey(EdgeHash *eh, int v0, int v1) { - return BLI_edgehash_lookup_p(eh, v0, v1)!=NULL; + return eh; } int BLI_edgehash_size(EdgeHash *eh) { @@ -154,13 +64,13 @@ void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp) { int i; for (i=0; i<eh->nbuckets; i++) { - Entry *e; + EdgeEntry *e; for (e= eh->buckets[i]; e; ) { - Entry *n= e->next; + EdgeEntry *n= e->next; if (valfreefp) valfreefp(e->val); - free(e); + BLI_mempool_free(eh->epool, e); e= n; } @@ -172,8 +82,10 @@ void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp) { void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp) { BLI_edgehash_clear(eh, valfreefp); - - free(eh->buckets); + + BLI_mempool_destroy(eh->epool); + + MEM_freeN(eh->buckets); MEM_freeN(eh); } @@ -183,11 +95,11 @@ void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp) { struct EdgeHashIterator { EdgeHash *eh; int curBucket; - Entry *curEntry; + EdgeEntry *curEntry; }; EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh) { - EdgeHashIterator *ehi= malloc(sizeof(*ehi)); + EdgeHashIterator *ehi= MEM_mallocN(sizeof(*ehi), "eh iter"); ehi->eh= eh; ehi->curEntry= NULL; ehi->curBucket= -1; @@ -200,7 +112,7 @@ EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh) { return ehi; } void BLI_edgehashIterator_free(EdgeHashIterator *ehi) { - free(ehi); + MEM_freeN(ehi); } void BLI_edgehashIterator_getKey(EdgeHashIterator *ehi, int *v0_r, int *v1_r) { diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index 8785415c6a1..6df942e8b13 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -2706,3 +2706,39 @@ float form_factor_hemi_poly(float p[3], float n[3], float v1[3], float v2[3], fl return contrib; } + +/* evaluate if entire quad is a proper convex quad */ + int is_quad_convex_v3(const float *v1, const float *v2, const float *v3, const float *v4) + { + float nor[3], nor1[3], nor2[3], vec[4][2]; + + /* define projection, do both trias apart, quad is undefined! */ + normal_tri_v3( nor1,v1, v2, v3); + normal_tri_v3( nor2,v1, v3, v4); + nor[0]= ABS(nor1[0]) + ABS(nor2[0]); + nor[1]= ABS(nor1[1]) + ABS(nor2[1]); + nor[2]= ABS(nor1[2]) + ABS(nor2[2]); + + if(nor[2] >= nor[0] && nor[2] >= nor[1]) { + vec[0][0]= v1[0]; vec[0][1]= v1[1]; + vec[1][0]= v2[0]; vec[1][1]= v2[1]; + vec[2][0]= v3[0]; vec[2][1]= v3[1]; + vec[3][0]= v4[0]; vec[3][1]= v4[1]; + } + else if(nor[1] >= nor[0] && nor[1]>= nor[2]) { + vec[0][0]= v1[0]; vec[0][1]= v1[2]; + vec[1][0]= v2[0]; vec[1][1]= v2[2]; + vec[2][0]= v3[0]; vec[2][1]= v3[2]; + vec[3][0]= v4[0]; vec[3][1]= v4[2]; + } + else { + vec[0][0]= v1[1]; vec[0][1]= v1[2]; + vec[1][0]= v2[1]; vec[1][1]= v2[2]; + vec[2][0]= v3[1]; vec[2][1]= v3[2]; + vec[3][0]= v4[1]; vec[3][1]= v4[2]; + } + + /* linetests, the 2 diagonals have to instersect to be convex */ + if( isect_line_line_v2(vec[0], vec[2], vec[1], vec[3]) > 0 ) return 1; + return 0; +} diff --git a/source/blender/blenlib/intern/math_vector_inline.c b/source/blender/blenlib/intern/math_vector_inline.c index 9f6a8afe2d5..dc3baf1698a 100644 --- a/source/blender/blenlib/intern/math_vector_inline.c +++ b/source/blender/blenlib/intern/math_vector_inline.c @@ -419,6 +419,29 @@ MINLINE float normalize_v3_v3(float r[3], const float a[3]) return d; } +MINLINE double normalize_dv3(double n[3]) +{ + double d= n[0]*n[0] + n[1]*n[1] + n[2]*n[2]; + + /* a larger value causes normalize errors in a + scaled down models with camera xtreme close */ + if(d > 1.0e-35f) { + double mul; + + d= sqrt(d); + mul = 1.0 / d; + + n[0] *= mul; + n[1] *= mul; + n[2] *= mul; + } else { + n[0] = n[1] = n[2] = 0; + d= 0.0; + } + + return d; +} + MINLINE float normalize_v3(float n[3]) { return normalize_v3_v3(n, n); diff --git a/source/blender/blenlib/intern/pbvh.c b/source/blender/blenlib/intern/pbvh.c index 95a43a998d3..e9a0ddd4825 100644 --- a/source/blender/blenlib/intern/pbvh.c +++ b/source/blender/blenlib/intern/pbvh.c @@ -1535,7 +1535,7 @@ void BLI_pbvh_apply_vertCos(PBVH *pbvh, float (*vertCos)[3]) } /* coordinates are new -- normals should also be updated */ - mesh_calc_normals(pbvh->verts, pbvh->totvert, pbvh->faces, pbvh->totprim, NULL); + mesh_calc_tessface_normals(pbvh->verts, pbvh->totvert, pbvh->faces, pbvh->totprim, NULL); for (a= 0; a < pbvh->totnode; ++a) BLI_pbvh_node_mark_update(&pbvh->nodes[a]); diff --git a/source/blender/blenlib/intern/scanfill.c b/source/blender/blenlib/intern/scanfill.c index 47a07d86e66..c5a5cdeb5b0 100644 --- a/source/blender/blenlib/intern/scanfill.c +++ b/source/blender/blenlib/intern/scanfill.c @@ -32,6 +32,10 @@ * \ingroup bli */ +#include <stdio.h> +#include <math.h> +#include <stdlib.h> +#include <string.h> #include "MEM_guardedalloc.h" @@ -40,6 +44,8 @@ #include "BLI_listbase.h" #include "BLI_math.h" #include "BLI_scanfill.h" +#include "BLI_utildefines.h" +#include "BLI_threads.h" /* callbacks for errors and interrupts and some goo */ static void (*BLI_localErrorCallBack)(const char*) = NULL; @@ -144,7 +150,7 @@ static void *new_mem_element(int size) { int blocksize= 16384; static int offs= 0; /* the current free address */ - static struct mem_elements *cur= 0; + static struct mem_elements *cur= 0, *first; static ListBase lb= {0, 0}; void *adr; @@ -152,6 +158,10 @@ static void *new_mem_element(int size) printf("incorrect use of new_mem_element\n"); } else if(size== -1) { + /*BMESH_TODO: keep the first block, gives memory leak on exit with 'newmem' */ + first = lb.first; + BLI_remlink(&lb, first); + cur= lb.first; while(cur) { MEM_freeN(cur->data); @@ -159,6 +169,12 @@ static void *new_mem_element(int size) } BLI_freelistN(&lb); + /*reset the block we're keeping*/ + BLI_addtail(&lb, first); + memset(first->data, 0, blocksize); + cur= first; + offs= 0; + return NULL; } @@ -187,6 +203,8 @@ void BLI_end_edgefill(void) fillvertbase.first= fillvertbase.last= 0; filledgebase.first= filledgebase.last= 0; fillfacebase.first= fillfacebase.last= 0; + + BLI_unlock_thread(LOCK_SCANFILL); } /* **** FILL ROUTINES *************************** */ @@ -500,7 +518,7 @@ static int scanfill(PolyFill *pf, short mat_nr) EditVert *eve,*v1,*v2,*v3; EditEdge *eed,*nexted,*ed1,*ed2,*ed3; float miny = 0.0; - int a,b,verts, maxface, totface; + int a,b,verts, maxface, totface; short nr, test, twoconnected=0; nr= pf->nr; @@ -752,6 +770,12 @@ static int scanfill(PolyFill *pf, short mat_nr) } +int BLI_begin_edgefill(void) +{ + BLI_lock_thread(LOCK_SCANFILL); + + return 1; +} int BLI_edgefill(short mat_nr) { @@ -767,17 +791,48 @@ int BLI_edgefill(short mat_nr) EditVert *eve; EditEdge *eed,*nexted; PolyFill *pflist,*pf; - float *minp, *maxp, *v1, *v2, norm[3], len; + float limit, *minp, *maxp, *v1, *v2, norm[3], len; short a,c,poly=0,ok=0,toggle=0; int totfaces= 0; /* total faces added */ /* reset variables */ eve= fillvertbase.first; + a = 0; while(eve) { eve->f= 0; eve->xs= 0; eve->h= 0; eve= eve->next; + a += 1; + } + + if (a == 3 && (mat_nr & 2)) { + eve = fillvertbase.first; + + addfillface(eve, eve->next, eve->next->next, 0); + return 1; + } else if (a == 4 && (mat_nr & 2)) { + float vec1[3], vec2[3]; + + eve = fillvertbase.first; + + if (1 && eve->next && eve->next->next && eve->next->next->next) { //BMESH_TODO) { + /*use shortest diagonal for quad*/ + sub_v3_v3v3(vec1, eve->co, eve->next->next->co); + sub_v3_v3v3(vec2, eve->next->co, eve->next->next->next->co); + + if (INPR(vec1, vec1) < INPR(vec2, vec2)) { + addfillface(eve, eve->next, eve->next->next, 0); + addfillface(eve->next->next, eve->next->next->next, eve, 0); + } else{ + addfillface(eve->next, eve->next->next, eve->next->next->next, 0); + addfillface(eve->next->next->next, eve, eve->next, 0); + } + } else { + addfillface(eve, eve->next, eve->next->next, 0); + addfillface(eve->next->next, eve->next->next->next, eve, 0); + } + return 2; } /* first test vertices if they are in edges */ @@ -812,9 +867,17 @@ int BLI_edgefill(short mat_nr) v1= eve->co; v2= 0; eve= fillvertbase.first; + limit = a < 5 ? FLT_EPSILON*200 : M_PI/24.0; while(eve) { if(v2) { if( compare_v3v3(v2, eve->co, COMPLIMIT)==0) { + float inner = angle_v3v3v3(v1, v2, eve->co); + + if (fabs(inner-M_PI) < limit || fabs(inner) < limit) { + eve = eve->next; + continue; + } + len= normal_tri_v3( norm,v1, v2, eve->co); if(len != 0.0) break; } diff --git a/source/blender/blenlib/intern/threads.c b/source/blender/blenlib/intern/threads.c index 7b59a7905aa..937e4ee06db 100644 --- a/source/blender/blenlib/intern/threads.c +++ b/source/blender/blenlib/intern/threads.c @@ -114,6 +114,7 @@ static pthread_mutex_t _viewer_lock = PTHREAD_MUTEX_INITIALIZER; static pthread_mutex_t _custom1_lock = PTHREAD_MUTEX_INITIALIZER; static pthread_mutex_t _rcache_lock = PTHREAD_MUTEX_INITIALIZER; static pthread_mutex_t _opengl_lock = PTHREAD_MUTEX_INITIALIZER; +static pthread_mutex_t _scanfill_lock = PTHREAD_MUTEX_INITIALIZER; static pthread_t mainid; static int thread_levels= 0; /* threads can be invoked inside threads */ @@ -349,6 +350,8 @@ void BLI_lock_thread(int type) pthread_mutex_lock(&_rcache_lock); else if (type==LOCK_OPENGL) pthread_mutex_lock(&_opengl_lock); + else if (type == LOCK_SCANFILL) + pthread_mutex_lock(&_scanfill_lock); } void BLI_unlock_thread(int type) @@ -365,6 +368,8 @@ void BLI_unlock_thread(int type) pthread_mutex_unlock(&_rcache_lock); else if(type==LOCK_OPENGL) pthread_mutex_unlock(&_opengl_lock); + else if(type == LOCK_SCANFILL) + pthread_mutex_unlock(&_scanfill_lock); } /* Mutex Locks */ |