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

2 files changed, 394 insertions, 546 deletions

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 require more buckets.
- */
-BLI_INLINE bool edgehash_test_expand_buckets(const uint nentries, const uint nbuckets)
-{
-	return (nentries > nbuckets * 3);
-}
+#define ITER_SLOTS(CONTAINER, EDGE, SLOT, INDEX) \
+    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])
 
-/**
- * Expand buckets to the next size up.
- */
-BLI_INLINE void edgehash_resize_buckets(EdgeHash *eh, const uint nbuckets)
-{
-	EdgeEntry **buckets_old = eh->buckets;
-	EdgeEntry **buckets_new;
-	const uint nbuckets_old = eh->nbuckets;
-	uint i;
+#define SLOT_EMPTY -1
+#define SLOT_DUMMY -2
 
-	BLI_assert(eh->nbuckets != nbuckets);
+#define CAPACITY_EXP_DEFAULT 3
 
-	eh->nbuckets = nbuckets;
-	buckets_new = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
+/** \} */
 
-	for (i = 0; i < nbuckets_old; i++) {
-		for (EdgeEntry *e = buckets_old[i], *e_next; e; e = e_next) {
-			const unsigned bucket_index = edgehash_bucket_index(eh, e->v0, e->v1);
-			e_next = e->next;
-			e->next = buckets_new[bucket_index];
-			buckets_new[bucket_index] = e;
-		}
-	}
+/* -------------------------------------------------------------------- */
+/** \name Internal Edge API
+ * \{ */
 
-	eh->buckets = buckets_new;
-	MEM_freeN(buckets_old);
+BLI_INLINE uint32_t calc_edge_hash(Edge edge)
+{
+	return (edge.v_low << 8) ^ edge.v_high;
 }
 
-/**
- * Increase initial bucket size to match a reserved amount.
- */
-BLI_INLINE void edgehash_buckets_reserve(EdgeHash *eh, const uint nentries_reserve)
+BLI_INLINE Edge init_edge(uint v0, uint v1)
 {
-	while (edgehash_test_expand_buckets(nentries_reserve, eh->nbuckets)) {
-		eh->nbuckets = _ehash_hashsizes[++eh->cursize];
+	Edge edge;
+	if (v0 < v1) {
+		edge.v_low = v0;
+		edge.v_high = v1;
 	}
-}
-
-/**
- * Internal lookup function.
- * Takes a \a bucket_index argument to avoid calling #edgehash_bucket_index multiple times.
- */
-BLI_INLINE EdgeEntry *edgehash_lookup_entry_ex(
-        EdgeHash *eh, uint v0, uint v1,
-        const uint bucket_index)
-{
-	EdgeEntry *e;
-	BLI_assert(v0 < v1);
-	for (e = eh->buckets[bucket_index]; e; e = e->next) {
-		if (UNLIKELY(v0 == e->v0 && v1 == e->v1)) {
-			return e;
-		}
+	else {
+		edge.v_low = v1;
+		edge.v_high = v0;
 	}
-	return NULL;
+	return edge;
 }
 
-/**
- * Internal lookup function, returns previous entry of target one too.
- * Takes bucket_index argument to avoid calling #edgehash_bucket_index multiple times.
- * Useful when modifying buckets somehow (like removing an entry...).
- */
-BLI_INLINE EdgeEntry *edgehash_lookup_entry_prev_ex(
-        EdgeHash *eh, uint v0, uint v1,
-        EdgeEntry **r_e_prev, const uint bucket_index)
-{
-	BLI_assert(v0 < v1);
-	for (EdgeEntry *e_prev = NULL, *e = eh->buckets[bucket_index]; e; e_prev = e, e = e->next) {
-		if (UNLIKELY(v0 == e->v0 && v1 == e->v1)) {
-			*r_e_prev = e_prev;
-			return e;
-		}
-	}
-
-	*r_e_prev = NULL;
-	return NULL;
+BLI_INLINE bool edges_equal(Edge e1, Edge e2)
+{
+	return memcmp(&e1, &e2, sizeof(Edge)) == 0;
 }
 
-/**
- * Internal lookup function. Only wraps #edgehash_lookup_entry_ex
- */
-BLI_INLINE EdgeEntry *edgehash_lookup_entry(EdgeHash *eh, uint v0, uint v1)
+static uint calc_capacity_exp_for_reserve(uint reserve)
 {
-	EDGE_ORD(v0, v1);
-	const uint bucket_index = edgehash_bucket_index(eh, v0, v1);
-	return edgehash_lookup_entry_ex(eh, v0, v1, bucket_index);
+	uint result = 1;
+	while (reserve >>= 1) result++;
+	return result;
 }
 
+/** \} */
 
-static EdgeHash *edgehash_new(const char *info,
-                              const uint nentries_reserve,
-                              const uint entry_size)
-{
-	EdgeHash *eh = MEM_mallocN(sizeof(*eh), info);
+/* -------------------------------------------------------------------- */
+/** \name Internal Utility API
+ * \{ */
 
-	eh->nbuckets = _ehash_hashsizes[0];  /* eh->cursize */
-	eh->nentries = 0;
-	eh->cursize = 0;
-	eh->flag = 0;
+#define EH_INDEX_HAS_EDGE(eh, index, edge) (index) >= 0 && edges_equal((edge), (eh)->entries[index].edge)
 
-	/* if we have reserved the number of elements that this hash will contain */
-	if (nentries_reserve) {
-		edgehash_buckets_reserve(eh, nentries_reserve);
+static void edgehash_free_values(EdgeHash *eh, EdgeHashFreeFP free_value)
+{
+	if (free_value) {
+		for (uint i = 0; i < eh->length; i++) {
+			free_value(eh->entries[i].value);
+		}
 	}
-
-	eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
-	eh->epool = BLI_mempool_create(entry_size, nentries_reserve, 512, BLI_MEMPOOL_NOP);
-
-	return eh;
 }
 
-/**
- * Internal insert function.
- * Takes a \a bucket_index argument to avoid calling #edgehash_bucket_index multiple times.
- */
-BLI_INLINE void edgehash_insert_ex(
-        EdgeHash *eh, uint v0, uint v1, void *val,
-        const uint bucket_index)
+BLI_INLINE void edgehash_insert_index(EdgeHash *eh, Edge edge, uint entry_index)
 {
-	EdgeEntry *e = BLI_mempool_alloc(eh->epool);
-
-	BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0));
-	IS_EDGEHASH_ASSERT(eh);
-
-	/* this helps to track down errors with bad edge data */
-	BLI_assert(v0 < v1);
-	BLI_assert(v0 != v1);
-
-	e->next = eh->buckets[bucket_index];
-	e->v0 = v0;
-	e->v1 = v1;
-	e->val = val;
-	eh->buckets[bucket_index] = e;
-
-	if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
-		edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]);
+	ITER_SLOTS(eh, edge, slot, index) {
+		if (index == SLOT_EMPTY) {
+			eh->map[slot] = (int32_t)entry_index;
+			break;
+		}
 	}
 }
 
-/**
- * Insert function that doesn't set the value (use for EdgeSet)
- */
-BLI_INLINE void edgehash_insert_ex_keyonly(
-        EdgeHash *eh, uint v0, uint v1,
-        const uint bucket_index)
+BLI_INLINE EdgeHashEntry *edgehash_insert_at_slot(EdgeHash *eh, uint slot, Edge edge, void *value)
 {
-	EdgeEntry *e = BLI_mempool_alloc(eh->epool);
-
-	BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0));
-
-	/* this helps to track down errors with bad edge data */
-	BLI_assert(v0 < v1);
-	BLI_assert(v0 != v1);
-
-	e->next = eh->buckets[bucket_index];
-	e->v0 = v0;
-	e->v1 = v1;
-	eh->buckets[bucket_index] = e;
-
-	if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
-		edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]);
-	}
+	EdgeHashEntry *entry = &eh->entries[eh->length];
+	entry->edge = edge;
+	entry->value = value;
+	eh->map[slot] = (int32_t)eh->length;
+	eh->length++;
+	return entry;
 }
 
