diff options
Diffstat (limited to 'source/blender/blenlib/BLI_smallhash.h')
-rwxr-xr-x | source/blender/blenlib/BLI_smallhash.h | 204 |
1 files changed, 204 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_smallhash.h b/source/blender/blenlib/BLI_smallhash.h new file mode 100755 index 00000000000..5badff062b7 --- /dev/null +++ b/source/blender/blenlib/BLI_smallhash.h @@ -0,0 +1,204 @@ +/** + * ***** 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 "BKE_utildefines.h" + +extern unsigned int hashsizes[]; +#define NONHASH -25436536 +typedef struct entry {intptr_t key; void *val;} entry; + +#define SMSTACKSIZE 521 +typedef struct SmallHash { + entry *table, _stacktable[SMSTACKSIZE], _copytable[SMSTACKSIZE]; + entry *stacktable, *copytable; + int used; + int curhash; + int size; +} SmallHash; + +/*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*)0x7FFFFFFD) +#define CELL_FREE ((void*)0x7FFFFFFD) + +#define HASHNEXT(h) (((h) + ((h)==0))*2) + +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, intptr_t key, void *item) +{ + int h; + + 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; + while (!ELEM(hash->table[h % newsize].val, CELL_UNUSED, CELL_FREE)) + h = HASHNEXT(h); + + 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; + while (!ELEM(hash->table[h % hash->size].val, CELL_UNUSED, CELL_FREE)) + h = HASHNEXT(h); + + h %= hash->size; + hash->table[h].key = key; + hash->table[h].val = item; + + hash->used++; +} + +BM_INLINE void BLI_smallhash_remove(SmallHash *hash, intptr_t key) +{ + int 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); + } + + h %= hash->size; + hash->table[h].key = 0; + hash->table[h].val = CELL_UNUSED; +} + +BM_INLINE void *BLI_smallhash_lookup(SmallHash *hash, intptr_t key) +{ + int 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); + } + + return hash->table[h % hash->size].val; +} + + +BM_INLINE int BLI_smallhash_haskey(SmallHash *hash, intptr_t key) +{ + int h = 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); + } + + return 1; +} + +BM_INLINE int BLI_smallhash_count(SmallHash *hash) +{ + return hash->used; +} + +#endif // BLI_SMALLHASH_H |