#include <stdlib.h>
#include <string.h>
#include "BLI_sys_types.h"
#include "MEM_guardedalloc.h"
#include "BLI_utildefines.h"
#include "BLI_smallhash.h"
#include "BLI_strict_flags.h"

Macros
#define	SMHASH_KEY_UNUSED ((uintptr_t)(UINTPTR_MAX - 0))

#define	SMHASH_CELL_FREE ((void *)(UINTPTR_MAX - 1))

#define	SMHASH_CELL_UNUSED ((void *)(UINTPTR_MAX - 2))

#define	SMHASH_NEXT(h, hoff)

#define	hashsizes BLI_ghash_hash_sizes

Functions
BLI_INLINE bool	smallhash_val_is_used (const void *val)

BLI_INLINE uint	smallhash_key (const uintptr_t key)

BLI_INLINE bool	smallhash_test_expand_buckets (const uint nentries, const uint nbuckets)

BLI_INLINE void	smallhash_init_empty (SmallHash *sh)

BLI_INLINE void	smallhash_buckets_reserve (SmallHash *sh, const uint nentries_reserve)

BLI_INLINE SmallHashEntry *	smallhash_lookup (const SmallHash *sh, const uintptr_t key)

BLI_INLINE SmallHashEntry *	smallhash_lookup_first_free (SmallHash *sh, const uintptr_t key)

BLI_INLINE void	smallhash_resize_buckets (SmallHash *sh, const uint nbuckets)

void	BLI_smallhash_init_ex (SmallHash *sh, const uint nentries_reserve)

void	BLI_smallhash_init (SmallHash *sh)

void	BLI_smallhash_release (SmallHash *sh)

void	BLI_smallhash_insert (SmallHash sh, uintptr_t key, void item)

bool	BLI_smallhash_reinsert (SmallHash sh, uintptr_t key, void item)

void *	BLI_smallhash_lookup (const SmallHash *sh, uintptr_t key)

void **	BLI_smallhash_lookup_p (const SmallHash *sh, uintptr_t key)

bool	BLI_smallhash_haskey (const SmallHash *sh, uintptr_t key)

int	BLI_smallhash_len (const SmallHash *sh)

BLI_INLINE SmallHashEntry *	smallhash_iternext (SmallHashIter iter, uintptr_t key)

void *	BLI_smallhash_iternext (SmallHashIter iter, uintptr_t key)

void **	BLI_smallhash_iternext_p (SmallHashIter iter, uintptr_t key)

void *	BLI_smallhash_iternew (const SmallHash sh, SmallHashIter iter, uintptr_t *key)

void **	BLI_smallhash_iternew_p (const SmallHash sh, SmallHashIter iter, uintptr_t *key)

Variables
const uint	BLI_ghash_hash_sizes []

Detailed Description

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 hashing approach (non-chaining) which uses more buckets than entries stepping over buckets when two keys share the same hash so any key can find a free bucket.

See: https://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.

SmallHashEntry.val

SMHASH_CELL_UNUSED means this cell is inside a key series.
SMHASH_CELL_FREE means this cell terminates a key series.

Note that the values and keys are often pointers or index values, use the maximum values to avoid real pointers colliding with magic numbers.

Definition in file smallhash.c.

Macro Definition Documentation

◆ hashsizes

#define hashsizes BLI_ghash_hash_sizes

Definition at line 83 of file smallhash.c.

◆ SMHASH_CELL_FREE

#define SMHASH_CELL_FREE ((void *)(UINTPTR_MAX - 1))

Definition at line 61 of file smallhash.c.

◆ SMHASH_CELL_UNUSED

#define SMHASH_CELL_UNUSED ((void *)(UINTPTR_MAX - 2))

Definition at line 62 of file smallhash.c.

◆ SMHASH_KEY_UNUSED

#define SMHASH_KEY_UNUSED ((uintptr_t)(UINTPTR_MAX - 0))

Definition at line 60 of file smallhash.c.

◆ SMHASH_NEXT

#define SMHASH_NEXT	(	h,
		hoff
	)

Value:

  (CHECK_TYPE_INLINE(&(h), uint *), \
   CHECK_TYPE_INLINE(&(hoff), uint *), \
   ((h) + (((hoff) = ((hoff)*2) + 1), (hoff))))

Definition at line 65 of file smallhash.c.

Function Documentation

◆ BLI_smallhash_haskey()

bool BLI_smallhash_haskey	(	const SmallHash *	sh,
		uintptr_t	key
	)

Definition at line 293 of file smallhash.c.

References e, NULL, and smallhash_lookup().

Referenced by BLI_smallhash_insert(), and knife_find_line_hits().

◆ BLI_smallhash_init()

void BLI_smallhash_init ( SmallHash * sh )

Definition at line 212 of file smallhash.c.

References BLI_smallhash_init_ex().

