Differential D5796 Diff 18227 source/blender/blenlib/intern/edgehash.cc

Changeset View

Standalone View

source/blender/blenlib/intern/edgehash.cc

This file was moved from source/blender/blenlib/intern/edgehash.c.

	Show All 26 Lines
	#include <string.h>			#include <string.h>
	#include <limits.h>			#include <limits.h>

	#include "MEM_guardedalloc.h"			#include "MEM_guardedalloc.h"

	#include "BLI_utildefines.h"			#include "BLI_utildefines.h"
	#include "BLI_edgehash.h"			#include "BLI_edgehash.h"
	#include "BLI_strict_flags.h"			#include "BLI_strict_flags.h"
				#include "BLI_vector_set.h"

				using BLI::VectorSet;

	typedef struct _EdgeHash_Edge Edge;			typedef struct _EdgeHash_Edge Edge;
	typedef struct _EdgeHash_Entry EdgeHashEntry;			typedef struct _EdgeHash_Entry EdgeHashEntry;

	typedef struct EdgeHash {			typedef struct EdgeHash {
	EdgeHashEntry *entries;			EdgeHashEntry *entries;
	int32_t *map;			int32_t *map;
	uint32_t slot_mask;			uint32_t slot_mask;
	uint capacity_exp;			uint capacity_exp;
	uint length;			uint length;
	uint dummy_count;			uint dummy_count;
	} EdgeHash;			} EdgeHash;

	typedef struct EdgeSet {			static EdgeSet wrap(VectorSet<Edge> es)
	Edge *entries;			{
	int32_t *map;			return (EdgeSet *)es;
	uint32_t slot_mask;			}
	uint capacity_exp;
	uint length;			static VectorSet<Edge> unwrap(EdgeSet es)
	} EdgeSet;			{
				return (VectorSet<Edge> *)es;
				}

	/* -------------------------------------------------------------------- */			/* -------------------------------------------------------------------- */
	/** \name Internal Helper Macros & Defines			/** \name Internal Helper Macros & Defines
	* \{ */			* \{ */

	#define ENTRIES_CAPACITY(container) (uint)(1 << (container)->capacity_exp)			#define ENTRIES_CAPACITY(container) (uint)(1 << (container)->capacity_exp)
	#define MAP_CAPACITY(container) (uint)(1 << ((container)->capacity_exp + 1))			#define MAP_CAPACITY(container) (uint)(1 << ((container)->capacity_exp + 1))
	#define CLEAR_MAP(container) \			#define CLEAR_MAP(container) \
	memset((container)->map, 0xFF, sizeof(int32_t) * MAP_CAPACITY(container))			memset((container)->map, 0xFF, sizeof(int32_t) * MAP_CAPACITY(container))
	#define UPDATE_SLOT_MASK(container) \			#define UPDATE_SLOT_MASK(container) \
	{ \			{ \
	(container)->slot_mask = MAP_CAPACITY(container) - 1; \			(container)->slot_mask = MAP_CAPACITY(container) - 1; \
	} \			} \
	((void)0)			((void)0)
	#define PERTURB_SHIFT 5			#define PERTURB_SHIFT 5

	#define ITER_SLOTS(CONTAINER, EDGE, SLOT, INDEX) \			#define ITER_SLOTS(CONTAINER, EDGE, SLOT, INDEX) \
	uint32_t hash = calc_edge_hash(EDGE); \			uint32_t hash = BLI::DefaultHash<Edge>{}(EDGE); \
	uint32_t mask = (CONTAINER)->slot_mask; \			uint32_t mask = (CONTAINER)->slot_mask; \
	uint32_t perturb = hash; \			uint32_t perturb = hash; \
	int32_t *map = (CONTAINER)->map; \			int32_t *map = (CONTAINER)->map; \
	uint32_t SLOT = mask & hash; \			uint32_t SLOT = mask & hash; \
	int INDEX = map[SLOT]; \			int INDEX = map[SLOT]; \
	for (;; SLOT = mask & ((5 * SLOT) + 1 + perturb), perturb >>= PERTURB_SHIFT, INDEX = map[SLOT])			for (;; SLOT = mask & ((5 * SLOT) + 1 + perturb), perturb >>= PERTURB_SHIFT, INDEX = map[SLOT])

	#define SLOT_EMPTY -1			#define SLOT_EMPTY -1
	#define SLOT_DUMMY -2			#define SLOT_DUMMY -2

	#define CAPACITY_EXP_DEFAULT 3			#define CAPACITY_EXP_DEFAULT 3

	/** \} */			/** \} */

	/* -------------------------------------------------------------------- */			/* -------------------------------------------------------------------- */
	/** \name Internal Edge API			/** \name Internal Edge API
	* \{ */			* \{ */

	BLI_INLINE uint32_t calc_edge_hash(Edge edge)			namespace BLI {
				template<> struct DefaultHash<Edge> {
				uint32_t operator()(Edge edge) const
	{			{
	return (edge.v_low << 8) ^ edge.v_high;			return (edge.v_low << 8) ^ edge.v_high;
	}			}
				};
				} // namespace BLI

				static bool operator==(Edge e1, Edge e2)
				{
				return e1.v_low == e2.v_low && e1.v_high == e2.v_high;
				}

	BLI_INLINE Edge init_edge(uint v0, uint v1)			BLI_INLINE Edge init_edge(uint v0, uint v1)
	{			{
	/* If there are use cases where we need this it could be removed (or flag to allow),			/* If there are use cases where we need this it could be removed (or flag to allow),
	* for now this helps avoid incorrect usage (creating degenerate geometry). */			* for now this helps avoid incorrect usage (creating degenerate geometry). */
	BLI_assert(v0 != v1);			BLI_assert(v0 != v1);
	Edge edge;			Edge edge;
	if (v0 < v1) {			if (v0 < v1) {
	edge.v_low = v0;			edge.v_low = v0;
	edge.v_high = v1;			edge.v_high = v1;
	}			}
	else {			else {
	edge.v_low = v1;			edge.v_low = v1;
	edge.v_high = v0;			edge.v_high = v0;
	}			}
	return edge;			return edge;
	}			}

	BLI_INLINE bool edges_equal(Edge e1, Edge e2)
	{
	return memcmp(&e1, &e2, sizeof(Edge)) == 0;
	}

	static uint calc_capacity_exp_for_reserve(uint reserve)			static uint calc_capacity_exp_for_reserve(uint reserve)
	{			{
	uint result = 1;			uint result = 1;
	while (reserve >>= 1) {			while (reserve >>= 1) {
	result++;			result++;
	}			}
	return result;			return result;
	}			}

	/** \} */			/** \} */

	/* -------------------------------------------------------------------- */			/* -------------------------------------------------------------------- */
	/** \name Internal Utility API			/** \name Internal Utility API
	* \{ */			* \{ */

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

	static void edgehash_free_values(EdgeHash *eh, EdgeHashFreeFP free_value)			static void edgehash_free_values(EdgeHash *eh, EdgeHashFreeFP free_value)
	{			{
	if (free_value) {			if (free_value) {
	for (uint i = 0; i < eh->length; i++) {			for (uint i = 0; i < eh->length; i++) {
	free_value(eh->entries[i].value);			free_value(eh->entries[i].value);
	}			}
	}			}
	Show All 20 Lines
	}			}

	BLI_INLINE bool edgehash_ensure_can_insert(EdgeHash *eh)			BLI_INLINE bool edgehash_ensure_can_insert(EdgeHash *eh)
	{			{
	if (UNLIKELY(ENTRIES_CAPACITY(eh) <= eh->length + eh->dummy_count)) {			if (UNLIKELY(ENTRIES_CAPACITY(eh) <= eh->length + eh->dummy_count)) {
	eh->capacity_exp++;			eh->capacity_exp++;
	UPDATE_SLOT_MASK(eh);			UPDATE_SLOT_MASK(eh);
	eh->dummy_count = 0;			eh->dummy_count = 0;
	eh->entries = MEM_reallocN(eh->entries, sizeof(EdgeHashEntry) * ENTRIES_CAPACITY(eh));			eh->entries = (EdgeHashEntry *)MEM_reallocN(eh->entries,
	eh->map = MEM_reallocN(eh->map, sizeof(int32_t) * MAP_CAPACITY(eh));			sizeof(EdgeHashEntry) * ENTRIES_CAPACITY(eh));
				eh->map = (int32_t )MEM_reallocN(eh->map, sizeof(int32_t) MAP_CAPACITY(eh));
	CLEAR_MAP(eh);			CLEAR_MAP(eh);
	for (uint i = 0; i < eh->length; i++) {			for (uint i = 0; i < eh->length; i++) {
	edgehash_insert_index(eh, eh->entries[i].edge, i);			edgehash_insert_index(eh, eh->entries[i].edge, i);
	}			}
	return true;			return true;
	}			}
	return false;			return false;
	}			}
	Show All 38 Lines
	/** \} */			/** \} */

	/* -------------------------------------------------------------------- */			/* -------------------------------------------------------------------- */
	/** \name Edge Hash API			/** \name Edge Hash API
	* \{ */			* \{ */

	EdgeHash BLI_edgehash_new_ex(const char info, const uint reserve)			EdgeHash BLI_edgehash_new_ex(const char info, const uint reserve)
	{			{
	EdgeHash *eh = MEM_mallocN(sizeof(EdgeHash), info);			EdgeHash eh = (EdgeHash )MEM_mallocN(sizeof(EdgeHash), info);
	eh->capacity_exp = calc_capacity_exp_for_reserve(reserve);			eh->capacity_exp = calc_capacity_exp_for_reserve(reserve);
	UPDATE_SLOT_MASK(eh);			UPDATE_SLOT_MASK(eh);
	eh->length = 0;			eh->length = 0;
	eh->dummy_count = 0;			eh->dummy_count = 0;
	eh->entries = MEM_calloc_arrayN(sizeof(EdgeHashEntry), ENTRIES_CAPACITY(eh), "eh entries");			eh->entries = (EdgeHashEntry *)MEM_calloc_arrayN(
	eh->map = MEM_malloc_arrayN(sizeof(int32_t), MAP_CAPACITY(eh), "eh map");			sizeof(EdgeHashEntry), ENTRIES_CAPACITY(eh), "eh entries");
				eh->map = (int32_t *)MEM_malloc_arrayN(sizeof(int32_t), MAP_CAPACITY(eh), "eh map");
	CLEAR_MAP(eh);			CLEAR_MAP(eh);
	return eh;			return eh;
	}			}

	EdgeHash BLI_edgehash_new(const char info)			EdgeHash BLI_edgehash_new(const char info)
	{			{
	return BLI_edgehash_new_ex(info, 1 << CAPACITY_EXP_DEFAULT);			return BLI_edgehash_new_ex(info, 1 << CAPACITY_EXP_DEFAULT);
	}			}
	▲ Show 20 Lines • Show All 222 Lines • ▼ Show 20 Lines

	/**			/**
	* Create a new EdgeHashIterator. The hash table must not be mutated			* Create a new EdgeHashIterator. The hash table must not be mutated
	* while the iterator is in use, and the iterator will step exactly			* while the iterator is in use, and the iterator will step exactly
	* BLI_edgehash_len(eh) times before becoming done.			* BLI_edgehash_len(eh) times before becoming done.
	*/			*/
	EdgeHashIterator BLI_edgehashIterator_new(EdgeHash eh)			EdgeHashIterator BLI_edgehashIterator_new(EdgeHash eh)
	{			{
	EdgeHashIterator *ehi = MEM_mallocN(sizeof(EdgeHashIterator), __func__);			EdgeHashIterator ehi = (EdgeHashIterator )MEM_mallocN(sizeof(EdgeHashIterator), __func__);
	BLI_edgehashIterator_init(ehi, eh);			BLI_edgehashIterator_init(ehi, eh);
	return ehi;			return ehi;
	}			}

	/**			/**
	* Init an already allocated EdgeHashIterator. The hash table must not			* Init an already allocated EdgeHashIterator. The hash table must not
	* be mutated while the iterator is in use, and the iterator will			* be mutated while the iterator is in use, and the iterator will
	* step exactly BLI_edgehash_len(eh) times before becoming done.			* step exactly BLI_edgehash_len(eh) times before becoming done.
	Show All 19 Lines
	/** \} */			/** \} */

	/* -------------------------------------------------------------------- */			/* -------------------------------------------------------------------- */
	/** \name EdgeSet API			/** \name EdgeSet API
	*			*
	* Use edgehash API to give 'set' functionality			* Use edgehash API to give 'set' functionality
	* \{ */			* \{ */

	#define ES_INDEX_HAS_EDGE(es, index, edge) \			EdgeSet BLI_edgeset_new_ex(const char UNUSED(info), const uint reserve)
	(index) >= 0 && edges_equal((edge), (es)->entries[index])

	EdgeSet BLI_edgeset_new_ex(const char info, const uint reserve)
	{			{
	EdgeSet *es = MEM_mallocN(sizeof(EdgeSet), info);			VectorSet<Edge> *es = new VectorSet<Edge>();
	es->capacity_exp = calc_capacity_exp_for_reserve(reserve);			es->reserve(reserve);
	UPDATE_SLOT_MASK(es);			return wrap(es);
	es->length = 0;
	es->entries = MEM_malloc_arrayN(sizeof(Edge), ENTRIES_CAPACITY(es), "es entries");
	es->map = MEM_malloc_arrayN(sizeof(int32_t), MAP_CAPACITY(es), "es map");
	CLEAR_MAP(es);
	return es;
	}			}

	EdgeSet BLI_edgeset_new(const char info)			EdgeSet BLI_edgeset_new(const char info)
	{			{
	return BLI_edgeset_new_ex(info, 1 << CAPACITY_EXP_DEFAULT);			return BLI_edgeset_new_ex(info, 1 << CAPACITY_EXP_DEFAULT);
	}			}

	void BLI_edgeset_free(EdgeSet *es)			void BLI_edgeset_free(EdgeSet *es_c)
	{
	MEM_freeN(es->entries);
	MEM_freeN(es->map);
	MEM_freeN(es);
	}

	int BLI_edgeset_len(EdgeSet *es)
	{
	return (int)es->length;
	}

	static void edgeset_insert_index(EdgeSet *es, Edge edge, uint entry_index)
	{
	ITER_SLOTS (es, edge, slot, index) {
	if (index == SLOT_EMPTY) {
	es->map[slot] = (int)entry_index;
	break;
	}
	}
	}

	BLI_INLINE void edgeset_ensure_can_insert(EdgeSet *es)
	{			{
	if (UNLIKELY(ENTRIES_CAPACITY(es) <= es->length)) {			delete unwrap(es_c);
	es->capacity_exp++;
	UPDATE_SLOT_MASK(es);
	es->entries = MEM_reallocN(es->entries, sizeof(Edge) * ENTRIES_CAPACITY(es));
	es->map = MEM_reallocN(es->map, sizeof(int32_t) * MAP_CAPACITY(es));
	CLEAR_MAP(es);
	for (uint i = 0; i < es->length; i++) {
	edgeset_insert_index(es, es->entries[i], i);
	}
	}
	}			}

	BLI_INLINE void edgeset_insert_at_slot(EdgeSet *es, uint slot, Edge edge)			int BLI_edgeset_len(EdgeSet *es_c)
	{			{
	es->entries[es->length] = edge;			return (int)unwrap(es_c)->size();
	es->map[slot] = (int)es->length;
	es->length++;
	}			}

	/**			/**
	* A version of BLI_edgeset_insert which checks first if the key is in the set.			* 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.			* \returns true if a new key has been added.
	*			*
	* \note EdgeHash has no equivalent to this because typically the value would be different.			* \note EdgeHash has no equivalent to this because typically the value would be different.
	*/			*/
	bool BLI_edgeset_add(EdgeSet *es, uint v0, uint v1)			bool BLI_edgeset_add(EdgeSet *es_c, uint v0, uint v1)
	{			{
	edgeset_ensure_can_insert(es);
	Edge edge = init_edge(v0, v1);			Edge edge = init_edge(v0, v1);
				return unwrap(es_c)->add(edge);
	ITER_SLOTS (es, edge, slot, index) {
	if (ES_INDEX_HAS_EDGE(es, index, edge)) {
	return false;
	}
	else if (index == SLOT_EMPTY) {
	edgeset_insert_at_slot(es, slot, edge);
	return true;
	}
	}
	}			}

	/**			/**
	* Adds the key to the set (no checks for unique keys!).			* Adds the key to the set (no checks for unique keys!).
	* Matching #BLI_edgehash_insert			* Matching #BLI_edgehash_insert
	*/			*/
	void BLI_edgeset_insert(EdgeSet *es, uint v0, uint v1)			void BLI_edgeset_insert(EdgeSet *es_c, uint v0, uint v1)
	{			{
	edgeset_ensure_can_insert(es);
	Edge edge = init_edge(v0, v1);			Edge edge = init_edge(v0, v1);
				unwrap(es_c)->add_new(edge);
	ITER_SLOTS (es, edge, slot, index) {
	if (index == SLOT_EMPTY) {
	edgeset_insert_at_slot(es, slot, edge);
	return;
	}
	}
	}			}

	bool BLI_edgeset_haskey(EdgeSet *es, uint v0, uint v1)			bool BLI_edgeset_haskey(EdgeSet *es_c, uint v0, uint v1)
	{			{
	Edge edge = init_edge(v0, v1);			Edge edge = init_edge(v0, v1);
				return unwrap(es_c)->contains(edge);
	ITER_SLOTS (es, edge, slot, index) {
	if (ES_INDEX_HAS_EDGE(es, index, edge)) {
	return true;
	}
	else if (index == SLOT_EMPTY) {
	return false;
	}
	}
	}			}

	EdgeSetIterator BLI_edgesetIterator_new(EdgeSet es)			EdgeSetIterator BLI_edgesetIterator_new(EdgeSet es_c)
	{			{
	EdgeSetIterator *esi = MEM_mallocN(sizeof(EdgeSetIterator), __func__);			VectorSet<Edge> *es = unwrap(es_c);
	esi->edges = es->entries;			EdgeSetIterator esi = (EdgeSetIterator )MEM_mallocN(sizeof(EdgeSetIterator), __func__);
	esi->length = es->length;			esi->edges = es->begin();
				esi->length = es->size();
	esi->index = 0;			esi->index = 0;
	return esi;			return esi;
	}			}

	void BLI_edgesetIterator_free(EdgeSetIterator *esi)			void BLI_edgesetIterator_free(EdgeSetIterator *esi)
	{			{
	MEM_freeN(esi);			MEM_freeN(esi);
	}			}

	/** \} */			/** \} */