BLI: New Edgehash and EdgeSet implementation
[blender.git] / source / blender / blenlib / intern / edgehash.c
index 81bfb566278bdc336283938477654a9723247927..996c815a0624296af8a1fb99011418f4dc8a96ce 100644 (file)
  * 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>
 
 #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
 /** \} */