Referenced by knife_find_line_hits(), and knife_make_cuts().

◆ BLI_smallhash_init_ex()

void BLI_smallhash_init_ex	(	SmallHash *	sh,
		const uint	nentries_reserve
	)

Definition at line 191 of file smallhash.c.

References SmallHash::buckets, SmallHash::buckets_stack, SmallHash::cursize, hashsizes, MEM_mallocN, SmallHash::nbuckets, SmallHash::nentries, smallhash_buckets_reserve(), smallhash_init_empty(), and SMSTACKSIZE.

Referenced by BLI_smallhash_init().

◆ BLI_smallhash_insert()

void BLI_smallhash_insert	(	SmallHash *	sh,
		uintptr_t	key,
		void *	item
	)

Definition at line 225 of file smallhash.c.

References BLI_assert, BLI_smallhash_haskey(), SmallHash::cursize, e, hashsizes, SmallHash::nbuckets, SmallHash::nentries, smallhash_lookup_first_free(), smallhash_resize_buckets(), smallhash_test_expand_buckets(), smallhash_val_is_used(), SMHASH_KEY_UNUSED, and UNLIKELY.

Referenced by BLI_smallhash_reinsert(), knife_find_line_hits(), and knife_make_cuts().

◆ BLI_smallhash_iternew()

void* BLI_smallhash_iternew	(	const SmallHash *	sh,
		SmallHashIter *	iter,
		uintptr_t *	key
	)

Definition at line 336 of file smallhash.c.

References BLI_smallhash_iternext(), SmallHashIter::i, and SmallHashIter::sh.

Referenced by knife_find_line_hits(), and knife_make_cuts().

◆ BLI_smallhash_iternew_p()

void** BLI_smallhash_iternew_p	(	const SmallHash *	sh,
		SmallHashIter *	iter,
		uintptr_t *	key
	)

Definition at line 344 of file smallhash.c.

References BLI_smallhash_iternext_p(), SmallHashIter::i, and SmallHashIter::sh.

Referenced by knife_find_line_hits().

◆ BLI_smallhash_iternext()

void* BLI_smallhash_iternext	(	SmallHashIter *	iter,
		uintptr_t *	key
	)

Definition at line 322 of file smallhash.c.

References e, NULL, and smallhash_iternext().

Referenced by BLI_smallhash_iternew(), knife_find_line_hits(), and knife_make_cuts().

◆ BLI_smallhash_iternext_p()

void** BLI_smallhash_iternext_p	(	SmallHashIter *	iter,
		uintptr_t *	key
	)

Definition at line 329 of file smallhash.c.

References e, NULL, and smallhash_iternext().

Referenced by BLI_smallhash_iternew_p(), and knife_find_line_hits().

◆ BLI_smallhash_len()

int BLI_smallhash_len ( const SmallHash * sh )

Definition at line 300 of file smallhash.c.

References SmallHash::nentries.

◆ BLI_smallhash_lookup()

void* BLI_smallhash_lookup	(	const SmallHash *	sh,
		uintptr_t	key
	)

Definition at line 279 of file smallhash.c.

References e, NULL, and smallhash_lookup().

Referenced by knife_find_line_hits(), and knife_make_cuts().

◆ BLI_smallhash_lookup_p()

void** BLI_smallhash_lookup_p	(	const SmallHash *	sh,
		uintptr_t	key
	)

Definition at line 286 of file smallhash.c.

References e, NULL, and smallhash_lookup().

◆ BLI_smallhash_reinsert()

bool BLI_smallhash_reinsert	(	SmallHash *	sh,
		uintptr_t	key,
		void *	item
	)

Inserts a new value to a key that may already be in ghash.

Avoids BLI_smallhash_remove, BLI_smallhash_insert calls (double lookups)

Returns: true if a new key has been added.

Definition at line 249 of file smallhash.c.

References BLI_smallhash_insert(), e, and smallhash_lookup().

Referenced by knife_find_line_hits().

◆ BLI_smallhash_release()

void BLI_smallhash_release ( SmallHash * sh )

Definition at line 218 of file smallhash.c.

References SmallHash::buckets, SmallHash::buckets_stack, and MEM_freeN.

Referenced by knife_find_line_hits(), and knife_make_cuts().

◆ smallhash_buckets_reserve()

BLI_INLINE void smallhash_buckets_reserve	(	SmallHash *	sh,
		const uint	nentries_reserve
	)

Increase initial bucket size to match a reserved amount.

Definition at line 112 of file smallhash.c.

References SmallHash::cursize, hashsizes, SmallHash::nbuckets, and smallhash_test_expand_buckets().

Referenced by BLI_smallhash_init_ex().

◆ smallhash_init_empty()

BLI_INLINE void smallhash_init_empty ( SmallHash * sh )

Definition at line 99 of file smallhash.c.