-/**
- * Insert function that doesn't set the value (use for EdgeSet)
- */
-BLI_INLINE void edgehash_insert_ex_keyonly_entry(
-        EdgeHash *eh, uint v0, uint v1,
-        const uint bucket_index,
-        EdgeEntry *e)
+BLI_INLINE bool edgehash_ensure_can_insert(EdgeHash *eh)
 {
-	BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0));
-
-	/* this helps to track down errors with bad edge data */
-	BLI_assert(v0 < v1);
-	BLI_assert(v0 != v1);
-
-	e->next = eh->buckets[bucket_index];
-	e->v0 = v0;
-	e->v1 = v1;
-	/* intentionally leave value unset */
-	eh->buckets[bucket_index] = e;
-
-	if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
-		edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]);
+	if (UNLIKELY(ENTRIES_CAPACITY(eh) <= eh->length + eh->dummy_count)) {
+		eh->capacity_exp++;
+		UPDATE_SLOT_MASK(eh);
+		eh->dummy_count = 0;
+		eh->entries = MEM_reallocN(eh->entries, sizeof(EdgeHashEntry) * ENTRIES_CAPACITY(eh));
+		eh->map = MEM_reallocN(eh->map, sizeof(int32_t) * MAP_CAPACITY(eh));
+		CLEAR_MAP(eh);
+		for (uint i = 0; i < eh->length; i++) {
+			edgehash_insert_index(eh, eh->entries[i].edge, i);
+		}
+		return true;
 	}
