Blender
V3.3
|
#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 |
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 EdgeHashEntry * | edgehash_insert_at_slot (EdgeHash *eh, uint slot, Edge edge, void *value) |
BLI_INLINE bool | edgehash_ensure_can_insert (EdgeHash *eh) |
BLI_INLINE EdgeHashEntry * | edgehash_insert (EdgeHash *eh, Edge edge, void *value) |
BLI_INLINE EdgeHashEntry * | edgehash_lookup_entry (const EdgeHash *eh, uint v0, uint v1) |
BLI_INLINE void | edgehash_change_index (EdgeHash *eh, Edge edge, int new_index) |
EdgeSet API | |
#define | ES_INDEX_HAS_EDGE(es, index, edge) (index) >= 0 && edges_equal((edge), (es)->entries[index]) |
EdgeSet * | BLI_edgeset_new_ex (const char *info, const uint reserve) |
EdgeSet * | BLI_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) |
EdgeSetIterator * | BLI_edgesetIterator_new (EdgeSet *es) |
void | BLI_edgesetIterator_free (EdgeSetIterator *esi) |
An (edge -> pointer) hash table. Using unordered int-pairs as keys.
Definition in file edgehash.c.
#define CAPACITY_EXP_DEFAULT 3 |
Definition at line 70 of file edgehash.c.
#define CLEAR_MAP | ( | container | ) | memset((container)->map, 0xFF, sizeof(int32_t) * MAP_CAPACITY(container)) |
Definition at line 49 of file edgehash.c.
#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.
Definition at line 47 of file edgehash.c.
#define ES_INDEX_HAS_EDGE | ( | es, | |
index, | |||
edge | |||
) | (index) >= 0 && edges_equal((edge), (es)->entries[index]) |
Definition at line 421 of file edgehash.c.
Definition at line 58 of file edgehash.c.
Definition at line 48 of file edgehash.c.
#define PERTURB_SHIFT 5 |
Definition at line 56 of file edgehash.c.
#define SLOT_DUMMY -2 |
Definition at line 68 of file edgehash.c.
#define SLOT_EMPTY -1 |
Definition at line 67 of file edgehash.c.
#define UPDATE_SLOT_MASK | ( | container | ) |
Definition at line 51 of file edgehash.c.
typedef struct _EdgeHash_Edge Edge |
Definition at line 1 of file edgehash.c.
typedef struct _EdgeHash_Entry EdgeHashEntry |
Definition at line 1 of file edgehash.c.
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().
void BLI_edgehash_clear_ex | ( | EdgeHash * | eh, |
EdgeHashFreeFP | free_value, | ||
const uint | UNUSEDreserve | ||
) |
Definition at line 373 of file edgehash.c.
References EdgeHash::capacity_exp, CAPACITY_EXP_DEFAULT, CLEAR_MAP, EdgeHash::dummy_count, edgehash_free_values(), and EdgeHash::length.
Referenced by BLI_edgehash_clear().
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.
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().
void BLI_edgehash_free | ( | EdgeHash * | eh, |
EdgeHashFreeFP | free_value | ||
) |
Definition at line 230 of file edgehash.c.
References edgehash_free_values(), EdgeHash::entries, EdgeHash::map, and MEM_freeN.
Referenced by BKE_mesh_validate_arrays(), ccgDM_release(), convert_mfaces_to_mpolys(), customdata_compare(), cutEdges(), DRW_displist_indexbuf_create_edges_adjacency_lines(), explodeMesh(), blender::draw::extract_lines_adjacency_finish(), laplacian_system_construct_end(), make_edges_mdata_extend(), mesh_calc_edges_mdata(), psys_sph_finalize(), blender::io::alembic::read_edge_creases(), split_faces_prepare_new_edges(), blender::draw::statvis_calc_sharp(), TEST(), and test_polyfill_topology().
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().
Insert edge (v0, v1) into hash with given value, does not check for duplicates.
Definition at line 261 of file edgehash.c.
References edgehash_ensure_can_insert(), edgehash_insert(), init_edge(), and v1.
Referenced by BKE_mesh_validate_arrays(), ccgDM_copyFinalLoopArray(), convert_mfaces_to_mpolys(), customdata_compare(), mesh_calc_edges_mdata(), blender::io::alembic::read_edge_creases(), sph_springhash_build(), TEST(), and test_polyfill_topology().
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().
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().
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().
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().
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().
Definition at line 212 of file edgehash.c.
References calc_capacity_exp_for_reserve(), EdgeHash::capacity_exp, CLEAR_MAP, EdgeHash::dummy_count, EdgeHash::entries, ENTRIES_CAPACITY, EdgeHash::length, EdgeHash::map, MAP_CAPACITY, MEM_calloc_arrayN, MEM_malloc_arrayN, MEM_mallocN, and UPDATE_SLOT_MASK.
Referenced by BKE_mesh_merge_verts(), BKE_mesh_validate_arrays(), BLI_edgehash_new(), ccgDM_copyFinalLoopArray(), convert_mfaces_to_mpolys(), customdata_compare(), DRW_displist_indexbuf_create_edges_adjacency_lines(), laplacian_system_construct_end(), blender::draw::line_adjacency_data_init(), make_edges_mdata_extend(), mesh_calc_edges_mdata(), blender::io::alembic::read_edge_creases(), sph_springhash_build(), split_faces_prepare_new_edges(), and blender::draw::statvis_calc_sharp().
Remove key (v0, v1) from eh, returning the value or NULL if the key wasn't found.
v0,v1 | The key to remove. |
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().
Definition at line 238 of file edgehash.c.
References _EdgeHash_Entry::edge, EdgeHash::entries, ENTRIES_CAPACITY, EdgeHash::length, EdgeHash::map, MAP_CAPACITY, _EdgeHash_Edge::v_high, _EdgeHash_Edge::v_low, and _EdgeHash_Entry::value.
Assign a new value to a key that may already be in edgehash.
Definition at line 268 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, SLOT_EMPTY, v1, and _EdgeHash_Entry::value.
Referenced by BKE_mesh_poly_edgehash_insert(), cutEdges(), explodeMesh(), and TEST().
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.
v0,v1 | The key to remove. |
free_value | Optional callback to free the value. |
Definition at line 328 of file edgehash.c.
References BLI_edgehash_popkey(), EdgeHash::length, and v1.
Referenced by BKE_mesh_merge_verts(), and TEST().
void BLI_edgehashIterator_free | ( | EdgeHashIterator * | ehi | ) |
Free an EdgeHashIterator.
Definition at line 408 of file edgehash.c.
References MEM_freeN.
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().
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.
ehi | The EdgeHashIterator to initialize. |
eh | The 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().
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().
A version of BLI_edgeset_insert which checks first if the key is in the set.
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().
Definition at line 441 of file edgehash.c.
References EdgeSet::entries, EdgeSet::map, and MEM_freeN.
Referenced by BKE_mesh_calc_edges_tessface(), cloth_build_springs(), cloth_free_errorsprings(), cloth_free_modifier(), cloth_free_modifier_extern(), SCULPT_cloth_brush_ensure_nodes_constraints(), ss_sync_from_uv(), and TEST().
Definition at line 513 of file edgehash.c.
References ES_INDEX_HAS_EDGE, init_edge(), ITER_SLOTS, SLOT_EMPTY, and v1.
Referenced by cloth_brush_sim_has_length_constraint(), cloth_build_springs(), cloth_bvh_selfcollision_is_active(), and TEST().
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().
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().
EdgeSet* BLI_edgeset_new | ( | const char * | info | ) |
Definition at line 436 of file edgehash.c.
References BLI_edgeset_new_ex(), and CAPACITY_EXP_DEFAULT.
Referenced by cloth_build_springs(), SCULPT_cloth_brush_ensure_nodes_constraints(), and TEST().
Definition at line 424 of file edgehash.c.
References calc_capacity_exp_for_reserve(), EdgeSet::capacity_exp, CLEAR_MAP, EdgeSet::entries, ENTRIES_CAPACITY, EdgeSet::length, EdgeSet::map, MAP_CAPACITY, MEM_malloc_arrayN, MEM_mallocN, and UPDATE_SLOT_MASK.
Referenced by BKE_mesh_calc_edges_tessface(), BLI_edgeset_new(), cloth_build_springs(), and ss_sync_from_uv().
void BLI_edgesetIterator_free | ( | EdgeSetIterator * | esi | ) |
Definition at line 536 of file edgehash.c.
References MEM_freeN.
Referenced by BKE_mesh_calc_edges_tessface().
EdgeSetIterator* BLI_edgesetIterator_new | ( | EdgeSet * | es | ) |
Definition at line 527 of file edgehash.c.
References EdgeSetIterator::edges, EdgeSet::entries, EdgeSetIterator::index, EdgeSetIterator::length, EdgeSet::length, and MEM_mallocN.
Referenced by BKE_mesh_calc_edges_tessface().
Definition at line 105 of file edgehash.c.
References result.
Referenced by BLI_edgehash_new_ex(), and BLI_edgeset_new_ex().
BLI_INLINE uint32_t calc_edge_hash | ( | Edge | edge | ) |
Definition at line 78 of file edgehash.c.
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().
BLI_INLINE bool edgehash_ensure_can_insert | ( | EdgeHash * | eh | ) |
Definition at line 152 of file edgehash.c.
References EdgeHash::capacity_exp, CLEAR_MAP, EdgeHash::dummy_count, _EdgeHash_Entry::edge, edgehash_insert_index(), EdgeHash::entries, ENTRIES_CAPACITY, EdgeHash::length, EdgeHash::map, MAP_CAPACITY, MEM_reallocN, UNLIKELY, and UPDATE_SLOT_MASK.
Referenced by BLI_edgehash_ensure_p(), BLI_edgehash_insert(), and BLI_edgehash_reinsert().
|
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().
BLI_INLINE EdgeHashEntry* edgehash_insert | ( | EdgeHash * | eh, |
Edge | edge, | ||
void * | value | ||
) |
Definition at line 169 of file edgehash.c.
References EdgeHash::dummy_count, edgehash_insert_at_slot(), ITER_SLOTS, SLOT_DUMMY, and SLOT_EMPTY.
Referenced by BLI_edgehash_ensure_p(), BLI_edgehash_insert(), and BLI_edgehash_reinsert().
BLI_INLINE EdgeHashEntry* edgehash_insert_at_slot | ( | EdgeHash * | eh, |
uint | slot, | ||
Edge | edge, | ||
void * | value | ||
) |
Definition at line 142 of file edgehash.c.
References _EdgeHash_Entry::edge, EdgeHash::entries, EdgeHash::length, EdgeHash::map, and _EdgeHash_Entry::value.
Referenced by BLI_edgehash_ensure_p(), BLI_edgehash_reinsert(), and edgehash_insert().
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().
BLI_INLINE EdgeHashEntry* edgehash_lookup_entry | ( | const EdgeHash * | eh, |
uint | v0, | ||
uint | v1 | ||
) |
Definition at line 182 of file edgehash.c.
References EH_INDEX_HAS_EDGE, EdgeHash::entries, init_edge(), ITER_SLOTS, NULL, SLOT_EMPTY, and v1.
Referenced by BLI_edgehash_haskey(), BLI_edgehash_lookup(), BLI_edgehash_lookup_default(), and BLI_edgehash_lookup_p().
BLI_INLINE bool edges_equal | ( | Edge | e1, |
Edge | e2 | ||
) |
Definition at line 100 of file edgehash.c.
BLI_INLINE void edgeset_ensure_can_insert | ( | EdgeSet * | es | ) |
Definition at line 463 of file edgehash.c.
References EdgeSet::capacity_exp, CLEAR_MAP, edgeset_insert_index(), EdgeSet::entries, ENTRIES_CAPACITY, EdgeSet::length, EdgeSet::map, MAP_CAPACITY, MEM_reallocN, UNLIKELY, and UPDATE_SLOT_MASK.
Referenced by BLI_edgeset_add(), and BLI_edgeset_insert().
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().
Definition at line 453 of file edgehash.c.
References ITER_SLOTS, EdgeSet::map, and SLOT_EMPTY.
Referenced by edgeset_ensure_can_insert().
BLI_INLINE Edge init_edge | ( | uint | v0, |
uint | v1 | ||
) |
Definition at line 83 of file edgehash.c.
References BLI_assert, and v1.
Referenced by BLI_edgehash_ensure_p(), BLI_edgehash_insert(), BLI_edgehash_popkey(), BLI_edgehash_reinsert(), BLI_edgeset_add(), BLI_edgeset_haskey(), BLI_edgeset_insert(), and edgehash_lookup_entry().