References SmallHash::buckets, SmallHashEntry::key, SmallHash::nbuckets, SMHASH_CELL_FREE, SMHASH_KEY_UNUSED, and SmallHashEntry::val.

Referenced by BLI_smallhash_init_ex(), and smallhash_resize_buckets().

◆ smallhash_iternext()

BLI_INLINE SmallHashEntry* smallhash_iternext	(	SmallHashIter *	iter,
		uintptr_t *	key
	)

Definition at line 305 of file smallhash.c.

References SmallHash::buckets, SmallHashIter::i, SmallHashEntry::key, SmallHash::nbuckets, NULL, SmallHashIter::sh, smallhash_val_is_used(), and SmallHashEntry::val.

Referenced by BLI_smallhash_iternext(), and BLI_smallhash_iternext_p().

◆ smallhash_key()

BLI_INLINE uint smallhash_key ( const uintptr_t key )

Definition at line 85 of file smallhash.c.

Referenced by smallhash_lookup(), and smallhash_lookup_first_free().

◆ smallhash_lookup()

BLI_INLINE SmallHashEntry* smallhash_lookup	(	const SmallHash *	sh,
		const uintptr_t	key
	)

Definition at line 119 of file smallhash.c.

References BLI_assert, SmallHash::buckets, e, SmallHash::nbuckets, NULL, smallhash_key(), SMHASH_CELL_FREE, SMHASH_CELL_UNUSED, SMHASH_KEY_UNUSED, and SMHASH_NEXT.

Referenced by BLI_smallhash_haskey(), BLI_smallhash_lookup(), BLI_smallhash_lookup_p(), and BLI_smallhash_reinsert().

◆ smallhash_lookup_first_free()

BLI_INLINE SmallHashEntry* smallhash_lookup_first_free	(	SmallHash *	sh,
		const uintptr_t	key
	)

Definition at line 141 of file smallhash.c.

References SmallHash::buckets, e, SmallHash::nbuckets, smallhash_key(), smallhash_val_is_used(), and SMHASH_NEXT.

Referenced by BLI_smallhash_insert(), and smallhash_resize_buckets().

◆ smallhash_resize_buckets()

BLI_INLINE void smallhash_resize_buckets	(	SmallHash *	sh,
		const uint	nbuckets
	)

Definition at line 155 of file smallhash.c.

References BLI_assert, SmallHash::buckets, SmallHash::buckets_stack, e, SmallHashEntry::key, MEM_freeN, MEM_mallocN, SmallHash::nbuckets, size(), smallhash_init_empty(), smallhash_lookup_first_free(), smallhash_val_is_used(), SMSTACKSIZE, and SmallHashEntry::val.

Referenced by BLI_smallhash_insert().

◆ smallhash_test_expand_buckets()

BLI_INLINE bool smallhash_test_expand_buckets	(	const uint	nentries,
		const uint	nbuckets
	)

Check if the number of items in the smallhash is large enough to require more buckets.

Definition at line 93 of file smallhash.c.

Referenced by BLI_smallhash_insert(), and smallhash_buckets_reserve().

◆ smallhash_val_is_used()

BLI_INLINE bool smallhash_val_is_used ( const void * val )

Definition at line 73 of file smallhash.c.

References ELEM, SMHASH_CELL_FREE, and SMHASH_CELL_UNUSED.

Referenced by BLI_smallhash_insert(), smallhash_iternext(), smallhash_lookup_first_free(), and smallhash_resize_buckets().

Variable Documentation

◆ BLI_ghash_hash_sizes

const uint BLI_ghash_hash_sizes[]

extern

Next prime after 2^n (skipping 2 & 3).

Note: Also used by: BLI_edgehash & BLI_smallhash.

Definition at line 56 of file BLI_ghash.c.

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ hashsizes

◆ SMHASH_CELL_FREE

◆ SMHASH_CELL_UNUSED

◆ SMHASH_KEY_UNUSED

◆ SMHASH_NEXT

Function Documentation

◆ BLI_smallhash_haskey()

◆ BLI_smallhash_init()

◆ BLI_smallhash_init_ex()

◆ BLI_smallhash_insert()

◆ BLI_smallhash_iternew()

◆ BLI_smallhash_iternew_p()

◆ BLI_smallhash_iternext()

◆ BLI_smallhash_iternext_p()

◆ BLI_smallhash_len()

◆ BLI_smallhash_lookup()

◆ BLI_smallhash_lookup_p()

◆ BLI_smallhash_reinsert()

◆ BLI_smallhash_release()

◆ smallhash_buckets_reserve()

◆ smallhash_init_empty()

◆ smallhash_iternext()

◆ smallhash_key()

◆ smallhash_lookup()

◆ smallhash_lookup_first_free()

◆ smallhash_resize_buckets()

◆ smallhash_test_expand_buckets()

◆ smallhash_val_is_used()

Variable Documentation

◆ BLI_ghash_hash_sizes