Blender  V3.3
Macros | Functions | Variables
smallhash.c File Reference
#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"

Go to the source code of this file.

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 SmallHashEntrysmallhash_lookup (const SmallHash *sh, const uintptr_t key)
 
BLI_INLINE SmallHashEntrysmallhash_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)
 
voidBLI_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 SmallHashEntrysmallhash_iternext (SmallHashIter *iter, uintptr_t *key)
 
voidBLI_smallhash_iternext (SmallHashIter *iter, uintptr_t *key)
 
void ** BLI_smallhash_iternext_p (SmallHashIter *iter, uintptr_t *key)
 
voidBLI_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

SmallHashEntry.val

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 67 of file smallhash.c.

◆ SMHASH_CELL_FREE

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

Definition at line 45 of file smallhash.c.

◆ SMHASH_CELL_UNUSED

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

Definition at line 46 of file smallhash.c.

◆ SMHASH_KEY_UNUSED

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

Definition at line 44 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))))
#define CHECK_TYPE_INLINE(val, type)
unsigned int uint
Definition: BLI_sys_types.h:67

Definition at line 49 of file smallhash.c.

Function Documentation

◆ BLI_smallhash_haskey()

bool BLI_smallhash_haskey ( const SmallHash sh,
uintptr_t  key 
)

Definition at line 269 of file smallhash.c.

References e, NULL, sh, 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 196 of file smallhash.c.

References BLI_smallhash_init_ex(), and sh.

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 
)

◆ BLI_smallhash_insert()

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

◆ BLI_smallhash_iternew()

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

Definition at line 312 of file smallhash.c.

References BLI_smallhash_iternext(), SmallHashIter::i, sh, 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 320 of file smallhash.c.

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

Referenced by knife_find_line_hits().

◆ BLI_smallhash_iternext()

void* BLI_smallhash_iternext ( SmallHashIter iter,
uintptr_t key 
)

Definition at line 298 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 305 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 276 of file smallhash.c.

References sh.

◆ BLI_smallhash_lookup()

void* BLI_smallhash_lookup ( const SmallHash sh,
uintptr_t  key 
)

Definition at line 255 of file smallhash.c.

References e, NULL, sh, 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 262 of file smallhash.c.

References e, NULL, sh, 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 225 of file smallhash.c.

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

Referenced by knife_find_line_hits().

◆ BLI_smallhash_release()

void BLI_smallhash_release ( SmallHash sh)
Note
does not free *sh itself! only the direct data!

Definition at line 201 of file smallhash.c.

References MEM_freeN, and sh.

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 96 of file smallhash.c.

References hashsizes, sh, 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 83 of file smallhash.c.

References sh, SMHASH_CELL_FREE, and SMHASH_KEY_UNUSED.

Referenced by BLI_smallhash_init_ex(), and smallhash_resize_buckets().

◆ smallhash_iternext()

BLI_INLINE SmallHashEntry* smallhash_iternext ( SmallHashIter iter,
uintptr_t key 
)

◆ smallhash_key()

BLI_INLINE uint smallhash_key ( const uintptr_t  key)

Definition at line 69 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 
)

◆ smallhash_lookup_first_free()

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

Definition at line 125 of file smallhash.c.

References e, sh, 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 
)

◆ 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 77 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)

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 40 of file BLI_ghash.c.