Blender  V3.3
Classes | Typedefs
edgehash.c File Reference
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "MEM_guardedalloc.h"
#include "BLI_edgehash.h"
#include "BLI_strict_flags.h"
#include "BLI_utildefines.h"

Go to the source code of this file.

Classes

struct  EdgeHash
 
struct  EdgeSet
 

Macros

Internal Helper Macros & Defines
#define ENTRIES_CAPACITY(container)   (uint)(1 << (container)->capacity_exp)
 
#define MAP_CAPACITY(container)   (uint)(1 << ((container)->capacity_exp + 1))
 
#define CLEAR_MAP(container)    memset((container)->map, 0xFF, sizeof(int32_t) * MAP_CAPACITY(container))
 
#define UPDATE_SLOT_MASK(container)
 
#define PERTURB_SHIFT   5
 
#define ITER_SLOTS(CONTAINER, EDGE, SLOT, INDEX)
 
#define SLOT_EMPTY   -1
 
#define SLOT_DUMMY   -2
 
#define CAPACITY_EXP_DEFAULT   3
 

Typedefs

typedef struct _EdgeHash_Edge Edge
 
typedef struct _EdgeHash_Entry EdgeHashEntry
 
typedef struct EdgeHash EdgeHash
 
typedef struct EdgeSet EdgeSet
 

Functions

Internal Edge API
BLI_INLINE uint32_t calc_edge_hash (Edge edge)
 
BLI_INLINE Edge init_edge (uint v0, uint v1)
 
BLI_INLINE bool edges_equal (Edge e1, Edge e2)
 
static uint calc_capacity_exp_for_reserve (uint reserve)
 
Edge Hash API
EdgeHashBLI_edgehash_new_ex (const char *info, const uint reserve)
 
EdgeHashBLI_edgehash_new (const char *info)
 
void BLI_edgehash_free (EdgeHash *eh, EdgeHashFreeFP free_value)
 
void BLI_edgehash_print (EdgeHash *eh)
 
void BLI_edgehash_insert (EdgeHash *eh, uint v0, uint v1, void *value)
 
bool BLI_edgehash_reinsert (EdgeHash *eh, uint v0, uint v1, void *value)
 
voidBLI_edgehash_lookup_default (const EdgeHash *eh, uint v0, uint v1, void *default_value)
 
voidBLI_edgehash_lookup (const EdgeHash *eh, uint v0, uint v1)
 
void ** BLI_edgehash_lookup_p (EdgeHash *eh, uint v0, uint v1)
 
bool BLI_edgehash_ensure_p (EdgeHash *eh, uint v0, uint v1, void ***r_value)
 
bool BLI_edgehash_remove (EdgeHash *eh, uint v0, uint v1, EdgeHashFreeFP free_value)
 
voidBLI_edgehash_popkey (EdgeHash *eh, uint v0, uint v1)
 
bool BLI_edgehash_haskey (const EdgeHash *eh, uint v0, uint v1)
 
int BLI_edgehash_len (const EdgeHash *eh)
 
void BLI_edgehash_clear_ex (EdgeHash *eh, EdgeHashFreeFP free_value, const uint UNUSED(reserve))
 
void BLI_edgehash_clear (EdgeHash *eh, EdgeHashFreeFP free_value)
 
Edge Hash Iterator API
EdgeHashIteratorBLI_edgehashIterator_new (EdgeHash *eh)
 
void BLI_edgehashIterator_init (EdgeHashIterator *ehi, EdgeHash *eh)
 
void BLI_edgehashIterator_free (EdgeHashIterator *ehi)
 

Internal Utility API

#define EH_INDEX_HAS_EDGE(eh, index, edge)    ((index) >= 0 && edges_equal((edge), (eh)->entries[index].edge))
 
static void edgehash_free_values (EdgeHash *eh, EdgeHashFreeFP free_value)
 
BLI_INLINE void edgehash_insert_index (EdgeHash *eh, Edge edge, uint entry_index)
 
BLI_INLINE EdgeHashEntryedgehash_insert_at_slot (EdgeHash *eh, uint slot, Edge edge, void *value)
 
BLI_INLINE bool edgehash_ensure_can_insert (EdgeHash *eh)
 
BLI_INLINE EdgeHashEntryedgehash_insert (EdgeHash *eh, Edge edge, void *value)
 
BLI_INLINE EdgeHashEntryedgehash_lookup_entry (const EdgeHash *eh, uint v0, uint v1)
 
BLI_INLINE void edgehash_change_index (EdgeHash *eh, Edge edge, int new_index)
 

EdgeSet API

Use edgehash API to give 'set' functionality

