diff options
Diffstat (limited to 'source/blender/blenlib/intern/smallhash.c')
| -rw-r--r-- | source/blender/blenlib/intern/smallhash.c | 17 |
1 files changed, 11 insertions, 6 deletions
diff --git a/source/blender/blenlib/intern/smallhash.c b/source/blender/blenlib/intern/smallhash.c index ba336ab6c4b..0b976e9612e 100644 --- a/source/blender/blenlib/intern/smallhash.c +++ b/source/blender/blenlib/intern/smallhash.c @@ -28,12 +28,16 @@ /** \file blender/blenlib/intern/smallhash.c * \ingroup bli * - * A light stack-friendly hash library, it uses stack space for smallish hash tables - * but falls back to heap memory once the stack limits reached. + * A light stack-friendly hash library, it uses stack space for relatively small, fixed size hash tables + * but falls back to heap memory once the stack limits reached (#SMSTACKSIZE). * - * based on a doubling non-chaining approach which uses more buckets then entries + * based on a doubling hashing approach (non-chaining) which uses more buckets then entries * stepping over buckets when two keys share the same hash so any key can find a free bucket. * + * See: http://en.wikipedia.org/wiki/Double_hashing + * + * \warning This should _only_ be used for small hashes where allocating a hash every time is unacceptable. + * Otherwise #GHash should be used instead. * * #SmallHashEntry.key * - ``SMHASH_KEY_UNUSED`` means the key in the cell has not been initialized. @@ -48,7 +52,8 @@ #include <string.h> #include <stdlib.h> -#include <BLI_sys_types.h> + +#include "BLI_sys_types.h" #include "MEM_guardedalloc.h" @@ -126,7 +131,7 @@ BLI_INLINE SmallHashEntry *smallhash_lookup(const SmallHash *sh, const uintptr_t BLI_assert(key != SMHASH_KEY_UNUSED); - /* note: there are always more buckets then entries, + /* note: there are always more buckets than entries, * so we know there will always be a free bucket if the key isn't found. */ for (e = &sh->buckets[h % sh->nbuckets]; e->val != SMHASH_CELL_FREE; @@ -221,7 +226,7 @@ void BLI_smallhash_init(SmallHash *sh) BLI_smallhash_init_ex(sh, 0); } -/*NOTE: does *not* free *sh itself! only the direct data!*/ +/* NOTE: does *not* free *sh itself! only the direct data! */ void BLI_smallhash_release(SmallHash *sh) { if (sh->buckets != sh->buckets_stack) { |