#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"

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
EdgeHash *	BLI_edgehash_new_ex (const char *info, const uint reserve)

EdgeHash *	BLI_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)

void *	BLI_edgehash_lookup_default (EdgeHash eh, uint v0, uint v1, void default_value)

void *	BLI_edgehash_lookup (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)

void *	BLI_edgehash_popkey (EdgeHash *eh, uint v0, uint v1)

bool	BLI_edgehash_haskey (EdgeHash *eh, uint v0, uint v1)

int	BLI_edgehash_len (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
EdgeHashIterator *	BLI_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 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 (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])

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 (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 (EdgeSet *es, uint v0, uint v1)

EdgeSetIterator *	BLI_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 84 of file edgehash.c.

◆ CLEAR_MAP

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

Definition at line 63 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 134 of file edgehash.c.

◆ ENTRIES_CAPACITY

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

Definition at line 61 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 509 of file edgehash.c.

◆ ITER_SLOTS

#define ITER_SLOTS	(	CONTAINER,
		EDGE,
		SLOT,
		INDEX
	)

Value:

  uint32_t hash = calc_edge_hash(EDGE); \
  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])

Definition at line 72 of file edgehash.c.

◆ MAP_CAPACITY

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

Definition at line 62 of file edgehash.c.

◆ PERTURB_SHIFT

#define PERTURB_SHIFT 5

Definition at line 70 of file edgehash.c.

◆ SLOT_DUMMY

#define SLOT_DUMMY -2

Definition at line 82 of file edgehash.c.

◆ SLOT_EMPTY

#define SLOT_EMPTY -1

Definition at line 81 of file edgehash.c.

◆ UPDATE_SLOT_MASK

#define UPDATE_SLOT_MASK ( container )

Value:

  { \
    (container)->slot_mask = MAP_CAPACITY(container) - 1; \
  } \
  ((void)0)

Definition at line 65 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

typedef struct _EdgeHash_Entry 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 455 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
	)

Remove all edges from hash.

Definition at line 442 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().

◆ BLI_edgehash_ensure_p()

bool BLI_edgehash_ensure_p	(	EdgeHash *	eh,
		uint	v0,
		uint	v1,
		void ***	r_value
	)

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 355 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(), lines_adjacency_triangle(), set_edge_adjacency_lines_indices(), split_faces_prepare_new_edges(), statvis_calc_sharp(), and TEST().

◆ BLI_edgehash_free()

void BLI_edgehash_free	(	EdgeHash *	eh,
		EdgeHashFreeFP	free_value
	)

◆ BLI_edgehash_haskey()

bool BLI_edgehash_haskey	(	EdgeHash *	eh,
		uint	v0,
		uint	v1
	)

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

Definition at line 426 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,
		uint	v0,
		uint	v1,
		void *	value
	)

Insert edge (v0, v1) into hash with given value, does not check for duplicates.

Definition at line 279 of file edgehash.c.

References edgehash_ensure_can_insert(), edgehash_insert(), init_edge(), and v1.

Referenced by BKE_mesh_convert_mfaces_to_mpolys_ex(), BKE_mesh_validate_arrays(), ccgDM_copyFinalLoopArray(), customdata_compare(), mesh_calc_edges_mdata(), sph_springhash_build(), TEST(), and test_polyfill_topology().

◆ BLI_edgehash_len()

int BLI_edgehash_len ( EdgeHash * eh )

Return number of keys in hash.

Definition at line 434 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	(	EdgeHash *	eh,
		uint	v0,
		uint	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 325 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(), sph_force_cb(), and TEST().

◆ BLI_edgehash_lookup_default()

void* BLI_edgehash_lookup_default	(	EdgeHash *	eh,
		uint	v0,
		uint	v1,
		void *	default_value
	)

A version of BLI_edgehash_lookup which accepts a fallback argument.

Definition at line 313 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,
		uint	v0,
		uint	v1
	)

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

Definition at line 335 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 239 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,
		uint	v0,
		uint	v1
	)

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

Parameters

v0,v1 The key to remove.

Returns: the value of key int eh or NULL.

Definition at line 401 of file edgehash.c.

References EdgeHash::dummy_count, _EdgeHash_Entry::edge, edgehash_change_index(), EH_INDEX_HAS_EDGE, EdgeHash::entries, init_edge(), ITER_SLOTS, 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 )

Definition at line 252 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.

◆ BLI_edgehash_reinsert()

bool BLI_edgehash_reinsert	(	EdgeHash *	eh,
		uint	v0,
		uint	v1,
		void *	value
	)

Assign a new value to a key that may already be in edgehash.

Definition at line 289 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().

◆ BLI_edgehash_remove()

bool BLI_edgehash_remove	(	EdgeHash *	eh,
		uint	v0,
		uint	v1,
		EdgeHashFreeFP	free_value
	)

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

Parameters

v0,v1	The key to remove.
free_value	Optional callback to free the value.

Returns: true if key was removed from eh.

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

Free an EdgeHashIterator.

Definition at line 496 of file edgehash.c.

References MEM_freeN.

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

◆ BLI_edgehashIterator_init()

void BLI_edgehashIterator_init	(	EdgeHashIterator *	ehi,
		EdgeHash *	eh
	)

Init 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

ehi	The EdgeHashIterator to initialize.
eh	The EdgeHash to iterate over.

Definition at line 486 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 471 of file edgehash.c.

References BLI_edgehashIterator_init(), and MEM_mallocN.

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