#define ES_INDEX_HAS_EDGE(es, index, edge)    (index) >= 0 && edges_equal((edge), (es)->entries[index])
 
EdgeSetBLI_edgeset_new_ex (const char *info, const uint reserve)
 
EdgeSetBLI_edgeset_new (const char *info)
 
void BLI_edgeset_free (EdgeSet *es)
 
int BLI_edgeset_len (const EdgeSet *es)
 
static void edgeset_insert_index (EdgeSet *es, Edge edge, uint entry_index)
 
BLI_INLINE void edgeset_ensure_can_insert (EdgeSet *es)
 
BLI_INLINE void edgeset_insert_at_slot (EdgeSet *es, uint slot, Edge edge)
 
bool BLI_edgeset_add (EdgeSet *es, uint v0, uint v1)
 
void BLI_edgeset_insert (EdgeSet *es, uint v0, uint v1)
 
bool BLI_edgeset_haskey (const EdgeSet *es, uint v0, uint v1)
 
EdgeSetIteratorBLI_edgesetIterator_new (EdgeSet *es)
 
void BLI_edgesetIterator_free (EdgeSetIterator *esi)
 

Detailed Description

An (edge -> pointer) hash table. Using unordered int-pairs as keys.

Note
The API matches BLI_ghash.c, but the implementation is different.

Definition in file edgehash.c.

Macro Definition Documentation

◆ CAPACITY_EXP_DEFAULT

#define CAPACITY_EXP_DEFAULT   3

Definition at line 70 of file edgehash.c.

◆ CLEAR_MAP

#define CLEAR_MAP (   container)     memset((container)->map, 0xFF, sizeof(int32_t) * MAP_CAPACITY(container))

Definition at line 49 of file edgehash.c.

◆ EH_INDEX_HAS_EDGE

#define EH_INDEX_HAS_EDGE (   eh,
  index,
  edge 
)     ((index) >= 0 && edges_equal((edge), (eh)->entries[index].edge))

Definition at line 120 of file edgehash.c.

◆ ENTRIES_CAPACITY

#define ENTRIES_CAPACITY (   container)    (uint)(1 << (container)->capacity_exp)

Definition at line 47 of file edgehash.c.

◆ ES_INDEX_HAS_EDGE

#define ES_INDEX_HAS_EDGE (   es,
  index,
  edge 
)     (index) >= 0 && edges_equal((edge), (es)->entries[index])

Definition at line 421 of file edgehash.c.

◆ ITER_SLOTS

#define ITER_SLOTS (   CONTAINER,
  EDGE,
  SLOT,
  INDEX 
)
Value:
uint32_t mask = (CONTAINER)->slot_mask; \
uint32_t perturb = hash; \
int32_t *map = (CONTAINER)->map; \
uint32_t SLOT = mask & hash; \
int INDEX = map[SLOT]; \
for (;; SLOT = mask & ((5 * SLOT) + 1 + perturb), perturb >>= PERTURB_SHIFT, INDEX = map[SLOT])
#define PERTURB_SHIFT
Definition: edgehash.c:56
BLI_INLINE uint32_t calc_edge_hash(Edge edge)
Definition: edgehash.c:78
#define INDEX(_x, _y)
ccl_device_inline float4 mask(const int4 &mask, const float4 &a)
Definition: math_float4.h:513
SocketIndexByIdentifierMap * map
#define hash
Definition: noise.c:153
unsigned int uint32_t
Definition: stdint.h:80

Definition at line 58 of file edgehash.c.

◆ MAP_CAPACITY

#define MAP_CAPACITY (   container)    (uint)(1 << ((container)->capacity_exp + 1))

Definition at line 48 of file edgehash.c.

◆ PERTURB_SHIFT

#define PERTURB_SHIFT   5

Definition at line 56 of file edgehash.c.

◆ SLOT_DUMMY

#define SLOT_DUMMY   -2

Definition at line 68 of file edgehash.c.

◆ SLOT_EMPTY

#define SLOT_EMPTY   -1

Definition at line 67 of file edgehash.c.

◆ UPDATE_SLOT_MASK

#define UPDATE_SLOT_MASK (   container)
Value:
{ \
(container)->slot_mask = MAP_CAPACITY(container) - 1; \
} \
((void)0)
SyclQueue void void size_t num_bytes void
#define MAP_CAPACITY(container)
Definition: edgehash.c:48

Definition at line 51 of file edgehash.c.

Typedef Documentation

◆ Edge

typedef struct _EdgeHash_Edge Edge

Definition at line 1 of file edgehash.c.

◆ EdgeHash

typedef struct EdgeHash EdgeHash

