diff options
author | Campbell Barton <ideasman42@gmail.com> | 2011-09-09 06:52:20 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2011-09-09 06:52:20 +0400 |
commit | fa59b801898c807d958e131c6b3ae032dc0b0e38 (patch) | |
tree | b107af1868e4f74829579b9a797b0319a6f40a88 | |
parent | 38b2618319530313d2cd5cc19f1c44355530b53b (diff) |
move smallhash into its own C file, was inlineing fairly large functions.
-rwxr-xr-x | source/blender/blenlib/BLI_smallhash.h | 225 | ||||
-rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 1 | ||||
-rw-r--r-- | source/blender/blenlib/intern/smallhash.c | 280 | ||||
-rwxr-xr-x | source/blender/editors/mesh/knifetool.c | 28 | ||||
-rw-r--r-- | source/blender/modifiers/intern/MOD_mirror.c | 3 |
5 files changed, 308 insertions, 229 deletions
diff --git a/source/blender/blenlib/BLI_smallhash.h b/source/blender/blenlib/BLI_smallhash.h index 2fafda9b2b8..c956b8c63ea 100755 --- a/source/blender/blenlib/BLI_smallhash.h +++ b/source/blender/blenlib/BLI_smallhash.h @@ -28,221 +28,46 @@ #ifndef BLI_SMALLHASH_H #define BLI_SMALLHASH_H -/*******a light stack-friendly hash library****** - * (it uses stack space for smallish hash tables) */ +/** \file BLI_smallhash.h + * \ingroup bli + */ -/*based on a doubling non-chaining approach */ +/* a light stack-friendly hash library, + * (it uses stack space for smallish hash tables) */ -#include "MEM_guardedalloc.h" -#include "BLO_sys_types.h" -#include "BLI_utildefines.h" -#include <string.h> +/* based on a doubling non-chaining approach */ -extern unsigned int hashsizes[]; -#define NONHASH -25436536 -typedef struct entry {uintptr_t key; void *val;} entry; +typedef struct { + uintptr_t key; + void *val; +} SmallHashEntry; /*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; + SmallHashEntry *table; + SmallHashEntry _stacktable[SMSTACKSIZE]; + SmallHashEntry _copytable[SMSTACKSIZE]; + SmallHashEntry *stacktable, *copytable; int used; int curhash; int size; } SmallHash; -typedef struct SmallHashIter { +typedef struct { 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; - - 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 = ABS((int)(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 = ABS((int)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; - - h = ABS((int)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; - void *v; - - h = ABS((int)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); - } - - v = hash->table[h % hash->size].val; - if (ELEM(v, CELL_UNUSED, CELL_FREE)) - return NULL; - return v; -} - - -BM_INLINE int BLI_smallhash_haskey(SmallHash *hash, uintptr_t key) -{ - int h = ABS((int)key); - int hoff =1; - - 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 !ELEM(hash->table[h % hash->size].val, CELL_UNUSED, CELL_FREE); -} - -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); -} +void BLI_smallhash_init(SmallHash *hash); +void BLI_smallhash_release(SmallHash *hash); +void BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item); +void BLI_smallhash_remove(SmallHash *hash, uintptr_t key); +void * BLI_smallhash_lookup(SmallHash *hash, uintptr_t key); +int BLI_smallhash_haskey(SmallHash *hash, uintptr_t key); +int BLI_smallhash_count(SmallHash *hash); +void * BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key); +void * BLI_smallhash_iternew(SmallHash *hash, SmallHashIter *iter, uintptr_t *key); +/* void BLI_smallhash_print(SmallHash *hash); */ /* UNUSED */ #endif // BLI_SMALLHASH_H diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 0fde91000b4..7ca1dba9cdc 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -79,6 +79,7 @@ set(SRC intern/rand.c intern/rct.c intern/scanfill.c + intern/smallhash.c intern/storage.c intern/string.c intern/threads.c diff --git a/source/blender/blenlib/intern/smallhash.c b/source/blender/blenlib/intern/smallhash.c new file mode 100644 index 00000000000..c78dcd415cc --- /dev/null +++ b/source/blender/blenlib/intern/smallhash.c @@ -0,0 +1,280 @@ +/** + * ***** 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 ***** + */ + +#include "MEM_guardedalloc.h" +#include "BLI_utildefines.h" +#include <string.h> + +#include "BLI_smallhash.h" + +/* SMHASH_CELL_UNUSED means this cell is inside a key series, + * while SMHASH_CELL_FREE means this cell terminates a key series. + * + * no chance of anyone shoving INT32_MAX-2 into a *val pointer, I + * imagine. hopefully. + * + * note: these have the SMHASH suffix because we may want to make them public. + */ +#define SMHASH_CELL_UNUSED ((void *)0x7FFFFFFF) +#define SMHASH_CELL_FREE ((void *)0x7FFFFFFD) + +#define SMHASH_NONZERO(n) ((n) + !(n)) +#define SMHASH_NEXT(h, hoff) ABS(((h) + ((hoff=SMHASH_NONZERO(hoff*2)+1), hoff))) + +extern unsigned int hashsizes[]; + +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 = SMHASH_CELL_FREE; + } +} + +/*NOTE: does *not* free *hash itself! only the direct data!*/ +void BLI_smallhash_release(SmallHash *hash) +{ + if (hash == NULL) { + return; + } + + if (hash->table != hash->stacktable) { + MEM_freeN(hash->table); + } +} + +void BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item) +{ + int h, hoff=1; + + if (hash->size < hash->used * 3) { + int newsize = hashsizes[++hash->curhash]; + SmallHashEntry *tmp; + int i = 0; + + if (hash->table != hash->stacktable || newsize > SMSTACKSIZE) { + tmp = MEM_callocN(sizeof(*hash->table) * newsize, "new hashkeys"); + } + else { + SWAP(SmallHashEntry *, hash->stacktable, hash->copytable); + tmp = hash->stacktable; + } + + SWAP(SmallHashEntry *, tmp, hash->table); + + hash->size = newsize; + + for (i=0; i<hash->size; i++) { + hash->table[i].val = SMHASH_CELL_FREE; + } + + for (i=0; i<hashsizes[hash->curhash-1]; i++) { + if (ELEM(tmp[i].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) { + continue; + } + + h = ABS((int)(tmp[i].key)); + hoff = 1; + while (!ELEM(hash->table[h % newsize].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) { + h = SMHASH_NEXT(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 = ABS((int)key); + hoff = 1; + + while (!ELEM(hash->table[h % hash->size].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) { + h = SMHASH_NEXT(h, hoff); + } + + h %= hash->size; + hash->table[h].key = key; + hash->table[h].val = item; + + hash->used++; +} + +void BLI_smallhash_remove(SmallHash *hash, uintptr_t key) +{ + int h, hoff=1; + + h = ABS((int)key); + + while ((hash->table[h % hash->size].key != key) || + (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED)) + { + if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) { + return; + } + + h = SMHASH_NEXT(h, hoff); + } + + h %= hash->size; + hash->table[h].key = 0; + hash->table[h].val = SMHASH_CELL_UNUSED; +} + +void *BLI_smallhash_lookup(SmallHash *hash, uintptr_t key) +{ + int h, hoff=1; + void *v; + + h = ABS((int)key); + + if (hash->table == NULL) { + return NULL; + } + + while ((hash->table[h % hash->size].key != key) || + (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED)) + { + if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) { + return NULL; + } + + h = SMHASH_NEXT(h, hoff); + } + + v = hash->table[h % hash->size].val; + if (ELEM(v, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) { + return NULL; + } + + return v; +} + + +int BLI_smallhash_haskey(SmallHash *hash, uintptr_t key) +{ + int h = ABS((int)key); + int hoff =1; + + if (hash->table == NULL) { + return 0; + } + + while ((hash->table[h % hash->size].key != key) || + (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED)) + { + if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) { + return 0; + } + + h = SMHASH_NEXT(h, hoff); + } + + return !ELEM(hash->table[h % hash->size].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE); +} + +int BLI_smallhash_count(SmallHash *hash) +{ + return hash->used; +} + +void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key) +{ + while (iter->i < iter->hash->size) { + if ( (iter->hash->table[iter->i].val != SMHASH_CELL_UNUSED) && + (iter->hash->table[iter->i].val != SMHASH_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; +} + +void *BLI_smallhash_iternew(SmallHash *hash, SmallHashIter *iter, uintptr_t *key) +{ + iter->hash = hash; + iter->i = 0; + + return BLI_smallhash_iternext(iter, key); +} + +/* note, this was called _print_smhash in knifetool.c + * it may not be intended for general use - campbell */ +#if 0 +void BLI_smallhash_print(SmallHash *hash) +{ + int i, linecol=79, c=0; + + printf("{"); + for (i=0; i<hash->size; i++) { + if (hash->table[i].val == SMHASH_CELL_UNUSED) { + printf("--u-"); + } + else if (hash->table[i].val == SMHASH_CELL_FREE) { + printf("--f-"); + } + else { + printf("%2x", (unsigned int)hash->table[i].key); + } + + if (i != hash->size-1) + printf(", "); + + c += 6; + + if (c >= linecol) { + printf("\n "); + c = 0; + } + } + + fflush(stdout); +} +#endif diff --git a/source/blender/editors/mesh/knifetool.c b/source/blender/editors/mesh/knifetool.c index 848b395f696..6dd5da6511a 100755 --- a/source/blender/editors/mesh/knifetool.c +++ b/source/blender/editors/mesh/knifetool.c @@ -745,34 +745,6 @@ static void knifetool_draw(const bContext *UNUSED(C), ARegion *UNUSED(ar), void glEnable(GL_DEPTH_TEST); } -static void _print_smhash(SmallHash *hash) -{ - int i, linecol=79, c=0; - - printf("{"); - for (i=0; i<hash->size; i++) { - if (hash->table[i].val == CELL_UNUSED) { - printf("--u-"); - } else if (hash->table[i].val == CELL_FREE) { - printf("--f-"); - } else { - printf("%2x", (unsigned int)hash->table[i].key); - } - - if (i != hash->size-1) - printf(", "); - - c += 6; - - if (c >= linecol) { - printf("\n "); - c = 0; - } - } - - fflush(stdout); -} - static int kfe_vert_in_edge(KnifeEdge *e, KnifeVert *v) { return e->v1 == v || e->v2 == v; } diff --git a/source/blender/modifiers/intern/MOD_mirror.c b/source/blender/modifiers/intern/MOD_mirror.c index d93d7aecb5d..4aa17b9762e 100644 --- a/source/blender/modifiers/intern/MOD_mirror.c +++ b/source/blender/modifiers/intern/MOD_mirror.c @@ -33,6 +33,8 @@ #include "DNA_meshdata_types.h" #include "DNA_object_types.h" +#include "MEM_guardedalloc.h" + #include "BLI_math.h" #include "BLI_smallhash.h" #include "BLI_array.h" @@ -44,7 +46,6 @@ #include "BKE_utildefines.h" #include "BKE_tessmesh.h" -#include "MEM_guardedalloc.h" #include "depsgraph_private.h" static void initData(ModifierData *md) |