[Bf-blender-cvs] [aa63a87d37d] blender2.8: BLI: New Edgehash and EdgeSet implementation
Jacques Lucke
noreply at git.blender.org
Thu Dec 13 11:29:37 CET 2018
Commit: aa63a87d37d3b190ec8c957c892af9c1be2ea301
Author: Jacques Lucke
Date: Thu Dec 13 11:21:31 2018 +0100
Branches: blender2.8
https://developer.blender.org/rBaa63a87d37d3b190ec8c957c892af9c1be2ea301
BLI: New Edgehash and EdgeSet implementation
The new data structure uses open addressing instead of chaining to resolve collisions in the hash table.
This new structure was never slower than the old implementation in my tests. Code that first inserts all edges and then iterates through all edges (e.g. to remove duplicates) benefits the most, because the `EdgeHashIterator` becomes a simple for loop over a continuous array.
Reviewer: campbellbarton
Differential Revision: D4050
===================================================================
M source/blender/blenlib/BLI_edgehash.h
M source/blender/blenlib/intern/edgehash.c
A tests/gtests/blenlib/BLI_edgehash_test.cc
M tests/gtests/blenlib/CMakeLists.txt
===================================================================
diff --git a/source/blender/blenlib/BLI_edgehash.h b/source/blender/blenlib/BLI_edgehash.h
index 83b519fc750..38f750dfe04 100644
--- a/source/blender/blenlib/BLI_edgehash.h
+++ b/source/blender/blenlib/BLI_edgehash.h
@@ -33,10 +33,19 @@
struct EdgeHash;
typedef struct EdgeHash EdgeHash;
+struct _EdgeHash_Edge {
+ uint v_low, v_high;
+};
+
+struct _EdgeHash_Entry {
+ struct _EdgeHash_Edge edge;
+ void *value;
+};
+
typedef struct EdgeHashIterator {
- EdgeHash *eh;
- struct EdgeEntry *curEntry;
- unsigned int curBucket;
+ struct _EdgeHash_Entry *entries;
+ uint length;
+ uint index;
} EdgeHashIterator;
typedef void (*EdgeHashFreeFP)(void *key);
@@ -49,6 +58,7 @@ EdgeHash *BLI_edgehash_new_ex(const char *info,
const unsigned int nentries_reserve);
EdgeHash *BLI_edgehash_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp);
+void BLI_edgehash_print(EdgeHash *eh);
void BLI_edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val);
bool BLI_edgehash_reinsert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val);
void *BLI_edgehash_lookup(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT;
@@ -63,33 +73,24 @@ int BLI_edgehash_len(EdgeHash *eh) ATTR_WARN_UNUSED_RESULT;
void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP valfreefp,
const unsigned int nentries_reserve);
void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp);
-void BLI_edgehash_flag_set(EdgeHash *eh, unsigned int flag);
-void BLI_edgehash_flag_clear(EdgeHash *eh, unsigned int flag);
EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
void BLI_edgehashIterator_init(EdgeHashIterator *ehi, EdgeHash *eh);
void BLI_edgehashIterator_free(EdgeHashIterator *ehi);
-void BLI_edgehashIterator_step(EdgeHashIterator *ehi);
-BLI_INLINE bool BLI_edgehashIterator_isDone(EdgeHashIterator *ehi) ATTR_WARN_UNUSED_RESULT;
-BLI_INLINE void BLI_edgehashIterator_getKey(EdgeHashIterator *ehi, unsigned int *r_v0, unsigned int *r_v1);
-BLI_INLINE void *BLI_edgehashIterator_getValue(EdgeHashIterator *ehi) ATTR_WARN_UNUSED_RESULT;
-BLI_INLINE void **BLI_edgehashIterator_getValue_p(EdgeHashIterator *ehi) ATTR_WARN_UNUSED_RESULT;
-BLI_INLINE void BLI_edgehashIterator_setValue(EdgeHashIterator *ehi, void *val);
-
-struct _eh_Entry { void *next; unsigned int v0, v1; void *val; };
+BLI_INLINE void BLI_edgehashIterator_step(EdgeHashIterator *ehi)
+{ ehi->index++; }
+BLI_INLINE bool BLI_edgehashIterator_isDone(EdgeHashIterator *ehi)
+{ return ehi->index >= ehi->length; }
BLI_INLINE void BLI_edgehashIterator_getKey(EdgeHashIterator *ehi, unsigned int *r_v0, unsigned int *r_v1)
-{ *r_v0 = ((struct _eh_Entry *)ehi->curEntry)->v0; *r_v1 = ((struct _eh_Entry *)ehi->curEntry)->v1; }
-BLI_INLINE void *BLI_edgehashIterator_getValue(EdgeHashIterator *ehi) { return ((struct _eh_Entry *)ehi->curEntry)->val; }
-BLI_INLINE void **BLI_edgehashIterator_getValue_p(EdgeHashIterator *ehi) { return &((struct _eh_Entry *)ehi->curEntry)->val; }
-BLI_INLINE void BLI_edgehashIterator_setValue(EdgeHashIterator *ehi, void *val) { ((struct _eh_Entry *)ehi->curEntry)->val = val; }
-BLI_INLINE bool BLI_edgehashIterator_isDone(EdgeHashIterator *ehi) { return (((struct _eh_Entry *)ehi->curEntry) == NULL); }
-/* disallow further access */
-#ifdef __GNUC__
-# pragma GCC poison _eh_Entry
-#else
-# define _eh_Entry void
-#endif
+{ struct _EdgeHash_Edge edge = ehi->entries[ehi->index].edge; *r_v0 = edge.v_low; *r_v1 = edge.v_high; }
+BLI_INLINE void *BLI_edgehashIterator_getValue(EdgeHashIterator *ehi)
+{ return ehi->entries[ehi->index].value; }
+BLI_INLINE void **BLI_edgehashIterator_getValue_p(EdgeHashIterator *ehi)
+{ return &ehi->entries[ehi->index].value; }
+BLI_INLINE void BLI_edgehashIterator_setValue(EdgeHashIterator *ehi, void *val)
+{ ehi->entries[ehi->index].value = val; }
+
#define BLI_EDGEHASH_SIZE_GUESS_FROM_LOOPS(totloop) ((totloop) / 2)
#define BLI_EDGEHASH_SIZE_GUESS_FROM_POLYS(totpoly) ((totpoly) * 2)
@@ -97,9 +98,13 @@ BLI_INLINE bool BLI_edgehashIterator_isDone(EdgeHashIterator *ehi) { return ((
/* *** EdgeSet *** */
struct EdgeSet;
-struct EdgeSetIterator;
typedef struct EdgeSet EdgeSet;
-typedef struct EdgeSetIterator EdgeSetIterator;
+
+typedef struct EdgeSetIterator {
+ struct _EdgeHash_Edge *edges;
+ uint length;
+ uint index;
+} EdgeSetIterator;
EdgeSet *BLI_edgeset_new_ex(const char *info,
const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
@@ -107,21 +112,18 @@ EdgeSet *BLI_edgeset_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
int BLI_edgeset_len(EdgeSet *es) ATTR_WARN_UNUSED_RESULT;
bool BLI_edgeset_add(EdgeSet *es, unsigned int v0, unsigned int v1);
void BLI_edgeset_insert(EdgeSet *es, unsigned int v0, unsigned int v1);
-bool BLI_edgeset_haskey(EdgeSet *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT;
+bool BLI_edgeset_haskey(EdgeSet *es, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT;
void BLI_edgeset_free(EdgeSet *es);
-void BLI_edgeset_flag_set(EdgeSet *es, unsigned int flag);
-void BLI_edgeset_flag_clear(EdgeSet *es, unsigned int flag);
/* rely on inline api for now */
-BLI_INLINE EdgeSetIterator *BLI_edgesetIterator_new(EdgeSet *gs) { return (EdgeSetIterator *)BLI_edgehashIterator_new((EdgeHash *)gs); }
-BLI_INLINE void BLI_edgesetIterator_free(EdgeSetIterator *esi) { BLI_edgehashIterator_free((EdgeHashIterator *)esi); }
-BLI_INLINE void BLI_edgesetIterator_getKey(EdgeSetIterator *esi, unsigned int *r_v0, unsigned int *r_v1) { BLI_edgehashIterator_getKey((EdgeHashIterator *)esi, r_v0, r_v1); }
-BLI_INLINE void BLI_edgesetIterator_step(EdgeSetIterator *esi) { BLI_edgehashIterator_step((EdgeHashIterator *)esi); }
-BLI_INLINE bool BLI_edgesetIterator_isDone(EdgeSetIterator *esi) { return BLI_edgehashIterator_isDone((EdgeHashIterator *)esi); }
-
-#ifdef DEBUG
-double BLI_edgehash_calc_quality(EdgeHash *eh);
-double BLI_edgeset_calc_quality(EdgeSet *es);
-#endif
+EdgeSetIterator *BLI_edgesetIterator_new(EdgeSet *gs);
+void BLI_edgesetIterator_free(EdgeSetIterator *esi);
+
+BLI_INLINE void BLI_edgesetIterator_getKey(EdgeSetIterator *esi, unsigned int *r_v0, unsigned int *r_v1)
+{ struct _EdgeHash_Edge edge = esi->edges[esi->index]; *r_v0 = edge.v_low; *r_v1 = edge.v_high; }
+BLI_INLINE void BLI_edgesetIterator_step(EdgeSetIterator *esi)
+{ esi->index++; }
+BLI_INLINE bool BLI_edgesetIterator_isDone(EdgeSetIterator *esi)
+{ return esi->index >= esi->length; }
#endif /* __BLI_EDGEHASH_H__ */
diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c
index 81bfb566278..996c815a062 100644
--- a/source/blender/blenlib/intern/edgehash.c
+++ b/source/blender/blenlib/intern/edgehash.c
@@ -15,19 +15,16 @@
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*
- * Contributor(s): Daniel Dunbar, Joseph Eagar
- *
* ***** END GPL LICENSE BLOCK *****
*/
/** \file blender/blenlib/intern/edgehash.c
* \ingroup bli
*
- * An (edge -> pointer) chaining hash table.
+ * An (edge -> pointer) hash table.
* Using unordered int-pairs as keys.
*
- * \note Based on 'BLI_ghash.c', which is a more generalized hash-table
- * make sure these stay in sync.
+ * \note The API matches BLI_ghash.c, but the implementation is different.
*/
#include <stdlib.h>
@@ -38,384 +35,298 @@
#include "BLI_utildefines.h"
#include "BLI_edgehash.h"
-#include "BLI_mempool.h"
#include "BLI_strict_flags.h"
-/**************inlined code************/
-static const uint _ehash_hashsizes[] = {
- 1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209,
- 16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169,
- 4194319, 8388617, 16777259, 33554467, 67108879, 134217757,
- 268435459
-};
-
-/* internal flag to ensure sets values aren't used */
-#ifndef NDEBUG
-# define EDGEHASH_FLAG_IS_SET (1 << 8)
-# define IS_EDGEHASH_ASSERT(eh) BLI_assert((eh->flag & EDGEHASH_FLAG_IS_SET) == 0)
-// # define IS_EDGESET_ASSERT(es) BLI_assert((es->flag & EDGEHASH_FLAG_IS_SET) != 0)
-#else
-# define IS_EDGEHASH_ASSERT(eh)
-// # define IS_EDGESET_ASSERT(es)
-#endif
-
-/* ensure v0 is smaller */
-#define EDGE_ORD(v0, v1) \
- if (v0 > v1) { \
- SWAP(uint, v0, v1); \
- } (void)0
-
-/***/
-
-typedef struct EdgeEntry {
- struct EdgeEntry *next;
- uint v0, v1;
- void *val;
-} EdgeEntry;
-
-struct EdgeHash {
- EdgeEntry **buckets;
- BLI_mempool *epool;
- uint nbuckets, nentries;
- uint cursize, flag;
-};
-
+typedef struct _EdgeHash_Edge Edge;
+typedef struct _EdgeHash_Entry EdgeHashEntry;
+
+typedef struct EdgeHash {
+ EdgeHashEntry *entries;
+ int32_t *map;
+ uint32_t slot_mask;
+ uint capacity_exp;
+ uint length;
+ uint dummy_count;
+} EdgeHash;
+
+typedef struct EdgeSet {
+ Edge *entries;
+ int32_t *map;
+ uint32_t slot_mask;
+ uint capacity_exp;
+ uint length;
+} EdgeSet;
/* -------------------------------------------------------------------- */
-/* EdgeHash API */
-
-/** \name Internal Utility API
+/** \name Internal Helper Macros & Defines
* \{ */
-/**
- * Compute the hash and get the bucket-index.
- */
-BLI_INLINE uint edgehash_bucket_index(EdgeHash *eh, uint v0, uint v1)
-{
- BLI_assert(v0 < v1);
-
- return ((v0 * 65) ^ (v1 * 31)) % eh->nbuckets;
-}
+#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) (container)->slot_mask = MAP_CAPACITY(container) - 1
+#define PERTURB_SHIFT 5
-/**
- * Check if the number of items in the GHash is large enough to
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list