◆ EdgeHashEntry

Definition at line 1 of file edgehash.c.

◆ EdgeSet

typedef struct EdgeSet EdgeSet

Function Documentation

◆ BLI_edgehash_clear()

void BLI_edgehash_clear ( EdgeHash eh,
EdgeHashFreeFP  free_value 
)

Wraps BLI_edgehash_clear_ex with zero entries reserved.

Definition at line 383 of file edgehash.c.

References BLI_edgehash_clear_ex().

Referenced by TEST().

◆ BLI_edgehash_clear_ex()

void BLI_edgehash_clear_ex ( EdgeHash eh,
EdgeHashFreeFP  free_value,
const uint   UNUSEDreserve 
)

◆ BLI_edgehash_ensure_p()

bool BLI_edgehash_ensure_p ( EdgeHash eh,
unsigned int  v0,
unsigned int  v1,
void ***  r_val 
)

Ensure (v0, v1) is exists in eh.

This handles the common situation where the caller needs ensure a key is added to eh, constructing a new value in the case the key isn't found. Otherwise use the existing value.

Such situations typically incur multiple lookups, however this function avoids them by ensuring the key is added, returning a pointer to the value so it can be used or initialized by the caller.

Returns
true when the value didn't need to be added. (when false, the caller must initialize the value).

Definition at line 307 of file edgehash.c.

References edgehash_ensure_can_insert(), edgehash_insert(), edgehash_insert_at_slot(), EH_INDEX_HAS_EDGE, EdgeHash::entries, init_edge(), ITER_SLOTS, NULL, SLOT_EMPTY, v1, and _EdgeHash_Entry::value.

Referenced by BKE_mesh_merge_verts(), laplacian_increase_edge_count(), blender::draw::lines_adjacency_triangle(), set_edge_adjacency_lines_indices(), split_faces_prepare_new_edges(), blender::draw::statvis_calc_sharp(), and TEST().

◆ BLI_edgehash_free()

void BLI_edgehash_free ( EdgeHash eh,
EdgeHashFreeFP  free_value 
)

◆ BLI_edgehash_haskey()

bool BLI_edgehash_haskey ( const EdgeHash eh,
unsigned int  v0,
unsigned int  v1 
)

Return boolean true/false if edge (v0,v1) in hash.

Definition at line 363 of file edgehash.c.

References edgehash_lookup_entry(), NULL, and v1.

Referenced by BKE_mesh_validate_arrays(), make_edges_mdata_extend(), and TEST().

◆ BLI_edgehash_insert()

void BLI_edgehash_insert ( EdgeHash eh,
unsigned int  v0,
unsigned int  v1,
void val 
)

◆ BLI_edgehash_len()

int BLI_edgehash_len ( const EdgeHash eh)

Return number of keys in hash.

Definition at line 368 of file edgehash.c.

References EdgeHash::length.

Referenced by make_edges_mdata_extend(), TEST(), and test_polyfill_topology().

◆ BLI_edgehash_lookup()

void* BLI_edgehash_lookup ( const EdgeHash eh,
unsigned int  v0,
unsigned int  v1 
)