+	return false;
 }
 
-BLI_INLINE void edgehash_insert(EdgeHash *eh, uint v0, uint v1, void *val)
+BLI_INLINE EdgeHashEntry *edgehash_insert(EdgeHash *eh, Edge edge, void *value)
 {
-	EDGE_ORD(v0, v1);
-	const uint bucket_index = edgehash_bucket_index(eh, v0, v1);
-	edgehash_insert_ex(eh, v0, v1, val, bucket_index);
+	ITER_SLOTS(eh, edge, slot, index) {
+		if (index == SLOT_EMPTY) {
+			return edgehash_insert_at_slot(eh, slot, edge, value);
+		}
+		else if (index == SLOT_DUMMY) {
+			eh->dummy_count--;
+			return edgehash_insert_at_slot(eh, slot, edge, value);
+		}
+	}
 }
 
-/**
- * Remove the entry and return it, caller must free from eh->epool.
- */
-BLI_INLINE EdgeEntry *edgehash_remove_ex(
-        EdgeHash *eh, uint v0, uint v1,
-        EdgeHashFreeFP valfreefp,
-        const uint bucket_index)
+BLI_INLINE EdgeHashEntry *edgehash_lookup_entry(EdgeHash *eh, uint v0, uint v1)
 {
-	EdgeEntry *e_prev;
-	EdgeEntry *e = edgehash_lookup_entry_prev_ex(eh, v0, v1, &e_prev, bucket_index);
-
-	BLI_assert(v0 < v1);
-
-	if (e) {
-		EdgeEntry *e_next = e->next;
-
-		if (valfreefp) {
-			valfreefp(e->val);
-		}
+	Edge edge = init_edge(v0, v1);
 
-		if (e_prev) {
-			e_prev->next = e_next;
+	ITER_SLOTS(eh, edge, slot, index) {
+		if (EH_INDEX_HAS_EDGE(eh, index, edge)) {
+			return &eh->entries[index];
 		}
-		else {
-			eh->buckets[bucket_index] = e_next;
+		else if (index == SLOT_EMPTY) {
+			return NULL;
 		}
-
-		eh->nentries--;
-		return e;
 	}
-
-	return e;
 }
 
-/**
- * Run free callbacks for freeing entries.
- */
-static void edgehash_free_cb(EdgeHash *eh, EdgeHashFreeFP valfreefp)
+BLI_INLINE void edgehash_change_index(EdgeHash *eh, Edge edge, int new_index)
 {
-	uint i;
-
-	BLI_assert(valfreefp);
-
-	for (i = 0; i < eh->nbuckets; i++) {
-		EdgeEntry *e;
-
-		for (e = eh->buckets[i]; e; ) {
-			EdgeEntry *e_next = e->next;
-
-			valfreefp(e->val);
-
-			e = e_next;
+	ITER_SLOTS(eh, edge, slot, index) {
+		if (EH_INDEX_HAS_EDGE(eh, index, edge)) {
+			eh->map[slot] = new_index;
+			break;
 		}
 	}
 }
 
 /** \} */
 
-
-/** \name Public API
+/* -------------------------------------------------------------------- */
+/** \name Edge Hash API
  * \{ */
 
-/* Public API */
-
-EdgeHash *BLI_edgehash_new_ex(const char *info,
-                              const uint nentries_reserve)
+EdgeHash *BLI_edgehash_new_ex(const char *info, const uint reserve)
 {
-	return edgehash_new(info,
-	                    nentries_reserve,
-	                    sizeof(EdgeEntry));
+	EdgeHash *eh = MEM_mallocN(sizeof(EdgeHash), info);
+	eh->capacity_exp = calc_capacity_exp_for_reserve(reserve);
+	UPDATE_SLOT_MASK(eh);
+	eh->length = 0;
+	eh->dummy_count = 0;
+	eh->entries = MEM_calloc_arrayN(sizeof(EdgeHashEntry), ENTRIES_CAPACITY(eh), "eh entries");
+	eh->map = MEM_malloc_arrayN(sizeof(int32_t), MAP_CAPACITY(eh), "eh map");
+	CLEAR_MAP(eh);
+	return eh;
 }
 
 EdgeHash *BLI_edgehash_new(const char *info)
 {
-	return BLI_edgehash_new_ex(info, 0);
+	return BLI_edgehash_new_ex(info, 1 << CAPACITY_EXP_DEFAULT);
+}
+
+void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP free_value)
+{
+	edgehash_free_values(eh, free_value);
+	MEM_freeN(eh->map);
+	MEM_freeN(eh->entries);
+	MEM_freeN(eh);
+}
+
+void BLI_edgehash_print(EdgeHash *eh)
+{
+	printf("Edgehash at %p:\n", eh);
+	printf("  Map:\n");
+	for (uint i = 0; i < MAP_CAPACITY(eh); i++) {
+		int index = eh->map[i];
+		printf("    %u: %d", i, index);
+		if (index >= 0) {
+			EdgeHashEntry entry = eh->entries[index];
+			printf(" -> (%u, %u) -> %p", entry.edge.v_low, entry.edge.v_high, entry.value);
+		}
+		printf("\n");
+	}
+	printf("  Entries:\n");
+	for (uint i = 0; i < ENTRIES_CAPACITY(eh); i++) {
+		if (i == eh->length) printf("    **** below is rest capacity ****\n");
+		EdgeHashEntry entry = eh->entries[i];
+		printf("    %u: (%u, %u) -> %p\n", i, entry.edge.v_low, entry.edge.v_high, entry.value);
+
+	}
 }
 
 /**
  * Insert edge (\a v0, \a v1) into hash with given value, does
  * not check for duplicates.
  */
-void BLI_edgehash_insert(EdgeHash *eh, uint v0, uint v1, void *val)
+void BLI_edgehash_insert(EdgeHash *eh, uint v0, uint v1, void *value)
 {
-	edgehash_insert(eh, v0, v1, val);
+	edgehash_ensure_can_insert(eh);
+	Edge edge = init_edge(v0, v1);
+	edgehash_insert(eh, edge, value);
 }
 
 /**
  * Assign a new value to a key that may already be in edgehash.
  */
-bool BLI_edgehash_reinsert(EdgeHash *eh, uint v0, uint v1, void *val)
+bool BLI_edgehash_reinsert(EdgeHash *eh, uint v0, uint v1, void *value)
 {
-	IS_EDGEHASH_ASSERT(eh);
-
-	EDGE_ORD(v0, v1);
-	const uint bucket_index = edgehash_bucket_index(eh, v0, v1);
+	Edge edge = init_edge(v0, v1);
 
-	EdgeEntry *e = edgehash_lookup_entry_ex(eh, v0, v1, bucket_index);
-	if (e) {
-		e->val = val;
-		return false;
-	}
-	else {
-		edgehash_insert_ex(eh, v0, v1, val, bucket_index);
-		return true;
+	ITER_SLOTS(eh, edge, slot, index) {
+		if (EH_INDEX_HAS_EDGE(eh, index, edge)) {
+			eh->entries[index].value = value;
+			return false;
+		}
+		else if (index == SLOT_EMPTY) {
+			if (edgehash_ensure_can_insert(eh)) {
+				edgehash_insert(eh, edge, value);
+			}
+			else {
+				edgehash_insert_at_slot(eh, slot, edge, value);
+			}
+			return true;
+		}
 	}
 }
 
 /**
+ * A version of #BLI_edgehash_lookup which accepts a fallback argument.
+ */
+void *BLI_edgehash_lookup_default(EdgeHash *eh, uint v0, uint v1, void *default_value)
+{
+	EdgeHashEntry *entry = edgehash_lookup_entry(eh, v0, v1);
+	return entry ? entry->value : default_value;
+}
+
+/**
+ * Return value for given edge (\a v0, \a 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().
+ */
+void *BLI_edgehash_lookup(EdgeHash *eh, uint v0, uint v1)
+{
+	EdgeHashEntry *entry = edgehash_lookup_entry(eh, v0, v1);
+	return entry ? entry->value : NULL;
+}
+
+/**
  * Return pointer to value for given edge (\a v0, \a v1),
  * or NULL if key does not exist in hash.
  */
 void **BLI_edgehash_lookup_p(EdgeHash *eh, uint v0, uint v1)
 {
-	EdgeEntry *e = edgehash_lookup_entry(eh, v0, v1);
-	IS_EDGEHASH_ASSERT(eh);
-	return e ? &e->val : NULL;
+	EdgeHashEntry *entry = edgehash_lookup_entry(eh, v0, v1);
+	return entry ? &entry->value : NULL;
 }
 
 /**
@@ -432,43 +343,25 @@ void **BLI_edgehash_lookup_p(EdgeHash *eh, uint v0, uint v1)
  * \returns true when the value didn't need to be added.
  * (when false, the caller _must_ initialize the value).
  */
-bool BLI_edgehash_ensure_p(EdgeHash *eh, uint v0, uint v1, void ***r_val)
+bool BLI_edgehash_ensure_p(EdgeHash *eh, uint v0, uint v1, void ***r_value)
 {
-	EDGE_ORD(v0, v1);
-	const uint bucket_index = edgehash_bucket_index(eh, v0, v1);
-	EdgeEntry *e = edgehash_lookup_entry_ex(eh, v0, v1, bucket_index);
-	const bool haskey = (e != NULL);
+	Edge edge = init_edge(v0, v1);
 
-	if (!haskey) {
-		e = BLI_mempool_alloc(eh->epool);
-		edgehash_insert_ex_keyonly_entry(eh, v0, v1, bucket_index, e);
+	ITER_SLOTS(eh, edge, slot, index) {
+		if (EH_INDEX_HAS_EDGE(eh, index, edge)) {
+			*r_value = &eh->entries[index].value;
+			return true;
+		}
+		else if (index == SLOT_EMPTY) {
+			if (edgehash_ensure_can_insert(eh)) {
+				edgehash_insert(eh, edge, NULL);
+			}
+			else {
+				*r_value = &edgehash_insert_at_slot(eh, slot, edge, NULL)->value;
+			}
+			return false;
+		}
 	}
-
-	*r_val = &e->val;
-	return haskey;
-}
-
-/**
- * Return value for given edge (\a v0, \a 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().
- */
-void *BLI_edgehash_lookup(EdgeHash *eh, uint v0, uint v1)
-{
-	EdgeEntry *e = edgehash_lookup_entry(eh, v0, v1);
-	IS_EDGEHASH_ASSERT(eh);
-	return e ? e->val : NULL;
-}
-
-/**
- * A version of #BLI_edgehash_lookup which accepts a fallback argument.
- */
-void *BLI_edgehash_lookup_default(EdgeHash *eh, uint v0, uint v1, void *val_default)
-{
-	EdgeEntry *e = edgehash_lookup_entry(eh, v0, v1);
-	IS_EDGEHASH_ASSERT(eh);
-	return e ? e->val : val_default;
 }
 
 /**
@@ -478,18 +371,12 @@ void *BLI_edgehash_lookup_default(EdgeHash *eh, uint v0, uint v1, void *val_defa
  * \param valfreefp: Optional callback to free the value.
  * \return true if \a key was removed from \a eh.
  */
-bool BLI_edgehash_remove(EdgeHash *eh, uint v0, uint v1, EdgeHashFreeFP valfreefp)
+bool BLI_edgehash_remove(EdgeHash *eh, uint v0, uint v1, EdgeHashFreeFP free_value)
 {
-	EDGE_ORD(v0, v1);
-	const uint bucket_index = edgehash_bucket_index(eh, v0, v1);
-	EdgeEntry *e = edgehash_remove_ex(eh, v0, v1, valfreefp, bucket_index);
-	if (e) {
-		BLI_mempool_free(eh->epool, e);
-		return true;
-	}
-	else {
-		return false;
-	}
+	uint old_length = eh->length;
+	void *value = BLI_edgehash_popkey(eh, v0, v1);
+	if (free_value && value) free_value(value);
+	return old_length > eh->length;
 }
 
 /* same as above but return the value,
@@ -502,17 +389,23 @@ bool BLI_edgehash_remove(EdgeHash *eh, uint v0, uint v1, EdgeHashFreeFP valfreef
  */
 void *BLI_edgehash_popkey(EdgeHash *eh, uint v0, uint v1)
 {
-	EDGE_ORD(v0, v1);
-	const uint bucket_index = edgehash_bucket_index(eh, v0, v1);
-	EdgeEntry *e = edgehash_remove_ex(eh, v0, v1, NULL, bucket_index);
-	IS_EDGEHASH_ASSERT(eh);
-	if (e) {
-		void *val = e->val;
-		BLI_mempool_free(eh->epool, e);
-		return val;
-	}
-	else {
-		return NULL;
+	Edge edge = init_edge(v0, v1);
+
+	ITER_SLOTS(eh, edge, slot, index) {
+		if (EH_INDEX_HAS_EDGE(eh, index, edge)) {
+			void *value = eh->entries[index].value;
+			eh->length--;
+			eh->dummy_count++;
+			eh->map[slot] = SLOT_DUMMY;
+			eh->entries[index] = eh->entries[eh->length];
+			if ((uint)index < eh->length) {
+				edgehash_change_index(eh, eh->entries[index].edge, index);
+			}
+			return value;
+		}
+		else if (index == SLOT_EMPTY) {
+			return NULL;
+		}
 	}
 }
 
@@ -521,7 +414,7 @@ void *BLI_edgehash_popkey(EdgeHash *eh, uint v0, uint v1)
  */
 bool BLI_edgehash_haskey(EdgeHash *eh, uint v0, uint v1)
 {
-	return (edgehash_lookup_entry(eh, v0, v1) != NULL);
+	return edgehash_lookup_entry(eh, v0, v1) != NULL;
 }
 
 /**
@@ -529,71 +422,34 @@ bool BLI_edgehash_haskey(EdgeHash *eh, uint v0, uint v1)
  */
 int BLI_edgehash_len(EdgeHash *eh)
 {
-	return (int)eh->nentries;
+	return (int)eh->length;
 }
 
 /**
  * Remove all edges from hash.
  */
-void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP valfreefp,
-                           const uint nentries_reserve)
+void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP free_value, const uint UNUSED(reserve))
 {
-	if (valfreefp)
-		edgehash_free_cb(eh, valfreefp);
-
-	eh->nbuckets = _ehash_hashsizes[0];  /* eh->cursize */
-	eh->nentries = 0;
-	eh->cursize = 0;
-
-	if (nentries_reserve) {
-		edgehash_buckets_reserve(eh, nentries_reserve);
-	}
-
-	MEM_freeN(eh->buckets);
-	eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
-
-	BLI_mempool_clear_ex(eh->epool, nentries_reserve ? (int)nentries_reserve : -1);
+	/* TODO: handle reserve */
+	edgehash_free_values(eh, free_value);
+	eh->length = 0;
+	eh->dummy_count = 0;
+	eh->capacity_exp = CAPACITY_EXP_DEFAULT;
+	CLEAR_MAP(eh);
 }
 
 /**
  * Wraps #BLI_edgehash_clear_ex with zero entries reserved.
  */
-void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp)
-{
-	BLI_edgehash_clear_ex(eh, valfreefp, 0);
-}
-
-void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp)
-{
-	BLI_assert((int)eh->nentries == BLI_mempool_len(eh->epool));
-
-	if (valfreefp)
-		edgehash_free_cb(eh, valfreefp);
-
-	BLI_mempool_destroy(eh->epool);
-
-	MEM_freeN(eh->buckets);
-	MEM_freeN(eh);
-}
-
-
-void BLI_edgehash_flag_set(EdgeHash *eh, uint flag)
-{
-	eh->flag |= flag;
-}
-
-void BLI_edgehash_flag_clear(EdgeHash *eh, uint flag)
+void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP free_value)
 {
-	eh->flag &= ~flag;
+	BLI_edgehash_clear_ex(eh, free_value, 0);
 }
 
 /** \} */
 
-
 /* -------------------------------------------------------------------- */
-/* EdgeHash Iterator API */
-
-/** \name Iterator API
+/** \name Edge Hash Iterator API
  * \{ */
 
 /**
@@ -603,7 +459,7 @@ void BLI_edgehash_flag_clear(EdgeHash *eh, uint flag)
  */
 EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh)
 {
-	EdgeHashIterator *ehi = MEM_mallocN(sizeof(*ehi), "eh iter");
+	EdgeHashIterator *ehi = MEM_mallocN(sizeof(EdgeHashIterator), __func__);
 	BLI_edgehashIterator_init(ehi, eh);
 	return ehi;
 }
@@ -618,37 +474,9 @@ EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh)
  */
 void BLI_edgehashIterator_init(EdgeHashIterator *ehi, EdgeHash *eh)
 {
-	ehi->eh = eh;
-	ehi->curEntry = NULL;
-	ehi->curBucket = UINT_MAX;  /* wraps to zero */
-	if (eh->nentries) {
-		do {
-			ehi->curBucket++;
-			if (UNLIKELY(ehi->curBucket == ehi->eh->nbuckets)) {
-				break;
-			}
-
-			ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
-		} while (!ehi->curEntry);
-	}
-}
-
-/**
- * Steps the iterator to the next index.
- */
-void BLI_edgehashIterator_step(EdgeHashIterator *ehi)
-{
-	if (ehi->curEntry) {
-		ehi->curEntry = ehi->curEntry->next;
-		while (!ehi->curEntry) {
-			ehi->curBucket++;
-			if (UNLIKELY(ehi->curBucket == ehi->eh->nbuckets)) {
-				break;
-			}
-
-			ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
-		}
-	}
+	ehi->entries = eh->entries;
+	ehi->length = eh->length;
+	ehi->index = 0;
 }
 
 /**
@@ -663,43 +491,71 @@ void BLI_edgehashIterator_free(EdgeHashIterator *ehi)
 /** \} */
 
 /* -------------------------------------------------------------------- */