Return value for given edge (v0, v1), or NULL if if key does not exist in hash. (If need exists to differentiate between key-value being NULL and lack of key then see BLI_edgehash_lookup_p().

Definition at line 295 of file edgehash.c.

References edgehash_lookup_entry(), NULL, v1, and _EdgeHash_Entry::value.

Referenced by BKE_mesh_validate_arrays(), copyFinalLoopArray_task_cb(), customdata_compare(), edgecut_get(), laplacian_edge_count(), make_edges_mdata_extend(), mesh_calc_edges_mdata(), blender::io::alembic::read_edge_creases(), sph_force_cb(), and TEST().

◆ BLI_edgehash_lookup_default()

void* BLI_edgehash_lookup_default ( const EdgeHash eh,
unsigned int  v0,
unsigned int  v1,
void default_value 
)

A version of BLI_edgehash_lookup which accepts a fallback argument.

Definition at line 289 of file edgehash.c.

References edgehash_lookup_entry(), v1, and _EdgeHash_Entry::value.

Referenced by TEST().

◆ BLI_edgehash_lookup_p()

void** BLI_edgehash_lookup_p ( EdgeHash eh,
unsigned int  v0,
unsigned int  v1 
)

Return pointer to value for given edge (v0, v1), or NULL if key does not exist in hash.

Definition at line 301 of file edgehash.c.

References edgehash_lookup_entry(), NULL, v1, and _EdgeHash_Entry::value.

Referenced by TEST(), and test_polyfill_topology().

◆ BLI_edgehash_new()

EdgeHash* BLI_edgehash_new ( const char *  info)

Definition at line 225 of file edgehash.c.

References BLI_edgehash_new_ex(), and CAPACITY_EXP_DEFAULT.

Referenced by cutEdges(), explodeMesh(), TEST(), and test_polyfill_topology().

◆ BLI_edgehash_new_ex()

EdgeHash* BLI_edgehash_new_ex ( const char *  info,
const uint  reserve 
)

◆ BLI_edgehash_popkey()

void* BLI_edgehash_popkey ( EdgeHash eh,
unsigned int  v0,
unsigned int  v1 
)

Remove key (v0, v1) from eh, returning the value or NULL if the key wasn't found.

Parameters
v0,v1The key to remove.
Returns
the value of key int eh or NULL.

Definition at line 338 of file edgehash.c.

References EdgeHash::dummy_count, _EdgeHash_Entry::edge, edgehash_change_index(), EH_INDEX_HAS_EDGE, EdgeHash::entries, init_edge(), ITER_SLOTS, blender::math::length(), EdgeHash::length, EdgeHash::map, NULL, SLOT_DUMMY, SLOT_EMPTY, v1, and _EdgeHash_Entry::value.

Referenced by BLI_edgehash_remove(), and TEST().

◆ BLI_edgehash_print()

void BLI_edgehash_print ( EdgeHash eh)

◆ BLI_edgehash_reinsert()

bool BLI_edgehash_reinsert ( EdgeHash eh,
unsigned int  v0,
unsigned int  v1,
void val 
)

◆ BLI_edgehash_remove()

bool BLI_edgehash_remove ( EdgeHash eh,
unsigned int  v0,
unsigned int  v1,
EdgeHashFreeFP  free_value 
)

Remove key (v0, v1) from eh, or return false if the key wasn't found.

Parameters
v0,v1The key to remove.
free_valueOptional callback to free the value.
Returns
true if key was removed from eh.

Definition at line 328 of file edgehash.c.

References BLI_edgehash_popkey(), EdgeHash::length, and v1.

Referenced by BKE_mesh_merge_verts(), and TEST().

◆ BLI_edgehashIterator_free()

void BLI_edgehashIterator_free ( EdgeHashIterator ehi)

◆ BLI_edgehashIterator_init()

void BLI_edgehashIterator_init ( EdgeHashIterator ehi,
EdgeHash eh 
)

Initialize an already allocated EdgeHashIterator. The hash table must not be mutated while the iterator is in use, and the iterator will step exactly BLI_edgehash_len(eh) times before becoming done.

Parameters
ehiThe EdgeHashIterator to initialize.
ehThe EdgeHash to iterate over.

Definition at line 401 of file edgehash.c.

References EdgeHashIterator::entries, EdgeHash::entries, EdgeHashIterator::index, EdgeHashIterator::length, and EdgeHash::length.

Referenced by BLI_edgehashIterator_new().

◆ BLI_edgehashIterator_new()

EdgeHashIterator* BLI_edgehashIterator_new ( EdgeHash eh)

Create a new EdgeHashIterator. The hash table must not be mutated while the iterator is in use, and the iterator will step exactly #BLI_edgehash_len(eh) times before becoming done.

Definition at line 394 of file edgehash.c.

References BLI_edgehashIterator_init(), and MEM_mallocN.

Referenced by cutEdges(), DRW_displist_indexbuf_create_edges_adjacency_lines(), explodeMesh(), blender::draw::extract_lines_adjacency_finish(), make_edges_mdata_extend(), blender::draw::statvis_calc_sharp(), TEST(), and test_polyfill_topology().

◆ BLI_edgeset_add()

bool BLI_edgeset_add ( EdgeSet es,
unsigned int  v0,
unsigned int  v1 
)

A version of BLI_edgeset_insert which checks first if the key is in the set.

Returns
true if a new key has been added.
Note
EdgeHash has no equivalent to this because typically the value would be different.

Definition at line 484 of file edgehash.c.

References edgeset_ensure_can_insert(), edgeset_insert_at_slot(), ES_INDEX_HAS_EDGE, init_edge(), ITER_SLOTS, SLOT_EMPTY, and v1.

Referenced by BKE_mesh_calc_edges_tessface(), cloth_brush_add_length_constraint(), cloth_build_springs(), ss_sync_from_uv(), and TEST().

◆ BLI_edgeset_free()

void BLI_edgeset_free ( EdgeSet es)

◆ BLI_edgeset_haskey()

bool BLI_edgeset_haskey ( const EdgeSet es,
uint  v0,
uint  v1 
)

◆ BLI_edgeset_insert()

void BLI_edgeset_insert ( EdgeSet es,
unsigned int  v0,
unsigned int  v1 
)

Adds the key to the set (no checks for unique keys!). Matching BLI_edgehash_insert

Definition at line 500 of file edgehash.c.

References edgeset_ensure_can_insert(), edgeset_insert_at_slot(), init_edge(), ITER_SLOTS, SLOT_EMPTY, and v1.

Referenced by cloth_build_springs(), and TEST().

◆ BLI_edgeset_len()

int BLI_edgeset_len ( const EdgeSet es)

Definition at line 448 of file edgehash.c.

References EdgeSet::length.

Referenced by BKE_mesh_calc_edges_tessface(), and TEST().

◆ BLI_edgeset_new()

EdgeSet* BLI_edgeset_new ( const char *  info)

◆ BLI_edgeset_new_ex()

EdgeSet* BLI_edgeset_new_ex ( const char *  info,
const uint  reserve 
)

◆ BLI_edgesetIterator_free()

void BLI_edgesetIterator_free ( EdgeSetIterator esi)

Definition at line 536 of file edgehash.c.

References MEM_freeN.

Referenced by BKE_mesh_calc_edges_tessface().

◆ BLI_edgesetIterator_new()

EdgeSetIterator* BLI_edgesetIterator_new ( EdgeSet es)

◆ calc_capacity_exp_for_reserve()

static uint calc_capacity_exp_for_reserve ( uint  reserve)
static

Definition at line 105 of file edgehash.c.

References result.

Referenced by BLI_edgehash_new_ex(), and BLI_edgeset_new_ex().

◆ calc_edge_hash()

BLI_INLINE uint32_t calc_edge_hash ( Edge  edge)

Definition at line 78 of file edgehash.c.

◆ edgehash_change_index()

BLI_INLINE void edgehash_change_index ( EdgeHash eh,
Edge  edge,
int  new_index 
)

Definition at line 196 of file edgehash.c.

References EH_INDEX_HAS_EDGE, ITER_SLOTS, and EdgeHash::map.

Referenced by BLI_edgehash_popkey().

◆ edgehash_ensure_can_insert()

BLI_INLINE bool edgehash_ensure_can_insert ( EdgeHash eh)

◆ edgehash_free_values()

static void edgehash_free_values ( EdgeHash eh,
EdgeHashFreeFP  free_value 
)
static

Definition at line 123 of file edgehash.c.

References EdgeHash::entries, EdgeHash::length, and _EdgeHash_Entry::value.

Referenced by BLI_edgehash_clear_ex(), and BLI_edgehash_free().

◆ edgehash_insert()

BLI_INLINE EdgeHashEntry* edgehash_insert ( EdgeHash eh,
Edge  edge,
void value 
)

◆ edgehash_insert_at_slot()

BLI_INLINE EdgeHashEntry* edgehash_insert_at_slot ( EdgeHash eh,
uint  slot,
Edge  edge,
void value 
)

◆ edgehash_insert_index()

BLI_INLINE void edgehash_insert_index ( EdgeHash eh,
Edge  edge,
uint  entry_index 
)

Definition at line 132 of file edgehash.c.

References ITER_SLOTS, EdgeHash::map, and SLOT_EMPTY.

Referenced by edgehash_ensure_can_insert().

◆ edgehash_lookup_entry()

BLI_INLINE EdgeHashEntry* edgehash_lookup_entry ( const EdgeHash eh,
uint  v0,
uint  v1 
)

◆ edges_equal()

BLI_INLINE bool edges_equal ( Edge  e1,
Edge  e2 
)

Definition at line 100 of file edgehash.c.

◆ edgeset_ensure_can_insert()

BLI_INLINE void edgeset_ensure_can_insert ( EdgeSet es)

◆ edgeset_insert_at_slot()

BLI_INLINE void edgeset_insert_at_slot ( EdgeSet es,
uint  slot,
Edge  edge 
)

Definition at line 477 of file edgehash.c.

References EdgeSet::entries, EdgeSet::length, and EdgeSet::map.

Referenced by BLI_edgeset_add(), and BLI_edgeset_insert().

◆ edgeset_insert_index()

static void edgeset_insert_index ( EdgeSet es,
Edge  edge,
uint  entry_index 
)
static

Definition at line 453 of file edgehash.c.

References ITER_SLOTS, EdgeSet::map, and SLOT_EMPTY.

Referenced by edgeset_ensure_can_insert().

◆ init_edge()

BLI_INLINE Edge init_edge ( uint  v0,
uint  v1 
)