-/* 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) (index) >= 0 && edges_equal((edge), (es)->entries[index])
 
-/** \name EdgeSet Functions
- * \{ */
-EdgeSet *BLI_edgeset_new_ex(const char *info,
-                                  const uint nentries_reserve)
-{
-	EdgeSet *es = (EdgeSet *)edgehash_new(info,
-	                                      nentries_reserve,
-	                                      sizeof(EdgeEntry) - sizeof(void *));
-#ifndef NDEBUG
-	((EdgeHash *)es)->flag |= EDGEHASH_FLAG_IS_SET;
-#endif
+EdgeSet *BLI_edgeset_new_ex(const char *info, const uint reserve)
+{
+	EdgeSet *es = MEM_mallocN(sizeof(EdgeSet), info);
+	es->capacity_exp = calc_capacity_exp_for_reserve(reserve);
+	UPDATE_SLOT_MASK(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)
 {
-	return BLI_edgeset_new_ex(info, 0);
+	return BLI_edgeset_new_ex(info, 1 << CAPACITY_EXP_DEFAULT);
+}
+
+void BLI_edgeset_free(EdgeSet *es)
+{
+	MEM_freeN(es->entries);
+	MEM_freeN(es->map);
+	MEM_freeN(es);
 }
 
 int BLI_edgeset_len(EdgeSet *es)
 {
-	return (int)((EdgeHash *)es)->nentries;
+	return (int)es->length;
 }
 
-/**
- * Adds the key to the set (no checks for unique keys!).
- * Matching #BLI_edgehash_insert
- */
-void BLI_edgeset_insert(EdgeSet *es, uint v0, uint v1)
+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)
 {
-	EDGE_ORD(v0, v1);
-	const uint bucket_index = edgehash_bucket_index((EdgeHash *)es, v0, v1);
-	edgehash_insert_ex_keyonly((EdgeHash *)es, v0, v1, bucket_index);
+	if (UNLIKELY(ENTRIES_CAPACITY(es) <= es->length)) {
+		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)
+{
+	es->entries[es->length] = edge;
+	es->map[slot] = (int)es->length;
+	es->length++;
 }
 
 /**
@@ -710,73 +566,63 @@ void BLI_edgeset_insert(EdgeSet *es, uint v0, uint v1)
  */
 bool BLI_edgeset_add(EdgeSet *es, uint v0, uint v1)
 {
-	EDGE_ORD(v0, v1);
-	const uint bucket_index = edgehash_bucket_index((EdgeHash *)es, v0, v1);
+	edgeset_ensure_can_insert(es);
+	Edge edge = init_edge(v0, v1);
 
-	EdgeEntry *e = edgehash_lookup_entry_ex((EdgeHash *)es, v0, v1, bucket_index);
-	if (e) {
-		return false;
-	}
-	else {
-		edgehash_insert_ex_keyonly((EdgeHash *)es, v0, v1, bucket_index);
-		return true;
+	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;
+		}
 	}
 }
 
-bool BLI_edgeset_haskey(EdgeSet *es, uint v0, uint v1)
+/**
+ * Adds the key to the set (no checks for unique keys!).
+ * Matching #BLI_edgehash_insert
+ */
+void BLI_edgeset_insert(EdgeSet *es, uint v0, uint v1)
 {
-	return (edgehash_lookup_entry((EdgeHash *)es, v0, v1) != NULL);
-}
+	edgeset_ensure_can_insert(es);
+	Edge edge = init_edge(v0, v1);
 
-
-void BLI_edgeset_free(EdgeSet *es)
-{
-	BLI_edgehash_free((EdgeHash *)es, NULL);
+	ITER_SLOTS(es, edge, slot, index) {
+		if (index == SLOT_EMPTY) {
+			edgeset_insert_at_slot(es, slot, edge);
+			return;
+		}
+	}
 }
 
-void BLI_edgeset_flag_set(EdgeSet *es, uint flag)
+bool BLI_edgeset_haskey(EdgeSet *es, uint v0, uint v1)
 {
-	((EdgeHash *)es)->flag |= flag;
-}
+	Edge edge = init_edge(v0, v1);
 
-void BLI_edgeset_flag_clear(EdgeSet *es, uint flag)
-{
-	((EdgeHash *)es)->flag &= ~flag;
+	ITER_SLOTS(es, edge, slot, index) {
+		if (ES_INDEX_HAS_EDGE(es, index, edge)) {
+			return true;
+		}
+		else if (index == SLOT_EMPTY) {
+			return false;
+		}
+	}
 }
 
-/** \} */
-
-/** \name Debugging & Introspection
- * \{ */
-#ifdef DEBUG
-
-/**
- * Measure how well the hash function performs
- * (1.0 is approx as good as random distribution).
- */
-double BLI_edgehash_calc_quality(EdgeHash *eh)
+EdgeSetIterator *BLI_edgesetIterator_new(EdgeSet *es)
 {
-	uint64_t sum = 0;
-	uint i;
-
-	if (eh->nentries == 0)
-		return -1.0;
-
-	for (i = 0; i < eh->nbuckets; i++) {
-		uint64_t count = 0;
-		EdgeEntry *e;
-		for (e = eh->buckets[i]; e; e = e->next) {
-			count += 1;
-		}
-		sum += count * (count + 1);
-	}
-	return ((double)sum * (double)eh->nbuckets /
-	        ((double)eh->nentries * (eh->nentries + 2 * eh->nbuckets - 1)));
+	EdgeSetIterator *esi = MEM_mallocN(sizeof(EdgeSetIterator), __func__);
+	esi->edges = es->entries;
+	esi->length = es->length;
+	esi->index = 0;
+	return esi;
 }
-double BLI_edgeset_calc_quality(EdgeSet *es)
+
+void BLI_edgesetIterator_free(EdgeSetIterator *esi)
 {
-	return BLI_edgehash_calc_quality((EdgeHash *)es);
+	MEM_freeN(esi);
 }
 
-#endif
 /** \} */